TY - GEN
T1 - Upper adjoints for fast inter-procedural variable equalities
AU - Müller-Olm, Markus
AU - Seidl, Helmut
PY - 2008
Y1 - 2008
N2 - We present a polynomial-time algorithm which at the extra cost of a factor (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.
AB - We present a polynomial-time algorithm which at the extra cost of a factor (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.
UR - http://www.scopus.com/inward/record.url?scp=47249108610&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-78739-6_15
DO - 10.1007/978-3-540-78739-6_15
M3 - Conference contribution
AN - SCOPUS:47249108610
SN - 3540787380
SN - 9783540787389
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 178
EP - 192
BT - Programming Languages and Systems - 17th European Symposium on Programming, ESOP 2008 - Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2008, Proceedings
T2 - 17th European Symposium on Programming, ESOP 2008
Y2 - 29 March 2008 through 6 April 2008
ER -