Chapter 24 · The Complete Pebble Compiler — and Beyond

Part 6 · Capstone · about 3 weeks · Previous: Ch 23 · Next: Where to go from here

The problem

Twenty-three chapters produced the parts: a front end that turns Pebble source into PIR (Ch 1–Ch 11), a code generator from PIR to LLVM IR, and a shelf of passes, pebble-mem2reg, pebble-sccp, pebble-gvn, pebble-licm, pebble-inline and the rest (Ch 12–Ch 20), with LLVM's own back end behind them (Ch 21–Ch 23). This chapter asks the questions that only arise when the parts meet. Given the set of passes \(\Sigma\) you wrote, each with the facts it needs and the facts it creates, in which order, and how many times, should pebblec -O1 run them, and how do you know the result is right and worth it? That is the first half: pipeline design, then the compile-time versus run-time decisions a language implementer makes (which checks to prove away statically, which code to specialize at run time), the JIT designs that move compilation to run time altogether, and the debug information that lets a debugger map machine state back to Pebble variables. The second half surveys what a Pebble successor would need next: memory management (reference counting, tracing collection with stack maps, ownership, regions), exception handling beyond Lesson 11.7, and the two directions modern compiler work points to: multi-level IRs (MLIR) and proofs (CompCert, Alive2). The inputs are your compiler and the course's 74 end-to-end programs; the outputs are a -O1 that is your optimizer end to end, a differential fuzzer that compares it with pir-run, -O0 and LLVM's -O2 on thousands of generated programs, a benchmark report, and (★) a JIT with a REPL, debug info that gdb understands, and a second front end in Rust held to the same conformance suite.

What you will be able to do

• Design a multi-stage optimization pipeline from the enabling relations of your passes: canonicalize first, iterate the simplification block to a fixpoint, run loop passes on canonical loops, clean up last; and prove that the fixpoint loop terminates (drill pass-order).
• Measure the pipeline: instructions, object size, compile time and run time at -O0, your -O1 and LLVM's -O2 on eight benchmarks, and explain each ratio with a pass.
• Fuzz your compiler differentially with a generator that emits only accepted, terminating Pebble programs, and turn a disagreement into a reduced witness.
• Decide, for a check or a specialization, whether it belongs at compile time (proof), at run time (dispatch, guard) or both (deoptimization), and read the stack map a deoptimization point leaves behind.
• Build an ORC LLJIT session that runs Pebble against the runtime, switch it to lazy compilation with LLLazyJIT, and explain what a re-optimizing tier adds.
• Emit debug information with DIBuilder and debug records, read the DWARF that llc produces (llvm-dwarfdump), evaluate a location expression by hand, and derive a location list (drill dwarf-location).
• Compare the four memory-management designs on the same allocation trace: count retains and releases (drill refcount-trace), compute the roots a stack map must hold at a safepoint (drill gc-roots), explain what the borrow checker rejects, and what a region frees.
• Place MLIR's dialect conversion, CompCert's simulation proofs and Alive2's translation validation on one map of "how do we know the compiler is right", and use alive-tv on your own pipeline's output.

Prerequisites: everything. Specifically Ch 12 (pass manager, pipelines, phase ordering, fuzzing, translation validation), Ch 13–Ch 20 (the passes you will order), Ch 11 (the driver, the runtime ABI, Lesson 11.7's exception handling), Ch 14 (liveness, for stack maps), Ch 9 (metadata and debug records), Ch 0 (JIT architectures, tiering). The fast track (0 → 8 → … → 24) builds the front end from the solutions: -DPEBBLE_USE_SOLUTION=lexer,parser,names,types,lower,codegen.

Notation

Shared notation follows the house notation: §1 (sets, functions), §3 (graphs), §7 (dataflow, liveness), §8 (complexity). In this chapter:

Symbol	Meaning
\(\Sigma\), \(s \in \Sigma\), \(s(P)\)	the set of passes; a pass as a function on programs (Ch 12, Definition 12.2.6)
\(\mathcal{F}\), \(F(P) \subseteq \mathcal{F}\)	the finite set of facts (opportunities) and the facts a program holds (Definition 24.1.1)
\(\mathrm{needs}(s)\), \(\mathrm{rem}(s)\), \(\mathrm{adds}(s)\)	the enabling relation of pass \(s\): facts that must be absent, facts it removes, facts it creates (Definition 24.1.2)
\(w = s_1 \cdots s_\ell\), \(w^{\omega}(P)\)	a pipeline word and its fixpoint (Ch 12, Definition 12.2.8)
\(\mathcal{C}_{\mathrm{ssa}}, \mathcal{C}_{\mathrm{loop}}\)	canonical forms: promotable allocas gone; loop-simplify + LCSSA (Definition 24.1.3)
\(t_c\), \(t_r\), \(n\)	compile-time cost, per-execution run-time cost, number of executions (Definition 24.2.1)
\(A\), \(g_A\), \(\mathrm{deopt}\)	a speculative assumption, its guard, the transfer to unoptimized code (Definition 24.2.6)
\(\mathrm{MU}\), \(\mathrm{JD}\), \(\mathrm{stub}(f)\)	ORC materialization unit, JITDylib, the lazy reexport stub of \(f\) (Definition 24.3.1)
\(\mathrm{DIE}\), \(\mathrm{loc}(v, a)\), \(\mathrm{LL}(v)\)	a DWARF debugging information entry; the location of variable \(v\) at address \(a\); its location list (Definitions 24.4.1–24.4.4)
\(\mathrm{rc}(o)\), \(\mathrm{live}(p)\), \(\mathrm{roots}(p)\)	reference count of object \(o\); values live at point \(p\); the pointers among them (Definitions 24.5.1, 24.5.5)
\(\rho\), \(\mathrm{owner}(v)\), \(\mathrm{borrows}(v)\)	a region; the owner of a value; its live borrows (Definitions 24.5.7, 24.5.9)
\(\mathrm{funclet}(pad)\), \(\mathrm{color}(B)\)	the outlined handler of an EH pad; the pad a block belongs to (Definition 24.6.1)
\(L_1 \sqsupseteq L_2\), \(\sim\)	refinement of semantics; a simulation relation (Definitions 24.7.3, 24.7.4)

Numbered statements are N.k.m (chapter, lesson, counter), as in NOTATION.md §9.

Technique map

Family	Techniques (origin)	Lesson
Pipeline design	staged pipelines ordered by enabling relations (Whitfield & Soffa 1997; LLVM PassBuilderPipelines); canonicalization gates: SSA, loop-simplify, LCSSA as preconditions (Cytron et al. 1991; LLVM LoopSimplify, Lesson 15.7); fixpoint iteration with change detection (Kildall 1973's fixpoint view; LLVM devirt<4>, GCC may_iterate)	24.1
Compile-time vs run-time trade-offs	static check elimination (bounds-check elimination: Gupta 1990, Bodík, Gupta & Sarkar 2000; Ch 18's pebble-bce); multiversioning and run-time dispatch (GCC/Clang target_clones, ifuncs; LLVM LoopVersioning); speculation with guards and deoptimization (Hölzle, Chambers & Ungar 1992; LLVM llvm.experimental.deoptimize)	24.2
JIT designs	ORC LLJIT (Lang Hames, 2018–; LLVM LLJIT); lazy compilation by reexport stubs (Deutsch & Schiffman 1984; LLVM LLLazyJIT, LazyReexports); tiered re-optimization (Hölzle & Ungar 1994; HotSpot C1/C2; LLVM ReOptimizeLayer)	24.3
Debug information	DWARF (DWARF 5, 2017; DIEs, line tables, location expressions and lists); DIBuilder metadata (DICompileUnit, DISubprogram, DILocalVariable, DILocation); debug records #dbg_declare/#dbg_value (LLVM 19, 2024)	24.4
Memory-management survey	reference counting, Swift ARC (Collins 1960; Swift's ARCOptimization); tracing GC with stack maps and statepoints (McCarthy 1960; Diwan, Moss & Hudson 1992; LLVM gc.statepoint); ownership and borrowing, Rust (Clarke, Potter & Noble 1998; rustc borrowck); regions (Tofte & Talpin 1994; glibc obstack)	24.5
Exception-handling survey (after Lesson 11.7)	funclet-based EH (Windows: MSVC personalities; LLVM catchswitch/catchpad/cleanuppad, WinEHPrepare); WebAssembly EH (Wasm exception-handling proposal, 2023; LLVM WasmEHPrepare); exception-aware optimization: nounwind inference, invoke to call, EH in the inliner (LLVM FunctionAttrs, SimplifyCFG, InlineFunction)	24.6
What's next	MLIR: dialects and progressive lowering by dialect conversion (Lattner et al. 2021); verified compilation: CompCert's simulation proofs (Leroy 2009); translation validation at scale: Alive2 (Lopes et al. 2021), on your pipeline	24.7

flowchart LR
  PM[Pass manager<br/>Ch 12] --> ST[Staged pipeline<br/>enabling relations]
  ST --> CG[Canonicalization gates<br/>SSA, loop-simplify]
  ST --> FX[Fixpoint iteration<br/>change detection]
  ST -->|"what to prove statically"| SE[Static check elimination<br/>Ch 18 BCE]
  SE -->|"cannot prove: choose at run time"| MV[Multiversioning<br/>target_clones, ifunc]
  MV -->|"assume and guard"| SP[Speculation + deopt]
  SP -->|"compile at run time"| JIT[ORC LLJIT]
  JIT --> LZ[Lazy stubs<br/>LLLazyJIT]
  LZ --> TR[Tiered re-optimization]
  SP -.->|"stack maps"| GC[Tracing GC<br/>statepoints]
  DW[DWARF] --> DI[DIBuilder metadata] --> DR[Debug records]
  RC[Reference counting<br/>ARC] --- GC --- OW[Ownership<br/>Rust] --- RG[Regions]
  EH11[Lesson 11.7 tables] --> FN[Funclets] --> WA[Wasm EH]
  EH11 --> EO[EH-aware optimization]
  TV[Ch 12 translation validation] --> A2[Alive2 at scale]
  A2 --- CC[CompCert proofs]
  ST --> ML[MLIR dialect conversion]

Who uses what

System	Technique	Notes
LLVM 23 / Clang	staged default<O1..O3> pipelines with devirt<4> iteration (24.1); target_clones ifunc dispatch, llvm.experimental.deoptimize (24.2); ORC LLJIT/LLLazyJIT/ReOptimizeLayer (24.3); DIBuilder, debug records, DWARF 5 emission (24.4); gc.statepoint stack maps (24.5); funclets, Wasm EH, nounwind inference (24.6)	the substrate of everything Pebble does
GCC 15	passes.def staged pipeline, ipa-pure-const nothrow inference, target_clones, DWARF 5	24.1, 24.6
Swift 6	ARC with owned/guaranteed conventions and the SIL ARC optimizer	24.5
rustc 1.94	ownership and borrowing (rustc_borrowck, NLL), drop elaboration, DWARF through DIBuilder	24.4, 24.5
HotSpot, V8	tiered compilation with deoptimization and OSR (Lesson 0.3); precise tracing GCs with stack maps	24.2, 24.3, 24.5
Wasmtime / Cranelift	one-pass "e-graph" pipeline (Lesson 17.8), stack maps for host GCs, Wasm EH	24.5, 24.6
CompCert 3.15	a verified staged pipeline (driver/Compiler.v) proved by forward simulations	24.7
MLIR (Flang, IREE, CIRCT)	dialects, progressive lowering by dialect conversion	24.7
Pebble	pebble-o1 runs your staged design; ★ pebble-jit, ★ pebble-debugify, ★ pebble-frontend-rust	exercises, labs

Comparison

The fixed columns follow docs/authoring/DEPTH_CONTRACT.md §3 item 8. Each lesson repeats its rows.

Pipeline design (lesson 24.1)

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Staged pipeline by enabling relations	every enabled opportunity is taken once (Theorem 24.1.10); order effects visible (57 vs 49 instructions on the witness)	one run of each pass · pebble-o1 6 stages, 10–20 ms on the benchmarks	predictable, explainable by the stage list	low: a table	every production optimizer (LLVM, GCC, CompCert)
Canonicalization gates	passes see one shape; a pass written for \(\mathcal{C}_{\mathrm{ssa}}\) is correct on every program (Proposition 24.1.8)	mem2reg, loop-simplify, lcssa are near-linear · negligible	fewer special cases in every later pass	low, but the discipline must be kept: re-canonicalize after passes that break the form	LLVM (mem2reg, loop-simplify, lcssa, instcombine's canonical forms)
Fixpoint iteration	reaches every opportunity the passes can expose to each other (Theorem 24.1.12); bounded by the round limit	\(O(k \cdot \lvert w \rvert)\) pass runs for \(k\) rounds · rounds 1–3 in practice (the trace box)	diminishing returns; a change detector is needed	moderate: hashing or change flags	LLVM devirt<4>, InstCombine's worklist, GCC may_iterate, pebble-o1's MaxRounds

Compile-time vs run-time trade-offs (lesson 24.2)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Static check elimination	removes a check iff a proof exists (sound; Theorem 24.2.8): 14 → 12 → 3 traps on bench-checks at -O0/-O1/-O2	compile time only · SCEV queries per check	zero run-time cost for proved checks; the rest stay	moderate (SCEV, dominating conditions)	Java, Swift, Rust, Pebble bounds checks
Multiversioning, run-time dispatch	\(k\) variants, one selected per call or per loop entry	code size \(\times k\); one indirect call or test · cheap	best variant per machine or per input; no correctness risk	low (attributes) to moderate (loop versioning)	target_clones, glibc ifuncs, LoopVersioning
Speculation with deoptimization	any assumption, with a guard; exact recovery (Theorem 24.2.10)	a test per guard; deopt is slow but rare	fastest when assumptions hold; cliffs when they fail	high: side tables, frame reconstruction	HotSpot, V8, llvm.experimental.deoptimize

JIT designs (lesson 24.3)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
ORC LLJIT (eager)	whole module compiled on first lookup; symbols resolved by JITDylib search order	compile everything up front (4 of 4 functions on the running example)	simplest; startup pays for unused code	low (LLJITBuilder)	lli, pebble-jit, Julia's base JIT
Lazy compilation (stubs)	one materialization unit per function; a function compiles at its first call (2 of 4)	startup proportional to what runs	one indirection per not-yet-compiled call, then patched	low with LLLazyJIT; moderate by hand	lli -jit-kind=orc-lazy, Kaleidoscope
Tiered re-optimization	recompile hot functions at higher -O with profile facts (Algorithm 24.3.6)	pays compile time only where it matters (nbody: 100 ms at -O0 vs 62 ms at -O2 in the JIT)	best steady-state; needs counters and redirection	high (ReOptimizeLayer, RedirectableSymbolManager)	HotSpot, V8, .NET, ORC's ReOptimizeLayer

Debug information (lesson 24.4)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
DWARF	describes any variable location (expression language, Theorem 24.4.6)	tables read lazily by the debugger · object size grows 2–5×	gdb prints Pebble variables (the box)	high to write by hand; LLVM emits it	every Unix toolchain, LLDB, GDB
DIBuilder metadata	scopes, types, variables, locations as IR metadata	linear in the IR	the source of every DWARF DIE	low: builder calls	Clang, rustc, Swift, pebble-debugify
Debug records	variable values per program point, surviving mem2reg; passes unaffected (Lesson 9.6)	no instruction-count effect	location lists at -O2 (the box); "optimized out" where values die	low to emit; passes must preserve them	LLVM 19+ IR; -g everywhere

Memory management (lesson 24.5)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Reference counting (ARC)	frees at the last release (Theorem 24.5.11); cycles leak	a retain/release per reference copy; ARC removes pairs	deterministic destruction; no pauses	moderate (compiler) + low (runtime)	Swift, Objective-C, Python's first line of defense
Tracing GC with stack maps	frees everything unreachable; needs exact roots (Theorem 24.5.12)	zero cost on copies; pauses or barriers	moving collectors need relocation of every live pointer (the stack-map box)	high: runtime + compiler support	Java, Go, V8, OCaml, Wasm hosts
Ownership (Rust)	no run-time work at all; rejects some correct programs	compile-time only	errors at compile time (the rustc box)	high in the type system; drop elaboration in the compiler	Rust, Cyclone's unique pointers
Regions	frees a whole region in \(O(1)\) (Proposition 24.5.13)	bump allocation; no per-object free	long-lived regions retain garbage	low (a library) to high (inference)	glibc obstacks, Apache pools, arenas in compilers, Cyclone, MLKit

Exception-handling survey (lesson 24.6)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Funclet EH	handlers as outlined functions with their own frames; exact nesting (Theorem 24.6.10)	zero cost on the happy path; a funclet call per handler	Windows SEH interop (__CxxFrameHandler3)	high: WinEHPrepare coloring and outlining	MSVC ABI, Clang on Windows
WebAssembly EH	structured try/catch instructions; no unwinder tables	zero cost; the engine unwinds	portable across engines	moderate: WasmEHPrepare	Emscripten, wasm32 targets
EH-aware optimization	nounwind inference removes unwind edges (Proposition 24.6.6)	cheap analyses	smaller code, more inlining	low	LLVM FunctionAttrs, GCC ipa-pure-const

What's next (lesson 24.7)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
MLIR dialect conversion	legality-driven rewriting to a target dialect (Theorem 24.7.7)	pattern-driven; worklist	mixed-dialect IR at every stage	a framework: high once, low per lowering	Flang, IREE, CIRCT, Triton
CompCert (verified compilation)	a machine-checked proof for every compilation (Theorem 24.7.8)	the compiler runs normally; proofs are static	no miscompilation, by construction	very high (proof engineering)	safety-critical C
Alive2 (translation validation)	per-run refinement check, bounded loops	SMT time, seconds to minutes per function	counterexamples with inputs (the box)	none for the user; the tool exists	LLVM's own test suite, your pebble-o1 output

Measured (reproduce: uv run python labs/ch24-capstone/provided/bench.py --pebblec build/<preset>/bin/pebblec --markdown labs/ch24-capstone/inputs/bench/*.pbl; full table in benchmark.md). On this container (x86-64, LLVM 23.1.2, minimum of 5 runs): the geometric-mean speedup of your -O1 over -O0 on the eight benchmarks is 3.6×, LLVM's -O2 over -O0 is 4.1×, so -O2 runs in 89 % of -O1's time on the geometric mean (from 1.42× vs 1.61× on bench-fib to 8.2× vs 9.5× on bench-matmul); -O1 leaves 1.3× the LLVM instructions of -O2 on the mean (0.7× on bench-matmul, where -O2 unrolls, to 1.9× on bench-fib); compile time is 1.2–2.2× that of -O0 for -O1 and 1.3–2.9× for -O2.

Route through this chapter

Step	What	Techniques	How it is exercised
1	Lesson 24.1	staged pipelines, canonicalization gates, fixpoint iteration	drill pass-order; E1: designCoursePipeline; ch24.Pipeline.*, ch24.e2e-ch11
2	Lesson 24.2	static elimination, multiversioning, speculation	quiz; the fuzz and benchmark lab E2
3	Lesson 24.3	LLJIT, lazy stubs, tiering	★ J1 pebble-jit (labs/ch24-jit)
4	Lesson 24.4	DWARF, DIBuilder, debug records	drill dwarf-location; ★ E3 pebble-debugify
5	Lesson 24.5	ARC, tracing GC, ownership, regions	drills refcount-trace, gc-roots; quiz
6	Lesson 24.6	funclets, Wasm EH, EH-aware optimization	quiz ("find it in LLVM")
7	Lesson 24.7	MLIR, CompCert, Alive2	quiz; alive-tv on your IR
8	Lab labs/ch24-capstone/ (exercises)	the generator L1; fuzzing and benchmarking your -O1 vs -O0 vs -O2	./course test 24; fuzz.py, bench.py
9	★ labs/ch24-rust-frontend/	a second front end held to the conformance suite	ch24.rust-e2e-* (needs cargo)
10	Final exam	all chapters	./course quiz 24 (cumulative; ≥ 80 % to finish the course)

Practice and check

./course drill pass-order --difficulty easy       # warm up; --solution shows every step
./course drill gc-roots                            # liveness at safepoints
./course drill dwarf-location                      # the DWARF stack machine, location lists
./course drill refcount-trace                      # naive ARC by hand
./course flash 24                                  # daily, a few minutes
./course quiz 24                                   # the cumulative final exam
./course test 24                                   # E1, L1 and the end-to-end suites; ★ parts labelled star
./course status                                    # done = quiz ≥ 80 % and tests pass

Where to go from here

You have written a compiler: a lexer, two parsers' worth of theory, a type checker, a lowering to a mid-level IR, a code generator, and an optimizer whose passes you can now order, iterate, fuzz, benchmark and validate. Three directions continue from here.

• Go deeper into LLVM. The pieces you used as black boxes are open: read PassBuilderPipelines.cpp with Lesson 24.1's vocabulary and try to improve default<O2> on your benchmarks; write a MachineFunctionPass for the back end of Chapters 21–23; contribute a fix to a pass you fuzzed. The LLVM Developer Policy and the llvm/docs/ pages cited in this chapter's references are the path in.
• Go up: MLIR. Lesson 24.7 shows that Pebble's front end and PIR already have the shape of a dialect. Rebuilding PIR as an MLIR dialect, with pebble-lower as a dialect conversion, is a two-week project that teaches the modern way to build domain compilers (the MLIR tutorial "Toy" is the starting point).
• Go formal. Run alive-tv over every -O1 output of the fuzzer (Lesson 24.7); then read the first three chapters of Leroy's Formal verification of a realistic compiler and CompCert's Compiler.v. The gap between "tested on 10 000 programs" and "proved for all programs" is where compiler research stands today.

Two small things remain in the course tree for you: the ★ labs you skipped, and tests/ch11/e2e/, which welcomes the two programs of your own that Chapter 11's E4 asked for. Thank you for building Pebble.

References

The chapter's annotated bibliography (papers, textbook sections, pinned LLVM, GCC, Swift, rustc and CompCert source files, documentation) is in references.md. Start with: [WS97] (enabling relations), [LLVM-PBP] (the pipeline you are improving on), [LLVM-ORC] and [LLVM-Statepoints] (the JIT and GC substrate), [DWARF5] (the format debuggers read), [HCU92] (deoptimization), [Ler09] (CompCert) and [LLH+21] (Alive2).