The architecture of an ahead-of-time compiler

A flat list of tokens has no shape. The parser gives it one: an abstract syntax tree, where every statement and every expression is a node and its parts hang beneath it. This one is a recursive-descent parser, one small function per rule of the grammar. Clang, rustc and Go’s compiler all parse this way, by hand.

Precedence is where the grammar shows. In sum + i * 2, the multiplication sits deeper in the tree than the addition, so it happens first. Nobody wrote a rule saying “multiply first”: the function for + calls the function for * to get its operands, and depth does the rest. Parentheses don’t survive into the tree at all; they only changed its shape.

Trees are good for checking and bad for optimising. So the compiler lowers the tree into an intermediate representation: short instructions, each doing one thing, grouped into basic blocks that run straight through and end in a jump. Draw the jumps as arrows and you get the control-flow graph below. The while loop is the arrow that goes back up.

The IR is in SSA form (static single assignment): every value gets exactly one name, assigned exactly once. The variable sum becomes %sum.0, %sum.1, %sum.2, one per assignment. Where two paths meet and each brings a different version, a phi picks the right one depending on which arrow you came in on. In exchange for that bookkeeping, every optimisation in the next plate becomes simple, because a name can never change behind your back.

Cranelift, the code generator Miri uses, builds its SSA with the same algorithm, and skips the phi notation altogether: its blocks take parameters, and a jump passes the values in, like a function call. It’s the same idea in different clothes.

An optimiser is a set of small, paranoid passes. Each one looks for a pattern it can prove safe to rewrite, rewrites it, and hands the IR to the next. None is clever on its own; run them in a loop until nothing changes and they add up.

Constant propagation replaces a name with its value when the value is known. Constant folding does arithmetic on known numbers at compile time, and turns a branch on a known condition into a plain jump. Common-subexpression elimination reuses a result instead of computing it twice. Strength reduction swaps an expensive operation for a cheaper one: i * 2 becomes i shl 1. Dead-code elimination deletes whatever no longer affects the output.

Pick arithmetic and switch the passes on one at a time. Propagation alone changes almost nothing visible; add folding and the whole program collapses into ret 42. The passes need each other. That is also why the order of passes is one of the most argued-about settings in any real compiler.

Then look at what this optimiser can’t do. The sum loop survives, because every pass here looks at one value at a time. LLVM can recognise that loop as an arithmetic series and replace it with the closed-form formula. That isn’t magic either, just a smarter pass than mine.

The assembler turns every instruction into bytes. These are real x86-64 encodings, checked byte for byte against Clang’s assembler, and the same code, linked and run natively, prints exactly what the interpreter in plate VI predicts. c3 is ret; 55 is push rbp; every jump is resolved to a distance in bytes.

One thing the assembler can’t resolve is print. It lives in another file, so its address is unknown. The assembler writes four zero bytes and a note, a relocation: “patch this with the distance to print, minus 4”. The result is an object file: code, a list of the symbols it defines, a list of the ones it needs.

The linker takes object files and makes one program: it lays the code out in memory, learns where every symbol landed, and goes back to patch each relocation. Step through it.

That’s the whole journey: characters, tokens, a tree, a checked tree, SSA, better SSA, assembly, bytes, a binary. Real compilers add types, generics, inlining, vectorisation and a hundred passes, but the skeleton is this one. Miri, the GPU-first language I’m building, walks the same road: lexing, parsing, type checking, a mid-level IR, then Cranelift for the machine code. And at the very end, every compiler meets the same thing, the fetch–decode–execute loop of the CPU notebook, reading these bytes one by one.