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

The careful reader will notice that this algorithm assumes that no virtual register is defined
but not used; this means we do not have local variables that are given values that are never
used. We leave dealing with the more peculiar cases as exercises.
Consider how Algorithm 7.3 would deal with basic block B3 of the LIR for Factorial.
computeIter() .
B3
25:LDC[-1][V36|I]
30:ADD[V33|I][V36|I][V37|I]
35:MUL[V34|I][V33|I][V38|I]
40:MOVE[V38|I][V34|I]
45:MOVE[V37|I][V33|I]
50:BRANCHB2
The progress of building intervals for basic block B3, as we sequence backward through its
instructions, is illustrated in Figure 7.4. (LiveOut contains V33 and V34.)
FIGURE 7.4 Building intervals for basic block B3.
At the start of processing B3, virtual registers V33 and V34 are in liveOut and so have
intervals with ranges extending from (for now) the start of the block (position 25) to the
end of the block (position 50), as illustrated in Figure 7.4(a). We then sequence through
the instructions in reverse order.
At position 50, the branch instruction has no register operands, so no intervals are
aected.