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.
- L. Almagor, K. D. Cooper, A. Grosul, T. J. Harvey, S. W. Reeves, D. Subramanian, L. Torczon, and T. Waterman. Finding effective compilation sequences. In LCTES, 2004. Google ScholarDigital Library
- B. Alpern, M.Wegman, and F. Zadeck. Detecting equality of variables in programs. In POPL, January 1988. Google ScholarDigital Library
- E. A. Ashcroft and W. W. Wadge. Lucid, a nonprocedural language with iteration. Communications of the ACM, 20(7):519--526, 1977. Google ScholarDigital Library
- S. Bansal and A. Aiken. Automatic generation of peephole superoptimizers. In ASPLOS, 2006. Google ScholarDigital Library
- R. Bird and P. Wadler. Introduction to Functional Programming. Prentice Hall, 1988. Google ScholarDigital Library
- James M. Boyle, Terence J. Harmer, and Victor L. Winter. The TAMPR program transformation system: simplifying the development of numerical software. Modern software tools for scientific computing, pages 353--372, 1997. Google ScholarDigital Library
- M. Bravenboer, K. T. Kalleberg, R. Vermaas, and E. Visser. Stratego/XT 0.17. A language and toolset for program transformation. Science of Computer Programming, 72(1-2):52--70, 2008. Google ScholarDigital Library
- K. D. Cooper C. Click. Combining analyses, combining optimizations. Transactions on Programming Languages and Systems, 17(2):181--196, 1995. Google ScholarDigital Library
- C. Click. Global code motion/global value numbering. In PLDI, June 1995. Google ScholarDigital Library
- K. D. Cooper, P. J. Schielke, and Subramanian D. Optimizing for reduced code space using genetic algorithms. In LCTES, 1999. Google ScholarDigital Library
- R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. An efficient method for computing static single assignment form. In POPL, January 1989. Google ScholarDigital Library
- Jeffrey Dean and Craig Chambers. Towards better inlining decisions using inlining trials. In Conference on LISP and Functional Programming, 1994. Google ScholarDigital Library
- D. Detlefs, G. Nelson, and J. Saxe. Simplify: A theorem prover for program checking. Journal of the Association for Computing Machinery, 52(3):365--473, May 2005. Google ScholarDigital Library
- E. Dijkstra. Go to statement considered harmful. pages 27--33, 1979. Google ScholarDigital Library
- J. Ferrante, K. Ottenstein, and J. Warren. The program dependence graph and its use in optimization. Transactions on Programming Languages and Systems, 9(3):319--349, July 1987. Google ScholarDigital Library
- Christopher W. Fraser, Robert R. Henry, and Todd A. Proebsting. BURG: fast optimal instruction selection and tree parsing. SIGPLAN Notices, 27(4):68--76, April 1992. Google ScholarDigital Library
- J. Giarratano and G. Riley. Expert Systems -- Principles and Programming. PWS Publishing Company, 1993. Google ScholarDigital Library
- Torbjorn Granlund and Richard Kenner. Eliminating branches using a superoptimizer and the GNU C compiler. In PLDI, 1992. Google ScholarDigital Library
- P. Havlak. Construction of thinned gated single-assignment form. In Workshop on Languages and Compilers for Parallel Computing, 1993. Google ScholarDigital Library
- W. M. Johnston, J. R. P. Hanna, and R. J. Millar. Advances in dataflow programming languages. ACM Computing Surveys, 36(1):1--34, 2004. Google ScholarDigital Library
- R. Joshi, G. Nelson, and K. Randall. Denali: a goal-directed superoptimizer. In PLDI, June 2002. Google ScholarDigital Library
- L. Torczon K. D. Cooper, D. Subramanian. Adaptive optimizing compilers for the 21st century. The Journal of Supercomputing, pages 7--22, 2002. Google ScholarDigital Library
- S. Lerner, D. Grove, and C. Chambers. Composing dataflow analyses and transformations. In POPL, January 2002. Google ScholarDigital Library
- Henry Massalin. Superoptimizer: a look at the smallest program. In ASPLOS, 1987. Google ScholarCross Ref
- G. Necula. Translation validation for an optimizing compiler. In PLDI, June 2000. Google ScholarDigital Library
- G. Nelson and D. Oppen. Simpliflication by cooperating decision procedures. Transactions on Programming Languages and Systems, 1(2):245--257, October 1979. Google ScholarDigital Library
- G. Nelson and D. Oppen. Fast decision procedures based on congruence closure. Journal of the Association for Computing Machinery, 27(2):356--364, April 1980. Google ScholarDigital Library
- K. Ottenstein, R. Ballance, and A. MacCabe. The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages. In PLDI, June 1990. Google ScholarDigital Library
- K. Pengali, M. Beck, and R. Johson. Dependence Flow graphs: an algebraic approach to program dependencies. In POPL, January 1991. Google ScholarDigital Library
- A. Pnueli, M. Siegel, and E. Singerman. Translation validation. In TACAS, 1998. Google ScholarDigital Library
- H. Sheini and K. Sakallah. Pueblo: A hybrid pseudo-boolean SAT solver. Journal on Satisfiability, Boolean Modeling and Computation, 2:61--96, 2006.Google Scholar
- B. Steffen, J. Knoop, and O. Ruthing. The value flow graph: A program representation for optimal program transformations. In European Symposium on Programming, 1990. Google ScholarDigital Library
- 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.Google Scholar
- P. Tu and D. Padua. Efficient building and placing of gating functions. In PLDI, June 1995. Google ScholarDigital Library
- R. Vallee-Rai, L. Hendren, V. Sundaresan, P. Lam, E. Gagnon, and P. Co. Soot -- a Java optimization framework. In CASCON, 1999. Google ScholarDigital Library
- M. G. J. van den Brand, J. Heering, P. Klint, and P. A. Olivier. Compiling language definitions: the ASF+SDF compiler. Transactions on Programming Languages and Systems, 24(4), 2002. Google ScholarDigital Library
- E. Visser, Z. Benaissa, and A Tolmach. Building program optimizers with rewriting strategies. In ICFP, 1998. Google ScholarDigital Library
- D. Weise, R. Crew, M. Ernst, and B. Steensgaard. Value dependence graphs: Representation without taxation. In POPL, 1994. Google ScholarDigital Library
- Debbie Whitfield and Mary Lou Soffa. An approach to ordering optimizing transformations. In PPOPP, 1990. Google ScholarDigital Library
- Deborah L. Whitfield and Mary Lou Soffa. An approach for exploring code improving transformations. Transactions on Programming Languages and Systems, 19(6):1053--1084, November 1997. Google ScholarDigital Library
- B. Xin, W. N. Sumner, and X. Zhang. Efficient program execution indexing. In PLDI, June 2008. Google ScholarDigital Library
- 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.Google Scholar
Index Terms
- Equality saturation: a new approach to optimization
Recommendations
Equality saturation: a new approach to optimization
POPL '09Optimizations 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 ...
QIRO: A Static Single Assignment-based Quantum Program Representation for Optimization
We propose an IR for quantum computing that directly exposes quantum and classical data dependencies for the purpose of optimization. The Quantum Intermediate Representation for Optimization(QIRO) consists of two dialects, one input dialect and one that ...
Comments