Next: Dataflow analysis: available expressions.
Up: Compiler Theory: Code Optimization
Previous: Dataflow analysis: reaching definitions
Many optimizations and user code introduce copy statements of the form
s: x := y
It is sometimes possible to eliminate such copy statements.
COPY PROPAGATION CONDITIONS. Assume that for a statement u where x is used
 statement s is the only definition of x reaching u
 on every path from s to u there are no assignments to y
Then we may substitute y for x in u.
Observe that
 we know how to check the first condition,
 but not the second one ...
We shall set up
 a new dataflow analysis together with
 new dataflow equations to solve this problem.
COPY REACHING A POINT. Let s: x := y be a copy statement and p be a point of the TAC program .
We say that the copy s: x := y reaches p if
every path from the initial node of to p
 contains s: x := y
 and subsequent to the last occurrence of s: x := y on
there is no assignment to y or x.
This implies that the statement s: x := y reaches the point p.
COPY PROPAGATION DATAFLOW SETS. For a basic block B
 in_{C}(B) is the set of the copies (from anywhere in ) reaching entry(B).
 out_{C}(B) is the set of the copies (from anywhere in ) reaching exit(B).
 gen_{C}(B) is the set of the copies defined in B and reaching exit(B).
 A copy statement s: x := y is killed in B if
 s: x := y
B and
 x or y are assigned in B.
 kill_{C}(B) is the set of the copy statements (from anywhere in ) that are killed in within block B by a redefinition of y or x.
Observe that
 in_{C}(B) can contain only one copy statement with
a given x on the left.
Observe that for every basic block B
 the dataflow sets gen_{C}(B) and kill_{C}(B) can be computed easily,
 the definitions of gen_{C}(B) and kill_{C}(B) essentially deals
with graph theory and will not detect copy statements that are never hit (= evaluated),
 so we may apply the following precautionary principles
 we add a copy statement to gen_{C}(B) only if we are sure that it is hit,
 we add a copy statement to kill_{C}(B) even if it is doubtful that it will be killed.
DATAFLOW EQUATIONS For every basic block B the dataflow sets in_{C}(B) and out_{C}(B) satisfy
the following equations
in_{C}(B) 
= 
out_{C}(B'), 
out_{C}(B) 
= 
gen_{C}(B) in_{C}(B) kill_{C}(B). 

(6) 
COMPUTING THE DATAFLOW SETS FOR THE COPY PROPAGATION PROBLEM Assume that the set C of all copy statements in has been computed.
Then, for each basis block B one can compute gen_{C}(B) and kill_{C}(B).
Now set
in_{C}(B_{1}) = and out_{C}(B_{1}) = gen_{C}(B_{1}) 
(7) 
where B_{1} is the first block
Then one can set up a completion algorithm
initializing every for basic block
B B_{1}
and using the updating equations
out_{C}(B) 
= 
gen_{C}(B) in_{C}(B) kill_{C}(B). 
in_{C}(B) 
= 
out_{C}(B'), 

(9) 
Next: Dataflow analysis: available expressions.
Up: Compiler Theory: Code Optimization
Previous: Dataflow analysis: reaching definitions
Marc Moreno Maza
20041202