Meta-Tracing

Meta-tracing is a technique for automatically deriving JIT compilers from interpreters. Instead of tracing the guest program (Lua, Python), it traces the host interpreter (C, RPython) while executing the guest.

Tracing vs meta-tracing

A regular tracing JIT watches guest code and records operations:

OP_LOOKUP("x")
guard true, pop() > 0
OP_ADD

A meta-tracing JIT watches the interpreter and records host operations:

push(lookup("x")); pc++;
guard true, pop() > 0; pc++;
push(pop() + pop()); pc++;

The meta-trace captures what the C (or RPython) interpreter actually did — memory accesses, arithmetic, control flow. That trace is then optimized and compiled to machine code.

Why it works

The key insight: an interpreter is just a program. A trace of the interpreter running guest code contains everything needed to execute that guest code efficiently, without the interpretation overhead.

Meta-tracing naturally inlines across function boundaries. When the trace encounters push(val), it doesn't record "called push" — it records the body of push: the bounds check, the store, the pointer increment. Deep inlining happens automatically.

This is why meta-tracing can optimize code far beyond the interpreter's main loop. Helper functions, type checks, method lookups — all get inlined into a single optimized trace.

Linearization and guards

Traces linearize control flow. When the traced execution takes the true branch of an if, the trace only contains that branch. The trace inserts a guard at the branch point. If the guard later fails (the condition was false), execution deoptimizes back to the interpreter.

Guards are where traces pay for their simplicity. A trace that took the "happy path" will deoptimize every time execution diverges. Heavily branching code produces traces with many guards, reducing the benefit.

RPython and Truffle

The two main meta-tracing systems:

RPython (part of PyPy) — Write your interpreter in a restricted Python subset. RPython compiles it to C and adds meta-tracing. PyPy itself is a Python interpreter written in RPython. High performance, but requires a new interpreter.

Truffle (GraalVM) — Write your interpreter in Java with Truffle annotations. GraalVM partially evaluates it into optimized machine code. Uses a technique closer to partial evaluation than classical meta-tracing, but achieves similar results.

Both produce excellent JITs but require starting from scratch. You can't take the existing CPython or PUC Lua and add meta-tracing.

yk: meta-tracing for C

yk applies meta-tracing directly to C interpreters. It uses a modified LLVM (ykllvm) to instrument the interpreter with trace recording. Add ~400 lines to PUC Lua, get a JIT.

The advantage: full compatibility with reference implementations. The disadvantage: C's semantics make some optimizations harder than in RPython or Truffle.

See retrofitting-jit-c-interpreters for details on the implementation.