A sparse algorithm for predicated global value numbering

ABSTRACT

This paper presents a new algorithm for performing global value numbering on a routine in static single assignment form. Our algorithm has all the strengths of the most powerful existing practical methods of global value numbering; it unifies optimistic value numbering with constant folding, algebraic simplification and unreachable code elimination. It goes beyond existing methods by unifying optimistic value numbering with further analyses: it canonicalizes the structure of expressions in order to expose more congruences by performing global reassociation, it exploits the congruences induced by the predicates of conditional jumps (predicate inference and value inference), and it associates the arguments of acyclic ø functions with the predicates controlling their arrival (ø predication), thus enabling congruence finding on conditional control structures. Finally, it implements an efficient sparse formulation and offers a range of tradeoffs between compilation time and optimization strength. We describe an implementation of the algorithm and present measurements of its strength and efficiency collected when optimizing the SPEC CINT2000 C benchmarks.

REFERENCES

• 1: B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73561]
• 2: Andrew Ayers , Stuart de Jong , John Peyton , Richard Schooler, Scalable cross-module optimization, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.301-312, June 17-19, 1998, Montreal, Quebec, Canada
• 3: Preston Briggs , Keith D. Cooper, Effective partial redundancy elimination, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.159-170, June 20-24, 1994, Orlando, Florida, United States
• 4: Preston Briggs , Keith D. Cooper , L. Taylor Simpson, Value numbering, Software—Practice & Experience, v.27 n.6, p.701-724, June 1997 [doi>10.1002/(SICI)1097-024X(199706)27:6<701::AID-SPE104>3.3.CO;2-S ]
• 5: P. Briggs, L. Torczon, and K. D. Cooper. Using Conditional Branches to Improve Constant Propagation. Technical Report CRPC-TR95533, Center for Research on Parallel Computation, Rice University, April 1995
• 6: Jong-Deok Choi , Ron Cytron , Jeanne Ferrante, Automatic construction of sparse data flow evaluation graphs, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.55-66, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99594]
• 7: Clifford Noel Click, Jr., Combining analyses, combining optimizations, Rice University, Houston, TX, 1996
• 8: Cliff Click, Global code motion/global value numbering, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.246-257, June 18-21, 1995, La Jolla, California, United States
• 9: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 10: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• 11: B. K. Rosen , M. N. Wegman , F. K. Zadeck, Global value numbers and redundant computations, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-27, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73562]
• 12: Oliver Rüthing , Jens Knoop , Bernhard Steffen, Detecting Equalities of Variables: Combining Efficiency with Precision, Proceedings of the 6th International Symposium on Static Analysis, p.232-247, September 22-24, 1999
• 13: Loren Taylor Simpson , Keith D. Cooper, Value-driven redundancy elimination, 1996
• 14: Vugranam C. Sreedhar , Guang R. Gao , Yong-Fong Lee, Incremental computation of dominator trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.2, p.239-252, March 1997 [doi>10.1145/244795.244799]
• 15: Mark N. Wegman , Frank Kenneth Zadeck, Constant propagation with conditional branches, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.291-299, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318659]
• 16: Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
global value numbering, static single assignment