Recall that a variable is live at a point p
of a program if it is referenced further in
(which can decided by considering the control flow graph)
otherwise it is said to be dead.
For a basic block B
useL(B) is the set of the variables which are used in B
before they are defined or re-defined in B.
Thus, such variables rely on some earlier definitions
(in the control flow graph).
defL(B) is the set of the variables which are defined in B before they are used
anywhere in the program.
This can be computed by using a topological sort of the control flow
graph (after its back edges have been removed).
bottomL(B) is the set of variables that are live at exit(B).
topL(B) is the set of variables that are live at entry(B).
The following iterative algorithm propagates liveness information backward
around the control flow graph.
For each basic block B we set
topL(B) = useL(B) andbottomL(B) =
For each basic block B
(bottomL(B) defL(B)) useL(B)
Repeat previous step until none of the sets change.