Compilers & LLVM — From Theory to a Working Compiler¶

Status: complete. All 25 chapters are written and independently reviewed; ./course status tracks your progress through them.

A self-paced course that takes you from lexing to instruction scheduling. By the end you'll have built pebblec, a compiler for Pebble, a small statically typed language, in C++23 against LLVM 23. It produces native executables optimized by your own LLVM passes.

25 chapters in 6 parts. About 70 % of the effort goes to IR, analysis, optimization, LLVM and the back end.
Width and depth. Every chapter surveys the whole family of techniques for its problem: LL, LR, GLR, PEG, Earley and Pratt for parsing; iterative, Cooper–Harvey–Kennedy, Lengauer–Tarjan and Semi-NCA for dominators. Each technique is taught to the same depth: full algorithm, a traced example, a correctness argument, complexity, variants, where real compilers use it, and a comparison. A comparison lab implements competing techniques side by side.
LLVM is the judge wherever it can be: your dominator tree vs llvm::DominatorTree, your loops vs LoopInfo, your SSA vs mem2reg. The comparisons run over a corpus and thousands of random inputs, and every transformation is also checked by running the program before and after.
macOS first (Apple Silicon, Homebrew LLVM and clang). Linux and a devcontainer are also supported.

The full design, syllabus and rationale are in docs/PROPOSAL.md.

Quickstart¶

Set up your machine first. Follow the guide for your platform:
docs/setup/macos.md (primary: Homebrew LLVM 23 + Homebrew clang; never Apple clang)
docs/setup/linux.md (apt.llvm.org LLVM 23)
docs/setup/devcontainer.md (Ubuntu 24.04 + LLVM 23, nothing to install locally)

If something goes wrong, see docs/setup/troubleshooting.md. 2. Create the Python environment and check the toolchain. Python dependencies (lit, PyYAML, the website tools) are managed by uv from pyproject.toml + uv.lock:

brew install uv                 # Linux: curl -LsSf https://astral.sh/uv/install.sh | sh
uv sync                         # creates .venv/ with the exact locked versions
./course doctor

Every line should be ✓. Each ✗ comes with the command that fixes it. (./course runs itself through uv run, so you never need to activate .venv.) 3. Open the course website — the lessons, math, diagrams, flashcards, quizzes and bibliography in your browser:

./course serve                  # http://127.0.0.1:8000 (reloads as files change)

To put it online, see docs/setup/hosting.md (Vercel is pre-configured). 4. Build and run a chapter's tests:

./course test 0          # configures with the macos/linux CMake preset, builds, runs ctest -L ch00

5. Start Chapter 0: chapters/00-architectures/README.md. The full index is in chapters/README.md.

How to study a chapter¶

Every chapter runs the same loop: understand → memorize → verify → implement → connect to LLVM.

Step	What you do	Command
1. Map	Read the chapter's `README.md`: the problem, the family of techniques, and the comparison table.	—
2. Learn	Work through `lessons/` one technique family at a time. Trace every worked example yourself before reading the table.	—
3. Drill	Solve randomized problems until they're boring. Ask for the step-by-step solution when you're stuck.	`./course drill <name>`
4. Memorize	A few minutes of flashcards a day (Leitner boxes; due cards first).	`./course flash NN`
5. Build	Do `exercises.md`: fill in the `PEBBLE_TODO`s in `pebble/` and the comparison lab.	`./course test NN`
6. Check	Take the theory test, then confirm the chapter is done.	`./course quiz NN`, `./course status`

A chapter is done when its quiz score is ≥ 80 % and all its implementation tests pass. ./course status tracks this for every chapter. Expect 1–3 weeks of part-time study per chapter.

The `course` command¶

Command	What it does
`./course doctor`	Checks uv and the synced Python environment, PyYAML, lit, the website tools, CMake, Ninja, LLVM 23, FileCheck, the compiler (Homebrew clang on macOS) and GoogleTest, and prints fixes. Honors `PEBBLE_LLVM_ROOT` / `LLVM_DIR`.
`./course test NN [--solution] [--preset P]`	Configures + builds + runs `ctest -L chNN`. `--solution` builds the reference solutions in a separate build directory.
`./course quiz NN`	Interactive theory test, with an explanation after every answer. Your best score is saved.
`./course quiz template NN -o answers/chNN.yaml` · `./course quiz grade NN`	File-based quiz: fill in an answers file, then grade it (also usable in CI).
`./course drill list` · `./course drill <name> [--seed N] [--difficulty easy\\|medium\\|hard] [--solution]`	Unlimited randomized problems graded by an oracle, with partial credit, precise feedback and step-by-step worked solutions.
`./course flash NN` · `./course flash export`	Spaced-repetition flashcards in the terminal, or export them to Anki.
`./course status`	Progress table: quiz best, drills practiced, last test result, done.
`./course check NN`	Grades `answers/chNN.yaml` and runs the tests, then gives one pass/fail verdict.
`./course serve` · `./course site build`	Read the course as a local website (MkDocs Material, http://127.0.0.1:8000), or build the static site into `build/site/` (strict).
`./course refs build\\|verify [NN]`	Regenerate / check a chapter's `references.md` from its annotated `references.yaml`.
`./course validate`	Course-integrity checks (used by CI and chapter authors).

Learner state (scores, flashcard boxes, test results) lives in .course/, which is never committed.

Syllabus¶

Part	Ch	Chapter	Highlights
0	0	Compiler Architectures & Your Toolchain	Pipeline shapes, interpreters vs VMs vs AOT vs JIT, retargeting, and a first tour of the LLVM tools.
I	1	Lexical Analysis	Regex to NFA to DFA, minimization, derivatives, maximal munch, context-sensitive and lossless lexing.
I	2	Grammars & Top-Down Parsing	CFGs and ambiguity, nullable/FIRST/FOLLOW, LL(1) tables, grammar transformations, recursive descent, ALL(*).
I	3	Bottom-Up Parsing	Shift-reduce, the LR family (LR(0), SLR, LALR, LR(1), IELR), conflicts, GLR and LR error recovery.
I	4	Parsing in Practice: Expressions, Other Paradigms, Recovery & Syntax Trees	Pratt and shunting-yard, PEG/packrat, Earley, resilient and incremental parsing, and syntax-tree design.
I	5	Names, Scopes & Semantic Analysis	Scoping, symbol-table designs, name-resolution strategies, attribute grammars and definite assignment.
I	6	Type Systems & Type Checking	Typing judgments and soundness, syntax-directed vs bidirectional checking, subtyping, narrowing, generics.
I	7	Type Inference	Unification, Hindley-Milner (Algorithms W, J, M), constraint-based inference, and Swift's solver.
II	8	The Design Space of Intermediate Representations	TAC, bytecode, CFG+SSA, block arguments, sea of nodes, CPS/ANF, MLIR; leaders, CFGs and traversal orders.
II	9	LLVM IR in Depth	Modules, types, SSA values, GEP in full, calls and attributes, metadata, and the verifier's invariants.
II	10	The LLVM C++ API	Ownership, Value/User/Use, IRBuilder, LLVM-style RTTI, PatternMatch, ADTs, Error/Expected, ORC LLJIT.
II	11	Lowering & Code Generation: AST → PIR → LLVM IR	SSA generation strategies, control-flow and switch lowering, aggregates and the ABI; native executables.
III	12	Passes, Pass Managers & Testing Compilers	Pass-manager architectures, plugins, FileCheck/lit, differential testing, reduction, Alive2 and fuzzing.
III	13	Local Optimization & Transformation Correctness	Folding, peephole engines, canonicalization, LVN, reassociation, and poison/undef/freeze refinement.
III	14	Dataflow Analysis & Abstract Interpretation	Lattices and monotone frameworks, worklist and elimination solvers, the four classics, intervals, Datalog.
III	15	Control-Flow Analysis: Dominance & Loops	Iterative, Cooper-Harvey-Kennedy and Lengauer-Tarjan dominators, frontiers, loop forests and reducibility.
III	16	Static Single Assignment Form	Minimal/pruned SSA, Cytron vs Braun construction, phi vs block arguments, destruction and SSA extensions.
IV	17	SSA-Based Scalar Optimizations	SCCP, ADCE, EarlyCSE and GVN variants, PRE/LCM, SimplifyCFG, and equality saturation.
IV	18	Loop Optimizations	LICM, induction variables and SCEV, strength reduction, loop restructuring, dependence analysis, vectorization.
IV	19	Memory: Alias Analysis & Memory Optimizations	TBAA and BasicAA, Andersen vs Steensgaard, sensitivity choices, MemorySSA, DSE and load forwarding.
IV	20	Interprocedural & Whole-Program Optimization	Call graphs (CHA/RTA), SCC traversal, inlining cost models, IPSCCP, attribute inference, LTO and PGO.
V	21	Instruction Selection & the LLVM Code Generator	Maximal munch vs DP tiling, BURS, SelectionDAG vs GlobalISel, ISLE, TableGen and the MC layer.
V	22	Register Allocation	Local, Chaitin-Briggs/IRC, linear scan, SSA-based and PBQP allocation, and LLVM's greedy allocator.
V	23	Instruction Scheduling & Machine-Level Optimization	Dependence DAGs, list scheduling, trace/superblock scheduling, modulo scheduling, MachineScheduler, BOLT.
VI	24	The Complete Pebble Compiler — and Beyond	Your own -O1 pipeline end to end, differential fuzzing, JIT designs, debug info, memory management.

Choose your path¶

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. Skip the front end by building it from the reference solutions, then come back to 1–7 and 11 later:
```
./course test 15 -D PEBBLE_USE_SOLUTION=lexer,parser,sema,lower
```
PEBBLE_USE_SOLUTION takes a comma- or semicolon-separated list of component switches, or all. ./course doctor lists the switches your build knows about, after the first configure.
Mix and match: every component can come from your code or from solutions/, so you're never blocked by an earlier chapter you skipped.

Solutions and spoilers¶

solutions/ mirrors the learner tree and contains complete reference implementations and the plaintext quiz answers (solutions/quizzes/). CI uses it to prove that every exercise is solvable and every quiz is consistent.

Don't browse it while you're working on a chapter. Use the hints in exercises.md first. The drills' --solution flag gives worked solutions for practice problems without spoiling the exercises.
The published quizzes (chapters/*/quiz.yaml) store answers as salted hashes and explanations base64-encoded, so opening them doesn't spoil anything by accident.
./course test NN --solution runs the reference solution in its own build directory without touching your code. That's useful to confirm that a failing test is your bug and not your toolchain.

Repository layout¶

README.md                  this page
course                     the CLI (Python ≥ 3.11; runs through uv)
pyproject.toml, uv.lock    Python dependencies (uv): lit, PyYAML, MkDocs Material for the website
mkdocs.yml, tools/site/    the course website, built in place from the Markdown below
chapters/NN-slug/          README (technique map) · lessons/ · exercises.md · flashcards.tsv · quiz.yaml
pebble/                    YOUR compiler: provided interfaces + skeletons with PEBBLE_TODO
labs/chNN-*/               standalone comparison labs
tests/chNN/                GoogleTest unit tests, lit + FileCheck IR tests, end-to-end tests
solutions/                 ⚠ spoilers: reference implementations + plaintext quiz sources
tools/course/              quiz engine, drills + oracles, flashcards, progress tracking
docs/                      setup, Pebble language spec, PIR spec, runtime ABI, authoring guides

For authors¶

Every chapter is written by an author agent and audited by a separate reviewer agent, against a binding contract: - docs/authoring/DEPTH_CONTRACT.md: the width-and-depth checklist, the rigor rules and the review rubric - STYLE.md: voice, LaTeX math and numbered theorem/proof boxes, real-world example boxes, the website - NOTATION.md: house notation - REFERENCES.md: annotated bibliographies (references.yaml) and citations - LABS.md: labs ship specs and a minimal test contract, not scaffolding - REVIEW_CHECKLIST.md: the reviewer's procedure - QUIZ_FORMAT.md - DRILLS.md - CHAPTER_TEMPLATE/

Infrastructure conventions are in docs/dev/FOUNDATION.md. Before submitting a chapter, run ./course validate --strict, ./course site build and uv run python -m unittest discover tools/course/tests.