Abstract
Detecting whether different variables have the same value at a program point is generally undecidable. Though the subclass of equalities, whose validity holds independently from the interpretation of operators (Herbrand-equivalences), is decidable, the technique which is most widely implemented in compilers, value numbering, is restricted to basic blocks. Basically, there are two groups of algorithms aiming at globalizations of value numbering: first, a group of algorithms based on the algorithm of Kildall, which uses data flow analysis to gather information on value equalities. These algorithms are complete in detecting Herbrand-equivalences, however, expensive in terms of computational complexity. Second, a group of algorithms influenced by the algorithm of Alpern, Wegman and Zadeck. They do not fully interpret the control flow, which allows them to be particularly efficient, however, at the price of being significantly less precise than their Kildall-like counterparts. In this article we discuss how to combine the best features of both groups by aiming at a fair balance between computational complexity and precision. We propose an algorithm, which extends the one of Alpern, Wegman and Zadeck. The new algorithm is polynomial and, in practice, expected to be almost as efficient as the original one. Moreover, for acyclic control flow it is as precise as Kildall’s one, i. e. it detects all Herbrand-equivalences.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
B. Alpern, M. Wegman, and F. K. Zadeck. Detecting equality of variables in programs. In Conf. Record of the 15 th ACM Symposium on the Principles of Programming Languages (POPL), January 1988.
P. Briggs, K. D. Cooper, and L. T. Simpson. Value numbering. Software-Practice and Experience, 27(6):701–724, June 1997.
C. Click. Global code motion/global value numbering. In Proc. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), volume 30,6 of ACM SIGPLAN Notices, pages 246–257, La Jolla, CA, June 1995.
J. Cocke and J. T. Schwartz. Programming languages and their compilers. Courant Institute of Mathematical Sciences, NY, 1970.
R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and F. K. Zadeck. Efficiently computing static single assignment form and the control dependency graph. ACM Transactions on Programming Languages and Systems, 13(4):451–490, 1991.
A. Fong, J. B. Kam, and J. D. Ullman. Application of lattice algebra to loop optimization. In Conf. Record of the 2 nd ACM Symposium on the Principles of Programming Languages (POPL), pages 1–9, Palo Alto, CA, 1975.
J. Hopcroft. An n log n algorithm for minimizing the states of a finite automaton. The Theory of Machines an Computations, pages 189–169, 1971.
G. A. Kildall. A unified approach to global program optimization. In Conf. Record of the 1 st ACM Symposium on the Principles of Programming Languages (POPL), pages 194–206, Boston, MA, 1973.
J. Knoop, O. Rüthing, and B. Steffen. Code motion and code placement: Just synonyms? In Proc. 6 th European Symposium on Programming (ESOP), Lecture Notes in Computer Science 1381, pages 154–196, Lisbon, Portugal, 1998. Springer-Verlag.
S. S. Muchnick. Advanced Compiler Design & Implementation. Morgan Kaufmann, San Francisco, CA, 1997.
M. H. A. Newman. On theories with a combinatorial definition of equivalence. Annals of Math., 43,2:223–243, 1942.
J. H. Reif and R. Lewis. Symbolic evaluation and the gobal value graph. In Conf. Record of the 4 th ACM Symposium on the Principles of Programming Languages (POPL), pages 104–118, Los Angeles, CA, 1977.
B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Global value numbers and redundant computations. In Conf. Record of the 15 th ACM Symposium on the Principles of Programming Languages (POPL), pages 12–27, San Diego, CA, 1988.
L. T. Simpson. Value-driven redundancy elimination. Technical Report TR98-308, Rice University, April 6, 1998.
B. Steffen. Optimal run time optimization. Proved by a new look at abstract interpretations. In Proc. 2 nd International Joint Conference on the Theory and Practice of Software Development (TAPSOFT), Lecture Notes in Computer Science 249, pages 52–68, Pisa, Italy, 1987. Springer-Verlag.
B. Steffen, J. Knoop, and O. Rüthing. The value flow graph: A program representation for optimal program transformations. In Proc. 3 rd European Symposium on Programming (ESOP), Lecture Notes in Computer Science 432, pages 389–405, Copenhagen, Denmark, 1990. Springer-Verlag.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rüthing, O., Knoop, J., Steffen, B. (1999). Detecting Equalities of Variables: Combining Efficiency with Precision. In: Cortesi, A., Filé, G. (eds) Static Analysis. SAS 1999. Lecture Notes in Computer Science, vol 1694. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48294-6_15
Download citation
DOI: https://doi.org/10.1007/3-540-48294-6_15
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66459-8
Online ISBN: 978-3-540-48294-9
eBook Packages: Springer Book Archive