#### Annexe 2.

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)  and  bottomL(B) = (1)

• For each basic block B

 bottomL(B) = topL(B') topL(B) = (bottomL(B) defL(B))  useL(B)
(2)

• Repeat previous step until none of the sets change.