Superoptimization
Superoptimization is the process of 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. While most standard compiler optimizations only improve code partly: real-world compilers generally cannot produce genuinely optimal code. A superoptimizer's goal is to find the optimal sequence.
The term superoptimization was first coined by Alexia Massalin in her 1987 paper, Superoptimizer: a look at the smallest program.[1] In 1992, the GNU Superoptimizer (GSO) was developed to integrate into the GNU Compiler Collection (GCC).[2][3] Later work further developed and extended these ideas. In 2001, goal-directed superoptimizing was demonstrated in the Denali project by Compaq research.[4] 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,[5][6] and superoptimizing was used to automatically generate general-purpose peephole optimizers.[7]
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)[2][3]
- Total Optimisation using Answer Set Technology (TOAST) project (2006)[5][6]
- The Aha! (A Hacker's Assistant) Superoptimizer (and paper about it) (2006)
- Stanford Superoptimizer (2006)[8]
- PIC microcontroller SuperOptimizer (2003)[9][10]
- Clojure superoptimizer for the Java virtual machine (2012)[11]
- A feasibility study by Embecosm (2014)
- STOKE - A stochastic optimizer for x86-64 x86 assembly language.
References
- ^ Massalin, Henry (October 1987). "Superoptimizer: a look at the smallest program". ACM SIGOPS Operating Systems Review. 21 (4): 122–126. doi:10.1145/36204.36194. Retrieved 2 September 2016.
- ^ a b 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 3 September 2016.
- ^ a b "Index of /gnu/superopt". GNU Operating System. Free Software Foundation, Inc. 14 June 1995. Retrieved 3 September 2016.
- ^ Joshi, Rajeev; Nelson, Greg; Randall, Keith (30 July 2001). "Denali: a goal-directed superoptimizer". Compaq Systems Research Center. HP Labs. Hewlett-Packard Co. Retrieved 2 September 2016.
- ^ a b Brain, Martin; Crick, Tom; De Vos, Marina; Fitch, John (17–20 August 2006). "TOAST: Applying Answer Set Programming to Superoptimisation". In Etalle, Sandro; Truszczyński, Mirosław (eds.). Logic Programming. Springer Berlin Heidelberg. pp. 270–284. ISBN 978-3-540-36636-2.
{{cite book}}:|access-date=requires|url=(help) - ^ a b "TOAST – KRRwiki". Department of Computer Science, Mathematical Foundations Group. Knowledge Representation and Reasoning (KRR) group. University of Bath. 7 August 2007. Retrieved 3 September 2016.
- ^ Bansal, Sorav; Aiken, Alex (21–25 October 2006). "Automatic Generation of Peephole Superoptimizers" (PDF). Stanford University. Computer Systems Lab, Stanford University. Retrieved 2 September 2016.
- ^ Bansal, Sorav; Aiken, Alex (25 October 2006). "Binary Translation Using Peephole Superoptimizers" (PDF). Department of Computer Science. Indian Institute of Technology, Delhi. Retrieved 17 October 2016.
- ^ Serpell, Daniel (2003). "SuperOptimizer for Microchip's PIC microcontrollers". Google Sites. Google. Retrieved 6 September 2016.
- ^ Serpell, Daniel (21 Jun 2003). "PIC Microcontroller SuperOptimizer". Freecode. Slashdot Media. Retrieved 6 September 2016.
- ^ Hume, Tom (21 August 2012). "Clojure program to exhaustively search for optimal Java programs". GitHub. GitHub, Inc. Retrieved 6 September 2016.