Copy propagation: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Nick Johnson
m (Copy propogation moved to Copy propagation: I misspelled the title.)
imported>Nick Johnson
(Fixed misspelling)
Line 1: Line 1:
'''Copy Propogation''' is an [[optimization]] used in [[translation system|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|register transfer level (RTL)]], and can operate on either the [[basic block]] or [[control flow graph]] level.
'''Copy Propagation''' is an [[optimization]] used in [[translation system|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 propagation operates on a low-level [[intermediate representation]] such as [[quads]] or [[register transfer level|register transfer level (RTL)]], and can operate on either the [[basic block]] or [[control flow graph]] level.


== Basic RTL Demonstration ==
== 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,
The basic idea of the copy propagation 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,


# <math>B\gets A</math>
# <math>B\gets A</math>
Line 17: Line 17:
Since the value of A has not changed, and since B also held that value, the third instruction must compute the same value.
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 ==
== When Copy Propagation 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 graph|control flow analysis]] to verify a few characteristics.   
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 graph|control flow analysis]] to verify a few characteristics.   
Line 43: Line 43:
In this example, the assignment <math>B\gets A</math> clearly dominates the assignment <math>C\gets B</math>.  However, we cannot change the second assignment to <math>C\gets A</math> 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.
In this example, the assignment <math>B\gets A</math> clearly dominates the assignment <math>C\gets B</math>.  However, we cannot change the second assignment to <math>C\gets A</math> 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 ==
== How Copy Propagation may enable other Optimizations ==




=== Creation of Dead Code ===
=== 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,
Copy propagation may aid the optimization process by creating more dead code, which can later be removed by [[dead code elimination]].  For instance,


# <math>B\gets A</math>
# <math>B\gets A</math>
Line 53: Line 53:
# <math>D\gets C</math>
# <math>D\gets C</math>


After copy propogation has been applied twice, we have
After copy propagation has been applied twice, we have


# <math>B\gets A</math>
# <math>B\gets A</math>
Line 62: Line 62:


=== Constant Folding ===
=== 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:
Copy propagation may also aid constant in [[constant folding]].  If, for instance, the operand A was a constant, and the use was an addition:


# <math>B\gets 4</math>
# <math>B\gets 4</math>
# <math>C\gets 2 + B</math>
# <math>C\gets 2 + B</math>


A single copy propogation will yield,
A single copy propagation will yield,


# <math>B\gets 4</math>
# <math>B\gets 4</math>

Revision as of 09:20, 9 February 2007

Copy Propagation 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 propagation 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 propagation 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,

  2. zero or more instructions

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:

  2. zero or more instructions

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 Propagation 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
  4. else
  6. end if

In this example, the assignment does not dominate the use , 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 must always be the most recent assignment to A or B before the assignment . Take for example, this loop:

  2. while( some condition )
  5. end loop

In this example, the assignment clearly dominates the assignment . However, we cannot change the second assignment to 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 Propagation may enable other Optimizations

Creation of Dead Code

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

After copy propagation has been applied twice, we have

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 propagation may also aid constant in constant folding. If, for instance, the operand A was a constant, and the use was an addition:

A single copy propagation will yield,

The constant can later be folded to,


Template:Stub

Retrieved from "https://citizendium.org/wiki/index.php?title=Copy_propagation&oldid=136413"