Copy propagation

Copy Propogation is an optimization used in compilers. It is an enabling optimization, which is to say that it does not directly reduce code size or increase code speed; rather, it reorganizes code so that other optimizations may be more effective. Copy propogation operates on a low-level intermediate representation such as quads or register transfer level (RTL), and can operate on either the basic block or control flow graph level.

Basic RTL Demonstration

The basic idea of the copy propogation optimization is to seek out two instructions where the at least one source of the second instruction is the destination operand of the first copy instruction. In RTL,

1. $B\gets A$
2. zero or more instructions
3. $C\gets f(x_{1},x_{2},\ldots ,B,\ldots ,x_{n})$

In other words, the code copies the value of A into both B, and then has some instruction which depends on the value of B. If the compiler finds such a pair of instructions, and if the compiler can prove that the intermediate instructions (2) do not modify the values of B or A, then the compiler can transform this to the equivalent code:

1. $B\gets A$
2. zero or more instructions
3. $C\gets f(x_{1},x_{2},\ldots ,A,\ldots ,x_{n})$

Since the value of A has not changed, and since B also held that value, the third instruction must compute the same value.

When Copy Propogation may be Applied

In the earlier RTL listings, it was assumed that the instructions take place within a basic block---that is, that there were no branching instructions or function calls. However, the presence of branches or calls does not necessarily prevent the compiler from performing this instruction. It does require that the compiler perform control flow analysis to verify a few characteristics.

First, it must be verified that the basic block which contains the assignment of B dominates the block which contains the use of B, or in other words that the definition is always executed at least once before the use. This test prevents cases such as this conditional statement, expressed in pseudocode:

1. if( some condition )
2. then
3. $B\gets A$
4. else
5. $B\gets X$
6. end if
7. $C\gets B$

In this example, the assignment $B\gets A$ does not dominate the use $C\gets B$, because there is a path of execution which contains the second assignment, but not the first (namely, the else clause).

Next, it must be shown that no other assignment to A or B dominates the second assingment and post-dominates the first assignment. In other words, the assignment $B\gets A$ must always be the most recent assignment to A or B before the assignment $C\gets B$. Take for example, this loop:

1. $B\gets A$
2. while( some condition )
3. $C\gets B$
4. $A\gets X$
5. end loop

In this example, the assignment $B\gets A$ clearly dominates the assignment $C\gets B$. However, we cannot change the second assignment to $C\gets A$ because A changes within the loop; after the first iteration of the loop, C would contain the value of X and not the value of the initial A.

How Copy Propogation may enable other Optimizations

Creation of Dead Code

Copy propogation may aid the optimization process by creating more dead code, which can later be removed by dead code elimination. For instance,

1. $B\gets A$
2. $C\gets B$
3. $D\gets C$

After copy propogation has been applied twice, we have

1. $B\gets A$
2. $C\gets A$
3. $D\gets A$

Suppose that instruction (3) was the only use of memory location C. If so, then no instructions depend on the value of C, and the instruction may be removed.

Constant Folding

Copy propogation may also aid constant in constant folding. If, for instance, the operand A was a constant, and the use was an addition:

1. $B\gets 4$
2. $C\gets 2+B$

A single copy propogation will yield,

1. $B\gets 4$
2. $C\gets 2+4$

The constant can later be folded to,

1. $B\gets 4$
2. $C\gets 6$