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

Algorithm 7.2 Computing Global Liveness Information
Input: The control-flow graph g for a method, and the local liveness sets liveUse and
liveDef for every basic block
Output: Two sets for each basic block: liveIn, registers live at the beginning of the block,
and liveOut, registers that are live at the end of the block
repeat
for block b in g.blocks in reverse order do
b.liveOut fg
for block s in b.successors do
b.liveOut b.liveOut [ s.liveIn
end for
b.liveIn (b.liveOut b.liveDef) [ b.liveUse
end for
until no liveOut has changed
We represent the live sets as BitSet s from the Java API, indexed by the register number
of the operands. Recall that registers numbered 0 to 31 are physical registers and registers
32 and higher are virtual registers. By the time we compute liveness intervals, we know how
many virtual registers we will need for a method's computation. Later, splitting of intervals
may create additional virtual registers but we do not need liveness sets for those.
We cannot compute the live sets for a loop in a single pass; the first time we process a
loop end block, we have not yet processed the corresponding loop header block; the loop
header's block's liveIn set (and so its predecessor blocks' liveOut sets) is computed correctly
only in the second pass. This means our algorithm must make d + 1 passes over the blocks,
where d is the depth of the deepest loop.
Continuing with our example for Factorial 's computeIter() , we start with the local
liveness sets in Figure 7.3. Our computation requires three iterations:
1. After the first iteration, the sets liveIn and liveOut for each block are
B4liveIn: V34
B4liveOut:
B3liveIn: V33V34
B3liveOut:
B2liveIn: V33V34
B2liveOut:V33V34
B1liveIn: $a0
B1liveOut:V33V34
B0liveIn: $a0
B0liveOut:$a0
Recall that at each iteration we process the blocks in reverse order; at the start,
liveOut for each block is empty.
(a) B4 has no successors so liveOut remains empty. Because V34 is used in B4 (in
B4's liveUse), it is added into B4's liveIn.
(b) B3's only successor B2 has not been processed yet so B3's liveOut is empty at
this iteration (the next iteration will add registers). Because B3's liveUse contains
V33 and V34 (as they are used before defined in the block), V33 and V34 are
added to B3's liveIn.
(c) B2 has successors B3 and B4. Because V33 and V34 are in B3's liveIn, they are
added to B2's liveOut; V34 is also in B4's liveIn but it is already in B2's liveOut.
Because neither V33 nor V34 are redened in B2, they are also added to B2's
liveIn.