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.