Java Reference
In-Depth Information
procedure
GCR
eg
A
lloc
(
proc
,
regCount
)
ig
← build
I
nterference
G
raph
(
proc
)
stack
←∅
while
ig
∅
do
if
∃
d
∈
ig
|
neighborCount
(
d
)
<
regCount
then
ig
←
ig
−{
d
}
call
push
(
d
)
else
d
← find
S
pill
N
ode
(
ig
)
ig
←
ig
−{
d
}
/
Generate code to spill
d
's live range
/
while
stack
∅
do
d
← pop
()
reg
(
d
)
←
any register not assigned to
neighbors
(
d
)
end
function
find
S
pill
N
ode
(
ig
)
returns
Node
bestCost
←∞
foreach
n
∈
ig
do
if
cost
(
n
)
neighborCount
(
n
)
<
bestCost
then
ans
←
n
bestCost
←
cost
(
n
)
neighborCount
(
n
)
return
(
ans
)
end
Figure 13.16: Chaitin's graph coloring register allocator.
interferences that will be removed by spilling the node. Chaitin suggests that
the node with the smallest value of
cost
/
neighbors
is the best node to spill. That
is, the ideal node to spill is one that has a low spill cost and many neighbors,
yielding a very small
cost
/
neighbors
value.
Chaitin's algorithm is shown in Figure 13.16. As an example, consider the
interference graph of Figure 13.15. Assume only two registers are available for
allocation. Since c has only one neighbor, it is immediately removed from the
graph and pushed on a stack for later register allocation. a, b,andi all have
two neighbors. One will have to be spilled. a has a very low cost (3) because
it is referenced only 3 times, all outside of the loop. b and i are used inside
the loop and have much higher costs. Since all three nodes have the same
number of neighbors, a is correctly chosen as the proper node to spill. After
a is removed, i and b become unconstrained. When registers are assigned, i
and b get di
ff
erent registers and c can be assigned either register. a gets no
