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

Algorithm 7.3 Building Liveness Intervals
Input: The control-flow graph g for a method with LIR, and the liveIn and liveOut sets
for each basic block
Output: A liveness interval for each register, with ranges and use positions
for block b in g.blocks in reverse order do
int blockFrom b.rstInstruction.id
Set blockTo b.lastInstruction.id
for register r in b.liveOut do
intervals[r].addOrExtendRange(blockFrom, blockRange)
end for
for instruction i in b.instructions in reverse order do
if i.isAMethodCall then
for physical register r in the set of physical registers do
intervals[r].addRange(i.id, i.id)
end for
end if
for virtual register r in i.writeOperands do
intervals[r].rstRange.from i.id
intervals[r].addUsePos(i.id)
end for
for virtual register r in i.readOperands do
intervals[r].addOrExtendRange(blockFrom, i.id)
intervals[r].addUsePos(i.id)
end for
end for
end for
Before we even look at the LIR instructions, we add ranges for all registers that are live
out. These ranges must extend to the end of the block because they are live out. Initially,
we define the ranges to extend from the start of the block because they may have been
defined in a predecessor; if we later find they are defined (or redefined) in the block, then
we shorten this range by overwriting the from position with the defining position.
As we iterate through the instructions of each block, in reverse order, we add or modify
ranges:
When we encounter a subroutine call, we add ranges of length 1 at the call's position
to the intervals of all physical registers. The reason for this is that we must assume
the subroutine itself will use these registers and so we would want to force spills.
In our current implementation, we do not do this step. Rather, we treat all registers
as callee-saved registers, making it the responsibility of the called subroutine to save
any physical registers that it uses. We leave alternative implementations as exercises.
If the instruction has a register that is written to, then we adjust the first (most
recent) range's start position to be the position of the (writing) instruction, and we
record the use position.
For each register that is read (or used) in the instruction, we add a new range extending
to this instruction's position. Initially, the new range begins at the start of the block;
a write may cause the start position to be re-adjusted.
Notice the addOrExtendRange() operation merges contiguous ranges into one.