Superoptimization is the task of finding the optimal code sequence for a single, loop-free sequence of instructions. While garden-variety compiler optimizations really just improve code (real-world compilers generally cannot produce genuinely optimal code), a superoptimizer's goal is to find the optimal sequence.
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.
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)
- Clojure superoptimizer for the JVM (2012)
- A feasibility study by Embecosm (2014)
- STOKE - A stochastic optimizer for x86_64 assembly.