News

Offset Assignment Using Simultaneous Variable Coalescing [abstract] (ACM DL, PDF, PostScript)
Desiree Ottoni, Guilherme Ottoni, Guido Araujo, and Rainer Leupers
ACM Transactions on Embedded Computing Systems (TECS), Volume 5, Number 4, November 2006.

The generation of efficient addressing code is a central problem in compiling for processors with restricted addressing modes, like Digital Signal Processors (DSPs). Offset Assignment (OA) is the problem of allocating scalar variables to memory, so as to minimize the need of addressing instructions. This problem is called Simple Offset Assignment (SOA) when a single address register is available, and General Offset Assignment (GOA) when more address registers are used. This paper shows how variables' liveness information can be used to dramatically reduce the addressing instructions required to access local variables on the program stack. Two techniques that make effective use of variable coalescing to solve SOA and GOA are described, namely Coalescing SOA (CSOA) and Coalescing GOA (CGOA). In addition, a thorough comparison between these algorithms and others described in the literature is presented. The experimental results, when compiling MediaBench benchmark programs with the LANCE compiler, reveal a very significant improvement of the proposed techniques over the other available solutions to the problem.