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

3. If the selected register has a blockPos in the middle of current, then it is not available
for current's entire lifetime; current is split before blockPos and the sorted child is
sorted into unhandled. (That the current interval starts before a use is probably the
result of a previous split.)
4. Notice that neither loads nor stores are actually generated in the LIR. This will be
done later based on the split intervals. This differs slightly from [Wimmer, 2004],
which (apparently) generates the loads and stores local to a block immediately, and
leaves those needed in other blocks to a (global) data-flow resolver.
Either current gets spilled or current is assigned a register. Many new split children may
be sorted into unhandled, but the allocator always advances position and so will eventually
terminate.
Algorithm 7.6 Spill and Allocate a Blocked Register
Input: The current interval current, from Algorithm 7.4
Output: A register is spilled and assigned to the current interval
for physical register r in the set of physical registers do
usePos[r] blockPos[r] maxInt
end for
for non-fixed interval i in active do
usePos[i.reg] min(usePos[i.reg], next usage of i after current.rstRange.from)
end for
for non-fixed interval i in inactive do
if i intersects with current then
usePos[i.reg] min(usePos[i.reg], next usage of i after current.rstRange.from)
end if
end for
for fixed interval i in active do
usePos[i] blockPos[i] 0
end for
for fixed interval i in inactive do
blockPos[i.reg] next intersection of i with current
usePos[i.reg] min(usePos[i.reg], blockPos[i.reg])
end for
register reg register with highest usePos
if usePos[reg] < first usage of current then
// all intervals are used before current ) spill current itself
assign a spill slot on stack frame to current
split current at an optimal position before first use position requiring a register
else if blockPos[reg] > current.lastRange.to then
// spilling frees reg for all of current
assign a spill slot on stack frame to child interval for reg
assign register reg to interval current
split, assign a stack slot, and spill intersecting active and inactive intervals for reg
else
// spilling frees reg for first part of current
assign a spill slot on stack frame to child interval for reg
assign register reg to interval current
split current at optimal position before blockPos[reg]
split, assign a stack slot, and spill intersecting active and inactive intervals for reg
end if