Java Reference
In-Depth Information
doubleSum(){
initVal = $a0;
// First parm passed in $a0
limit = $a1;
// Second parm passed in $a1
sum = initVal;
i=1;
temp1 = i <= limit;
while (temp1) {
temp2 = sum + i;
sum = temp2;
temp3 = i + 1;
i = temp3;
temp1 = i <= limit; }
temp4 = 2 * sum;
$v0 = temp4; // Return value register is $v0
}
Figure 13.18: Subprogram doubleSum with initial register assignments
a=b, an explicit register copy can be avoided if a and b are allocated to
the same register. Values a and b will be automatically assigned to the same
register if we
coalesce
their live ranges. That is, if we combine the nodes for a
and b in the interference graph, then a and b must receive the same register.
When is coalescing a and b safe? At a minimum, they must not interfere.
If they do interfere, then they are live at the same time and will need distinct
registers. Even if a and b do not interfere, coalescing themmay be problematic.
The di
culty is that combining the live ranges of a and b will in general create
a larger live range that is harder to color. We certainly do not want to spill
a combined range when the individual ranges might have been individually
colored.
To avoid problems in coloring coalesced interference graph nodes we
can adopt a
conservative coalescing
approach. We will say a node in an
interference graph has
significant degree
if it has
n
or more neighbors (where
n
is the number of colors available). A node of significant degree may have
to be spilled. A node that has
insignificant degree
(i.e., is not significant)
is always colorable. We can conservatively coalesce nodes
a
and
b
if the
combined interference graph node has fewer than
n
significant neighbors. This
is because insignificant neighbors are always removed since they are trivially
colorable. If the combined node has fewer than
n
significant neighbors, then,
after insignificant neighbors are removed, the combined node will have fewer
than
n
neighbors, so it too will be trivially colorable.
