Register Allocation - Introduction to Compiler Construction in a Java World - page 271

FIGURE 7.9 Pruning an interference graph.
Graph Coloring Register Allocation Algorithm
Algorithm 7.9 performs graph coloring register allocation based on that of ([Muchnick,
1997]). The algorithm attempts to coalesce virtual registers where there is a move from
one to the next and the two registers' intervals do not conict. Also, once spill code is
generated, it repeats the register allocation process. It does this repeatedly until it succeeds
in assigning physical registers to virtual registers without introducing additional spills.