Optimization Passes

This page describes the current SSA builder and backend implementation. Start with the new text walkthrough for esper 1 syntax and the roadmap for the library-first migration boundary.

Note: Esper BE is a work in progress and all passes are subject to change.

Pass execution order

When driven by esper_optimize(unit, &config), passes execute in the following fixed order:

1. Stack-slot promotion (mem2reg)
2. Constant folding
3. Peephole
4. Strength reduction
5. Copy propagation
6. CSE
7. GVN
8. LICM
9. Devirtualization
10. Inlining
11. Tail call optimization
12. Escape analysis
13. SROA
14. Control-flow simplification
15. Dead code elimination
16. Symbol-table sweep
17. Hot-path estimation

Individual passes may be invoked independently via their public API functions. Passes that mutate the CFG invalidate hot-path side tables automatically.

Block parameters and the passes

A merge is a block parameter, and its incoming values ride the branches into the block. That is what makes most of these passes short on merge bookkeeping: a pass that rewrites a branch moves the values with it, and a pass that rewrites operands generically moves them without knowing they are edge values.

Three passes build a merge of their own: stack-slot promotion when it promotes a slot whose definitions join, LICM when it synthesizes a pre-header, and TCO when it rewrites a self tail call.

Stack-slot promotion (mem2reg)

Promotes stack slots that are only loaded from and stored to into ordinary SSA values, inserting the block parameters the control flow needs.

This is the pass that lets a frontend skip SSA construction entirely. Emitting one slot per local, a store for every assignment and a load for every read, is the easy shape for a frontend to produce: no dominance frontiers, no merge placement, no reasoning about which definition reaches which use. Without this pass those loads and stores survive to the backend and every local costs memory traffic.

Eligibility:

A slot qualifies when all of the following hold. Anything else leaves it as memory, because those are the cases where the slot is memory in a way an SSA value cannot stand in for.

• It comes from SALLOC. ALLOC is not promoted; run escape analysis first if a frontend emits the polymorphic form.
• Its SSA id appears only as the address operand of LOAD and STORE. An address that is derived, compared, passed to a call, stored somewhere, or used as the value operand of a store disqualifies the slot.
• Every access agrees on one type.
• No access carries a byte or bit offset.
• No access is volatile. Promotion is exactly the rewrite that turns a memory access into a register one, so one volatile access declines the whole slot.
• Every load is reached only along paths that have already stored to the slot. A load before any store reads whatever the slot happened to hold, and an SSA value has to come from somewhere.

Construction:

The pass indexes slot accesses once. A backward worklist grows each local’s live-in region from reads, stopping where a block has a reaching store. Only joins in that region need parameters. An earlier join or switch outside the region cannot prevent promotion.

Planning finishes before the instruction stream moves. Each accepted live join reserves exactly one parameter for that slot, appended after existing block parameters. The pass then creates those parameters, resolves single-predecessor chains iteratively, supplies incoming branch arguments, and rewrites indexed loads and stores. Value substitutions are applied across the function once. Scopes, named locals and inline-frame positions follow the remapped instructions.

A live join entered through fallthrough or a jump-table edge cannot currently receive arguments, so affected slots remain in memory. Slots with accesses in unreachable blocks are also retained conservatively. These checks apply to each slot’s live region, rather than rejecting an entire function for an unrelated join. The pass does not invent a value for an uninitialized read.

Ordering: Runs first, because its output enables scalar optimization. DCE removes the allocation and access instructions that promotion turns into NOPs; parameter reservations themselves are exact. See parser performance for scaling measurements and the sparse-worklist design.

Constant folding

Evaluates instructions with all-constant operands at compile time and replaces them with LDI (for i32) or LDC (for other types). Operates as a single forward pass over each function’s instruction stream, maintaining a flat table of known constant values indexed by SSA id.

Transformations:

• Integer arithmetic: ADD, SUB, MUL, DIV_S, DIV_U, REM_S, REM_U, NEG
• Bitwise: AND, OR, XOR, NOT, SHL, SHR_S, SHR_U, ROTL, ROTR, CLZ, CTZ, POPCNT
• Integer comparison: EQ, NE, LT_S, GT_S, LE_S, GE_S, LT_U, GT_U, LE_U, GE_U, EQZ
• Float arithmetic: FADD, FSUB, FMUL, FDIV, FNEG, FABS, FSQRT, FCEIL, FFLOOR, FMIN, FMAX
• Float comparison: FEQ, FNE, FLT, FGT, FLE, FGE
• Conversions: F2I_S, F2I_U, I2F_S, I2F_U, FCONV, EXTEND_S, EXTEND_U, TRUNC, BITCAST
• SELECT with constant condition or equal arms
• a block parameter every edge supplies with the same constant

Ordering: Should run first so later passes see simplified constants. Benefits from running before copy propagation and DCE.

Peephole

Pattern-matches short instruction sequences and replaces them with simpler equivalents. Runs to a fixed point (up to 8 rounds per function).

Transformations:

• Double negation: neg(neg(x)) to x
• Double NOT: not(not(x)) to x
• Self-ops: x - x to 0, x ^ x to 0, x & x to x, x | x to x
• sub x (neg y) to add x y; add x (neg y) to sub x y
• Redundant extension/truncation/fconv to same width to copy
• EXTEND chain collapse (e.g., extend_s i32 (extend_s i16 x) to extend_s i32 x)
• TRUNC over EXTEND_S/EXTEND_U back to source width to copy
• EQ x 0 to EQZ x
• EQZ of a comparison to the comparison’s logical inverse
• EQZ(EQZ x) to x when x is a known boolean
• BITCAST(BITCAST x) round-trip to x
• SELECT(cond, 1, 0) to cond; SELECT(cond, 0, 1) to EQZ cond
• FNEG(FNEG x) to x; FABS(FABS x) to FABS x; FABS(FNEG x) to FABS x
• EXTEND_U(TRUNC x) to AND x mask when a suitable LDI exists
• De Morgan with a constant operand (single-use guard)
• Constant reassociation: (x + c1) + c2 to x + (c1+c2) (and SUB variants)

Ordering: Run after constant folding. Produces dead instructions for DCE.

Strength reduction

Replaces expensive operations with cheaper equivalents when one operand is a known constant. Pass NULL for config to disable fast-math float rewrites.

Transformations (integer):

• x * 0 to ldi 0
• x * 1 to x
• x * -1 to neg x
• x * 2^N to x << N
• x * C to shift+add decomposition when popcount(|C|) is small
• x * -C to negated shift+add chain
• x / 1 to x
• x /u 2^N to x >>u N
• x %u 2^N to x & (2^N - 1)
• x /s ±2^k to bias+shift sequence
• x %s ±2^k to bias+mask sequence
• Identity: x + 0, x - 0, x | 0, x ^ 0, x << 0, x >> 0 to x
• Annihilator: x & 0 to 0, x | -1 to -1
• 0 - x to neg x, x ^ -1 to not x
• Shift chain: (x << k) << j to x << (k+j)

Transformations (float, requires config->fast_math):

• FMUL x 1.0 to x
• FMUL x 0.0 / FADD x -0.0 to 0.0
• FDIV x C to FMUL x (1/C) when C is a non-zero constant

Ordering: Run after constant folding and peephole. The MUL decomposition phase inserts new instructions, rebuilding the function’s instruction array and block boundaries. Benefits from copy propagation running beforehand.

Copy propagation

Rewrites all uses of a trivial copy to reference the original value directly. Operates to a fixed point to collapse multi-hop chains.

Trivial-copy patterns detected:

• a block parameter every edge supplies with the same value (self-references ignored)
• a block parameter whose block has a single predecessor edge
• cycles of parameters that forward a single outside value
• SELECT cond x x (both arms identical)
• SELECT with constant LDI condition
• Same-type BITCAST iN <- iN
• Identity EXTEND_S / EXTEND_U where source type matches destination
• FIELD_SET(agg, i, FIELD(agg, i)) (write-back of the same field is identity with agg)

Ordering: Run after constant folding and peephole. Enables further simplification by DCE and control-flow optimization.

Common subexpression elimination

Deduplicates pure value-producing instructions with identical (opcode, type, operands) within a single basic block. Redundant instructions are rewritten to NOP and their SSA ids are redirected to the original computation. Commutative opcodes (ADD, MUL, AND, OR, XOR, EQ, NE, FADD, FMUL, FMIN, FMAX, FEQ, FNE) are canonicalized by sorting operand ids before hashing.

Uses an open-addressed hash table per block with FNV-1a hashing and linear probing. Loads and side-effecting opcodes are conservatively excluded, and a volatile access never keys into the table at all: two volatile reads of one address are two values, not one.

Ordering: Run after copy propagation so operand ids are canonical. Strictly intrablock; GVN handles cross-block redundancies.

Global value numbering

Assigns every SSA value a congruence-class “value number” (VN) such that two values share a VN when they are computed by the same opcode, type, and operand VN tuple. Replaces redundant computations across basic blocks using dominator information.

Pipeline:

1. Seed every SSA id with VN = id.
2. Iterate in program order, building canonical keys with commutative operand VN sorting. A block parameter is its own class, since its value depends on which edge arrived (modulo back-edge self-references).
3. Build a replacement table mapping each id to the smallest-index leader that dominates it within its congruence class.
4. Rewrite operand references. Dead instructions are left for DCE.

A volatile access is its own congruence class, since two reads of one address may answer differently with no write anywhere between them.

Requires the esper_dom utility for dominator computation.

Ordering: Run after CSE. Subsumes CSE for cross-block cases. Should run before LICM.

Loop-invariant code motion

Hoists pure, loop-invariant computations out of natural loops into a pre-header block. Iterates to a fixed point so multiple and nested loops are processed.

Pipeline:

1. Build dominator tree via esper_dom.
2. Discover natural loops by identifying back edges (successor dominates source).
3. Ensure a unique pre-header exists; synthesize one if necessary.
4. Iteratively classify invariant instructions: an instruction is invariant when its opcode is pure, speculatable, and every SSA operand is defined outside the loop or is itself invariant.
5. Move invariant instructions into the pre-header.

Safety: A two-tier check guards hoisting decisions. Structural purity excludes loads, stores, calls, atomics, fences, allocations, and block parameters, and a volatile access on top of that: a loop-invariant address does not make the access invariant, because it has to happen once per trip. Speculation safety excludes division, remainder, FDIV, float arithmetic, and F2I conversions, which may trap or raise IEEE 754 exception flags.

A header that takes block parameters. A synthesized pre-header declares the same parameters its header declares and forwards them on its own jump. Each edge arriving from outside the loop is then re-aimed at the pre-header by changing only the block its branch names, so every edge keeps the arguments it was already carrying. The alternative, a parameterless pre-header carrying fixed arguments on its own jump, works only when there is exactly one outside edge, and a header with two outside predecessors is precisely the case where no existing block can be reused. The back edge is not in the re-aimed set and still names the header, which is what keeps the pre-header outside the loop and the hoisted code out of every iteration.

Two outside edges are declined rather than re-aimed, and only when the header actually declares parameters: one leaving a jump table, whose targets are a single shared list with no room for per-edge values, and a fall-through, which has no terminator to carry anything.

A block parameter is itself never hoisted: both take their value from whichever edge arrived, so neither can be evaluated ahead of the block it belongs to.

Ordering: Run after GVN. Invalidates hot-path side tables. Rebuilds the function’s instruction array and block layout.

Devirtualization

Rewrites indirect calls (CALL_IND / CALL_IND_BIG) whose target SSA value resolves to a single known function id into direct calls (CALL / CALL_BIG).

Resolution sources:

• LDI with an integer immediate naming a valid function index
• GLOBAL_GET of an immutable global whose initializer constant is in range

Uses a three-state lattice per SSA id (UNKNOWN, SINGLE(fn), MULTI). Leaves are seeded in one pass; every other instruction stays UNKNOWN. A target that reaches the call through a block parameter is not resolved, because its values arrive on the branches rather than on one instruction.

Ordering: Run before inlining so newly direct calls become inlining candidates. Run before TCO and escape analysis.

Function inlining

Substitutes small callee bodies into their caller at direct call sites. Self-recursive callees and extern declarations are skipped.

Cost model:

• Single-block callees: up to 8 instructions (16 when the call site is hot)
• Multi-block callees: up to 16 instructions (32 when the call site is hot)
• Hot-site boost uses esper_hotpath side tables when available

Algorithm:

1. Split the caller block at the call site.
2. Copy callee blocks with remapped SSA ids (params map to call arguments).
3. Rewrite callee RET instructions as JMP to a post-call block that declares one parameter per returned component, each edge carrying the values.
4. Reroute downstream uses of the call result to the new parameters.

Ordering: Run after devirtualization. Invalidates hot-path side tables. Benefits from running before control-flow simplification and DCE.

Tail call optimization

Rewrites self-tail call ... ret patterns into in-place jump-to-entry loops. Only intra-procedural self-recursion is handled; sibling-tail calls and mutual recursion are left for backends.

Transform shape:

• Insert a preamble block 0 with a JMP to the original entry (now block 1).
• Give the loop header one merge per function parameter. The preamble edge carries the original parameter; each tail-call edge carries the call’s arguments.
• NOP the tail CALL and rewrite the trailing RET as a JMP to the loop header.

What comes out. The header declares one parameter per function parameter and each edge carries the arguments: the edge is the merge, so there is no predecessor list to fall out of step with the CFG.

What it declines: an entry block that already declares parameters, whose values the added merges would sit behind and never feed, and an entry block some branch already targets, whose incoming edge brings values the pass has no argument for.

Ordering: Run after devirtualization and inlining. Invalidates hot-path side tables.

Escape analysis

Lowers polymorphic ALLOC opcodes into SALLOC (stack) or HALLOC (heap) based on a def-use walk from each allocation result. Classifies each allocation as:

• Non-escaping: pointer never leaves function scope. Lowered to SALLOC.
• Bounded lifetime: pointer flows into a non-extern callee but does not escape further. Lowered to HALLOC with auto-inserted FREE before each RET.
• Unbounded lifetime: pointer is returned, stored to a global, or passed to an extern callee. Lowered to HALLOC with no auto-free.

Pointer derivation is tracked through ADD, SUB, SELECT, and BITCAST producing ptr-typed results, and through the branch arguments that carry a pointer into a block parameter. The analysis is intraprocedural; extern callees are conservatively assumed to leak.

Ordering: Run after inlining and TCO. May insert FREE instructions, rebuilding the function’s instruction stream.

Scalar replacement of aggregates (SROA)

Decomposes non-escaping aggregate SSA values (produced by STRUCT_NEW or STRUCT_NEW_BIG) into per-member scalar SSA values, eliminating aggregate construction overhead when every use is a FIELD projection or FIELD_SET replacement.

Eligibility:

A STRUCT_NEW is eligible for scalarization when every consumer of its SSA result is either a FIELD or a FIELD_SET instruction. If any use escapes (passed to a call, stored to memory, travels as a branch argument), the aggregate is left intact.

Transformations:

• FIELD consumers are replaced with the corresponding member operand of the original STRUCT_NEW.
• FIELD_SET consumers are replaced with a new STRUCT_NEW that copies all original members except the replaced one.
• The original STRUCT_NEW is NOPed when all uses are rewritten.

Ordering: Run after copy propagation (so trivial merge chains are collapsed and aggregate copies are canonical) and before DCE (so dead member instructions left behind are swept). In the standard pipeline, SROA runs after escape analysis and before control-flow simplification.

Control-flow simplification

Simplifies the control-flow graph. Nine sub-phases run in this order to a fixed point, and a tenth runs once afterwards:

1. Branch-on-constant: JMP_IF with a known LDI condition to unconditional JMP.
2. JMP_TABLE simplification: constant index to JMP; all-same targets to JMP.
3. Diamond collapse: JMP_IF with identical then/else targets to JMP.
4. Unreachable-after-terminator: NOP instructions trailing a terminator within a block.
5. Jump threading: terminators targeting pure-JMP forwarding blocks are rewritten to skip the intermediary.
6. Unreachable-arm folding: a JMP_IF with one arm leading only to an unreachable becomes a JMP along the other.
7. Redundant jump: JMP to the immediately following block (fallthrough) is NOPed.
8. Unreachable block elimination: blocks with no incoming edges are NOPed.
9. Block fusion: a block whose single predecessor is the block immediately above it is merged into it. A block that declares parameters is left alone, since fusing away the edge would delete the only place its arguments are named.
10. Branch reversal: when the cold arm of a JMP_IF is in fall-through position and the hot arm is not, the comparison is inverted and the targets swapped.

Branch reversal sits outside the fixed-point loop because it reads block_hot[], which every CFG mutation invalidates. It runs once, after the graph has stopped moving, and does nothing when no hot-path tables exist.

Unreachable-arm folding. Taking an arm that leads to an unreachable would be undefined, so control provably never takes it and the branch becomes a jump to the other arm. A bounds check whose failure a frontend has already proved impossible then costs nothing, since the comparison feeding the branch is left for DCE. The qualifying rule is stricter than “has no side effect”: past the block’s parameters it must hold one unreachable and nothing else but NOPs, so even a pure ldi there blocks the fold. A denylist of effects would default a newly added opcode to foldable, and getting that wrong deletes a real effect; a pure computation in a block with no successors is dead by construction anyway. A trap never qualifies, because stopping the program is an effect rather than an assertion that the path is impossible.

Nothing to keep in step. A merge’s values travel on the branch, so a phase that drops or merges an edge moves them with it and there is no predecessor list to repair. Two phases decline rather than rewrite: threading refuses a forwarder that carries arguments, since skipping past it would drop them, and refuses to thread both arms of one branch into a block that takes parameters, which would need two argument lists on one arm.

Ordering: Run after copy propagation (which may create constant conditions) and before DCE (which sweeps dead instructions left by NOP rewrites). Invalidates hot-path side tables.

Dead code elimination

Removes instructions whose results are never used and which have no side effects. Iterates to a fixed point.

Sub-passes (run in dependency order per iteration):

1. Unreachable block elimination: blocks with no incoming edges are NOPed.
2. HALLOC/FREE pair removal: when a HALLOC’s only consumer is a FREE, both are NOPed.
3. Dead block parameter elimination: a parameter with no use outside the argument it is passed for itself goes, from the end of the block’s run, and every branch into the block drops the matching argument.
4. Base sweep: any value-producing, side-effect-free instruction with zero uses is NOPed.

Side-effecting opcodes are never removed: stores, calls, returns, jumps and jump tables, TRAP and UNREACHABLE, MEMCPY / MEMMOVE / MEMSET, FREE, atomic stores, RMWs and compare-exchanges, fences, vector stores, and syscalls. None of the bulk-memory three produces a value, so a use count says nothing about whether they matter; they are pinned by opcode.

BLOCK_PARAM is pinned by the same switch, though not because it has an effect. Its incoming values ride on the branches into its block, so removing an unused parameter would leave every one of those branches passing an argument for a parameter that is no longer there.

Unused ATOMIC_LOAD is only removable under ESP_MEM_RELAXED ordering, and a volatile load is never removable: performing the access is the observable effect, so an unused result says nothing about whether the instruction is dead.

Ordering: Run after all other optimization passes. Should run before the symbol-table sweep.

Symbol-table sweep

Removes module-level symbols (globals, constants, extern functions) that have no remaining live references after DCE has converged. Defined (non-extern) functions are always pinned as exports.

Algorithm:

1. Pin all defined functions as live.
2. Sweep every live instruction and mark referenced globals, constants, and function indices.
3. Pin initializer constants for surviving globals.
4. Build old-to-new remap tables, compact each symbol table, and rewrite operand references.

Ordering: Must run after DCE. Single-pass; does not iterate with DCE.

Hot-path estimation

Produces per-block static frequency estimates without modifying the IR. Populates func->block_weight[] and func->block_hot[] as side tables.

Algorithm:

1. Build CFG and dominator tree.
2. Discover natural loops and compute per-block loop depth.
3. Assign base weight 10^depth per block.
4. Apply cold bias (halve weight) for blocks containing DIV/REM/FDIV or extern calls, and for predecessors of RET.
5. Derive block_hot[b] = (block_weight[b] >= threshold). A zero threshold defaults to 10 (one loop nesting level).

Query API:

u32  esper_block_weight(const EsperFunc *func, u32 bb);
bool esper_block_is_hot(const EsperFunc *func, u32 bb);
void esper_hotpath_print(const EsperUnit *unit, FILE *out);
void esper_hotpath_invalidate(EsperFunc *func);

Ordering: Run last. Consumed by inlining cost model and devirtualization. Any CFG-mutating pass must call esper_hotpath_invalidate on affected functions.

Configuration reference

All pass flags live on the EsperConfig struct:

typedef struct {
  bool opt_mem2reg : 1;     // Stack slots promoted to SSA values
  bool opt_const_fold : 1;  // Constant folding
  bool opt_peephole : 1;    // Peephole pattern replacement
  bool opt_strength : 1;    // Strength reduction
  bool opt_copy_prop : 1;   // Copy propagation
  bool opt_cse : 1;         // Common subexpression elimination
  bool opt_gvn : 1;         // Global value numbering
  bool opt_licm : 1;        // Loop-invariant code motion
  bool opt_devirt : 1;      // Indirect-call devirtualization
  bool opt_inlining : 1;    // Function inlining
  bool opt_tco : 1;         // Tail call optimization
  bool opt_escape : 1;      // Escape analysis (ALLOC lowering)
  bool opt_cf_opt : 1;      // Control-flow simplification
  bool opt_dce : 1;         // Dead code elimination
  bool opt_prune : 1;       // Symbol-table sweep
  bool opt_hotpath : 1;     // Hot-path estimation side tables
  bool opt_sroa : 1;        // Scalar replacement of aggregates
  u32  hotpath_threshold;   // Block-weight threshold for hot marking
  bool fast_math : 1;       // Permit non-IEEE float rewrites
} EsperConfig;

Pass config to esper_optimize(unit, &config) to run all enabled passes in their fixed order, or invoke each pass function individually for custom pipelines.