On-stack replacement

Deep dive

How it works

Parts:

• Tier 0, the bytecode interpreter over compiled bytecode — frame = pc plus slots; the semantic reference.
• Back-edge counter — bumped on every jump to a lower pc.
• OSR compile — a variant of the method entered at one loop header, live values as parameters.
• Entry map — slot to register, stack slot or constant, plus type or range guards.
• Exit map — per guard, the mapping reversed, then resume in tier 0 (see deoptimization).
• Controller — caps retries so enter-fail loops end.

1. Run in tier 0; every jump to a lower pc bumps the counter.
2. Over the threshold, enqueue an OSR compile for this loop header on a background thread (as in JIT compilation); keep interpreting.
3. The variant is compiled with the current profile (inline caches, shapes) and the entry values as inputs. Facts checked once at entry (this local is a small integer) may be assumed inside.
4. When installed, the next back-edge runs the entry check; if the guards pass, slots are copied into the variant's registers and execution continues at the header.
5. A failed guard jumps to an exit stub: values go back into slots, pc is set to the recorded bytecode index, tier 0 resumes.
6. Cap the exits; then stay in tier 0 for this loop or recompile with wider assumptions.

 interpreter frame            OSR variant (loop header H)
 pc=H  [i=3][acc=5][n=9] --enter (guards)--> r0=3 r1=5 r2=9 ... loop
   ^                                                          | guard fails
   +--------- exit map: r0,r1 -> slots, pc=H <----------------+

Why headers. A header is reached every iteration, usually with an empty operand stack, so the live set is small and the same for all entries. OSR at arbitrary pcs needs one map each and blocks optimization at the merge point.

Code

Bytecode for acc += i; i += 1 while i < n. Past the threshold the live slots move into osr_loop, native code that speculates i and acc fit in i32. Overflow fails a guard, the state returns to the slots and the interpreter resumes at the header. Asserts compare all thresholds with pure interpretation and count entries and exits; n = 100_000 overflows i32 and forces the exit.

#[derive(Clone, Copy)]
enum Op {
    JumpIfGe { a: usize, b: usize, to: usize },
    AddTo { dst: usize, src: usize },
    Inc(usize),
    Jump(usize), // a back-edge when to <= own pc
    Halt,
}
const I: usize = 0; const ACC: usize = 1; const N: usize = 2;

struct Frame { pc: usize, slots: [i64; 3] }

enum Exit { Done(i64), Deopt { i: i64, acc: i64 } }

// "Compiled" code entered at the loop header. Speculates that i and acc fit in
// i32; a guard runs before state changes, so a failure leaves exactly the
// interpreter's state at the header.
fn osr_loop(i: i64, acc: i32, n: i64) -> Exit {
    let (mut i, mut acc) = (i, acc);
    while i < n {
        let next = i32::try_from(i).ok().and_then(|v| acc.checked_add(v));
        match next {
            Some(a) => { acc = a; i += 1; }
            None => return Exit::Deopt { i, acc: acc as i64 },
        }
    }
    Exit::Done(acc as i64)
}

#[derive(Default, Debug)]
struct Stats { backedges: u64, osr_entries: u32, osr_exits: u32 }

fn run(code: &[Op], n: i64, threshold: u64, st: &mut Stats) -> i64 {
    let mut f = Frame { pc: 0, slots: [0, 0, n] };
    let loop_header = 0; // the one OSR entry point
    let mut tried = false;
    loop {
        match code[f.pc] {
            Op::JumpIfGe { a, b, to } => f.pc = if f.slots[a] >= f.slots[b] { to } else { f.pc + 1 },
            Op::AddTo { dst, src } => { f.slots[dst] += f.slots[src]; f.pc += 1 }
            Op::Inc(s) => { f.slots[s] += 1; f.pc += 1 }
            Op::Jump(to) => {
                if to <= f.pc {
                    st.backedges += 1;
                    if !tried && st.backedges > threshold {
                        tried = true; // one attempt per run: no enter/exit ping-pong
                        // OSR entry: slots -> arguments, with an entry guard.
                        if let Ok(acc) = i32::try_from(f.slots[ACC]) {
                            st.osr_entries += 1;
                            match osr_loop(f.slots[I], acc, f.slots[N]) {
                                Exit::Done(v) => return v,
                                Exit::Deopt { i, acc } => {
                                    // OSR exit: the mapping in reverse.
                                    st.osr_exits += 1;
                                    f.slots[I] = i; f.slots[ACC] = acc; f.pc = loop_header;
                                    continue;
                                }
                            }
                        }
                    }
                }
                f.pc = to;
            }
            Op::Halt => return f.slots[ACC],
        }
    }
}

fn main() {
    use Op::*;
    let code = [JumpIfGe { a: I, b: N, to: 4 }, AddTo { dst: ACC, src: I }, Inc(I), Jump(0), Halt];
    let sum = |n: i64| n * (n - 1) / 2;
    for n in [0i64, 1, 10, 1000, 100_000] { // 100_000 overflows i32
        let pure = run(&code, n, u64::MAX, &mut Stats::default());
        assert_eq!(pure, sum(n));
        for t in [0u64, 1, (n / 2) as u64, n as u64, n as u64 + 7] {
            let mut st = Stats::default();
            assert_eq!(run(&code, n, t, &mut st), pure, "n={n} t={t}");
            let entered = (n as u64 > t) as u32; // n back-edges; OSR at edge t+1
            assert_eq!(st.osr_entries, entered, "n={n} t={t}");
            let overflows = entered == 1 && sum(n) > i32::MAX as i64;
            assert_eq!(st.osr_exits, overflows as u32, "n={n} t={t}");
        }
    }
    println!("ok");
}

Own noisy measurement (Apple M4 Pro, release, n = 60,000 repeated, best of 5): about 4.2-4.6 ns per iteration interpreted, 0.57-0.65 ns after OSR.

Complexity and constants

• Counter: one increment and compare per back-edge; entry or exit copies O(live values).
• Cost drivers: back-edge checks in tier 0, one extra compile per hot loop entry (code-cache bytes, compile CPU) and frame-map metadata per entry and guard.

Efficiency

• Cost: One transfer copies each live slot once. The gain is the whole remaining loop at tier-1 speed, about 7x in the toy (self-measured). Bound: compile latency and interpreter dispatch before the swap.
• Levers:
  • Entry only at back-edges — one map per loop and full loop optimization (dotnet/runtime OSR design doc) — whenever the engine can pick the points.
  • Separate back-edge thresholds per tier — OSR into C1 at 60,000 and C2 at 40,000 back-edges by default (Tier3BackEdgeThreshold, Tier4BackEdgeThreshold, compiler_globals.hpp) — tuned for long loops.
  • Notify the policy in batches — every 2^13 back-edges by default (Tier3BackedgeNotifyFreqLog = 13) instead of on every jump — hot interpreter loops.
  • Guard the entry once, not per iteration — facts checked at entry hold inside the loop — numeric loops.
  • Cap failed entries — SpiderMonkey allows 6000 OSR attempts before invalidating the script (osrPcMismatchesBeforeRecompile, JitOptions.cpp) — unstable code.
• Naive → standard → state of the art: wait for the next call · a one-call loop stays slow; back-edge counter and OSR at headers · fast after the threshold; multi-tier OSR with exit on guard failure · V8, HotSpot.

Implementation notes

• Keep the interpreter's frame layout the one the compiled code expects, as V8's Sparkplug does, and OSR needs almost no translation (V8 blog).
• Entry checks once, exit guards inside; loop-carried values get registers from the normal register allocator and SSA facts.
• Metering or preemption can share the back-edge check.

Pitfalls

• State mismatch: a slot missing from the map, or a value narrowed without a guard (the i32 entry check above), silently changes results.
• Enter and exit ping-pong: without a cap the loop mostly copies state; the toy tries OSR once per run.
• Debuggers and profilers expect interpreter frames; optimized frames need the exit map to show source-level locals (why Self invented dynamic deoptimization).

Variants and alternatives

In production

• HotSpot: -XX:+PrintCompilation marks OSR compiles with % (compileTask.cpp); Tier3/Tier4 back-edge thresholds trigger them.
• V8: OSR from Ignition to optimized code for hot loops, and back on deopt (Sparkplug post); --osr-from-maglev controls Maglev to TurboFan (flag-definitions.h).
• SpiderMonkey: osr default true, "functions may be entered at loop headers" (JitOptions.cpp).
• .NET 7: OSR and quick JIT for loops on by default (Toub, .NET 7 performance post); patchpoints at back-edges, OSR_HitLimit 10.
• LuaJIT: trace start at hot loops (lj_jit.h). Databases: HyPer adaptive execution (paper).

Implementations

Sources

• Hölzle, Chambers, Ungar, Debugging Optimized Code with Dynamic Deoptimization, PLDI 1992. paper
• D'Elia, Demetrescu, On-Stack Replacement, Distilled, PLDI 2018. paper
• Kohn, Leis, Neumann, Adaptive Execution of Compiled Queries, ICDE 2018. paper
• Ayers, On Stack Replacement in the CLR, design doc. doc
• Toub, Performance Improvements in .NET 7, 2022. post
• OpenJDK, compileTask.cpp. code · compiler_globals.hpp. code
• V8, Sparkplug, 2021. post · flag-definitions.h. code
• Mozilla, JitOptions.cpp. code · LuaJIT, lj_jit.h. code