In
compiler theory
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
, copy propagation is the process of replacing the occurrences of targets of direct assignments with their values.
A direct assignment is an instruction of the form
x = y, which simply assigns the value of
y to
x.
From the following code:
y = x
z = 3 + y
Copy propagation would yield:
z = 3 + x
Copy propagation often makes use of
reaching definitions,
use-def chains
Within computer science, a Use-Definition Chain (''UD Chain'') is a data structure that consists of a use, U, of a variable, and all the definitions, D, of that variable that can reach that use without any other intervening definitions. A UD Chain ...
and
def-use chains
Within computer science, a Use-Definition Chain (''UD Chain'') is a data structure that consists of a use, U, of a Variable (programming), variable, and all the definitions, D, of that variable that can reach that use without any other intervening ...
when computing which occurrences of the target may be safely replaced. If all
upwards exposed uses of the target may be safely modified, the assignment operation may be eliminated.
Copy propagation is a useful "clean up" optimization frequently used after other compiler passes have already been run. Some optimizations—such as classical implementations of
elimination of common sub expressions[—''require'' that copy propagation be run afterwards in order to achieve an increase in efficiency.
]
See also
* Copy elision In C++ computer programming, copy elision refers to a compiler optimization technique that eliminates unnecessary copying of objects.
The C++ language standard generally allows implementations to perform any optimization, provided the resulting p ...
* Constant folding and constant propagation
References
Further reading
Muchnick, Steven S. ''Advanced Compiler Design and Implementation''. Morgan Kaufmann. 1997.
{{Compiler optimizations
Compiler optimizations