In
compiler theory
In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primaril ...
, partial redundancy elimination (PRE) is a
compiler optimization
An optimizing compiler is a compiler designed to generate code that is optimized in aspects such as minimizing program execution time, memory usage, storage size, and power consumption. Optimization is generally implemented as a sequence of op ...
that eliminates
expressions that are redundant on some but not necessarily all paths through a program. PRE is a form of
common subexpression elimination.
An expression is called partially redundant if the
value computed by the expression is already available on some but not all paths through a program to that expression. An expression is fully redundant if the value computed by the expression is available on all paths through the program to that expression. PRE can eliminate partially redundant expressions by inserting the partially redundant expression on the paths that do not already compute it, thereby making the partially redundant expression fully redundant.
For instance, in the following code:
if (some_condition)
else
z = x + 4;
the expression
x+4 assigned to
z is partially redundant because it is computed twice if
some_condition is true. PRE would perform
code motion on the expression to yield the following optimized code:
if (some_condition)
else
z = t;
An interesting property of PRE is that it performs (a form of)
common subexpression elimination and
loop-invariant code motion
In computer programming, loop-invariant code consists of statements or expressions (in an imperative programming, imperative programming language) that can be moved outside the body of a loop without affecting the semantics of the program. Loop-i ...
at the same time.
In addition, PRE can be extended to eliminate ''injured'' partial redundancies, thereby effectively performing
strength reduction. This makes PRE one of the most important optimizations in optimizing compilers. Traditionally, PRE is applied to lexically equivalent expressions, but recently formulations of PRE based on
static single assignment form have been published that apply the PRE algorithm to values instead of expressions, unifying PRE and
global value numbering.
See also
*
Value numbering
*
Redundant code
*
Dead code elimination
In compiler theory, dead-code elimination (DCE, dead-code removal, dead-code stripping, or dead-code strip) is a compiler optimization to remove dead code (code that does not affect the program results). Removing such code has several benefits: i ...
References
Further reading
* Muchnick, Steven S. ''Advanced Compiler Design and Implementation''. Morgan Kaufmann. 1997.
* Knoop, J., Ruthing, O., and
Steffen, B. ''Lazy Code Motion''. ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI.
* Paleri, V. K., Srikant, Y. N., and Shankar, P. ''A Simple Algorithm for Partial Redundancy Elimination''. SIGPLAN Notices, Vol. 33(12). pages 35–43 (1998).
* Kennedy, R., Chan, S., Liu, S.M., Lo, R., Peng, T., and Chow, F. ''Partial Redundancy Elimination in SSA Form''. ACM Transactions on Programming Languages Vol. 21, Num. 3, pp. 627–676, 1999.
* VanDrunen, T., and Hosking, A.L. ''Value-Based Partial Redundancy Elimination'', Lecture Notes in Computer Science Vol. 2985/2004, pp. 167 – 184, 2004.
* Cai, Q. and Xue, J. ''Optimal and Efficient Speculation-Based Partial Redundancy Elimination''. International Symposium on Code Generation and Optimization (CGO'03), 91-104, 2003.
* Xue, J. and Knoop, J. '' A Fresh Look at PRE as a Maximum Flow Problem''. International Conference on Compiler Construction (CC'06), pages 139—154, Vienna, Austria, 2006.
* Xue, J. and Cai Q. '' A lifetime optimal algorithm for speculative PRE''. ACM Transactions on Architecture and Code Optimization Vol. 3, Num. 3, pp. 115–155, 2006.
{{Compiler optimizations
Articles with example C code
Compiler optimizations