Legalityimplementation

Phase Ordering

The same passes in a different order produce different code, and no order is best for every program. Constant propagation, branch simplification and dead-code elimination are the canonical cascade — and running the pipeline to a fixed point is what a compiler does instead of solving the problem.

The question

Does the order of optimization passes matter, and if so, what is the right order?

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

What the program is here

The IR after each pass, considered as a sequence rather than as a result. What matters at this level is not any one representation but the *transitions* between them: each pass leaves the IR in a shape that makes some later passes' preconditions provable and others' unprovable. The pipeline is a path through that space, and the question this framing exists to answer is "which opportunities did this order create, and which did it destroy".

What this phase may assume or do

Order never affects legality. Every pass tests its own precondition on the IR it is given, so any order produces a correct program — an ordering bug produces slower code, not wrong code. What order affects is which preconditions are *provable*: constant propagation makes a branch condition literal, which is what branch simplification requires; branch simplification makes a block unreachable, which is what block elimination requires; removing the block makes definitions unused, which is what dead-code elimination requires. Each pass is the previous one's enabling condition.

Key points

Order never affects correctness — every pass checks its own precondition — so an ordering mistake produces slower code, never wrong code.
Order decides which preconditions are provable, which is why constant propagation, branch simplification and dead-code elimination form a cascade in exactly that direction.
No order is best for every program: inlining, unrolling, code motion and vectorization each both create and destroy each other's opportunities.
Production pass orders are empirical artifacts, tuned against benchmarks and containing deliberate repeats, not derived from any principle.
Iterating to a fixed point recovers most of the enablement cheaply, and needs a hard iteration bound as a termination guard.
Fusing the passes that most need each other — as SCCP does — removes an instance of the problem rather than scheduling around it.
Searching the order per program beats a fixed pipeline and costs many compilations, which is affordable only when the program is compiled once and run forever.

The canonical cascade

The clearest demonstration needs three passes and four lines of source. A variable is assigned a constant; a branch tests it; one arm is therefore unreachable; everything that fed it is therefore dead. No single pass in that chain can do any of the others' work, and each one's output is the next one's input.

Run it in the right order and the whole thing collapses to a single instruction. Run dead-code elimination first and it finds nothing dead, because at that moment the store still has a reader and both branches are still reachable. The pass was correct; it simply ran when its opportunity did not yet exist.

This is the general shape of the problem. A transformation is enabled by the transformations that ran before it, and there is no ordering that enables everything for every program — inlining exposes constants, so it should run early; inlining also grows functions, which makes some analyses less precise, so it should run late; unrolling exposes vectorization opportunities, and vectorization sometimes wants the un-unrolled form. The literature calls this the phase-ordering problem, and it has no closed solution.

let x = 1; if (x == 1) { print(10); } else { print(20); } through the AtlasLang pipeline

After lowering

%1 = const 1
store @x, %1
%2 = load @x
%3 = bool %2 == 1
branch %3 ? b1 : b2
b1: print 10
b2: print 20

At the fixed point

▸print 10

Read it asFour passes and none of them could have gone first. Propagation replaces %2 with 1, which lets folding evaluate 1 == 1 to a literal, which lets branch simplification turn the conditional into a jump, which lets unreachable-block elimination delete b2 — and only then does dead-code elimination find the store and the load with no remaining readers. Toggle any one of them off at /compilers/passes and everything downstream of it stops firing, which is the cascade made visible.

Why there is no best order

The obvious response is to find the order that enables the most. It does not exist, for a reason that is structural rather than a matter of insufficient effort: passes both create and destroy opportunities, and which they do depends on the program.

Inlining versus everything. Inlining substitutes a callee into a caller, exposing the caller's constants to the callee's code — a large source of downstream optimization, arguing for running it early. It also produces a much larger function, and several analyses have per-function size cutoffs beyond which they give up, arguing for running it late. Worse, whether inlining a given call is profitable depends on how much the callee will simplify after substitution, which is not known until after the passes that would simplify it have run.

Unrolling versus vectorization. Unrolling a loop exposes instruction-level parallelism and lets a scheduler interleave iterations. Vectorization wants the rolled form so it can widen the iteration itself. Doing both, in the wrong order, produces an unrolled loop the vectorizer no longer recognises.

Code motion versus register pressure. Hoisting a computation out of a loop removes work per iteration and extends the value's live range, which raises register pressure and may cause a spill in the loop body — trading a cheap recomputation for a memory access, which is a straightforward loss. [[loop-invariant-code-motion]] and [[register-allocation]] are in genuine tension, and the allocator runs much later than the pass whose decision caused the problem.

The result is that pass order in a production compiler is an empirical artifact. It is tuned against benchmark suites, adjusted when a regression is reported, and contains passes scheduled more than once specifically because a later pass creates work for an earlier one. Nobody derives it; everybody measures it.

Pairs of passes that want opposite orderstypical

Pair	Argument for A first	Argument for B first
Inlining / simplification	Substitution exposes constants and dead branches for the simplifier to remove.	A simplified callee is smaller, so the inliner's size heuristic judges it more accurately.
Unrolling / vectorization	Unrolled bodies expose instruction-level parallelism to the scheduler.	The vectorizer needs the rolled form to widen the iteration itself.
LICM / register allocation	Hoisting removes work from every iteration of the loop.	The extended live range may spill, turning a register access into a memory one.
CSE / code motion	Reusing a dominating computation removes an instruction outright.	Sinking a computation to its use may make it dead on some paths entirely.
Devirtualization / inlining	Resolving the target is what makes the call inlinable at all.	Inlining the caller may reveal the concrete type that enables devirtualization.
Vectorization / alias analysis	The vectorizer requests exactly the aliasing facts it needs.	Earlier transformations may have destroyed the memory-access pattern the analysis could reason about.

What compilers do instead of solving it

Iterate to a fixed point. Run the pipeline repeatedly until an iteration changes nothing. This is what AtlasLang does, and it is why the pass manager reports its iteration count rather than assuming one trip sufficed: the count is direct evidence that the passes fed each other. It is the simplest answer, it recovers most of the enablement, and it costs compile time proportional to the number of iterations. A hard bound is required as a termination guard, because two passes can in principle undo each other forever.

Schedule specific passes more than once. Production pipelines do a targeted version of the same thing: run the simplifier again after inlining, run DCE again after the loop passes, run the CFG simplifier at half a dozen points. This is cheaper than iterating everything and is tuned by measurement rather than derived.

Fuse the passes that most need each other. Sparse conditional constant propagation performs constant propagation, folding and branch simplification as one algorithm over a lattice, and finds constants that the three passes separately never converge on, because it treats edges out of provably-false branches as contributing nothing to a merge. This dissolves one instance of the ordering problem by removing the boundary that created it.

Search the order. Iterative compilation and machine-learning-driven pass selection treat the order as a search space and optimize it per program or per function, which measurably beats a fixed pipeline and costs many compilations of the same code. This is practical when a program is compiled once and run for years, and impractical for a normal build.

Change the representation so the order matters less. Equality saturation keeps many equivalent versions of the program in one e-graph and extracts the best at the end, so no rewrite ever destroys an opportunity. It is the most direct attack on the problem and pays for it in memory and implementation complexity, which is why it appears in specialised compilers rather than in general-purpose ones.

The order that finds nothing, and the order that finds everything

Before

DCE first:
  %1 = const 1        (kept: %1 is used)
  store @x, %1        (kept: stores have effects)
  %2 = load @x        (kept: %2 is used)
  %3 = bool %2 == 1   (kept: %3 is used by the branch)
  branch %3 ? b1 : b2 (kept: terminator)
  -> zero instructions removed

After

Propagate, fold, simplify, then DCE:
  %3 becomes const true -> branch becomes jump b1
  -> b2 unreachable, load and store now unread
  -> print 10

Legal only when

Both orders are legal and both produce a correct program: every pass tested its own precondition on the IR it was actually given. The difference is entirely in what was provable at the moment each pass ran, which is why an ordering mistake shows up as slower code rather than as wrong code.

Illegal when

There is no ordering that is illegal — which is precisely what makes this problem hard to notice. A compiler with a badly ordered pipeline passes every correctness test it has, and the only symptom is generated code that is worse than it needed to be, on programs nobody measured. Compare a pass acting on a *stale analysis*, which is a different failure entirely and does produce wrong code — see [[pass-pipelines]].

How it works

The steps, in the order the compiler takes them.

Each pass tests a precondition against the IR it receives; whether that precondition holds depends on what earlier passes did.
A pass that fires changes the IR, creating opportunities for some passes and destroying them for others.
The pipeline order therefore determines which opportunities exist at the moment each pass looks for them.
A fixed-point loop repeats the whole pipeline until an iteration produces no change, so a pass that missed its opportunity gets another chance.
An iteration bound terminates the loop regardless, guarding against two passes that undo each other.
Production pipelines instead schedule chosen passes at several points, tuned by measurement against benchmark suites.
Where two passes are strictly stronger together, they may be fused into one algorithm over a shared lattice, removing the boundary entirely.

How it breaks

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

An optimization that clearly should have applied does not, and the reason is that the pass ran before the pass that would have enabled it.
A source change that should be irrelevant — reordering two declarations, extracting a helper — changes performance measurably, because it changed what a pass could prove at the point it ran.
Compile time doubles after a pipeline change, because the fixed-point loop now needs more iterations to converge on typical input.
Two passes oscillate: one sinks a computation and the other hoists it, and the iteration bound is the only thing that stops the compile.
A benchmark regresses after a compiler upgrade with no pass changed, because the default pipeline order was retuned against a different benchmark suite.
A custom pipeline assembled from individually correct passes produces markedly worse code than the default, because the default order encodes tuning that is nowhere written down.

When it helps

Explaining why an optimization did not happen: the answer is usually about what was provable when, not about whether the compiler knows the transformation.
Understanding compile-time cost: a fixed-point loop and repeated cleanup passes are where a surprising share of it goes.
Building a custom pipeline on LLVM or MLIR, where the default order is the accumulated tuning you are giving up.
Reading missed-optimization remarks, where "not vectorized" frequently means "an earlier pass changed the shape into one the vectorizer does not recognise".

When it hurts

As a reason to hand-tune pass order for a general-purpose compiler. Benchmarks disagree with each other, and an order that wins on one suite routinely loses on another.
As an explanation for a performance problem before measuring. Phase ordering explains small differences; algorithmic and data-layout problems explain large ones, and they are far more likely.

What it costs

Every one of these is paid by something.

Iterating to a fixed point buys most of the enablement with no scheduling effort and pays compile time proportional to the number of iterations, on every function.
Hand-tuned repeats buy most of the same benefit for less compile time and pay maintenance: the schedule encodes empirical knowledge that nobody can re-derive, and it ages with the benchmark suite it was tuned against.
Fusing passes buys strictly better results for the fused pair and pays modularity — the fused algorithm cannot be tested, bisected or reused separately, which is the property [[pass-pipelines]] existed to provide.
Searching the order per program buys measurable improvements over any fixed pipeline and pays many compilations per build, which only pays back for code compiled once and deployed widely.

What else you could do

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

Sparse conditional constant propagation, which unifies folding, propagation and branch simplification over one lattice and finds constants none of them finds alone.
Equality saturation, which represents all equivalent forms simultaneously in an e-graph and extracts the best one, so no rewrite destroys an opportunity — at a substantial cost in memory.
Iterative compilation and learned pass schedules, which search the space per program; effective, and only affordable where compilation cost is amortised over a long deployment.
A JIT, which sidesteps part of the problem by re-optimizing at run time with information the static ordering could not have had, and by discarding and recompiling when the shape changes — [[tiered-compilation]].

See it for yourself

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

Toggle passes at /compilers/passes and watch the reported fixed-point iteration count change: disabling propagation makes the branch cascade stop firing entirely.
LLVM: opt -passes='dce,sccp' versus opt -passes='sccp,dce' on the same .ll file. Two orders, two outputs, both correct.
LLVM: -print-changed shows which passes actually modified the IR, so a pass that fired on the third iteration and not the first is directly visible.
GCC: -fdump-tree-all writes one numbered file per pass; diffing consecutive files shows what each one enabled for the next.
-Rpass-missed=loop-vectorize on a loop that stopped vectorizing after a source change frequently names an earlier transformation as the reason.

Plausible wrong readings

Stated the way a confident engineer states them.

"There is a correct pass order and good compilers use it." There is a well-tuned order for a benchmark suite. Different suites, and different programs, prefer different orders.
"Running everything twice fixes it." It recovers enablement and does nothing for the pairs that actively destroy each other's opportunities, such as unrolling and vectorization.
"Phase ordering is a correctness concern." It is a quality concern. Every order is legal, which is exactly why a badly ordered pipeline passes every test and simply produces worse code.
"The compiler will find it eventually if it iterates enough." Iteration recovers missed enablement. It does not recover an opportunity a transformation destroyed, because the form that opportunity needed no longer exists.

Misconceptions

The claim, and what is actually true.

A wrong pass order can produce a wrong program.

It cannot. Each pass checks its own precondition on the IR it receives, so any order is correct. The cost of a bad order is entirely in code quality.

Compilers pick pass order from theory.

They measure. The order in a production compiler is an accumulation of benchmark-driven decisions and regression fixes, including deliberate repeats of the same pass.

Iterating to a fixed point solves phase ordering.

It recovers enablement that a single pass missed. It does nothing about transformations that destroy each other's opportunities, which is the harder half of the problem.

Go deeper

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

overview

Optimizations feed each other. Replacing a variable with the constant it holds makes a branch condition constant, which makes one side of the branch unreachable, which makes the code that fed it dead. Run those steps in the wrong order and each one finds nothing to do. Since no single order works best for every program, compilers simply run the whole sequence again and again until nothing more changes.

practical

When an optimization you expected did not happen, ask what would have had to be provable at the point that pass ran, and look for the earlier transformation that either failed to expose it or destroyed the shape it needed. Missed-optimization remarks usually name it. And be suspicious of performance differences that follow from apparently meaningless source changes: extracting a helper or reordering declarations can change what a pass could prove, which is a real effect and a small one.

advanced

Phase ordering is the price of the modular pass architecture. Passes communicate only through a shared mutable representation, so each rewrite is destructive: the form one pass produces is the only form the next one sees, and any opportunity that depended on the previous form is gone. Every serious attack on the problem changes that property rather than the schedule. Fusion keeps the intermediate states inside one algorithm. Equality saturation keeps all forms simultaneously and defers the choice to an extraction step. A JIT keeps the ability to start over with better information. Search treats the schedule as the thing being optimized. Recognising which of those four a proposal is makes the literature much easier to read — and it explains why the fixed-point loop, which does none of them, remains the default: it is the only one that costs nothing but compile time.

How much this depends on

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

implementationThat LLVM and GCC schedule specific passes several times, and where, is a per-version property of their default pipelines, retuned against benchmark suites between releases. This is why a benchmark can regress on a compiler upgrade with no pass changed and no source changed — the schedule moved. Print the pipeline for the compiler in front of you rather than relying on any published ordering.

simplifiedAtlasLang iterates its whole eight-pass pipeline to a fixed point with a hard bound of twelve rounds, which is a termination guard rather than a tuning knob. Production compilers do not iterate everything — the compile-time cost would be unacceptable on large functions — and instead hand-schedule repeats of chosen passes. The cascade the fixed point demonstrates is real; the strategy is a teaching simplification.

typicalMainstream compilers order inlining before most scalar simplification and run the simplifier again afterwards, on the reasoning that substitution exposes more than the size heuristic loses. That is a measured default rather than a principle, and specific programs — particularly those with very large callees or deep call chains — do better under other choices, which is what per-function attributes and inlining pragmas exist to express.

If you were asked this in an interview

Give me three passes that must run in a specific order, and say what each one enables.
Can a bad pass order produce an incorrect program? Defend your answer.
How would you decide whether inlining should run before or after your simplifier?

Connections

DSAdag topological-sort

Computer Architectureinstruction-cache

Performancemeasure-before-optimizing performance-regression-detection

Domains that do not exist yet

DevOps / Production Engineering — Build-time budgets and CI cost
Fixed-point iteration and repeated cleanup passes are a real share of compile time, and compile time is paid on every commit by every engineer. Deciding how much build time an optimization schedule may consume is a production-engineering trade-off, and the compiler-side lever is [[incremental-compilation]].