Java Reference
In-Depth Information
int doubleSum(int initVal, int limit){
int sum = initVal;
for (int i=1; i <= limit; i++)
sum += i;
return 2*sum;
}
Figure 13.17: The subprogram doubleSum
register. Rather, whenever it is used, it is loaded from or stored into a memory
location, just like an ordinary variable.
Improvements to Graph Coloring Register Allocators
Briggs et al. [BCT94] suggest a number of useful improvements to Chaitin's
approach. They point out that nodes with the smallest number of neighbors
ought to be removed first from the interference graph. This is because nodes
with fewneighbors are the easiest to color andhence they ought to be processed
last during the phase in which stacked nodes are popped and colored.
Another improvement follows from the observation that as nodes are re-
moved to simplify the interference graph, they need not be spilled immediately.
Rather, removed nodes should be stacked just like unconstrained nodes. When
nodes are colored, constrained nodes may be colorable (because they happen
to have neighbors that share the same color or happen to have neighbors that
are also marked to be spilled). Constrained nodes that cannot be colored are
spilled only when we are sure they are uncolorable.
Register allocators need to handle two other problems. Assignments be-
tween register values are common. We would like to reduce register moves by
assigning the source and target values in the assignment to the same register,
making the assignment a trivial one. Moreover, architectural and operating
system constraints sometimes force values to be assigned to specific registers.
Wewould like our allocator to try to choose register assignments that anticipate
and adhere to predetermined register conventions.
To see how coloring allocators can handle register moves and preallocated
registers, consider the simple subprogram doubleSum shown in Figure 13.17.
When doubleSum is translated, many short-lived temporary locations are cre-
ated. Moreover, rules involving register allocation for parameters and return
values are enforced. Prior to register allocation, doubleSumhas the formshown
in Figure 13.18.
The explicit use of register names in doubleSum represents live ranges that
must be assigned to a particular register; such nodes are said to be
precolored
.
If variables a and b are both allocated to registers, and we have the assignment
