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.
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.
Traditionally, 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, 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 setdeclarative programming was used for superoptimising in the Total Optimisation using Answer Set Technology (TOAST) project at the University of Bath.[7][8]
Superoptimization can be used to automatically generate general-purpose peephole optimizers.[9]
^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. 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.
^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. ISBN978-3-540-36636-2.
^"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.