Anticipation-Based Partial Redundancy Elimination for Static Single Assignment Form

VanDrunen, Thomas and Hosking, Antony L.


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.

  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}