Superoptimization

From Wikipedia, the free encyclopedia
  (Redirected from Superoptimizer)
Jump to navigation Jump to search

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.[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.

See also

References

  1. ^ 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. (Also: ACM Sigplan Notices, Vol. 22 #10, IEEE Computer Society Press #87CH2440-6, October 1987)
  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 2016-09-03.
  3. ^ a b "Index of /gnu/superopt". GNU Operating System. Free Software Foundation, Inc. 1995-06-14. Retrieved 2016-09-03.
  4. ^ 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.
  5. ^ a b 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.
  6. ^ a b "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.
  7. ^ Bansal, Sorav; Aiken, Alex (2006-10-21). "Automatic Generation of Peephole Superoptimizers" (PDF). Stanford University. Computer Systems Lab, Stanford University. Retrieved 2016-09-02.
  8. ^ 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.
  9. ^ Serpell, Daniel (2003). "SuperOptimizer for Microchip's PIC microcontrollers". Google Sites. Google. Retrieved 2016-09-06.
  10. ^ Serpell, Daniel (2003-06-21). "PIC Microcontroller SuperOptimizer". Freecode. Slashdot Media. Retrieved 2016-09-06.
  11. ^ Hume, Tom (2012-08-21). "Clojure program to exhaustively search for optimal Java programs". GitHub. GitHub, Inc. Retrieved 2016-09-06.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Superoptimization&oldid=851506335"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Superoptimizer
This page is based on the copyrighted Wikipedia article "Superoptimization"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA