Elamur Research⌕
☰
home / papers / 2006 / Automatic Generation of Peephole Superoptimizers

Automatic Generation of Peephole Superoptimizers

Paper · 2006 · Sorav Bansal and Alex Aiken

Summary

Peephole optimizers usually depend on rewrite rules written by hand. Writing them takes architecture expertise, and the resulting rule sets cover only a few hundred cases. Bansal and Aiken show that such rules can instead be learned automatically through brute-force superoptimization done ahead of time.

Their system has three parts:

  • A harvester collects short single-entry instruction sequences from existing x86 binaries, along with the registers live at each sequence's end.
  • An enumerator exhaustively generates candidate sequences and checks each one against all harvested targets at once.
  • Fingerprint hashing filters candidates quickly, and a SAT-based test confirms true equivalence.

Canonicalization keeps the search manageable by discarding sequences that differ only in register or constant names. Verified rewrites go into an indexed database, so applying them at compile time costs no more than a conventional peephole pass. The prototype supports nearly the full x86 opcode set, including memory accesses and branches. It learned thousands of rules and sped up several compute-heavy kernels by 1.7× to 10× over an optimizing compiler. This suggests mature compilers still leave substantial performance unexploited.

Key points

  • The work was published at ASPLOS 2006 by Sorav Bansal and Alex Aiken (Stanford). They frame the rule database as something that could grow to millions of entries and be served like a search engine.
  • The prototype covers roughly 300+ x86 opcodes. The authors call it the first superoptimizer to correctly handle memory operations and branches and to account for live-register context.
  • The pipeline runs harvester → canonicalizer → fingerprint hashtable → Boolean (SAT) equivalence test → optimization database. The cost of a single enumeration is shared across many target sequences.
  • Compared with earlier systems:
    • The GNU Superoptimizer (GSO) produced a few tens of rules and needed manually specified goal functions.
    • Massalin's search reached sequences of about 12 instructions but used only 10–15 opcodes.
    • Denali relies on hand-written axioms.
  • One limitation is that the system misses optimizations involving loop-carried dependencies, such as keeping a loop variable in a register. Loop unrolling is suggested as a partial workaround.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Stanford UniversityStanford · United States567 works · 335,189 citations

 Fields, topics and concepts

📚 Shelves 3The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksHardware and Architecture · 183 works

Cite

Cite as Sorav Bansal and Alex Aiken. 2006. Automatic Generation of Peephole Superoptimizers. ASPLOS 2006.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{bansal2006automatic,
  title = {{Automatic Generation of Peephole Superoptimizers}},
  author = {Sorav Bansal and Alex Aiken},
  booktitle = {ASPLOS 2006},
  year = {2006},
  doi = {10.1145/1168857.1168906},
  url = {https://doi.org/10.1145/1168857.1168906}
}

References

13 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  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. find
  4. M. E. Benitez and J. W. Davidson. A portable global optimizer and linker. In Proceedings of the SIGPLAN ’88 Conference on Programming Language Design and Implementation, pages 329– 338, 1988. find
  5. J. Davidson and C. Fraser. Code selection through object code optimization. ACM Transactions on Programming Languages and Systems (TOPLAS), 6(4):505–526, 1984. find
  6. T. Granlund and R. Kenner. Eliminating branches using a superoptimizer and the gnu C compiler. In Proceedings of the ACM SIGPLAN ’92 Conference on Programming Language Design and Implementation, volume 27, pages 341–352, San Francisco, CA, June 1992. find
  7. J. L. Henning. SPEC CPU2000: Measuring CPU performance in the new millenium. IEEE Computer, 33(7):28–35, July 2000. find
  8. R. Joshi, G. Nelson, and K. H. Randall. Denali: A goal-directed superoptimizer. In Proceedings of the ACM SIGPLAN ’02 Conference on Programming Language Design and Implementation, pages 304– 314, Berlin, Germany, June 2002. find
  9. X. Leroy, D. Doligez, J. Garrigue, and J. Vouillon. The Objective Caml system. Software and documentation available at http://caml.inria.fr. ↗
  10. H. Massalin. Superoptimizer: A look at the smallest program. In Second International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS II), pages 122–126, 1987. find
  11. M. W. Moskewicz, C. F. Madigan, Y. Zhao, L. Zhang, and S. Malik. Chaff: Engineering an Efficient SAT Solver. In Proceedings of the 38th Design Automation Conference (DAC’01), 2001.
  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. find
  13. L. Zhang, C. F. Madigan, M. W. Moskewicz, and S. Malik. Efficient conflict driven learning in boolean satisfiability solver. In ICCAD, pages 279–285, 2001. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/bansal-2006-automatic-generation-peephole-superoptimizers/