Java Reference
In-Depth Information
The problem of determining whether a graph is “
n
-colorable” is NP-
complete [GJ79]. This means the best-known algorithms that solve this prob-
lem exactly have a time bound that is exponential in the size of the graph. As
a result, register allocators based on graph coloring normally use
heuristics
to
solve the coloring problem approximately.
We will first consider an approach to register allocation using coloring
devised by Chaitin [CAC
+
81]. Initially, the algorithm assumes that all register
candidates can be allocated registers. This is often an impossible goal, so
the interference graph is tested to see if it is
n
-colorable (the NP-complete
problem, whichwe discuss below), where
n
is the number of registers available
for allocation. If the interference graph is
n
-colorable, a register allocation is
produced from the colors assigned to the interference graph.
If the graph is not
n
-colorable, it is simplified. A node (corresponding to
a live range) is selected and spilled. That is, the live range is denied a register.
Instead, whenever it is assigned to or used, it is loaded from or stored into
memory usingwork registers (similar to the pseudo-registers of Section 13.3.1).
Since the live range that was spilled is no longer a register candidate it is
removed from the interference graph. The graph is simpler andmay now be
n
-
colorable. If it is, our register allocation is successful; all remaining candidates
can be allocated registers. If the graph still is not
n
-colorable, we select and
spill another candidate, further simplifying the graph. This process continues
until an
n
-colorable graph is obtained.
Two questions arise. How do we decide if a graph is
n
-colorable? (Recall
this is currently considered to be a very hard problem.) If a graph is not
n
-colorable, how do we choose the “right” register candidate to spill?
In testing for
n
-colorability, Chaitin made the following simple but power-
ful observation. If a node in the interference graph has fewer than
n
neighbors,
that node can always be colored (just choose any color not assigned to any of
its neighbors). Such nodes (termed
unconstrained nodes
) are removed from
the interference graph. This simplifies the graph, often making further nodes
unconstrained. Sometimes all nodes are removed, demonstrating that the
graph is
n
-colorable.
When only nodes with
n
or more neighbors remain, a node is spilled to
allow the graph to be simplified. Chaitin suggests that in choosing a node to
spill, two criteria be considered. First, the
cost
of spilling a node should be
considered. That is, we compute the extra loads and stores that will have to
be executed should a live range be spilled, weighted by the loop nesting level.
Each level of loop nesting is arbitrarily assumedtoaddafactorof10tocosts.
Thus a live range in a single loop has its loads and stores multiplied by 10, a
doubly nested loop multiplies loads and stores by 100, etc.
The second criterion Chaitin used is the number of
neighbors
anodehas.
The greater the number of neighbors a node has, the greater the number of
