---
title: "Automatic Generation of Peephole Superoptimizers — Bansal 2006"
description: "Bansal and Aiken show that such rules can instead be learned automatically through brute-force… 13 references, cited by 19 papers here."
authors: ["Sorav Bansal", "Alex Aiken"]
year: 2006
venue: "ASPLOS 2006"
source: "https://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf"
licence: "author's copy — read only"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/bansal-2006-automatic-generation-peephole-superoptimizers/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/bansal-2006-automatic-generation-peephole-superoptimizers/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2006](https://md.research.elamur.ai/free/en/papers/2006/) / Automatic Generation of Peephole Superoptimizers

# Automatic Generation of Peephole Superoptimizers

**Authors:** Sorav Bansal and [Alex Aiken](https://md.research.elamur.ai/free/en/authors/alex-aiken/) · **Year:** 2006 · **Venue:** ASPLOS 2006 · **Licence:** author's copy — read only

**Links:** [Publisher's page](https://doi.org/10.1145/1168857.1168906) · [PDF](https://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf) · [OpenAlex](https://openalex.org/W2160145830)

**Citations:** 161 citations (OpenAlex, 2026-10-14) · [19](https://md.research.elamur.ai/free/en/papers/bansal-2006-automatic-generation-peephole-superoptimizers/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## 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 University](https://md.research.elamur.ai/free/en/universities/stanford-university/) — University, Stanford, United States · 567 works · 335,189 citations

📚 Shelves (3): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 19,503 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 18,805 works · [🔌 Hardware and Architecture](https://md.research.elamur.ai/free/en/shelves/computer-science/hardware-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.

```bibtex
@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}
}
```

- [← previous Discriminant-Based MRS Banking](https://md.research.elamur.ai/free/en/papers/oepen-2006-discriminant-based-mrs-banking/)
- [next → Phrasetable Smoothing for Statistical Machine Translation](https://md.research.elamur.ai/free/en/papers/foster-2006-phrasetable-smoothing-statistical-machine-translation/)
- [↑ back to papers of 2006](https://md.research.elamur.ai/free/en/papers/2006/)

## 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](http://www.intel.com/software/products/compilers/clin). [↗](http://www.intel.com/software/products/compilers/clin)
2. Superoptimizer prototype. Available on the web at [http://cs.stanford.edu/∼sbansal/superoptimizer/](http://cs.stanford.edu/∼sbansal/superoptimizer/). [↗](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](https://scholar.google.com/scholar?q=B%2E+Anckaert%2C+F%2E+Vandeputte%2C+B%2E+D%2E+Bus%2C+B%2E+D%2E+Sutter%2C+and+K%2E+D%2E+Bosschere%2E+Link%2Dtime+optimization+of+ia64+binaries%2E+In+Proceedings+of+the+10th+International+Euro%2Dpar+Conference%2C+pages+211%E2%80%93220%2C+2004%2E)
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](https://scholar.google.com/scholar?q=M%2E+E%2E+Benitez+and+J%2E+W%2E+Davidson%2E+A+portable+global+optimizer+and+linker%2E+In+Proceedings+of+the+SIGPLAN+%E2%80%9988+Conference+on+Programming+Language+Design+and+Implementation%2C+pages+329%E2%80%93+338%2C+1988%2E)
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](https://scholar.google.com/scholar?q=J%2E+Davidson+and+C%2E+Fraser%2E+Code+selection+through+object+code+optimization%2E+ACM+Transactions+on+Programming+Languages+and+Systems+%28TOPLAS%29%2C+6%284%29%3A505%E2%80%93526%2C+1984%2E)
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](https://scholar.google.com/scholar?q=T%2E+Granlund+and+R%2E+Kenner%2E+Eliminating+branches+using+a+superoptimizer+and+the+gnu+C+compiler%2E+In+Proceedings+of+the+ACM+SIGPLAN+%E2%80%9992+Conference+on+Programming+Language+Design+and+Implementation%2C+volum)
7. J. L. Henning. SPEC CPU2000: Measuring CPU performance in the new millenium. IEEE Computer, 33(7):28–35, July 2000. [find](https://scholar.google.com/scholar?q=J%2E+L%2E+Henning%2E+SPEC+CPU2000%3A+Measuring+CPU+performance+in+the+new+millenium%2E+IEEE+Computer%2C+33%287%29%3A28%E2%80%9335%2C+July+2000%2E)
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](https://scholar.google.com/scholar?q=R%2E+Joshi%2C+G%2E+Nelson%2C+and+K%2E+H%2E+Randall%2E+Denali%3A+A+goal%2Ddirected+superoptimizer%2E+In+Proceedings+of+the+ACM+SIGPLAN+%E2%80%9902+Conference+on+Programming+Language+Design+and+Implementation%2C+pages+304%E2%80%93+314%2C+Berl)
9. X. Leroy, D. Doligez, J. Garrigue, and J. Vouillon. The Objective Caml system. Software and documentation available at [http://caml.inria.fr](http://caml.inria.fr). [↗](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](https://scholar.google.com/scholar?q=H%2E+Massalin%2E+Superoptimizer%3A+A+look+at+the+smallest+program%2E+In+Second+International+Conference+on+Architectural+Support+for+Programming+Languages+and+Operating+Systems+%28ASPLOS+II%29%2C+pages+122%E2%80%93126%2C+198)
11. M. W. Moskewicz, C. F. Madigan, Y. Zhao, L. Zhang, and S. Malik. [Chaff: Engineering an Efficient SAT Solver](https://md.research.elamur.ai/free/en/papers/moskewicz-2001-chaff-engineering-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](https://scholar.google.com/scholar?q=L%2E+V%2E+Put%2C+D%2E+Chanet%2C+B%2E+D%2E+Bus%2C+B%2E+D%2E+Sutter%2C+and+K%2E+D%2E+Bosschere%2E+Diablo%3A+a+reliable%2C+retargetable+and+extensible+link%2Dtime+rewriting+framework%2E+In+Proceedings+of+the+2005+IEEE+International+Symposi)
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](https://scholar.google.com/scholar?q=L%2E+Zhang%2C+C%2E+F%2E+Madigan%2C+M%2E+W%2E+Moskewicz%2C+and+S%2E+Malik%2E+Efficient+conflict+driven+learning+in+boolean+satisfiability+solver%2E+In+ICCAD%2C+pages+279%E2%80%93285%2C+2001%2E)

*Updated 3 November 2026*