Annexe 2.

Recall that a variable is live at a point p of a program $\cal {P}$ if it is referenced further in $\cal {P}$ (which can decided by considering the control flow graph) otherwise it is said to be dead. For a basic block B

• use_L(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).
• def_L(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).
• bottom_L(B) is the set of variables that are live at exit(B).
• top_L(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

  $$\emptyset$$ (1)

  
  

• For each basic block B

  bottomL(B)	=	$$\bigcup_{{{\ B' \ \in \ {\mbox{\sf pred}}(B)}}}^{{}}$$topL(B')
  topL(B)	=	(bottomL(B) $$\setminus$$ defL(B)) $$\bigcup$$ useL(B)

  (2)

  
  

• Repeat previous step until none of the sets change.