Tiered Compilation and Deoptimization: Undoing a Speculation

A runtime that compiles a dynamically typed function has to guess. It cannot prove that a variable holds an integer; it can only observe that it did the last thousand times and generate code that assumes it will again. The guess is worth making because the code it produces drops the per-operation type tests that the general path performs on every execution, and because it lets the compiler inline calls that the general path has to dispatch. The machinery that makes the guess safe is deoptimization: when an assumption fails, execution is transferred back to a state the interpreter can resume from, with the program’s observable state reconstructed exactly as if the optimized code had never run.

Two axes of tiering

The first axis is how much work the compiler does. An interpreter executes bytecode directly; a baseline compiler translates it to machine code with little optimization; an optimizing compiler performs inlining, type specialization, and escape analysis. Each tier costs compile time and buys run-time speed, so the choice depends on how many times the code will run.

The second axis is what the compiler assumes. A baseline compiler can assume only what the bytecode guarantees, which for a dynamic language is very little. An optimizing compiler assumes the types and shapes it has observed, which requires guards and therefore requires a way to undo them.

The two axes are usually coupled: the optimizing tier is where speculation pays off, because speculation enables inlining, and inlining is the optimization that matters most. A call that cannot be inlined because the target is unknown at compile time costs a call, a frame, and the loss of every optimization that would have crossed it. Once the compiler knows the target, it can inline, and the inlined body’s type checks become the caller’s type checks, which are hoisted out of loops.

When to compile

The trigger is a counter. A function’s entry count, or its back-edge count for loops, increments as it executes, and crossing a threshold queues it for compilation. The threshold is a policy decision with no universally right value: too low and the runtime spends compile time on code that runs once; too high and hot code runs in the slow tier for too long.

Interpreters can afford a low threshold because their counters are cheap. Implementations that keep the counter in the function object rather than in a register pay a load and an increment per call, which is negligible next to the call itself. The interesting case is a loop whose body is hot but whose enclosing function is called once: the entry counter never fires, so the compiler must also count loop iterations. That is what back-edge counters are for, and it is why a compiler that only counts calls will leave a long-running loop in the interpreter.

A second trigger is on-stack replacement. A function that has been running for a long time in the interpreter, typically because it contains an outer loop, can be compiled while it is executing, and the running activation can be transferred into the compiled version mid-loop. That requires mapping the interpreter’s state onto the compiled frame’s state at the loop’s header, which is the same mapping deoptimization needs in reverse.

What a speculation record contains

When the optimizing compiler emits a guard, it records enough information to reconstruct the interpreter state if the guard fails. The record is keyed by the guard’s code offset and contains:

• The bytecode offset to resume at. This is the interpreter’s program counter after the guard.
• For each value live at that point, where the optimized code keeps it: a register, a stack slot, a constant, or a location derived from another value.
• The set of inlined frames that were active, with their method identities and bytecode offsets, so the interpreter can rebuild the logical call stack.

The reconstruction is a materialization problem. The optimized code may have kept a value in a register that the interpreter expects in a stack slot; the deoptimization code stores it. It may have eliminated a value entirely because it was a constant or because its computation was redundant; the code recomputes it or stores the constant. It may have kept two logical variables in one register because they were proven equal; the code writes the same value into both slots.

/* A guard on a speculative type, with a slow path that rebuilds interpreter state. */
if (value_tag(x) != TAG_INT) {
    /* Bail out: the recorded map says where each live value is. */
    deoptimize(frame, guard_id);      /* never returns; resumes in the interpreter */
}
long a = value_as_int(x);              /* unguarded from here on */

The record is per guard, and the number of guards in a compiled method can be large. Implementations compact them: guards that share a resume point share a record, and the per-guard data is an index into a table of records. The table is part of the compiled code’s metadata, and it must survive as long as the code can execute.

The deoptimization path

The mechanics are a small interpreter of their own. The runtime allocates interpreter frames for the logical stack the optimized code was standing in for, fills their slots from the recorded locations, and transfers control to the interpreter at the recorded bytecode offset. The optimized frame is discarded.

Three details make this harder than it sounds.

Locks and other side effects. If the optimized code acquired a monitor or registered a resource before the guard, the deoptimization must preserve the fact that the resource is held, or release it. A common design is to keep such state in the interpreter’s own structures rather than in the compiled frame, so that the transition does not need to move it.

Partial initialization. The optimized code may have written a value into an object before the guard failed, and the write is visible to the program after deoptimization. That is correct, since the optimized code executed it, but the interpreter’s view of the object must be consistent. If the optimized code wrote a value of a type the object’s shape does not allow, the shape transition must have been performed before the write, not after.

Recursion and the stack walk. Deoptimizing a frame that has inlined callees means materializing several interpreter frames at once. The stack walk that does this must respect the frame ordering, and the inlining tree must be walked from the innermost inlined frame outward, because the innermost frame’s bytecode offset is what determines where the outer frames resume.

The transition is also a safepoint. Since the runtime allocates frames during deoptimization, a collection can occur in the middle, and the collector must be able to walk the partially materialized stack. Implementations either forbid collection during the transition or make the transition’s intermediate states describable; the safepoint machinery is what makes the second possible. The rebuild itself resembles the frame materialization that exception unwinding performs when a compiled frame has to hand control to a handler, and most runtimes share the frame description format between the two.

Why the guard can be hoisted

The payoff of speculation is not that a guard is cheap; it is that a guard can be moved out of a loop. If a loop’s body adds two values, the general path checks both tags and the overflow condition on every iteration. The optimized path checks them once before the loop, then runs an unguarded add. The check’s cost per iteration drops to zero, and the loop’s body becomes a few instructions.

Hoisting requires the compiler to prove that the values do not change kind inside the loop. That proof comes from the loop’s own body: if nothing in the loop writes to the variables, their kinds are invariant, and a single check before the loop suffices. If something does write, the compiler can either re-check after the write or give up on hoisting. This is the same invariance reasoning that licenses loop-invariant code motion, applied to type tags rather than to computations.

The failure mode is a loop that is almost always integer and occasionally not. The guard passes, the loop runs fast, and then one iteration hits the slow path. The cost is the deoptimization itself plus the recompilation or re-entry cost, and if the pattern repeats, the code may oscillate between optimized and deoptimized states. Runtimes guard against this by tracking the number of deoptimizations per function and, after a threshold, compiling a version with less aggressive speculation or leaving the function in the interpreter permanently.

The cost of the metadata

Everything the deoptimizer needs must be available at run time, which means the compiled code carries a description of its own state. That description is large. A method with many guards, many inlined frames, and many live values has a metadata section that can rival the code’s size, and it must be resident while the code is live.

The size has consequences. It limits how much inlining is worthwhile, since each inlined frame adds records. It also affects the runtime’s memory accounting: a JIT-compiled method occupies code space, metadata space, and the object headers that let the runtime find both. Because the metadata is read only on the deoptimization path, a runtime can page it out or reclaim it when it decides the compiled code is no longer hot.

The trade is the same one that runs through the whole design. The interpreter needs no metadata because its state is its own data structures. The optimizing compiler needs a lot because it has compressed the state into registers and eliminated the structures the interpreter would have used. Tiering exists because neither extreme is right for all code, and the interesting engineering is in deciding where the boundary sits and how cheaply the state can be moved across it.