JIT compilation

Deep dive

How it works

Parts:

• Tier 0, the bytecode interpreter — runs everything first; collects counters and type feedback (inline caches, shapes).
• Counters — per function (invocations) and per loop (back-edges); one increment on entry or branch.
• Tier policy — thresholds that decide when to enqueue a compile, and which tier.
• Compile queue and threads — background workers that compile; the running program keeps going in the old tier.
• Baseline tier — fast, template-like compiler with almost no optimization (V8 Sparkplug, JSC Baseline, SpiderMonkey Baseline).
• Optimizing tier — speculative compiler using feedback: inlining, instruction selection, register allocation.
• Code cache — bounded memory for machine code, written under W^X rules.
• Exit paths — deoptimization back to tier 0, and on-stack replacement to enter new code mid-loop.

1. Every function starts in tier 0 with its counters at zero.
2. Each call and each loop back-edge increments a counter; the check against the threshold is the only hot-path cost.
3. At the threshold the runtime enqueues a compile request.
4. A compiler thread builds code and installs it in the code cache; the interpreter serves calls until the entry point is swapped.
5. A long-running loop cannot wait for the next call, so a back-edge counter triggers an OSR compile entered at the loop header.
6. If the next tier has its own thresholds, the process repeats (HotSpot: interpreter, C1 with profiling, C2).
7. If a speculation fails, execution drops to tier 0; counters restart or the code is blacklisted.
8. When the code cache fills, cold code is freed or compilation stops.

 interp --calls>=T1--> baseline --calls>=T2--> optimized
   ^                      |                       |
   +---- deopt (bad bet) -+-----------------------+
 loop in tier 0 --back-edges>=B--> OSR compile --> enter at loop header

Method JIT vs tracing JIT. A method JIT compiles whole functions, with inlining. A tracing JIT records one hot path through a loop (including calls) as straight-line code with guards, and compiles that; other paths are side exits that grow new traces. LuaJIT traces from hot loops and calls (hotloop = 56 iterations, hotexit = 10 taken exits start a side trace). PyPy traces the interpreter itself (meta-tracing), so a language implemented in RPython gets a JIT without writing a compiler. Traces suit loops with stable paths; method JITs suit branchy code.

Code

Two-tier executor for a tiny stack bytecode. Tier 0 interprets with a per-function call counter. When the counter reaches the threshold, the bytecode is closure-compiled: the operand stack is simulated at compile time, so each stack slot becomes one closure and the dispatch loop disappears. Calls from either tier go through call, so counters see all traffic.

use std::cell::{Cell, OnceCell};

#[derive(Clone, Copy)]
enum Op { Const(i64), Arg, Add, Mul, Call(usize) }

type Compiled = Box<dyn Fn(&Vm, i64) -> i64>;

struct Func {
    code: Vec<Op>,
    calls: Cell<u32>,         // profiling counter
    interpreted: Cell<u32>,   // for the test: calls served by tier 0
    compiled: OnceCell<Compiled>,
}

struct Vm { funcs: Vec<Func>, threshold: u32 }

impl Vm {
    fn new(codes: Vec<Vec<Op>>, threshold: u32) -> Vm {
        let funcs = codes.into_iter().map(|code| Func {
            code, calls: Cell::new(0), interpreted: Cell::new(0), compiled: OnceCell::new(),
        }).collect();
        Vm { funcs, threshold }
    }

    fn call(&self, f: usize, arg: i64) -> i64 {
        let func = &self.funcs[f];
        let n = func.calls.get() + 1;
        func.calls.set(n);
        if n == self.threshold {                       // tier-up exactly here
            let _ = func.compiled.set(compile(&func.code));
        }
        match func.compiled.get() {
            Some(c) => c(self, arg),                   // tier 1
            None => { func.interpreted.set(func.interpreted.get() + 1); self.interpret(&func.code, arg) }
        }
    }

    fn interpret(&self, code: &[Op], arg: i64) -> i64 {
        let mut st: Vec<i64> = Vec::with_capacity(8);
        for op in code {
            match *op {
                Op::Const(c) => st.push(c),
                Op::Arg => st.push(arg),
                Op::Add => { let b = st.pop().unwrap(); let a = st.pop().unwrap(); st.push(a.wrapping_add(b)) }
                Op::Mul => { let b = st.pop().unwrap(); let a = st.pop().unwrap(); st.push(a.wrapping_mul(b)) }
                Op::Call(g) => { let a = st.pop().unwrap(); st.push(self.call(g, a)) }
            }
        }
        st.pop().unwrap()
    }
}

// Closure compilation: simulate the operand stack at compile time, so each
// stack slot becomes one closure and the dispatch loop disappears.
fn compile(code: &[Op]) -> Compiled {
    let mut st: Vec<Compiled> = Vec::new();
    for op in code {
        let node: Compiled = match *op {
            Op::Const(c) => Box::new(move |_, _| c),
            Op::Arg => Box::new(|_, a| a),
            Op::Call(g) => { let x = st.pop().unwrap(); Box::new(move |vm, a| { let v = x(vm, a); vm.call(g, v) }) }
            Op::Add | Op::Mul => {
                let (b, a) = (st.pop().unwrap(), st.pop().unwrap());
                match *op {
                    Op::Add => Box::new(move |vm, x| a(vm, x).wrapping_add(b(vm, x))),
                    _ => Box::new(move |vm, x| a(vm, x).wrapping_mul(b(vm, x))),
                }
            }
        };
        st.push(node);
    }
    st.pop().unwrap()
}

fn program() -> Vec<Vec<Op>> {
    use Op::*;
    vec![
        vec![Arg, Arg, Mul, Const(1), Add],                          // f0(x) = x*x + 1
        vec![Arg, Call(0), Arg, Const(1), Add, Call(0), Add],        // f1(x) = f0(x) + f0(x+1)
    ]
}

fn main() {
    let t = 50;
    let vm = Vm::new(program(), t);
    let reference = Vm::new(program(), u32::MAX); // never tiers up
    let mut sum = 0i64;
    for x in 0..1000 { sum = sum.wrapping_add(vm.call(1, x)); }
    println!("sum={sum}");
    for x in 0..1000 { assert_eq!(vm.call(1, x), reference.call(1, x)); }
    // f1 is called once per x, so it tiers up at call t: t-1 interpreted calls
    assert_eq!(vm.funcs[1].interpreted.get(), t - 1);
    assert!(vm.funcs[1].compiled.get().is_some());
    assert!(reference.funcs[1].compiled.get().is_none());
    // f0 reaches the threshold inside interpreted f1, so it also ran t-1 times in tier 0
    assert_eq!(vm.funcs[0].interpreted.get(), t - 1);
}

Run on an Apple M4 Pro: about 64 ns per tier-0 call of f1 (two inner calls) against about 12 ns in tier 1, and compiling f1 takes about 100 ns (self-measured, release build, order of).

Complexity and constants

• Per call: one counter increment and compare, O(1); in HotSpot the counters live in a profile object next to the method.
• Compile cost grows with code size and optimization level: baseline is one linear pass, optimizing runs many passes.
• Drivers: machine-code bytes per bytecode byte, compile CPU per method, and the executable-page flips per install.

Efficiency

• Cost: Tier 0 to tier 1 gave about 5x per call in the toy above (self-measured). In a real system the compile costs milliseconds, not nanoseconds: PostgreSQL's docs show a trivial query (plan cost 16) spending 7.1 ms in JIT generation, inlining and emission, so JIT must not run on cheap queries. Bound: compile CPU and warm-up latency, then code-cache memory.
• Levers:
  • Cost-based gate — PostgreSQL JIT only above jit_above_cost = 100,000, inlining and expensive optimization above 500,000 (PostgreSQL docs) — when queries vary widely in size.
  • Several tiers — a cheap baseline gets most code fast while the optimizer waits for stronger evidence (HotSpot 200 vs 5,000 call thresholds, compiler_globals.hpp) — when peak speed matters but start-up too.
  • Background threads — the program continues while compiling (BackgroundCompilation, CICompilerCount flags in HotSpot) — whenever spare cores exist; costs energy on small machines.
  • Reuse — compile once, run many: PCRE2 advises JIT when a pattern is matched many times (PCRE2 docs) — regexes, eBPF load.
  • Bounded code cache — LuaJIT caps machine code at 2,048 KB in 64 KB areas (lj_jit.h) — when memory is capped; HotSpot reserves 48 MB base, scaled by 5 for tiered mode (c2_globals_x86.hpp, compilerDefinitions.cpp).
• Naive → standard → state of the art: interpret everything · low start-up, slow forever; compile everything at load · slow start-up, wasted code; counters plus 2 tiers · fast start and fast peak (HotSpot C1/C2, JSC LLInt/Baseline/DFG/FTL); 3-4 tiers plus background compile, OSR and deopt · V8 adds Sparkplug and Maglev between Ignition and TurboFan.

Implementation notes

• Count at loop back-edges as well as calls, otherwise a single long-running main never tiers up.
• Compile with the profile at enqueue time; recheck on install, since the profile can change while the job waits.
• Order the queue by hotness, drop stale jobs, and bound the thread count to leave cores free.
• Emit into a writable region, flip to executable, flush the instruction cache (see W^X, emission).

Pitfalls

• Threshold too low: compile costs more than it saves (the PostgreSQL 7 ms example). Too high: warm-up drags on.
• Benchmarks must report warm-up and steady state separately.
• Deopt loops: speculate, fail, recompile the same way; cap retries (see deoptimization).
• Code-cache exhaustion: compilation stops and throughput falls, with no error.
• Compile threads steal CPU in small containers. Racy counters are fine in practice; exact tier-up tests need one thread, as above.

Variants and alternatives

In production

• V8: Ignition interpreter, Sparkplug baseline, Maglev mid-tier, TurboFan optimizer (V8 blog).
• JavaScriptCore: four tiers ending in FTL (WebKit blog). SpiderMonkey: Baseline Interpreter, Baseline JIT, then Ion/Warp (Mozilla Hacks; later names from memory).
• HotSpot: interpreter, C1 (levels 1-3), C2 (level 4); Graal can replace C2 via JVMCI (from memory).
• PostgreSQL: LLVM JIT for expressions and tuple deforming (docs). Linux: eBPF programs are JIT-translated after the verifier passes, controlled by bpf_jit_enable (kernel docs).
• QEMU TCG: guest code translated block by block at first execution, blocks chained (QEMU docs). PCRE2: pcre2_jit_compile on demand (docs).

Implementations

Sources

• John Aycock, A Brief History of Just-In-Time, ACM Computing Surveys 2003. paper
• Arnold, Fink, Grove, Hind, Sweeney, A Survey of Adaptive Optimization in Virtual Machines, Proceedings of the IEEE 2005. paper
• Bolz, Cuni, Fijalkowski, Rigo, Tracing the Meta-Level: PyPy's Tracing JIT Compiler, ICOOOLPS 2009. paper
• OpenJDK, compiler_globals.hpp, compilerDefinitions.cpp. code
• LuaJIT, lj_jit.h. code
• PostgreSQL docs, When to JIT? docs
• V8 team, Maglev, 2023. post · Sparkplug, 2021. post
• WebKit, Introducing the WebKit FTL JIT. post · Mozilla Hacks, The Baseline Interpreter, 2019. post
• QEMU, Translator Internals. docs · Linux kernel, net sysctl bpf_jit_enable. docs · PCRE2, pcre2jit. docs