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

Algorithm 7.5 Attempting to Allocate a Free Register
Input: The current interval current, from Algorithm 7.4
Output: true if a free register was assigned to the current interval; false if no free register
was found
List unhandled a list of all intervals, sorted in increasing start-position order
for physical register r in the set of physical registers do
freePos[r] maxInt //

default

end for
for interval i in active do
freePos[i.reg] 0 // unavailable
end for
for interval i in inactive do
if i intersects with current then
freePos[i.reg] min(freePos[i.reg], next intersection of i with current)
end if
end for
register reg register with highest freePos
if freePos[reg] = 0 then
return false // failure
else if freePos[reg] > current.lastRange.to then
// available for all of current interval
current.r reg // assign it to current interval
else
// register available for first part of current
current.r reg // assign it to current interval
// split current at optimal position before freePos[reg]
put current with the split-off part back on unhandled
end if
return true // success

The array freePos[] is used to compute the next position that each register is used; the
register is free up until that position. The element freePos[r] records this position for the
physical register (numbered) r.
By default, all physical registers are free for the lifetime of the method; hence, the freePos
is maxInt. But none of the physical registers assigned to intervals that are on the active
list are free; hence the freePos is 0. But registers assigned to intervals that are inactive
(and so in a hole) are assigned a freePos equal to the next position that the current interval
intersects with the interval in question, that is, the position where both intervals would need
the same register; the register is free to be assigned to the current interval up until that
position. Because the same physical register may (because of previous splits) have several
next use positions, we choose the closest (the minimum) for freePos.
So, when we choose the register with the highest freePos, we are choosing that register
that will be free the longest.
If the chosen register has a freePos of 0, then neither it nor any other register is free
and so we return false to signal we will have to spill some register. But if its freePos is
greater than the to position of current's last range, then it is available for the duration
of current and so is assigned to current. Otherwise, the interval we are considering is in
a hole; indeed, it is in a hole that extends the furthest of any other interval in a hole. Its
register is available to the current interval up until that position. So we split the current
interval at some optimal position between the current position and that freePos, we assign