Superoptimizer: a look at the smallest program

By H. Massalin. 1987

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. The search space is defined by the processor's instruction set, which may include the whole set, but it is typically restricted to a subset. By constraining the instructions and observing the effect on the output program, one can gain insight into the design of instruction sets. In addition, superoptimized programs may be used by peephole optimizers to improve the quality of generated code, or by assembly language programmers to improve manually written code.

Subfields: Code Generation & Program Synthesis, Program Analysis & Verification

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Code Generation & Program Synthesis

In Program Analysis & Verification

Citations in the corpus

SPoC: Search-based Pseudocode to Code (2019, background): “For other problems, brute force enumeration of programs (with some optimization) works surprisingly well [26, 3], but when the search space is too large for enumeration, randomized search guided by a cost function can be effective [30].”
Dimensions in program synthesis (2010, unknown): “Initial work [2, 52, 21] on automated synthesis of such algorithms used brute-force search, while recent work [23, 33] uses logical reasoning based techniques (powered by underlying SAT/SMT solvers) and scales much better.”
egg: Fast and extensible equality saturation (2020, methodology): “The Denali [Joshi et al. 2002] superoptimizer first demonstrated how to use e-graphs for optimized code generation as an alternative to hand-optimized machine code and prior exhaustive approaches [Massalin 1987], both of which were less scalable.”
Oracle-guided component-based program synthesis (2010, methodology): “…Program Synthesis Susmit Jha Sumit Gulwani Sanjit A. Seshia Ashish Tiwari UC Berkeley Microsoft Research UC Berkeley SRI International jha@eecs.berkeley.edu sumitg@microsoft.com sseshia@eecs.berkeley.edu tiwari@csl.sri.com ABSTRACT We present a novel approach to automatic synthesis of…”
Compiler validation via equivalence modulo inputs (2014, unknown): “Extending work on super-optimization [3, 11, 15], in particular Denali [11], Tate et al.”
Foofah: Transforming Data By Example (2017, methodology): “Search-based techniques are another common approach used by previous program synthesis projects [25,30,32,35].”
The New C Standard (Excerpted material) An Economic and Cultural Commentary (2008, unknown): “Massalin[279] built a superoptimizer to do just that; it worked off-line and was not intended to be used to generate instruction sequences during translation.”
AlphaEvolve: A coding agent for scientific and algorithmic discovery (2025, unknown): “The idea of code superoptimization goes back to the 1980s [69]; pre-LLM approaches to the problem included systematic enumeration [69], genetic search [20], Monte Carlo sampling [86], and deep reinforcement learning [68].”
Post-compiler software optimization for reducing energy (2014, background): “Massalin’s classic work introducing superoptimization [37] exhaustively tested all possible combinations of instructions in Motorola’s 68020 assembly language to ﬁnd the fastest possible implementation of simple programs up to 14 instructions in length.”
Contrastive Code Representation Learning (2020, background): “, 2002; Bansal and Aiken, 2006) and approximate verification is costly and runs untrusted code (Massalin, 1987).”
Program Synthesis (2017, background): “The control structure of the program may be restricted to a user-provided looping template [135], a partial program with holes [132], straight-line programs [8, 47, 63, 87, 109], or a guarded statement set with control flow at the very top [43].”
Automatic performance tuning of sparse matrix kernels (2003, background): “Superoptimizers Massalin coined the term superoptimizer for his exhaustive search-based instruction generator [214].”
TASO: optimizing deep learning computation with automatic generation of graph substitutions (2019, methodology): “Superoptimization is a compiler optimization technique that was originally designed to find the optimal code for a sequence of instructions [25].”