Global Address Register Allocation for Array References in DSPs [abstract] (PDF, PostScript)
Guilherme de Lima Ottoni
Master's Thesis, Institute of Computing,
Universidade Estadual de Campinas (UNICAMP), December 2002.
Best Master's Thesis Award (2nd Prize Nationwide).
The technological advances in computing systems have stimulated the
growth of the embedded systems market, which is continuously becoming
more ordinary in people's lives, for example in mobile phones,
palmtops and automotive control systems. Because of their
characteristics, these new applications demand the combination of low
cost, high performance and low power consumption. One way to meet
these constraints is through the design of specialized processors.
However, processor specialization imposes new challenges to the
development of software for these systems. In particular, compilers
-- generally responsible for code optimization -- need to be adapted
in order to produce efficient code for these new processors.
In the digital signal processing arena, such as in cellular
telephones, specialized processors, known as DSPs (Digital Signal
Processors), are largely used. DSPs typically have few general purpose
registers and very restricted addressing modes. In addition, many DSP
applications include large data streams processing, which are usually
stored in arrays. As a result, studing array reference optimization
techniques became an important task in compiling for DSPs. This work
studies this problem, known as Global Array Reference
Allocation (GARA). The central GARA subproblem consists of
determining, for a given set of array references to be allocated to
the same address register, the minimum cost of the instructions
required to keep this register with the correct address at all program
points. In this work, this subproblem is modeled as a graph
theoretical problem and proved to be NP-hard. In addition, an
efficient algorithm, based on dynamic programming, is proposed to
optimally solve this subproblem under some restrictions. Based on
this algorithm, two techniques to solve GARA are proposed.
Experimental results, from the implementation of these techniques in
the GCC compiler, compare them with previous work in the
literature. The results show the effectiveness of the techniques
proposed in this work.