Just-In-Time Compilation

Just-In-Time compilation is the run-time translation of interpreted bytecode (or an intermediate representation) into native machine code, performed selectively and adaptively based on observed execution behavior, rather than exhaustively ahead of time. The defining property is adaptivity: the compiler's decisions — what to compile, how aggressively to optimize, what to inline, what types to specialize for — are driven by profiling data gathered while the program itself is running. Three ideas make this tractable. First, hot-spot detection: most programs obey a heavy-tailed execution distribution where a small fraction of code (loops, frequently-called methods) accounts for almost all execution time; compiling everything wastes effort compiling code that runs once. Second, tiering: rather than one compiler, runtimes chain multiple execution strategies — an interpreter, a fast/unoptimized JIT ("baseline" or "C1"-style compiler), and a slow/highly optimizing JIT ("C2"/"TurboFan"/"Ignition+TurboFan"-style) — promoting a method upward as evidence accumulates that the extra compile cost will pay off. Third, speculation with deoptimization: an optimizing JIT can assume facts that are usually true (a call site always sees one concrete type, an array bound is never violated, a branch is never taken) and compile fast code under that assumption, guarded by a cheap runtime check; if the assumption ever fails, execution safely reverts — deoptimizes — to unoptimized code or the interpreter. These mechanisms sit directly on top of the Interpreters versus Compilers distinction: a JIT is not "a compiler instead of an interpreter" but a system that starts as an interpreter and escalates to compilation only where profiling justifies it. The optimizing tier typically compiles through an SSA-based intermediate representation — see Static Single Assignment (SSA) Form — because SSA's single-definition property makes type specialization, constant propagation, and inlining decisions compositional and easy to verify. Loop-heavy hot methods are where classical Loop Optimizations and Loop-Invariant Code Motion pay off most, since loops are exactly the code shape that hot-spot detection is built to find.

A tiered JIT runtime is best understood as a state machine attached to every method (or loop), driven by counters, with compilation happening on background threads so the interpreter never stalls waiting for a compile to finish.

Step 1 — Interpretation with counting. Every method begins execution in the interpreter (or the lowest tier). The interpreter increments an invocation counter each time the method is called, and a separate back-edge counter each time a loop's back edge is taken (loops can become hot without the enclosing method being called often).

Step 2 — Threshold crossing triggers compilation. When a counter crosses a threshold, the runtime enqueues a compilation request for that method at the next tier, but keeps interpreting it in the meantime — compilation happens asynchronously.

Step 3 — Baseline (Tier 1) compilation. A fast, mostly non-optimizing compiler produces machine code quickly (compiling in milliseconds), often doing little more than templated code generation with type feedback recording (inline caches). This code is not fast in the "optimizing compiler" sense, but it is far faster than tree-walking or bytecode dispatch.

Step 4 — Profiling continues in Tier 1. The baseline-compiled code itself gathers richer profile data: which concrete types appear at polymorphic call sites, which branches are taken, which methods called from here are themselves hot. This is stored as type feedback / inline caches.

Step 5 — Promotion to the optimizing tier. When a method's counters cross a second, higher threshold, the accumulated profile is handed to the optimizing compiler, which builds an SSA-form IR, and applies aggressive, speculative optimizations: type specialization, inlining guided by observed call targets, loop-invariant code motion, bounds-check elimination, escape analysis.

Step 6 — Guards and speculation. Every speculative optimization inserts a cheap runtime guard: e.g., "check that the object at this call site still has hidden-class C" before running specialized code that assumes it. If a guard fails, control transfers to a deoptimization stub.

Step 7 — On-Stack Replacement (OSR). A long-running loop inside an interpreted method may become hot before the method itself is called again — waiting for the next call to install compiled code would waste the rest of this execution. OSR compiles just that loop and transplants the interpreter's live state (locals, stack) into the equivalent compiled-code frame while the loop is running, resuming execution in native code without restarting the method.

Step 8 — Deoptimization. If a guard fails (a call site starts seeing a second type, an assumed-non-null value is null, an inlined method is overridden by newly loaded code), the runtime cannot simply "jump back" — the optimized frame's layout differs from the interpreter's. Instead it reconstructs an equivalent interpreter frame from safepoint metadata recorded at compile time, discards the optimized code (or marks it for recompilation with updated assumptions), and resumes in the interpreter or a lower tier. ``` // Simplified tiered JIT driver, one instance per compiled method M state(M) = INTERPRETED invocationCount(M) = 0 backEdgeCount(M) = 0 function onMethodEntry(M): if state(M) == INTERPRETED: invocationCount(M) += 1 if invocationCount(M) >= T1_THRESHOLD: enqueueCompilation(M, tier = BASELINE) // async, background thread interpretBytecode(M) function onBackEdge(M, loopHeader): backEdgeCount(M, loopHeader) += 1 if backEdgeCount(M, loopHeader) >= OSR_THRESHOLD and state(M) == INTERPRETED: code = compileLoopForOSR(M, loopHeader, profile(M)) // compile just this loop frame = transplantInterpreterFrame(currentFrame(), code) transferControl(frame) // resume in native code, mid-loop function onBaselineExecute(M): invocationCount(M) += 1 recordTypeFeedback(M) // inline-cache style: which types/targets seen if invocationCount(M) >= T2_THRESHOLD: enqueueCompilation(M, tier = OPTIMIZING) function optimizingCompile(M, profile): ir = buildSSA(bytecodeOf(M)) ir = specializeTypes(ir, profile.observedTypes) // insert type guards ir = inlineHotCallees(ir, profile.callTargets) // insert inlining guards ir = loopInvariantCodeMotion(ir) ir = boundsCheckElimination(ir) ir = escapeAnalysis(ir) // stack-allocate non-escaping objects code = codegen(ir, recordSafepoints = true) // safepoints enable deopt installCode(M, code) state(M) = OPTIMIZED function onGuardFailure(M, pc, liveState): frame = reconstructInterpreterFrame(M, pc, liveState, safepointMap(M, pc)) invalidate(compiledCodeOf(M)) updateProfile(M, observedFailureReason) state(M) = BASELINE // or INTERPRETED, depending on policy resumeInterpreter(frame) ```

Compilation cost per method. Baseline compilation is designed to run in time roughly linear in bytecode size, $O(n)$ for $n$ bytecode instructions, with a small constant factor, because it performs no global data-flow analysis — it emits templated machine code per bytecode with light peephole cleanup. Optimizing compilation is asymptotically more expensive: building SSA form and running classical data-flow optimizations (LICM, global value numbering, escape analysis) typically costs $O(n \log n)$ to $O(n^2)$ in practice depending on the analyses used (dominator-tree construction for SSA is near-linear via the Lengauer–Tarjan algorithm; some optimizations like alias analysis can be superlinear). This cost is paid once per hot method, amortized over however many times that method subsequently executes — the entire economic argument for JIT compilation rests on this amortization.

Why tiering is asymptotically the right trade. Suppose a method runs $k$ times. Pure interpretation costs $k \cdot c_{\text{interp}}$ where $c_{\text{interp}}$ is the (large) per-execution interpretive overhead. Compiling immediately costs $c_{\text{compile}} + k \cdot c_{\text{native}}$ where $c_{\text{native}} \ll c_{\text{interp}}$ but $c_{\text{compile}}$ is large for an optimizing compiler. Tiering approximates the decision "compile only if $k$ is large enough that $c_{\text{compile}} < k(c_{\text{interp}} - c_{\text{native}})$" without knowing $k$ in advance, by using observed counts as an online estimator of $k$. The threshold-crossing rule is a simple but effective proxy: a method that has already run $T$ times is, empirically (heavy-tailed execution distributions), overwhelmingly likely to run many more times, so the expected future benefit exceeds the compile cost. This is a heuristic, not a proof of optimality — pathological programs that run exactly $T$ times and then stop pay pure overhead — but it is correct in expectation for realistic workloads, which is the standard the whole field is judged against.

Correctness of speculative optimization. The crux is that speculation must never produce a wrong answer, only occasionally a slower one. This is guaranteed structurally: every optimization that relies on an unproven fact $\phi$ (a type, a non-null check, a lack of aliasing, a monomorphic call target) is compiled as

placed before any code that depends on $\phi$, and the compiler records enough metadata at that program point (a safepoint: mapping from optimized-code registers/stack slots back to interpreter locals) to reconstruct an equivalent unoptimized state. The invariant maintained is: at every guard, the reconstructed interpreter state is semantically equivalent to what the interpreter's state would have been had it executed up to that point — this is what makes deoptimization observably transparent; the program's semantics under a JIT are identical to the program's semantics under pure interpretation, only the performance differs. Proving this invariant is exactly why compiler writers build optimizing tiers on SSA form (per Static Single Assignment (SSA) Form): SSA's explicit def-use chains make it tractable to compute, for any program point, which interpreter variable each optimized value corresponds to.

On-Stack Replacement correctness. OSR is trickier because it swaps execution strategy mid-loop, not at a method boundary. Correctness requires the compiled loop code to accept an entry state matching any valid loop-header state reachable from the interpreter (not just from the loop's natural start), which is why OSR-compiled code is generated with a dedicated OSR entry point that reads all live locals from the interpreter frame layout, rather than assuming values live in specific registers already.

Honest tradeoffs. JIT compilation trades peak-throughput determinism for adaptivity: warm-up time (the interval before hot methods are optimized) is real overhead absent from AOT-compiled code, which is why short-lived scripts and CLI tools often prefer interpreters or AOT compilation (see Interpreters versus Compilers). Speculative deoptimization also means worst-case latency is not fully predictable — a guard failure at an inopportune moment causes a stall while reconstructing frames and possibly recompiling, which matters for hard real-time systems (this is a major reason JVMs are avoided in latency-critical embedded control loops). Memory overhead is also nontrivial: profiling counters, inline-cache metadata, and multiple compiled versions of hot methods all consume space the interpreter alone would not need.

Consider this JavaScript-like hot loop, executed inside a V8-style engine: ``` function sum(arr) { let total = 0; for (let i = 0; i < arr.length; i++) { total += arr[i]; } return total; } // called in a loop 10,000,000 times with arr = [Int32, Int32, ...] ``` Trace through the tiers:

The key lesson: the optimizing compiler never proved `arr` is always `Int32` — it observed this in 9,000 prior calls and bet on it, protected by a single guard so cheap it is invisible next to the speedup from eliminating property lookups and bounds checks on every element. If the bet is wrong even once, correctness is preserved by falling back, not by crashing or returning a wrong sum.

The idea of compiling at run time rather than ahead of time predates modern dynamic languages by decades, originating in work on adaptive execution of Smalltalk and Self, then reaching mass deployment through the Java Virtual Machine's HotSpot compiler and later through JavaScript engines competing for browser performance.

Tiered JIT compilation with speculative optimization is the execution engine behind essentially every mainstream managed-language runtime in production today. The HotSpot JVM (Java, Kotlin, Scala) uses exactly this client/server (C1/C2) tiered scheme, with C2 performing SSA-based optimization and OSR for loop-heavy numerical code. V8 (Chrome, Node.js, Electron apps) uses Ignition as its interpreter/baseline tier and TurboFan as its SSA-based optimizing compiler, with hidden classes standing in for the "type" concept in inline caches. .NET's CLR uses RyuJIT with tiered compilation (a quick Tier 0 pass followed by a fully-optimizing Tier 1). PyPy applies tracing-JIT variants of these ideas to Python, and LuaJIT does the same for Lua. Mobile platforms use JIT-adjacent hybrid strategies: Android's ART historically combined AOT compilation at install time with a JIT for methods whose behavior AOT profiling could not predict, later feeding JIT-collected profiles back into subsequent AOT recompilation. Databases and query engines (e.g., PostgreSQL's JIT via LLVM, Apache Spark's Tungsten) JIT-compile query plans once the query shape and data statistics are known, applying the same speculate-and-guard philosophy to SQL execution rather than general-purpose bytecode.

Ask the tutor: How would you extend a tiered JIT's threshold logic to avoid bailout thrashing on a megamorphic call site?