Superoptimization

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

Techniques

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. It is also possible to use a SMT solver to approach the problem.

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]

Superoptimization can be used to automatically generate general-purpose peephole optimizers.[7]

Publicly available superoptimizers

Several superoptimizers are available for free download.

See also

References
  1. Massalin, Henry (1987). "Superoptimizer: A look at the smallest program" (PDF). ACM SIGARCH Computer Architecture News. 15 (5): 122–126. doi:10.1145/36177.36194. Archived (PDF) from the original on 2017-07-04. Retrieved 2012-04-25. 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.
  2. Granlund, Torbjörn; Kenner, Richard (July 1992). "Eliminating branches using a superoptimizer and the GNU C compiler". ACM SIGPLAN Notices. 27 (7): 341–352. CiteSeerX 10.1.1.58.3509. doi:10.1145/143095.143146. ISBN 978-0-89791475-8. S2CID 8825539.
  3. "Index of /gnu/superopt". GNU Operating System. Free Software Foundation, Inc. 1995-06-14. Archived from the original on 2016-09-11. 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. Archived from the original on 2016-05-27. Retrieved 2016-09-02.
  5. 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 (eds.). Logic Programming. Springer-Verlag, Berlin / Heidelberg. pp. 270–284. ISBN 978-3-540-36636-2.
  6. "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. Archived (PDF) from the original on 2016-06-11. 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. Archived (PDF) from the original on 2016-09-08. Retrieved 2016-10-17.
  9. Serpell, Daniel (2003). "SuperOptimizer for Microchip's PIC microcontrollers". Google Sites. Archived from the original on 2016-10-11. Retrieved 2016-09-06.
  10. Serpell, Daniel (2003-06-21). "PIC Microcontroller SuperOptimizer". Freecode. Slashdot Media. Archived from the original on 2016-09-17. Retrieved 2016-09-06.
  11. Hume, Tom (2012-08-21). "Clojure program to exhaustively search for optimal Java programs". GitHub. Archived from the original on 2018-06-10. Retrieved 2016-09-06.
  12. Cabrera Arteaga, Javier; Donde, Shrinish; Gu, Jian; Floros, Orestis; Satabin, Lucas; Baudry, Benoit; Monperrus, Martin (2020). "Superoptimization of WebAssembly bytecode". Conference Companion of the 4th International Conference on Art, Science, and Engineering of Programming. Porto Portugal: ACM: 36–40. arXiv:2002.10213. doi:10.1145/3397537.3397567. ISBN 978-1-4503-7507-8. S2CID 211259480.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.