Superoptimization

Quality 0.50 · 1 view · Updated 2 months ago

Compiler optimization technique

title: "Superoptimization" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["compiler-optimizations"] description: "Compiler optimization technique" topic_path: "general/compiler-optimizations" source: "https://en.wikipedia.org/wiki/Superoptimization" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Compiler optimization technique ::

Superoptimization is the process where a 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 only improve code partly, a superoptimizer's goal is to find the optimal sequence, the 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 first coined by Alexia Massalin in the 1987 paper Superoptimizer: A Look at the Smallest Program. 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.

In 1992, the GNU Superoptimizer (GSO) was developed to integrate into the GNU Compiler Collection (GCC). Later work further developed and extended these ideas.

Techniques

Traditionally, superoptimizing is performed via exhaustive 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 to approach the problem, vastly improving the search efficiency (although inputs more complex than a basic block remain out of reach).

In 2001, goal-directed superoptimizing was demonstrated in the Denali project by Compaq research. In 2006, answer set declarative programming was applied to superoptimization in the Total Optimisation using Answer Set Technology (TOAST) project at the University of Bath.

Superoptimization can be used to automatically generate general-purpose peephole optimizers.

Publicly available superoptimizers

Several superoptimizers are available for free download.

  • For the x86 family of instruction sets:
    • GNU superoptimizer (superopt) (GSO) (1992) – also supports many other ISAs
    • STOKE, a stochastic optimizer for x86-64 x86 assembly language.
  • For ARM:
    • Unbounded Superoptimizer, transforming LLVM IR into ARMv7-A assembly
  • For embedded systems:
  • For the JVM:
  • For LLVM IR:
    • souper superoptimizer for programs in the LLVM intermediate language.
  • For WebAssembly
    • slumps provides superoptimization for WASM programs based on souper.

References

References

  1. (25 October 2017). "Unbounded superoptimization".
  2. [https://www.embecosm.com/research/superoptimization/ Superoptimization – Embecosm] [https://github.com/embecosm/gnu-superopt Source Code]
  3. (1987). "Superoptimizer: A look at the smallest program". ACM SIGARCH Computer Architecture News.
  4. (2002). "Denali: A Goal-directed Superoptimizer". ACM SIGPLAN Notices.
  5. (1992). "Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation - PLDI '92".
  6. (1995-06-14). "Index of /gnu/superopt". Free Software Foundation, Inc..
  7. (2001-07-30). "Denali: a goal-directed superoptimizer". [[Hewlett-Packard Co.]].
  8. (2006-08-17). "Logic Programming". [[Springer-Verlag]].
  9. Crick, Tom. (2009). "Superoptimisation: Provably Optimal Code Generation using Answer Set Programming". University of Bath.
  10. . (2007-08-07). ["TOAST – KRRwiki"](http://krr.cs.bath.ac.uk/index.php/TOAST). *[[University of Bath]]*.
  11. (2006). "Automatic Generation of Peephole Superoptimizers".
  12. (2008). "Binary Translation Using Peephole Superoptimizers".
  13. (2003). "SuperOptimizer for Microchip's PIC microcontrollers".
  14. (2003-06-21). "PIC Microcontroller SuperOptimizer". Slashdot Media.
  15. (2012-08-21). "Clojure program to exhaustively search for optimal Java programs".
  16. "GNU Superoptimizer".
  17. StanfordPL. "STOKE".
  18. "A feasibility study by Embecosm".
  19. (2017). "Souper: A Synthesizing Superoptimizer".
  20. (23 March 2020). "Superoptimization of WebAssembly bytecode".

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::

compiler-optimizations