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.