Legalityimplementation

Pass Pipelines

The middle-end is a sequence: IR in, pass, IR out, repeat. Passes come in three kinds — analyses that compute facts, transformations that rewrite, and cleanups that make the next pass's job possible — and the pipeline is how a compiler is actually organised.

The question

How is an optimizer actually structured, and what is a "pass"?

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

What the program is here

One IR, rewritten in place, with a side structure of analysis results attached to it: dominance, loop nests, alias information, call-graph shape. The IR is the program; the analyses are facts about it that are expensive to compute and cheap to invalidate. That split is the whole architecture — passes that only read the facts can be reordered freely, and passes that rewrite must declare what they invalidated, or a later pass will act on a fact that stopped being true.

What this phase may assume or do

A pass may assume the IR it receives satisfies the representation's invariants — well-formed SSA, every block terminated, every phi with one entry per predecessor — because a verifier ran or a previous pass guaranteed it. It may assume analysis results it requests are current, which is the pass manager's obligation to enforce. It may assume nothing about which passes ran before it: a pass that only works after some other pass has run is a latent bug, which is why cleanup passes are scheduled explicitly rather than hoped for.

Key points

A pipeline is IR in, pass, IR out, repeated; the passes come in three kinds and reading a pipeline means telling them apart.
Analyses compute facts and change nothing; transformations rewrite under preconditions; cleanups normalise the IR so the next pass can match on it.
The pass manager's real job is analysis invalidation: stale facts are worse than missing ones, because a transformation on a false fact has no precondition at all.
Passes operate at different granularities — module, call-graph SCC, function, loop — and a pipeline is largely a nesting of those.
Canonicalisation passes are load-bearing rather than cosmetic: most transformations only recognise their opportunity in a canonical form.
The architecture buys testability, bisectability and reuse across frontends and targets, which is why it is universal despite the ordering problem it creates.
AtlasLang's manager is the same idea with no analysis caching and a fixed-point loop, which is enough to demonstrate the enablement cascade.

Three kinds of pass

The word "pass" covers three genuinely different things, and confusing them is why pipelines look arbitrary from outside.

An analysis computes facts and changes nothing: dominance, liveness, loop structure, alias relationships, value ranges, the call graph. It is expensive, it is reused by many transformations, and its result is cached until something invalidates it. [[dominators]], [[liveness-analysis]] and [[alias-analysis]] are all analyses in this sense.

A transformation rewrites the IR under a precondition it establishes from those facts. Inlining, unrolling, vectorization, code motion and every optimization in the optimize and loops modules are transformations. These are the passes that need legality arguments, and they are the ones that invalidate analyses.

A simplification or cleanup normalises the IR so later passes can pattern-match on it: canonicalising commutative operands into a fixed order, simplifying the CFG by merging trivially chained blocks, promoting memory to registers, deleting dead instructions. These are unglamorous and they are load-bearing, because most transformations only recognise their opportunity in a canonical form. LLVM's instcombine and simplifycfg run many times through a pipeline for exactly this reason.

Read a real pipeline with those three categories in mind and it stops looking like a list and starts looking like a rhythm: canonicalise, analyse, transform, clean up, canonicalise again.

One trip through the AtlasLang pipeline, as the pass manager runs itsimplified

Lowered IRbuild time
Three-address SSA over virtual registers, straight from the frontend, with every local still a memory slot.
Constant foldingbuild time
The same IR with literal-operand operations replaced by constants.
Values the frontend could not know were constant.
Strength reductionbuild time
Algebraic identities removed: x + 0, x * 1, x * 0.
Fewer operations, and often a copy the next pass can propagate.
Constant propagationbuild time
Uses of a register whose single definition is a literal replaced by the literal.
Literal branch conditions — the input branch simplification needs.
Copy propagationbuild time
Copies and single-source phis forwarded to their sources.
Direct def-use edges, which makes CSE's key comparison meaningful.
The redundant phis SSA construction inserted on the dominance frontier.
Branch simplificationbuild time
Conditional branches with literal conditions turned into jumps.
The fact that one successor is now unreachable.
The CFG edge to the untaken block — this is where control flow starts disappearing.
Unreachable block eliminationbuild time
Blocks with no path from entry removed, and phi operands naming them dropped.
Entire regions of the function, along with any diagnostics that would have referred to them.
Common subexpression eliminationbuild time
Repeated pure computations replaced by a reference to a dominating one.
Requires a fresh dominator tree, which the CFG changes above invalidated.
Dead code eliminationbuild time
Instructions with no effect and no user removed.
The definitions of values nothing reads — and, with them, the debugger's ability to show those variables.

Read it asRead the adds column as a chain of enablements rather than a list of improvements: propagation exists to make branches literal, branch simplification exists to make blocks unreachable, and elimination exists to make definitions dead. That is why the pass manager repeats the whole sequence until an iteration changes nothing — one trip through leaves work that the trip itself created. The loses column is the price: every entry there is information no later phase can recover, which is why [[debugging-optimized-code]] is hard.

The pass manager, and the thing it is really managing

implementationThe module/CGSCC/function/loop nesting and the require-and-preserve protocol are LLVM's new pass manager as it currently stands; the legacy manager expressed the same ideas with a different and much less explicit dependency mechanism, and GCC organises its pipeline around passes over GIMPLE and RTL with its own property-set machinery. The categories generalise; the API and the exact invalidation rules do not, and LLVM has restructured its pipeline several times.

A pass manager runs the passes, but the job that makes it non-trivial is managing analyses. An analysis result is expensive — computing dominance or alias information over a large function is real work — and it is invalidated by almost any transformation. Recomputing everything after every pass is prohibitively slow; keeping a stale result is a correctness bug of the worst kind, because a transformation acting on a false fact has no precondition at all.

LLVM's answer, in its current pass manager, is an explicit analysis manager: a pass declares which analyses it requires, receives cached results, and returns a set of analyses it preserved. Everything not preserved is dropped and recomputed on demand by whoever asks next. That protocol is why a pass that "does nothing" can still be expensive to insert into a pipeline — if it fails to declare a preservation, it forces a recomputation of everything downstream.

The other structural decision is granularity. Passes operate over different units: a module pass sees the whole translation unit, a call-graph pass sees a strongly connected component of the call graph (which is how inlining and interprocedural work are ordered bottom-up), a function pass sees one function, and a loop pass sees one loop nest. Smaller units mean better locality and the possibility of running in parallel; larger units mean more context. A pipeline is largely a nesting of these: run these function passes over every function inside this call-graph traversal, and repeat this loop pipeline over every loop in each function.

AtlasLang's pass manager is deliberately the simplest thing that demonstrates the ideas: eight function-level passes, no analysis caching — computeDominance is recomputed by the pass that needs it — and a fixed-point loop with a hard iteration bound as a termination guard rather than a tuning knob. That is enough to show the enablement cascade and nothing more, and the gap between it and LLVM's manager is almost entirely the analysis-invalidation protocol.

Pass granularity and what each level can and cannot seeimplementation

Unit	Sees	Cannot see	Typical passes
Module	Every function and global in the translation unit	Anything in another translation unit, absent LTO	Global DCE, internalisation, whole-module attribute inference
Call graph (SCC)	A group of mutually recursive functions and their callees	Callers, since the traversal is bottom-up	Inlining, interprocedural attribute inference
Function	One function's CFG and all its instructions	What its callees do, beyond their attributes	CSE, DCE, simplification, code motion
Loop	One loop nest, its exits and its induction variables	The rest of the function, except through preserved analyses	LICM, unrolling, vectorization, strength reduction

What a pipeline is for, beyond running things in order

A pipeline organised this way buys three things that are easy to overlook until you try to build a compiler without them.

Testability. A pass with a declared input, a declared output and no hidden state can be run in isolation on a small IR file and its output compared against an expected result. That is what opt -passes=dce on a .ll file is, and it is why LLVM's test suite consists overwhelmingly of small IR files with expected output rather than of end-to-end compilations — see [[golden-tests]].

Attribution. When a program is miscompiled, the pipeline gives a bisection space. Run the pipeline with passes disabled one at a time, or up to pass N, and find the pass that introduces the wrong behavior. That reduces "the compiler broke my program" to "this pass, on this function" in a fixed number of steps, and it is the single most useful debugging property the architecture has.

Composability. A frontend for a new language, a backend for a new target and an embedded JIT can share the same passes because none of them knows where the IR came from. That reuse is the entire argument for [[llvm-architecture]] and for [[multiple-frontends-one-backend]], and it only works because a pass's contract is with the IR rather than with the pipeline around it.

The cost is real and worth naming: the discipline of declaring requirements and preservations, the compile time of recomputing invalidated analyses, and the pass-ordering problem that having many independent passes creates in the first place. That last one is large enough to be its own lesson — [[phase-ordering]].

How it works

The steps, in the order the compiler takes them.

The driver selects a pipeline from the optimization level and any explicit pass arguments.
The pass manager walks the pipeline in order, at the appropriate granularity: module passes once, function passes over each function, loop passes over each loop nest.
Before running a pass, the manager supplies the analysis results it declared it requires, computing any that are not cached.
The pass reads the IR and the analyses, tests its precondition, and rewrites where the precondition holds.
It returns which analyses it preserved; everything else is invalidated and will be recomputed when next requested.
Cleanup passes are scheduled explicitly at points where the pipeline knows the IR needs renormalising, rather than being left to chance.
A verifier may run between passes in a debug build, checking the IR's structural invariants and catching a malformed rewrite at the pass that caused it — [[ir-verification]].
The whole sequence may repeat: AtlasLang iterates to a fixed point, and production pipelines schedule specific passes several times at points where earlier passes are known to create work for them.

How it breaks

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

A transformation acts on a stale analysis and produces wrong code, and the symptom appears only when a specific earlier pass happened to invalidate the fact.
A pass produces structurally invalid IR — a phi with an operand for a removed predecessor, an unterminated block — and the crash surfaces in an unrelated pass much later.
A pass silently depends on an earlier one having run, works in the default pipeline, and breaks when someone builds a custom pipeline or the default is reordered.
Compile time regresses badly after a new pass is added, because it failed to declare a preservation and forced a dominator-tree recomputation per function.
A pass is correct in isolation and wrong in combination, because it left the IR in a form the next pass's pattern matcher misreads.
A miscompilation is reproducible only at a specific optimization level, because that level is the only pipeline in which the two passes involved run in that order.

When it helps

Debugging a miscompilation: bisecting the pipeline localises the fault to one pass, which is the difference between a fixable bug and a mystery.
Reading an unfamiliar compiler, where the pipeline definition is the fastest overview of what the middle-end actually does.
Adding an optimization to a real compiler, where the hard part is not the transformation but declaring its analysis requirements and preservations correctly.
Building a domain-specific compiler on existing infrastructure, where you are composing an existing pass set rather than writing one — [[dsl-implementation-strategies]].

When it hurts

Reading pipeline order as a claim about importance. Cleanup passes run most often and are the least interesting; the ordering reflects enablement, not value.
Assuming a named pass is where a specific optimization happened. Production compilers combine several conceptually distinct transformations into single passes such as instcombine, so the attribution from output alone is usually wrong.

What it costs

Every one of these is paid by something.

Many small passes buy testability, bisectability and reuse, and pay repeated traversals of the IR plus the analysis invalidation that each rewrite triggers.
Fusing passes buys compile time — one traversal instead of five, and facts that stay live across the transformations — and pays testability and attribution, since the fused pass can no longer be run or bisected alone.
Caching analyses buys the cost of recomputation and pays an invalidation protocol that every pass author must get right, with a wrong-code bug as the penalty for getting it wrong.
Explicit cleanup scheduling buys predictability and pays pipeline length: LLVM runs instcombine and simplifycfg many times through a default pipeline, and a meaningful share of compile time is those repeats.

What else you could do

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

A single monolithic optimizer that does everything in one traversal, as some fast compilers do: much lower compile time, no ordering problem, and nearly impossible to test or extend in pieces.
Combining passes that mutually enable each other into one algorithm — sparse conditional constant propagation folds, propagates and simplifies branches simultaneously, finding constants none of the three finds alone.
Equality saturation, which represents many equivalent programs at once in an e-graph and extracts the best one, dissolving the ordering problem rather than scheduling around it — at a large cost in memory and implementation.
Superoptimization, which searches for an optimal instruction sequence directly for small regions rather than applying transformations at all. Exact, and far too slow for anything but peepholes — [[peephole-optimization]].

See it for yourself

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

Toggle passes individually at /compilers/passes and watch both the IR after each pass and the fixed-point iteration count change.
LLVM: opt -passes='default<O2>' -print-pipeline-passes prints the entire default pipeline as a single string, which is the most direct answer to "what does -O2 actually run".
LLVM: opt -passes=... -print-after-all (or -print-changed) dumps the IR after each pass, so an unexpected change can be attributed to a specific one.
GCC: -fdump-tree-all and -fdump-rtl-all write one file per pass, numbered in execution order — the same bisection material in a different form.
Run a single pass on hand-written IR: opt -passes=dce input.ll -S. That is what almost every LLVM regression test is, and writing one is the fastest way to understand a pass's contract.

Plausible wrong readings

Stated the way a confident engineer states them.

"A pass is an optimization." Many passes optimize nothing. Analyses compute facts, canonicalisers normalise form, and verifiers only check — and pipelines contain more of those than of transformations.
"Passes are independent, so order does not matter." Order is most of the design. Each pass creates and destroys opportunities for the others — [[phase-ordering]].
"More passes means better code." Beyond a point it means more compile time and more chances to leave the IR in a form the next matcher misses. Production pipelines are curated, not accumulated.
"The pass manager just calls the passes in a list." It arbitrates analysis lifetimes, and that arbitration is the part that produces wrong code when it is wrong.

Misconceptions

The claim, and what is actually true.

The optimizer is one algorithm.

It is dozens to hundreds of small ones with declared contracts, plus a manager arbitrating the facts they share. That structure is what makes any of them testable.

Analyses are just helper functions.

They are cached, shared, and invalidated by rewrites. Managing their lifetimes correctly is where the hardest bugs in a middle-end live.

Cleanup passes are cosmetic.

Most transformations only fire on a canonical form, so canonicalisation is what makes the rest of the pipeline effective. That is why it runs repeatedly rather than once.

Go deeper

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

overview

An optimizer is not one program but a queue of small ones. Each takes the intermediate representation, does one job, and hands it on. Some only compute facts about the code, some rewrite it, and some tidy it into a standard shape so the next one can recognise what it is looking at. Running them in a sensible order, repeatedly, is what "optimizing" actually consists of.

practical

When something in a compiled program is wrong, use the pipeline: dump the IR after each pass and find the first one whose output is wrong. When something is slow to compile, look for a pass that invalidates an expensive analysis and forces recomputation. When you write a pass, the two things to get right are the precondition you test and the analyses you declare you preserved — a wrong preservation is a wrong-code bug, and it will not show up in your pass's own tests.

advanced

The architecture is a bet that composability is worth more than the ordering problem it creates, and the bet is mostly correct: many small, testable, individually bisectable passes are what let a compiler with thousands of contributors stay correct at all. The costs are visible in the places where it strains. Passes that mutually enable each other — folding, propagation and branch simplification — are strictly weaker apart than together, which is why SCCP exists as a single algorithm doing all three. Canonicalisation exists only because passes communicate through a shared representation rather than through structured facts. And the fixed-point iteration that AtlasLang runs explicitly is present in production pipelines as hand-scheduled repeats of specific passes, tuned empirically. Every one of those is a place where the modular design is paying for itself in compile time, and the alternatives — fusion, e-graphs, search — trade that compile time for a different structure with its own costs.

How much this depends on

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

implementationThe require/preserve protocol, the CGSCC traversal and the pipeline-printing flags are LLVM's new pass manager at its current state; the legacy manager and GCC's GIMPLE/RTL pass structure express similar ideas with different mechanisms and different guarantees. Pass names, pipeline contents and even the set of granularities have all changed across LLVM releases, so any concrete pipeline listing dates quickly.

simplifiedAtlasLang's pass manager has no analysis caching at all — the CSE pass recomputes dominance every time it runs — and no granularity beyond the function. That is a deliberate omission: it removes the single hardest part of a real pass manager so the enablement cascade is visible without it. A production compiler that made the same choice would spend most of its compile time recomputing facts.

typicalMainstream compilers fuse conceptually separate transformations into single passes for compile time, so the mapping from "optimization" to "pass" is many-to-one. Attributing a specific change in the output to a specific named optimization therefore requires the per-pass dumps rather than inspection of the final assembly.

If you were asked this in an interview

What are the three kinds of pass, and which of them needs a legality argument?
What is the hardest part of writing a pass manager, and what goes wrong if you get it wrong?
A program is miscompiled at -O2. How does the pipeline structure help you find the cause?

Connections

DSAdag topological-sort dfs

Performanceprofiling-basics

Domains that do not exist yet

Testing & Reliability Engineering — Bisection as a debugging technique
A pipeline turns "the compiler is wrong" into a bisectable sequence with a known number of steps, which is the same technique as bisecting a commit history and works for the same reason. The general practice is owned there; the compiler-specific material is [[golden-tests]] and [[differential-testing]].

Runtime gain3

Compile cost3

Debuggability3

Implementation4

Context dependence3

The architecture does not itself make code faster — it is what makes many independent transformations composable, so the runtime gain is indirect. Compile cost is real and dominated by repeated traversals and analysis recomputation. Implementation complexity is the highest score here: the invalidation protocol, the granularity nesting and the ordering problem are the bulk of a production middle-end's design, and getting the protocol wrong produces silent miscompilation.

Try it

pass manager →ir explorer →pipeline explorer →