Superoptimization is the process where a
compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
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 optimization
In computing, an optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program. Common requirements are to minimize a program's execution time, memory footprint, storage size, and power con ...
s only improve code partly, a superoptimizer's goal is to find the optimal sequence, the
canonical form
In mathematics and computer science, a canonical, normal, or standard form of a mathematical object is a standard way of presenting that object as a mathematical expression. Often, it is one which provides the simplest representation of an obje ...
. 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
Alexia Massalin (formerly Henry Massalin) is an American computer scientist and programmer. She pioneered the concept of superoptimization, and designed the ''Synthesis kernel'', a small kernel with a Unix compatibility layer that makes heavy ...
in the 1987 paper ''Superoptimizer: A Look at the Smallest Program''.
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.
In 1992, the GNU Superoptimizer (GSO) was developed to integrate into the
GNU Compiler Collection
The GNU Compiler Collection (GCC) is an optimizing compiler produced by the GNU Project supporting various programming languages, hardware architectures and operating systems. The Free Software Foundation (FSF) distributes GCC as free software ...
(GCC).
Later work further developed and extended these ideas.
Techniques
Typically, superoptimizing is performed via exhaustive
brute-force search
In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the soluti ...
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
In computer science and mathematical logic, satisfiability modulo theories (SMT) is the problem of determining whether a mathematical formula is satisfiable. It generalizes the Boolean satisfiability problem (SAT) to more complex formulas involvi ...
to approach the problem.
In 2001, goal-directed superoptimizing was demonstrated in the Denali project by Compaq research.
In 2006,
answer set declarative programming
In computer science, declarative programming is a programming paradigm—a style of building the structure and elements of computer programs—that expresses the logic of a computation without describing its control flow.
Many languages that ap ...
was used for superoptimising in the Total Optimisation using Answer Set Technology (TOAST) project at the
University of Bath
(Virgil, Georgics II)
, mottoeng = Learn the culture proper to each after its kind
, established = 1886 (Merchant Venturers Technical College) 1960 (Bristol College of Science and Technology) 1966 (Bath University of Technology) 1971 (univ ...
.
Superoptimization can be used to automatically generate general-purpose
peephole optimizers.
Publicly available superoptimizers
Several superoptimizers are available for free download.
* For the x86 family of instruction sets:
** GNU Superoptimizer
(GSO) (1992)
** STOKE,
a stochastic optimizer
for
x86-64
x86-64 (also known as x64, x86_64, AMD64, and Intel 64) is a 64-bit version of the x86 instruction set, first released in 1999. It introduced two new modes of operation, 64-bit mode and compatibility mode, along with a new 4-level paging mod ...
x86 assembly language
x86 assembly language is the name for the family of assembly languages which provide some level of backward compatibility with CPUs back to the Intel 8008 microprocessor, which was launched in April 1972. It is used to produce object code for t ...
* For embedded systems:
**
PIC microcontroller
PIC (usually pronounced as ''"pick"'') is a family of microcontrollers made by Microchip Technology, derived from the PIC1650"PICmicro Family Tree", PIC16F Seminar Presentation originally developed by General Instrument's Microelectronics ...
SuperOptimizer (2003)
** A feasibility study by Embecosm (2014)
* For the JVM:
**
Clojure
Clojure (, like ''closure'') is a dynamic and functional dialect of the Lisp programming language on the Java platform. Like other Lisp dialects, Clojure treats code as data and has a Lisp macro system. The current development process is comm ...
superoptimizer for the
Java virtual machine
A Java virtual machine (JVM) is a virtual machine that enables a computer to run Java programs as well as programs written in other languages that are also compiled to Java bytecode. The JVM is detailed by a specification that formally describes ...
(2012)
* For LLVM IR:
** souper
superoptimizer for programs in the
LLVM
LLVM is a set of compiler and toolchain technologies that can be used to develop a front end for any programming language and a back end for any instruction set architecture. LLVM is designed around a language-independent intermediate represen ...
intermediate language.
* For WebAssembly
** slumps
provides superoptimization for WASM programs based on souper.
See also
*
Peephole optimization
Peephole optimization is an optimization technique performed on a small set of compiler-generated instructions; the small set is known as the peephole or window.
Peephole optimization involves changing the small set of instructions to an equiva ...
*
Dead code elimination
In compiler theory, dead-code elimination (also known as DCE, dead-code removal, dead-code stripping, or dead-code strip) is a compiler optimization to remove code which does not affect the program results. Removing such code has several benefits: ...
*
Metacompilation
Metacompilation is a computation which involves metasystem transitions (MST) from a computing machine ''M'' to a metamachine ''M' '' which controls, analyzes and imitates the work of ''M''. Semantics-based program transformation, such as partial e ...
References
{{Compiler optimizations
Compiler optimizations