Global Copy Propagation and Dead Code Elimination

KEY IDEA. With the data-flow sets in_R(B) and in_C(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 in_R(B) (where in_R(B) denotes the set of the definitions that reach B).
• If b := c also belongs to in_C(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 $\in$ in_C(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.

Figure 10: A control flow graph.

• Copy statement 1 belongs to in_R(B₃) and in_R(B₄) and reaches references of s there. However, 1 does not belong to neither in_C(B₃) nor in_C(B₄). So, the replacement cannot be done.
• Copy statement 2 belongs to in_R(B₃), in_R(B₄) and in_R(B₅) and reaches the reference of i there. But 2 does not belong to any of in_C(B₃), in_C(B₄) or in_C(B₅).
• Copy statement 3 belongs to in_R(B₅) and in_C(B₅) 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.