Equality saturation: a new approach to optimization

ABSTRACT

Optimizations in a traditional compiler are applied sequentially, with each optimization destructively modifying the program to produce a transformed program that is then passed to the next optimization. We present a new approach for structuring the optimization phase of a compiler. In our approach, optimizations take the form of equality analyses that add equality information to a common intermediate representation. The optimizer works by repeatedly applying these analyses to infer equivalences between program fragments, thus saturating the intermediate representation with equalities. Once saturated, the intermediate representation encodes multiple optimized versions of the input program. At this point, a profitability heuristic picks the final optimized program from the various programs represented in the saturated representation. Our proposed way of structuring optimizers has a variety of benefits over previous approaches: our approach obviates the need to worry about optimization ordering, enables the use of a global optimization heuristic that selects among fully optimized programs, and can be used to perform translation validation, even on compilers other than our own. We present our approach, formalize it, and describe our choice of intermediate representation. We also present experimental results showing that our approach is practical in terms of time and space overhead, is effective at discovering intricate optimization opportunities, and is effective at performing translation validation for a realistic optimizer.

REFERENCES

• 1: L. Almagor , Keith D. Cooper , Alexander Grosul , Timothy J. Harvey , Steven W. Reeves , Devika Subramanian , Linda Torczon , Todd Waterman, Finding effective compilation sequences, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11-13, 2004, Washington, DC, USA
• 2: 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]
• 3: E. A. Ashcroft , W. W. Wadge, Lucid, a nonprocedural language with iteration, Communications of the ACM, v.20 n.7, p.519-526, July 1977 [doi>10.1145/359636.359715]
• 4: Sorav Bansal , Alex Aiken, Automatic generation of peephole superoptimizers, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 5: Richard Bird , Philip Wadler, An introduction to functional programming, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1988
• 6: James M. Boyle , Terence J. Harmer , Victor L. Winter, The TAMPR program transformation system: simplifying the development of numerical software, Modern software tools for scientific computing, Birkhauser Boston Inc., Cambridge, MA, 1997
• 7: Martin Bravenboer , Karl Trygve Kalleberg , Rob Vermaas , Eelco Visser, Stratego/XT 0.17. A language and toolset for program transformation, Science of Computer Programming, v.72 n.1-2, p.52-70, June, 2008 [doi>10.1016/j.scico.2007.11.003]
• 8: Cliff Click , Keith D. Cooper, Combining analyses, combining optimizations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.181-196, March 1995 [doi>10.1145/201059.201061]
• 9: 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
• 10: Keith D. Cooper , Philip J. Schielke , Devika Subramanian, Optimizing for reduced code space using genetic algorithms, Proceedings of the ACM SIGPLAN 1999 workshop on Languages, compilers, and tools for embedded systems, p.1-9, May 05-05, 1999, Atlanta, Georgia, United States
• 11: R. Cytron , J. Ferrante , B. K. Rosen , M. N. Wegman , F. K. Zadeck, An efficient method of computing static single assignment form, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-35, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75280]
• 12: Jeffrey Dean , Craig Chambers, Towards better inlining decisions using inlining trials, Proceedings of the 1994 ACM conference on LISP and functional programming, p.273-282, June 27-29, 1994, Orlando, Florida, United States
• 13: David Detlefs , Greg Nelson , James B. Saxe, Simplify: a theorem prover for program checking, Journal of the ACM (JACM), v.52 n.3, p.365-473, May 2005 [doi>10.1145/1066100.1066102]
• 14: E. Dijkstra, Go to statement considered harmful, Classics in software engineering, Yourdon Press, Upper Saddle River, NJ, 1979
• 15: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 16: Christopher W. Fraser , Robert R. Henry , Todd A. Proebsting, BURG: fast optimal instruction selection and tree parsing, ACM SIGPLAN Notices, v.27 n.4, p.68-76, April 1992 [doi>10.1145/131080.131089]
• 17: Joseph C. Giarratano , Gary Riley, Expert Systems: Principles and Programming, PWS Publishing Co., Boston, MA, 1994
• 18: Torbjörn Granlund , Richard Kenner, Eliminating branches using a superoptimizer and the GNU C compiler, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.341-352, June 15-19, 1992, San Francisco, California, United States
• 19: Paul Havlak, Construction of Thinned Gated Single-Assignment Form, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.477-499, August 12-14, 1993
• 20: Wesley M. Johnston , J. R. Paul Hanna , Richard J. Millar, Advances in dataflow programming languages, ACM Computing Surveys (CSUR), v.36 n.1, p.1-34, March 2004 [doi>10.1145/1013208.1013209]
• 21: Rajeev Joshi , Greg Nelson , Keith Randall, Denali: a goal-directed superoptimizer, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 22: Keith D. Cooper , Devika Subramanian , Linda Torczon, Adaptive Optimizing Compilers for the 21st Century, The Journal of Supercomputing, v.23 n.1, p.7-22, August 2002 [doi>10.1023/A:1015729001611]
• 23: Sorin Lerner , David Grove , Craig Chambers, Composing dataflow analyses and transformations, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.270-282, January 16-18, 2002, Portland, Oregon
• 24: Henry Massalin, Superoptimizer: a look at the smallest program, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.122-126, October 1987, Palo Alto, California, United States
• 25: George C. Necula, Translation validation for an optimizing compiler, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.83-94, June 18-21, 2000, Vancouver, British Columbia, Canada
• 26: Greg Nelson , Derek C. Oppen, Simplification by Cooperating Decision Procedures, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.2, p.245-257, Oct. 1979 [doi>10.1145/357073.357079]
• 27: Greg Nelson , Derek C. Oppen, Fast Decision Procedures Based on Congruence Closure, Journal of the ACM (JACM), v.27 n.2, p.356-364, April 1980 [doi>10.1145/322186.322198]
• 28: Karl J. Ottenstein , Robert A. Ballance , Arthur B. MacCabe, The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.257-271, June 1990, White Plains, New York, United States
• 29: Keshav Pingali , Micah Beck , Richard Johnson , Mayan Moudgill , Paul Stodghill, Dependence flow graphs: an algebraic approach to program dependencies, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.67-78, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99595]
• 30: Amir Pnueli , Michael Siegel , Eli Singerman, Translation Validation, Proceedings of the 4th International Conference on Tools and Algorithms for Construction and Analysis of Systems, p.151-166, March 28-April 04, 1998
• 31: H. Sheini and K. Sakallah. Pueblo: A hybrid pseudo-boolean SAT solver. Journal on Satisfiability, Boolean Modeling and Computation, 2:61--96, 2006.
• 32: Bernhard Steffen , Jens Knoop , Oliver Rüthing, The Value Flow Graph: A Program Representation for Optimal Program Transformations, Proceedings of the 3rd European Symposium on Programming, p.389-405, May 15-18, 1990
• 33: Ross Tate, Michael Stepp, Zachary Tatlock, and Sorin Lerner. Translating between PEGs and CFGs. Technical Report CS2008-0931, University of California, San Diego, November 2008.
• 34: Peng Tu , David Padua, Efficient building and placing of gating functions, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.47-55, June 18-21, 1995, La Jolla, California, United States
• 35: Raja Vallée-Rai , Phong Co , Etienne Gagnon , Laurie Hendren , Patrick Lam , Vijay Sundaresan, Soot - a Java bytecode optimization framework, Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research, p.13, November 08-11, 1999, Mississauga, Ontario, Canada
• 36: Mark G. J. van den Brand , J. Heering , P. Klint , P. A. Olivier, Compiling language definitions: the ASF+SDF compiler, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.4, p.334-368, July 2002 [doi>10.1145/567097.567099]
• 37: Eelco Visser , Zine-el-Abidine Benaissa , Andrew Tolmach, Building program optimizers with rewriting strategies, Proceedings of the third ACM SIGPLAN international conference on Functional programming, p.13-26, September 26-29, 1998, Baltimore, Maryland, United States
• 38: Daniel Weise , Roger F. Crew , Michael Ernst , Bjarne Steensgaard, Value dependence graphs: representation without taxation, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.297-310, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177907]
• 39: D. Whitfield , M. L. Soffa, An approach to ordering optimizing transformations, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.137-146, March 14-16, 1990, Seattle, Washington, United States
• 40: Deborah L. Whitfield , Mary Lou Soffa, An approach for exploring code improving transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.6, p.1053-1084, Nov. 1997 [doi>10.1145/267959.267960]
• 41: Bin Xin , William N. Sumner , Xiangyu Zhang, Efficient program execution indexing, Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, June 07-13, 2008, Tucson, AZ, USA
• 42: Lenore Zuck, Amir Pnueli, Yi Fang, and Benjamin Goldberg. VOC: A methodology for the translation validation of optimizing compilers. Journal of Universal Computer Science, 9(3):223--247, March 2003.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Languages, Performance

Keywords:
compiler optimization, equality reasoning, intermediate representation