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

At the end of the linear scan allocation, all intervals have been assigned physical registers
and the LIR now looks as follows:
B0
B1
0:LDC[1]$t0
5:MOVE$a0$t1
10:MOVE$t0$t2
B2
15:LDC[0]$t0
20:BRANCH[LE]$t1$t0B4
B3
25:LDC[-1]$t0
30:ADD$t1$t0$t3
35:MUL$t2$t1$t0
40:MOVE$t0$t2
45:MOVE$t3$t1
50:BRANCHB2
B4
55:MOVE$t2$v0
60:RETURN$v0
Now, if no register is free to be assigned to current even for a portion of its lifetime, then
we must spill some interval to a memory location on the stack frame. We use Algorithm
7.6 [Wimmer, 2004] to select an interval for spilling and to assign the freed register to
current. The algorithm chooses to spill that register that is not used for the longest time|
that register next used at the highest position in the code.
Algorithm 7.6 describes the behavior of the method foundFreeRegisterFor(). This algo-
rithm collects two positions for each physical register r by iterating through all active and
inactive intervals:
1. usePos[r] records the position where an interval with register r assigned is used next.
If more than one use position is available, the minimum is used. It is used in selecting
a spill candidate.
2. blockPos[r] records a (minimum) hard limit where register r cannot be freed by
spilling. Because this is a candidate value for usePos, usePos can never be higher
than this hard blockPos.
The register with the highest usePos is selected as a candidate for spilling. Based on the
use positions, the algorithm identifies three possibilities:
1. It is better to spill current if its first use position is found after the candidate with
the highest usePos. We split current before its first use position where it must be
reloaded; the active and inactive intervals are left untouched. This case also applies if
all registers are blocked at a method-call site.
2. Otherwise, current is assigned the selected register. All inactive and active intervals
for this register intersecting with current are split before the start of current and
spilled. We need not consider these split children further because they do not have a
register assigned. But if they have use positions requiring a register, they will have to
be reloaded to some register so they are split a second time before the use positions
and the second split children are sorted back into unhandled. They will get a register
assigned when the allocator has advanced to their position.