Deoptimization

Deep dive

How it works

Parts:

• Slow tier — interpreter or baseline; the semantic reference; collects feedback (inline caches, type profiles).
• Optimized tier — code compiled from feedback, values unboxed in registers or stack slots.
• Guards — compare/branch per assumption (type, shape, bounds, overflow, callee); the failure edge is cold.
• Deopt metadata (frame state) — per deopt point: bytecode offset, and per interpreter local its location (register, stack slot, constant, or virtual object to allocate).
• Dependency table — assumption -> compiled code relying on it (class hierarchy, prototype chain, constant global).
• Controller — counts exits; recompiles, backs off or stops optimizing.

1. Tier up: hot code (call or back-edge counters) is compiled from feedback, one guard per assumption.
2. At each guard the compiler records the frame state: bytecode index plus a location for every live interpreter value. For inlined calls it records the whole chain of virtual frames, each with its own index and values.
3. Eager deopt: a guard fails and jumps to a stub that reads the metadata, boxes values, allocates scalar-replaced objects, builds one interpreter frame per virtual frame and resumes at the recorded index; the failing operation re-executes in the slow tier.
4. Lazy deopt: when an assumption in the dependency table breaks (a subclass loads, a prototype is mutated, a "constant" global is written), dependent code is marked invalid. Activations already on the stack deoptimize when control returns into them; no new calls enter.
5. The slow tier updates feedback (the site now sees the new type) and the controller counts the exit.
6. Recompile with wider feedback, or stop optimizing this code once exits pass a limit.
7. OSR entry, the opposite direction: a hot interpreted loop jumps into optimized code at a loop header if its frame satisfies the compiled assumptions. Entry is harder than exit: extra entry points weaken optimization at merge points.

 interpreter frame            optimized code (raw regs)
 [acc: Int(5)][i: 3] --OSR--> r0=5  r1=3 ... guard(a[i] is Int)
        ^                                        | fail
        +-- rebuild frames <-- metadata[pc] -----+
        (inlined callee => 2+ frames from one machine frame)

Origin: Hölzle, Chambers and Ungar (Self, PLDI 1992) used dynamic deoptimization so a debugger can see source-level state of optimized code, converting optimized frames lazily into unoptimized ones. The same machinery became the safety net for speculation.

Code

Toy two-tier executor for acc += a[i]; seen += 1: a generic interpreter with boxed values, an int-specialized tier with two guards (type, overflow), OSR entry from the interpreter, and deopt via metadata back to the interpreter, resuming mid-loop. Asserts that every combination equals the pure interpreter.

#[derive(Clone, Copy, PartialEq, Debug)]
enum V { Int(i64), Flt(f64) }

/// Interpreter frame: loop index plus boxed locals [acc, seen].
#[derive(Clone, PartialEq, Debug)]
struct Frame { i: usize, slots: [V; 2] }

fn add(a: V, b: V) -> V {
    match (a, b) {
        (V::Int(x), V::Int(y)) => match x.checked_add(y) {
            Some(s) => V::Int(s),
            None => V::Flt(x as f64 + y as f64), // overflow promotes
        },
        (V::Int(x), V::Flt(y)) | (V::Flt(y), V::Int(x)) => V::Flt(x as f64 + y),
        (V::Flt(x), V::Flt(y)) => V::Flt(x + y),
    }
}

/// Tier 0: generic interpreter for `loop { acc += a[i]; seen += 1 }`.
fn interp(a: &[V], mut f: Frame, until: usize) -> Frame {
    while f.i < until.min(a.len()) {
        f.slots[0] = add(f.slots[0], a[f.i]);
        f.slots[1] = add(f.slots[1], V::Int(1));
        f.i += 1;
    }
    f
}

/// Deopt metadata: machine register r lives in interpreter slot META[r] as Int.
const META: [usize; 2] = [0, 1];

enum Exit { Done([i64; 2]), Deopt { i: usize, regs: [i64; 2] } }

/// Tier 1: assumes every a[i] is Int and sums do not overflow. Guards run
/// before the iteration commits, so regs hold the state at its start.
fn fast(a: &[V], mut i: usize, mut r: [i64; 2]) -> Exit {
    while i < a.len() {
        let V::Int(x) = a[i] else { return Exit::Deopt { i, regs: r } }; // type guard
        let Some(s) = r[0].checked_add(x) else { return Exit::Deopt { i, regs: r } }; // overflow guard
        r[0] = s;
        r[1] += 1;
        i += 1;
    }
    Exit::Done(r)
}

/// OSR entry: allowed only if the interpreter frame satisfies the assumption.
fn osr_enter(f: &Frame) -> Option<[i64; 2]> {
    match f.slots { [V::Int(a), V::Int(b)] => Some([a, b]), _ => None }
}

/// Deopt: rebuild the boxed interpreter frame from registers via metadata.
fn materialize(i: usize, regs: [i64; 2]) -> Frame {
    let mut f = Frame { i, slots: [V::Int(0); 2] };
    for (r, &slot) in META.iter().enumerate() { f.slots[slot] = V::Int(regs[r]); }
    f
}

/// Interpret `warm` iterations, OSR into tier 1, deopt back if a guard fails.
fn run(a: &[V], warm: usize) -> (Frame, bool) {
    let f = interp(a, Frame { i: 0, slots: [V::Int(0); 2] }, warm);
    let Some(regs) = osr_enter(&f) else { return (interp(a, f, a.len()), false) };
    match fast(a, f.i, regs) {
        Exit::Done(r) => (materialize(a.len(), r), false),
        Exit::Deopt { i, regs } => (interp(a, materialize(i, regs), a.len()), true),
    }
}

fn main() {
    let ints: Vec<V> = (1..=100).map(V::Int).collect();
    let mut mixed = ints.clone();
    mixed[60] = V::Flt(0.5); // type guard fails mid-loop
    let mut ovf = ints.clone();
    ovf[10] = V::Int(i64::MAX); // overflow guard fails
    for (a, want) in [(&ints, false), (&mixed, true), (&ovf, true)] {
        let reference = interp(a, Frame { i: 0, slots: [V::Int(0); 2] }, a.len());
        for warm in [0, 5, 70, 100] {
            let (f, deopted) = run(a, warm);
            assert_eq!(f, reference);
            if warm <= 10 { assert_eq!(deopted, want); }
        }
    }
}

Compiled and run (stable Rust). The guard fires before the iteration commits, so registers equal the state at the start of iteration i.

Complexity and constants

• Fast path: one compare and a predicted-not-taken branch per guard (tag or shape-id compare).
• A deopt: decode metadata, box values, build frames, resume; linear in live values and inlined frames. No figures here, they differ per engine.
• Metadata grows with deopt points times live values; engines compress it (PyPy's resume.py encodes frame chains compactly).
• Cost drivers: guards left in loops (hoist or fold), metadata bytes and code-cache pressure, the recompile after each invalidation, and slow-tier time before re-optimization.

Efficiency

• Cost: a compare per assumption (bound: branch throughput, not memory); an exit rebuilds frames, then runs at slow-tier speed until recompiled. Recompilation dominates: the V8 Maglev post reports Maglev compiling about 10x slower than Sparkplug and 10x faster than TurboFan. No measured exit latencies here.
• Levers:
  • hoist/eliminate guards after the first check — one check proves a fact for later uses (JSC post) — straight-line code, loops
  • dependencies instead of runtime checks for stable facts — zero guard cost in code (Maglev blog) — constant globals, shapes never transitioned away
  • cap trap counts and back off exponentially — bounds wasted compiles (HotSpot flags, JSC) — unstable code
  • tier up once feedback is stable — fewer exits (JSC control system) — large apps
• Naive -> standard -> state of the art: interpret everything · slow, never wrong; guards plus deopt to the interpreter · a compare per guard, rare exits; cheap mid-tier (Maglev, DFG) with dependency invalidation · recompiles are cheap.

Implementation notes

• Deopt points must be consistent: no side effect (store, call) may happen between the last committed bytecode boundary and the guard, or the slow tier would repeat it.
• Record only values live at the bytecode index: smaller metadata, fewer live registers.
• Inlining: store virtual frames outer-to-inner; the deoptimizer builds all of them (V8 TranslatedFrame has kinds for inlined and stub frames).
• Scalar-replaced (escape-analyzed) objects need materialization data: type, field values.
• Lazy deopt needs patchable return addresses or an invalid flag checked on return, plus a way to find dependents quickly (dependency table keyed by class/shape).
• To stay cheap: few and merged guards, cold stubs, metadata shared across sites.

Pitfalls

• Deopt loop: same speculation, same failure. Fix: record the failure in feedback so the next compile does not repeat the guess, and cap recompiles.
• Tier-up on unstable feedback: compile, deopt, compile again; the waste is compile time.
• Frame-state bugs show only on the rare failing path: test by forcing deopts (V8 has a DeoptimizeNow reason).
• Side effects before a guard (hoisted or reordered) make the resume point unsound.

Variants and alternatives

In production

• V8: Ignition, Maglev and TurboFan share one deoptimizer; kinds kEager, kLazy, kLazyAfterFastCall; reasons such as "hole", "lost precision", "division by zero".
• HotSpot (C1/C2): uncommon traps with reasons and actions, PerBytecodeTrapLimit 4, PerMethodTrapLimit 100, PerMethodRecompilationCutoff 400 in current source; class-hierarchy dependencies (unique_concrete_method, leaf_type) invalidate compiled code.
• JavaScriptCore: DFG/FTL "OSR exit" to Baseline or LLInt; exit counting, jettison, recompilation with exponential backoff; failing watchpoints jettison at once.
• LuaJIT: guards exit to snapshots restoring the Lua stack. PyPy: guards carry resume data; failures are counted and bridges compiled.

Implementations

Sources

• Urs Hölzle, Craig Chambers, David Ungar, Debugging Optimized Code with Dynamic Deoptimization, PLDI 1992. paper
• Filip Pizlo, Speculation in JavaScriptCore, WebKit blog. post
• V8 team, Maglev - V8's Fastest Optimizing JIT, 2023. post
• OpenJDK, src/hotspot/share/runtime/deoptimization.hpp. code
• LuaJIT, src/lj_jit.h, src/lj_snap.c. code