A new algorithm for partial redundancy elimination based on ssa form

A new algorithm, SSAPRE, for performing partial redun-dancy elimination based entirely on SSA form is presented. It achieves optimal code motion similar to lazy code mo-tion [KRS94a, DS93], but is formulated independently and does not involve iterative data flow analysis and bit vec-tors in its solution. It not only exhibits the characteristics common to other sparse approaches, but also inherits the advantages shared by other SSA-based optimization tech-niques. SSAPRE also maintains its output in the same SSA form as its input. In describing the algorithm, we state theo-rems with proofs giving our claims about SSAPRE. We also give additional description about our practical implementa-tion of SSAPRE, and analyze and compare its performance with a bit-vector-based implementation of PRE. We con-clude with some discussion of the implications of this work.