FerrousPath

Level 5 · Research· Lesson 5 of 9 · 40 min

Compiler architecture

From source text to machine code — the representations, the query system and incremental compilation, monomorphization, backends, and how to start contributing.

To do research on Rust, or simply to understand why it behaves as it does, you need a map of rustc. This lesson is that map, with instructions for looking at each stage yourself.

The pipeline

source text
   │  lexing, parsing
   ▼
AST ──────────── macro expansion, name resolution, early lints
   │  lowering (desugars `for`, `?`, `async`, `if let`…)
   ▼
HIR ──────────── type collection, type inference & checking, trait solving, late lints
   │  lowering with types attached
   ▼
THIR ─────────── pattern exhaustiveness checking, unsafety checking
   │  MIR building
   ▼
MIR ──────────── borrow checking, const evaluation (the Miri engine), optimisations
   │  monomorphization collection
   ▼
backend IR (LLVM IR / Cranelift IR / GIMPLE) ── optimisation, code generation
   │
   ▼
object files ── linking ──▶ executable or library
IR What it is Why it exists
Token stream Lexed tokens, grouped into token trees Input and output of macros
AST Syntax tree, close to the source Macro expansion, name resolution
HIR Desugared tree with resolved names and stable IDs Type checking; much smaller surface than the AST
THIR Fully typed tree, with autoderef, coercions and method calls explicit Exhaustiveness checking; building MIR
MIR Control-flow graph of simple statements on places Borrow checking, optimisation, const evaluation, monomorphization
LLVM IR Monomorphic, SSA, typed, low-level Target-independent optimisation and code generation

Each lowering removes sugar and adds explicitness. By MIR, for x in v { … } has become a loop calling Iterator::next and matching on the result, with explicit drops.

Look at each stage

Take a small function and print it at every level:

fn sum_evens(v: &[u32]) -> u32 {
    let mut total = 0;
    for &x in v {
        if x % 2 == 0 {
            total += x;
        }
    }
    total
}

fn main() {
    println!("{}", sum_evens(&[1, 2, 3, 4]));
}
To see Command
Macro-expanded source cargo expand (or rustc -Zunpretty=expanded on nightly)
HIR rustc +nightly -Zunpretty=hir-tree or hir
THIR rustc +nightly -Zunpretty=thir-tree
MIR rustc --emit=mir (stable), or Show MIR on the Rust Playground
LLVM IR rustc --emit=llvm-ir -C opt-level=3
Assembly rustc --emit=asm -C opt-level=3, cargo asm, or Compiler Explorer
Type layouts rustc +nightly -Zprint-type-sizes
Time per pass cargo +nightly rustc -- -Ztime-passes, -Zself-profile

Do this once for a function with a closure, a match, an async fn, and a generic. An hour spent here explains more about Rust than a week of reading.

The front end

Parsing produces the AST with a hand-written recursive-descent parser with extensive error recovery — the source of Rust’s good syntax errors.

Macro expansion and name resolution are interleaved, because macros can define names and names determine which macro is invoked. The loop runs to a fixed point. Hygiene is implemented with syntax contexts attached to identifiers.

HIR lowering desugars and assigns each item a DefId and each node a HirId, stable identifiers used throughout later stages.

Type checking

Type checking runs per function body (typeck), and has three intertwined jobs:

  • Type inference, Hindley–Milner-style with unification variables, extended with subtyping (for lifetimes), coercions, integer/float fallback, and bidirectional expectation propagation that makes closures and literals infer well.
  • Trait solving (previous lesson): method lookup probes candidate receivers through autoderef; obligations generated by each expression are registered and solved as inference variables are resolved.
  • Region constraints are collected but not solved here — lifetimes are erased from the typeck results and re-derived on MIR by the borrow checker. That separation is why lifetimes never affect which method is called or how code is generated.

Whole-crate type inference does not exist: each function is inferred from its body against its declared signature. This is a deliberate design choice — signatures are the unit of abstraction and of compilation.

MIR and its uses

MIR is the hub:

  • Borrow checking (lesson 5.2).
  • Const evaluation: const, static, array lengths and const fn are evaluated by an interpreter over MIR. Miri-the-tool is this same engine with extra checks.
  • MIR optimisations: inlining, constant and copy propagation, dead-code and dead-store elimination, jump threading, scalar replacement of aggregates. Optimising before monomorphization pays once per generic function instead of once per instance.
  • Coroutine transform: async blocks and generators are turned into state-machine enums here.
  • Drop elaboration: conditional drops are made explicit with drop flags.

Monomorphization and code generation

Starting from the roots (main, exported functions), the collector walks MIR and finds every concrete instance needed: Vec<u32>::push, Option<String>::map::<usize, {closure}>. Instances are partitioned into codegen units, which are translated to backend IR and optimised in parallel.

Consequences you have already met: generic code costs compile time and binary size per instance; dyn Trait avoids that; a generic function’s body must be available to downstream crates (stored as MIR in the .rmeta metadata), which is why generic and #[inline] functions can be inlined across crates and others cannot without LTO.

Backends:

  • LLVM — the default; mature optimisation and broad target support.
  • Cranelift (rustc_codegen_cranelift) — faster compilation, lighter optimisation; intended for debug builds.
  • GCC (rustc_codegen_gcc) — libgccjit as a backend, for targets LLVM lacks. gccrs is a separate, independent front end within GCC.

Rust-specific information passed to LLVM is what turns the language’s guarantees into speed: noalias on &mut and (non-UnsafeCell) & parameters, nonnull and dereferenceable, readonly, range metadata on enums and bool. Those attributes are the concrete form of the aliasing model — and wrong ones are miscompilations, which is why the model matters.

The query system

rustc is not a sequence of passes over the whole crate. It is demand-driven: a set of memoised functions called queries, keyed mostly by DefId.

optimized_mir(f)
  └─ mir_borrowck(f)
       └─ mir_built(f)
            └─ thir_body(f)
                 └─ typeck(f)
                      ├─ fn_sig(g)        for each callee g
                      ├─ type_of(S)       for each type mentioned
                      └─ predicates_of(…) …

Asking for a result runs the provider on first use and caches the answer in the type context (TyCtxt, the central data structure through which everything is reached). Types, predicates and other immutable values are interned in arenas, so equality is pointer comparison.

Incremental compilation falls out of this design. The compiler records the dependency graph between queries and a hash of each result. On the next build it uses the red-green algorithm: a query is green if all its dependencies are green (its cached result is reused), otherwise it is re-run; if the new result hashes the same as before, it is marked green anyway, cutting off the change. Edit a function body and its typeck and MIR are recomputed, but fn_sig is unchanged, so callers are untouched.

This architecture is also what lets rust-analyzer (which uses its own query engine, salsa) answer IDE requests in milliseconds.

Diagnostics as a design priority

Rust’s error messages are a deliberate engineering investment: structured diagnostics with spans, labels, notes and machine-applicable suggestions; dedicated recovery in the parser; thousands of UI tests pinning the exact output. Much of the compiler’s complexity exists for the error path. If you want a first contribution, improving a diagnostic is the traditional place to start.

Working on the compiler

git clone https://github.com/rust-lang/rust
cd rust
./x setup            # choose the "compiler" profile
./x check            # type-check the compiler
./x build library    # build a stage-1 compiler and standard library
./x test tests/ui    # run the UI test suite
  • The compiler is bootstrapped: a downloaded stage 0 compiler builds stage 1 from source, which can build stage 2.
  • Read the rustc dev guide alongside the source. The code is organised as crates named rustc_* — rustc_parse, rustc_resolve, rustc_hir_typeck, rustc_trait_selection, rustc_borrowck, rustc_mir_transform, rustc_codegen_ssa, rustc_middle (shared definitions, including TyCtxt).
  • Coordination happens on the rust-lang Zulip. Language changes go through RFCs and the lang team; compiler-internal changes through major change proposals. The types team owns the type system and trait solver; the opsem team owns operational semantics and UB.
  • Changes that may break code are tested with crater, which builds and tests every crate on crates.io with the modified compiler — an empirical tool almost unique to Rust’s process.
  • Issues labelled E-easy and E-mentor are intended for newcomers.

Reading list

  1. The Rust Compiler Development Guide — the primary reference.
  2. Matsakis, “Introducing MIR” (2016) and RFC 1211.
  3. The rustc_middle::ty API documentation — the vocabulary of the type system as implemented.
  4. Appel, Modern Compiler Implementation, or Cooper and Torczon, Engineering a Compiler — for general background.
  5. Lattner and Adve, “LLVM: A Compilation Framework for Lifelong Program Analysis and Transformation” (2004).
  6. The salsa documentation, for the query model in isolation.

Exercises

  1. Emit MIR for sum_evens. Find the iterator next call, the discriminant switch for the Option, and the overflow check on total += x.
  2. Emit optimised LLVM IR for the same function. Was the loop vectorised? Find the noalias and readonly attributes on the parameter.
  3. Use -Zself-profile on a medium-sized crate and identify the three most expensive queries.
  4. Write a function that monomorphizes into 100 instances (a generic called with 100 array lengths via a macro). Measure the effect on compile time and binary size; then refactor to a thin generic wrapper around a non-generic inner function.
  5. Build rustc from source and change the wording of one error message. Run the affected UI tests and update their expected output with --bless.

Check your understanding

Pick an answer to see the explanation.

  1. 1.In which intermediate representation are generic functions still generic?

  2. 2.What is the query system?

  3. 3.Why does incremental compilation's red-green algorithm sometimes avoid recomputing a query whose input changed?

Key terms in this lesson

Finished the lesson and the exercises?