Pipelinetypical

The Phases, and Why Each One Exists

Thirteen stages from characters to execution, each justified by a question the previous representation could not express — and the reason "phase" and "pass" are not the same word.

The question

What are the phases of a compiler, and why is each one a separate phase instead of one big function?

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

What the program is here

A sequence of representations, each a data structure with a stated invariant: a character buffer, a token vector with spans, a parse tree, an AST, an annotated AST, a typed AST, an IR over virtual registers, machine IR, and finally encoded bytes. The phase list *is* the list of representations; a phase that does not change the representation is a pass, not a phase.

What this phase may assume or do

Each phase may assume its predecessor established that predecessor's invariant, and may assume nothing else. The parser may assume the tokens are well-formed lexemes with valid spans; the type checker may assume every identifier has been resolved to a declaration; the optimizer may assume the program type-checked, which is precisely why it is entitled to fold int arithmetic without re-proving that both operands are integers. A phase that assumes something no earlier phase guarantees is a miscompilation waiting for the right input.

Key points

Each phase exists because the previous representation could not express the next question. That is the only justification a phase needs, and the only one it gets.
Splitting at a common IR turns m languages times n targets into m plus n implementations, which is the economic argument that produced LLVM.
A phase changes representation; a pass traverses one. Semantic analysis is one phase and several passes; the middle-end is one phase and dozens.
A phase may assume exactly what earlier phases guarantee, and assuming more is how correct-looking passes miscompile.
Language rules like declaration-before-use are often fossils of single-pass implementations, not semantic necessities.

Why not one function

You can write a working compiler for a small language as a single recursive function that reads characters and emits code, and people did, for real languages, when memory was measured in kilobytes. It works and it is genuinely fast. What it cannot do is answer a question about a part of the program it has already passed, and almost every feature engineers now expect requires exactly that.

Forward references need the whole program before any of it can be checked. Overload resolution needs every candidate. Type inference needs constraints gathered from uses that come after the definition. Optimization needs to see a loop whole. Each of those forces a representation that persists after the text has been consumed, and once you have one, a phase boundary has appeared whether you named it or not.

The second argument for phases is combinatorial and is the one that built the modern toolchain. With m source languages and n targets, one monolithic compiler per pair is m x n implementations. Split at a common intermediate representation and it is m + n. That is [[frontend-middle-backend]], and it is why LLVM exists.

The thirteen stages

typicalThirteen stages describes Clang, GCC and rustc in outline. CPython stops after emitting bytecode and never has an IR in this sense; V8 begins at bytecode and re-enters code generation at run time; tsc performs semantic analysis and then deletes the types rather than lowering them. Do not carry the count, or the order, to an implementation without checking it.

This is the canonical rail the rest of the domain hangs off. Read the adds column as the justification for the phase and the loses column as its bill. No phase is free, and a phase that added nothing the next one needed would simply be deleted.

The conventional ahead-of-time pipelinetypical

Sourcebuild time
A decoded character sequence.
Lexingbuild time
A scanner consuming characters left to right by maximal munch.
Grouping: which characters form one lexeme, and of what kind.
Tokensbuild time
A flat vector of (kind, text, start, end).
A stream a parser can look ahead in cheaply.
Whitespace and comments, unless deliberately kept as trivia for a formatter. See [[concrete-syntax-tree]].
Parsingbuild time
A grammar-directed consumption of tokens, by recursive descent or by a table-driven automaton.
Structure: precedence, associativity and nesting, none of which the token list expressed.
ASTbuild time
A tree of semantic node kinds with spans: Assign(Var, Binary(+, Var, Var)).
A shape later phases can pattern-match on without knowing the grammar.
Punctuation, parentheses, and exact layout.
Semantic analysisbuild time
A traversal with a scope stack and a symbol table.
Which declaration each name refers to, and whether it was legal to use it there at all.
Typed programbuild time
The same tree with a type on every expression and a symbol on every identifier.
That the program is well-formed — the guarantee every later phase spends.
Nothing yet, which is why language servers stop here.
IRbuild time
Three-address instructions over unbounded virtual registers, grouped into basic blocks.
An explicit evaluation order and a name for every intermediate value.
Expression nesting, and usually most source-level type structure.
Optimizationbuild time
Analyses producing facts, and transformations consuming them, over the same IR.
Nothing to the representation — it removes work and exposes more of it.
Correspondence between IR positions and source positions, unless debug locations are maintained through every pass.
Code generationbuild time
Target instructions, still over virtual registers, then over physical ones.
A commitment to one instruction set and one calling convention.
Portability, and the identity of every value that got a register or a stack slot.
Machine code / bytecodebuild time
Encoded bytes in an object file, with a symbol table and relocations.
An artifact that exists outside the compiler process.
Everything not explicitly emitted as metadata. Names survive only for exported symbols and in debug sections.
Linkingbuild time
Several object files plus libraries, resolved into one image.
Addresses for names that were promises, and a decision about which definition wins.
The boundary between translation units, which is why a duplicate-symbol error names two files and no line.
Loading and executionrun time
Mapped pages, bound symbols, an entry point, and a running process.
The actual inputs, and everything only the running program knows.

Read it asTwo readings. Downward, this is the order in which questions become answerable. Upward from any row, it is the list of assumptions that row is entitled to make — and every miscompilation is a row making an assumption a row above it never established.

Phases are not passes

A phase is a change of representation. A pass is one traversal of a representation. The two get conflated constantly, and the distinction matters because the number of passes is an engineering decision while the number of phases is close to forced.

Semantic analysis is one phase and usually several passes: one to collect declarations so forward references work, one to resolve names, one to check types, sometimes another for definite assignment or exhaustiveness. The middle-end is one phase and dozens of passes, run in an order that is itself a design problem — see [[pass-pipelines]] and [[phase-ordering]].

Going the other way, phases can be fused. A single-pass compiler emits code directly from the parser and never builds a tree, which is why Pascal required declaration before use and why C needs a forward declaration for a function you call before defining. Those language rules are fossils of an implementation constraint, and they are a clean example of [[declaration-order]] being a design decision rather than a law.

Phase, pass, and what each phase is allowed to reject

Phase	Typical passes	Rejects	Cannot possibly reject
Lexing	One	An unterminated string, an illegal character, a malformed numeric literal	An undeclared variable — it does not know what declarations are
Parsing	One, with lookahead	A missing brace, an operator with no operand, a statement where an expression was required	A type error — it has no types
Semantic analysis	Two to five	Undeclared names, duplicate definitions, use before initialisation, type mismatches	A division by zero that only happens on Tuesdays
Middle-endtypical	Tens	Nothing. It has no diagnostics; a program that reaches it is already valid	Anything — by this point rejection is not an option, only warnings
Code generation	Several	A construct the target cannot express, such as a 128-bit integer on a target without support	A logic error
Linking	One or two	Undefined symbols, duplicate definitions, incompatible ABI tags	Anything about the inside of a function

The invariant is the contract

implementationThe verifier and -verify-each are LLVM facilities and run by default in assertion-enabled builds only; release builds of Clang ship with assertions off and will happily miscompile malformed IR instead of reporting it. GCC has an analogous but differently spelled checking mechanism under -fchecking, and neither exists in a small hand-written compiler unless you build it.

Every phase boundary is an interface, and like any interface it is only as good as what it promises. The promises are unusually strong here: "every identifier node has a non-null symbol", "every basic block ends in exactly one terminator", "no value is used before its definition dominates the use". Real compilers check them, because a violated invariant produces a crash a hundred thousand instructions later, in a pass that did nothing wrong.

LLVM ships a verifier that runs between passes and asserts the IR's invariants; running it on every pass boundary is what -mllvm -verify-each does, and it converts "the backend segfaulted" into "pass X produced malformed IR". That mechanism is the subject of [[ir-verification]], and it is the single most useful thing to know when a compiler crashes on your input rather than on your bug.

How it works

The steps, in the order the compiler takes them.

The lexer converts characters to a token vector, recording a source span on every token.
The parser consumes tokens against the grammar and builds a tree whose nodes carry the spans of the tokens they came from.
A declaration-collection pass populates the symbol table so that forward references resolve, after which a resolution pass binds every identifier.
A type-checking pass computes and records a type on every expression node, rejecting the program if any rule fails.
Lowering flattens the checked tree into IR, fixing an evaluation order and naming every intermediate.
The pass manager runs analyses and transformations over the IR in a configured order, re-running analyses invalidated by transformations.
Instruction selection, scheduling and register allocation turn IR into target instructions; the assembler encodes them; the linker resolves the names they refer to.

How it breaks

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

The compiler crashes on valid input rather than reporting an error, because one pass produced a representation that violated an invariant the next pass relied on.
An error message names a construct the developer did not write, because a desugaring phase rewrote it and the diagnostic was emitted against the rewritten form. See [[diagnostic-quality]].
A forward reference fails to resolve in a language that permits it, because declaration collection and name resolution were fused into one pass and the collection had not reached the definition yet.
Adding a language feature to the parser makes it work in expressions and silently do nothing inside a macro or a template, because a second path through the same phase was never updated.
Debug builds and release builds disagree about a line number, because a pass moved an instruction without carrying its debug location.

When it helps

Locating a defect before forming a hypothesis. Wrong tokens, wrong tree, wrong types, wrong IR and wrong registers each have a different dump and a different fix.
Deciding where to implement a feature. Sugar in the parser, a lowering in the middle-end and a backend change have wildly different costs, and only one of them usually needs to be paid.
Reading someone else's compiler. The directory names are almost always the phase names, and a component's phase tells you what it can possibly be responsible for.

When it hurts

Treating the phase list as universal. It describes ahead-of-time compilation of a statically typed language and describes a tree-walking interpreter, a JIT tier and a type-erasing transpiler badly.
Adding phases for symmetry. Every representation needs a printer, a verifier and a test suite, and an intermediate form nobody analyses is pure cost — see [[ir-design-tradeoffs]].

What it costs

Every one of these is paid by something.

Separate phases buy testability, retargetability and the ability to answer questions about the whole program, and cost memory proportional to the program size, compile time in the handovers, and a verifier plus a printer per representation.
Fusing phases into a single pass buys compile speed and a tiny implementation, and costs language expressiveness: forward references, whole-program type inference and any optimization that spans more than a statement all become impossible.
Maintaining spans and debug locations across every phase costs memory on every node and discipline in every transformation, and buys diagnostics, debuggers and source maps. Compilers that skipped it could not retrofit it cheaply.

What else you could do

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

A single-pass compiler that emits code straight from the parser: Turbo Pascal compiled entire programs in seconds on hardware that could not hold an AST, at the cost of language rules that exist purely to make one pass sufficient.
A query-based compiler that has no fixed phase order at all — rustc and Roslyn compute facts on demand and cache them, which is what makes incremental recompilation proportional to the change. See [[incremental-compilation]].
A tree-walking interpreter that stops after the typed AST and executes it directly, skipping every later phase — [[tree-walk-interpreter]].
A transpiler that stops at another language's source and delegates the remaining phases entirely, which is what [[typescript-pipeline]] does.

See it for yourself

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

Tokens: clang -Xclang -dump-tokens file.c. Tree: clang -Xclang -ast-dump file.c, or python -c "import ast,sys; print(ast.dump(ast.parse(open(sys.argv[1]).read()), indent=2))" file.py.
IR: clang -S -emit-llvm -o - file.c. Run it again with -O2 and diff — the difference is the middle-end in its entirety.
The pass list actually run: clang -O2 -mllvm -print-pipeline-passes, and -mllvm -print-after-all to see the IR after each one.
The phase timings: clang -ftime-report and rustc -Z time-passes on nightly attribute wall time to phases, which is the fastest way to find out why a build is slow.
Our pipeline explorer at /compilers/pipeline shows eight of these representations for one program at once, with spans linked across panels.

Plausible wrong readings

Stated the way a confident engineer states them.

"Every compiler has these thirteen phases." Every compiler has *some* sequence of representations. Thirteen is a description of one family, and a bad description of interpreters, JITs and transpilers.
"More phases means a better compiler." More phases means more compile time and more surface. A phase is justified by a question, and a phase with no consumer is dead weight.
"Optimization is a phase like the others." It is the one phase that adds nothing to the representation. It exists to remove work, and it is also the phase most able to make the compiler wrong.
"The parser checks my program." The parser checks that the program has a valid shape. Whether it means anything is the next phase's problem entirely.

Misconceptions

The claim, and what is actually true.

The frontend produces assembly and the rest is bookkeeping.

The frontend produces a typed tree and never sees an instruction. Most of a compiler's code, and nearly all of its runtime cost at high optimization levels, is downstream of it.

A pass and a phase are the same thing.

A phase changes what the program is; a pass traverses what it currently is. One phase routinely contains dozens of passes, and the ordering between them is its own research problem.

Declaration before use is a semantic requirement.

It is an artefact of compilers that could not afford to keep the program in memory. Languages designed after that constraint lifted mostly dropped the rule.

Go deeper

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

overview

A compiler is a chain of representations: characters, tokens, a tree, a checked tree, an intermediate form, instructions, bytes. Each link exists because the previous form could not answer the next question, and each link throws something away on the way past.

practical

Use the phase list as a bisection tool. Dump the tokens: are they what you expect? Dump the tree: is the shape right? Dump the IR before and after optimization: did something disappear that should not have? Each dump is one flag, and finding the first representation that is wrong is worth more than any amount of reasoning about the source.

advanced

The interesting engineering question is not how many phases but where the invariants sit and who enforces them. Strong invariants let later passes be simple and aggressive; weak ones push defensive checks into every consumer. LLVM's verifier is the load-bearing example: it makes "the IR is well-formed" a checkable property rather than a convention, which is what allows several hundred passes to be written by different people without each one re-validating its input. The same argument explains why query-based compilers took so long to appear — a demand-driven design has no phase order to hang the invariants off, so the invariants have to be attached to the queries instead.

How much this depends on

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

typicalThe stage list and the pass counts describe mainstream ahead-of-time toolchains at present. The middle-end pass count in particular ranges from zero in a teaching compiler to several hundred in Clang at -O3, and the ordering is retuned between releases, so a transformation you observed in one version may not survive an upgrade.

implementationThe claim that the middle-end emits no diagnostics is true of LLVM in the ordinary case and false in detail: several passes emit optimization remarks under -Rpass, and -Wmaybe-uninitialized in GCC is famously a middle-end warning, which is why it appears and disappears with the optimization level.

simplifiedThe rail collapses several real stages. Preprocessing, template instantiation, monomorphization, macro expansion and constant evaluation each occupy a phase in the languages that have them, and each has its own invariant. See [[the-preprocessor]] and [[monomorphization]].

If you were asked this in an interview

Name the phases of a compiler and, for each one, the question it exists to answer that the previous representation could not.
What is the difference between a phase and a pass? Give an example of one phase with several passes.
A compiler crashes rather than reporting an error on your input. What does that tell you, and where do you look first?

Connections

DSAbinary-tree dfs hash-table

Computer Architectureinstruction-decode

OS & Networkingprogram-vs-process

Domains that do not exist yet

Testing & Reliability Engineering — Invariant checking and contract testing at module boundaries in general
A compiler's phase boundaries are contracts and its verifiers are contract tests; the technique is not compiler-specific and is owned there. What is ours is which invariants a representation must carry.