# Retrofitting JIT Compilers into C Interpreters

Laurence Tratt describes [[yk]], a system that automatically turns C interpreters into JIT-compiling VMs through [[meta-tracing]]. The pitch: add ~400 lines to PUC Lua or MicroPython, get ~2x geometric mean speedup while retaining full compatibility with the reference implementation.

## Why this matters

JIT compilers are expensive. HotSpot has consumed over 1,000 person-years. V8 has a large team working for many years. And JIT compilers tend to lag behind language specifications — changes in the language break assumptions embedded deep in the JIT. LuaJIT is stuck on 13-year-old Lua 5.1.

The alternative approaches (RPython, Truffle) produce excellent JITs but require writing a *new* interpreter. Users don't tolerate almost-compatible implementations.

yk fills a gap: derive a JIT from the C reference interpreter itself. Full compatibility is automatic because you're JIT-compiling the actual reference implementation.

## How meta-tracing works

A tracing JIT watches a *guest* program (Lua, Python) and records execution. A meta-tracing JIT watches the *host* interpreter (C) executing the guest program.

When the Lua interpreter runs:

```c
switch (GET_OPCODE(i)) {
  case OP_ADD: push(pop() + pop()); pc++; break;
  ...
}
```

The meta-tracer records not "OP_ADD happened" but the actual C operations: the memory loads, the addition, the stores. It then optimizes and compiles that trace to machine code.

The key advantage: meta-tracing naturally inlines across function boundaries. Rather than recording `push(...)`, it records the contents of `push`. This is what makes yk different from copy-and-patch approaches that only JIT the core interpreter loop.

## Implementation via ykllvm

yk uses a fork of LLVM that instruments the interpreter during compilation. It inserts `__yk_trace_basicblock(id)` calls at every control flow point, giving each basic block a unique ID. When a hot loop is detected, the system records which blocks execute.

The trace gets optimized and compiled to machine code. When the interpreter next reaches that loop, it hands execution to the JIT-compiled code.

## Three key optimizations

**Promotion** — The `yk_promote(val)` function tells the tracer "burn this runtime value into the trace as a constant." The trace then includes a guard that deoptimizes if the value changes. For interpreter dispatch, promoting the opcode removes the switch statement entirely.

**Idempotent functions** — Marking a function `yk_idempotent` tells the optimizer it's pure given the same inputs. This enables aggressive constant propagation. The paper claims 4x improvement just from marking opcode loading as idempotent, removing instruction decoding overhead.

**Backward code generation** — Adapted from LuaJIT. Generating machine code in reverse order produces better register allocation and implicitly eliminates dead code.

## Deoptimization

When a guard fails, execution must return to the interpreter. This requires reconstructing the interpreter's stack frame and register state at the guard point — jumping from JIT-compiled code back into the middle of an AOT-compiled function.

yk extends LLVM's stackmap mechanism for this. It uses shadow stacks to maintain the information needed to reconstruct interpreter state at any guard.

## The trade-off

yklua reaches ~2x geometric mean on benchmarks, some up to 4-6x. That's less than hand-optimized LuaJIT's peak. But yklua upgraded from Lua 5.4.6 to 5.5.0 in under two hours. LuaJIT would need months.

The design space yk occupies: you sacrifice peak performance for trivial version tracking and complete compatibility.

## Current status

Alpha-stage software, funded by Shopify and the Royal Academy of Engineering. x64 only. Missing optimizations. You can hit TODOs that halt execution. But it works well enough to see meaningful speedups on real programs.

Projects: [[yk]] (core), yklua (Lua), ykmicropython (MicroPython), ykllvm (LLVM fork).