How do you decide the order of an ahead-of-time compiler's optimisation passes when no single order is best for every program?
answer
- passes create and destroy opportunities
- inlining exposes constants for folding
- cheap cleanups after every heavy pass
- motion lengthens ranges, allocator pays
- per-program search costs a compile each
basics
~20 sOrder passes by what they enable: transforms that expose facts run before the passes that consume them, cheap cleanups run after every heavyweight transform, and lossy lowering runs last. Then cap the repetition with a compile-time budget, because searching for a per-program optimal order costs a full compile per candidate.
solid answer
~40 sPasses both create and destroy each other's opportunities, so order changes the result. The backbone is the **enabling chain**: inlining puts a caller's constant arguments inside the callee, propagation carries them to their uses, folding evaluates them, a folded condition makes an arm unreachable, and elimination deletes it. Against that sit **destructive** interactions — hoisting and aggressive scheduling lengthen live ranges and cost spills later; inlining trades code size for those facts. Practice is therefore: a fixed pipeline, cheap cleanup passes (folding, elimination, redundancy removal) repeated after each heavyweight transform to normalise the representation, an iteration cap set by the compile-time budget, and lowering placed late because it destroys information. Searching for the best order per program is possible but costs a compile per candidate, which rarely pays.
go deeper
Recall that a compiler runs many separate passes and that the order they run in changes the code that comes out.
Explain one concrete enabling chain end to end — inlining, then propagation, then folding, then elimination — and say what each step handed to the next.
Show the destructive side from experience: motion and scheduling raising register pressure, inlining thresholds trading size for facts, and how you bisect a pipeline when an optimised build misbehaves.
Own the portfolio: compile-time budget, code size, reproducibility and debuggability, plus the call on whether a per-program search is ever worth a compile per candidate.
## Why order matters at all Each optimisation pass reads one form of the program and writes another. A pass can only fire on opportunities that are *visible* in the form it receives, and every pass changes what the next one sees. That makes ordering a real decision rather than an implementation detail — the same set of passes, in two orders, produces different code. The interactions come in two kinds. **Enabling.** One pass manufactures the precondition another needs. The canonical chain in an ahead-of-time pipeline runs: 1. **Inlining** substitutes a callee's body at the call site, so the caller's argument values are now ordinary local facts rather than opaque parameters. 2. **Constant propagation** carries those literals to their uses inside the substituted body. 3. **Constant folding** evaluates the expressions they now sit in, including branch conditions. 4. A folded condition makes one arm **unreachable**, and elimination removes it — frequently most of the inlined body, which is how inlining pays back its size cost. 5. **Dead-code elimination** then clears the assignment chains whose only consumers have just been replaced by literals. **Destructive.** One pass consumes a resource another needs, or erases information it wanted. - Loop-invariant motion and aggressive instruction scheduling both lengthen live ranges, handing the register allocator a denser interference graph and buying spills in hot loops. - Inlining grows code, which costs instruction-fetch efficiency and compile time, and it is irreversible within the pipeline. - Lowering to a more machine-specific form discards structure — a loop that was obvious becomes a branch to a label — so passes that need that structure must run before it. ## What a real pipeline does about it | tactic | what it buys | |---|---| | fixed, hand-ordered pipeline | predictable, reproducible builds and a bounded compile time | | cheap cleanups repeated after each heavyweight pass | a normalised representation, so every pass sees the same idioms | | an iteration cap on the cleanup loop | a compile-time budget that cannot run away | | heavyweight analyses run once, early | their results stay valid across the cleanups | | lowering placed late | structural passes keep the information they need | | tiers of pipelines, selected per build | a fast build for iteration, a long one for what ships | The repeated-cleanup idea is the important one. Folding, propagation, elimination and redundancy removal are cheap and they *canonicalise*: after they run, the representation is in a predictable shape. Running them between heavyweight transforms means each transform is written against one idiom rather than against everything its predecessors might have emitted. That is worth more than any clever global ordering. ## Why you do not search for the optimal order The best order genuinely is program-specific, and it is possible to search for it: compile with a candidate sequence, measure, try another. Two things make it a poor default. Each candidate costs a full compile plus a measurement run, so the search is orders of magnitude more expensive than the build; and the winner is specific to that program and often to that input distribution, so it must be re-derived when either changes. It is a reasonable investment for a small, extremely hot artefact compiled rarely and run constantly, and an unreasonable one for everything else. ## The judgement a lead actually owns The decision is rarely "which order is fastest". It is a portfolio of constraints: - **Compile-time budget.** Every extra cleanup round is paid by every engineer on every build. - **Code size.** Inlining thresholds are an ordering decision in disguise, because they determine how much material the later passes get to work on. - **Reproducibility.** Two builds of the same source must produce the same output; anything order-dependent on timing or on profile data collected per build breaks that. - **Debuggability.** The more the pipeline rewrites, the less the running code resembles the source, and toolchains differ in how much tracking information they can preserve through it. - **Bisectability.** When an optimised build misbehaves, the fastest route to the cause is to disable passes one at a time, or dump the representation after each. A pipeline built without that affordance turns a one-hour investigation into a one-week one. That last point is the one that most often distinguishes a considered pipeline from an accumulated one: the ordering will be wrong for some program eventually, and what matters is how quickly the team can find out which pass did it.
- Which pass ordering decision most often costs performance rather than gaining it?Anything that lengthens live ranges before allocation. Hoisting invariant work and scheduling definitions earlier both look locally profitable, but they hand the allocator a denser interference graph and can buy a spill and reload inside the hot loop they were meant to speed up. The mitigation is a cost model that is pressure-aware, plus rematerialisation of cheap values at their uses.
- Why do cheap cleanup passes run several times rather than once at the end?Because each heavyweight transform leaves debris and leaves the representation in its own idiom. Running folding, propagation and elimination immediately afterwards both removes the debris and canonicalises the form, so the next transform is written against one shape instead of many. Running them only at the end would mean every pass in between reasons about messier input.
- An optimised build produces the wrong result and the unoptimised one does not. What does the pipeline need to make this tractable?The ability to bisect it: disable passes individually or truncate the pipeline, and dump the intermediate representation after each stage so the first divergent form can be identified. Without that, the investigation is a guess. It is a design property of the pipeline, not something that can be added during the incident.
saying these in an interview costs you the question
- Claims one universally optimal pass order exists.
- Says ordering does not matter once every pass has run.
- Treats every transform as monotonically beneficial.
- Ignores the compile-time cost of extra cleanup rounds.
- Assumes only the final pass affects the generated code.