Next: Global Recycling of Available Expressions Up: Compiler Theory: Code Optimization Previous: Global Live Variable Analysis

# Global Copy Propagation and Dead Code Elimination

KEY IDEA. With the data-flow sets inR(B) and inC(B) computed in the previous sections we can consider global copy propagation and dead-code elimination across basic blocks.

• Consider a basic block B and a statement S of B which references a variable b.
• If a copy statement b := c reaches statement S, then it belongs to inR(B) (where inR(B) denotes the set of the definitions that reach B).
• If b := c also belongs to inC(B) then we know that this is the only definition of b reaching B.
• In addition, if there is no other definition of b or c in block B before S (which is easily checked) then we can replace b by c in statement S.
• Finally, if all references to b that are reached by b := c can be replaced by c, then the assigned b := c becomes dead code and can be removed.

ALGORITHM. For each copy statement S: b := c in the program do

1. Find all uses of b in some statement S'. That is, find every reference to b in a statement S' of block B such that no redefinitions of b or c appear between entry(B) and S'.
2. For each such use of b where, furthermore, S inC(B), replace b by c.
3. if we can do this replacement in all the above cases, then remove the copy statement S: b := c.

EXERCISE. Apply the previous algorithm to Figure 10.

• Copy statement 1 belongs to inR(B3) and inR(B4) and reaches references of s there. However, 1 does not belong to neither inC(B3) nor inC(B4). So, the replacement cannot be done.
• Copy statement 2 belongs to inR(B3), inR(B4) and inR(B5) and reaches the reference of i there. But 2 does not belong to any of inC(B3), inC(B4) or inC(B5).
• Copy statement 3 belongs to inR(B5) and inC(B5) and reaches the reference of n in statement 10. So, the replacement can be done.
• After these modifications we have to update the dataflow information for the modified flow graph.

Next: Global Recycling of Available Expressions Up: Compiler Theory: Code Optimization Previous: Global Live Variable Analysis
Marc Moreno Maza
2004-12-02