Java Reference
In-Depth Information
doubleSum(){
$v0 = 1;
$t0 = $v0 <= $a1;
while ($t0) {
$a0 = $a0 + $v0;
$v0 = $v0 + 1;
$t0 = $v0 <= $a1;
}
$v0 = 2 * $a0;
}
Figure 13.19: Subprogram doubleSum after register allocation
In our above doubleSum example, we have three values that must be
register-resident (the two parameter values at the start, and the return value
at the end). We have eight local variables and temporaries (initVal, limit, i,
sum, temp1, temp2, temp3,andtemp4). We will aim for a 4-coloring (a register
allocation that uses 4 registers). Temporary temp1 interferes with i, limit,and
sum, so we know that we cannot use fewer than 4 registers without spilling.
We can coa l e s c e temp4 and $v0, guaranteeing that 2*sum is computed into
the return value register. We can coalesce $a0 and initVal, allowing initVal
to be accessed directly from $a0 throughout the subprogram. Even more
interestingly, we can then coalesce initVal and sum, allowing sum to use $a0
as well. Temporary temp2 can also be coalesced with sum, allowing it to use
$a0 also. limit can be coalesced with $a1, allowing it to use $a1 throughout
the subprogram.
Tempor a ry temp3 can be coalesced with i since the combined node has
fewer than 4 neighbors. Since neither temp1 nor the combined i and temp3
interfere with $v0, either of these can be assigned $v0 to use. The other is
assigned an unused register, for example $t0. The resulting register alloca-
tion, with register names replacing variables and temporaries, is shown in
Figure 13.19. Note that all register-to-register copies have been removed, and
that only one register, beyond the preassigned ones, is used.
It is sometimes possible to coalesce interference graph nodes that have
more than n significant neighbors. This is done by iterating between interfer-
ence graph simplification and node coalescing [GA96]. The resulting algorithm
is very e
ff
ective, and is one of the simplest andmost e
ff
ective register allocators
in current use.
Search WWH ::




Custom Search