Java Reference
In-Depth Information
1. The first, called the degree < R rule, derives from the fact that a graph with a node
of degree <R (that is a node with <R adjacent nodes) is R-colorable if and only
if the graph with that node removed is R-colorable. We may use this rule to prune
the graph, removing one node of degree <R at a time and pushing it onto a stack;
removing nodes from the graph removes corresponding edges, potentially creating
more nodes with degree <R. We continue removing nodes until either all nodes have
been pruned or until we reach a state where all remaining nodes have degrees R.
2. The second is called the optimistic heuristic and allows us to continue pruning nodes
even with degree R. We use a heuristic function spillCost() to nd a node having
the smallest cost of spilling its associated virtual register; we mark that register for
possible spilling and remove the node (and its edges) and push it onto the stack in
the hope that we will not really have to spill it later. (Just because a node has degree
R does not mean the nodes need different colors.)
Let us attempt to prune the interference graph in Figure 7.8 where R = 3, meaning we have
three physical registers to work with. In this case, we need to invoke just the first degree < R
rule. The steps to pruning the graph are illustrated in Figure 7.9. Figure 7.9 pretty much
speaks for itself. We start with V32, which (in Figure 7.9(a)) has just one adjacent interval,
remove it, and push it onto the stack to give us the graph in Figure 7.9(b). We continue
in this way until all nodes have been removed and pushed onto the stack. Removing nodes
with degree < 3 causes edges to be removed and so more nodes end up with degree < 3.
We may then pop the virtual registers off the list, one at a time, and try to assign
physical register numbers (r1, r2, or r3) to each in such a way that adjacent virtual registers
(in the graph) are never assigned the same physical register. A possible assignment is
V38 r1
V37 r2
V34 r3
V33 r1
V36 r2
V35 r2
V32 r2
Imposing this mapping onto our LIR for Factorial.computeIter() gives us
B0
B1
0:LDC[1]r2
5:MOVE$a0r1
10:MOVEr2r3
B2
15:LDC[0]r2
20:BRANCH[LE]r1r2B4
B3
25:LDC[-1]r2
30:ADDr1r2r2
35:MULr3r1r1
40:MOVEr1r3
45:MOVEr2r1
50:BRANCHB2
B4
55:MOVEr3$v0
60:RETURN$v0
 
Search WWH ::




Custom Search