Step 7 — Pass manager and phase ordering

A pass manager is the small piece of glue that decides which passes to run when. Ours is twenty lines:

PassStats runAll(Module& m) {
    PassStats st;
    for (auto& f : m.functions) {
        for (int i = 0; i < 16; ++i) {
            ++st.iterations;
            bool a = constFold(*f);
            bool b = dce(*f);
            bool c = simplifyCFG(*f);
            if (!a && !b && !c) break;
            ...
        }
    }
    return st;
}

That is enough. But it raises three real questions.

1. Why fixed-point at all?

Each pass can enable the next:

• constFold rewrites cjmp t, bbT, bbF to jmp bbT when t is a known constant.
• simplifyCFG drops the now-unreachable bbF.
• dce drops the temps that were only used inside bbF.
• Some of those temps' definitions were the only uses of even earlier temps. Drop them too.
• Now constFold may see a new chain of single-def Moves. Re-run.

The fuel cap (i < 16) is paranoia: if some pass interaction caused oscillation, we'd notice in tests rather than hanging. In practice real programs reach fix point in 1–3 iterations.

2. Why this order?

constFold → dce → simplifyCFG puts the creator of opportunities first and the consumer last. The reverse order would still reach the fixed point but slower:

Multiply by every program in the test suite and the difference compounds. LLVM's pass pipelines (O0, O1, O2, O3, Os) are extensively tuned for exactly this kind of ordering.

3. Why not analysis caching?

LLVM's "new pass manager" tracks analyses — dominator trees, alias sets, loop info — separately from transforms. Analyses are computed lazily and invalidated when a transform mutates the IR. This avoids re-computing a dominator tree just because some unrelated pass tweaked a branch.

Our compiler has no analyses to cache (no dominator tree, no alias info), so we get away without the machinery. When cp-11/12 introduce LLVM properly, the new pass manager is what schedules everything.

How real compilers structure this

• LLVM opt -O2 runs a sequence of ~70 passes including InstCombine (constant folding + tons of peepholes), GVN, SCCP, LoopUnroll, Inline, SimplifyCFG, DCE, EarlyCSE, ...
• HotSpot C2 runs roughly four phases: GVN, LoopOpts, Macro Expand, Optimisation. Each is itself a fix-point of smaller passes.
• V8 Turbofan runs a graph-based scheduler instead — passes mutate a sea-of-nodes representation, and a final "schedule" pass linearises back to blocks.

The common thread: every modern compiler iterates its passes until nothing changes, then hands off to the backend.

Where this lab takes us

After cp-09 we have:

• A correctness oracle (runProgram).
• A small but real optimisation pipeline.
• Tests that both verify pass behaviour (golden IR) and verify semantic equivalence (interpret before vs after).

cp-10 takes the same IR shape but emits LLVM IR text instead of running our own interpreter. cp-11 hands that off to llc. After that, the pass manager that runs over our IR is LLVM's, not ours.