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

Algorithm 7.4 Linear Scan Register Allocation
Input: The control-flow graph g for a method with its associated liveness intervals
Output: A version of the LIR where all virtual registers are mapped to physical registers,
and code for any necessary spills, has been inserted into the LIR
List unhandled a list of all intervals, sorted in increasing start-position order
List active fg
List inactive fg
List handled fg
while unhandled 6= fg do
current rst interval removed from unhandled
position current.rstRange.from
for interval i in active do
if i.lastRange.to < position then
move i from active to handled
else if i.covers(position) then
move i from active to inactive
end if
end for
for interval i in inactive do
if i.lastRange.to < position then
move i from inactive to handled
else if i.covers(position) then
move i from inactive to inactive
end if
end for
if foundFreeRegisterFor(current) then
allocateBlockedRegisterFor(current)
end if
end while
The algorithm scans through the unhandled intervals one at a time, finding a physical
register for each; in the first instance, it looks for a free physical register and, if it fails at
that, it looks for a register to spill. In either case, a split may occur, creating an additional
interval and sorting it back into unhandled. Before allocating a register, the algorithm does
a little bookkeeping: based on the new position (the start of the current interval), it moves
intervals among the lists.
The method foundFreeRegisterFor() takes an interval as its argument and attempts to
map it to a freely available register; if it is successful, it returns true ; if unsuccessful in
finding a free register, it returns false . In the latter case, the linear scan algorithm calls
upon the method allocateBlockedRegisterFor(), which determines which register should be
spilled so that it can be allocated to the interval.
Algorithm 7.5 describes the behavior of the method foundFreeRegisterFor() .