Efficient Array Reference Allocation for Loops in Embedded Processors [abstract]
Guilherme Ottoni and Guido Araujo
Proceedings of the IEEE Workshop on Embedded System Codesign, September 2002.
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, 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.