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

FIGURE 7.3 Control-flow graph for Factorial.computeIter() with local liveness sets
computed.
Our next step is to use this local liveness information to compute global liveness infor-
mation; for each basic block, we want to know which registers are live, both coming into
the block and going out of the block.
Computing Global Liveness Sets
We can compute the set of operands that are live at the beginning and end of a block using
a backward data-flow analysis [Aho et al., 2007]. We call the set of operands that are live
at the start of a block liveIn. We call the set of operands that are live at the end of a block
liveOut.
Algorithm 7.2 computes this global liveness data for us. Notice we iterate through the
blocks, and also the instruction sequence within each block, in a backwards direction.