Chapter 0 · Compiler Architectures & Your Toolchain¶

Part 0 · Orientation · about 2–3 weeks · Next: Ch 1

The problem¶

A compiler maps a program \(p\) in a source language to a program in a target language that refines it (Definition 0.1.4: every behavior of the output is a behavior of \(p\), unless \(p\) has undefined behavior). This chapter is about the architecture of that map rather than any one algorithm inside it: how the work is split into passes and in what order it runs (multi-pass, single-pass, query-based, multi-level), when translation happens relative to execution (interpretation, AOT, JIT, tiers, transpilation), how one compiler serves many languages and machines (shared IRs, retargeting), how a compiler that compiles itself is built and trusted (bootstrapping, Trusting Trust, diverse double-compiling), and which tools surround it (preprocessor, assembler, linker, loader, C runtime). Every later chapter fills in one box of the pictures drawn here; the Pebble compiler you build is a multi-pass, AOT, LLVM-based compiler whose shared IR is PIR.

What you will be able to do¶

State the correctness criterion of a compiler (refinement) and prove that a pipeline of correct passes is correct (Theorem 0.1.6).
Trace a one-pass compiler with backpatching, a query system's red-green marking, and an MLIR progressive lowering on a small program.
Compile expressions to stack and register bytecode, compute stack depth and Ershov numbers, and count dispatch mispredictions for switch vs threaded dispatch (./course drill stack-code, ./course drill dispatch).
Explain method, tracing and tiered JITs, deoptimization, and when a JIT pays off (the 2-competitive threshold rule); state and prove the Futamura projections.
Compose T-diagrams to plan a bootstrap or a cross-compiler (./course drill tdiagram), and explain why stage 2 = stage 3 does not rule out a trojan while diverse double-compiling does.
Attribute an error or artifact to the right toolchain phase — preprocessor to loader (./course drill phases) — and compute a relocation by hand.
Use the course toolchain: clang -emit-llvm, opt, llc, lli, llvm-readelf, llvm-objdump, pebblec, pir-run.
Write LLVM IR by hand and build a tree-walker, a stack VM (switch and threaded) and an LLVM JIT for one small language, and measure them.

Prerequisites: none beyond C++ and a working environment (./course doctor). Chapters 1–7 later build the front-end pieces this chapter only names.

Notation¶

Shared notation follows the house notation (§1 sets and logic, §6 semantics, §8 complexity). In this chapter:

Symbol	Meaning
\(\mathrm{Beh}(p)\)	the set of observable behaviors of program \(p\), possibly containing \(\mathrm{ub}\) (Definition 0.1.1)
\(\mathrm{ub}\)	"has undefined behavior": a source allowed to do anything
\(q \preceq p\)	\(q\) refines \(p\): \(\mathrm{ub} \in \mathrm{Beh}(p)\) or \(\mathrm{Beh}(q) \subseteq \mathrm{Beh}(p)\) (Definition 0.1.2)
\(C : L_S \rightharpoonup L_T\)	a compiler, a partial function between languages (Definition 0.1.4)
\(P_k \circ \dots \circ P_1\)	a pipeline of passes (Definition 0.1.5)
\(\mathrm{fp}(v)\), \(\mathrm{deps}(v)\)	fingerprint and recorded dependencies of a query node (Definition 0.1.11)
\(\mathbb{Z}_{64}\), \(\mathrm{wrap}(n)\)	64-bit two's-complement integers and reduction into them (Definition 0.2.2)
\(\langle e, \sigma \rangle \Downarrow v\), \(\langle \bar{s}, \sigma \rangle \Downarrow \sigma'\)	big-step evaluation of Tiny expressions and statements; \(\sigma\) a state, \(\sigma_0 = \lambda x.\,0\) (Definition 0.2.2)
\(a \mathbin{\hat{\oplus}} b\)	the total semantic operator of Tiny's \(\oplus\) (division and remainder defined for \(b = 0\) and \(b = -1\))
\((pc, S, \sigma)\), \(\to\)	a stack-machine configuration and one step (Definition 0.2.4)
\(D(e)\), \(E(e)\)	stack depth of postorder code and Ershov number of expression \(e\) (Theorems 0.2.13, 0.2.14)
\(\ell\), \(o\)	numbers of leaves and operators of an expression (Proposition 0.2.15)
\(M_{\mathrm{sw}}\), \(M_{\mathrm{th}}\)	mispredicted dispatches under switch and threaded dispatch (Definition 0.2.9)
\([\![q]\!]\)	the input–output function of program \(q\) (Definition 0.3.1)
\(\mathit{int}\), \(\mathit{comp}\), \(\mathit{mix}\)	interpreter, compiler, specializer (partial evaluator) as programs (Definition 0.3.1)
\(c\), \(\Delta\), \(N\)	compile cost, per-run saving of compiled code, number of runs (Theorem 0.3.14)
\(C(S, T, I)\), \(R(S, I)\)	T-diagrams: a compiler from \(S\) to \(T\) written in \(I\); an interpreter for \(S\) written in \(I\) (Definition 0.5.1)
\(b_k\)	stage-\(k\) compiler binary (Definition 0.5.7)
\(S\), \(A\), \(P\)	symbol address, addend and place of a relocation; PC-relative value \(S + A - P\) (Definition 0.6.4)
\(\mathrm{HS}(t)\)	hide set of a preprocessing token (Definition 0.6.1)

Technique map¶

Family	Techniques (origin)	Lesson
Pipeline shapes	multi-pass pipelines (FORTRAN I, Backus et al. 1957); single-pass compilation (Wirth's Pascal 1971; Turbo Pascal 1983; TCC); query-based incremental compilation (rustc queries, salsa, Swift request evaluator, Roslyn; Adapton, Hammer et al. 2014; Mokhov–Mitchell–Peyton Jones 2018); multi-level IR (MLIR, Lattner et al. 2021)	0.1
Interpreters	tree-walking interpreters (McCarthy 1960); stack-based bytecode VMs (P-code, JVM, CPython); register-based bytecode VMs (Lua 5, Ierusalimschy et al. 2005; Shi et al. 2005); dispatch: switch vs direct/indirect/token threading (Bell 1973; Ertl–Gregg 2003)	0.2
Compilation strategies	AOT compilation (FORTRAN I 1957; PGO, Pettis–Hansen 1990); method JITs (Deutsch–Schiffman 1984); tracing JITs (Dynamo, Bala et al. 2000; TraceMonkey, Gal et al. 2009; LuaJIT; PyPy meta-tracing, Bolz et al. 2009); tiered compilation (Self, Hölzle et al. 1992–94; HotSpot C1/C2; V8 Ignition/Sparkplug/Maglev/TurboFan); transpilers (Cfront; TypeScript; Emscripten, Zakai 2011); partial evaluation and the Futamura projections (Futamura 1971; Jones–Gomard–Sestoft 1993; Truffle, Würthinger et al. 2017)	0.3
Retargeting	the m × n problem and shared IRs (UNCOL, Strong et al. 1958); LLVM's three-phase design (Lattner–Adve 2004); GCC's GENERIC/GIMPLE/RTL; Cranelift (CLIF, ISLE; VanHattum et al. 2024)	0.4
Bootstrapping and trust	T-diagrams (Bratman 1961; Earley–Sturgis 1970); self-hosting and multi-stage builds (GCC 3-stage bootstrap, Clang stage⅔, Go toolchain1–3); Trusting Trust (Thompson 1984); diverse double-compiling (Wheeler 2005, 2009)	0.5
The toolchain around the compiler	the preprocessor (C, 1970s; hide sets, Prosser 1986); assemblers and object files (ELF, Mach-O, COFF); static linking (Levine 2000); loading and dynamic linking (PLT/GOT, lazy binding; Drepper 2011); the C runtime (crt files, libc)	0.6

flowchart LR
  subgraph Shape[How work is organized]
    MP[Multi-pass<br/>FORTRAN I 1957] --> Q[Query-based<br/>rustc, salsa]
    SP[Single-pass<br/>Wirth 1971, TCC] -.->|baseline JITs| TI
    MP --> ML[Multi-level IR<br/>MLIR 2021]
  end
  subgraph When[When translation happens]
    TW[Tree walker<br/>McCarthy 1960] --> BC[Bytecode VM<br/>stack / register]
    BC --> TH[Threaded dispatch<br/>Bell 1973]
    BC --> MJ[Method JIT<br/>Deutsch-Schiffman 1984]
    BC --> TJ[Tracing JIT<br/>Dynamo 2000, TraceMonkey 2009]
    MJ --> TI[Tiered + deopt<br/>Self, HotSpot, V8]
    TW -->|Futamura 1971| PE[Partial evaluation<br/>Truffle, PyPy]
    AOT[AOT<br/>FORTRAN I] --> TR[Transpilers]
  end
  subgraph Where[Many languages, many machines]
    UN[UNCOL 1958<br/>m + n] --> LV[LLVM three-phase<br/>2004]
    UN --> GC[GCC GIMPLE/RTL]
    UN --> CL[Cranelift]
  end
  MP --> AOT
  LV --> MJ

Read the diagram as three independent axes: a compiler has a shape (left), a timing (middle) and a retargeting strategy (right). pebblec is multi-pass, AOT, and LLVM-based; the lab's JIT engine is multi-pass (IR generation, default<O2>, code generation) inside a method JIT.

Who uses what¶

System	Shape · timing · retargeting	Where in this chapter
Clang / LLVM 23	multi-pass · AOT (and ORC JIT, `lli`) · three-phase, 48 targets	Lessons 0.1, 0.3, 0.4, 0.6
GCC 13–15	multi-pass (364 passes at `-O2` in gcc 13.3) · AOT · GENERIC/GIMPLE/RTL, 3-stage bootstrap	Lessons 0.1, 0.4, 0.5
rustc 1.94 / rust-analyzer	query-based incremental · AOT · LLVM (or Cranelift) back end	Lessons 0.1, 0.4
TCC 0.9.27	single-pass · AOT · x86/ARM/RISC-V back ends in C	Lessons 0.1, 0.5
MLIR-based compilers (Flang, IREE, CIRCT)	multi-level IR · AOT · LLVM at the bottom	Lesson 0.1
CPython 3.11	stack bytecode VM, token-threaded dispatch, quickening	Lesson 0.2
Lua 5.4 / LuaJIT 2.1	register VM / tracing JIT	Lessons 0.2, 0.3
HotSpot (OpenJDK 21)	stack bytecode + tiered C1/C2 JIT with deoptimization	Lessons 0.2, 0.3
V8 12.4 (Node 22)	Ignition register/accumulator VM + Sparkplug + (Maglev) + TurboFan	Lessons 0.2, 0.3
PyPy	meta-tracing JIT (a dynamic Futamura projection)	Lesson 0.3
TypeScript 5.9	transpiler to JavaScript	Lesson 0.3
Wasmtime 37 / Cranelift	JIT/AOT for Wasm · CLIF with block parameters, ISLE lowering	Lesson 0.4
Go 1.24	self-hosting, toolchain½/3 bootstrap	Lesson 0.5
pebblec (this course)	multi-pass · AOT · PIR shared IR → LLVM	Tour

Comparison¶

The rows below are the lessons' §8 tables, gathered in one place (same text as in each lesson).

Lesson 0.1 — Pipeline shapes: multi-pass, single-pass, query-based, multi-level

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Multi-pass pipelines	any optimization; whole-function and (with LTO) whole-program views	\(\sum_i T_{P_i}(n)\) · `clang -O2`: 8.6 s on 5 000 functions	best code; errors reported per phase, all at once	high, but modular (one pass at a time)	production AOT compilers (Clang, GCC, rustc, pebblec)
Single-pass compilation	local decisions only; no global optimization	\(O(n)\) · TCC: 0.02 s on 5 000 functions (≈ 50× `clang -O0`)	naive code (every variable in memory); stops at first error in the simplest designs	lowest: one recursive-descent parser	fast compilers (TCC, Turbo Pascal), baseline JITs, small DSLs
Query-based incremental compilation	same as the batch pipeline it replaces	rebuild \(\approx O(\lvert V \rvert + \lvert E \rvert)\) + impact of the edit	same output; enables precise IDE answers	very high: purity discipline everywhere	IDEs and incremental builds (rustc, rust-analyzer, Swift, Roslyn)
Multi-level IR (MLIR)	domain abstractions survive until lowered (loops, tensors, hardware)	linear per lowering step · depends on the pattern sets	depends on the dialects; verifier per dialect	high infrastructure cost, low per new abstraction	ML, HPC, hardware and new-language compilers (IREE, Flang, CIRCT)

Lesson 0.2 — Interpreters: tree walkers, bytecode VMs and dispatch

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Tree-walking interpreters	full language; the reference semantics	\(\Theta(N)\) node visits · slowest (1× in the lab)	best: errors point at tree nodes with source positions	lowest (one function per construct)	reference interpreters (`pir-run`), prototypes, DSLs
Stack-based bytecode VMs	same	\(\Theta(\ell + o)\) per expression · 1.6–1.9× the tree walker	good (bytecode keeps position tables)	low: postorder compiler + loop	JVM, CPython, WebAssembly, .NET
Register-based bytecode VMs	same	\(\Theta(o)\) per expression · ~47% fewer instructions [SGBE05]	good	medium: temporaries, operand encoding	Lua 5, V8 Ignition, Dalvik
Dispatch: switch and threaded code	same (only the dispatch changes)	same \(T\) · threaded 1.5–1.9× faster than switch in the lab	identical	switch: trivial; threading: needs computed goto or tail calls	CPython (threaded), Lua (switch), HotSpot (template handlers)

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

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

Lesson 0.4 — Retargeting: the m × n problem, LLVM, GCC and Cranelift

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
The m × n problem and shared IRs (UNCOL)	limited by what the IR can express	\(m + n\) translators instead of \(m \cdot n\)	as good as the IR's semantics is precise	one IR design + \(m + n\) translators	every retargetable compiler; PIR in this course
LLVM's three-phase design	rich SSA IR, ~120 `-O2` passes, 48 targets	minutes-scale AOT builds · `-O0` for fast compiles	excellent code; IR verifier catches broken passes	front end only, for a new language	Clang, rustc, swiftc, Flang, pebblec
GCC's GENERIC, GIMPLE and RTL	three IRs; RTL is very close to the machine	comparable to LLVM; 364 passes at `-O2` (gcc 13.3)	excellent code	high (GCC internals, machine descriptions)	GCC's C/C++/Fortran/Ada/Go front ends
Cranelift	fewer optimizations; verified lowering rules	fast compilation by design (JIT/AOT for Wasm)	good, not best, code	moderate (Rust, ISLE DSL)	Wasmtime, rustc debug builds

Lesson 0.5 — Bootstrapping, self-hosting and trust

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
T-diagrams and bootstrapping	decides what can be built from what; exact	saturation polynomial in the number of languages · instant by hand	a plan (derivations), or "impossible" with a reason	pencil and paper; `./course drill tdiagram`	planning ports, cross-compilers, new languages
Self-hosting and multi-stage builds	detects miscompilation of the compiler by itself (stage 2 ≠ 3)	\(3 T_c\) · hours for GCC/Clang	a byte-level mismatch, hard to diagnose	build-system support	GCC `make bootstrap`, Clang stage⅔, Go toolchain1–3
Trusting Trust	an attack: undetectable by source inspection or stage comparison	invisible at run time	none — that is the point	modest for a skilled attacker	the threat model for toolchains
Diverse double-compiling	detects Thompson-style trojans, assuming one trusted compiler	\(2 T_c\) per trusted compiler	match / mismatch	needs deterministic builds and a second compiler	auditing compiler binaries; reproducible-builds projects

Lesson 0.6 — The toolchain around the compiler: preprocessor, assembler, linker, loader, runtime

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
The preprocessor	textual: can generate any token sequence, knows no types	linear in expanded size, which can be huge · C++ headers dominate compile time	notoriously poor (errors appear in expanded code; clang tracks macro locations to help)	moderate (hide sets, stringizing, pasting)	C, C++, assembly with macros
Assemblers and object files	exact encoding; no optimization	two passes + relaxation · negligible time	precise (line, invalid register or operand)	one encoder per ISA (LLVM: TableGen-generated)	every native toolchain; integrated in LLVM
Static linking	whole-program symbol resolution and layout	\(O(n + y + r)\) · seconds even for huge programs with lld/mold	clear for undefined/duplicate symbols; object and offset named	high (formats, relocation types, archives)	every native build
Loading and dynamic linking	late binding: libraries shared and updated independently	\(O(\ell + r)\) at startup + lazy lookups · milliseconds	errors only at run time (missing library, symbol version)	high (in libc and kernel)	every dynamically linked program
The C runtime (crt, libc)	defines what runs before and after `main`	negligible for C	failures look like crashes before `main`	small (crt), huge (libc)	every hosted C program; Pebble's runtime

Comparison-lab results (reproduce with build/<preset>/bin/ch00-bench --runs=5 on a build with -DPEBBLE_USE_SOLUTION=tiny-exec; x86-64, the course container): on bench-collatz the tree walker takes 376 ms, the switch VM 232 ms, the threaded VM 150 ms and the LLVM JIT 6.1 ms after 9.6 ms of compilation; on bench-sum the JIT folds the whole input-free program to a constant.

Route through this chapter¶

Step	What	Techniques	How it is exercised
1	Setup · `./course doctor`	—	E0
2	Lesson 0.1	multi-pass, single-pass, query-based, MLIR	drill `phases`; quiz; flashcards
3	Lesson 0.2	tree walker, stack VM, register VM, dispatch	drills `stack-code`, `dispatch`; quiz
4	Lesson 0.3	AOT, method/tracing/tiered JITs, transpilers, Futamura	quiz; lab timing
5	Lesson 0.4	m × n, LLVM, GCC, Cranelift	quiz
6	Lesson 0.5	T-diagrams, self-hosting, Trusting Trust, DDC	drill `tdiagram`; quiz
7	Lesson 0.6	preprocessor, assembler, linker, loader, crt	drill `phases --difficulty hard`; quiz
8	Exercises E1 and lab L1	the LLVM tools; hand-written IR	`./course test 0` (first-ir tests)
9	Comparison lab `labs/ch00-exec`	tree walker vs stack VM (switch, threaded) vs LLVM JIT	`./course test 0` + `ch00-bench`
10	Theory test	all	`./course quiz 0` (≥ 80 % to finish)

Pebble itself implements nothing in this chapter; the techniques are implemented in the two labs (the ★ comparison lab covers four of them) and the rest are theory + drills.

Tour: the toolchain this course uses¶

  foo.pbl ─► pebblec front end (Ch 1–7, 11) ─► PIR ─► PIR→LLVM (Ch 11) ─► LLVM IR ─► opt passes (yours: Ch 12–20)
                                              │                                  │
                                              └─► pir-run (reference interpreter) └─► llc / back end (Ch 21–23) ─► .o ─► ld + runtime ─► a.out

Tool	What it is	Try	Documentation
`pebblec`	the course compiler driver: front end, PIR verifier, PIR→LLVM, `-O0/-O1/-O2`, object emission, linking	`pebblec foo.pir --emit=llvm -O2 -o -` (Lesson 0.4 box)	docs/architecture.md
PIR	Pebble's shared, versioned mid-level IR (MIR/SIL style): typed locals, basic blocks, explicit safety checks	read `tests/conformance/lit/pir/fib.pir`	docs/pir/pir-spec.md
`pir-run`, `pir-opt`	reference PIR interpreter; parse/verify/print PIR	`pir-run sum.pir`	docs/pir/pir-spec.md §16
`clang`	C/C++ front end and driver (`-###`, `-ccc-print-phases`, `-E`, `-S -emit-llvm`, `-c`)	Lesson 0.1 boxes	Clang driver internals
`opt`	runs LLVM IR passes: `-passes='default<O2>'`, `-print-pipeline-passes`, `-print-after-all`, `-passes=dot-cfg`	Lesson 0.1 boxes	LLVM passes
`llc`	LLVM back end: IR → assembly or object for any `-mtriple`	Lesson 0.4 box	llc
`lli`	runs IR: ORC JIT by default, `-force-interpreter` for the IR interpreter	Lessons 0.2 and lab L1	lli
`llvm-readelf`, `llvm-objdump`, `llvm-nm`	inspect objects and executables	Lesson 0.6 boxes	LLVM command guide
LLVM IR	the language `first.ll` is written in	lab L1	LangRef
Compiler Explorer	compare compilers and flags in the browser (`-emit-llvm`, `-O0` vs `-O2`, other targets)	paste `sum.c`	godbolt.org

Two more commands worth knowing from day one: opt -passes=dot-cfg -disable-output f.ll writes one Graphviz file per function (.sum.dot; view with dot -Tsvg), and clang -ftime-trace -c f.c writes a Chrome-trace JSON of where compile time went.

Practice and check¶

./course doctor                                     # toolchain OK
./course drill phases --difficulty easy             # which phase? (Lessons 0.1, 0.6)
./course drill stack-code --difficulty medium       # stack vs register code (Lesson 0.2)
./course drill dispatch --difficulty easy           # switch vs threaded mispredictions (Lesson 0.2)
./course drill tdiagram --difficulty medium         # bootstrapping (Lesson 0.5)
./course flash 0                                    # daily, a few minutes
./course quiz 0                                     # after the lessons
./course test 0                                     # after the labs
./course status

References¶

The chapter's annotated bibliography — papers, textbook sections, pinned source files, docs — is in references.md. Start with: [Dragon2, §1.2] (the phases of a compiler), [Lat11] (LLVM's three-phase design in its author's words), [EG03] (why dispatch dominates interpreters), [Fut71] (the projections), [Tho84] (three pages that changed how we trust compilers), and [EaC3] for a gentler overview.