Partial redundancy elimination (PRE) is a program transformation that identifies and eliminates expressions that are redundant on at least one (but not necessarily all) execution paths of a program without increasing any path length. Chow, Kennedy and co-workers devised an algorithm (SSAPRE) for performing partial redundancy elimination on intermediate representations in static single assignment (SSA) form. The practicality of that algorithm is limited by the following concerns: (1) it makes assumptions about the namespace that are stronger than those of SSA form and that may not be valid if other optimizations have already been performed on the program; (2) if redundancies occur in nested expressions, the algorithm may expose but not eliminate them (requiring a second pass of the algorithm); (3) it misses cases covered by the state of the art in PRE; and (4) it is difficult to understand and implement. We present an algorithm (A-SSAPRE) structurally similar to SSAPRE that uses anticipation rather than availability; this algorithm is simpler than SSAPRE, covers more cases, eliminates nested redundancies on a single pass, and makes no assumptions about the namespace.
@article{VanDrunen+2004SPE,
author = {VanDrunen, Thomas and Hosking, Antony L.},
title = {Anticipation-Based Partial Redundancy Elimination for Static
Single Assignment Form},
journal = {Software --- Practice and Experience},
year = {2004},
volume = {34},
number = {15},
pages = {1413--1439},
month = {December},
doi = {10.1002/spe.618},
gscholar = {11}
}