Pipelinetypical

One Line, All the Way Down

Follow `x = a + b` from characters to retired machine instructions, and watch each stage answer a question the previous representation could not even express.

The question

What actually happens to a single line of source code between my editor and the CPU?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

Nine of them in sequence — characters, tokens, a parse tree, an AST, a typed AST, three-address IR, SSA, virtual-register machine code, and finally physical instructions. The lesson is that these are different *representations of the same program*, each one built because the previous one could not answer the next question.

What this phase may assume or do

Every handover must preserve observable behavior, which for this line means: the value stored in x is the sum of the values of a and b under the language's arithmetic rules, and any trap or overflow the language defines still occurs. Everything else — the order of the loads, whether an addition instruction exists at all, whether x lives in memory — is the compiler's to choose.

Key points

A compiler is a sequence of representations; each stage exists because the previous form could not express the next question.
Spans recorded by the lexer are what every later diagnostic, debugger and source map depends on. Dropping them is unrecoverable.
The parser produces structure and deliberately checks no meaning; the resolver and type checker annotate that structure without restructuring it.
IR imposes an evaluation order and names intermediates, which is what makes analysis possible at all.
Every stage may reorder, merge or delete work — but only while the program's defined observable behavior is unchanged.
The compiler's model of the machine is simpler than the machine; the CPU reorders again underneath it.

Nine representations, one program

The line x = a + b is thirteen characters. Nothing about that sequence of bytes says which of them belong together, that + is a binary operator, that a was declared, that a and b are the same type, or that anything is stored anywhere. Each of those is a separate question, and each stage of a compiler exists because some earlier representation could not express the answer.

That is the whole idea of the pipeline, and it is worth stating before any of the machinery: a compiler is a sequence of representations, not a translation step. A stage is justified when it makes the next question answerable, and it is a bad stage when it discards something a later stage needed — which is exactly what [[information-loss]] is about.

The line through a typical ahead-of-time compilertypical

Charactersyou write it
A byte sequence. No structure of any kind.
Tokensbuild time
A flat list of classified lexemes with source spans.
Which characters belong together, and what kind of thing each group is.
Whitespace and comments, unless the lexer deliberately keeps them as trivia.
Parse treebuild time
A tree mirroring the grammar, including every punctuation node.
Grouping and precedence — that + joins a and b, and that the result is assigned.
ASTbuild time
A tree of semantically meaningful nodes: Assign(x, Add(a, b)).
A shape later phases can pattern-match on without knowing the grammar.
Parentheses, exact token positions unless spans are threaded through deliberately.
Typed ASTbuild time
The same tree with a type and a resolved symbol on every node.
That a refers to *this* declaration, that both operands are int, and that + is defined for them.
IRbuild time
Three-address instructions over an unbounded supply of virtual registers.
An explicit evaluation order and named intermediate values, which is what makes analysis possible.
Expression nesting — the tree is now a linear sequence.
SSAbuild time
The same instructions with every value defined exactly once.
Explicit data dependencies: each use points at exactly one definition.
Machine IRbuild time
Target instructions still using virtual registers.
A commitment to a specific instruction set.
Portability. From here the program is about one machine.
Machine codebuild time
Encoded bytes using physical registers and stack slots.
A decision about where every live value physically lives.
The names. a and b survive only in debug metadata — see [[debug-information]].

Read it asRead the loses column downward: that is the list of things a debugger has to reconstruct, and the reason [[debugging-optimized-code]] is hard. Nothing in the pipeline is obliged to keep them; keeping them is a deliberate, paid-for choice.

Characters become tokens

The lexer walks the characters left to right and groups them into the largest lexeme that forms a valid token at each position — the *maximal munch* rule. It emits a kind, the matched text, and the half-open source range the text occupied.

That range is the load-bearing part. Every diagnostic, every jump-to-definition, every source map and every debugger line table ultimately derives from spans recorded here. A lexer that discards positions produces a compiler that can only say "syntax error", which is why [[source-locations]] is a lesson rather than a footnote.

The token stream for x = a + b;

x = a + b;

Read it asThe lexer has decided which characters belong together and nothing else. It does not know that x was declared, that + binds tighter than =, or that any of these names refer to anything. Those are the parser's and the resolver's questions.

Tokens become structure

The parser imposes the grammar. = is right-associative and binds loosest, so the assignment is the root; + binds tighter, so the addition sits underneath it. Nothing in the token list said this — it comes entirely from the grammar, which is why [[operator-precedence]] is a property of the language rather than of the expression.

The tree below is an AST, not a parse tree. A parse tree for the same input would also contain nodes for the = and ; tokens and for every grammar rule traversed on the way down. The AST keeps what later phases need to pattern-match on and drops the rest — see [[parse-tree-vs-ast]].

AST after parsing, before any name or type is known

AST — only what later phases match on

Assign“x = a + b”

├── Identifier x“x”— A name. Not yet known to refer to anything.

└── Binary +“a + b”

├── Identifier a“a”

└── Identifier b“b”

Read it asThe tree is well-formed and completely unchecked. a might not exist. b might be a string. x might be a constant that cannot be assigned to. The parser is not allowed to care: its job is structure, and a parser that also checked meaning would be [[what-parsing-does]]'s red flag.

Structure becomes a checked program

Semantic analysis walks the same tree twice over. Name resolution attaches each identifier to the declaration it refers to, following the scope rules — which is what makes [[shadowing]] decidable. Type checking then asks whether + is defined for the operand types it now knows, and records the result type on the node.

After this pass the tree carries three things it did not before: a symbol on every identifier, a type on every expression, and — crucially — the knowledge that the program is well-formed. Everything downstream is allowed to assume it. That assumption is what [[optimization-legality]] rests on later: an optimizer may assume the program type-checked, because it would not have reached the optimizer otherwise.

The same tree after name resolution and type checking

Typed AST — same shape, with symbols and types attached

Assign: int

├── Identifier x: int→ local#0 x: int— Resolved to a declaration, so the compiler knows it is assignable and where it lives.

└── Binary +: int→ int::operator+

├── Identifier a: int→ local#1 a: int

└── Identifier b: int→ local#2 b: int

Read it asCompare with the previous tree: same shape, two new fields. That is what a semantic pass does — it annotates rather than restructures. The restructuring happens at lowering, and the tree is discarded shortly after.

The tree becomes a sequence

simplifiedReal IRs from LLVM or GCC carry alignment, address spaces, nsw/nuw overflow flags, debug locations and type metadata on every instruction. Ours shows opcode and operands only. The flags matter: add nsw is what tells the optimizer that signed overflow is undefined here and may therefore be assumed not to happen — see [[ub-and-optimization]].

A tree says what depends on what; it does not say in which order anything happens. IR fixes an evaluation order and gives every intermediate result a name, so that later analyses have something to talk about. t1 below exists purely so that "the result of a + b" is a thing with an identity.

This is also the point at which the program stops being about the source language. A C frontend, a Rust frontend and our own AtlasLang frontend can all produce this same three-address form, which is the entire argument for [[why-ir-exists]].

Three-address IR, then SSA

Three-address

t1 = load a
t2 = load b
t3 = add t1, t2
store x, t3

SSA (already single-assignment here)

▸%1 = load i32 %a
▸%2 = load i32 %b
▸%3 = add i32 %1, %2
▸store i32 %3, ptr %x

Read it asA straight-line statement with no reassignment is already in SSA form — every name is defined once. SSA only starts to cost anything when control flow merges, which is where [[phi-functions]] come from. This line is the trivial case, and showing the trivial case first is the point.

Where the loads go

The IR loads a and b from memory because that is what the frontend emits for a local variable. On any optimization level above none, that is usually not what runs: if a and b are ordinary locals whose addresses are never taken, the loads and the store collapse into register moves, and often into nothing at all once the surrounding code is considered.

The transformation below is legal only under a stated condition, and stating that condition is the discipline this whole domain runs on. It is not "the compiler optimizes it away" — it is "the compiler may eliminate the memory traffic if it can prove nothing else observes that memory".

Promoting locals out of memory

Before

t1 = load a
t2 = load b
t3 = add t1, t2
store x, t3

After

%3 = add i32 %a, %b

Legal only when

Only if a, b and x are locals whose addresses never escape the function, no other thread can observe their storage, and none of them is volatile or otherwise declared to have observable access. Under those conditions the memory locations are unobservable, so the loads and the store are not part of the program's defined behavior.

Illegal when

If &a was passed to another function, or x is a volatile hardware register, or a signal handler or another thread may read the storage. Then the load and the store *are* observable behavior and removing them changes what the program does — see [[alias-analysis]] and [[escape-analysis]].

Virtual registers become real ones

targetx86-64 System V only. On AArch64 AAPCS the same function is add w0, w0, w1; ret — different register names, different argument registers, different return register, and no equivalent of the lea trick because AArch64 arithmetic does not set flags unless you ask. On Windows x64 the first two integer arguments are ecx and edx. The shape of the lesson survives all three; none of the register names do.

The IR assumed an unlimited supply of names. A CPU has a fixed, small set of general-purpose registers — sixteen on x86-64, thirty-one on AArch64 — and every value that is live at the same time as another value needs somewhere different to live. Deciding that is [[register-allocation]], and when there are not enough registers the loser goes to a stack slot, which is [[spilling]].

For three values in a straight line this is trivial. It stops being trivial the moment a loop keeps a dozen values live across a call, at which point the calling convention starts dictating the answer, because some registers are destroyed by any call at all.

x86-64, System V ABI, with `a` and `b` arriving as the first two arguments

1add:
2  lea eax, [rdi + rsi]   ; a arrives in edi, b in esi; the ADDRESS operands are the
3                         ; full 64-bit rdi/rsi, because x86-64 addressing is 64-bit
4  ret                    ; eax is the integer return register

The addition is done by lea, an address-computation instruction, because it adds two registers into a third without touching the flags register. That is [[instruction-selection]] choosing a cheaper encoding for an operation that is not, on its face, an addition at all. Note the register widths: the operands are written rdi/rsi because x86-64 address computation is 64-bit, while the destination is eax because the value is an int — and writing to a 32-bit register zeroes the upper half for free, which is why no truncation instruction is needed.

What the CPU actually receives

The assembler encodes lea eax, [rdi + rsi] into bytes — an opcode, a ModR/M byte selecting the addressing form, and a SIB byte naming the two registers. Those bytes are what the instruction fetcher reads. Everything above this line was a compiler's internal bookkeeping; only the bytes exist at runtime.

And then the hardware takes its own liberties, which are a separate subject with a separate owner. The processor may execute the addition before an earlier instruction that it does not depend on, rename eax to a different physical register entirely, and retire the results in program order to preserve the illusion. [[out-of-order-execution]] and [[register-renaming]] in Computer Architecture are the right place for that; what matters here is that the compiler's model of the machine is deliberately simpler than the machine.

Which question each representation can answertypical

Representation	Can answer	Cannot answer
Characters	Nothing structural	Which characters form one name
Tokens	Which characters group, and into what kind	Which groups belong to which expression
AST	What is applied to what	Whether the names exist or the types agree
Typed AST	Whether the program is well-formed	What order things happen in
IR / SSA	Which value flows where, and what is dead	Which instruction can encode it
Machine IRtarget	Which target instruction implements it	Where the value physically lives
Machine codetarget	Exactly what executes	What the programmer called any of it

How it works

The steps, in the order the compiler takes them.

The lexer scans left to right, taking the longest valid lexeme at each position, and emits (kind, text, start, end).
The parser consumes tokens against the grammar, using precedence and associativity to decide the shape, and builds AST nodes that carry the spans of the tokens they came from.
Name resolution walks the tree with a scope stack, binding each identifier to a declaration and attaching the resulting symbol to the node.
Type checking walks the annotated tree bottom-up, computing a type for each node from its children and rejecting operators that are not defined for the operand types.
Lowering flattens the tree into three-address instructions over virtual registers, fixing an evaluation order in the process.
The optimizer runs analyses and transformations over the IR, each transformation guarded by a legality precondition it must establish first.
Instruction selection pattern-matches IR subtrees onto target instructions; register allocation then assigns each virtual register a physical register or a stack slot.
The assembler encodes the chosen instructions into bytes, and the linker later resolves any names those bytes refer to.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

The lexer discards or miscomputes spans, and every downstream error message points at the wrong line — usually the line *after* the mistake, because the span used was the next token's.
The parser encodes precedence wrongly, so a + b * c builds as (a + b) * c. Nothing errors. The program compiles and returns wrong numbers, which is the hardest possible class of compiler bug to notice.
Name resolution binds to the wrong declaration under shadowing, and a variable silently reads an outer scope's value.
Lowering fixes an evaluation order the language did not specify, and a program with side-effecting operands behaves differently from another compiler's output.
An optimizer applies a transformation whose legality precondition it did not actually establish, and code that was defensive against a null pointer disappears — see [[ub-and-optimization]].
Register allocation reuses a register whose value is still live, and a value is silently corrupted mid-function. The symptom is a wrong result far from the cause.

When it helps

Reading an unfamiliar compiler, tool or language implementation: knowing which representation a component operates on tells you what it can possibly be responsible for.
Debugging: locating a defect to a stage — wrong tokens, wrong tree, wrong types, wrong IR, wrong registers — narrows the search enormously before any hypothesis is formed.
Deciding where a feature belongs. Most language features can be implemented as sugar in the parser, as a lowering, or as a backend change, and the three have very different costs.

When it hurts

Treating this ordering as universal. A tree-walking interpreter stops after the typed AST; a JIT starts at bytecode and revisits stages at runtime; TypeScript type-checks and then discards the types entirely.
Reasoning about performance from the IR. The IR is a model. The out-of-order machine underneath it will reorder again, and the cost of an instruction is not visible at this level.

What it costs

Every one of these is paid by something.

More intermediate representations buy analysability and retargetability, and cost compile time, memory, and a great deal of implementation surface — every representation needs a printer, a verifier and a test suite.
Threading spans through every stage costs memory on every node and discipline in every transformation, and buys the diagnostics and the debugger. Compilers that skipped it could not add it back cheaply.
Aggressive optimization buys runtime speed and pays in compile time, code size, and correspondence between the running code and the source — which is precisely why [[debug-vs-release]] is a real choice and not laziness.

What else you could do

What a different compiler or language does instead, and when that is better.

A tree-walking interpreter skips everything from IR onward and executes the typed AST directly. Far simpler, far slower, and a completely legitimate implementation of the same language — see [[tree-walk-interpreter]].
A bytecode VM stops at a linear instruction format and interprets it, trading native speed for portability and much faster startup — see [[bytecode]].
A JIT defers the last several stages to runtime, where it knows the actual types and the actual hot paths, and pays for it in warmup and memory — see [[jit-compilation]].
A transpiler stops at another language's source and hands the remaining stages to that language's compiler, which is what TypeScript does — see [[typescript-pipeline]].

See it for yourself

The flag, dump or tool that shows you this directly.

Tokens and AST: most compilers can dump them. clang -Xclang -dump-tokens and clang -Xclang -ast-dump for C and C++; python -m ast and dis.dis for Python; rustc -Z unpretty=hir on nightly for Rust.
IR: clang -S -emit-llvm -o - prints LLVM IR. Run it again with -O2 and diff the two — the difference is the entire middle-end.
Assembly: clang -S -o - or gcc -S -o -. Add -fverbose-asm for register commentary, and always name the target explicitly if the claim depends on it.
Everything at once, in a browser, for many compilers and versions: Compiler Explorer. Its value is the diff between two flag sets, not any single listing.
Our own pipeline explorer at /compilers/pipeline runs all nine stages of the real AtlasLang implementation on whatever you type, with spans linked across every panel.

Plausible wrong readings

Stated the way a confident engineer states them.

"The compiler turns code into assembly." It turns code into a sequence of representations, and assembly is one of the last. Almost every interesting decision happens before it.
"These stages happen in this order in every language." They happen in this order in an ahead-of-time compiler for a statically typed language. Python, JavaScript and TypeScript each take a genuinely different route — that is what [[four-languages-one-program]] exists to show.
"The IR is what the CPU runs." Nothing runs the IR. It is a data structure inside a process that has usually exited before your program starts.
"If I can see it in the source, the debugger can show it to me." Only if the compiler emitted metadata for it and the optimizer preserved that metadata. Frequently neither is true — [[debugging-optimized-code]].

Misconceptions

The claim, and what is actually true.

Compilation is translation — source in, machine code out.

It is a sequence of representations. Most of the compiler never sees machine code, and the decisions that determine performance are made several representations earlier.

The AST and the parse tree are the same thing.

A parse tree contains a node for every grammar rule and every token, punctuation included. An AST keeps only what later phases need to match on. Formatters need the former; optimizers need the latter.

Optimizations make the instruction sequence shorter.

Many make it longer on purpose. Inlining, unrolling and monomorphization all increase code size to remove work or expose further transformations.

What I see in the assembly is what the CPU does.

The CPU may execute those instructions out of order, rename their registers and speculate past their branches. The assembly is the contract, not the schedule.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

Source code passes through several forms on the way to running. Each form makes a different question answerable: tokens say which characters group together, a tree says what applies to what, types say whether it means anything, IR says in what order it happens, and machine code says exactly what executes. If you remember one thing, remember that these are stages of *representation*, not steps of translation.

practical

When something is wrong, locate it to a stage before forming a hypothesis. Wrong error position means spans. Wrong arithmetic result with no error means precedence or associativity in the parser. A variable reading the wrong value means name resolution. Code that vanished means the optimizer had a legality precondition you did not expect it to have — most often an undefined-behavior assumption. Every one of these has a dump flag that will show you the representation directly, and reading the dump beats reasoning about it.

advanced

The interesting design question is not how many stages but *where each piece of information dies*. Spans die in the parser unless deliberately threaded. Types die at erasure, which is why generic code cannot always be specialized late. Source-level variable identity dies in register allocation, which is why debuggers report "optimized out". Every one of those deaths is a design decision with a cost on the other side, and a compiler is largely characterised by which ones it refuses to accept — a language server, for instance, is a compiler frontend that is not allowed to let anything die.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

typicalThe nine-stage sequence describes mainstream ahead-of-time compilers such as Clang, GCC and rustc. CPython stops at bytecode; V8 begins at bytecode and adds tiers at runtime; tsc type-checks and then erases. Do not carry the ordering to a language before checking it.

targetThe assembly listing is x86-64 System V. Register names, argument registers, the return register and the availability of lea-style three-operand addition all differ on AArch64 and on Windows x64. Only the shape of the argument transfers.

simplifiedOur IR shows opcode and operands only. Production IRs carry overflow flags, alignment, address spaces and debug locations, and several optimizations are legal only because of a flag we are not showing.

If you were asked this in an interview

Walk me through what happens between the source file and the running process.
At which point does the compiler know that a and b are integers, and what could it not do before that point?
The debugger says a variable is optimized out. What does that tell you about which stages ran?

Connections

DSAbinary-tree dfs

Computer Architectureout-of-order-execution register-renaming registers instruction-decode instruction-set-architecture

Performancejit-and-warmup

OS & Networkingprogram-vs-process process-memory-layout

Domains that do not exist yet

Programming Languages & Runtime Internals — What the process does with the machine code once the loader has mapped it
This domain stops at the handover. Object representation, allocation and garbage collection are the runtime's half of the same story, and several stages here exist only to emit metadata that half will need.
Testing & Reliability Engineering — Differential testing and property-based testing as general techniques
Applying them to a compiler is [[differential-testing]] and [[compiler-fuzzing]] here, but the techniques themselves are not compiler-specific and are owned there.