Premium
Anticipation‐based partial redundancy elimination for static single assignment form
Author(s) -
VanDrunen Thomas,
Hosking Antony L.
Publication year - 2004
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.618
Subject(s) - redundancy (engineering) , namespace , computer science , transformation (genetics) , algorithm , anticipation (artificial intelligence) , path (computing) , program transformation , theoretical computer science , programming language , artificial intelligence , computer network , biochemistry , chemistry , gene , operating system
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. Copyright © 2004 John Wiley & Sons, Ltd.