Lesson 24.1 — Pipeline design: stages, canonical forms and fixpoints¶

Techniques: staged pipelines ordered by enabling relations — each pass consumes some opportunities and creates others; order the passes so that producers run before consumers, grouped into stages; canonicalization gates — a few passes exist to put the program into a normal form (SSA, loop-simplify, LCSSA) that every later pass may assume, and the pipeline re-establishes the form whenever a pass breaks it; fixpoint iteration with change detection — a stage whose passes enable each other is repeated while the module changes, up to a round limit · Pebble implements: all three, in designCoursePipeline (E1), run by the provided pebble-o1 pass · Drill: pass-order · Prerequisites: Lesson 12.2 (pipeline templates, the phase-ordering problem, fixed-point pipelines), Lesson 15.7, Lesson 16.4, Lesson 17.8 · Time: 6 hours

Chapter 12 proved that no fixed order of passes is optimal for every program (Definition 12.2.6) and showed how LLVM assembles default<O2> anyway. This lesson is about assembling yours. You have about twenty passes from Chapters 12–20. Run them in a bad order and half of them do nothing: pebble-gvn before pebble-mem2reg sees only loads and stores and finds no redundancy; pebble-licm before loop-simplify finds no preheader to hoist into. Run them in a good order once and you still miss what a pass exposes for a pass that already ran: after pebble-inline puts a callee's constants into the caller, pebble-sccp has new work, and after pebble-sccp deletes a branch, pebble-simplifycfg and pebble-gvn have new work. The three techniques of this lesson are three answers to "in which order, and how often": order the passes by the facts they produce and consume; put the canonicalizing passes first and repeat them when needed; iterate the mutually enabling group to a fixpoint with a bound. pebblec -O1 is the result: the driver's step list (function(pebble-strength) from Chapter 12, then pebble-o1 from this chapter), where pebble-o1 runs the stages your designCoursePipeline returns.

1. Problem and motivation¶

Staged pipelines by enabling relations¶

Whitfield and Soffa [WS97] made the folk knowledge of compiler writers precise: a transformation has preconditions it needs and postconditions it creates, and one transformation enables another when its postcondition establishes the other's precondition, or disables it when it destroys one. From the enabling and disabling relations they derived orderings for a set of classical optimizations, and showed that some pairs interact in both directions, which is why no total order is right. LLVM's PassBuilderPipelines.cpp [LLVM-PBP] is a hand-tuned answer to the same question: early cleanup, then the inliner with a function simplification pipeline inside it, then loop passes, then a late cleanup. Pebble's pebble-o1 makes the answer explicit as a table of stages, so that you can see and test the order rather than infer it from 2 000 lines of C++.

Canonicalization gates¶

A pass is easier to write and to prove when its input has one shape. Cytron et al.'s SSA form [CFRWZ91] is the canonical example: once every variable has one definition, constant propagation, value numbering and dead-code elimination become sparse. Loop-simplify form and LCSSA (Lesson 15.7) do the same for loop passes: one preheader, one latch, dedicated exits, no value used outside its loop except through a phi. The pipeline discipline is to run the canonicalizing passes first and to treat their output as a precondition, a gate through which every later pass sees the program. It has a price: some passes break the form (inlining brings new allocas, unrolling creates new loops), so the gate must be re-established after them. Chapter 13's canonical forms for expressions (Lesson 13.4) are the same idea at the instruction level.

Fixpoint iteration with change detection¶

Kildall's insight that a dataflow analysis is the least fixpoint of a monotone function (Lesson 14.1) applies to whole pipelines too, in a weaker form: a group of passes that enable each other converges when a round changes nothing. LLVM runs its CGSCC inliner pipeline with devirt<4>, up to four rounds when a devirtualized call appears [LLVM-PBP]; InstCombine iterates its worklist until no rule fires (Lesson 13.4); GCC's pass_fre has a may_iterate flag [GCC-PassesDef]. The questions are when to stop and how to know that something changed. pebble-o1 hashes the printed module after each round, which is exact and cheap at Pebble's scale; a production compiler would use the change flags that passes already return as PreservedAnalyses (Lesson 12.1).

2. Definitions and algorithms¶

Definition 24.1.1 (Facts, abstract program)

Let $\mathcal{F}$ be a finite set of facts: kinds of opportunity a program may hold, such as "there are promotable allocas" ($A$), "a loop lacks a preheader" ($P$), "two instructions compute the same value" ($R$), "a conditional branch has a constant condition" ($C$), "a block is unreachable" ($U$), "an instruction is dead" ($D$), "a computation is loop-invariant" ($I$). The abstract program of a concrete program $P$ is the set $F(P) \subseteq \mathcal{F}$ of facts it holds. An abstract pass is a function $\hat{s} : \mathcal{P}(\mathcal{F}) \to \mathcal{P}(\mathcal{F})$.

Definition 24.1.2 (Enabling relation of a pass)

A pass $s$ is described by three sets $\mathrm{needs}(s), \mathrm{rem}(s), \mathrm{adds}(s) \subseteq \mathcal{F}$ with $\mathrm{rem}(s) \cap \mathrm{adds}(s) = \emptyset$. It is blocked on $F$ when $\mathrm{needs}(s) \cap F \ne \emptyset$ (a fact it needs absent is present), idle when $\mathrm{rem}(s) \cap F = \emptyset$, and enabled otherwise. Its abstract effect is

\[ \hat{s}(F) \triangleq \begin{cases} F & \text{if } s \text{ is blocked or idle on } F \\ (F \setminus \mathrm{rem}(s)) \cup \mathrm{adds}(s) & \text{otherwise.} \end{cases} \]

Pass $t$ enables $s$ (written $t \rhd s$) when $\mathrm{adds}(t) \cap \mathrm{rem}(s) \ne \emptyset$ or $\mathrm{rem}(t) \cap \mathrm{needs}(s) \ne \emptyset$; $t$ disables $s$ when $\mathrm{adds}(t) \cap \mathrm{needs}(s) \ne \emptyset$. The enabling graph has the passes as nodes and an edge $t \to s$ whenever $t \rhd s$.

The course passes (the drill's table)

pass	needs absent	removes	adds
`mem2reg`	–	$A$	–
`loop-simplify`	–	$P$	–
`gvn`	$A$	$R$	$D$
`sccp`	$A$	$C$	$U, D$
`simplifycfg`	–	$U$	–
`licm`	$A, P$	$I$	$R$
`dce`	–	$D$	–

mem2reg $\rhd$ gvn (it removes $A$, which gvn needs absent); sccp $\rhd$ simplifycfg and sccp $\rhd$ dce (it adds $U$ and $D$); licm $\rhd$ gvn (hoisted code can be redundant with code already in the preheader). Nothing disables anything in this table; in the real pipeline the inliner disables gvn and sccp by adding $A$, and unrolling disables licm by adding $P$.

Definition 24.1.3 (Canonical form, canonicalizing pass)

A canonical form is a predicate $\mathcal{C}$ on programs. $\mathcal{C}_{\mathrm{ssa}}(P)$ holds when $P$ has no promotable alloca (Definition 16.4.1); $\mathcal{C}_{\mathrm{loop}}(P)$ holds when every loop is in loop-simplify form and LCSSA (Definitions 15.7.3 and 15.7.4). A pass $c$ is canonicalizing for $\mathcal{C}$ if $\mathcal{C}(c(P))$ holds for every $P$, and a pass $s$ preserves $\mathcal{C}$ if $\mathcal{C}(P) \Rightarrow \mathcal{C}(s(P))$. A pass $s$ assumes $\mathcal{C}$ if its correctness argument uses $\mathcal{C}(P)$ as a precondition. In the abstract model, $\mathcal{C}$ is "$F(P)$ avoids a set of facts": $\mathcal{C}_{\mathrm{ssa}}$ is $A \notin F(P)$ and $\mathcal{C}_{\mathrm{loop}}$ is $P \notin F(P)$; a pass that assumes $\mathcal{C}$ lists those facts in $\mathrm{needs}$.

Staged pipelines by enabling relations¶

Algorithm 24.1.4 (Stage construction from the enabling graph)

Input: the passes $\Sigma$ with their $\mathrm{needs}$, $\mathrm{rem}$, $\mathrm{adds}$; the canonical forms $\mathcal{C}_1, \dots$ with their canonicalizing passes.
Output: a list of stages $\langle (w_1, k_1), \dots, (w_m, k_m) \rangle$: a pass word $w_j$ and a round limit $k_j$.
Precondition: every pass that assumes a form $\mathcal{C}_i$ lists its facts in $\mathrm{needs}$.
Postcondition: for every edge $t \rhd s$ of the enabling graph, $t$ precedes $s$ in some stage word or $s$'s stage follows $t$'s; passes in one strongly connected component share a stage with $k_j > 1$ (Theorem 24.1.10).
Invariant: while stages are emitted, every pass already placed has all of its enablers placed or in the same component.

function BuildStages(Σ, forms):
    G ← enabling graph of Σ                                   # Definition 24.1.2
    comps ← strongly connected components of G, in topological order of the condensation
    stages ← []
    stages.append((canonicalizers of every form, 1))          # the gate: A and P absent from here on
    for comp in comps:
        w ← passes of comp ordered so that each t ⊳ s pair inside comp has t before s
             where possible (any order for the cycle edges)
        w ← w · (canonicalizers of forms that passes of comp break)   # re-establish the gate
        k ← 1 if |comp| = 1 and comp has no self-enabling edge else RoundLimit(comp)
        stages.append((w, k))
    stages.append((dce, simplifycfg, 1))                      # a cleanup stage for the facts the last stage added
    return stages

function RoundLimit(comp):
    return 1 + number of enabling edges inside comp, capped at 3     # Theorem 24.1.12 bounds the useful rounds

designCoursePipeline is this algorithm run by hand on the course's passes, with the interprocedural passes as their own stage because they change every function at once.

The six stages of the reference design, and LLVM's own staging

Reproduce (pebblec and opt 23.1.2 from a -DPEBBLE_USE_SOLUTION=all build; SOL=$PWD/build/ci-solutions-linux, or ci-solutions-macos):

cat > sq.pbl <<'EOF'
fn sq(x: int) -> int { return x * x; }
fn main() -> int { var s = 0; for i in 0..10 { s = s &+ sq(i); } print(s); return 0; }
EOF
$SOL/bin/pebblec --passes='pebble-o1<print>' --emit=llvm sq.pbl -o /dev/null
echo 'define i64 @pebble_main() { ret i64 0 }' > empty.ll
opt -passes='default<O1>' -print-pipeline-passes -disable-output empty.ll | tr ',' '\n' | grep -c .
opt -passes='default<O1>' -print-pipeline-passes -disable-output empty.ll | tr ',' '\n' | grep -n 'cgscc\|^function<\|mem2reg\|^sroa\|loop-simplify\|^licm\|loop-rotate' | head -12

Output (the second listing abridged to the lines that name a stage boundary):

pebble-o1: stage canonicalize (max 1 round): function(pebble-mem2reg,pebble-simplifycfg,pebble-constfold,pebble-peephole,pebble-dce)
pebble-o1: stage early-scalar (max 2 rounds): function(pebble-lvn,pebble-sccp,pebble-simplifycfg,pebble-peephole,pebble-dce)
pebble-o1: stage ipo (max 1 round): pebble-inline<cost>,pebble-funcattrs,function(pebble-tre)
pebble-o1: stage simplify (max 3 rounds): function(pebble-mem2reg,pebble-simplifycfg,pebble-constfold,pebble-peephole,pebble-reassociate,pebble-gvn,pebble-loadfwd,pebble-sccp,pebble-adce,pebble-simplifycfg,pebble-dce)
pebble-o1: stage loops (max 1 round): function(loop-simplify,lcssa,loop(loop-rotate),pebble-licm,pebble-bce,pebble-osr,pebble-strength,pebble-unroll)
pebble-o1: stage late (max 2 rounds): function(pebble-dse,pebble-loadfwd,pebble-gvn,pebble-peephole,pebble-constfold,pebble-adce,pebble-simplifycfg,pebble-dce)
100
6:function<eager-inv>(ee-instrument<>
9:sroa<modify-cfg>
15:function<eager-inv>(mem2reg
22:cgscc(devirt<4>(inline
24:function<eager-inv;no-rerun>(sroa<modify-cfg>
33:licm<no-allowspeculation>
34:loop-rotate<header-duplication;no-prepare-for-lto;no-check-exit-count>
35:licm<allowspeculation>
63:function<eager-inv>(drop-unnecessary-assumes
66:loop(loop-rotate<header-duplication;no-prepare-for-lto;check-exit-count>

What to notice: both pipelines have the shape of Algorithm 24.1.4. LLVM's 100-element default<O1> starts with a canonicalizing function stage (sroa, early-cse, then mem2reg at element 15), puts the inliner in cgscc(devirt<4>(...)) with a function simplification pipeline inside it (elements 22–51: the fixpoint block, run once per SCC and repeated on devirtualization), and runs a separate module optimization stage (from element 63) with loop-rotate and the late licm. The reference design is the same five ideas in six lines, with the round limits written down.

Canonicalization gates¶

Algorithm 24.1.5 (Gated stage)

Input: a stage word $w$, the forms $\mathcal{C}_1, \dots, \mathcal{C}_r$ that passes of $w$ assume, their canonicalizers $c_1, \dots, c_r$.
Output: the word $c_1 \cdots c_r \cdot w'$ where $w'$ is $w$ with $c_i$ re-inserted after every pass that breaks $\mathcal{C}_i$.
Precondition: each $c_i$ is canonicalizing for $\mathcal{C}_i$ and preserves every $\mathcal{C}_j$, $j < i$.
Postcondition: every pass of $w'$ that assumes $\mathcal{C}_i$ runs on a program satisfying $\mathcal{C}_i$ (Proposition 24.1.8).
Invariant: after any prefix of the output word, every form whose last canonicalizer ran after the last breaking pass holds.

function Gate(w, forms):
    out ← [c_1, ..., c_r]
    for s in w:
        out.append(s)
        for i in 1..r:
            if s breaks C_i:                       # e.g. inlining adds allocas; unrolling adds loops
                out.append(c_i)
    return out

In pebble-o1 the gate is spread over the stages: pebble-mem2reg opens both canonicalize and simplify (the inliner between them breaks $\mathcal{C}_{\mathrm{ssa}}$), and loop-simplify,lcssa open the loops stage, because none of the earlier passes maintains loop-simplify form.

Why the gate comes first: value numbering before and after mem2reg

Reproduce (opt 23.1.2 with the course plugin from a -DPEBBLE_USE_SOLUTION=all build, SOL as above):

cat > order.pbl <<'EOF'
fn main() -> int {
    var xs: [int; 8];
    let k = 3;
    var s = 0;
    for i in 0..8 {
        xs[i] = i * k;
        if k > 2 { s = s &+ xs[i] &+ xs[i]; } else { s = s &- 1; }
    }
    print(s);
    return 0;
}
EOF
$SOL/bin/pebblec -O0 --emit=llvm order.pbl -o order.ll
for w in 'print<pebble-icount>' 'pebble-gvn,pebble-mem2reg,print<pebble-icount>' \
         'pebble-mem2reg,pebble-gvn,print<pebble-icount>' \
         'pebble-mem2reg,pebble-simplifycfg,pebble-sccp,pebble-dce,print<pebble-icount>' \
         'pebble-mem2reg,pebble-sccp,pebble-simplifycfg,pebble-dce,print<pebble-icount>'; do
  echo "$w: $(opt -load-pass-plugin=$SOL/lib/PebblePasses.so -passes="function($w)" -disable-output order.ll 2>&1 | cut -d' ' -f3)"
done

Output (complete):

print<pebble-icount>: 103
pebble-gvn,pebble-mem2reg,print<pebble-icount>: 57
pebble-mem2reg,pebble-gvn,print<pebble-icount>: 49
pebble-mem2reg,pebble-simplifycfg,pebble-sccp,pebble-dce,print<pebble-icount>: 50
pebble-mem2reg,pebble-sccp,pebble-simplifycfg,pebble-dce,print<pebble-icount>: 48

What to notice: pebble-gvn before pebble-mem2reg is blocked in the sense of Definition 24.1.2: it numbers loads, which it treats as opaque, and finds nothing, so the pair leaves 57 instructions, the same as pebble-mem2reg alone. After the gate it removes the second xs[i] load and its bounds check: 49. The second pair shows an enabling edge: pebble-sccp folds k > 2 to true and adds an unreachable block ($U$), which pebble-simplifycfg removes only if it runs afterwards (48 vs 50).

Fixpoint iteration with change detection¶

Definition 24.1.6 (Round, stable stage)

A round of stage $(w, k)$ runs the word $w$ once. The stage is stable after round $j$ if the program after round $j$ equals the program before it. pebble-o1 runs rounds $1, \dots, k$ and stops at the first stable round; the stable round counts. Equality is decided by hashing the printed module (exact for a deterministic printer; Chapter 12's snapshot idea).

Algorithm 24.1.7 (Fixpoint stage with change detection: what pebble-o1 runs)

Input: a module $M$ and a design $\langle (w_j, k_j) \rangle_{j=1..m}$ whose words parse.
Output: $M$ transformed.
Precondition: every pass in every $w_j$ preserves the program's behavior (its own chapter's theorem).
Postcondition: the output refines the input (Proposition 24.1.11), and every stage either ran $k_j$ rounds or ended on a stable round.
Invariant: before round $r$ of stage $j$, $M$ is the result of rounds $1..r-1$ of stage $j$ applied to the output of stage $j-1$; the recorded hash is the hash of that $M$.

function RunDesign(M, stages):
    for (w, k) in stages:
        PM ← ParsePipeline(w)                     # a fresh PassBuilder with every course pass registered
        h ← Hash(Print(M))
        for r in 1..k:
            PM.run(M)
            h' ← Hash(Print(M))
            if h' = h: break                      # the stable round
            h ← h'
    return M

Rounds on the witness program

Reproduce (opt 23.1.2 with the course plugin; order.ll from the box above):

opt -load-pass-plugin=$SOL/lib/PebblePasses.so -passes='pebble-o1<trace>' -disable-output order.ll

Output (complete):

pebble-o1: stage canonicalize round 1: 53 instructions
pebble-o1: stage early-scalar round 1: 48 instructions
pebble-o1: stage early-scalar round 2: 48 instructions (unchanged)
pebble-o1: stage ipo round 1: 48 instructions (unchanged)
pebble-o1: stage simplify round 1: 38 instructions
pebble-o1: stage simplify round 2: 38 instructions
pebble-o1: stage simplify round 3: 38 instructions (unchanged)
pebble-o1: stage loops round 1: 39 instructions
pebble-o1: stage late round 1: 38 instructions
pebble-o1: stage late round 2: 38 instructions (unchanged)

What to notice: simplify round 2 has the same instruction count as round 1 but is not reported unchanged: a pass rewrote something without deleting (a peephole rule or a reassociation), so the hash differs and a third round is needed to certify stability. The instruction count is a poor change detector; the hash is exact. The loops stage grows the module by one instruction (loop rotation duplicates the exit test) and the late stage takes it back.

3. Worked example¶

Running example (used for every technique in this lesson): the abstract program $F_0 = \{A, R, C, I, P\}$ and the pass table of the example under Definition 24.1.2, drawn as the enabling graph:

flowchart LR
  M[mem2reg] -->|"A absent"| G[gvn]
  M -->|"A absent"| S[sccp]
  M -->|"A absent"| L[licm]
  LS[loop-simplify] -->|"P absent"| L
  S -->|"adds U"| SC[simplifycfg]
  S -->|"adds D"| D[dce]
  G -->|"adds D"| D
  L -->|"adds R"| G

Staged pipelines by enabling relations¶

Algorithm 24.1.4 on this graph: it is acyclic, so every component is one pass; the topological order puts the canonicalizers first, then sccp and licm (enabled only by canonicalizers), then gvn (enabled by licm), then simplifycfg and dce. One round of the word mem2reg, loop-simplify, sccp, licm, gvn, simplifycfg, dce:

step	pass	before	effect	after
1	mem2reg	{A P R C I}	removes A	{P R C I}
2	loop-simplify	{P R C I}	removes P	{R C I}
3	sccp	{R C I}	removes C, adds U D	{R U D I}
4	licm	{R U D I}	removes I, adds R	{R U D}
5	gvn	{R U D}	removes R, adds D	{U D}
6	simplifycfg	{U D}	removes U	{D}
7	dce	{D}	removes D	{}

Every fact is gone after one round: the order took every opportunity (Theorem 24.1.10). The same passes in the order gvn, mem2reg, sccp, simplifycfg, dce (the first row of the unit-test golden in tools/course/tests/test_ch24.py) leave {P R I} after one round with gvn as a no-op, and need three rounds as a fixpoint loop.

Canonicalization gates¶

The concrete counterpart is the box in §2: pebble-gvn before the gate is a no-op (57 = mem2reg alone), after it does its work (49). Algorithm 24.1.5 on the reference design inserts pebble-mem2reg twice: once at the start and once after pebble-inline, because inlining copies the callee's entry-block allocas into the caller (InlineFunction moves static allocas to the caller's entry block, Lesson 20.3), breaking $\mathcal{C}_{\mathrm{ssa}}$.

Fixpoint iteration with change detection¶

Take the concrete program order.pbl through the reference design; the trace box in §2 is the table. Rounds per stage: 1, 2 (second stable), 1 (stable at once: nothing to inline; main has no callees), 3 (round 2 changed the text without changing the count, round 3 stable), 1, 2 (second stable). Ten pass-manager runs for six stages; the limits MaxRounds = 1, 2, 1, 3, 1, 2 were never the reason a stage stopped.

Try it

./course drill pass-order --seed 3 --difficulty hard, then check yourself with --solution. The hard level asks for the number of rounds, the question Theorem 24.1.12 answers in general.

4. Invariants and correctness¶

Staged pipelines by enabling relations¶

Proposition 24.1.8 (A gated pass is never blocked)

Let $s$ assume $\mathcal{C}$, let $c$ be canonicalizing for $\mathcal{C}$, and let $w = c \cdot u \cdot s$ where every pass of $u$ preserves $\mathcal{C}$. Then $s$ runs on a program satisfying $\mathcal{C}$, for every input.

Proof

By induction on the length of $u$. Base: after $c$, $\mathcal{C}$ holds by the definition of a canonicalizing pass. Step: if $\mathcal{C}$ holds before a pass $t$ of $u$, it holds after, because $t$ preserves $\mathcal{C}$ (Definition 24.1.3). Hence $\mathcal{C}$ holds when $s$ starts. In the abstract model this is Definition 24.1.2: after $c$ the facts of $\mathcal{C}$ are absent, the passes of $u$ do not add them ($\mathrm{adds}(t) \cap \mathrm{needs}(s) = \emptyset$ says exactly that $t$ does not disable $s$), so $s$ is not blocked. The reference design's second pebble-mem2reg exists because pebble-inline does not preserve $\mathcal{C}_{\mathrm{ssa}}$, which violates the hypothesis for the simplify stage unless the gate is repeated.

Definition 24.1.9 (Rank of a fact)

Let the enabling graph be acyclic and let $\mathrm{rank}(s)$ be the length of the longest path ending at $s$ in it. For a fact $f$, let $\mathrm{rank}(f) \triangleq \min\{\mathrm{rank}(s) \mid f \in \mathrm{rem}(s)\}$ (the earliest pass that can remove it), or $\infty$ if no pass removes it.

Theorem 24.1.10 (A topological round leaves no enabled pass)

Let the enabling graph of $\Sigma$ be acyclic and let $w$ list $\Sigma$ in a topological order. Then after one round of $w$ on any $F_0$, no pass of $\Sigma$ is enabled on the result $F_1$: every remaining fact is one that no pass removes, or one whose removing passes are all blocked on $F_1$ (by some remaining fact).

Proof

Suppose some pass $s$ is enabled on $F_1$: $s$ is not blocked and some $f \in \mathrm{rem}(s) \cap F_1$. Consider the moment $s$ ran in the round, with facts $F$. Case 1: $f \in F$ and $s$ was not blocked at that time. Then $s$ removed $f$, and $f \in F_1$ means a later pass $t$ added it: $f \in \mathrm{adds}(t) \cap \mathrm{rem}(s)$, so $t \rhd s$, contradicting that $t$ comes after $s$ in a topological order. Case 2: $f \notin F$ at that time. Then a later pass $t$ added $f$: again $t \rhd s$, contradiction. Case 3: $s$ was blocked by some $g \in \mathrm{needs}(s) \cap F$. Since $s$ is not blocked on $F_1$, some later pass $t$ removed $g$: $g \in \mathrm{rem}(t) \cap \mathrm{needs}(s)$, so $t \rhd s$, contradiction. Hence no such $s$ exists, which is the second sentence of the statement read contrapositively: a remaining fact whose remover $s$ were unblocked on $F_1$ would make $s$ enabled. Every fact of $\mathrm{rank} = \infty$ remains (nothing removes it), and a blocked remover stays blocked only because a fact of $\mathrm{needs}(s)$ remains, so the blocking chains end at facts of rank $\infty$ or at facts whose removers were blocked at their turn.

When it breaks: the argument needs an acyclic enabling graph. With licm $\rhd$ gvn $\rhd$ dce there is no cycle, but the real pipeline has one: pebble-inline enables pebble-sccp (new constants), pebble-sccp enables pebble-simplifycfg, and pebble-simplifycfg, by merging blocks and deleting branches, makes callees smaller and enables pebble-inline again. LLVM's devirt<4> is the same cycle through devirtualized calls. A cycle is exactly what the fixpoint technique is for.

Proposition 24.1.11 (A design refines)

If every pass named in a design preserves behavior (refines its input in the sense of Definition 12.8.2), then Algorithm 24.1.7 refines its input, for any stage words and round limits.

Proof

Refinement is reflexive and transitive: if $P_1 \sqsupseteq P_0$ and $P_2 \sqsupseteq P_1$ then for every input, either $P_0$ is UB, or $P_1$ is not UB and its outcome is included in $P_0$'s, hence $P_2$ is not UB and its outcome is included in $P_1$'s and so in $P_0$'s. Algorithm 24.1.7 runs a finite sequence of passes, each of which refines by hypothesis; by induction on the sequence the output refines the input. The order and the number of rounds are irrelevant to correctness; they only affect how much is optimized. This is why the differential fuzzer of the lab tests behavior at -O1 against pir-run and never the pipeline text.

Canonicalization gates¶

Proposition 24.1.8 is the whole correctness story: a gate turns a pass's precondition into an invariant of the pipeline. The important failure is silent: a pass that assumes $\mathcal{C}_{\mathrm{loop}}$ and runs on a loop without a preheader (pebble-licm hoisting into "the" predecessor of a header that has two) does not crash, it miscompiles. Chapter 18's tests run loop-simplify first for this reason, and pebble-o1's loops stage does too.

Fixpoint iteration with change detection¶

Theorem 24.1.12 (Termination and bound of fixpoint iteration)

Let the enabling graph be acyclic with $d$ the length of its longest path, and let a stage repeat any word $w$ that contains every pass at least once. Then the stage is stable after at most $d + 2$ rounds, and the facts left are those of Theorem 24.1.10.

Proof

Call a pass $s$ settled after round $r$ if $s$ never again runs non-idle and unblocked in later rounds, that is, it never removes or adds anything again. Claim: after round $r$, every pass of rank $\le r - 1$ is settled. Base ($r = 1$, rank 0): a pass $s$ of rank 0 has no enabler, so no pass adds a fact of $\mathrm{rem}(s)$ and no pass removes a fact of $\mathrm{needs}(s)$ (either would be an enabling edge into $s$). Its blocked status can therefore only go from unblocked to blocked (a disabler may add a fact of $\mathrm{needs}(s)$), never back. If blocked at its run in round 1, it never runs. If not, it runs in round 1, removes $\mathrm{rem}(s) \cap F$, and those facts are never re-added; from then on it is idle. Step: let $s$ have rank $r$. Its enablers have rank $< r$ and are settled after round $r$ by the claim, so during round $r + 1$ no fact of $\mathrm{rem}(s)$ is added and no fact of $\mathrm{needs}(s)$ is removed by any pass, before or after $s$ in the word. Hence $s$'s status at its run in round $r + 1$ is final: blocked forever, or unblocked, in which case it removes what it can and, since nothing re-adds those facts (an adder would be an enabler), it is idle afterwards. So $s$ is settled after round $r + 1$. Conclusion: every pass has rank $\le d$, so all are settled after round $d + 1$; round $d + 2$ changes nothing and is the stable round. The facts left are those no pass removes and those whose removers are blocked by such a fact, as in Theorem 24.1.10. Termination holds for a cyclic graph too, by the round limit $k$; what is lost is the guarantee that the stable state has no enabled pass. In the concrete compiler the facts are not finite in this sense (a pass can create arbitrarily many instructions), so MaxRounds is the only guarantee: the reference design uses 3 for simplify, the value of $d + 2$ for the cycle-free part of its enabling graph ($d = 1$: sccp $\rhd$ simplifycfg).

5. Complexity¶

$|\Sigma|$ = passes, $|\mathcal{F}|$ = facts, $d$ = longest path of the enabling graph, $k$ = round limit, $n$ = instructions of the module, $c(s)$ = the cost of pass $s$ on $n$ instructions (Chapters 13–20 give each), $c_{\Sigma} = \sum_s c(s)$.

Technique	Time (worst)	Time (typical)	Space	Justification
Stage construction	$O(\lvert\Sigma\rvert^2 \lvert\mathcal{F}\rvert)$ to build the graph, $O(\lvert\Sigma\rvert + e)$ for SCCs and the topological order	done once, by hand	$O(\lvert\Sigma\rvert + e)$	each pair of passes is compared on $\lvert\mathcal{F}\rvert$ facts; Tarjan's SCC (Lesson 20.2) is linear
Running a staged word once	$c_{\Sigma}$	$c_{\Sigma}$	the module	one run per pass
Canonicalization gates	$+\,c(c_i)$ per re-insertion; `mem2reg` is $O(n \cdot \alpha)$ with pruned SSA (Lesson 16.4), `loop-simplify` $O(n)$	a few percent of $c_{\Sigma}$	the module	the canonicalizers are the cheap passes of the set
Fixpoint iteration	$k \cdot c_{\Sigma}$ per stage, plus $O(n)$ per round for the hash	rounds observed: 1–3 (the trace box; 1.4 per stage on average over the benchmarks, where no stage needs a third round)	one hash	Theorem 24.1.12 bounds the useful rounds by $d + 2$; the hash prints the module once per round

Pathological family (rounds). Take $m$ passes $s_1, \dots, s_m$ with $\mathrm{rem}(s_i) = \{f_i\}$, $\mathrm{adds}(s_i) = \{f_{i+1}\}$, and the word $w = s_m \cdots s_1$ (reverse topological order). Each round removes exactly one fact: $f_1$ in round 1 (its remover runs last), $f_2$ in round 2 (added in round 1 by $s_1$, removed by $s_2$ which runs before $s_1$ in the word, so only in the next round), and so on. The stage needs $m + 1$ rounds, $m \cdot (m + 1)$ pass runs, for work that the topological order does in one round of $m$ runs. Chapter 12's default<O2> has 119 elements for the same reason LLVM's pipeline is long rather than iterated: a long topological word is cheaper than iteration.

At scale: LLVM caps devirt at 4 iterations (MaxDevirtIterations in PassBuilderPipelines.cpp [LLVM-PBP]) and runs InstCombine with max-iterations=1 in default<O1> (the printed instcombine<max-iterations=1;no-verify-fixpoint> above; Lesson 13.4 §7); on the eight benchmarks of this chapter pebble-o1 runs 6–9 pass-manager rounds for its 6 stages (bench-fib: every stage after canonicalize is stable at once; the others: early-scalar, simplify and late each certify stability in a second round) and its compile time is 1.2–2.2× that of -O0 on the run recorded in benchmark.md.

Staged pipelines by enabling relations¶

Extension points [LLVM-PB]: a fixed stage list with hooks (registerPeepholeEPCallback, registerPipelineStartEPCallback) where a plugin inserts passes; trade-off: the plugin sees the stage's canonical form but cannot reorder the stage (Lesson 12.2).
Search-based ordering [CSS99, KWTD06]: genetic search or exhaustive enumeration of distinct outcomes per program; trade-off: minutes of compile time for a few percent, used offline to tune the fixed order (Lesson 12.2, Algorithm 12.2.7).
Learned decisions [TQB+21]: MLGO replaces a heuristic inside a fixed pipeline (the inliner's decision, the eviction order of the register allocator) by a learned model, rather than reordering passes; trade-off: a model in the compiler, retrained per target.
Combined passes instead of ordering (Lesson 17.8): Click and Cooper's combined constant propagation and unreachable-code elimination, and equality saturation, remove the ordering problem for a subset of passes; trade-off: an algorithm per combination.

Canonicalization gates¶

Canonical instruction forms (Lesson 13.4) [LLVM-InstCombine]: InstCombine's rewrites choose one spelling per computation (x * 2 → x << 1, commuted constants on the right) so that later pattern matchers see one shape; trade-off: a rewrite that is not itself an optimization.
Loop canonicalization (Lesson 15.7): loop-simplify, LCSSA and loop-rotate (which makes the latch the exiting block, the shape pebble-unroll requires); trade-off: rotation duplicates the exit test (the $+1$ instruction in the trace box).
Canonicalize-then-lower in MLIR (Lesson 24.7): a canonicalize pass runs the dialects' canonicalization patterns before every lowering; trade-off: patterns must be registered per operation.
Verified canonical forms: LLVM's -verify-each and the LoopSimplify verifier check the form after every pass in debug builds; trade-off: compile time, only in +Asserts builds.

Fixpoint iteration with change detection¶

Change flags from PreservedAnalyses (Lesson 12.1): a pass that returns all() changed nothing, so a round is stable when every pass did; trade-off: a pass that lies (changes and preserves all) hides the change; pebble-o1 hashes instead.
Worklist iteration inside a pass (InstCombine, Lesson 13.4): re-examine only the users of a changed instruction; trade-off: the fixpoint is per pass, not across passes.
devirt<N> [LLVM-PBP]: repeat the inliner pipeline only when a devirtualized call site appeared, at most $N$ times; trade-off: a specific trigger instead of a general change test.
Bounded rounds with a time budget (GCC's --param max-iterations-style limits): stop by count or by compile time; trade-off: results depend on the machine's speed.

7. In real compilers¶

Staged pipelines by enabling relations¶

LLVM

llvm/lib/Passes/PassBuilderPipelines.cpp — PassBuilder::buildPerModuleDefaultPipeline, buildModuleSimplificationPipeline, buildInlinerPipeline (the devirt<MaxDevirtIterations> wrapper), buildO1FunctionSimplificationPipeline, buildModuleOptimizationPipeline (LLVM 23.1.2) [LLVM-PBP]. The textbook version has one word; LLVM's is a tree of adaptors: module(function(...), cgscc(devirt(inline, function(...))), function(loop(...))), because the pass manager runs function passes on one function at a time, and CGSCC passes bottom-up over the call graph (Lesson 12.1).

GCC gcc/passes.def — NEXT_PASS and PUSH_INSERT_PASSES_WITHIN (GCC 15) [GCC-PassesDef]: the same staging as a static list (pass_all_early_optimizations, IPA passes, pass_all_optimizations), with may_iterate passes.
CompCert driver/Compiler.v — transf_rtl_program (CompCert 3.15) [CompCert-Compiler]: a fixed word of RTL passes (Tailcall, Inlining, Renumber, Constprop, Renumber, CSE, Deadcode, ...), each with a proof; note Renumber after Inlining and after Constprop: a canonicalization gate (contiguous node numbering), re-run after every pass that breaks it.

Find where LLVM does it. Open llvm/lib/Passes/PassBuilderPipelines.cpp and find buildInlinerPipeline. Question: which constant bounds the devirt iterations, and what is its value (the N of devirt<N> that opt -passes='default<O2>' -print-pipeline-passes prints)? (Quiz find-devirt-iterations.)

Canonicalization gates¶

LLVM

llvm/lib/Transforms/Utils/LoopSimplify.cpp — simplifyLoop, LoopSimplifyPass::run; llvm/lib/Transforms/Utils/LCSSA.cpp — formLCSSA; llvm/lib/Transforms/Utils/Mem2Reg.cpp — PromotePass (LLVM 23.1.2) [LLVM-LoopSimplify]. The loop pass manager re-establishes both forms itself: LoopPassManager requires LoopSimplifyPass and LCSSAPass before every loop pipeline (FunctionToLoopPassAdaptor in llvm/include/llvm/Transforms/Scalar/LoopPassManager.h), and LoopStandardAnalysisResults carries the analyses they preserve. The textbook says "assume loop-simplify form"; LLVM makes the adaptor guarantee it.

GCC gcc/tree-ssa-loop-manip.cc — rewrite_into_loop_closed_ssa (loop-closed SSA, GCC 15) [GCC-LoopManip]; GCC's pass_fix_loops and loop_optimizer_init (LOOPS_NORMAL) play the role of loop-simplify.
MLIR mlir/lib/Transforms/Canonicalizer.cpp — the canonicalize pass (LLVM 23.1.2): dialect-provided canonicalization patterns run to a fixpoint by the greedy driver, before and after lowerings.

Find where LLVM does it. In llvm/include/llvm/Transforms/Scalar/LoopPassManager.h, find where FunctionToLoopPassAdaptor::run establishes loop-simplify form and LCSSA before running the loop passes. Question: which two passes does it run, and which flag makes it use MemorySSA?

Fixpoint iteration with change detection¶

LLVM

llvm/lib/Analysis/CGSCCPassManager.cpp — DevirtSCCRepeatedPass::run (declared in llvm/include/llvm/Analysis/CGSCCPassManager.h; LLVM 23.1.2) [LLVM-CGSCC]: runs the wrapped pass, then checks whether an indirect call became direct (it keeps value handles on the indirect calls, UR.IndirectVHs, and counts direct and indirect calls per function before and after), and repeats up to MaxIterations times. The change detector is specific: not "did anything change" but "did a devirtualization happen", because that is the only change worth another inliner round.

GCC gcc/passes.def: NEXT_PASS (pass_fre, true /* may_iterate */) and pass_cse_sincos's neighbors; gcc/tree-ssa-sccvn.cc iterates do_rpo_vn when may_iterate is set [GCC-PassesDef].
Pebble pebble/lib/Passes/Pipeline/provided/O1Pass.cpp — O1Pass::run: Algorithm 24.1.7 with std::hash of the printed module.

Find where LLVM does it. In llvm/lib/Analysis/CGSCCPassManager.cpp, find DevirtSCCRepeatedPass::run. Question: what does it keep on the indirect call sites to detect that one of them was devirtualized, and what does it do when none was?

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Staged pipeline by enabling relations	every enabled opportunity is taken once (Theorem 24.1.10); order effects visible (57 vs 49 instructions on the witness)	one run of each pass · `pebble-o1` 6 stages, 10–20 ms on the benchmarks	predictable, explainable by the stage list	low: a table	every production optimizer (LLVM, GCC, CompCert)
Canonicalization gates	passes see one shape; a pass written for $\mathcal{C}_{\mathrm{ssa}}$ is correct on every program (Proposition 24.1.8)	mem2reg, loop-simplify, lcssa are near-linear · negligible	fewer special cases in every later pass	low, but the discipline must be kept: re-canonicalize after passes that break the form	LLVM (`mem2reg`, `loop-simplify`, `lcssa`, instcombine's canonical forms)
Fixpoint iteration	reaches every opportunity the passes can expose to each other (Theorem 24.1.12); bounded by the round limit	$O(k \cdot \lvert w \rvert)$ pass runs for $k$ rounds · rounds 1–3 in practice (the trace box)	diminishing returns; a change detector is needed	moderate: hashing or change flags	LLVM `devirt<4>`, InstCombine's worklist, GCC `may_iterate`, `pebble-o1`'s `MaxRounds`

Choose a staged word when the enabling graph is acyclic or nearly so: it is the cheapest complete order. Choose a gate when a pass has a precondition that another pass can break: it is cheaper to re-run mem2reg than to teach gvn about allocas. Choose iteration when a cycle exists (inlining ↔ simplification) and each round is cheap relative to what it exposes; set the limit from the cycle's length, not from hope.

Measured (benchmark.md, reproduce with bench.py): the reference design gives a geometric-mean speedup of 3.6× over -O0 on the eight benchmarks against 4.1× for LLVM's -O2, at 1.2–2.2× the compile time of -O0; -O1 leaves 1.3× the instructions of -O2 on the mean, from 0.7× (bench-matmul, where -O2 unrolls) to 1.9× (bench-fib).

9. Assessment¶

Quiz: stage-order-witness (sequence), enabling-edges (mapping), gate-mem2reg-twice (single), canonical-form-breakers (set), fixpoint-rounds (number), find-devirt-iterations (number). Tags staged-pipeline, canonicalization, fixpoint-iteration.
Drill: ./course drill pass-order (easy: the facts left; medium: plus the no-op passes; hard: plus the rounds of the fixpoint loop).
Flashcards: tags staged-pipeline, canonicalization, fixpoint-iteration.
Exercises: E1 (designCoursePipeline: the stages, their words and round limits; tests ch24.Pipeline.*, ch24.lit, ch24.e2e, ch24.e2e-ch11), E2 (the benchmark report).

Pitfall

"More rounds are always safe." Correct, yes (Proposition 24.1.11); useful, no. A round that changes the text without changing the behavior (reassociation, peephole rewrites that ping-pong between two canonical spellings) never becomes stable, so a design without MaxRounds can loop forever. Theorem 24.1.12's bound $d + 2$ is the number to write down, and the change detector must be exact: instruction counts miss rewrites (the trace box).

References¶

See the chapter references.

pass	needs absent	removes	adds
`mem2reg`	–	\(A\)	–
`loop-simplify`	–	\(P\)	–
`gvn`	\(A\)	\(R\)	\(D\)
`sccp`	\(A\)	\(C\)	\(U, D\)
`simplifycfg`	–	\(U\)	–
`licm`	\(A, P\)	\(I\)	\(R\)
`dce`	–	\(D\)	–

Technique	Time (worst)	Time (typical)	Space	Justification
Stage construction	\(O(\lvert\Sigma\rvert^2 \lvert\mathcal{F}\rvert)\) to build the graph, \(O(\lvert\Sigma\rvert + e)\) for SCCs and the topological order	done once, by hand	\(O(\lvert\Sigma\rvert + e)\)	each pair of passes is compared on \(\lvert\mathcal{F}\rvert\) facts; Tarjan's SCC (Lesson 20.2) is linear
Running a staged word once	\(c_{\Sigma}\)	\(c_{\Sigma}\)	the module	one run per pass
Canonicalization gates	\(+\,c(c_i)\) per re-insertion; `mem2reg` is \(O(n \cdot \alpha)\) with pruned SSA (Lesson 16.4), `loop-simplify` \(O(n)\)	a few percent of \(c_{\Sigma}\)	the module	the canonicalizers are the cheap passes of the set
Fixpoint iteration	\(k \cdot c_{\Sigma}\) per stage, plus \(O(n)\) per round for the hash	rounds observed: 1–3 (the trace box; 1.4 per stage on average over the benchmarks, where no stage needs a third round)	one hash	Theorem 24.1.12 bounds the useful rounds by \(d + 2\); the hash prints the module once per round

Lesson 24.1 — Pipeline design: stages, canonical forms and fixpoints¶

1. Problem and motivation¶

Staged pipelines by enabling relations¶

Canonicalization gates¶

Fixpoint iteration with change detection¶

2. Definitions and algorithms¶

Staged pipelines by enabling relations¶

Canonicalization gates¶

Fixpoint iteration with change detection¶

3. Worked example¶

Staged pipelines by enabling relations¶

Canonicalization gates¶

Fixpoint iteration with change detection¶

4. Invariants and correctness¶

Staged pipelines by enabling relations¶

Canonicalization gates¶

Fixpoint iteration with change detection¶

5. Complexity¶

6. Variants and refinements¶

Staged pipelines by enabling relations¶

Canonicalization gates¶

Fixpoint iteration with change detection¶

7. In real compilers¶

Staged pipelines by enabling relations¶

Canonicalization gates¶

Fixpoint iteration with change detection¶

8. Comparison¶

9. Assessment¶

References¶