Superoptimization
Encyclopedia
Superoptimization is the task of finding the optimal code
sequence
for a single, loop-free sequence of instructions. While garden-variety compiler optimization
s really just improve code (real-world compilers generally cannot produce genuinely optimal code), a superoptimizer's goal is to find the optimal sequence at the outset.
The term superoptimization was first coined by Alexia Massalin
in her 1987 paper and then later developed for integration within the GNU Compiler Collection
(GSO 1992). Recent work has further developed and extended this idea: (2001, 2006, 2006).
Typically, superoptimization is performed via exhaustive search
in the space of valid instruction sequences. While this is an expensive technique, and therefore impractical for general-purpose compilers, it has been shown to be useful in optimizing performance-critical inner loops. Recent work has used superoptimization to automatically generate general-purpose peephole optimizers
.
Code
A code is a rule for converting a piece of information into another form or representation , not necessarily of the same type....
sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
for a single, loop-free sequence of instructions. While garden-variety compiler optimization
Compiler optimization
Compiler optimization is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the amount of memory occupied...
s really just improve code (real-world compilers generally cannot produce genuinely optimal code), a superoptimizer's goal is to find the optimal sequence at the outset.
The term superoptimization was first coined by Alexia Massalin
Alexia Massalin
Alexia Massalin is an American computer scientist and programmer. Massalin pioneered the concept of superoptimization, and designed the Synthesis kernel...
in her 1987 paper and then later developed for integration within the GNU Compiler Collection
GNU Compiler Collection
The GNU Compiler Collection is a compiler system produced by the GNU Project supporting various programming languages. GCC is a key component of the GNU toolchain...
(GSO 1992). Recent work has further developed and extended this idea: (2001, 2006, 2006).
Typically, superoptimization is performed via exhaustive search
Brute-force search
In computer science, brute-force search or exhaustive search, also known as generate and test, is a trivial but very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's...
in the space of valid instruction sequences. While this is an expensive technique, and therefore impractical for general-purpose compilers, it has been shown to be useful in optimizing performance-critical inner loops. Recent work has used superoptimization to automatically generate general-purpose peephole optimizers
Peephole optimization
In compiler theory, peephole optimization is a kind of optimization performed over a very small set of instructions in a segment of generated code. The set is called a "peephole" or a "window"...
.
Publicly available superoptimizers
- GNU Superoptimizer (GSO) (1992)
- TOAST Superoptimiser (2006)
- The Aha! (A Hacker's Assistant) Superoptimizer (and paper about it) (2006)
- Stanford's Superoptimizer (2006)
- PIC Microcontroller SuperOptimizer (2007)