Superoptimization
Template:Short description Template:Use dmy dates Template:Use list-defined references 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.[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 (GCC).[3][4] 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 remains out of reach).[5]
In 2001, goal-directed superoptimizing was demonstrated in the Denali project by Compaq research.[6] In 2006, answer set declarative programming was applied to superoptimization in the Total Optimisation using Answer Set Technology (TOAST) project[7] at the University of Bath.[8][9]
Superoptimization can be used to automatically generate general-purpose peephole optimizers.[10]
Publicly available superoptimizers
Several superoptimizers are available for free download.
- For the x86 family of instruction sets:
- For ARM:
- Unbounded Superoptimizer,[5] transforming LLVM IR into ARMv7-A assembly
- For embedded systems:
- For the JVM:
- Clojure superoptimizer for the Java virtual machine (2012)[18]
- For LLVM IR:
- For WebAssembly
- slumps[20] provides superoptimization for WASM programs based on souper.
See also
References
Template:Compiler optimizations
- ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedMassalin_1987_Superoptimizer - ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedDenali - ↑ a b Cite error: Invalid
<ref>tag; no text was provided for refs namedGCCsuperACM - ↑ a b Cite error: Invalid
<ref>tag; no text was provided for refs namedGCCsuperopt - ↑ a b Script error: No such module "citation/CS1".
- ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedJoshi_2001 - ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedTOAST-KRR - ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedTOAST-book - ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedcrick-phd - ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedBansal_2006 - ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedGSO_1992 - ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedSTOKE - ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedBansal_2008 - ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedSerpell_2003_1 - ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedSerpell_2003_2 - ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedEmbecosm_2014 - ↑ Superoptimization – Embecosm Source Code
- ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedHume_2012 - ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedsouper - ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedslumps