Next: Global Copy Propagation and Dead Up: Compiler Theory: Code Optimization Previous: Data-flow analysis: available expressions.

# 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

• useL(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).
• 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 topogical 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 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

 topL(B) = useL(B)  and  bottomL(B) = (13)

• For each basic block B

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

• Repeat previous step until none of the sets change.

Next: Global Copy Propagation and Dead Up: Compiler Theory: Code Optimization Previous: Data-flow analysis: available expressions.
Marc Moreno Maza
2004-12-02