__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

- 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'`. - For each such use of
`b`where, furthermore,*S**in*_{C}(*B*), replace`b`by`c`. - 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*in*_{R}(*B*_{3}) and*in*_{R}(*B*_{4}) and reaches references of`s`there. However,`1`does not belong to neither*in*_{C}(*B*_{3}) nor*in*_{C}(*B*_{4}). So, the replacement cannot be done. - Copy statement
`2`belongs to*in*_{R}(*B*_{3}),*in*_{R}(*B*_{4}) and*in*_{R}(*B*_{5}) and reaches the reference of`i`there. But`2`does not belong to any of*in*_{C}(*B*_{3}),*in*_{C}(*B*_{4}) or*in*_{C}(*B*_{5}). - Copy statement
`3`belongs to*in*_{R}(*B*_{5}) and*in*_{C}(*B*_{5}) 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.

2004-12-02