Improving Offset Assignment through Simultaneous Variable Coalescing [abstract] (PDF, PostScript)
Desiree Ottoni, Guilherme Ottoni, Guido Araujo, and Rainer Leupers
Proceedings of the 7th International Workshop on Software and Compilers for Embedded Systems, LNCS 2826 (SCOPES), September 2003.
Best Paper Award.
Efficient address code optimization is a central problem
in code generation for processors with restricted addressing modes,
like Digital Signal Processors (DSPs). This paper proposes a new
heuristic to solve the Simple Offset Assignment (SOA) problem, the
problem of allocating scalar variables to memory so as to minimize
addressing code. This new approach, called Coalescing SOA (CSOA),
performs variable memory slot coalescing simultaneously to offset
assignment computation. Experimental results, based on compiling
MediaBench benchmark programs with LANCE compiler, reveal a very
significant improvement over the previous solutions to SOA. In fact,
CSOA produces, on average, 37.3% fewer update instructions when
comparing with the prior solution that perform memory slot coalescing
before applying SOA, and 66.2% fewer update instructions when
comparing with the best traditional SOA solution.