Superoptimization
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 thus 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 used for superoptimising in the Total Optimisation using Answer Set Technology (TOAST) project at the University of Bath.[7][8]
Superoptimization can be used to automatically generate general-purpose peephole optimizers.[9]
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)[17]
- For LLVM IR:
- For WebAssembly
- slumps[19] provides superoptimization for WASM programs based on souper.
See also
References
- ↑ "Superoptimizer: A look at the smallest program". ACM SIGARCH Computer Architecture News 15 (5): 122–126. 1987. doi:10.1145/36177.36194. https://web.stanford.edu/class/cs343/resources/superoptimizer.pdf. 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.".
- ↑ Joshi, Rajeev; Nelson, Greg; Randall, Keith (2002). "Denali: A Goal-directed Superoptimizer". ACM SIGPLAN Notices 37 (5): 304–314. doi:10.1145/543552.512566. https://dl.acm.org/doi/10.1145/543552.512566.
- ↑ 3.0 3.1 "Eliminating branches using a superoptimizer and the GNU C compiler". ACM SIGPLAN Notices 27 (7): 341–352. July 1992. doi:10.1145/143095.143146. ISBN 978-0-89791475-8.
- ↑ 4.0 4.1 "Index of /gnu/superopt". Free Software Foundation, Inc.. 1995-06-14. https://ftp.gnu.org/gnu/superopt/.
- ↑ 5.0 5.1 Jangda, Abhinav; Yorsh, Greta (25 October 2017). "Unbounded superoptimization". Onward!’17, October 25–27, 2017, Vancouver, Canada. pp. 78–88. doi:10.1145/3133850.3133856.
- ↑ "Denali: a goal-directed superoptimizer". Hewlett-Packard Co.. 2001-07-30. https://hpl.hp.com/techreports/Compaq-DEC/SRC-RR-171.html.
- ↑ "TOAST: Applying Answer Set Programming to Superoptimisation". Logic Programming. Springer-Verlag, Berlin / Heidelberg. 2006-08-17. pp. 270–284. ISBN 978-3-540-36636-2.
- ↑ "TOAST – KRRwiki". University of Bath. 2007-08-07. http://krr.cs.bath.ac.uk/index.php/TOAST.
- ↑ "Automatic Generation of Peephole Superoptimizers". 2006. https://sorav.compiler.ai/pubs/asplos06.pdf.
- ↑ "GNU Superoptimizer". https://www.gnu.org/software/superopt/.
- ↑ StanfordPL. "STOKE". https://github.com/StanfordPL/stoke.
- ↑ "Binary Translation Using Peephole Superoptimizers". 2008. https://sorav.compiler.ai/pubs/osdi08.pdf.
- ↑ "SuperOptimizer for Microchip's PIC microcontrollers". 2003. https://sites.google.com/site/danielserpell/picmicrocontrollersuperoptimizer.
- ↑ "PIC Microcontroller SuperOptimizer". Slashdot Media. 2003-06-21. http://freecode.com/projects/picsuperoprimizer/.
- ↑ "A feasibility study by Embecosm". http://superoptimization.org.
- ↑ Superoptimization – Embecosm Source Code
- ↑ "Clojure program to exhaustively search for optimal Java programs". 2012-08-21. https://github.com/twhume/superoptimiser.
- ↑ Sasnauskas, Raimondas; Chen, Yang; Collingbourne, Peter; Ketema, Jeroen; Lup, Gratian; Taneja, Jubi; Regehr, John (2017). "Souper: A Synthesizing Superoptimizer". arXiv:1711.04422. GitHub source code
- ↑ Cabrera Arteaga, Javier; Donde, Shrinish; Gu, Jian; Floros, Orestis; Satabin, Lucas; Baudry, Benoit; Monperrus, Martin (23 March 2020). "Superoptimization of WebAssembly bytecode". MoreVMs: Workshop on Modern Language Runtimes, Ecosystems, and VMs. pp. 36–40. doi:10.1145/3397537.3397567. GitHub source code
![]() | Original source: https://en.wikipedia.org/wiki/Superoptimization.
Read more |