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

register or liveness interval, and a set of edges. There is an edge between two nodes if the
corresponding intervals interfere, that is, if they are live at the same time.
For example, reconsider the liveness intervals for the virtual registers V32 to V38 of
Factorial.computeIter() , originally in Figure 7.2 but repeated here as Figure 7.7.
FIGURE 7.7 Liveness intervals for Factorial.computeIter() , yet again.
Figure 7.8 shows the corresponding interference graph.
FIGURE 7.8 Interference graph for intervals for Factorial.computeIter() .
We need not draw an arc from the node for a virtual register we are using to the node
for the virtual register we are defining. For example, at position 10, the instruction
10:MOVE[V32|I][V34|I]
uses V32 to define virtual register V34; so the interval for V32 ends where the interval for
V34 begins. So we draw no edge from V32 to V34.
Register allocation then becomes coloring the graph but using physical registers as the
colors. The question becomes: can the graph be \colored" such that no two adjacent nodes
(that is no two intervals that are live at the same time) share the same physical register?
John Cocke was the first person to see that register allocation could be modeled as graph
coloring [Allen and Kennedy, 2002]. Gregory Chaitin and colleagues ([Chaitin et al., 1981]
and [Chaitin, 1982]) implemented such an allocator at IBM in 1981.
We say that a graph has an R-coloring if it can be colored using R distinct colors, or
in our case R distinct physical registers. To exhaustively find such an R-coloring for R
2 has long been known to be NP-complete. But there are two heuristics available to us for
simplifying the graph.