Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


ucin982089462.pdf (880.26 KB)

ETD Abstract Container

Abstract Header

A Just in Time Register Allocation and Code Optimization Framework for Embedded Systems

Thammanur, Sathyanarayan
http://rave.ohiolink.edu/etdc/view?acc_num=ucin982089462

Abstract Details

2001, MS, University of Cincinnati, Engineering : Computer Engineering.
Mobile programs are being used extensively to be run on embedded systems. These programs typically needs to be downloaded as code slices onto the embedded device. Code slices on embedded system would be compiled “just-in-time” and run. Code size is an important issue for such embedded systems. Register allocators in current literature have always targeted speed of execution as their key issue and hence are not suited for embedded systems. We describe a “just-in-time”, usage density based register allocator geared towards systems with limited general purpose register set wherein speed, code size and memory requirements are equally of concern. The main attraction of the allocator is that it does not make use of the traditional live range and interval analysis nor performs advanced optimizations based on range splitting or spilling but results in very good code quality. We circumvent the need for traditional analysis by using a measure of usage density of a variable. The usage density of a variable at a program point represents both the frequency and the density of the uses. We contend that using this measure we can capture both range and frequency information which is essentially used by the good allocators based on splitting and spilling. We describe a two-pass framework based on this measure which has a linear complexity in terms of the program size. We perform comparisons with the static allocators based on graph coloring and the ones targeted towards dynamic compilation systems like linear scan of live ranges. We have implemented our allocator inside the tcc compiler. We find that the usage density allocator generates a better code quality than the other allocators for smaller set of registers. Our results show an improvement over Briggs-style allocator in reducing code size of up to 12% for a register set of size 16 in some cases. The results are interesting with decreasing register set size in terms of both code size as well as memory requirements. The algorithm is of interest in applications where speed, code size and the memory requirements are all equally of concern like embedded processors with limited general purpose register set and “just-in-time” compilers. To optimize the code size further, we also developed a Dynamic Dead Code Elimination framework which selectively removes branches within the loops and reduces the mobile code slice to be transmitted to the embedded device. We found that there were some opportunities that were exploited by this framework. We present the results for the same.
Dr. Santosh Pande (Advisor)
100 p.
compiler optimizations; dynamic compilation; code generation; register allocation

Recommended Citations

Citations

  • Thammanur, S. (2001). A Just in Time Register Allocation and Code Optimization Framework for Embedded Systems [Master's thesis, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin982089462

    APA Style (7th edition)

  • Thammanur, Sathyanarayan. A Just in Time Register Allocation and Code Optimization Framework for Embedded Systems. 2001. University of Cincinnati, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin982089462.

    MLA Style (8th edition)

  • Thammanur, Sathyanarayan. "A Just in Time Register Allocation and Code Optimization Framework for Embedded Systems." Master's thesis, University of Cincinnati, 2001. http://rave.ohiolink.edu/etdc/view?acc_num=ucin982089462

    Chicago Manual of Style (17th edition)

ucin982089462
819
© 2001, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.