A NEW ALGORITHM FOR PARTIAL REDUNDANCY ELIMINATION BASED ON SSA FORM

A new algorithm, SSAPRE, for performing partial redundancy elimination based entirely on SSA form is presented. It achieves optimal code mot ion similar to lazy code motion [KRS94a, DS93], but is formulated inde pendently and does not involve iterative data flow analysis and bit ve ctors in its solution. It not only exhibits the characteristics common to other sparse approaches, but also inherits the advantages shared b y other SSA-based optimization techniques. SSAPRE also maintains its o utput in the same SSA form as its input. In describing the algorithm, we state theorems with proofs giving our claims about SSAPRE. We also give additional description about our practical implementation of SSAP RE, and analyze and compare its performance with a bit-vector-based im plementation of PRE. We conclude with some discussion of the implicati ons of this work.