Tiered Compilation and On-Stack Replacement

A single compilation threshold forces a runtime into a bad bargain. Compile early with an optimizing compiler and every method pays a large fixed cost, most of it wasted on code that runs once. Compile late with a simple compiler and hot code runs slowly for a long time. Tiering escapes the bargain by compiling more than once, starting with something cheap and escalating as evidence accumulates. The cost of that arrangement is that code can be replaced while it is running.

The Ladder of Tiers

A typical three-tier ladder begins with an interpreter, moves to a fast non-optimizing compiler, and ends at an optimizing compiler with profiling-driven specialization.

The interpreter has no compilation cost and no warmup, but pays dispatch overhead on every bytecode, as described in interpreter dispatch overhead. The baseline compiler maps bytecodes to machine instructions with little analysis: it allocates registers by a simple scheme, keeps values in fixed frame slots, and emits a call for any operation it cannot express inline. Its output is typically several times faster than interpretation and costs on the order of tens of microseconds per method to produce. The optimizing compiler builds a full intermediate representation, performs inlining, escape analysis, loop transformations, and global register allocation, and can produce code another factor faster, at a cost that grows with method size and has to be amortized over many invocations.

Between the extremes, the interesting property is not the speed ratio but the ratio of speed to compile time. A baseline tier that gives most of the available speedup for a small fraction of the compile cost is what makes the ladder worthwhile. If the optimizing compiler were only slightly faster than baseline, the middle tier would be pointless; if baseline were nearly as slow as interpretation, the first rung would be pointless. The spread between tiers is what a tiered system is exploiting, and it exists because most of an interpreter’s overhead is structural, consisting of dispatch and memory-resident state, and is removed by any compiler, while the remaining optimizations deliver smaller increments.

Two additional tiers sometimes appear: a profiling tier that runs instrumented code purely to collect type and branch data, and a recompilation of already-optimized code with better profile data. Both are refinements of the same idea, that compilation decisions should be made on evidence gathered at the tier below.

Counters That Gate Promotion

Promotion is driven by the same counters that detect hot code, with different thresholds per tier. A method that overflows the interpreter’s entry counter is compiled at baseline; if it keeps accumulating count at baseline, it is queued for the optimizing compiler. The queue is drained by background compiler threads so that the program does not stall waiting for code generation.

The queue introduces a policy question the single-tier model did not have: what happens when the queue is full. A runtime can block the requesting thread, which preserves the property that hot code gets compiled promptly but stalls execution; it can drop the request, which risks leaving hot code at a low tier indefinitely; or it can prioritize, which requires an estimate of each request’s benefit. Real runtimes do some combination, often compiling on the requesting thread when the queue is saturated so that the cost is charged to the code that caused it.

A second question is whether to keep interpreting while compilation proceeds. Interpreting is the safe choice, since the compiled code may take a while and the interpreter can continue making progress. It also means the method’s counters keep incrementing during compilation, which is why the counter is reset at submission time rather than at completion.

Moving a Frame Mid-Loop

The hard part of tiering is not compiling twice; it is replacing code that is currently executing. A method called in a loop will eventually return, and its next invocation can enter compiled code with no special machinery. A method containing a long-running loop may not return for minutes, and waiting for it would forfeit most of the benefit of compiling it. The mechanism that avoids the wait is on-stack replacement: the runtime constructs a compiled version of the loop and transfers the live frame into it at the loop header.

The transfer must satisfy an invariant: the compiled code’s view of the frame at the loop header must equal the interpreted frame’s state at the same point. In the interpreter, locals live in an array and the operand stack lives in another array, both indexed and both potentially holding values the compiled code intends to keep in registers. The compiled code’s entry point at the loop header expects specific values in specific registers and stack slots. The runtime therefore needs a mapping from the interpreted frame layout to the compiled frame layout at that bytecode offset, and it needs that mapping to have been recorded by the compiler.

Compilers emit this mapping as part of the method’s metadata, one entry per point where execution can be transferred or where a guard can fail. Each entry lists, for every live value, whether it is in a register, a stack slot, or a constant, and where in the frame it lives. The same metadata serves deoptimization in the opposite direction, which is why deoptimization treats it as the central data structure of the whole system.

/* Transfer an interpreted frame into compiled code at a loop header.
   The compiler recorded, for this offset, where each local and stack slot lives. */
struct osr_entry {
    uint32_t bci;             /* bytecode index of the loop header */
    uint32_t nlocals;
    struct location locals[MAX_LOCALS];   /* REG(n) | SLOT(n) | CONST(v) */
    uint32_t stack_depth;
    struct location stack[MAX_STACK];
    void *code_entry;         /* compiled entry expecting this layout */
};

void osr_transfer(struct frame *f, const struct osr_entry *e) {
    struct compiled_frame *cf = push_compiled_frame(e->code_entry);
    for (uint32_t i = 0; i < e->nlocals; i++)
        write_location(cf, &e->locals[i], read_local(f, i));
    for (uint32_t i = 0; i < e->stack_depth; i++)
        write_location(cf, &e->stack[i], read_stack(f, i));
    pop_interpreted_frame(f);   /* the values now live in the compiled frame */
}

The code above omits the parts that make the operation delicate. Values held in registers at the transfer point must be spilled into the compiled frame before the jump, or the compiled prologue must be told to reload them. The interpreted frame may be referenced by an object that the compiled code can no longer see, requiring the runtime to either keep the interpreted frame alive or rewrite references. And the transfer point must be one where the two representations agree on the program counter, which is why OSR entry is placed at loop headers rather than at arbitrary bytecodes.

Why OSR Entries Are Loop Headers

A loop header dominates the loop body, so any iteration can be entered from the header without skipping work that a previous iteration performed. Transferring at a point inside the body would require replaying the partial iteration, and replaying is unsound when the iteration has already had side effects.

Placing the entry at the header also means the compiled code can be entered with the loop’s induction variables in whatever representation the compiled code chose. The compiler can specialize the loop’s trip count, unroll it, or vectorize it, provided the entry point reconstructs the state the vectorized prologue expects. In practice this means a compiled method may have several OSR entry points, one per loop, and each carries its own frame map.

A loop whose header is inside an inlined callee complicates matters: the frame being transferred belongs to the caller, but the loop lives in code the compiler inlined. The frame map must describe the caller’s state in terms the compiled code understands, including the values the inlined callee would have had in its own frame. Compilers handle this by treating inlined frames as part of the caller’s map, with a chain of virtual frame descriptions that deoptimization can materialize if needed.

Failure Modes of the Ladder

Tiered systems fail in ways a single-tier compiler cannot.

Compilation storms occur when a method is promoted, deoptimized, and promoted again in a cycle. Backoff on the promotion threshold bounds the work but does not eliminate the cycle; a method whose behaviour alternates between two profiles will keep moving up and down. Runtimes usually respond by capping the number of recompilations or by pinning the method at a tier where it is at least correct.

Queue latency is the second failure. A program that becomes hot all at once, such as a batch job that starts processing after a long idle period, can saturate the compiler queue with hundreds of methods. The compiled code arrives after the work that needed it. Runtimes mitigate this by prioritizing callers over callees, or by compiling at baseline first so that the interpreted path is short.

Warmup interacts badly with short-lived processes. A command-line tool that runs for a second spends most of that second in the interpreter or at baseline. Startup-time compilation of methods known to be hot, recorded from a previous run, is the usual answer, at the cost of a profile file that must be generated, stored, and invalidated when the code changes.

Finally, the tier boundary is visible in behaviour. A method that behaves differently under the optimizing compiler than under the interpreter is a compiler bug, and it tends to surface only after warmup, because the interpreted path runs first and the divergence needs the optimized version to be installed before it can appear. The assumptions that make the optimized version fast are the same assumptions that can make it wrong, which is why the guard machinery in speculative inlining and guard placement and the recovery path in deoptimization are the parts of the ladder where a mistake changes behaviour rather than only speed.