Global Live Variable Analysis

We return to the analysis of live varaibles. Our earlier analysis and optimization were restricted to a basic block, We recall the following definition.

A VARIABLE IS LIVE AT A POINT P of the program if it is referenced further in the program (which can decided by considering the control flow graph) otherwise it is said to be dead.

DATA-FLOW SETS. We assume that the control flow graph is reducible. For a basic block B

• use_L(B) is the set of the variables which are used in B before they are (re-)dedefined 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 topogical 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 safety principle requires that we should assume that variables remain live if there is any doubt.

COMPUTING THE DATA-FLOW SETS. Note that the information to be computed is opposite to the flow of control

The following iterative algorithm propagates liveness information backwards around the control flow graph.

• For each basic block B we set

  $$\emptyset$$ (13)

  
  

• 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)

  (14)

  
  

• Repeat previous step until none of the sets change.