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

Computing Local Liveness Sets
As a first step in building the liveness intervals for LIR operands, we compute, for each
block, two local liveness sets: liveUse and liveDef. The liveUse operands are those operands
that are read (or used) before they are written (dened) in the block's instruction sequence;
presumably they were defined in a predecessor block (or are arguments to the method). The
liveDef operands are those operands that are written to (defined) by some instruction in
the block.
Algorithm 7.1 computes liveUse and liveDef for each basic block in a method.
Algorithm 7.1 Computing Local Liveness Information
Input: The control-flow graph g for a method
Output: Two sets for each basic block: liveUse, registers used before they are overwritten
(defined) in the block and liveDef, registers that are defined in the block
for block b in g.blocks do
Set b.liveUse fg
Set b.liveDef fg
for instruction i in b.instructions do
for virtual register v in i.readOperands do
if v 2 b.liveDef then
b.liveUse.add(v)
end if
end for
for virtual register v in i.writeOperands do
b.liveDef.add(v)
end for
end for
end for
For example, the control-flow graph for Factorial 's computeIter() but with its local
liveness sets computed is illustrated in Figure 7.3.
In the computation of the local liveness sets, we can sequence through the blocks in
any order because all computations are local to each block. Our computation proceeds as
follows:
B0 There are no registers in block B0 to be used or defined.
B1 In block B1, there are four registers. V32 is defined in instruction 0. At instruction 5,
$a0 is used in the block before it is defined and V33 is defined. At instruction 10, V34
is defined (V32 is used but it is already defined in this block).
B2 In block B2, V35 is defined in instruction 15. V33 is used in instruction 20 without
previously being defined in the block.
B3 In block B3, V36 is defined in instruction 25. In instruction 30, V33 is used (before
defined) and V37 is defined. In instruction 35, V34 is used (before defined) and V38
is defined. V34 is defined in instruction 40 and V33 is defined in instruction 45. No
register is used or defined in the branch at 50.
B4 In block B4, V34 is used and $v0 is defined in instruction 55. $v0 is used in instruction
60 but not before it is defined in the block.