A Tour of rustc's Internals: The Thirty-Eight Tricks That Make the Compiler Fast

TL;DR: rustc is a compiler that has spent twenty years turning “the obvious implementation” into “the slow implementation, replaced by something clever”. This is a tour of thirty-eight of those somethings — from an 8-byte Span with four internal layouts to a dataflow engine with no worklist — and where in the source tree each one lives.

rustc --version prints a version number. What it does not print is the several hundred small decisions that make a large crate compile in seconds rather than minutes. This is a tour of the ones that are worth knowing about, grouped by the part of the compiler they live in.

1. Everything is a query, and nothing is cached

rustc’s compiler is built on a query system: every computation is a memoized, dependency-tracked node in a DAG. The interesting parts are the peripherals.

• The colour map that is also an index — one u32 per node holds red, green and the current-session index, so there is no side table.
• Green means same — incremental compilation re-runs queries and compares 128-bit fingerprints, so fingerprints have to be reversible: DefIds hash to a stable DefPathHash.
• Four shapes of cache — a OnceLock for unit keys, a dense vector cache for local DefIds, a sharded map for the rest; the slot packs “initialised?” and the dep-node index into one atomic word.
• The lock that disappears — the thread count is a compile-time decision, so a single-threaded build has zero atomic instructions in its cache path.
• 38 bytes and a mask — the dependency graph file has fixed-size node headers, varint edge lists that stay varint in memory, and an encoder that hands out node indices in blocks of 256.

2. The borrow checker solves in one pass

Region inference is not a fixpoint over regions; it is a fixpoint over an SCC condensation of the region graph.

• One pass, no fixpoint — regions in a cycle are equal by construction, so the condensation is a DAG and one topological sweep suffices.
• end(X) doesn’t live in the CFG — region values are three independent dimensions (points, free regions, placeholders), so the “end of lifetime X” marker costs no extra CFG points and the interval sets stay contiguous.
• The blame is the most interesting constraint — a BFS finds the shortest path through the constraint graph, then a hand-tuned ranking picks the most user-facing constraint on it, and the expensive constraint objects are built only on the error path.
• No queue at all — the dataflow framework’s dirty set is a bitset indexed by reverse-postorder rank; rewinding to a lower rank on a back edge is both the correctness rule and the reason loop-free code is analysed in a single pass.
• Two-phase borrows are dominator queries — v.push(v.len()) works because “is this borrow active here?” is answered with two tree queries instead of an extra dataflow analysis.

3. The trait solver thinks in lattices

• Coinduction for free — cycles are classified Inductive < Unknown < Coinductive, joined with a max-like operation, and the kind is recomputed compositionally on every stack push.
• Divide by four — after an overflow the recursion budget is divided rather than decremented, which turns a quadratic blowup into a geometric one.
• Proof trees, not errors — the solver never formats a message; it records a replayable trace and reconstructs the error afterwards, with the cache disabled so the replay is faithful.

4. MIR optimisation is where the sharp edges are

• GVN refuses to merge two borrows — every pointer value carries a marker type whose Hash and PartialEq are unreachable!(), so “accidentally unify two &muts” is impossible rather than unlikely.
• The call graph from the wrong MIR — the inliner computes the call graph from pre-optimization MIR to avoid a query cycle, and gives up with an eighth of the recursion limit so the cheap analysis fails before the expensive one.
• Four ways to drop — drop sites are classified dead, static, conditional or open; only the conditional case allocates a flag, so most drops cost nothing.
• Drop glue gets four times the budget — the monomorphiser divides the recursion depth by four for drop glue only, because dropping a value legitimately recurses through the type structure.
• Merging codegen units by overlap — CGUs are merged by inlined-item overlap, not by size, because duplicated inlined code is what makes LLVM’s job harder.
• Sorting fields and hiding a niche — the layout algorithm sorts fields by log2(max(align, size)) and reserves the biggest invalid-value hole as the discriminant, which is why Option<&T> is one pointer.

5. The front end never fails, and never copies

• The lexer that never fails — unterminated strings and stray characters are token kinds; the lexer is a total function from bytes to tokens, and it refuses to be greedy so 0..2 and 12.foo() tokenize correctly.
• One token, two operators — >> is split on demand with byte-exact spans, so a proc macro sees exactly what the source said.
• Capturing tokens by replaying them — the captured range is a half-open interval of bump counts; the tokens are materialised only if something asks for them, which is rare.
• macro_rules! is an NFA — the matcher keeps a set of live positions and follows epsilon transitions, so there is no backtracking and no exponential blowup.
• Did you mean a hyphen? — a static confusables table doubles as the recovery mechanism and the diagnostic source.

6. Const evaluation is one interpreter with two personalities

• One interpreter, two machines — the Machine trait has eight associated types and 57 hooks; Miri and CTFE are two instantiations, so Miri gets provenance tracking for free.
• The init mask is a single boolean — uninitialised-byte tracking starts as one bool and only materialises a bitmap on a partial write; a full overwrite de-materialises it again.
• Provenance in eight bytes — an allocation id plus two flags fit in one NonZero<u64>, and the provenance of stored pointers is sparse relocations rather than per-byte metadata.

7. The standard library is where the bytes are

• Vec’s capacity lives in a niche — RawVec stores the capacity in a UsizeNoHighBit, so Vec is three words instead of four.
• collect() reuses your allocation — in-place collection turns map + collect into a loop with no allocation, no copy and no free.
• Sixteen buckets at a time — the SwissTable compares 16 control bytes with one SSE2 instruction, and the top 7 bits of the hash filter candidates before any key comparison.
• SipHash’s field order is a SIMD hint — v0, v2, v1, v3 instead of v0, v1, v2, v3, so the compiler can find two SIMD lanes by itself.
• Thirteen elements, forty-five comparisons — small slices are sorted with a fixed, branchless sorting network.
• One XOR and one CLZ — the powersort merge-tree depth is computed from the leading zeros of an XOR, not from rational comparisons.
• Sixteen bytes at a time — UTF-8 validation is an ASCII scanner with a Unicode-aware fallback.

8. And the data structures underneath everything

• Always bump downwards — arenas allocate downwards from the end of a chunk and use hint::assert_unchecked to tell LLVM the alignment invariant holds, deleting the alignment arithmetic.
• How a span fits in eight bytes — four internal layouts selected by a prefix, decoded by a macro because the enum version did not optimise; and SyntaxContext deliberately does not implement Ord, because its allocation order is nondeterministic.
• Tables that pick their own integer width — metadata tables choose their element width at encode time by stripping trailing zeros, and byte-interleave integer pairs so both halves compress at once.
• Pruning irrelevant pattern columns — a relevancy flag per matrix row turns an exponential exhaustiveness check into a linear one.

The themes

Read the list again and four patterns emerge.

Representation follows the common case. The init mask is a bool until it cannot be; the provenance map is None until it cannot be; the capacity is a niche until it cannot be. The rare case should never cost the common case.

Delete work rather than optimise it. No worklist. No error messages during solving. No token collection for nodes that do not need tokens. No locks in a single-threaded build. Most of the speed comes from not doing the thing.

Change the representation to change the cost. Powersort’s merge depth becomes an XOR and a lzcnt because the number line is rescaled. Region values become three dimensions so end(X) is free. Metadata elements are byte-interleaved so one stripping pass compresses two integers.

Make the illegal state unrepresentable. VnOpaque’s panicking PartialEq. SyntaxContext’s missing Ord. The assert_unchecked alignment invariant. The compile-time size budgets on query keys and values. These are not optimisations; they are the reason the optimisations are safe.

Where to start reading

If you want to read the source with a plan rather than at random:

• compiler/rustc_middle/src/dep_graph/ — the incremental machinery, which is self-contained and unusually well commented.
• compiler/rustc_mir_dataflow/src/framework/ — a small, elegant framework you can read in one sitting.
• compiler/rustc_expand/src/mbe/macro_parser.rs — the NFA, with a module-level tutorial that is better than most blog posts.
• library/core/src/slice/sort/ — driftsort and ipnsort, and the 13-element sorting network.
• library/alloc/src/vec/ — specialisation-driven collect, in-place collection, the niche-packed capacity.

The compiler’s own documentation is at https://rustc-dev-guide.rust-lang.org/, and the rustc-dev-guide source lives in src/doc/rustc-dev-guide/ in the same repository.