# Superoptimization

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Superoptimization
> Markdown URL: https://mediated.wiki/source/Superoptimization.md
> Source: https://en.wikipedia.org/wiki/Superoptimization
> Source revision: 1354933104
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Compiler optimization technique

**Superoptimization** is the process where a [compiler](/source/Compiler) automatically finds the optimal sequence for a loop-free sequence of instructions. Real-world compilers generally cannot produce genuinely *optimal* code, and while most standard [compiler optimizations](/source/Compiler_optimization) only improve code partly, a superoptimizer's goal is to find the optimal sequence, the [canonical form](/source/Canonical_form). Superoptimizers can be used to improve conventional optimizers by highlighting missed opportunities so a human can write additional rules.

## History

The term superoptimization was coined by [Alexia Massalin](/source/Alexia_Massalin) in the 1987 paper *Superoptimizer: A Look at the Smallest Program*.[1] The label "program optimization" has been given to a field that does not aspire to optimize but only to improve. This misnomer forced Massalin to call her system a superoptimizer, which is actually an optimizer to find an optimal program.[2]

In 1992, the GNU Superoptimizer (GSO) was developed to integrate into the [GNU Compiler Collection](/source/GNU_Compiler_Collection) (GCC).[3][4] Later work further developed and extended these ideas.

## Techniques

Traditionally, superoptimizing is performed via exhaustive [brute-force search](/source/Brute-force_search) in the space of valid instruction sequences. This is a costly method, and largely impractical for general-purpose compilers. Yet, it has been shown to be useful in optimizing performance-critical inner loops. It is also possible to use a [SMT solver](/source/Satisfiability_modulo_theories) to approach the problem, vastly improving the search efficiency (although inputs more complex than a [basic block](/source/Basic_block) remain out of reach).[5]

In 2001, goal-directed superoptimizing was demonstrated in the Denali project by Compaq research.[6] In 2006, [answer set](/source/Answer_set_programming) [declarative programming](/source/Declarative_programming) was applied to superoptimization in the *Total Optimisation using Answer Set Technology* (TOAST) project[7] at the [University of Bath](/source/University_of_Bath).[8][9]

Superoptimization can be used to automatically generate general-purpose [peephole optimizers](/source/Peephole_optimization).[10]

## Publicly available superoptimizers

Several superoptimizers are available for free download.

- For the x86 family of instruction sets: - GNU superoptimizer (superopt)[11] (GSO) (1992)[3][4] – also supports many other ISAs - STOKE,[12] a stochastic optimizer[13] for [x86-64](/source/X86-64) [x86 assembly language](/source/X86_assembly_language).

- For ARM: - Unbounded Superoptimizer,[5] transforming LLVM IR into ARMv7-A assembly

- For embedded systems: - [PIC microcontroller](/source/PIC_microcontroller) SuperOptimizer (2003)[14][15] - A feasibility study by Embecosm (2014) for [AVR](/source/AVR_microcontrollers), based on GSO[16][17]

- For the JVM: - [Clojure](/source/Clojure) superoptimizer for the [Java virtual machine](/source/Java_virtual_machine) (2012)[18]

- For LLVM IR: - souper[19] superoptimizer for programs in the [LLVM](/source/LLVM) intermediate language.

- For WebAssembly - slumps[20] provides superoptimization for WASM programs based on souper.

## See also

- [Peephole optimization](/source/Peephole_optimization)

- [Dead code elimination](/source/Dead_code_elimination)

- [Metacompilation](/source/Metacompilation)

## References

1. **[^](#cite_ref-Massalin_1987_Superoptimizer_1-0)** Massalin, Henry (1987). ["Superoptimizer: A look at the smallest program"](https://web.stanford.edu/class/cs343/resources/superoptimizer.pdf) (PDF). *ACM SIGARCH Computer Architecture News*. **15** (5): 122–126. [doi](/source/Doi_(identifier)):[10.1145/36177.36194](https://doi.org/10.1145%2F36177.36194). Retrieved 2023-05-01. Given an instruction set, the superoptimizer finds the shortest program to compute a function. Startling programs have been generated, many of them engaging in convoluted bit-fiddling bearing little resemblance to the source programs which defined the functions. The key idea in the superoptimizer is a probabilistic test that makes exhaustive searches practical for programs of useful size.

1. **[^](#cite_ref-Denali_2-0)** Joshi, Rajeev; Nelson, Greg; Randall, Keith (2002). ["Denali: A Goal-directed Superoptimizer"](https://dl.acm.org/doi/10.1145/543552.512566). *ACM SIGPLAN Notices*. **37** (5): 304–314. [doi](/source/Doi_(identifier)):[10.1145/543552.512566](https://doi.org/10.1145%2F543552.512566).

1. ^ [***a***](#cite_ref-GCCsuperACM_3-0) [***b***](#cite_ref-GCCsuperACM_3-1) Granlund, Torbjörn; Kenner, Richard (1992). "Eliminating branches using a superoptimizer and the GNU C compiler". *Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation - PLDI '92*. [CiteSeerX](/source/CiteSeerX_(identifier)) [10.1.1.58.3509](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.3509). [doi](/source/Doi_(identifier)):[10.1145/143095.14314](https://doi.org/10.1145%2F143095.14314) (inactive 2025-09-07). [ISBN](/source/ISBN_(identifier)) [978-0-89791475-8](https://en.wikipedia.org/wiki/Special:BookSources/978-0-89791475-8). [S2CID](/source/S2CID_(identifier)) [8825539](https://api.semanticscholar.org/CorpusID:8825539).{{[cite book](https://en.wikipedia.org/wiki/Template:Cite_book)}}: CS1 maint: DOI inactive as of September 2025 ([link](https://en.wikipedia.org/wiki/Category:CS1_maint:_DOI_inactive_as_of_September_2025))

1. ^ [***a***](#cite_ref-GCCsuperopt_4-0) [***b***](#cite_ref-GCCsuperopt_4-1) ["Index of /gnu/superopt"](https://ftp.gnu.org/gnu/superopt/). *GNU Operating System*. Free Software Foundation, Inc. 1995-06-14. Retrieved 2023-05-01.

1. ^ [***a***](#cite_ref-jangda_5-0) [***b***](#cite_ref-jangda_5-1) Jangda, Abhinav; Yorsh, Greta (2017-10-25). *Unbounded superoptimization*. Onward!’17, October 25–27, 2017, Vancouver, Canada. pp. 78–88. [doi](/source/Doi_(identifier)):[10.1145/3133850.3133856](https://doi.org/10.1145%2F3133850.3133856).

1. **[^](#cite_ref-Joshi_2001_6-0)** Joshi, Rajeev; Nelson, Greg; Randall, Keith (2001-07-30). ["Denali: a goal-directed superoptimizer"](https://hpl.hp.com/techreports/Compaq-DEC/SRC-RR-171.html). Compaq Systems Research Center. *HP Labs*. [Hewlett-Packard Co.](/source/Hewlett-Packard_Co.) Retrieved 2023-05-01.

1. **[^](#cite_ref-TOAST-KRR_7-0)** ["TOAST – KRRwiki"](https://web.archive.org/web/20121128143632/http://krr.cs.bath.ac.uk/index.php/TOAST). Department of Computer Science, Mathematical Foundations Group. *Knowledge Representation and Reasoning (KRR) group*. [University of Bath](/source/University_of_Bath). 2007-08-07. Archived from [the original](http://krr.cs.bath.ac.uk/index.php/TOAST) on 2012-11-28. Retrieved 2016-09-03.

1. **[^](#cite_ref-TOAST-book_8-0)** Brain, Martin; Crick, Tom; De Vos, Marina; Fitch, John (2006-08-17). "TOAST: Applying Answer Set Programming to Superoptimisation". In Etalle, Sandro; Truszczyński, Mirosław (eds.). *Logic Programming*. Lecture Notes in Computer Science. Vol. 4079. [Springer-Verlag](/source/Springer-Verlag). pp. 270–284. [doi](/source/Doi_(identifier)):[10.1007/11799573_21](https://doi.org/10.1007%2F11799573_21). [ISBN](/source/ISBN_(identifier)) [978-3-540-36636-2](https://en.wikipedia.org/wiki/Special:BookSources/978-3-540-36636-2).

1. **[^](#cite_ref-crick-phd_9-0)** Crick, Tom (2009). [*Superoptimisation: Provably Optimal Code Generation using Answer Set Programming*](https://researchportal.bath.ac.uk/en/studentTheses/superoptimisation-provably-optimal-code-generation-using-answer-s) (PhD thesis). University of Bath. Retrieved 2024-11-15.

1. **[^](#cite_ref-Bansal_2006_10-0)** Bansal, Sorav; Aiken, Alex (2006). ["Automatic Generation of Peephole Superoptimizers"](https://sorav.compiler.ai/pubs/asplos06.pdf) (PDF). Retrieved 2023-05-01.

1. **[^](#cite_ref-GSO_1992_11-0)** ["GNU Superoptimizer"](https://www.gnu.org/software/superopt/).

1. **[^](#cite_ref-STOKE_12-0)** StanfordPL. ["STOKE"](https://github.com/StanfordPL/stoke). *[GitHub](/source/GitHub)*.

1. **[^](#cite_ref-Bansal_2008_13-0)** Bansal, Sorav; Aiken, Alex (2008). ["Binary Translation Using Peephole Superoptimizers"](https://sorav.compiler.ai/pubs/osdi08.pdf) (PDF). Retrieved 2023-05-01.

1. **[^](#cite_ref-Serpell_2003_1_14-0)** Serpell, Daniel (2003). ["SuperOptimizer for Microchip's PIC microcontrollers"](https://sites.google.com/site/danielserpell/picmicrocontrollersuperoptimizer). *Google Sites*. [Archived](https://web.archive.org/web/20161011090623/https://sites.google.com/site/danielserpell/picmicrocontrollersuperoptimizer) from the original on 2016-10-11. Retrieved 2016-09-06.

1. **[^](#cite_ref-Serpell_2003_2_15-0)** Serpell, Daniel (2003-06-21). ["PIC Microcontroller SuperOptimizer"](http://freecode.com/projects/picsuperoprimizer/). *Freecode*. Slashdot Media. [Archived](https://web.archive.org/web/20160917164828/http://freecode.com/projects/picsuperoprimizer/) from the original on 2016-09-17. Retrieved 2016-09-06.

1. **[^](#cite_ref-Embecosm_2014_16-0)** ["A feasibility study by Embecosm"](http://superoptimization.org).

1. **[^](#cite_ref-17)** [Superoptimization – Embecosm](https://www.embecosm.com/research/superoptimization/) [Source Code](https://github.com/embecosm/gnu-superopt)

1. **[^](#cite_ref-Hume_2012_18-0)** Hume, Tom (2012-08-21). ["Clojure program to exhaustively search for optimal Java programs"](https://github.com/twhume/superoptimiser). *GitHub*. [Archived](https://web.archive.org/web/20180610233155/https://github.com/twhume/superoptimiser) from the original on 2018-06-10. Retrieved 2016-09-06.

1. **[^](#cite_ref-souper_19-0)** Sasnauskas, Raimondas; Chen, Yang; Collingbourne, Peter; Ketema, Jeroen; Lup, Gratian; Taneja, Jubi; Regehr, John (2017). "Souper: A Synthesizing Superoptimizer". [arXiv](/source/ArXiv_(identifier)):[1711.04422](https://arxiv.org/abs/1711.04422) [[cs.PL](https://arxiv.org/archive/cs.PL)]. [GitHub source code](https://github.com/google/souper)

1. **[^](#cite_ref-slumps_20-0)** Cabrera Arteaga, Javier; Donde, Shrinish; Gu, Jian; Floros, Orestis; Satabin, Lucas; Baudry, Benoit; Monperrus, Martin (2020-03-23). *Superoptimization of WebAssembly bytecode*. MoreVMs: Workshop on Modern Language Runtimes, Ecosystems, and VMs. pp. 36–40. [arXiv](/source/ArXiv_(identifier)):[2002.10213](https://arxiv.org/abs/2002.10213). [doi](/source/Doi_(identifier)):[10.1145/3397537.3397567](https://doi.org/10.1145%2F3397537.3397567). [GitHub source code](https://github.com/KTH/slumps/tree/master/superoptimizer)

v t e Compiler optimizations Basic block Peephole optimization Local value numbering Loop Automatic parallelization Automatic vectorization Induction variable Loop fusion Loop-invariant code motion Loop inversion Loop interchange Loop nest optimization Loop splitting Loop unrolling Loop unswitching Software pipelining Strength reduction Data-flow analysis Available expression Common subexpression elimination Constant folding Dead store elimination Induction variable recognition and elimination Live-variable analysis Upwards exposed uses Use-define chain Reaching definitions SSA-based Global value numbering Sparse conditional constant propagation Code generation Instruction scheduling Instruction selection Register allocation Rematerialization Functional Deforestation Tail-call elimination Global Interprocedural optimization Other Bounds-checking elimination Compile-time function execution Dead-code elimination Expression templates Inline expansion Jump threading Partial evaluation Profile-guided optimization Static analysis Alias analysis Array-access analysis Control-flow analysis Data-flow analysis Dependence analysis Escape analysis Pointer analysis Shape analysis Value range analysis

---
Adapted from the Wikipedia article [Superoptimization](https://en.wikipedia.org/wiki/Superoptimization) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Superoptimization?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.