Superoptimization

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

Superoptimizer studies, documents, and several working examples, are available for free download.

References[edit]

  1. ^ 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. 
  2. ^ 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. 
  3. ^ a b "Index of /gnu/superopt". GNU Operating System. Free Software Foundation, Inc. 14 June 1995. Retrieved 3 September 2016. 
  4. ^ 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. 
  5. ^ 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. Logic Programming. Springer Berlin Heidelberg. pp. 270–284. ISBN 978-3-540-36636-2. 
  6. ^ 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. 
  7. ^ 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. 
  8. ^ Serpell, Daniel. "SuperOptimizer for Microchip's PIC microcontrollers". Google Sites. Google. Retrieved 6 September 2016. 
  9. ^ Serpell, Daniel (21 Jun 2003). "PIC Microcontroller SuperOptimizer". Freecode. Slashdot Media. Retrieved 6 September 2016. 
  10. ^ Hume, Tom (21 August 2012). "Clojure program to exhaustively search for optimal Java programs". GitHub. GitHub, Inc. Retrieved 6 September 2016.