Markus Müller-Olm and Helmut Seidl. Upper Adjoints for Fast Inter-procedural Variable Equalities. In Sophia Drossopoulou, editor, Programming Languages and Systems, volume 4960 of Lecture Notes in Computer Science, pages 178-192, Budapest, Hungary, April 2008. Springer.

We present a polynomial-time algorithm which at the extra cost of a factor $\mathcal{O}(k)$ ( $\mathnormal{k}$ the number of variables) generalizes inter-procedural copy constant propagation. Our algorithm infers variable-variable equalities in addition to equalities between variables and constants. Like copy constant propagation, it tracks constant and copying assignments but abstracts more complex assignments and guards. The algorithm is based on the observation that, for the abstract lattice of consistent equivalence relations, the upper adjoints of summary functions can be represented much more succinctly than summary functions themselves.

Download: PDF Reference: Bibtex The original publication is available at www.springerlink.com