Java Reference
In-Depth Information
Hennessy and Chow [CH90] and Larus and Hilfinger [LH86] suggest inter-
esting alternatives to Chaitin's graph coloring approach. After unconstrained
nodes (which are trivially colorable) are removed from the interference graph,
a
priority
is computed for each remaining node. This priority is similar to
Chaitin's cost estimate, except that it normalizes the cost using the size of the
live range. That is, if two live ranges have the same cost, but one is smaller
(in terms of the number of instructions it spans), the smaller live range ought
to be given preference over the larger one. Thus, the smaller the live range is,
the shorter the span of instructions in which it ties up a register. The priority
function recommended is
cost
/
size
(
liverange
). The greater the priority of a live
range, the more likely it is to receive a register.
Another important di
erence is that when a node cannot be colored (be-
cause its neighbors have been allocated all of the available colors), the node
is
split
rather than being spilled. That is, if possible, the live range is divided
into two smaller live ranges. Loads and stores are placed at the boundary of
the split ranges, but each
split live range
may be allocated a (possibly di
ff
er-
ent) register. Because split ranges usually have fewer interferences than the
original range, split ranges are often colorable when the original range is not.
There are many ways a live range may be split into smaller ranges. The
following simple heuristic is often used:
ff
1. Remove the first instruction of the live range (usually a load or compu-
tation), putting it into a new live range,
NR
.
2. Move successors to instructions in
NR
from the original live range to
NR
as long as
NR
remains colorable.
at least one instruction, and then add instructions
as long as the split range appears colorable. Instructions not split o
The idea is to break o
ff
remain
in what is left of the original live range, which may be split again. Single
definitions or uses that cannot be colored are spilled.
A priority-based register allocator, P
ff
, is shown in Fig-
ure 13.20. Reconsider the interference graph of Figure 13.15, assuming two
registers, $r1 and $r2.Variablec is unconstrained; it is trivial to color and
will be handled after all other variables have been allocated registers. a, b,
and i are all constrained. i has the highest priority for register allocation,
since assigning it a register saves 51 loads and stores, and it spans only two
statements. Assume it is assigned register $r1.Variableb has the next highest
priority (22 loads and stores saved). It is given $r2.Variablea is the last
candidate in
constrained
, but it cannot be colored. We split it into two smaller
live ranges, a1 and a2. a1 is the single assignment at the top of the procedure.
Range a2 spans the two print statements. a1 is e
riority
R
eg
A
lloc
ff
ectively spilled since its
