# 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:

```c
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.