Address Register Allocation for Arrays in Loops of Embedded Programs [abstract] (PDF, PostScript)
Guilherme Ottoni and Guido Araujo
Microelectronics Journal -- Special Issue on IEEE Workshop on Embedded System Codesign, Volume 34, Number 11, November 2003.
Efficient address register allocation has been shown to be a central
problem in code generation for processors with restricted addressing
modes. This paper extends previous work on Global Array Reference
Allocation (GARA), the problem of allocating address registers to
array references in loops. It describes two heuristics to the problem,
presenting experimental data to support them. In addition, it proposes
an approach to solve GARA optimally which, albeit computationally
exponential, is useful to measure the efficiency of other
methods. Experimental results, using the MediaBench benchmark and
profiling information, reveal that the proposed heuristics can solve
the majority of the benchmark loops near optimality in
polynomial-time. A substantial execution time speedup is reported for
the benchmark programs, after compiled with the original and the
optimized versions of GCC.