Register Allocation - Introduction to Compiler Construction in a Java World - page 258

the interval's register (temporarily) to the rst split o part of current, and we put current
with the remaining split off part back on unhandled for further processing. So we make the
best use of registers that are assigned to intervals that are currently in holes.
If the current and the candidate interval do not intersect at all, then both intervals may
make use of the same physical register with no conflict; one interval is in a hole while the
other is making use of the shared register.
When we say we split the current interval at some optimal position, we are choosing
how much of the hole to take up for current's purposes. One could say we want as much as
possible, that is, all the way up to freePos. But, in the next section we shall see that this is
not always wise.
Consider the intervals for Factorial.computeIter() from Figure 7.2 and repeated in
Figure 7.5.
FIGURE 7.5 Liveness intervals for Factorial.computeIter() , again.
We rst assume we have four free physical registers ($t0{$t3) that we can allocate to
our seven virtual registers (V32{V38); that is, we invoke j-- with
>j---slinear-r4Factorial.java
The argument -s specifies that we are using linear scan; the -r4 says we are working with
four physical registers. Algorithm 7.4 does a linear scan through the seven virtual registers,
in order of their starting positions V32, V33,..., V38, as follows.
Algorithm 7.4 starts of with the list of seven unhandled intervals, an empty active list
and an empty inactive list. A trace of the linear scan process follows: 3 .
1. unhandled: [V32, V33, V34, V35, V36, V37, V38]
The first interval in the list is removed and becomes current. The active and inactive
lists remain empty. All four physical registers are available for allocation.
current = V32
active:
inactive:
free registers: [$t0, $t1, $t2, $t3]
The current interval, V32, is assigned the first free physical register $t0; V32 is put
on the active list for the next iteration.
3 In the trace, we do not italicize variables.