Skip to content

Lab 0.L2–L5 · One language, four executors: tree walker, stack VM (switch, threaded), LLVM JIT

Chapter: 0 · Compiler Architectures & Your Toolchain · Lessons: 0.2 (interpreters, dispatch), 0.3 (JIT) · Time: 8–15 hours · Tests: ./course test 0 (labels ch00)

Goal

Execute the same tiny language, Tiny, four ways and measure the difference: a tree-walking interpreter (Algorithm 0.2.3), a stack bytecode compiler (Algorithm 0.2.5) with a VM using switch dispatch and the same VM with direct-threaded dispatch (Algorithm 0.2.10), and a JIT that generates LLVM IR and runs it with ORC LLJIT (Lesson 0.3). The parser is provided; everything after the syntax tree is yours. The tests check that all four engines compute exactly the values the language definition prescribes, on hand-written programs and on hundreds of random ones; a benchmark reports how fast each is.

The Tiny language

program  = { stmt } "return" expr ";" ;
stmt     = IDENT "=" expr ";"
         | "while" expr "{" { stmt } "}"
         | "if" expr "{" { stmt } "}" [ "else" "{" { stmt } "}" ] ;
expr     = and { "||" and } ;
and      = cmp { "&&" cmp } ;
cmp      = add [ ( "<" | "<=" | ">" | ">=" | "==" | "!=" ) add ] ;   (* comparisons do not chain *)
add      = mul { ( "+" | "-" ) mul } ;
mul      = unary { ( "*" | "/" | "%" ) unary } ;
unary    = ( "-" | "!" ) unary | primary ;
primary  = INT | IDENT | "(" expr ")" ;
INT      = digit { digit } ;          (* at most 2^63 - 1; write -9223372036854775807 - 1 for INT64_MIN *)
IDENT    = ( letter | "_" ) { letter | digit | "_" } ;   (* except while, if, else, return *)

# starts a comment that runs to the end of the line. Example (inputs/gcd.tiny):

a = 1071;
b = 462;
while b != 0 {
  t = a % b;
  a = b;
  b = t;
}
return a;

Semantics

Exactly Definition 0.2.2 of Lesson 0.2. In words:

  • Values are 64-bit two's-complement integers. Every variable exists from the start with value 0.
  • +, -, * and unary - wrap modulo \(2^{64}\) (no undefined behavior).
  • / truncates toward zero; % has the sign of the dividend; x / 0 = 0, x % 0 = x, and INT64_MIN / -1 = INT64_MIN, x % -1 = 0. (So a == (a / b) * b + a % b for every b.)
  • Comparisons and ! produce 0 or 1. a && b is 1 iff both are non-zero, a || b iff either is; the right operand is evaluated only if needed (unobservable in Tiny, since expressions have no effects and never fail).
  • while e { … } repeats while e is non-zero; if e { … } else { … } chooses by e ≠ 0.
  • The program's value is the value of its final return expression. Programs may loop forever; the tests use only terminating ones.

Requirements

  • R1 (all engines). For every terminating program, every engine returns the value of Definition 0.2.2, bit for bit — including the wrapping and division edge cases.
  • R2 (Tree). Engine::Tree evaluates the syntax tree directly (no translation in prepare).
  • R3 (VMSwitch). Engine::VMSwitch compiles the tree to stack bytecode of your design once, in prepare, and runs it with a loop around a switch on the opcode. The runner must not walk the syntax tree.
  • R4 (VMThreaded). Engine::VMThreaded runs the same bytecode with direct-threaded dispatch: translate opcodes to handler addresses in prepare (GNU C "labels as values", &&label / goto *p, supported by clang and GCC) and end every handler with its own indirect jump. (On a compiler without computed goto you may fall back to switch dispatch; the course compilers have it.)
  • R5 (JIT). Engine::JIT translates the program to LLVM IR (one function), optimizes it (e.g. default<O2>), compiles it with ORC LLJIT, and the runner calls the compiled function. The generated IR must not contain undefined behavior for any input — in particular sdiv/srem are UB for a zero divisor and for INT64_MIN / -1, and add nsw etc. are UB on overflow, while Tiny defines all of them.
  • R6 (runners). A Runner may be called repeatedly; each call starts from all-zero variables and returns the same value. prepare reports failures (e.g. the JIT cannot be created) as an error string, never by throwing or printing.
  • R7 (performance, informational). On the course container the reference solution runs bench-collatz.tiny in about 380 ms (tree), 230 ms (switch), 150 ms (threaded) and 6 ms after 10 ms of compilation (JIT). Your numbers are not tested, but your threaded VM should beat your switch VM and your JIT should beat both on the long-running programs.

The contract

// labs/ch00-exec/include/tiny/Engines.h  (provided; do not change)
namespace tiny {
enum class Engine { Tree, VMSwitch, VMThreaded, JIT };

/// Runs the prepared program once; returns the value of its `return` expression.
/// Callable any number of times; every run starts with all variables 0.
/// May refer to the Program passed to prepare(), which outlives it.
using Runner = std::function<std::int64_t()>;

/// Everything before execution for engine E: nothing (Tree), bytecode compilation
/// (VMs), IR generation + optimization + JIT compilation (JIT).
std::expected<Runner, std::string> prepare(const Program &P, Engine E);
}

Program is the provided syntax tree (include/tiny/AST.h): statements and expressions with unique_ptr children, and every variable already resolved to a dense slot number 0 .. Vars.size()-1.

Command line

The provided driver ch00-exec (tools/ExecMain.cpp) parses a file and calls your prepare:

usage: ch00-exec [--engine=tree|vm-switch|vm-threaded|jit] [--time] [--repeat=N]
                 (<file.tiny> | --random=SEED)
       ch00-exec --print-random=SEED
  • Prints the result as a decimal integer and a newline; exit status 0.
  • Parse errors: <file>:<line>:<col>: error: <message> on stderr, exit status 1. Engine errors: error: <message>, exit status 2.
  • --time adds prepare <ms> ms, run <ms> ms (min of N) on stderr; --repeat=N runs the runner N times (and checks the results agree).
  • --random=SEED runs the random program with that seed; --print-random=SEED prints it (use it to debug a failing differential test).

Provided infrastructure

File What it gives you
include/tiny/AST.h, provided/Parser.cpp the syntax tree, parseProgram, printProgram (parsing is Chapters 1–4's topic, not this lab's)
include/tiny/Random.h, provided/Random.cpp randomProgram(seed): deterministic random terminating programs using every operator and edge values
tools/ExecMain.cpp the ch00-exec driver
bench/Bench.cpp the ch00-bench benchmark driver
inputs/*.tiny sample programs (answer, arith, logic, gcd, nested, unused) and benchmarks (bench-sum, bench-collatz, bench-primes, bench-fib)
src/ yours: Stub.cpp defines prepare with TODO(ch00); add any files

What the tests check

Test Checks
ch00.Engines/EngineTest.Goldens/<engine> R1 on inputs/{answer,arith,logic,gcd,nested,unused}.tiny; expected values from the Python oracle tools/course/lib/tiny.py
ch00.Engines/EngineTest.Semantics/<engine> R1 on 20 one-line programs covering wrapping, / and % by 0 and −1, truncation, logic
ch00.Engines/EngineTest.RandomOracle/<engine> R1 on random programs, seeds 1–200, against tests/ch00/Inputs/random-expected.txt (computed by the Python oracle; regenerate with tests/ch00/update_goldens.py)
ch00.Engines/DifferentialTest.AgreesWithTree/<engine> VMSwitch, VMThreaded and JIT agree with Tree on random programs, seeds 1000–1599
ch00.Engines/EngineTest.Repeatable/<engine> R6
ch00.lit exec-*.test the CLI on every sample program and engine; benchmark results for the fast engines; --random/--print-random/--repeat/--time; error messages (exec-errors.test passes before you write code: it only exercises the provided driver and parser; the others need prepare)
ch00.lab.bench-smoke ch00-bench --quick: all four engines agree on the benchmarks (times are informational)

R2–R4's "how" (no tree walking in the VMs, threaded dispatch) is not observable by tests; the benchmark shows it, and the reference solution in solutions/labs/ch00-exec/src/ is one way to do it.

Milestones

  1. L2 — Tree walker. ctest --test-dir build/<preset> -R 'ch00.Engines/EngineTest.*/tree' passes.
  2. L3 — Stack bytecode + switch VM. Design the instruction set and the compiler (Algorithm 0.2.5); -R 'vm_switch' passes. Add a disassembler for yourself.
  3. L4 — Threaded dispatch. -R 'vm_threaded' passes; compare ch00-exec --engine=vm-switch --time --repeat=5 inputs/bench-sum.tiny with vm-threaded.
  4. L5 — JIT. IR generation + LLJIT; -R 'jit' passes; the whole ./course test 0 is green.
  5. Measure. build/<preset>/bin/ch00-bench --runs=5 and fill in:
program tree (ms) switch (ms) threaded (ms) JIT prepare (ms) JIT run (ms)
bench-collatz
bench-fib
bench-primes
bench-sum

Then answer: after how many runs does the JIT pay off on gcd.tiny (Theorem 0.3.14)? Why is bench-sum's JIT run time 0?

Hints

Hint 1 — where to start

Write the tree walker first: it is Definition 0.2.2 read as code, and every later engine is tested against it. Put the operator semantics (wrapping +, total / and %) in one small header shared by all engines; do the arithmetic in uint64_t to avoid C++'s signed-overflow undefined behavior.

Hint 2 — the key ideas

VM: one flat std::vector of instructions with an opcode and one integer operand is enough; the compiler can compute the maximum stack depth (Theorem 0.2.13) so the VM needs no bounds checks. Jumps: emit a placeholder and patch it (Algorithm 0.1.10). Threaded VM: the handler addresses exist only inside the function that contains the labels, so let that function also do the translation (for example, a call with a null program returns its label table). JIT: keep each variable in an alloca and let default<O2> promote them to registers; guard sdiv/srem by replacing the divisor with 1 in the two special cases and fixing the result with select.

Hint 3 — a design sketch

Bytecode { vector<Instr> code; unsigned numVars, maxStack; } with Instr { Op op; int64_t arg; }; ops push load store add sub mul div rem lt le gt ge eq ne neg not jmp jz jnz ret; &&/|| compile to jumps. Threaded: struct TInstr { const void *handler; int64_t arg; const TInstr *target; }. JIT: LLVMContext + Module + IRBuilder, one i64 @tiny_main(), PassBuilder::buildPerModuleDefaultPipeline(O2), LLJITBuilder().create(), addIRModule(ThreadSafeModule(...)), lookup("tiny_main"), toPtr<int64_t (*)()>(); call InitializeNativeTarget and InitializeNativeTargetAsmPrinter once. Keep the LLJIT alive inside the runner (a shared_ptr captured by the lambda). The most common failures the tests catch: INT64_MIN / -1, 7 % 0, && returning the right operand's value instead of 0/1, and runners that forget to reset variables.

Stretch goals ★

  • A register VM (Algorithm 0.2.7) as a fifth engine; count executed instructions against the stack VM.
  • Superinstructions: fuse load x; load y or load x; push k; add and measure (Lesson 0.2 §6).
  • Lazy JIT: interpret first and JIT only after the program's loop has run \(k\) times (Algorithm 0.3.3); pick \(k\) from your measured \(c\) and \(\Delta\).