Skip to content

Compilers & LLVM — From Theory to a Working Compiler

Course proposal · status: approved (2026-09-24). This document is the blueprint the lesson-building subagents follow. Decisions are recorded in §8.

1. At a glance

  • 25 chapters in 6 parts, from lexing to instruction scheduling. The front end gets 7 chapters; IR, analysis, optimization, LLVM and the back end get 16.
  • Width and depth everywhere (§6.0). Every chapter surveys the family of modern techniques for its problem, never just one. Each technique is taught to the same depth: full algorithm, a traced worked example, a correctness argument, complexity, variants, production use and a comparison. Every chapter also has a lab that implements competing techniques side by side.
  • One project that grows chapter by chapter: pebblec, a compiler for Pebble, a small statically typed language. It is built with C++23 against LLVM 23, with macOS as the primary platform and Linux also supported. A language-neutral front-end interface (§5.8) lets a future Rust front end plug in without touching the middle end, so the result is real native executables optimized by your own LLVM passes.
  • Every chapter has the same loop:
  • a lesson (theory, worked examples, diagrams)
  • an auto-graded theory test
  • randomized drills with unlimited practice problems, graded by an oracle
  • flashcards for memorization
  • implementation exercises with automated tests
  • a guided reading of the matching LLVM source
  • Tests use LLVM itself as the judge wherever possible: your dominator tree vs llvm::DominatorTree, your loops vs LoopInfo, your SSA construction vs mem2reg. They run over a corpus plus thousands of random CFGs. Every transformation is also checked by running the program before and after.
  • Design target: each chapter takes about 1–3 weeks of part-time study. There is an IR/optimization fast track that uses the provided solution front end, so you can go straight to the middle end.

2. What should be covered — research summary

I compared the topic order of well-regarded compiler courses and books:

  • Cornell CS 6120 (Sampson, self-guided, 2025 fall): CFGs → local optimization (DCE, LVN) → data flow → dominators/loops → SSA in and out → LLVM passes → loop optimization → interprocedural and alias analysis → GC, JITs. Uses its own teaching IR (Bril).
  • CMU 15-745 (2024): LLVM → local optimization → data flow → SSA and SSA optimizations → LICM/induction variables → PRE → pointer analysis → register allocation → scheduling.
  • Stanford CS 143 / CS 243: lexing → LL(1)/recursive descent → bottom-up → type checking → codegen (CS 143); data flow → PRE → scheduling → SSA → pointer analysis → interprocedural (CS 243).
  • LLVM-based assignments: UofT CSCD70 (data flow, LICM, SCEV, register allocation in LLVM), UIUC CS 426 (a language compiled to LLVM IR plus an LLVM register allocator), Michigan EECS 583 (profiling pass → profile-guided LICM).
  • Books: Engineering a Compiler 3e; SSA-based Compiler Design (2022); Static Program Analysis (Møller & Schwartzbach); Crafting Interpreters; LLVM Code Generation (Colombet, 2025, written against LLVM 20); Learn LLVM 17.
  • Official LLVM material: Kaleidoscope, "Writing an LLVM Pass" (new pass manager), the Testing Guide (lit/FileCheck), the GEP FAQ, the Undefined Behavior manual, MemorySSA, GlobalISel; llvm-tutor for hands-on pass examples.

Consensus core (almost every source): phases and IRs; regex → NFA → DFA; CFGs, recursive descent, FIRST/FOLLOW and LL(1), an LR overview; scopes and type checking; three-address code, basic blocks and CFGs; local optimization (LVN, DCE, folding); data-flow analysis (lattices, monotone frameworks, worklist; liveness, reaching definitions, available expressions); dominators, dominance frontiers and loops; SSA construction and destruction; SSA optimizations (SCCP, GVN, ADCE); LICM and induction variables; alias analysis; interprocedural analysis and inlining; instruction selection, scheduling and register allocation.

Modern topics worth including (fewer sources, but important in 2026): - poison/undef/freeze semantics and translation validation with Alive2 - Braun et al.'s SSA construction - block arguments as an alternative to phi (Swift SIL, MLIR, Cranelift) - MemorySSA and ScalarEvolution - GlobalISel vs SelectionDAG - e-graphs (egg, Cranelift's aegraphs) - sea-of-nodes (and V8 leaving it in 2025) - MLIR

LLVM-specific churn is real — opaque pointers since 15, debug records in 19, GEP canonicalization toward byte offsets, and the pass-mixin API still changing on main. That argues for pinning one LLVM version for the whole course.

The syllabus below covers the entire consensus core, puts about 70 % of the effort on IR, analysis, optimization and LLVM, and marks the advanced topics as theory-only or optional deep dives.

3. Implementation language: C++ vs Rust vs Swift

The deciding question is what language lets you write optimization passes and use LLVM's analyses, since that is the heart of this course.

C++ Rust Swift
Build LLVM IR ✅ native IRBuilder ✅ inkwell 0.10 (wraps the C API; releases support LLVM ≤ 22) ⚠️ no maintained bindings: LLVMSwift is dead (LLVM 11, last commit 2023); swiftlang/swift-llvm-bindings is still a work in progress
Use LLVM analyses (DominatorTree, LoopInfo, ScalarEvolution, alias analysis, MemorySSA) ✅ ❌ the C API doesn't expose them ❌
Write your own passes for opt / the pass manager ✅ native pass plugins ⚠️ llvm-plugin crate: release supports LLVM ≤ 18 (master ≤ 20), no built-in analyses, no loop/CGSCC passes ❌ would need C++ shims (Swift's C++ interop can't use uninstantiated templates like PassInfoMixin<T> or IRBuilder<>)
Learning material everything: LLVM docs, Kaleidoscope, llvm-tutor, books, LLVM's own source a few front-end tutorials essentially none for LLVM
Front-end ergonomics good (and LLVM-style RTTI, which you need anyway to read LLVM code) excellent (enums + match, cargo) excellent (enums + pattern matching)
Known friction macOS: build with Homebrew clang, not Apple clang (mixing toolchains crashes) static linking against Homebrew LLVM is broken on macOS (zstd); must pin LLVM to inkwell's range Swift/C++ interop gaps on Linux; no one is doing this in practice
Verifiable in this environment ✅ ✅ ❌ (toolchain not installable here)

Decision: C++23 for the whole course. LLVM's headers compile fine under C++23, and the course code uses modern features: std::expected for errors, std::print, std::ranges, std::span, deducing this, consteval. It does not use C++20 modules, because tooling support alongside LLVM's headers is still unreliable on macOS/Homebrew. - It is the only option that gives native pass plugins. - It lets you check your dominator tree against DominatorTreeAnalysis and use LoopInfo, SCEV and alias analysis. - You can read LLVM's source and docs without translating them. - It matches your stated goal of learning LLVM in C++.

A hybrid (Rust front end + C++ passes) is workable, but not worth it here: two toolchains, linking friction, version lock-step with inkwell, and the front end is the smaller part of this course. Swift should be avoided for LLVM work today. The course will still use the Swift compiler as a case study (SIL, block arguments).

Keeping Rust/Swift on the table for later: - The end-to-end tests are black-box (Pebble source in → program output out). - Textual LLVM IR is language-neutral. - The front end/middle end boundary is designed for this from day one (§5.8). A Rust front end emits the language-neutral PIR and reuses the whole middle end, back end, test suite and your C++ passes.

4. LLVM version & platforms

Decision: LLVM 23 (latest release, 23.1.x), macOS first, Linux second. - macOS (primary): - brew install llvm lit. Homebrew's llvm is 23.1.x and ships headers, CMake config and FileCheck. - The course builds with Homebrew clang (not Apple clang) through a macos CMake preset, because mixing the two toolchains crashes. - Pass plugins link with -undefined dynamic_lookup. - Linux: LLVM 23 from apt.llvm.org (llvm.sh 23 all), plus a linux CMake preset. A devcontainer (Ubuntu 24.04 + LLVM 23) is also provided. - Modern LLVM APIs only: - the new pass manager and plugin API v2 (llvm/Plugins/PassPlugin.h, the LLVM 22+ header) - opaque pointers - debug records - the ORC JIT - no legacy or deprecated APIs - Verification: - Every solution is built and tested against LLVM 23.1.2 in this environment, which runs Linux (installed from conda-forge because apt.llvm.org is blocked here). - CI runs on macOS (Apple Silicon, Homebrew LLVM 23) and on Ubuntu (apt.llvm.org LLVM 23). macOS can only be verified through CI, so the macOS job is treated as the release gate. - Tooling notes: - C test inputs are generated with -Xclang -disable-O0-optnone, because otherwise optnone silently disables your passes. - LLVM is built with -fno-exceptions, so course code reports errors with std::expected rather than exceptions.

5. How the course works

5.1 Anatomy of a chapter

Every chapter follows the same loop — understand → memorize → verify → implement → connect to LLVM:

Piece File Purpose
Technique map chapters/NN-*/README.md The landscape of approaches to the chapter's problem, how they relate, who uses what, and a comparison table.
Lesson units chapters/NN-*/lessons/*.md One unit per technique family, each meeting the depth contract (§6.0): algorithm, traced example, correctness, complexity, variants, production use.
Comparison lab labs/ + tests Two or more competing techniques implemented and measured on the same inputs.
Theory test chapters/NN-*/quiz.yaml Auto-graded questions (single/multi choice, numeric, sets, maps such as "node → idom"). Answers are stored as salted hashes, so reading the file doesn't spoil them.
Drills generated by course drill Unlimited randomized problems (random grammars, CFGs, programs…) checked by a built-in oracle, with step-by-step worked solutions on request. For memorization through repetition.
Flashcards chapters/NN-*/flashcards.tsv Definitions, invariants, algorithm steps, complexities, LLVM API names. Anki-importable, or reviewed in the terminal with course flash (Leitner-box spaced repetition).
Exercises chapters/NN-*/exercises.md + TODOs in code Step-by-step implementation tasks with collapsible hints.
Implementation tests tests/chNN/ GoogleTest unit tests, lit + FileCheck IR tests, end-to-end program tests.
LLVM source reading in the lesson "Find where LLVM does X" tasks pointing at real files, with questions in the quiz.

A chapter counts as done when its quiz score is ≥ 80 % and all its implementation tests pass (course status shows this for every chapter).

5.2 The project: Pebble and pebblec

You build one compiler throughout the course, for Pebble, a small, statically typed, C/Rust-flavored language designed to exercise the optimizer:

struct Point { x: int, y: int }

fn fib(n: int) -> int {
    if n < 2 { return n; }
    return fib(n - 1) + fib(n - 2);
}

fn main() -> int {
    var xs: [int; 10];
    for i in 0..10 { xs[i] = fib(i); }   // bounds-checked, like Swift/Rust
    var total = 0;                        // type inferred
    for i in 0..10 { total = total + xs[i]; }
    print(total);                         // 88
    return 0;
}
  • Types: int (64-bit), bool, float, fixed-size arrays, structs; functions with recursion; extern fn for C interop.
  • Control flow: if/else, while, for i in a..b, break, continue, short-circuit &&/||.
  • Safety checks (array bounds, division by zero) that trap, like Swift/Rust — so the optimization chapters have real redundancy to remove.
  • The full language specification is written in Phase 1 (see §7); exact features may be trimmed to keep codegen manageable.

The course provides stable interfaces (headers for tokens, AST, diagnostics, pass registration), and you fill in the implementations. That keeps tests stable and lets each chapter's tests target exactly one component.

Standalone comparison labs implement competing techniques side by side. Examples: three regex engines; LL(1) vs LR(0)/SLR/LALR/LR(1) tables; Pratt vs shunting-yard vs PEG vs Earley; Algorithm W vs J; CHK vs Lengauer–Tarjan; Cytron vs Braun SSA; hash vs partition GVN; Andersen vs Steensgaard; four register allocators.

5.3 Implementation tests

  • Unit tests — GoogleTest, per chapter (ctest -L ch11).
  • IR tests — lit + FileCheck, the same methodology LLVM itself uses: RUN: opt -load-pass-plugin %plugin -passes=pebble-licm -S %s | FileCheck %s.
  • Semantic-equivalence tests — each transformation test also runs the program before and after your pass (lli) and compares results, so a pass that "looks right" but miscompiles fails.
  • Oracle tests — where LLVM already implements the concept, LLVM is the judge: your dominator tree vs llvm::DominatorTree, your loops vs LoopInfo, your phi count vs mem2reg, your SCC order vs scc_iterator, over a corpus plus thousands of randomly generated CFGs.
  • End-to-end tests — Pebble programs with expected output / exit code / trap, compiled at -O0/-O1/-O2; later, differential fuzzing.

5.4 Theory tests

  • Quizzes (per chapter, ~15–30 questions): interactive (course quiz 11) or file-based (answers/ch11.yaml, graded by course check 11, so CI can grade them too). Wrong answers show an explanation; hashing keeps answers out of sight when you open the file.
  • Drills (generated, unlimited): e.g. "Here is a random CFG — give each node's immediate dominator", "Compute FIRST/FOLLOW for this grammar", "Where do phi nodes go for variable x?", "What's the byte offset of this GEP?", "Run Chaitin–Briggs with K = 3". A Python oracle grades the answer and can print the full worked solution (e.g. every worklist iteration).
  • Part exams: cumulative mixed quizzes at the end of each part, which act as spaced repetition.

5.5 The course CLI

./course doctor          # check toolchain, LLVM version, Python deps
./course test 11         # build + run chapter 11's implementation tests
./course quiz 11         # interactive theory test
./course drill dom       # random dominance problems (list: ./course drill --list)
./course flash 11        # flashcard review (spaced repetition)
./course check 11        # quiz answers + implementation tests → pass/fail
./course status          # progress table for all chapters

5.6 Repository layout

LLVMLearning/
├── README.md                 course home: syllabus, study guide, progress
├── course                    CLI entry point (Python)
├── docs/                     setup (macOS/Linux/Docker), Pebble language spec, conventions
├── chapters/NN-slug/         README.md (lesson) · quiz.yaml · flashcards.tsv · exercises.md
├── pebble/                   YOUR compiler — skeleton with TODOs, grows chapter by chapter
│   ├── include/pebble/       provided interfaces
│   ├── lib/{Lex,Parse,Sema,CodeGen,Passes}/
│   ├── runtime/              tiny C runtime (print, traps)
│   └── tools/pebblec/        the driver
├── labs/                     standalone algorithm labs (regex→DFA, LL/LR toolkit, tiling, regalloc, scheduling)
├── tests/chNN/               unit, lit/FileCheck, and end-to-end tests per chapter
├── solutions/                ⚠ spoilers: complete solutions + plaintext quiz answers (used by CI)
├── tools/course/             quiz engine, drill generators + oracles, progress tracking
└── .github/workflows/ci.yml  macOS + Linux: builds solutions and skeleton; runs every test
Solutions live in a separate top-level solutions/ folder that mirrors the learner tree. A CMake switch lets you build any component from solutions/ instead of your own code (for example -DPEBBLE_USE_SOLUTION=lexer,parser,sema,lower). That means you can skip or defer the front-end chapters and go straight to IR and optimization without being blocked.

5.7 Suggested paths

  • Full course: chapters 0 → 24 in order.
  • IR/optimization fast track: 0 → 8 → 9 → 10 → 12 → 13 → 14 → 15 → 16 → 17 → 18 → (19, 20) → 24, using the solution front end and lowering; come back to 1–7 and 11 later.

5.8 Front-end ↔ IR architecture: built for more than one front end

  Pebble source ─► C++ front end ──────────────┐   (in-process: pebble::Frontend interface)
                   Lex → Parse → Sema → Lower  │
  Pebble source ─► Rust front end (future) ────┤   (out-of-process: emits PIR text on stdout,
                   any language, no LLVM needed │    diagnostics as JSON lines on stderr)
                                               ▼
                 PIR — Pebble Intermediate Representation
                 language-neutral, versioned (pir 1.x), MIR/SIL-style:
                 typed locals, basic blocks, statements, terminators,
                 explicit safety checks; text format + C++ API + verifier
                                               ▼
                 PIR → LLVM IR lowering (C++, shared by every front end)
                                               ▼
                 LLVM IR ─► your passes (plugin) ─► LLVM back end ─► object / executable
  • The contract is PIR, not a C++ header. PIR is a small, documented, versioned mid-level IR modeled on Rust MIR and Swift SIL. Any front end in any language only has to print PIR text; it never needs LLVM bindings. The C++ side parses it, runs the verifier, and lowers it to LLVM IR.
  • pebble::Frontend interface plus a registry. The C++ front end is one registered implementation. ExternalFrontend runs any executable that follows the PIR protocol, so pebblec --frontend=rust foo.pbl works once a Rust front end exists. A plain C API (pebble-c/PIR.h) for in-process FFI builders is planned as a later extension point.
  • A conformance suite any front end must pass:
  • PIR golden tests (normalized output)
  • PIR verifier checks
  • the black-box end-to-end suite The Rust front end will be judged by exactly the same tests as the C++ one.
  • A second entry point: pebblec --from-llvm file.ll accepts LLVM IR directly, for front ends that use inkwell, following the documented runtime ABI (docs/runtime-abi.md).
  • Where it's taught: PIR is introduced as a case study in Ch 8 (IR design). In Ch 11 you write both halves: AST → PIR lowering (front end) and PIR → LLVM IR (shared back end). Ch 24's ★ extension is the Rust front end.

6. Detailed syllabus

6.0 The width-and-depth rule (applies to every chapter)

Width. No chapter teaches a single technique. Each chapter opens with a technique map: the main families of solutions to its problem, how they relate, and which production compilers use which. Then it covers each technique in turn. For example, parsing covers LL, LR, GLR, PEG/packrat, Earley, Pratt and combinators. Type inference covers syntax-directed checking, bidirectional typing, Hindley–Milner and constraint solving. Register allocation covers local, graph coloring, linear scan, SSA-based and PBQP.

Depth. Every technique in the map, including the ones you don't implement, must meet the same depth contract in its lesson:

  1. Problem and motivation: what it solves, its history, and the paper it comes from.
  2. Precise definitions and the algorithm: full pseudo-code, not a sketch.
  3. A worked example traced step by step: every table, set, stack or worklist state is shown.
  4. Invariants and a correctness argument: why it terminates, why it's right, and what the fixed point or loop invariant is.
  5. Complexity: best and worst case, pathological inputs, and what goes wrong at scale.
  6. Variants and refinements: the known improvements and the trade-offs each makes.
  7. Where it lives in real compilers: LLVM, GCC, Clang, rustc, swiftc, V8, HotSpot, Cranelift, tree-sitter and so on, with source-file pointers.
  8. Comparison: a table against the other techniques in the chapter covering power, speed, error quality, implementation effort and typical use.
  9. Assessment: quiz questions, randomized drills with worked solutions, and flashcards that cover it.

Implementation across the width. Every chapter has a comparison lab that implements at least two competing techniques and runs them on the same inputs. The tests check that each one is correct, then the lab measures what differs: speed, precision, table size, number of spills, and so on. The technique the Pebble compiler actually uses is implemented in full. The rest are implemented as labs (★ = optional) or taught to full depth in theory with drills.

A chapter is therefore a folder of lesson units (one unit per technique family) rather than one long page. Expect 1–3 weeks of part-time study per chapter.

Legend: Techniques is the technique map. Build is what you implement. Tests covers both implementation and theory. ★ marks an optional lab.

6.1 Learner feedback folded in after the pilot (2026-09-24)

  • Rigorous theory, written in LaTeX: numbered definitions, lemmas and theorems with proofs (or clearly labelled proof sketches that cite the full proof), and precise notation.
  • Real examples alongside the theory: every technique shows the concept in a real system (actual clang, opt or ANTLR output, rustc or Swift snippets) with a reproducible command.
  • Rich references: each chapter has a curated, annotated bibliography. The website aggregates them into a global bibliography.
  • Minimal lab scaffolding: labs ship a spec (instructions, requirements, input/output formats, what the tests check, hidden hints) plus the smallest possible test contract. Learners design their own data structures and code layout. The solutions stay complete.
  • Tooling: Python dependencies are managed with uv. The course is readable as a local website (./course serve).
  • Process: every chapter is written by an author subagent and then audited by a separate reviewer subagent (docs/authoring/REVIEW_CHECKLIST.md).

Part 0 — Orientation

Ch 0 · Compiler Architectures & Your Toolchain

  • Techniques:
  • Pipeline shapes:
    • classic multi-pass (GCC, Clang)
    • single-pass (Turbo Pascal, TCC)
    • query-based and incremental compilation (rustc queries, Swift's request evaluator, Roslyn, rust-analyzer's salsa)
    • multi-level IR (MLIR)
  • Execution strategies:
    • tree-walking interpreter
    • bytecode VM (stack- and register-based; switch vs threaded dispatch)
    • AOT compilation
    • JIT: method, tracing and tiered (V8, HotSpot, LuaJIT, PyPy)
    • transpilers
  • Retargeting: the m × n argument, LLVM's three-phase design, and how GCC and Cranelift differ.
  • Bootstrapping and self-hosting.
  • LLVM: a tour with clang -emit-llvm at -O0 vs -O2, opt -print-after-all, dot-cfg, llc, lli, and Compiler Explorer.
  • Build: set up the environment and write a first hand-written .ll file. ★ Lab: run the same tiny expression language three ways — tree-walker, stack bytecode VM, and LLVM JIT — and benchmark them.
  • Tests: course doctor; your .ll runs; ★ the three executors agree on random programs. Quiz and drills on architectures and trade-offs.

Part I — Front End (7 chapters)

Ch 1 · Lexical Analysis

  • Techniques:
  • Theory: regular languages; Thompson (regex → NFA); NFA simulation (Pike/Thompson VM); subset construction; lazy (on-the-fly) DFA as in RE2; Brzozowski derivatives and Owens' derivative-based lexers.
  • DFA minimization: Hopcroft, Moore and Brzozowski's double reversal.
  • Implementation styles:
    • hand-written loop and switch (Clang, rustc, swiftc)
    • table-driven DFA (flex)
    • direct-coded DFA (re2c)
    • regex combinators
    • SIMD and bulk-classification lexing (simdjson-style)
  • Disambiguation: maximal munch and rule priority; the quadratic worst case of naive maximal munch and Reps' linear-time fix.
  • Context-sensitive lexing:
    • lexer modes/start conditions (string interpolation)
    • JavaScript / as regex vs division
    • C++ >> in templates
    • Python INDENT/DEDENT
    • raw strings
    • the "lexer hack" for C typedef names
  • Other concerns: keyword recognition (perfect hashing with gperf, tries, switch on length); Unicode (UTF-8 decoding, XID identifiers, normalization); lossless lexing with trivia (Roslyn, Swift's SwiftSyntax, rust-analyzer); incremental relexing for IDEs (tree-sitter).
  • Build: the Pebble lexer, hand-written, with spans, trivia and string-interpolation modes. Comparison lab: one regex engine with three back ends (Thompson NFA simulation, subset-constructed and Hopcroft-minimized DFA, and a derivative-based matcher), plus a generated table-driven lexer for Pebble, benchmarked against your hand-written one.
  • Tests: golden token streams and edge cases; all engines agree with each other and with std::regex on random regexes and strings; minimal-DFA sizes match the expected values. Drills cover ε-closures, subset construction, minimization partitions, derivatives and maximal-munch outcomes.

Ch 2 · Grammars & Top-Down Parsing

  • Techniques:
  • Grammar theory: CFGs; the Chomsky hierarchy; derivations; parse trees vs ASTs vs CSTs; ambiguity and its undecidability; precedence and associativity through grammar layering.
  • Predictive parsing: nullable/FIRST/FOLLOW as fixed points; LL(1) tables and conflicts; strong LL(k) vs full LL(k).
  • Grammar transformations: left-recursion elimination (direct and indirect) and left factoring.
  • Recursive descent: predictive vs backtracking.
  • More powerful top-down methods: LL(*) and ALL(*) as used in ANTLR 4 (adaptive lookahead via ATN simulation).
  • Error recovery: panic mode with FOLLOW-based synchronizing sets, phrase-level recovery, and insertion/deletion repair.
  • Build: LL(1) toolkit lab: grammar → nullable/FIRST/FOLLOW → table → conflicts → table-driven parser with a derivation trace; automatic left-recursion removal and left factoring. Comparison lab: the same grammars parsed by the table-driven LL(1) parser and by a generated recursive-descent parser, and a backtracking recursive-descent parser shown going exponential on adversarial input.
  • Tests: golden sets and tables; conflict detection; transformed grammars must be LL(1) and accept the same language up to a length bound. Drills cover FIRST/FOLLOW, table cells, conflict classification, left-recursion elimination and ALL(*) lookahead decisions.

Ch 3 · Bottom-Up Parsing

  • Techniques:
  • Foundations: shift-reduce parsing, handles and viable prefixes.
  • The LR family: LR(0) items with closure/goto; SLR(1); LALR(1), both by merging LR(1) states and by DeRemer–Pennello lookahead propagation; canonical LR(1); IELR(1) / minimal LR(1) as in Bison; state-count comparisons across the family.
  • Conflicts: shift/reduce and reduce/reduce, precedence and associativity declarations, and when they're safe.
  • Operator-precedence parsing (Floyd) as a historical special case.
  • Generalized LR (GLR): Tomita's algorithm, graph-structured stacks, shared packed parse forests; used in Bison %glr, Elkhound, and in tree-sitter's GLR-style conflict handling.
  • LR error recovery: yacc's error token, Burke–Fisher repair, and Menhir's .messages for hand-written error messages.
  • In practice: why production compilers moved to hand-written recursive descent (GCC's C++ parser rewrite), and where LR generators still dominate.
  • Build: add to the grammar toolkit: LR(0), SLR(1), LALR(1) and LR(1) table construction, one shift-reduce driver for all four, and conflict reports. Comparison lab: state and conflict counts across the four on a grammar corpus. ★ A GLR driver for ambiguous grammars that produces a parse forest.
  • Tests: item sets and tables against golden files; parses agree with the LL(1) toolkit where both apply; each grammar is classified correctly (LR(0), SLR, LALR, LR(1) or none). Drills cover closure/goto, lookahead computation, the ACTION/GOTO table and a shift-reduce trace.

Ch 4 · Parsing in Practice: Expressions, Other Paradigms, Recovery & Syntax Trees

  • Techniques:
  • Expression parsing: precedence climbing, Pratt parsing (binding powers; prefix/infix/postfix/mixfix), Dijkstra's shunting-yard, and the precedence-layered grammar, with proofs that they agree.
  • PEG and packrat parsing: ordered choice and its pitfalls, memoization and linear time, and left recursion in PEGs (Warth et al.).
  • Earley parsing: all CFGs, O(n³) general and linear for most unambiguous grammars; the Leo optimization.
  • Also covered: CYK; GLL; parser combinators (Parsec, nom, chumsky) and their performance and error trade-offs.
  • Error-resilient and incremental parsing: rust-analyzer's resilient LL, tree-sitter's incremental reparsing, and error nodes vs error productions.
  • Syntax-tree design:
    • owning class hierarchies with LLVM-style RTTI (Clang)
    • sum types via std::variant
    • arena/index-based ASTs
    • lossless CSTs with red–green trees (Roslyn, rowan, SwiftSyntax)
    • lowering CST → AST → HIR
  • Syntax extension: macros overview (token-based vs AST-based, hygiene).
  • Build: the Pebble parser (recursive descent plus Pratt) with multi-error recovery and an AST dumper. Comparison lab: the Pebble expression grammar implemented as Pratt, shunting-yard, packrat PEG and Earley recognizers, checked against each other on random expressions and benchmarked. ★ An incremental reparse of an edited function.
  • Tests: golden ASTs; randomized precedence/associativity tests (parse, then evaluate against an oracle); expected diagnostics for malformed input. Drills cover Pratt binding-power traces, shunting-yard stacks, packrat memo tables, Earley charts and "which paradigm accepts this grammar?".

Ch 5 · Names, Scopes & Semantic Analysis

  • Techniques:
  • Scoping: static vs dynamic scope; shadowing.
  • Symbol-table implementations: a stack of hash tables, persistent/functional maps, a single table with scope marks, de Bruijn indices, and scope graphs (Néron et al.).
  • Name-resolution strategies:
    • declare-before-use (C)
    • multi-pass order independence (Java, Rust, Swift)
    • module and import resolution
    • overload resolution (C++, Swift)
    • argument-dependent lookup
    • macro hygiene
  • Attribute grammars: synthesized vs inherited attributes, S- and L-attributed definitions; the theory behind syntax-directed semantic analysis.
  • Where results live: annotating the AST vs side tables vs query-based incremental semantic analysis (rustc, Swift's request evaluator).
  • Desugaring and HIR lowering.
  • Control-flow-sensitive checks: reachability, missing returns, and definite assignment (the Java, C# and Swift rules). These are a preview of dataflow analysis.
  • Diagnostics: spans, notes and fix-its, error recovery and poisoning, and cascades.
  • Build: the Pebble resolver and semantic checks (duplicate and undeclared names, missing returns, break outside a loop, definite assignment). Comparison lab: the same resolver backed by a scope stack, a persistent map and de Bruijn indexing, with correctness compared and costs measured.
  • Tests: a corpus of valid programs and a corpus of invalid ones with the expected error code and location. Drills cover resolving identifiers in nested scopes, attribute-grammar evaluation order and definite-assignment verdicts.

Ch 6 · Type Systems & Type Checking

  • Techniques:
  • Formal foundations: typing judgments and inference rules; soundness via progress + preservation, with proof sketches; strong vs weak and static vs dynamic typing.
  • Checking disciplines:
    • syntax-directed checking (C, Java)
    • bidirectional typing (Pierce–Turner local type inference; Dunfield–Krishnaswami), with synthesis vs checking modes
  • Subtyping: nominal vs structural, variance, top/bottom types, and algorithmic subtyping.
  • Flow-sensitive typing: TypeScript narrowing, Kotlin smart casts, occurrence typing in Typed Racket.
  • Gradual typing: the dynamic type and blame.
  • Also covered: implicit conversions and numeric promotion; overloading; l-values, mutability and references.
  • Implementing generics:
    • monomorphization (C++, Rust)
    • erasure/boxing (Java)
    • dictionary passing / witness tables (Haskell, Swift)
  • Ownership and borrowing: an overview of Rust's NLL borrow checking as a dataflow problem on MIR (a link to Part III).
  • Build: the Pebble type checker (bidirectional, with a typed AST, casts and precise diagnostics). Comparison lab: the same small language checked by a purely syntax-directed checker and by a bidirectional one, comparing annotation burden and error quality. ★ Structural subtyping with variance for records.
  • Tests: well-typed programs with golden typed-AST dumps; ill-typed programs with the expected errors. Drills cover building and checking derivations, mode assignment in bidirectional rules, subtyping queries and narrowing results.

Ch 7 · Type Inference

  • Techniques:
  • Unification algorithms: Robinson, Martelli–Montanari and union-find based, and the occurs check.
  • Hindley–Milner: Algorithm W vs Algorithm J (in-place union-find), Algorithm M, let-polymorphism and generalization, level-based generalization (OCaml), the value restriction, and complexity (DEXPTIME-complete in theory, near-linear in practice).
  • Constraint-based inference: HM(X) and OutsideIn(X) in GHC.
  • Swift's constraint solver: why some expressions take exponential time, and the mitigations.
  • Also covered: local and flow-based inference in Rust, Kotlin and TypeScript; type classes and traits (instance resolution, coherence, dictionary passing vs monomorphization); higher-rank and impredicativity (overview); error localization in inference.
  • Build: a type-inference lab for a mini-ML. Comparison lab: Algorithm W vs Algorithm J (with levels) on the same programs, checking identical principal types and comparing performance on deep let nesting. Pebble then gets local inference for let bindings and numeric literals. ★ Type classes via dictionary passing.
  • Tests: principal types against golden answers; failure cases (occurs check, mismatches). Drills cover unification (MGU or failure), W/J traces and generalization decisions.

Part II — Intermediate Representations & LLVM

Ch 8 · The Design Space of Intermediate Representations

  • Techniques:
  • Linear IRs: three-address code (quadruples, triples, indirect triples); stack bytecode (JVM, Wasm, CPython); register bytecode (Lua, Dalvik).
  • Graph IRs: ASTs/HIR, DAGs, CFG + SSA (LLVM, GCC GIMPLE), block arguments (MLIR, Swift SIL, Cranelift), sea of nodes (HotSpot C2, Graal) and why V8 left it, PDG/VSDG/RVSDG.
  • Functional IRs: CPS and ANF (SML/NJ, GHC), and the SSA ≡ ANF correspondence (Kelsey; Appel's "SSA is Functional Programming").
  • Also covered: e-graphs as an IR; MLIR's multi-level dialects and progressive lowering.
  • Mechanics: basic blocks and the leaders algorithm; CFGs; critical edges; DFS pre/postorder and reverse postorder.
  • Case studies: Clang (AST, then ClangIR/CIR, then LLVM IR); rustc (HIR → THIR → MIR); swiftc (AST → SIL → LLVM IR); GCC (GENERIC → GIMPLE → RTL).
  • Build: read the PIR specification and write PIR by hand (it's the course's own MIR-style IR). Comparison lab: compile one expression/statement language into stack bytecode, TAC, ANF and a block-argument SSA form, run each on a provided interpreter, and compare instruction counts. Build CFGs from TAC with the leaders algorithm and compute traversal orders.
  • Tests: all four forms agree on random programs; CFG edges and orders are checked. Drills cover leaders, RPO, critical edges, and converting between forms (e.g. phi ↔ block arguments, TAC ↔ ANF).

Ch 9 · LLVM IR in Depth

  • Techniques:
  • The language: modules, globals and linkage; functions, blocks and SSA values; the type system (iN, FP, opaque ptr, arrays, structs, vectors, target extension types); terminators; phi and select.
  • Memory: alloca, load and store; GEP in full (index semantics, inbounds/nuw, the move toward byte-offset getelementptr i8); casts.
  • Calls: calls and invoke, calling conventions, attributes, intrinsics.
  • Other constructs: atomics and the memory model (overview); metadata (TBAA, loop, debug records); data layout and target triples.
  • Semantics: the verifier's invariants; a first look at poison, undef and UB (in full in Ch 13).
  • Comparison: LLVM IR set side by side with GIMPLE, SIL, MIR, Cranelift IR and Wasm on the same function.
  • Build: a set of hand-written .ll exercises (loops with phi, arrays and structs through GEP, switch, varargs printf, invoke), plus "fix the broken IR" exercises driven by verifier errors.
  • Tests: each program is linked with a C driver and run on many inputs; FileCheck structural rules. Drills cover GEP byte offsets, validity and dominance checks, and attribute semantics.

Ch 10 · The LLVM C++ API

  • Techniques:
  • Object model: the ownership model (Context, Module, Function, BasicBlock, Instruction); Value/User/Use and def-use chains; RAUW.
  • Building IR: IRBuilder, including insertion points, folders (constant vs no-folder) and inserters.
  • Casting: LLVM-style RTTI (isa/cast/dyn_cast, classof) compared with C++ RTTI, std::variant and visitor patterns (InstVisitor).
  • Pattern matching: the PatternMatch DSL.
  • ADTs and why they exist: SmallVector, DenseMap and its hashing, SetVector, StringRef/ArrayRef/Twine, ilist intrusive lists.
  • Error handling: Error/Expected vs exceptions.
  • Running IR: ways to execute it — lli, the interpreter, MCJIT, ORC LLJIT — and what distinguishes them.
  • Consuming LLVM from CMake.
  • Build: programmatic IR construction; inspection tools; safe rewriting while iterating. Comparison lab: the same analysis written with raw casts, with InstVisitor and with PatternMatch, plus the same function executed through the interpreter and through LLJIT.
  • Tests: GoogleTest checks that the IR verifies and that JIT results are right; FileCheck. Quiz on ownership, invalidation, and cast vs dyn_cast.

Ch 11 · Lowering & Code Generation: AST → PIR → LLVM IR (milestone: native executables)

  • Techniques:
  • SSA generation strategies: tree-walking syntax-directed translation; allocas then mem2reg (Clang); direct SSA construction during codegen (Braun et al.; Cranelift, Go and V8 style), taught here and implemented in Ch 16.
  • Control-flow lowering: boolean values vs jumping code for short-circuit; switch lowering (jump tables vs binary search vs bit tests vs LLVM's switch plus backend lowering); loop shapes (while vs rotated do-while).
  • Expressions: l-value/r-value evaluation.
  • Aggregates and the ABI: by value, sret, byval, and ABI coercion as Clang does it.
  • Safety checks: trap vs unwind vs error return.
  • Exception handling (overview): zero-cost tables with invoke/landingpad vs setjmp/longjmp vs explicit error returns (Swift, Rust).
  • Closure conversion and lambda lifting (overview).
  • Runtime library design; object emission and linking.
  • Build: AST → PIR lowering (front end); PIR → LLVM IR codegen (shared back end); the pebblec driver (--emit=ast|pir|llvm|obj|exe, --frontend=, --from-pir, --from-llvm) and the runtime. Comparison lab: short-circuit as jumping code vs select/boolean evaluation, and three switch lowerings, compared on IR shape and speed.
  • Tests: an end-to-end suite of 60+ programs covering output, exit codes and traps; FileCheck on IR shapes; every module must verify. Drills cover translation schemes: block/edge counts for jumping code and switch-lowering choices.

Part III — Analysis Foundations & SSA

Ch 12 · Passes, Pass Managers & Testing Compilers

  • Techniques:
  • Pass-manager architectures: LLVM's legacy vs new pass manager (analysis caching, invalidation, adaptors, CGSCC); GCC's pass manager; MLIR's nested op-anchored pass manager; plugins and extension points; how -O2 is assembled.
  • Compiler-testing methodologies:
    • FileCheck/lit
    • snapshot and golden tests (Turnt, insta)
    • differential testing
    • random program generation (Csmith, YARPGen, llvm-stress)
    • test-case reduction (C-Reduce, llvm-reduce, delta debugging)
    • translation validation (Alive2)
    • bisection (opt-bisect-limit)
    • fuzzing (libFuzzer on the parser)
  • Build: the pass plugin (an analysis printer, strength reduction, a basic-block counting instrumentation pass). Comparison lab: write the same check as FileCheck, snapshot and differential tests, then reduce a planted miscompile with delta debugging.
  • Tests: lit tests; negative tests; lli equivalence. Quiz on invalidation, pipelines and FileCheck semantics.

Ch 13 · Local Optimization & Transformation Correctness

  • Techniques:
  • Constant folding.
  • Peephole engines: hand-written (InstCombine) vs pattern DSLs (LLVM PatternMatch, GCC match.pd, Cranelift ISLE) vs superoptimization (Massalin, STOKE, Souper).
  • Canonicalization as a design principle.
  • Local value numbering and its extensions: commutativity, identities, memory versions.
  • DAG-based local optimization.
  • Reassociation: ranks (Briggs–Cooper) and tree-height reduction.
  • Correctness:
    • refinement
    • undefined behavior
    • poison vs undef (deprecated) and freeze
    • nsw/nuw/exact flags and dropping them
    • floating-point semantics and fast-math
    • Alive2 and SMT-based verification
    • bounded exhaustive checking
  • Build: passes: constant folding, a flag-aware peephole engine built on PatternMatch, LVN, reassociation. Comparison lab: a hand-coded peephole engine vs a rule-table/DSL-driven one on the same rules. ★ A brute-force superoptimizer for i8 sequences.
  • Tests: a FileCheck test per rule; must-not-transform cases; lli equivalence; instruction-count deltas. Drills cover LVN tables, reassociation ranks, and "is this rewrite valid?" with a counterexample, checked exhaustively.

Ch 14 · Dataflow Analysis & Abstract Interpretation

  • Techniques:
  • Lattice theory: partial orders, lattices, monotone frameworks, fixed points (Kleene, Tarski); MFP vs MOP and distributivity.
  • Solution methods:
    • round-robin
    • worklist, with the effect of RPO/postorder and priority queues
    • bit-vector implementations
    • elimination methods: Allen–Cocke interval analysis, structural analysis, Tarjan's path expressions
    • sparse, SSA-based propagation
  • The four classics: reaching definitions, liveness, available expressions, very busy expressions.
  • Abstract interpretation: abstract domains (signs, constants, intervals, octagons, polyhedra), widening/narrowing, and the Galois-connection view.
  • Declarative analysis: Datalog-based analysis (Soufflé, Doop).
  • Interprocedural preview: IFDS/IDE.
  • Build: a generic dataflow framework with instances (liveness, reaching stores, definite initialization → a pebble-uninit warning pass) and an interval analysis with widening. Comparison lab: round-robin vs worklist (in several orders) vs sparse solving on the same analyses, counting iterations and timing, plus the same analysis written as Datalog rules.
  • Tests: golden IN/OUT results; MFP equals brute-force MOP on random distributive instances; interval soundness checked by concrete executions. Drills cover IN/OUT tables, worklist traces, lattice heights and widening steps.

Ch 15 · Control-Flow Analysis: Dominance & Loops

  • Techniques:
  • Dominator algorithms: iterative dataflow; Cooper–Harvey–Kennedy; Lengauer–Tarjan (simple and sophisticated linking); Semi-NCA (LLVM); incremental dominator updates (LLVM's DomTreeUpdater).
  • Post-dominance.
  • Dominance frontiers: Cytron's, CHK's per-node approach, DJ graphs (Sreedhar–Gao), and iterated DF.
  • Control dependence.
  • Loop detection: natural loops via back edges; Tarjan's and Havlak's loop nesting forests (including irreducible loops); Steensgaard's loop forest.
  • Reducibility: T1/T2 and node splitting.
  • Canonical loop forms: loop-simplify and LCSSA.
  • Build: dominators via CHK and Lengauer–Tarjan; DF computed two ways; post-dominators; loop nesting (natural loops plus Havlak for irreducible CFGs); a reducibility check. Comparison lab: timing on large random CFGs.
  • Tests: everything is checked against LLVM's DominatorTree/PostDominatorTree/LoopInfo on a corpus and thousands of random CFGs. Drills cover dominators, idoms, DF, back edges, loop bodies and reducibility.

Ch 16 · Static Single Assignment Form

  • Techniques:
  • Flavors of SSA: minimal, semi-pruned and pruned SSA.
  • Construction algorithms:
    • Cytron et al. (iterated DF + renaming)
    • Sreedhar–Gao (DJ graphs)
    • Braun et al. (on the fly, with sealed blocks)
    • Aycock–Horspool (build then minimize)
  • Representation choices: phi nodes vs block arguments vs upsilon/phi (Pizlo).
  • Destruction methods:
    • Cytron's naive copies
    • Briggs et al. (the lost-copy and swap problems)
    • Sreedhar's CSSA methods I–III
    • Boissinot et al. (parallel copies, fast interference with value checking)
    • coalescing
  • SSA extensions: SSI/e-SSA (predicates), gated SSA, Memory SSA, Array SSA, Hashed SSA.
  • Case study: LLVM's mem2reg/SROA/SSAUpdater.
  • Build: pebble-mem2reg (Cytron, pruned); Braun-style SSA construction built into pebblec's codegen; out-of-SSA with parallel-copy sequentialization. Comparison lab: Cytron vs Braun on the same programs, comparing phi counts and speed, and naive vs Briggs vs Boissinot destruction by copy count.
  • Tests: verifier; no promotable allocas remain; lli equivalence; phi counts compared with LLVM's mem2reg; exhaustive parallel-copy simulation; the end-to-end suite still passes with your SSA. Drills cover phi placement (minimal and pruned), renaming stacks and destruction puzzles.

Part IV — Optimization

Ch 17 · SSA-Based Scalar Optimizations

  • Techniques:
  • Constant propagation variants: Kildall; simple SSA CP; SCCP (Wegman–Zadeck); range and known-bits analyses (LLVM's LVI, CVP, KnownBits).
  • DCE variants: mark–sweep and aggressive DCE via control dependence.
  • Redundancy elimination:
    • dominator-scoped CSE (EarlyCSE)
    • hash-based GVN
    • partition-based GVN (Alpern–Wegman–Zadeck, Click)
    • NewGVN
  • PRE variants: Morel–Renvoise, lazy code motion (Knoop–Rüthing–Steffen), SSAPRE, GVN-PRE.
  • CFG simplification and jump threading.
  • Phase ordering vs equality saturation: egg; Cranelift's aegraphs.
  • Build: passes: SCCP, ADCE, GVN (hash-based), SimplifyCFG-lite. Comparison lab: hash-based vs partition-based value numbering, and simple CP vs SCCP, compared on how many constants and redundancies each finds on a corpus. ★ LCM on a lab IR; ★ a mini e-graph rewriter.
  • Tests: FileCheck; lli equivalence; the precision ordering must hold (SCCP ⊇ simple CP). Drills cover SCCP lattice traces, value-numbering partitions, and LCM anticipability/availability sets.

Ch 18 · Loop Optimizations

  • Techniques:
  • Code motion: LICM (hoisting, sinking, promoting scalars out of memory, speculation safety).
  • Induction variables: classic detection, scalar evolution (chains of recurrences), trip counts.
  • Strength reduction: Allen–Cocke–Kennedy vs operator strength reduction (Cooper–Simpson–Vick) vs LLVM's LSR; linear-function test replacement.
  • Loop restructuring: rotation, peeling, unrolling, unswitching, versioning, fusion/fission, interchange, tiling.
  • Dependence analysis: GCD, Banerjee, the Omega test; the polyhedral model (Polly).
  • Vectorization: the loop vectorizer and VPlan, SLP, predication, runtime checks.
  • Software pipelining: taught in Ch 22.
  • Bounds-check elimination.
  • Build: passes: LICM; IV recognition + OSR strength reduction. Comparison lab: classic IV detection vs your SCEV-style recurrences, and classic SR vs OSR on the same loops. ★ Unrolling; ★ bounds-check elimination for Pebble loops.
  • Tests: FileCheck (code hoisted into the preheader); lli equivalence; IVs compared with LLVM's SCEV. Drills cover LICM legality, {a,+,b} forms, trip counts and dependence vectors.

Ch 19 · Memory: Alias Analysis & Memory Optimizations

  • Techniques:
  • Local alias rules: type-based (TBAA) and BasicAA-style reasoning.
  • Points-to analysis:
    • Andersen (inclusion constraints; online cycle detection, wave/deep propagation)
    • Steensgaard (unification)
    • Das's one-level flow
    • flow-sensitive analysis (staged/sparse)
  • Sensitivity choices: context sensitivity (call strings vs cloning vs summaries; k-CFA, object sensitivity) and field sensitivity.
  • Also covered: escape analysis; shape analysis (overview); MemorySSA; SROA; DSE; store-to-load forwarding and load PRE; restrict/noalias.
  • Build: comparison lab: Andersen and Steensgaard over the same IR, with precision measured as alias-pair counts and checked for soundness at run time. Passes: DSE and load forwarding on MemorySSA.
  • Tests: soundness (never NoAlias when pointers do alias); the precision ordering (Andersen ⊆ Steensgaard); FileCheck + lli. Drills cover points-to sets under each algorithm and building MemorySSA.

Ch 20 · Interprocedural & Whole-Program Optimization

  • Techniques:
  • Call-graph construction: direct calls, CHA, RTA, VTA, points-to based.
  • Traversal: SCCs; bottom-up vs top-down.
  • Inlining: heuristics and cost models; ML-guided inlining (MLGO).
  • Specialization: cloning and function specialization.
  • Interprocedural analysis: IPSCCP; summary-based vs context-sensitive analysis; IFDS/IDE.
  • Other transforms: attribute inference, dead-argument elimination, argument promotion, devirtualization, tail-recursion elimination, outlining.
  • Whole-program compilation: LTO vs ThinLTO.
  • Profile-guided optimization: instrumentation vs sampling (AutoFDO) vs post-link optimization (BOLT).
  • Build: call graph + SCCs; pebble-inline (your cost model); pebble-funcattrs; pebble-tre. Comparison lab: three inlining heuristics (size threshold, bottom-up cost/benefit, profile-guided with your Ch 12 counters), compared on code size and speed.
  • Tests: SCC order matches scc_iterator; FileCheck; lli equivalence; the end-to-end suite passes. Drills cover SCC orders, CHA/RTA call-graph results and inlining decisions.

Part V — Back End

Ch 21 · Instruction Selection & the LLVM Code Generator

  • Techniques:
  • Selection approaches: macro expansion; maximal munch.
  • Optimal tree tiling: dynamic programming (Aho–Ganapathi–Tjiang) and BURS generators (BURG, iburg).
  • DAG covering: NP-completeness and the heuristics used in practice.
  • LLVM's selectors: SelectionDAG (build → combine → legalize → select → schedule), GlobalISel (IRTranslator → Legalizer → RegBankSelect → InstructionSelect), FastISel.
  • Other frameworks: Cranelift ISLE rewrite rules; e-graph-based selection.
  • Target description: TableGen.
  • Lowering details: calling conventions and frame lowering.
  • The MC layer: assembler, relocations, object formats.
  • Build: tiling lab on a toy RISC ISA (with a provided simulator): macro expansion, maximal munch and DP-optimal tiling. ★ A small BURG-style generator from a rules file. Guided MIR exploration with llc -print-after-all / -stop-after.
  • Tests: the simulator checks correctness; DP ≤ munch ≤ macro-expansion cost, and DP is optimal against brute force on small trees. Drills cover munch vs DP tilings and legalization steps.

Ch 22 · Register Allocation

  • Techniques:
  • Local allocation: Belady / furthest-next-use.
  • Graph coloring: Chaitin, Briggs optimistic coloring, iterated register coalescing (George–Appel), conservative coalescing tests (Briggs, George).
  • Linear scan: Poletto–Sarkar, second-chance binpacking (Traub), and SSA linear scan (Wimmer).
  • SSA-based allocation (Hack): chordal graphs, MaxLive, decoupled spilling.
  • Formulations: PBQP (in LLVM) and ILP-based allocation.
  • LLVM's greedy allocator: splitting, eviction, cascades.
  • Spill-code placement and rematerialization.
  • Constraints: pre-colored registers and calling conventions.
  • Build: comparison lab over SSA LLVM IR used as virtual registers: local, Chaitin–Briggs with IRC, linear scan, and SSA-based coloring in dominance order, all run through one checker and one spill rewriter.
  • Tests: an independent validity checker; lli equivalence after spilling; spill counts and moves compared across allocators. Drills cover interference graphs, simplify/select traces, coalescing verdicts and linear-scan outcomes.

Ch 23 · Instruction Scheduling & Machine-Level Optimization

  • Techniques:
  • Dependence DAGs: true, anti and output dependences.
  • List scheduling: top-down vs bottom-up; priority functions such as critical path and register pressure.
  • Region scheduling: trace and superblock scheduling.
  • Software pipelining: modulo scheduling (Rau's iterative approach), MII from resources and recurrences.
  • In LLVM: the MachineScheduler, post-RA scheduling, machine models.
  • Machine-level transforms: if-conversion and predication; block placement; machine peepholes.
  • Post-link optimization: BOLT.
  • Build: comparison lab: top-down vs bottom-up list scheduling with different priorities; modulo scheduling for simple loops.
  • Tests: schedules respect all dependences and resources; length is compared with lower bounds; the II achieved is compared with MII. Drills cover critical paths, list-scheduling traces and MII computation.

Part VI — Capstone

Ch 24 · The Complete Pebble Compiler — and Beyond

  • Techniques:
  • Pipeline design: ordering, iteration and canonicalization.
  • Compile-time vs run-time trade-offs.
  • JIT designs: ORC LLJIT, lazy compilation, tiering.
  • Debug info: DWARF, and DIBuilder vs debug records.
  • Memory-management survey:
    • reference counting (Swift ARC)
    • tracing GC with stack maps and statepoints
    • ownership (Rust)
    • regions
  • Exception-handling survey.
  • What's next: MLIR; formal verification (CompCert, Alive2).
  • Build: pebblec -O1 running your pipeline end to end; differential fuzzing with a random Pebble program generator; a benchmark report comparing your pipeline with LLVM's -O2. ★ JIT REPL; ★ debug info; ★ a Rust front end emitting PIR, plugged in via --frontend=rust and held to the same conformance suite.
  • Tests: the whole end-to-end suite at -O0/-O1/-O2 with identical results; a fuzzing run; a cumulative final exam.

7. Build plan (after approval)

Phase 1 — Foundation (me, plus one or two subagents; must be sequential because everything depends on it) - Pebble language specification; provided interfaces (tokens, AST, diagnostics, pass registry). - CMake build (LLVM discovery, RTTI/flags matching the LLVM build, GoogleTest, pass-plugin target, lit configuration, PEBBLE_USE_REFERENCE switch). - course CLI: quiz engine (hashed answers, explanations), drill framework with oracles, flashcards, status, doctor. - Chapter template and style guide (so 25 chapters written by different subagents read as one course, and every technique meets the depth contract). - CI workflow (GitHub Actions, macOS + Linux, LLVM 23): build solutions/ → all tests must pass; build the skeleton → it must compile and its tests must fail cleanly; validate quiz hashes against the plaintext answers. - Setup docs for macOS and Linux, plus a Dockerfile/devcontainer.

Phase 2 — Pilot: Ch 2 (top-down parsing) and Ch 15 (dominance & loops), one front-end and one middle-end chapter, each built to the full width-and-depth contract. You review them, and I adjust the template before fanning out.

Gate: Phase 3 does not start until you have reviewed the pilot and explicitly asked for the remaining chapters.

Phase 3 — Fan-out. Subagents run in parallel, each in an isolated git worktree. Every chapter agent delivers the lesson, quiz, drills and oracles, flashcards, exercises, skeleton, solution and tests, and must show that the solution passes and the skeleton fails. I review and merge each wave, and CI stays green.

Wave Chapters Why this grouping
A 0, 1, 3, 8, 9, 10, 14 independent of each other (grammar toolkit comes from the pilot)
B 4, 12, 13, 16, 21 4 needs the lexer; 16 needs dataflow (14) + dominance (15)
C 5, 17, 18, 19, 22 5 needs the parser; 22 reuses liveness (14)
D 6, 7, 20, 23 type checking follows name resolution
E 11, then 24 codegen needs the typed AST; the capstone needs everything
F integration review cross-references, consistency, a depth-contract audit per technique, full CI run, fresh-clone walkthrough

All work lands on claude/lucid-clarke-g8eb4h. No other branches are pushed unless you allow it.

8. Decisions (resolved 2026-09-24)

  1. Language: C++23 everywhere. The front end/IR boundary is language-neutral (PIR, §5.8), ready for a future Rust front end.
  2. LLVM: 23 (latest), using only modern APIs. macOS first, Linux second.
  3. Solutions: a separate top-level solutions/ folder.
  4. Rollout: pilot first. The foundation plus Ch 2 and Ch 15 are built, then work stops for your review. Your feedback is folded into the template, and the remaining 23 chapters are built in waves only after you explicitly say to build them.
  5. Name: Pebble / pebblec.