Superoptimization: Difference between revisions

From HandWiki
(simplify)
 
(change)
 
Line 1: Line 1:
{{Short description|Compiler optimization technique}}
{{Use list-defined references|date=August 2022}}
'''Superoptimization''' is the process where a [[Compiler|compiler]] automatically finds the optimal sequence for a loop-free sequence of instructions. Real-world compilers generally cannot produce genuinely ''optimal'' code, and while most standard compiler optimizations only improve code partly, a superoptimizer's goal is to find the optimal sequence, the [[Canonical form|canonical form]]. Superoptimizers can be used to improve conventional optimizers by highlighting missed opportunities so a human can write additional rules.
'''Superoptimization''' is the process where a [[Compiler|compiler]] automatically finds the optimal sequence for a loop-free sequence of instructions. Real-world compilers generally cannot produce genuinely ''optimal'' code, and while most standard compiler optimizations only improve code partly, a superoptimizer's goal is to find the optimal sequence, the [[Canonical form|canonical form]]. Superoptimizers can be used to improve conventional optimizers by highlighting missed opportunities so a human can write additional rules.


Line 11: Line 9:


==Techniques==
==Techniques==
Traditionally, superoptimizing is performed via exhaustive [[Brute-force search|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 [[Satisfiability modulo theories|SMT solver]] to approach the problem, vastly improving the search efficiency (although inputs more complex than a [[Basic block|basic block]] remains out of reach).<ref name="jangda">{{cite conference |last1=Jangda |first1=Abhinav |last2=Yorsh |first2=Greta |title=Unbounded superoptimization |conference=Onward!’17, October 25–27, 2017, Vancouver, Canada |date=25 October 2017 |pages=78–88 |doi=10.1145/3133850.3133856}}</ref>
Traditionally, superoptimizing is performed via exhaustive [[Brute-force search|brute-force search]] in the space of valid instruction sequences. This is a costly method, and largely 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 [[Satisfiability modulo theories|SMT solver]] to approach the problem, vastly improving the search efficiency (although inputs more complex than a [[Basic block|basic block]] remains out of reach).<ref name="jangda">{{cite conference |last1=Jangda |first1=Abhinav |last2=Yorsh |first2=Greta |title=Unbounded superoptimization |conference=Onward!’17, October 25–27, 2017, Vancouver, Canada |date=25 October 2017 |pages=78–88 |doi=10.1145/3133850.3133856}}</ref>


In 2001, goal-directed superoptimizing was demonstrated in the Denali project by Compaq research.<ref name="Joshi_2001"/> In 2006, [[Answer set programming|answer set]] [[Declarative programming|declarative programming]] was used for superoptimising in the Total Optimisation using Answer Set Technology (TOAST) project at the [[Organization:University of Bath|University of Bath]].<ref name="TOAST-book"/><ref name="TOAST-KRR"/>
In 2001, goal-directed superoptimizing was demonstrated in the Denali project by Compaq research.<ref name="Joshi_2001"/> In 2006, [[Answer set programming|answer set]] [[Declarative programming|declarative programming]] was applied to superoptimization in the ''Total Optimisation using Answer Set Technology'' (TOAST) project<ref name="TOAST-KRR"/> at the [[Organization:University of Bath|University of Bath]].<ref name="TOAST-book"/><ref name="crick-phd"/>


Superoptimization can be used to automatically generate general-purpose [[Peephole optimization|peephole optimizers]].<ref name="Bansal_2006"/>
Superoptimization can be used to automatically generate general-purpose [[Peephole optimization|peephole optimizers]].<ref name="Bansal_2006"/>
Line 43: Line 41:
{{Reflist|refs=
{{Reflist|refs=
<ref name="Massalin_1987_Superoptimizer">{{cite journal |doi=10.1145/36177.36194 |title=Superoptimizer: A look at the smallest program |date=1987 |author-last=Massalin |author-first=Henry |journal=ACM SIGARCH Computer Architecture News |volume=15 |issue=5 |pages=122–126 |url=https://web.stanford.edu/class/cs343/resources/superoptimizer.pdf |access-date=2023-05-01 |quote=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.}}</ref>
<ref name="Massalin_1987_Superoptimizer">{{cite journal |doi=10.1145/36177.36194 |title=Superoptimizer: A look at the smallest program |date=1987 |author-last=Massalin |author-first=Henry |journal=ACM SIGARCH Computer Architecture News |volume=15 |issue=5 |pages=122–126 |url=https://web.stanford.edu/class/cs343/resources/superoptimizer.pdf |access-date=2023-05-01 |quote=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.}}</ref>
<ref name="Denali">{{cite journal |last1=Joshi |first1=Rajeev |last2=Nelson |first2=Greg |last3=Randall |first3=Keith |title=Denali: A Goal-directed Superoptimizer |journal=ACM SIGPLAN Notices |date=2002 |volume=37 |issue=5 |pages=304–314 |doi=10.1145/543552.512566 |url=https://dl.acm.org/doi/10.1145/543552.512566}}</ref>
<ref name="Denali">{{cite journal |last1=Joshi |first1=Rajeev |last2=Nelson |first2=Greg |last3=Randall |first3=Keith |title=Denali: A Goal-directed Superoptimizer |journal=ACM SIGPLAN Notices |date=2002 |volume=37 |issue=5 |pages=304–314 |doi=10.1145/543552.512566 |url=https://dl.acm.org/doi/10.1145/543552.512566|url-access=subscription }}</ref>
<ref name="GCCsuperACM">{{cite journal |author-last1=Granlund |author-first1=Torbjörn |author-last2=Kenner |author-first2=Richard |title=Eliminating branches using a superoptimizer and the GNU C compiler |journal=ACM SIGPLAN Notices |date=July 1992 |volume=27 |issue=7 |pages=341–352 |isbn=978-0-89791475-8 |doi=10.1145/143095.143146 |citeseerx=10.1.1.58.3509 |s2cid=8825539}}</ref>
<ref name="GCCsuperACM">{{cite book |author-last1=Granlund |author-first1=Torbjörn |author-last2=Kenner |author-first2=Richard |chapter=Eliminating branches using a superoptimizer and the GNU C compiler |title=Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation - PLDI '92 |isbn=978-0-89791475-8 |doi=10.1145/143095.14314 |citeseerx=10.1.1.58.3509 |s2cid=8825539}}</ref>
<ref name="GCCsuperopt">{{cite web |url=https://ftp.gnu.org/gnu/superopt/ |title=Index of /gnu/superopt |date=1995-06-14 |website=GNU Operating System |publisher=Free Software Foundation, Inc. |access-date=2023-05-01}}</ref>
<ref name="GCCsuperopt">{{cite web |url=https://ftp.gnu.org/gnu/superopt/ |title=Index of /gnu/superopt |date=1995-06-14 |website=GNU Operating System |publisher=Free Software Foundation, Inc. |access-date=2023-05-01}}</ref>
<ref name="Joshi_2001">{{cite web |url=https://hpl.hp.com/techreports/Compaq-DEC/SRC-RR-171.html |title=Denali: a goal-directed superoptimizer |author-last1=Joshi |author-first1=Rajeev |author-last2=Nelson |author-first2=Greg |author-last3=Randall |author-first3=Keith |date=2001-07-30 |department=Compaq Systems Research Center |website=HP Labs |publisher=Hewlett-Packard Co. |access-date=2023-05-01}}</ref>
<ref name="Joshi_2001">{{cite web |url=https://hpl.hp.com/techreports/Compaq-DEC/SRC-RR-171.html |title=Denali: a goal-directed superoptimizer |author-last1=Joshi |author-first1=Rajeev |author-last2=Nelson |author-first2=Greg |author-last3=Randall |author-first3=Keith |date=2001-07-30 |department=Compaq Systems Research Center |website=HP Labs |publisher=Hewlett-Packard Co. |access-date=2023-05-01}}</ref>
<ref name="TOAST-book">{{cite book |author-last1=Brain |author-first1=Martin |author-last2=Crick |author-first2=Tom |author-last3=De Vos |author-first3=Marina |author-last4=Fitch |author-first4=John |editor-last1=Etalle |editor-first1=Sandro |editor-last2=Truszczyński |editor-first2=Mirosław |title=Logic Programming |publisher=[[Physics:Springer-Verlag|Springer-Verlag]], Berlin / Heidelberg |date=2006-08-17 |pages=270–284 |chapter=TOAST: Applying Answer Set Programming to Superoptimisation |isbn=978-3-540-36636-2}}</ref>
<ref name="TOAST-book">{{cite book |author-last1=Brain |author-first1=Martin |author-last2=Crick |author-first2=Tom |author-last3=De Vos |author-first3=Marina |author-last4=Fitch |author-first4=John |editor-last1=Etalle |editor-first1=Sandro |editor-last2=Truszczyński |editor-first2=Mirosław |title=Logic Programming |publisher=[[Physics:Springer-Verlag|Springer-Verlag]] |date=2006-08-17 |pages=270–284 |chapter=TOAST: Applying Answer Set Programming to Superoptimisation |doi=10.1007/11799573_21|isbn=978-3-540-36636-2}}</ref>
<ref name="crick-phd">{{cite thesis |last=Crick |first=Tom |date=2009 |title=Superoptimisation: Provably Optimal Code Generation using Answer Set Programming |url=https://researchportal.bath.ac.uk/en/studentTheses/superoptimisation-provably-optimal-code-generation-using-answer-s |degree=PhD |publisher=University of Bath | access-date=2024-11-15}}</ref>
<ref name="TOAST-KRR">{{cite web |title=TOAST – KRRwiki |author=<!--Wiki writer(s); no by-lines.--> |date=2007-08-07 |department=Department of Computer Science, Mathematical Foundations Group |website=Knowledge Representation and Reasoning (KRR) group |publisher=[[Organization:University of Bath|University of Bath]] |url=http://krr.cs.bath.ac.uk/index.php/TOAST |access-date=2016-09-03 |url-status=dead|archive-url=https://web.archive.org/web/20121128143632/http://krr.cs.bath.ac.uk/index.php/TOAST |archive-date=2012-11-28}}</ref>
<ref name="TOAST-KRR">{{cite web |title=TOAST – KRRwiki |author=<!--Wiki writer(s); no by-lines.--> |date=2007-08-07 |department=Department of Computer Science, Mathematical Foundations Group |website=Knowledge Representation and Reasoning (KRR) group |publisher=[[Organization:University of Bath|University of Bath]] |url=http://krr.cs.bath.ac.uk/index.php/TOAST |access-date=2016-09-03 |url-status=dead|archive-url=https://web.archive.org/web/20121128143632/http://krr.cs.bath.ac.uk/index.php/TOAST |archive-date=2012-11-28}}</ref>
<ref name="Bansal_2006">{{cite web |url=https://sorav.compiler.ai/pubs/asplos06.pdf |title=Automatic Generation of Peephole Superoptimizers |author-last1=Bansal |author-first1=Sorav |author-last2=Aiken |author-first2=Alex |date=2006 |access-date=2023-05-01}}</ref>
<ref name="Bansal_2006">{{cite web |url=https://sorav.compiler.ai/pubs/asplos06.pdf |title=Automatic Generation of Peephole Superoptimizers |author-last1=Bansal |author-first1=Sorav |author-last2=Aiken |author-first2=Alex |date=2006 |access-date=2023-05-01}}</ref>
Line 57: Line 56:
<ref name="STOKE">{{cite web |author=StanfordPL |url=https://github.com/StanfordPL/stoke |title=STOKE|website=[[GitHub]] }}</ref>
<ref name="STOKE">{{cite web |author=StanfordPL |url=https://github.com/StanfordPL/stoke |title=STOKE|website=[[GitHub]] }}</ref>
<ref name="Embecosm_2014">{{cite web |url=http://superoptimization.org |title=A feasibility study by Embecosm}}</ref>
<ref name="Embecosm_2014">{{cite web |url=http://superoptimization.org |title=A feasibility study by Embecosm}}</ref>
<ref name="souper">{{cite arXiv |last1=Sasnauskas |first1=Raimondas |last2=Chen |first2=Yang |last3=Collingbourne |first3=Peter |last4=Ketema |first4=Jeroen |last5=Lup |first5=Gratian |last6=Taneja |first6=Jubi |last7=Regehr |first7=John |title=Souper: A Synthesizing Superoptimizer |date=2017 |eprint=1711.04422}} [https://github.com/google/souper GitHub source code]</ref>
<ref name="souper">{{cite arXiv |last1=Sasnauskas |first1=Raimondas |last2=Chen |first2=Yang |last3=Collingbourne |first3=Peter |last4=Ketema |first4=Jeroen |last5=Lup |first5=Gratian |last6=Taneja |first6=Jubi |last7=Regehr |first7=John |title=Souper: A Synthesizing Superoptimizer |date=2017 |class=cs.PL |eprint=1711.04422}} [https://github.com/google/souper GitHub source code]</ref>
<ref name="slumps">{{cite conference |last1=Cabrera Arteaga |first1=Javier |last2=Donde |first2=Shrinish |last3=Gu |first3=Jian |last4=Floros |first4=Orestis |last5=Satabin |first5=Lucas |last6=Baudry |first6=Benoit |last7=Monperrus |first7=Martin |title=Superoptimization of WebAssembly bytecode |date=23 March 2020 |pages=36–40 |doi=10.1145/3397537.3397567 |arxiv=2002.10212 |conference=MoreVMs: Workshop on Modern Language Runtimes, Ecosystems, and VMs}} [https://github.com/KTH/slumps/tree/master/superoptimizer GitHub source code]</ref>
<ref name="slumps">{{cite conference |last1=Cabrera Arteaga |first1=Javier |last2=Donde |first2=Shrinish |last3=Gu |first3=Jian |last4=Floros |first4=Orestis |last5=Satabin |first5=Lucas |last6=Baudry |first6=Benoit |last7=Monperrus |first7=Martin |title=Superoptimization of WebAssembly bytecode |date=23 March 2020 |pages=36–40 |doi=10.1145/3397537.3397567 |arxiv=2002.10213 |conference=MoreVMs: Workshop on Modern Language Runtimes, Ecosystems, and VMs}} [https://github.com/KTH/slumps/tree/master/superoptimizer GitHub source code]</ref>
}}
}}


Latest revision as of 21:30, 29 August 2025

Superoptimization is the process where a compiler automatically finds the optimal sequence for a loop-free sequence of instructions. Real-world compilers generally cannot produce genuinely optimal code, and 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] The label "program optimization" has been given to a field that does not aspire to optimize but only to improve. This misnomer forced Massalin to call her system a superoptimizer, which is actually an optimizer to find an optimal program.[2]

In 1992, the GNU Superoptimizer (GSO) was developed to integrate into the GNU Compiler Collection (GCC).[3][4] Later work further developed and extended these ideas.

Techniques

Traditionally, superoptimizing is performed via exhaustive brute-force search in the space of valid instruction sequences. This is a costly method, and largely 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, vastly improving the search efficiency (although inputs more complex than a basic block remains out of reach).[5]

In 2001, goal-directed superoptimizing was demonstrated in the Denali project by Compaq research.[6] In 2006, answer set declarative programming was applied to superoptimization in the Total Optimisation using Answer Set Technology (TOAST) project[7] at the University of Bath.[8][9]

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

Publicly available superoptimizers

Several superoptimizers are available for free download.

  • For the x86 family of instruction sets:
  • For ARM:
    • Unbounded Superoptimizer,[5] transforming LLVM IR into ARMv7-A assembly
  • For embedded systems:
    • PIC microcontroller SuperOptimizer (2003)[14][15]
    • A feasibility study by Embecosm (2014) for AVR, based on GSO[16][17]
  • For the JVM:
  • For LLVM IR:
    • souper[19] superoptimizer for programs in the LLVM intermediate language.
  • For WebAssembly
    • slumps[20] provides superoptimization for WASM programs based on souper.

See also

References

  1. ↑ "Superoptimizer: A look at the smallest program". ACM SIGARCH Computer Architecture News 15 (5): 122–126. 1987. doi:10.1145/36177.36194. https://web.stanford.edu/class/cs343/resources/superoptimizer.pdf. Retrieved 2023-05-01. "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. ↑ Joshi, Rajeev; Nelson, Greg; Randall, Keith (2002). "Denali: A Goal-directed Superoptimizer". ACM SIGPLAN Notices 37 (5): 304–314. doi:10.1145/543552.512566. https://dl.acm.org/doi/10.1145/543552.512566. 
  3. ↑ 3.0 3.1 "Eliminating branches using a superoptimizer and the GNU C compiler". Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation - PLDI '92. doi:10.1145/143095.14314. ISBN 978-0-89791475-8. 
  4. ↑ 4.0 4.1 "Index of /gnu/superopt". Free Software Foundation, Inc.. 1995-06-14. https://ftp.gnu.org/gnu/superopt/. 
  5. ↑ 5.0 5.1 Jangda, Abhinav; Yorsh, Greta (25 October 2017). "Unbounded superoptimization". Onward!’17, October 25–27, 2017, Vancouver, Canada. pp. 78–88. doi:10.1145/3133850.3133856. 
  6. ↑ "Denali: a goal-directed superoptimizer". Hewlett-Packard Co.. 2001-07-30. https://hpl.hp.com/techreports/Compaq-DEC/SRC-RR-171.html. 
  7. ↑ "TOAST – KRRwiki". University of Bath. 2007-08-07. http://krr.cs.bath.ac.uk/index.php/TOAST. 
  8. ↑ "TOAST: Applying Answer Set Programming to Superoptimisation". Logic Programming. Springer-Verlag. 2006-08-17. pp. 270–284. doi:10.1007/11799573_21. ISBN 978-3-540-36636-2. 
  9. ↑ Crick, Tom (2009). Superoptimisation: Provably Optimal Code Generation using Answer Set Programming (PhD thesis). University of Bath. Retrieved 2024-11-15.
  10. ↑ "Automatic Generation of Peephole Superoptimizers". 2006. https://sorav.compiler.ai/pubs/asplos06.pdf. 
  11. ↑ "GNU Superoptimizer". https://www.gnu.org/software/superopt/. 
  12. ↑ StanfordPL. "STOKE". https://github.com/StanfordPL/stoke. 
  13. ↑ "Binary Translation Using Peephole Superoptimizers". 2008. https://sorav.compiler.ai/pubs/osdi08.pdf. 
  14. ↑ "SuperOptimizer for Microchip's PIC microcontrollers". 2003. https://sites.google.com/site/danielserpell/picmicrocontrollersuperoptimizer. 
  15. ↑ "PIC Microcontroller SuperOptimizer". Slashdot Media. 2003-06-21. http://freecode.com/projects/picsuperoprimizer/. 
  16. ↑ "A feasibility study by Embecosm". http://superoptimization.org. 
  17. ↑ Superoptimization – Embecosm Source Code
  18. ↑ "Clojure program to exhaustively search for optimal Java programs". 2012-08-21. https://github.com/twhume/superoptimiser. 
  19. ↑ Sasnauskas, Raimondas; Chen, Yang; Collingbourne, Peter; Ketema, Jeroen; Lup, Gratian; Taneja, Jubi; Regehr, John (2017). "Souper: A Synthesizing Superoptimizer". arXiv:1711.04422 [cs.PL]. GitHub source code
  20. ↑ Cabrera Arteaga, Javier; Donde, Shrinish; Gu, Jian; Floros, Orestis; Satabin, Lucas; Baudry, Benoit; Monperrus, Martin (23 March 2020). "Superoptimization of WebAssembly bytecode". MoreVMs: Workshop on Modern Language Runtimes, Ecosystems, and VMs. pp. 36–40. doi:10.1145/3397537.3397567.  GitHub source code



Retrieved from "https://handwiki.org/wiki/index.php?title=Superoptimization&oldid=3742735"