Superoptimization

Unlike traditional compilers that apply heuristic-based peephole optimizations, superoptimization performs an exhaustive search over the space of all possible instruction sequences up to a certain length. Its goal is to find the provably optimal program—the shortest or fastest sequence—for a given target function on a specific processor. This search is guided by a formal specification of the target's input-output behavior, often using Satisfiability Modulo Theories (SMT) solvers like Z3 to verify candidate equivalence.

Correctness is guaranteed through formal verification. The target function is defined by a precise logical specification (e.g., input-output pairs, a reference implementation, or a mathematical formula). Each candidate instruction sequence generated by the search is automatically verified against this specification using automated theorem proving. This ensures the synthesized program is semantically equivalent to the target, making superoptimization a correct-by-construction technique.

Due to the combinatorial explosion of the search space, superoptimization is practically applied only to short, straight-line code sequences, often called superblocks or basic blocks. These are sequences of instructions with a single entry and exit point and no internal branches. Typical targets include:

• Critical inner loops in performance-sensitive code.
• Library functions for cryptography or math (e.g., memcpy, sin).
• Instruction sequences generated by a compiler's intermediate representation. The technique is often used as a post-pass optimizer after conventional compilation.

Superoptimization is deeply tied to the instruction set architecture (ISA) of the target processor. The search space is defined by the ISA's legal instructions, their latencies, and side effects. This allows it to discover optimal sequences that exploit obscure, synergistic, or undocumented hardware behaviors which heuristic optimizers miss. For example, it can find optimal sequences using complex Single Instruction, Multiple Data (SIMD) instructions or specific flag-setting patterns that minimize clock cycles.

A core algorithmic framework for superoptimization is Counterexample-Guided Inductive Synthesis (CEGIS). This iterative loop consists of two phases:

1. Synthesis (Inductive Generalization): A candidate program is generated, often using a stochastic search or enumerative search.
2. Verification (Deductive Check): The candidate is checked for equivalence against the formal specification using an SMT solver or theorem prover. If verification fails, the solver produces a counterexample—a concrete input where the candidate and specification differ. This counterexample is added to the set of constraints, refining the search in the next iteration until a provably correct candidate is found.

To navigate the vast search space, superoptimizers employ sophisticated search strategies:

• Enumerative Search: Systematically enumerates all programs of increasing length, often using pruning based on semantics rather than syntax to eliminate equivalent candidates early.
• Stochastic Search: Uses techniques like Markov Chain Monte Carlo (MCMC) or genetic programming to sample the space more efficiently, guided by a cost function (e.g., program length or estimated latency).
• Component-Based Synthesis: Builds programs by composing smaller, verified code fragments or using a grammar (as in Syntax-Guided Synthesis) to constrain the search to meaningful constructs.

The overarching field of automatically generating executable code from a high-level specification. Unlike superoptimization, which focuses on optimality for short segments, general program synthesis aims for functional correctness from specifications like:

• Input-output examples (Programming by Example)
• Natural language descriptions
• Formal logical constraints The goal is to automate coding tasks, reduce bugs, and allow non-programmers to create software.

A core algorithmic loop used to implement superoptimizers and other synthesizers. CEGIS iterates between:

1. Inductive Synthesis: A search procedure (e.g., stochastic search, SMT solving) generates a candidate program that works for a finite set of examples.
2. Verification: A formal verifier (e.g., an SMT solver) checks if the candidate satisfies the full specification.
3. Counterexample Refinement: If verification fails, the counterexample (an input where the program fails) is added to the set of examples, and the loop repeats. This creates a powerful feedback mechanism that converges on a provably correct program.

A traditional compiler optimization that is the manual precursor to superoptimization. A peephole optimizer examines short sequences of generated machine code (the "peephole") and replaces them with faster or smaller equivalent sequences using a hand-crafted set of rules.

• Key Difference: Superoptimization searches for the optimal sequence, while peephole optimization applies a predefined set of transformations.
• Superoptimization can discover novel, unexpected instruction sequences that are absent from a compiler's peephole optimization rule database.

A modern variant that uses probabilistic search techniques, like Markov Chain Monte Carlo (MCMC), to navigate the enormous space of possible instruction sequences for longer code segments (5-20 instructions).

• Instead of exhaustive search, it uses a cost function (e.g., code size, latency model) and proposes random mutations to a candidate program.
• It accepts mutations that lower the cost and, with a calculated probability, some that increase it to escape local minima.
• This trades provable optimality for the ability to optimize more realistic, longer code blocks found in real-world binaries.

The formal verification task at the heart of superoptimization. It answers the question: "Do two programs (the original and the candidate) produce identical outputs for all possible inputs?"

• For superoptimization, this is typically done by encoding both programs as logical formulas in a theory of bit-vectors and asking an SMT solver if the formulas are equivalent.
• This is a semantic check, ensuring behavioral equivalence, not just syntactic similarity.
• Advanced techniques like supervised translation validation use this principle to verify the correctness of entire compiler passes.