Superoptimization is the process of automatically finding the optimal code sequence for one, loop-free sequence of instructions. It is performed in and by a type of computer software termed a compiler. Real-world compilers generally cannot produce genuinely optimal code. While most standard compiler optimizations only improve code partly, a superoptimizer's goal is to find the optimal sequence, the canonical form.
The term superoptimization was first coined by Henry Massalin in the 1987 paper Superoptimizer: A Look at the Smallest 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. In 2001, goal-directed superoptimizing was demonstrated in the Denali project by Compaq research. 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, and superoptimizing was used to automatically generate general-purpose peephole optimizers.
Typically, 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.
Publicly available superoptimizers
Superoptimizer studies, documents, and several working examples, are available for free download.
- GNU Superoptimizer (GSO) (1992)
- Total Optimisation using Answer Set Technology (TOAST) project (2006)
- The Aha! (A Hacker's Assistant) Superoptimizer (and paper about it) (2006)
- Stanford Superoptimizer (2006)
- PIC microcontroller SuperOptimizer (2003)
- Clojure superoptimizer for the Java virtual machine (2012)
- A feasibility study by Embecosm (2014)
- STOKE - A stochastic optimizer for x86-64 x86 assembly language.
- souper superoptimizer for programs in the LLVM intermediate language.
- Massalin, Henry (October 1987). Katz, Randy, ed. "Superoptimizer: A Look at the Smallest Program" (PDF). Proceedings of the Second International Conference on Architectural support for Programming Languages and Operating Systems (ASPLOS II) ACM SIGOPS Operating Systems Review. 21 (4): 122–126. doi:10.1145/36206.36194. ISBN 0-8186-0805-6. Archived (PDF) from the original on 2017-07-04. Retrieved 2012-04-25. Lay summary (1995-06-14).
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.
- Granlund, Torbjörn; Kenner, Richard (July 1992). "Eliminating branches using a superoptimizer and the GNU C compiler". ACM SIGPLAN Notices. 27 (7): 341–352. doi:10.1145/143095.143146. Retrieved 2016-09-03.
- "Index of /gnu/superopt". GNU Operating System. Free Software Foundation, Inc. 1995-06-14. Retrieved 2016-09-03.
- Joshi, Rajeev; Nelson, Greg; Randall, Keith (2001-07-30). "Denali: a goal-directed superoptimizer". Compaq Systems Research Center. HP Labs. Hewlett-Packard Co. Retrieved 2016-09-02.
- 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. Logic Programming. Springer-Verlag, Berlin / Heidelberg. pp. 270–284. ISBN 978-3-540-36636-2.
- "TOAST – KRRwiki". Department of Computer Science, Mathematical Foundations Group. Knowledge Representation and Reasoning (KRR) group. University of Bath. 2007-08-07. Archived from the original on 2012-11-28. Retrieved 2016-09-03.
- Bansal, Sorav; Aiken, Alex (2006-10-21). "Automatic Generation of Peephole Superoptimizers" (PDF). Stanford University. Computer Systems Lab, Stanford University. Retrieved 2016-09-02.
- Bansal, Sorav; Aiken, Alex (2006-10-25). "Binary Translation Using Peephole Superoptimizers" (PDF). Department of Computer Science. Indian Institute of Technology, Delhi. Retrieved 2016-10-17.
- Serpell, Daniel (2003). "SuperOptimizer for Microchip's PIC microcontrollers". Google Sites. Google. Retrieved 2016-09-06.
- Serpell, Daniel (2003-06-21). "PIC Microcontroller SuperOptimizer". Freecode. Slashdot Media. Retrieved 2016-09-06.
- Hume, Tom (2012-08-21). "Clojure program to exhaustively search for optimal Java programs". GitHub. GitHub, Inc. Retrieved 2016-09-06.