Lesson 0.3 — Compilation strategies: AOT, JITs, transpilers and partial evaluation¶

Techniques: AOT compilation, method JITs, tracing JITs, tiered compilation, transpilers, partial evaluation (Futamura projections) · Pebble uses: AOT (pebblec → object file → executable) · Lab: the JIT engine of labs/ch00-exec (LLVM IR + ORC LLJIT) against the interpreters of Lesson 0.2 · Prerequisites: Lesson 0.1, Lesson 0.2 · Time: 5–7 hours

Lesson 0.2's benchmark ended with this row: the lab's JIT spends 9.6 ms compiling bench-collatz and then runs it 62 times faster than the tree walker. Whether that trade is worth it depends on how often the code runs, which the compiler may not know in advance. This lesson covers when translation to machine code happens: before the program runs (AOT), while it runs, one method at a time or one hot path at a time (JITs), in several stages of increasing effort (tiers), into another high-level language (transpilers) — and the theory that connects interpreters and compilers (partial evaluation).

1. Problem and motivation¶

The problem. A program \(p\) will be run on inputs that arrive over time. Choose when and how much to compile each part of \(p\) so that total time — translation plus execution — is small, and the observed behavior is still \(\mathrm{Beh}(p)\) (Definition 0.1.4).

AOT compilation¶

Ahead-of-time compilation translates the whole program before any input is seen: FORTRAN I did it in 1957 [BBB+57], and C, C++, Rust, Swift, Go and Pebble still do. All compile time is paid once, by the developer, and the optimizer may spend minutes. What AOT lacks is run-time information (which branches are hot, what types flow where); profile-guided optimization recovers part of it by compiling twice around a training run [PH90].

Method JITs¶

A just-in-time compiler translates code while the program runs [Ayc03]. The method JIT translates one function at a time, typically when it is first called or has been called often. Deutsch and Schiffman's Smalltalk-80 implementation (1984) compiled methods to native code on first use and introduced inline caches [DS84]; the JVM, .NET and JavaScript engines followed. A method JIT sees the actual run-time types and values, but must pay its compile time while the user waits.

Tracing JITs¶

A tracing JIT compiles paths, not functions: it records the operations the interpreter executes along one hot loop iteration, including calls it inlines on the way, and compiles that straight-line trace with guards that exit back to the interpreter when execution leaves the recorded path. Dynamo did this for machine code (2000) [BDB00]; TraceMonkey brought it to JavaScript [Gal+09]; LuaJIT is the best-known production tracing JIT; PyPy traces the interpreter of the language rather than the program (meta-tracing) [BCFR09].

Tiered compilation¶

Tiered systems combine several strategies for one function over time: interpret first (cheap to start, collects profiles), then a fast baseline compiler, then an optimizing compiler that speculates on the profile, with deoptimization back to a lower tier when a speculation fails. Self pioneered adaptive optimization with type feedback and deoptimization [HCU92, HU94]; HotSpot has tiers 0–4 (interpreter, C1, C2) [PVC01, KWM+08, HS-Tiered]; V8 has Ignition → Sparkplug → Maglev → TurboFan [V8-Sparkplug, V8-Maglev].

Transpilers¶

A transpiler (source-to-source compiler) targets another high-level language instead of machine code: Cfront translated C++ to C, the TypeScript compiler translates TypeScript to JavaScript [TS-Handbook], Nim and Chicken Scheme emit C, Emscripten turned LLVM IR into JavaScript [Zak11]. The target language's compiler does the rest, so a transpiler gets portability and a mature back end for the price of one extra pipeline stage.

Partial evaluation and the Futamura projections¶

Futamura observed in 1971 that an interpreter and a compiler are related by specialization: fixing an interpreter's program input and simplifying yields compiled code [Fut71]. A partial evaluator (mix) does that specialization automatically. The three Futamura projections turn this into compilers and compiler generators. The idea became practical decades later: PyPy's meta-tracing JIT and GraalVM's Truffle derive a JIT compiler from an interpreter [BCFR09, WWH+17], and LLVM's ordinary optimizer performs the first projection on a small interpreter (box below).

2. Definitions and algorithms¶

Definition 0.3.1 (Interpreter, compiler, specializer as programs)

Write \([\![q]\!]\) for the input–output function of a program \(q\) (a partial function; for Tiny, the value of Definition 0.2.2). A program \(\mathit{int}\) is an interpreter for \(L\) if \([\![\mathit{int}]\!]\,(p, d) = [\![p]\!]_L(d)\) for all \(p \in L\) and inputs \(d\). A program \(\mathit{comp}\) is a compiler from \(L\) to \(T\) if \([\![\, [\![\mathit{comp}]\!]\,(p) \,]\!]_T(d) = [\![p]\!]_L(d)\) (the deterministic special case of Definition 0.1.4). A program \(\mathit{mix}\) is a specializer (partial evaluator) if

\[ [\![\, [\![\mathit{mix}]\!]\,(q, s) \,]\!]\,(d) = [\![q]\!]\,(s, d) \quad \text{for all programs } q \text{ and inputs } s, d. \]

(\(s\) is the static input, known at specialization time; \(d\) the dynamic one.)

AOT compilation¶

AOT is the pipeline of Lesson 0.1 run once, before the first input; its one algorithmic addition is profile guidance.

Algorithm 0.3.2 (Profile-guided AOT compilation)

Input: a program \(p\); a set of training inputs \(D_{\mathrm{train}}\).
Output: an executable \(x\) optimized for the behavior observed on \(D_{\mathrm{train}}\).
Precondition: the instrumented and the final build see the same source; the training inputs are representative (otherwise the result is still correct, only slower).
Postcondition: \(x \preceq p\) (correctness does not depend on the profile).
Invariant: the profile influences only choices between correct translations (layout, inlining, unrolling), never the set of behaviors.

function PGO(p, D_train):
    x_instr ← Compile(p, instrument = true)          # counters on edges/blocks/calls
    for d in D_train: run x_instr on d               # writes raw profiles
    prof ← MergeProfiles(raw profiles)                # llvm-profdata merge
    return Compile(p, profile = prof)                 # hot/cold layout, inlining, ...

AOT with and without optimization: clang -O0 vs -O2

Reproduce (clang 23.1.2; sum.c from Lesson 0.1):

clang-23 --target=x86_64-linux-gnu -O0 -fno-discard-value-names -S -emit-llvm sum.c -o sum-O0.ll
clang-23 --target=x86_64-linux-gnu -O2 -fno-discard-value-names -S -emit-llvm sum.c -o sum-O2.ll
sed -n '/^define/,/^}/p' sum-O0.ll sum-O2.ll

Output (complete):

define dso_local i32 @sum(i32 noundef %n) #0 {
entry:
  %n.addr = alloca i32, align 4
  %s = alloca i32, align 4
  %i = alloca i32, align 4
  store i32 %n, ptr %n.addr, align 4
  store i32 0, ptr %s, align 4
  store i32 0, ptr %i, align 4
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry
  %0 = load i32, ptr %i, align 4
  %1 = load i32, ptr %n.addr, align 4
  %cmp = icmp slt i32 %0, %1
  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond
  %2 = load i32, ptr %i, align 4
  %3 = load i32, ptr %s, align 4
  %add = add nsw i32 %3, %2
  store i32 %add, ptr %s, align 4
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %4 = load i32, ptr %i, align 4
  %inc = add nsw i32 %4, 1
  store i32 %inc, ptr %i, align 4
  br label %for.cond, !llvm.loop !5

for.end:                                          ; preds = %for.cond
  %5 = load i32, ptr %s, align 4
  ret i32 %5
}
define dso_local i32 @sum(i32 noundef %n) local_unnamed_addr #0 {
entry:
  %cmp4 = icmp sgt i32 %n, 0
  br i1 %cmp4, label %for.body.preheader, label %for.cond.cleanup

for.body.preheader:                               ; preds = %entry
  %0 = add nsw i32 %n, -1
  %1 = zext nneg i32 %0 to i33
  %2 = add nsw i32 %n, -2
  %3 = zext i32 %2 to i33
  %4 = mul i33 %1, %3
  %5 = lshr i33 %4, 1
  %6 = trunc nuw i33 %5 to i32
  %7 = add i32 %n, %6
  %8 = add i32 %7, -1
  br label %for.cond.cleanup

for.cond.cleanup:                                 ; preds = %for.body.preheader, %entry
  %s.0.lcssa = phi i32 [ 0, %entry ], [ %8, %for.body.preheader ]
  ret i32 %s.0.lcssa
}

What to notice: at -O0 every variable is an alloca loaded and stored around each use (the front end's straightforward translation). At -O2 the loop is gone: scalar evolution recognized \(s = \sum_{i=0}^{n-1} i\) and emitted a closed form, computed in 33-bit arithmetic so that \((n-1)(n-2)\) cannot overflow; \(n + (n-1)(n-2)/2 - 1 = n(n-1)/2\). An AOT compiler can afford analyses like this because it runs once, before the program.

Method JITs¶

Algorithm 0.3.3 (Counter-triggered method JIT)

Input: a program whose functions start in an interpreter; a threshold \(k\); a compiler \(C\) from functions to machine code.
Output: the program's behavior, with hot functions executed as machine code.
Precondition: \(C\) is correct (Definition 0.1.4) for each function in isolation; functions are entered only through the call path below.
Postcondition: every call returns what the interpreter would have returned (Theorem 0.3.11).
Invariant: code[f] is either empty or \(C(f)\); each function is compiled at most once.

function Call(f, args):
    if code[f] ≠ empty: return code[f](args)          # native entry
    count[f] ← count[f] + 1
    if count[f] ≥ k:
        code[f] ← C(f)                                # the lab's prepare() for JIT
        return code[f](args)
    return Interpret(f, args)

V8 compiles a hot method with TurboFan

Reproduce (Node.js 22.22.2, V8 12.4.254.21; addresses and timings masked):

cat > tiers.js <<'EOF'
function sum(n) {
  let s = 0;
  for (let i = 0; i < n; i++) s += i;
  return s;
}
let t = 0;
for (let k = 0; k < 200000; k++) t += sum(10);
console.log(t);
EOF
node --trace-opt tiers.js 2>&1 | sed -E 's/0x[0-9a-f]+/0x…/g; s/took [0-9., ]+ms/took … ms/' | grep 'JSFunction sum'

Output (complete):

[marking 0x… <JSFunction sum (sfi = 0x…)> for optimization to TURBOFAN, ConcurrencyMode::kConcurrent, reason: hot and stable]
[compiling method 0x… <JSFunction sum (sfi = 0x…)> (target TURBOFAN), mode: ConcurrencyMode::kConcurrent]
[completed compiling 0x… <JSFunction sum (sfi = 0x…)> (target TURBOFAN) - took … ms]
[completed optimizing 0x… <JSFunction sum (sfi = 0x…)> (target TURBOFAN)]

What to notice: the unit of compilation is the method sum, chosen because it became "hot and stable" (a counter plus stable type feedback, Algorithm 0.3.3's count[f] ≥ k). It is compiled concurrently on a background thread while the program keeps running in a lower tier — a way to hide JIT latency.

Tracing JITs¶

Definition 0.3.4 (Trace, guard, side exit)

A trace is a straight-line sequence of IR operations recorded while the interpreter executes one path through a loop, starting and ending at the loop header. Every run-time check the interpreter made on that path (a branch direction, a type test, a bounds check) becomes a guard \(g\): an operation that continues when the recorded condition holds and otherwise leaves the trace through a side exit, which restores the interpreter state (the values of all live variables) at that point and resumes interpretation there.

Algorithm 0.3.5 (Trace recording and execution)

Input: an interpreter with loop headers marked; a hotness threshold \(h\).
Output: the program's behavior, with hot loop paths executed as compiled traces.
Precondition: the recorder captures every value and condition an operation depends on (as guards); the trace compiler is correct for straight-line code with guards.
Postcondition: execution produces the interpreter's behavior (Theorem 0.3.12).
Invariant: at every guard, the side-exit map describes how to rebuild the full interpreter state from the trace's registers.

function AtLoopHeader(pc, state):
    if trace[pc] exists:
        state, exit_pc ← RunTrace(trace[pc], state)     # loops until a guard fails
        return Interpret from exit_pc with state
    hot[pc] ← hot[pc] + 1
    if hot[pc] ≥ h: start Record(pc)                    # the next iteration is recorded

function Record(pc):                                    # interpreter runs, recorder listens
    ops ← []
    repeat:
        execute one instruction; append its operation to ops
        for each check the instruction made: append Guard(condition, exit map)
        if a call: inline the callee's operations (keep recording)
        if back at pc: trace[pc] ← Compile(Optimize(ops) + loop back); return
        if the trace grows too long or leaves the loop: abort recording

A LuaJIT trace: guards, a loop, and phis

Reproduce (LuaJIT 2.1 from Ubuntu 24.04 apt-get install luajit, 2.1.1703358377):

cat > sum.lua <<'EOF'
local function sum(n)
  local s = 0
  for i = 0, n - 1 do s = s + i end
  return s
end
print(sum(1000))
EOF
luajit -jdump=tbi sum.lua

Output (complete):

---- TRACE 1 start sum.lua:3
0006  ADDVV    1   1   5
0007  FORL     2 => 0006
---- TRACE 1 IR
0001 >  int SLOAD  #5    CRI
0002 >  int LE     0001  +2147483646
0003    int SLOAD  #4    CI
0004 >  num SLOAD  #3    T
0005    num CONV   0003  num.int
0006  + num ADD    0005  0004
0007  + int ADD    0003  +1  
0008 >  int LE     0007  0001
0009 ------ LOOP ------------
0010    num CONV   0007  num.int
0011  + num ADD    0010  0006
0012  + int ADD    0007  +1  
0013 >  int LE     0012  0001
0014    int PHI    0007  0012
0015    num PHI    0006  0011
---- TRACE 1 stop -> loop

499500

What to notice: the trace starts at the loop (sum.lua:3), not at the function: only the two bytecodes of the hot path were recorded (ADDVV, FORL). Lines marked > are guards (Definition 0.3.4): the loop bound is an integer, s is a number (T = type check). LuaJIT peels one iteration (0001–0008), so the loop proper (after LOOP) needs only one guard, the exit test 0013; the PHIs are the loop-carried values, as in SSA (Ch 16).

Tiered compilation¶

Definition 0.3.6 (Tiers, speculation, deoptimization, OSR)

A tiered system executes each function \(f\) with one of \(\tau_0, \dots, \tau_m\) (interpreter, baseline compiler, optimizing compilers), moving \(f\) up when its counters and profile say so. An optimizing tier speculates: it compiles \(f\) under assumptions \(A\) taken from the profile (types, never-taken branches, a call target) and guards each assumption. Deoptimization is the transfer, when a guard fails, from the optimized frame to an equivalent frame of a lower tier, using metadata that maps optimized state (registers, stack slots) back to the lower tier's state at the same program point. On-stack replacement (OSR) is the opposite transfer, into optimized code in the middle of a running loop.

Algorithm 0.3.7 (Tiered execution with speculation and deoptimization)

Input: function \(f\); tiers \(\tau_0\) (interpreter, profiling) … \(\tau_m\); thresholds \(k_1 < \dots < k_m\).
Output: \(f\)'s results.
Precondition: each tier's code for \(f\) refines \(f\) under its assumptions \(A_j\); every assumption is guarded; deoptimization metadata is exact.
Postcondition: every call returns what \(\tau_0\) would return (Theorem 0.3.13).
Invariant: the tier currently installed for \(f\) is valid for all executions that pass its guards.

function Invoke(f, args):
    j ← tier[f]
    result, deopt ← Run(code_j[f], args)                  # may exit at a failed guard
    if deopt ≠ none:
        frame ← Reconstruct(deopt.metadata, deopt.state)  # rebuild τ0's frame
        invalidate code_j[f]; tier[f] ← 0; update profile with the new fact
        result ← ResumeInterpreter(frame)                  # continue, not restart
    counter[f] ← counter[f] + 1
    if tier[f] < m and counter[f] ≥ k_{tier[f]+1}:
        code_{tier[f]+1}[f] ← Compile_{tier[f]+1}(f, assumptions from profile)
        tier[f] ← tier[f] + 1                               # possibly in the background
    return result

HotSpot's tiers: C1 at level 3, C2 at level 4, OSR, deoptimization

Reproduce (OpenJDK 21.0.10; Sum.java from Lesson 0.2's JVM box):

javac Sum.java
java -XX:+PrintCompilation Sum 2>&1 | grep 'Sum::'

Output (complete; the first column is milliseconds since start, and the order of concurrent compilations varies from run to run):

40    8       3       Sum::sum (21 bytes)
40    9       4       Sum::sum (21 bytes)
41    8       3       Sum::sum (21 bytes)   made not entrant
42   10 %     3       Sum::main @ 4 (33 bytes)
43   12 %     4       Sum::sum @ 4 (21 bytes)
44   10 %     3       Sum::main @ 4 (33 bytes)   made not entrant
44   11       3       Sum::main (33 bytes)
45   13 %     4       Sum::main @ 4 (33 bytes)
47   13 %     4       Sum::main @ 4 (33 bytes)   made not entrant

What to notice: the third column is the tier: sum is first compiled by C1 with profiling (level 3), then by C2 (level 4), and the level-3 code is "made not entrant" (no new calls enter it). % marks OSR compilations entered in the middle of the loop at bytecode index 4. "Made not entrant" means no new activation may enter that code: it happens when a better version replaces it (the level-3 sum) or after a deoptimization, when compiled code hits a path its speculation said would never run (an "uncommon trap", Definition 0.3.6). The log does not say which of the two retired main's last OSR code.

V8's tiers: Ignition, Sparkplug, TurboFan

Reproduce (Node.js 22.22.2, V8 12.4.254.21; tiers.js from the method-JIT box):

node --trace-opt --trace-baseline-batch-compilation tiers.js 2>&1 | sed -E 's/0x[0-9a-f]+/0x…/g; s/took [0-9., ]+ms/took … ms/' | grep -E 'SFI sum |JSFunction sum' | uniq | head -6
node --v8-options | grep -A1 -E '^\s+--(sparkplug|maglev) '

Output (complete):

[Baseline batch compilation] Enqueued SFI sum with estimated size 224 (current budget: 1337/4096)
[Baseline batch compilation] Enqueued SFI sum with estimated size 224 (current budget: 1974/4096)
[marking 0x… <JSFunction sum (sfi = 0x…)> for optimization to TURBOFAN, ConcurrencyMode::kConcurrent, reason: hot and stable]
[compiling method 0x… <JSFunction sum (sfi = 0x…)> (target TURBOFAN), mode: ConcurrencyMode::kConcurrent]
[Baseline batch compilation] Enqueued SFI sum with estimated size 224 (current budget: 2198/4096)
[Baseline batch compilation] Enqueued SFI sum with estimated size 224 (current budget: 2422/4096)
  --maglev (enable the maglev optimizing compiler)
        type: bool  default: --no-maglev
--
  --sparkplug (enable Sparkplug baseline compiler)
        type: bool  default: --sparkplug

What to notice: sum starts in Ignition (Lesson 0.2), is queued for the one-pass baseline compiler Sparkplug (batched to amortize the cost), and later compiled by TurboFan. The middle tier Maglev exists in this V8 but is off by default in Node 22 (--no-maglev); Chrome enables it [V8-Maglev]. Tiers are configuration, not architecture.

Transpilers¶

Definition 0.3.8 (Transpiler, desugaring)

A transpiler is a compiler (Definition 0.1.4) whose target \(T\) is a language meant to be compiled or interpreted further, typically human-readable. When \(T \subseteq L_S\) (a core subset of the source language, e.g. ES5 inside ES2022), it is a desugarer: a set of rewrite rules \(\ell \Rightarrow r\) where every \(r\) uses only core constructs.

Algorithm 0.3.9 (Downleveling by bottom-up desugaring)

Input: a syntax tree \(p\) of \(L_S\); rewrite rules \(R\) (e.g. let x ⇒ var x' with a fresh name when needed; (a) => e ⇒ function (a) { return e; } with this captured; class ⇒ constructor function + prototype assignments).
Output: a tree using only core constructs, printed as \(T\) source.
Precondition: each rule is semantics-preserving in every context; for every non-core construct some rule applies.
Postcondition: the output refines \(p\) and contains no non-core construct.
Invariant: after processing a subtree, that subtree contains only core constructs.

function Desugar(node):
    for child in children(node): child ← Desugar(child)     # bottom-up
    while node is not core:
        node ← apply the rule of R for node's construct (fresh names from a counter)
        for child in new children(node): child ← Desugar(child)
    return node

TypeScript: the same program for two targets

Reproduce (TypeScript 5.9.3 tsc, e.g. npm i typescript@5.9.3; Node.js 22.22.2. TypeScript 6 deprecates --target ES5 and rejects it with error TS5107 unless ignoreDeprecations is set):

cat > sum.ts <<'EOF'
const sum = (n: number): number => {
  let s = 0;
  for (let i = 0; i < n; i++) s += i;
  return s;
};
class Counter {
  private count = 0;
  tick(): number { return ++this.count; }
}
console.log(sum(10), new Counter().tick());
EOF
tsc --target ES5 sum.ts && cat sum.js && node sum.js
tsc --target ES2022 --outDir es2022 sum.ts && cat es2022/sum.js

Output (complete):

var sum = function (n) {
    var s = 0;
    for (var i = 0; i < n; i++)
        s += i;
    return s;
};
var Counter = /** @class */ (function () {
    function Counter() {
        this.count = 0;
    }
    Counter.prototype.tick = function () { return ++this.count; };
    return Counter;
}());
console.log(sum(10), new Counter().tick());
45 1
const sum = (n) => {
    let s = 0;
    for (let i = 0; i < n; i++)
        s += i;
    return s;
};
class Counter {
    count = 0;
    tick() { return ++this.count; }
}
console.log(sum(10), new Counter().tick());

What to notice: for ES2022 the transpiler only erases types (: number, private); for ES5 it also desugars (Algorithm 0.3.9): const/let → var, the arrow function → function, the class → a constructor function plus a prototype method. The type checker (the part of tsc that rejects programs) runs before either output exists.

Partial evaluation and the Futamura projections¶

Algorithm 0.3.10 (Online specialization of an interpreter to a static program)

Input: an interpreter interp(code, n, x) for straight-line stack code; the static code and n.
Output: a residual program target(x) with no dispatch on code.
Precondition: the interpreter's loop is bounded by static values (n), and every branch on the program depends only on static data.
Postcondition: \([\![\mathtt{target}]\!]\,(x) = [\![\mathtt{interp}]\!]\,(\mathtt{code}, n, x)\) for all \(x\) (Definition 0.3.1).
Invariant: the partial evaluator's environment maps each variable to a static value or a residual expression; static values are exact.

function Specialize(interp, code, n):
    env ← {code ↦ code, n ↦ n, x ↦ residual "x", stack ↦ [], sp ↦ 0}
    for pc in 0 .. n−1:                            # static loop: unrolled
        case code[pc].op of                        # static branch: decided now
            PUSH: push residual constant code[pc].imm
            ARG:  push residual "x"
            ADD:  b ← pop; a ← pop; push residual (a + b)   # folded if both static
            MUL:  b ← pop; a ← pop; push residual (a * b)
    return "target(x) = " + residual(top of stack)

clang -O2 performs the first Futamura projection

Reproduce (clang 23.1.2):

cat > mix.c <<'EOF'
/* An interpreter for a tiny stack language (straight-line programs, no jumps). */
enum Op { PUSH, ARG, ADD, MUL };
struct Ins { enum Op op; int imm; };

static int interp(const struct Ins *code, int n, int x) {
  int stack[8], sp = 0;
  for (int pc = 0; pc < n; pc++) {
    switch (code[pc].op) {
    case PUSH: stack[sp++] = code[pc].imm; break;
    case ARG:  stack[sp++] = x; break;
    case ADD:  sp--; stack[sp - 1] += stack[sp]; break;
    case MUL:  sp--; stack[sp - 1] *= stack[sp]; break;
    }
  }
  return stack[sp - 1];
}

/* The static input: the program x*x + 3*x + 1, as stack code. */
static const struct Ins prog[] = {{ARG, 0}, {ARG, 0}, {MUL, 0}, {PUSH, 3}, {ARG, 0},
                                  {MUL, 0}, {ADD, 0}, {PUSH, 1}, {ADD, 0}};

/* The interpreter specialized to prog: Futamura's first projection. */
int target(int x) { return interp(prog, 9, x); }
EOF
clang-23 --target=x86_64-linux-gnu -O2 -S -emit-llvm -fno-discard-value-names mix.c -o - | sed -n '/define.*@target/,/^}/p'

Output (complete):

define dso_local range(i32 -2147483647, -2147483648) i32 @target(i32 noundef %x) local_unnamed_addr #0 {
entry:
  %mul.5.i1 = add i32 %x, 3
  %add.6.i = mul i32 %mul.5.i1, %x
  %add.8.i = add nsw i32 %add.6.i, 1
  ret i32 %add.8.i
}

What to notice: the interpreter loop, the switch and the operand stack are gone. Inlining interp, fully unrolling the loop over the static prog (trip count 9) and folding the loads of the constant array is exactly Algorithm 0.3.10; instcombine then factored \(x^2 + 3x + 1\) into \(x(x + 3) + 1\). What is left is compiled code for prog: \(\mathit{target} = [\![\mathit{mix}]\!]\,(\mathit{interp}, \mathit{prog})\). The same experiment with a loop whose trip count is dynamic does not specialize — the precondition of Algorithm 0.3.10 matters.

3. Worked examples¶

Running example. A function executed \(N\) times, which costs \(r_i = 1\ \mu\mathrm{s}\) per call when interpreted and \(r_c = 0.05\ \mu\mathrm{s}\) compiled, and costs \(c = 1000\ \mu\mathrm{s}\) to compile (roughly the lab's numbers for a small loop: 9.6 ms compile, 60× faster code). The extra cost of an interpreted call is \(\Delta = r_i - r_c = 0.95\ \mu\mathrm{s}\).

AOT compilation¶

AOT pays \(c\) before the first call, whatever \(N\) is. Total time \(T_{\mathrm{AOT}}(N) = c + N r_c\):

\(N\)	\(T_{\mathrm{AOT}}\)	pure interpreter \(N r_i\)	winner
10	1 000.5 µs	10 µs	interpreter
1 000	1 050 µs	1 000 µs	interpreter (barely)
1 053	1 052.65 µs	1 053 µs	break-even: \(N^{*} = c / \Delta = 1052.6\)
100 000	6 000 µs	100 000 µs	AOT

With AOT the compile time is usually paid by the developer at build time, not by the user: the table describes the JIT's dilemma, where \(c\) is paid at run time.

Method JITs¶

Algorithm 0.3.3 with threshold \(k = \lceil c / \Delta \rceil = 1053\): the first 1052 calls are interpreted, call 1053 compiles.

\(N\)	JIT cost \(T_k(N) - N r_c\) (extra over ideal)	offline optimum \(\min(N\Delta, c)\)	ratio
10	9.5	9.5	1.00
1 052	999.4	999.4	1.00
1 053	999.4 + 1 000 = 1 999.4	1 000	2.00
100 000	1 999.4	1 000	2.00

The ratio never exceeds 2 (Theorem 0.3.14): the threshold policy is never more than twice as bad as an oracle that knew \(N\) in advance.

Tracing JITs¶

Recording (Algorithm 0.3.5) on the Tiny loop while i < 2 { s = s + i; i = i + 1; } with hotness threshold \(h = 1\): the header is reached at the start of iteration 1, so iteration 2 is recorded.

step	interpreter executes	recorder appends
1	`load i; push 2; lt` (1 < 2 → 1)	`t1 = lt i, 2`
2	`jz 17` falls through	`guard t1 ≠ 0` (exit map: pc 17, s, i)
3	`load s; load i; add; store s`	`s = add s, i`
4	`load i; push 1; add; store i`	`i = add i, 1`
5	`jmp 4` — back at the header	close the loop: jump to step 1

The compiled trace is 3 operations, 1 guard and the loop-back jump per iteration instead of 13 dispatched instructions. On the next header visit (\(i = 2\)) the trace runs, the guard fails, and the side exit resumes the interpreter at pc 17 with \(s = 1\), \(i = 2\).

Tiered compilation¶

HotSpot's output above, read as Algorithm 0.3.7 on Sum::sum and Sum::main:

time (ms)	event	tier of `sum`	tier of `main`
< 40	interpreted, counters rise	0	0
40	`sum` compiled by C1 with profiling	3	0
40	`sum` compiled by C2	4	0
41	level-3 `sum` made not entrant	4	0
42	OSR into `main`'s loop at bci 4 (C1)	4	3 (OSR)
45	OSR by C2	4	4 (OSR)
47	C2 OSR code of `main` made not entrant (retired: replaced or deoptimized)	4	lower tier

Transpilers¶

Algorithm 0.3.9 on the arrow function of the TypeScript box (bottom-up):

step	subtree	rule	result
1	`let s = 0`	`let` ⇒ `var` (no shadowing, so no rename)	`var s = 0`
2	`for (let i = 0; …)`	`let` ⇒ `var` (no closure captures `i`)	`for (var i = 0; …)`
3	`(n: number): number => {…}`	erase types; arrow ⇒ `function` (no `this` used)	`function (n) {…}`
4	`const sum = …`	`const` ⇒ `var`	`var sum = function (n) {…}`

Partial evaluation and the Futamura projections¶

Algorithm 0.3.10 on the box's prog (static stack of residual expressions):

pc	instruction	residual stack after
0	`ARG`	[x]
1	`ARG`	[x, x]
2	`MUL`	[x·x]
3	`PUSH 3`	[x·x, 3]
4	`ARG`	[x·x, 3, x]
5	`MUL`	[x·x, 3·x]
6	`ADD`	[x·x + 3·x]
7	`PUSH 1`	[x·x + 3·x, 1]
8	`ADD`	[x·x + 3·x + 1]

Residual program: target(x) = x*x + 3*x + 1 — clang printed the algebraically simplified \(x(x + 3) + 1\).

Try it

In the lab, time ch00-exec --engine=jit --time --repeat=100 against --engine=vm-threaded on inputs/gcd.tiny and inputs/bench-primes.tiny, and compute the break-even number of runs \(c / \Delta\) for each (the quiz question jit-breakeven asks for one).

4. Invariants and correctness¶

AOT compilation¶

AOT correctness is Theorem 0.1.6 for the pipeline. For PGO, Algorithm 0.3.2's invariant is the whole argument: every transformation whose decision uses the profile is correct for all inputs (inlining, layout, unrolling are correct regardless of the profile), so the result refines \(p\) whatever the profile says; an unrepresentative profile only costs speed.

Method JITs¶

Theorem 0.3.11 (A counter-triggered JIT is transparent)

If the interpreter and \(C\) are correct and deterministic, every call through Algorithm 0.3.3 returns the value the interpreter alone would return.

Proof

By induction on the number of calls. A call either interprets \(f\) (correct by assumption) or runs code[f], which by the invariant equals \(C(f)\), correct for \(f\) in isolation; since both are deterministic, they return the same value on the same arguments and global state. Compiling has no observable effect other than time (it does not run \(f\)). Each function is compiled at most once because code[f] is set before it is used and never cleared.

Tracing JITs¶

Theorem 0.3.12 (Guarded traces are correct)

Suppose every condition the interpreter tested while recording is guarded, operations in the trace compute what the interpreter computed, and each side exit's map rebuilds the interpreter state. Then executing a trace from a state \(\sigma\) at the loop header produces the same sequence of states at the header, and, on exit, the same state at the exit pc, as the interpreter would.

Proof

By induction on the number of trace iterations. Within one iteration, if all guards pass, the interpreter from the same state would take exactly the recorded path (every branch and type test on that path is decided by a guarded condition, and they all hold), executing the same operations, so the resulting states agree. If guard \(g\) fails, the operations before \(g\) are a prefix of both executions (same argument), and the exit map rebuilds the interpreter state at the instruction the interpreter would execute next; the interpreter then continues from there. When it breaks: an unguarded assumption (for instance, that a global variable read during recording is still the same) makes the trace wrong after the assumption changes — TraceMonkey and LuaJIT guard such reads explicitly.

Tiered compilation¶

Theorem 0.3.13 (Speculation with exact deoptimization is sound)

Under the precondition of Algorithm 0.3.7, every call of Invoke returns what the interpreter \(\tau_0\) returns.

Proof

Consider one execution of tier \(j\)'s code. If all guards pass, the execution satisfies the assumptions \(A_j\), under which the code refines \(f\); with deterministic \(f\) it returns \(f\)'s result. If a guard fails, the side effects performed so far are exactly those of \(f\)'s execution up to the corresponding point (guards precede any action that depends on their assumption), and Reconstruct builds \(\tau_0\)'s frame at that point exactly (exact metadata); resuming \(\tau_0\) completes the same execution. Invalidating the failed code keeps the invariant for future calls. When it breaks: if an optimization moves a side effect before a guard, the deoptimized interpreter re-executes it (a double store or a duplicated print). Optimizing JITs therefore restrict code motion across deoptimization points.

Theorem 0.3.14 (The threshold policy is 2-competitive)

Let a function be called \(N\) times (\(N\) unknown in advance), with interpretation costing \(\Delta > 0\) more per call than compiled code and compilation costing \(c\). The policy "compile when the count reaches \(k = \lfloor c / \Delta \rfloor + 1\)" has extra cost at most \(2 \cdot \min(N \Delta, c)\), and no deterministic policy has a ratio below \(2 - \Delta / c\).

Proof (the ski-rental argument; full treatment: [KMRS88])

Extra cost means cost above the ideal \(N r_c\). The policy interprets \(\min(N, k - 1)\) calls and compiles iff \(N \ge k\). If \(N < k\): extra \(= N\Delta\), and since \(N \le k - 1 \le c / \Delta\), \(N\Delta \le c\), so the optimum is \(N\Delta\): ratio 1. If \(N \ge k\): extra \(= (k-1)\Delta + c \le c + c = 2c\), and \(N\Delta \ge k\Delta > c\), so the optimum is \(c\): ratio at most 2. Lower bound: a deterministic policy either never compiles — then \(N \to \infty\) makes its extra cost \(N\Delta\) unbounded against the optimum \(c\) — or compiles at some call \(j\), and an adversary stops calling right after it. The policy then pays \((j-1)\Delta + c\) while the optimum pays \(\min(j\Delta, c)\). If \(j\Delta \le c\) the ratio is \(1 + (c - \Delta)/(j\Delta) \ge 1 + (c - \Delta)/c\); if \(j\Delta > c\) it is \(1 + (j-1)\Delta/c > 1 + (c - \Delta)/c\). Either way it is at least \(2 - \Delta / c\) (the classic ski-rental bound). JITs use this reasoning implicitly: thresholds are set where a compile would have paid for itself.

Transpilers¶

Transpilers are compilers, so Theorem 0.1.6 applies to the composition "transpiler, then target compiler". For Algorithm 0.3.9 the invariant gives termination (each rule application removes a non-core node at the root and introduces only core constructs or smaller non-core subtrees, which are desugared recursively) and correctness (each rule preserves semantics in every context, and contexts compose). When it breaks: let inside a loop captured by a closure has per-iteration bindings in ES2015; naive let ⇒ var changes behavior, so TypeScript's rule introduces a helper function per iteration in that case — the rule's context condition matters.

Partial evaluation and the Futamura projections¶

Theorem 0.3.15 (Futamura projections)

Let \(\mathit{int}\) be an interpreter for \(L\) and \(\mathit{mix}\) a specializer, both written in the same language \(M\) in which \(\mathit{mix}\) can take programs of \(M\) as data. Then:

\(\mathit{target} = [\![\mathit{mix}]\!]\,(\mathit{int}, p)\) satisfies \([\![\mathit{target}]\!]\,(d) = [\![p]\!]_L(d)\): specializing the interpreter to a program compiles the program;
\(\mathit{comp} = [\![\mathit{mix}]\!]\,(\mathit{mix}, \mathit{int})\) is a compiler from \(L\) to \(M\): specializing the specializer to an interpreter yields a compiler;
\(\mathit{cogen} = [\![\mathit{mix}]\!]\,(\mathit{mix}, \mathit{mix})\) satisfies \([\![\mathit{cogen}]\!]\,(\mathit{int}) = \mathit{comp}\): it is a compiler generator that turns interpreters into compilers.

Proof

Each step is one use of the defining equation of \(\mathit{mix}\) (Definition 0.3.1). (1) \([\![\, [\![\mathit{mix}]\!]\,(\mathit{int}, p) \,]\!]\,(d) = [\![\mathit{int}]\!]\,(p, d) = [\![p]\!]_L(d)\). (2) \([\![\mathit{comp}]\!]\,(p) = [\![\, [\![\mathit{mix}]\!]\,(\mathit{mix}, \mathit{int}) \,]\!]\,(p) = [\![\mathit{mix}]\!]\,(\mathit{int}, p) = \mathit{target}\), so by (1) \([\![\, [\![\mathit{comp}]\!]\,(p) \,]\!]\,(d) = [\![p]\!]_L(d)\): the definition of a compiler. (3) \([\![\mathit{cogen}]\!]\,(\mathit{int}) = [\![\, [\![\mathit{mix}]\!]\,(\mathit{mix}, \mathit{mix}) \,]\!]\,(\mathit{int}) = [\![\mathit{mix}]\!]\,(\mathit{mix}, \mathit{int}) = \mathit{comp}\). The theorem says nothing about efficiency: that the compiled program is faster than interpreting (the "Jones optimality" question) depends on how much work \(\mathit{mix}\) removes [JGS93, Ch. 1].

Lemma 0.3.16 (Correctness of Algorithm 0.3.10)

Under its precondition, Algorithm 0.3.10's residual expression \(r\) satisfies \([\![r]\!]\,(x) = [\![\mathtt{interp}]\!]\,(\mathtt{code}, n, x)\) for every \(x\).

Proof

Induction on \(pc\) with the invariant "the residual stack, evaluated at \(x\), equals the interpreter's stack after executing instructions \(0..pc-1\) on input \(x\)". It holds initially (both empty). Each case pushes the residual form of what the interpreter pushes (the constant, \(x\), or the operator applied to the same two operands in the same order), and the interpreter's control decisions depend only on code[pc].op, which is static, so both take the same branch. At \(pc = n\) the interpreter returns the top of its stack, which is \([\![r]\!]\,(x)\).

5. Complexity¶

Variables: \(c\) = compile cost, \(\Delta\) = per-execution saving of compiled code, \(N\) = number of executions, \(n\) = program size, \(L\) = trace length, \(h\) = hotness threshold.

Technique	Time (worst)	Time (typical)	Space	Variables
AOT compilation	\(c(n)\) once at build time + \(N r_c\)	best steady-state speed; zero warm-up	code for the whole program	\(c, N, n\)
Method JITs	extra \(\le 2 \min(N\Delta, c)\) (Theorem 0.3.14)	warm-up of milliseconds per hot method	code only for hot methods	\(c, \Delta, N\)
Tracing JITs	recording \(O(L)\) per trace + compile \(O(L)\) (linear passes over straight-line code)	very fast loops; trace explosion on branchy code	\(O(L)\) per trace, many traces	\(L, h\)
Tiered compilation	\(\sum_j c_j\) per hot function + deopt costs	fast start (tier 0/1) and fast steady state (top tier)	several versions per function	\(c_j\), number of tiers
Transpilers	\(O(n)\) desugaring + the target compiler's cost	seconds for large TypeScript projects (type checking dominates)	one output file per input	\(n\)
Partial evaluation	unbounded in general (specialization may not terminate); \(O(n \cdot \lvert \mathit{int} \rvert)\) for the unrolling of Algorithm 0.3.10	residual size proportional to the static program	residual program	\(n\)

Proposition 0.3.17 (Linear-time trace compilation and specialization)

Recording a trace of \(L\) operations and compiling it with a constant number of forward passes costs \(O(L)\); Algorithm 0.3.10 costs \(O(n)\) for a static program of \(n\) instructions and produces a residual expression of size \(O(n)\).

Proof

Recording appends \(O(1)\) items per executed instruction; a trace has no internal join points except the loop header, so each optimization pass (constant folding, CSE with a hash table, dead-code elimination by a backward sweep) and linear-scan register allocation visit each operation \(O(1)\) times. Algorithm 0.3.10 executes each case in \(O(1)\) and each instruction adds at most one node to the residual expression.

Pathological inputs. (1) Tracing: a loop body with \(b\) independent ifs has \(2^b\) paths; a tracing JIT may record many of them (trace explosion), while a method JIT compiles the body once. (2) Tiered / speculative: a function whose argument types alternate between two classes every \(k\) calls deoptimizes and recompiles repeatedly (a "deopt loop"); engines cap recompilations and fall back to generic code. (3) Partial evaluation: specializing an interpreter to a program whose static loop is unbounded (a while over static data that never terminates) makes the specializer itself diverge — the precondition of Algorithm 0.3.10 excludes it. (4) JIT thresholds: \(N = k\) exactly is the worst case of Theorem 0.3.14.

At scale. The lab's JIT spends 4.5–9.6 ms per program in prepare (IR generation + default<O2> + code generation) and pays off after a few runs of the benchmark programs, but not for inputs/gcd.tiny run once (measure it: quiz jit-breakeven).

AOT compilation¶

PGO [PH90] (Algorithm 0.3.2) and AutoFDO/sampling PGO — profiles from production samples instead of instrumented runs; trade-off: less precise, no training build.
LTO / ThinLTO — defer optimization to link time for whole-program information (Lesson 0.1 §6).
AOT for managed languages — GraalVM Native Image, .NET NativeAOT and Android ART compile JIT languages ahead of time; trade-off: no speculation on run-time profiles, faster startup.

Method JITs¶

Inline caches [DS84] — cache the target of a dynamically dispatched call at the call site; polymorphic inline caches extend this and feed type profiles to the optimizer.
Lazy compilation — compile each function on first call (ORC's lazy lli -jit-kind=orc-lazy); trade-off: many small compile jobs.

Tracing JITs¶

Trace trees and side-exit stitching [Gal+09] — hot side exits start new traces attached to the exit; trade-off: trace-tree management.
Meta-tracing [BCFR09] — trace the language's interpreter (written in RPython) with hints marking its dispatch loop; the traced program is the user program. Trade-off: the interpreter author writes hints, but gets a JIT for free.

Tiered compilation¶

Baseline compilers — one-pass template compilers from bytecode (V8 Sparkplug [V8-Sparkplug], HotSpot C1 at level 1–3); trade-off: little optimization.
Mid-tier optimizing compilers — V8 Maglev [V8-Maglev] trades peak performance for compile speed between Sparkplug and TurboFan.
OSR — enter optimized code in the middle of a long-running loop (the % lines in HotSpot's log).

Transpilers¶

Type-erasing transpilers (TypeScript → ES2022) vs desugaring transpilers (→ ES5); trade-off: output readability and size vs reach.
Compiling through C (Nim, Chicken, early C++) — portability and the C compiler's optimizer; trade-off: C's undefined behavior must be avoided in generated code, and debugging maps back through two languages.

Partial evaluation and the Futamura projections¶

Offline partial evaluation with binding-time analysis [JGS93] — decide statically which variables are static; makes self-application (projections 2 and 3) practical.
Partial evaluation of self-optimizing AST interpreters (Truffle/Graal) [WWH+17] — the first projection performed at run time by a JIT, with deoptimization when assumptions change.

7. In real compilers¶

AOT compilation¶

LLVM

clang/lib/CodeGen/BackendUtil.cpp runs the optimization pipeline and code generation for an AOT compile (LLVM 23.1.2); PGO data enters through llvm-profdata and the -fprofile-instr-generate / -fprofile-instr-use flags [LLVM-Pipelines].

GCC -fprofile-generate / -fprofile-use; the pass list is gcc/passes.def [GCC-Passes].
pebblec — pebblec -O2 foo.pbl -o foo is AOT; --emit=llvm shows the IR before the back end.

Method JITs¶

LLVM ORC llvm/lib/ExecutionEngine/Orc/LLJIT.cpp — LLJIT::addIRModule, LLJIT::lookupLinkerMangled (what the lab's JIT engine calls) [LLVM-JIT, LLVM-ORC].
V8 TurboFan src/compiler/pipeline.cc (12.4.254.21) [V8-Src].

Find where LLVM does it. Open llvm/lib/ExecutionEngine/Orc/LLJIT.cpp at llvmorg-23.1.2. Question: which LLJITBuilderState member function fills in defaults (target machine, object linking layer) before an LLJIT is constructed? (quiz llvm-where-lljit)

Tracing JITs¶

LuaJIT src/lj_trace.c — lj_trace_hot starts recording at a hot loop, lj_trace_ins feeds each instruction to the recorder; src/lj_record.c — lj_record_ins (v2.1) [LUAJIT-Src].
PyPy rpython/jit/metainterp/pyjitpl.py — class MetaInterp; rpython/rlib/jit.py — class JitDriver, whose jit_merge_point marks the interpreter's dispatch loop (release-pypy3.10-v7.3.17) [PYPY-Src].

Tiered compilation¶

HotSpot src/hotspot/share/compiler/compilationPolicy.cpp — CompilationPolicy::event, call_event, common decide tier transitions; src/hotspot/share/runtime/deoptimization.cpp — Deoptimization::fetch_unroll_info, uncommon_trap (jdk-21+35) [HS-Tiered].
V8 src/execution/tiering-manager.cc — TieringManager::MaybeOptimizeFrame; src/baseline/baseline-compiler.cc — BaselineCompiler::GenerateCode (Sparkplug); src/maglev/maglev-compiler.cc — MaglevCompiler::Compile [V8-Src].

Transpilers¶

TypeScript — the tsc compiler's emit pipeline applies per-target transformers (ES2015 classes, arrow functions, block scoping) [TS-Handbook].
Emscripten — historically transpiled LLVM IR to JavaScript (asm.js) [Zak11]; today it targets WebAssembly through LLVM's WebAssembly back end.

Partial evaluation and the Futamura projections¶

GraalVM Truffle performs the first Futamura projection at run time on AST interpreters [WWH+17].
PyPy — meta-tracing is a dynamic first projection: the trace of the interpreter specialized to the user loop [BCFR09].
LLVM — plain -O2 (inlining + full unrolling + constant folding) specializes a small interpreter to a static program, as the box shows.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
AOT compilation	whole program, no run-time information (except PGO)	compile once, \(N r_c\) per run · best cold start and predictable speed	errors at build time	high (optimizer), no runtime	C, C++, Rust, Swift, Go, Pebble
Method JITs	run-time types and values, one method at a time	extra \(\le 2\min(N\Delta, c)\) · lab JIT: 4.5–9.6 ms compile, 12–62× faster runs	errors at run time; stack traces through JIT code need metadata	high (compiler inside the runtime)	JVM, .NET, JavaScript engines, the lab
Tracing JITs	exact hot paths across calls, with guards	\(O(L)\) per trace · excellent on loops, poor on branchy code	hard to debug (traces, side exits)	medium–high	LuaJIT, PyPy, TraceMonkey (retired)
Tiered compilation	best of all tiers; speculation + deoptimization	fast start and fast steady state · HotSpot C1→C2, V8 Ignition→Sparkplug→TurboFan	same as method JITs	highest (several compilers + deopt)	HotSpot, V8, JavaScriptCore, .NET
Transpilers	limited to what the target language can express	\(O(n)\) + target compiler · seconds	errors in generated code may confuse users	low–medium (a pretty-printer + rewrites)	TypeScript, Nim, cfront, Babel
Partial evaluation and the Futamura projections	derives compilers from interpreters	may diverge; residual size \(O(n)\) for simple interpreters	depends on the interpreter	research-grade (offline PE), framework-grade (Truffle)	Truffle/Graal, PyPy, specializing optimizers

Choose AOT when the program ships as a binary and startup and predictability matter. Choose a method JIT when the language is dynamic or bytecode must stay portable, and hot methods dominate. Choose tracing when the workload is loop-heavy with stable hot paths (numeric Lua code). Choose tiering when you need both fast startup and peak performance in a long-running dynamic runtime. Choose a transpiler when the target language already runs everywhere you need. Use partial evaluation when you would rather write an interpreter than a compiler and can build (or reuse) the specializer.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch00.yaml`)	Drill	Flashcard tag	Exercises
AOT compilation	`aot-o2-closed-form`, `jit-breakeven`	— (no randomized instance adds to the break-even computation, which the quiz covers)	`aot`	E1
Method JITs	`jit-breakeven`, `ski-rental-ratio`, `llvm-where-lljit`	— (as above)	`method-jit`	lab L5
Tracing JITs	`trace-guards`, `tracing-vs-method`	— (trace recording is traced step by step in §3 and in the quiz)	`tracing-jit`	—
Tiered compilation	`hotspot-tiers`, `deopt-purpose`	— (reading real tier logs is the exercise; see the boxes)	`tiered`	—
Transpilers	`transpiler-es5`, `transpiler-definition`	— (desugaring rules are language-specific)	`transpiler`	—
Partial evaluation and the Futamura projections	`futamura-second`, `futamura-residual`	— (the projections are equational; the quiz tests them)	`futamura`	—

Pitfall

"JIT code is always faster than AOT code" and its converse are both folklore. A JIT can specialize on run-time facts an AOT compiler never sees, but it pays compile time at run time and must stay ready to deoptimize. On the lab's bench-sum, the JIT's "run" is 0 ms because LLVM evaluated the whole input-free program at compile time — measure prepare and run separately, as ch00-exec --time does.

References¶

See the chapter references.

Lesson 0.3 — Compilation strategies: AOT, JITs, transpilers and partial evaluation¶

1. Problem and motivation¶

AOT compilation¶

Method JITs¶

Tracing JITs¶

Tiered compilation¶

Transpilers¶

Partial evaluation and the Futamura projections¶

2. Definitions and algorithms¶

AOT compilation¶

Method JITs¶

Tracing JITs¶

Tiered compilation¶

Transpilers¶

Partial evaluation and the Futamura projections¶

3. Worked examples¶

AOT compilation¶

Method JITs¶

Tracing JITs¶

Tiered compilation¶

Transpilers¶

Partial evaluation and the Futamura projections¶

4. Invariants and correctness¶

AOT compilation¶

Method JITs¶

Tracing JITs¶

Tiered compilation¶

Transpilers¶

Partial evaluation and the Futamura projections¶

5. Complexity¶

6. Variants and refinements¶

AOT compilation¶

Method JITs¶

Tracing JITs¶

Tiered compilation¶

Transpilers¶

Partial evaluation and the Futamura projections¶

7. In real compilers¶

AOT compilation¶

Method JITs¶

Tracing JITs¶

Tiered compilation¶

Transpilers¶

Partial evaluation and the Futamura projections¶

8. Comparison¶

9. Assessment¶

References¶