Partial redundancy elimination

Partial redundancy elimination

In compiler theory, Partial redundancy elimination (PRE) is a compiler optimization that eliminates expressions that are redundant on some but not necessarily all paths through a program. PRE is a form of common subexpression elimination (CSE).

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) { // some code y = x + 4; } else { // other code } 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) { // some code y = x + 4; t = y; } else { // other code t = x + 4; } z = t;

An interesting property of PRE is that it performs (a form of) CSE and loop-invariant code motion 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 Static single assignment form - based formulations of PRE have been published that apply the PRE algorithm to values instead of expressions, unifying PRE and GVN (Global value numbering).

Further reading

Muchnick, Steven S. Advanced Compiler Design and Implementation. Morgan Kaufmann. 1997.

Morel, E., and Renvoise, C. Global Optimization by Suppression of Partial Redundancies. Communications of the acm, Vol. 22, Num. 2, Feb. 1979.

Knoop, J., Ruthing, O., and Steffen, B. Lazy Code Motion. ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI.

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.

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.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Compiler optimization — is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the… …   Wikipedia

  • GNU Compiler Collection — Cc1 redirects here. For other uses of CC1 or CC 1, see CC1 (disambiguation). GNU Compiler Collection Developer(s) GNU Project Initial release May 23, 1987 ( …   Wikipedia

  • Static single assignment form — In compiler design, static single assignment form (often abbreviated as SSA form or SSA) is an intermediate representation (IR) in which every variable is assigned exactly once. Existing variables in the original IR are split into versions , new… …   Wikipedia

  • Avr-gcc — GNU Compiler Collection Entwickler: GCC Team Aktuelle Version: 4.4.0 (21. April 2009) …   Deutsch Wikipedia

  • EGCS — GNU Compiler Collection Entwickler: GCC Team Aktuelle Version: 4.4.0 (21. April 2009) …   Deutsch Wikipedia

  • GNU C-Compiler — GNU Compiler Collection Entwickler: GCC Team Aktuelle Version: 4.4.0 (21. April 2009) …   Deutsch Wikipedia

  • GNU C Compiler — GNU Compiler Collection Entwickler: GCC Team Aktuelle Version: 4.4.0 (21. April 2009) …   Deutsch Wikipedia

  • GNU Compiler Collection — Entwickler GCC Team Aktuelle Version 4.6.2 (26. Oktober 2011) Betriebssyste …   Deutsch Wikipedia

  • Pre — may refer to:*The ... HTML element, pre as in pre formatted *Andalusian horse, Pura Raza Española *Steve Prefontaine (1951 1975), a runner nicknamed Pre *Preston Railway Station in Northern England (national rail code) *Personal Rescue Enclosure …   Wikipedia

  • respiration, human — ▪ physiology Introduction       the process by which oxygen is taken up and carbon dioxide discharged. The design of the respiratory system  The human gas exchanging organ, the lung, is located in the thorax, where its delicate tissues are… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”