Rastislav Bodik and Sadun Anik
When analyzing programs for value recomputation, each value is identified with its lexical name. When two expressions match the name, they compute the same value. But what name should be used when the value flows between equivalent expressions that have different names? This paper presents a way to overcome the naming problem by synthesizing names that fully trace the flow of a value, and by performing data-flow analysis on this synthesized name space.
Our analysis integrates three orthogonal techniques: symbolic interpretation, value numbering, and data-flow analysis. Symbolic interpretation first creates all necessary names and value numbering then determines which names are synonymous. The result is expressed in a new program representation, called Value Name Graph (VNG). Once the VNG is constructed, any conventional data-flow analysis can answer two fundamental optimization questions: which computations are value-equivalent, and along which control flow paths?
VNG analysis is path-sensitive: value reuse is detected even when each path requires different names, for example due to conditionally incremented loop induction variables. The VNG is the core of our new optimization framework for redundancy optimizations like constant propagation or VLIW load/store elimination. By phrasing these optimizations on the VNG, we obtain greater optimization power and broader applicability.
Keywords: data-flow analysis frameworks, value numbering, partial redundancy elimination, interprocedural constant propagation.
full paper (.ps)
The talk: slides, slides w/comments (.ps.gz)