Automatic generation of peephole superoptimizers

ABSTRACT

Peephole optimizers are typically constructed using human-written pattern matching rules, an approach that requires expertise and time, as well as being less than systematic at exploiting all opportunities for optimization. We explore fully automatic construction of peephole optimizers using brute force superoptimization. While the optimizations discovered by our automatic system may be less general than human-written counterparts, our approach has the potential to automatically learn a database of thousands to millions of optimizations, in contrast to the hundreds found in current peephole optimizers. We show experimentally that our optimizer is able to exploit performance opportunities not found by existing compilers; in particular, we show speedups from 1.7 to a factor of 10 on some compute intensive kernels over a conventional optimizing compiler.

REFERENCES

• 1: Intel C++ Compiler 9.0. Software available at http://www.intel.com/software/products/compilers/clin.
• 2: Superoptimizer prototype. Available on the web at http://cs.stanford.edu/~sbansal/superoptimizer/.
• 3: B. Anckaert, F. Vandeputte, B.D. Bus, B.D. Sutter, and K.D. Bosschere. Link-time optimization of ia64 binaries. In Proceedings of the 10th International Euro-par Conference, pages 211--220, 2004.
• 4: M. E. Benitez , J. W. Davidson, A portable global optimizer and linker, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.329-338, June 20-24, 1988, Atlanta, Georgia, United States
• 5: Jack W. Davidson , Christopher W. Fraser, Code selection through object code optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.505-526, Oct. 1984 [doi>10.1145/1780.1783]
• 6: 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
• 7: John L. Henning, SPEC CPU2000: Measuring CPU Performance in the New Millennium, Computer, v.33 n.7, p.28-35, July 2000 [doi>10.1109/2.869367]
• 8: 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
• 9: X. Leroy, D. Doligez, J. Garrigue, and J. Vouillon. The Objective Caml system. Software and documentation available at http://caml.inria.fr.
• 10: 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
• 11: Matthew W. Moskewicz , Conor F. Madigan , Ying Zhao , Lintao Zhang , Sharad Malik, Chaff: engineering an efficient SAT solver, Proceedings of the 38th conference on Design automation, p.530-535, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379017]
• 12: L.V. Put, D. Chanet, B.D. Bus, B.D. Sutter, and K.D. Bosschere. Diablo: a reliable, retargetable and extensible link-time rewriting framework. In Proceedings of the 2005 IEEE International Symposium on Signal Processing and Information Technology, pages 7--12, 2005.
• 13: Lintao Zhang , Conor F. Madigan , Matthew H. Moskewicz , Sharad Malik, Efficient conflict driven learning in a boolean satisfiability solver, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
code selection, peephole optimization, superoptimization