Data-flow analysis: copy propagation.

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 data-flow analysis together with
• new data-flow 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 $\cal {P}$. We say that the copy s: x := y reaches p if every path $\gamma$ from the initial node of $\cal {P}$ to p

• contains s: x := y
• and subsequent to the last occurrence of s: x := y on $\gamma$ there is no assignment to y or x.

This implies that the statement s: x := y reaches the point p.

COPY PROPAGATION DATA-FLOW SETS. For a basic block B

• in_C(B) is the set of the copies (from anywhere in $\cal {P}$) reaching entry(B).
• out_C(B) is the set of the copies (from anywhere in $\cal {P}$) 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 $\not\in$ B and
  • x or y are assigned in B.
• kill_C(B) is the set of the copy statements (from anywhere in $\cal {P}$) 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 data-flow 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.

DATA-FLOW EQUATIONS For every basic block B the data-flow sets in_C(B) and out_C(B) satisfy the following equations

inC(B)	=	$$\bigcap_{{{\ B' \ \in \ {\mbox{\sf pred}}(B)}}}^{{}}$$ outC(B'),
outC(B)	=	genC(B) $$\bigcup$$ $$\left(\vphantom{ in_C(B) \setminus kill_C(B) }\right.$$inC(B) $$\setminus$$ killC(B)$$\left.\vphantom{ in_C(B) \setminus kill_C(B) }\right)$$.

(6)

COMPUTING THE DATA-FLOW SETS FOR THE COPY PROPAGATION PROBLEM Assume that the set C of all copy statements in $\cal {P}$ has been computed. Then, for each basis block B one can compute gen_C(B) and kill_C(B). Now set

$$\emptyset$$ (7)

where B₁ is the first block Then one can set up a completion algorithm initializing every for basic block B $\neq$ B₁

in_C(B)  =  C (8)

and using the updating equations

outC(B)	=	genC(B) $$\bigcup$$ $$\left(\vphantom{ in_C(B) \setminus kill_C(B) }\right.$$inC(B) $$\setminus$$ killC(B)$$\left.\vphantom{ in_C(B) \setminus kill_C(B) }\right)$$.
inC(B)	=	$$\bigcap_{{{\ B' \ \in \ {\mbox{\sf pred}}(B)}}}^{{}}$$ outC(B'),

(9)