TABLE OF CONTENTS In most compiler courses, we teach students that the problem of scalar register allocation has essentially been solved by the register coloring techniques pioneered by Chaitin and his colleagues at IBM research [69, 68] and refined by Chow and Hennessy at Stanford [76] and by Briggs et al. at Rice [45].
These techniques attempt to allocate all of the uses of each scalar variable in a single "live range" the program region through which the given variable is live to a register. To accomplish this, the compiler typically carries out the following steps:
It identifies the live ranges of variables and gives each a unique name.
It builds an interference graph to model which pairs of live ranges cannot be assigned to the same register.
Using a fast heuristic coloring algorithm, it attempts to color the resulting interference graph with a number of colors equal to the number of registers available.
If the coloring fails, it forces at least one live range out of registers and repeats the attempt to color beginning at step 3.
This approach is used in the C and Fortran compilers for every RISC processor known to the authors. In practice, this method is very effective. In most small routines it produces a perfect allocation, in which every nonarray variable is assigned to a register throughout every one of its live ranges. Thus, conventional wisdom says that nothing more can be done to improve register usage on a uniprocessor.
However, conventional wisdom fails to...
