ACM Transactions on Programming Languages and Systems · 1999 · 93 citations · 28 references
ComputingComputer EngineeringComputer ScienceAlgorithmsCompilersComputer ArchitectureAlgorithm AnalysisData-flow AnalysisPerformance OptimizationRedundancy ManagementRedundancy ResolutionRedundancy TechniquesCompile-time OptimizationOptimality CriteriaPartial Redundancy EliminationRedundancy EliminationRedundant ComputationSparse ModelsSparse Reduction
The SSAPRE algorithm for performing partial redundancy elimination based entirely on SSA form is presented. The algorithm is formulated based on a new conceptual framework, the factored redundancy graph, for analyzing redundancy, and representes the first sparse approach to the classical problem and on methods for its solution. With the algorithm description, theorems and their proofs are given showing that the algorithm produces the best possible code by the criteria of computational optimality and lifetime optimality of the introduced temporaries. In addition to the base algorithm, a practical implementation of SSAPRE that exhibits additional compile-time efficiencies is described. In closing, measurement statistics are provided that characterize the instances of the partial redundancy problem from a set of benchmark programs and compare optimization time spent by an implementation of SSAPRE aganist a classical partial redundancy elimination implementation. The data lend insight into the nature of partial redundancy elimination and demonstrate the expediency of this new approach.
28
Global value numbers and redundant computations
Barry K. Rosen, Mark N. Wegman, F. K. Zadeck · 1988 · 483 citations
Detecting equality of variables in programs
Bowen Alpern, Mark N. Wegman, F. K. Zadeck · 1988 · 427 citations
Global optimization by suppression of partial redundancies
E. H. Morel, C. Renvoise · Communications of the ACM · 1979 · 377 citations · Full text