The Power of Belady's Algorithm in Register Allocation
for Long Basic Blocks
Jia Guo, Maria Jesus Garzaran, David Padua
To appear at
16th Workshop on Languages and Compilers for Parallel Computing (LCPC03), College Station, TX, 2-4 October 2003
Full Text, Printable Abstract.
Abstract
Optimization techniques such as loop-unrolling and
trace-scheduling can result in long straight-line
codes. It is, however, unclear how well the register
allocation algorithms of current compilers perform on
these codes. Compilers may well have been optimized
for human written codes, which are likely to have
short basic blocks. To evaluate how state-of the
art compilers behave on long straight-line codes
we wrote a compiler that implements the simple
Belady's MIN algorithm.
The main contribution of this paper is the evaluation
of Belady's MIN algorithm when used for register
allocation for long straight-line codes. These
codes were executed on a MIPS R12000 processor.
Our results show that applications compiled using
Belady's MIN algorithm run faster than when
compiled with the MIPSPro or GCC compiler. In
particular, Fast Fourier Transforms (FFTs) of
size 32 and 64 run 12% and 33% faster than when
compiled using the MIPSPro compiler.