|[HGG:2006:RA_SSA]||Sebastian Hack, Daniel Grund, Gerhard Goos, Register allocation for programs in SSA-form, Andreas Zeller, Alan Mycroft (Ed.), Compiler Construction 2006, Springer, March 2006.
As register allocation is one of the most important phases
in optimizing compilers, much work has been done to improve its quality
and speed. We present a novel register allocation architecture for
programs in SSA-form which simplifies register allocation significantly.
We investigate certain properties of SSA-programs and their interference
graphs, showing that they belong to the class of chordal graphs.
This leads to a quadratic-time optimal coloring algorithm and allows for
decoupling the tasks of coloring, spilling and coalescing completely. After
presenting heuristic methods for spilling and coalescing, we compare
our coalescing heuristic to an optimal method based on integer linear