Lesson 12.2 — Pipelines, plugins and extension points, and the phase-ordering problem¶

Techniques: pass plugins and extension points (LLVM's PassPlugin API, PassBuilder parsing and extension-point callbacks, the course registry); how -O1/-O2/-O3/-Os pipelines are assembled (buildPerModuleDefaultPipeline, simplification vs optimization pipelines, optsize/minsize); the phase-ordering problem (non-commuting passes, fixed-point pipelines, search) · Pebble implements: pebble-strength joins the course -O1 pipeline (E2) · Drill: none (see §9) · Prerequisites: Lesson 12.1 · Time: 3–4 hours

clang -O2 does not run "the optimizer"; it runs a pipeline: 119 top-level entries in LLVM 23, many of them adaptors holding dozens more passes, several passes appearing four or five times. Who decides that list, how can you add your own pass to it without recompiling LLVM, and why is there no single best order? This lesson answers the three questions: plugins and extension points, pipeline assembly, and phase ordering.

1. Problem and motivation¶

Pass plugins and extension points¶

A compiler ships a fixed set of passes, but users (researchers, language implementers, this course) need their own. Rebuilding LLVM for every experiment is not an option, so LLVM loads pass plugins: shared libraries exporting llvmGetPassPluginInfo, whose callback registers passes with a PassBuilder [LLVM-WNPM]. Registered passes are reachable by name in textual pipelines (opt -passes=pebble-strength). To join the default pipelines, a plugin registers callbacks at extension points: named holes in the pipeline templates (registerPeepholeEPCallback, registerOptimizerLastEPCallback, …) [LLVM-PB]. The legacy manager had the same idea (PassManagerBuilder::addExtension); GCC plugins insert passes relative to a named existing pass (register_callback(..., PLUGIN_PASS_MANAGER_SETUP, ...) with a register_pass_info) [GCC-Plugins].

Optimization pipelines¶

A pipeline for an optimization level is a design artifact: simplify first (inline, SROA, InstCombine, SimplifyCFG, GVN, loop canonicalization), then optimize for the machine (vectorize, unroll, lower). LLVM builds it in code, in PassBuilderPipelines.cpp [LLVM-PBP]; -print-pipeline-passes prints it as text you can re-run with -passes=. Size levels are no longer separate pipelines in LLVM 23: -Os/-Oz are the -O2 pipeline on functions carrying optsize/minsize attributes, which cost models consult.

Phase ordering¶

Passes do not commute: CSE before mem2reg sees loads and stores and finds nothing to merge; after mem2reg it removes a multiplication (§3). The phase-ordering problem asks for the sequence of passes that optimizes a metric for a given program. It has been attacked by exhaustive enumeration of distinct pipeline outcomes [KWTD06], genetic search [CSS99] and, in production compilers, by hand-tuned fixed pipelines that repeat cheap canonicalizing passes. Pebble meets it in Chapter 24, where you order your own passes.

2. Definitions and algorithms¶

Definition 12.2.1 (Pipeline text)

LLVM's textual pipelines are words of the grammar

\[ \begin{aligned} \mathit{pipeline} &\to \mathit{element} \;\{\; \texttt{,}\ \mathit{element} \;\} \\ \mathit{element} &\to \mathit{name} \;[\; \texttt{<}\ \mathit{params}\ \texttt{>} \;]\; [\; \texttt{(}\ \mathit{pipeline}\ \texttt{)} \;] \end{aligned} \]

where name is a run of letters, digits and -_., and params is any text with balanced <>. An element with a parenthesized sub-pipeline is an adaptor (function(...), cgscc(...), loop(...), devirt<4>(...)) or a nested pass manager; the others are passes, require<a>, invalidate<a>, or default<O2>-style aliases.

Pass plugins and extension points¶

Definition 12.2.2 (Plugin, registration, extension point)

A plugin is a shared object exporting PassPluginLibraryInfo llvmGetPassPluginInfo() with fields APIVersion (LLVM_PLUGIN_API_VERSION, 2 in LLVM 23), PluginName, PluginVersion and RegisterPassBuilderCallbacks(PassBuilder &) (llvm/include/llvm/Plugins/PassPlugin.h [LLVM-PassPlugin]). A parsing callback is a partial function $\kappa : \mathit{name} \times \mathit{PM} \rightharpoonup \mathit{PM}$ that appends a pass for a name it accepts. An extension point $e$ of a pipeline template $T$ is a position where the builder calls $T$'s registered callbacks $\mathcal{C}_e = \langle c_1, \dots, c_m \rangle$; the instantiated pipeline is $T[e \mapsto c_m \circ \dots \circ c_1(\mathit{PM}_e)]$ for every $e$.

Algorithm 12.2.3 (Resolving a pipeline element, PassBuilder::parsePassPipeline)

Input: pipeline text $t$; the built-in pass registry $\mathcal{R}$ (PassRegistry.def); parsing callbacks $\kappa_1, \dots, \kappa_r$ in registration order.
Output: a pass manager, or an error "unknown pass name".
Precondition: $t$ is a word of Definition 12.2.1.
Postcondition: each element became exactly one pass or adaptor of the right IR level.
Invariant: the current nesting level (module, cgscc, function, loop) of every element is determined by its enclosing adaptors; an element whose level is lower than the current one is wrapped in the adaptor chain.

function Parse(t, level):
    elements ← ParseList(t)                  # recursive descent on Definition 12.2.1
    PM ← new pass manager at level
    for E in elements:
        if E has a sub-pipeline and E.name names an adaptor A:
            PM.add(A(Parse(E.sub, InnerLevel(A))))
        else if E.name ∈ R at level:
            PM.add(R[E.name](E.params))
        else if some κ_j (first in registration order) accepts (E.name, PM):
            pass                              # κ_j appended its pass
        else if E.name is a pass of a lower level L' < level:
            PM.add(AdaptorChain(level, L')(Parse(E, L')))
        else:
            error "unknown pass name 'E.name'"
    return PM

The course registry is a set of parsing callbacks

pebble/lib/Passes/Registry.cpp gives each PEBBLE_FUNCTION_PASS("pebble-strength", StrengthPass) one parsing callback that accepts the name (and pebble-strength<params>) and appends the pass. A skeleton build has no such callback, so Algorithm 12.2.3 reaches the last line: that is the "unknown pass name 'pebble-strength'" your tests show before you write the pass.

Optimization pipelines¶

Definition 12.2.4 (Pipeline template, optimization level)

An optimization level is $\ell \in \{\mathrm{O0}, \mathrm{O1}, \mathrm{O2}, \mathrm{O3}\}$ plus the size attributes of each function. A pipeline template $T_\ell$ is a function from $\ell$ and the registered extension-point callbacks to a module pipeline. In LLVM 23,

\[ T_\ell = \mathrm{prologue} \cdot \mathcal{C}_{\mathrm{PipelineStart}} \cdot \mathrm{Simplify}_\ell \cdot \mathrm{Optimize}_\ell \cdot \mathrm{epilogue} \]

where $\mathrm{Simplify}_\ell$ is buildModuleSimplificationPipeline (IPSCCP, globalopt, the CGSCC inliner pipeline with function simplification inside) and $\mathrm{Optimize}_\ell$ is buildModuleOptimizationPipeline (loop rotation and unrolling, vectorizers, final cleanup).

Algorithm 12.2.5 (Per-module default pipeline, buildPerModuleDefaultPipeline)

Input: level $\ell$, LTO phase, registered EP callbacks.
Output: the module pass manager for default<ℓ>.
Precondition: $\ell \ne \mathrm{O0}$ (O0 has its own builder: only required passes such as always-inline).
Postcondition: the pipeline of Definition 12.2.4, with EP callbacks inserted at their points.
Invariant: every element added is a pass or adaptor valid at module level.

function PerModuleDefault(ℓ, phase):
    MPM ← ⟨ memprof-remove-attributes (if no LTO), annotation2metadata, forceattrs ⟩
    MPM ← MPM · Callbacks(PipelineStart, ℓ)
    MPM ← MPM · ModuleSimplification(ℓ, phase)   # inferattrs, early function cleanup (EarlySimplification EP),
                                                 # ipsccp, globalopt, cgscc(devirt<4>(inline, function-attrs,
                                                 #   function(FunctionSimplification(ℓ)))), ...
    MPM ← MPM · ModuleOptimization(ℓ, phase)     # OptimizerEarly EP, loop rotate/unroll, vectorizers
                                                 # (VectorizerStart/End EPs), OptimizerLast EP, cleanup
    MPM ← MPM · ⟨ annotation-remarks ⟩ · (LTO pre-link additions)
    return MPM

function FunctionSimplification(ℓ):
    if ℓ = O1: return O1FunctionSimplification()    # no GVN, no jump threading, fewer loop passes
    return ⟨ sroa, early-cse<memssa>, speculative-execution, jump-threading, correlated-propagation,
             simplifycfg, instcombine, Peephole EP, ..., loop(licm, loop-rotate, simple-loop-unswitch, ...),
             ..., sroa, vector-combine, mldst-motion, gvn, sccp, bdce, instcombine, Peephole EP,
             jump-threading, correlated-propagation, adce, memcpyopt, dse, loop(licm), coro-elide,
             simplifycfg, instcombine, Peephole EP ⟩  # abridged; print it with -print-pipeline-passes

Phase ordering¶

Definition 12.2.6 (Phase-ordering problem)

Let $\Sigma$ be a finite set of passes, each a total function $\mathcal{P} \to \mathcal{P}$, and let $m : \mathcal{P} \to \mathbb{N}$ be a cost (instruction count, code size, run time on an input). For a word $w = s_1 \cdots s_\ell \in \Sigma^{*}$ write $w(P) = s_\ell(\cdots s_1(P))$. The phase-ordering problem for $P$ and a length bound $L$ asks for $\arg\min_{w \in \Sigma^{\le L}} m(w(P))$. Two passes commute on $P$ if $s t(P) = t s(P)$.

Algorithm 12.2.7 (Exhaustive phase-order search over distinct outcomes, after Kulkarni et al.)

Input: program $P$, passes $\Sigma$, cost $m$, length bound $L$.
Output: a word $w \in \Sigma^{\le L}$ minimizing $m(w(P))$.
Precondition: passes are deterministic; programs can be compared for equality (e.g. by hashing printed IR).
Postcondition: the returned $w$ is optimal among $\Sigma^{\le L}$.
Invariant: seen maps every distinct program reachable with at most $d$ passes to a shortest word producing it.

function Search(P, Σ, m, L):
    seen ← { P ↦ ε }; frontier ← [P]; best ← P
    for d ← 1 to L:
        next ← []
        for Q in frontier:
            for s in Σ:
                R ← s(Q)
                if R ∉ dom(seen):              # a pass that changed nothing, or reached a known program, is pruned
                    seen[R] ← seen[Q] · s
                    next ← next · [R]
                    if m(R) < m(best): best ← R
        frontier ← next
    return seen[best]

Definition 12.2.8 (Fixed-point pipeline)

A fixed-point pipeline repeats a word $w = s_1 \cdots s_\ell$ as long as some pass of the round reported a change (it returned something other than "all preserved"): round $j+1$ runs iff some $s_i$ changed its input in round $j$. It stabilizes at $w^{\omega}(P) = w^{j}(P)$ if round $j+1$ changes nothing. GCC's pass_fre with may_iterate, LLVM's devirt<4> and InstCombine's internal worklist are bounded instances.

3. Worked example¶

The running example is the function of Chapter 12's pass exercises:

int f(int a, int b) {
  int x = a * b;
  int y = a * b;
  return (x + y) * 8;
}

compiled with clang -O0 -Xclang -disable-O0-optnone, so every local lives in an alloca. Take $\Sigma = \{\texttt{mem2reg}, \texttt{early-cse}, \texttt{pebble-strength}\}$ and $m$ = instructions in the function body. All $3! = 6$ orders of the three passes, run with opt 23.1.2 and the course plugin:

order	instructions	why
mem2reg, early-cse, pebble-strength	4	CSE sees `mul %a, %b` twice on SSA values and merges them
mem2reg, pebble-strength, early-cse	4	same; strength reduction is independent of the other two
pebble-strength, mem2reg, early-cse	4	same
early-cse, mem2reg, pebble-strength	5	CSE ran on loads and stores: the two `mul`s read different loads
early-cse, pebble-strength, mem2reg	5	same
pebble-strength, early-cse, mem2reg	5	same

So early-cse and mem2reg do not commute on $P$ (Definition 12.2.6), while pebble-strength commutes with both: it only needs the constant operand, which is there before and after mem2reg. Algorithm 12.2.7 with $L = 3$ finds a 4-instruction result after exploring the distinct programs; the ordering constraint "promote memory before CSE" is exactly what LLVM's simplification pipeline hard-codes (sroa precedes early-cse in FunctionSimplification).

Two passes that do not commute

Reproduce (clang 23.1.2, opt 23.1.2):

printf 'int f(int a, int b) {\n  int x = a * b;\n  int y = a * b;\n  return x + y;\n}\n' > po.c
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm po.c -o po.ll
for p in 'early-cse,mem2reg' 'mem2reg,early-cse'; do
  echo "== $p"; opt -passes="$p" -S po.ll | sed -n '/^define/,/^}/p'
done

Output:

== early-cse,mem2reg
define dso_local i32 @f(i32 noundef %a, i32 noundef %b) #0 {
entry:
  %mul = mul nsw i32 %a, %b
  %mul1 = mul nsw i32 %a, %b
  %add = add nsw i32 %mul, %mul1
  ret i32 %add
}
== mem2reg,early-cse
define dso_local i32 @f(i32 noundef %a, i32 noundef %b) #0 {
entry:
  %mul = mul nsw i32 %a, %b
  %add = add nsw i32 %mul, %mul
  ret i32 %add
}

What to notice: the same two passes, two results. Before mem2reg the multiplications read %0 = load %a.addr and %2 = load %a.addr — different SSA values, so EarlyCSE cannot prove them equal; after mem2reg both read %a directly (Proposition 12.2.10 below).

4. Invariants and correctness¶

Proposition 12.2.9 (Pipeline text is LL(1))

The grammar of Definition 12.2.1 is LL(1); parsePassPipeline recognizes a pipeline of length $n$ in $O(n)$ time.

Proof

After a name, the next token decides the production: < starts params, ( starts a sub-pipeline, , or ) or the end closes the element — pairwise distinct, so the FIRST sets of the alternatives are disjoint, and name never derives the empty string. The params part is a balanced bracket word scanned with a counter. Each character is examined a constant number of times, which gives linear time. (Name resolution, Algorithm 12.2.3, then costs one lookup per element plus the callbacks tried.) ∎

Proposition 12.2.10 (Non-commutation)

early-cse and mem2reg do not commute: there is a program $P$ with $\texttt{mem2reg}(\texttt{early-cse}(P)) \ne \texttt{early-cse}(\texttt{mem2reg}(P))$.

Proof

The program of the real-world box above is a witness: the two results differ in their instruction counts (4 and 3 non-label lines in the function body). ∎

Theorem 12.2.11 (Soundness composes)

If every pass $s \in \Sigma$ is sound — for every program $P$, $s(P)$ refines $P$ (every behavior of $s(P)$ is a behavior of $P$; Definition 12.8.2) — then every pipeline $w \in \Sigma^{*}$, and every fixed-point pipeline $w^{\omega}$ that terminates, is sound.

Proof

Refinement $\sqsupseteq$ is reflexive and transitive: if the behaviors of $Q$ are included in those of $P$ and the behaviors of $R$ in those of $Q$, then those of $R$ are included in those of $P$. By induction on $\lvert w \rvert$: the empty word is the identity (reflexivity); $w s$ applied to $P$ is $s(w(P))$, which refines $w(P)$ by soundness of $s$, which refines $P$ by the induction hypothesis; transitivity concludes. A terminating $w^{\omega}(P) = w^{j}(P)$ is a finite pipeline. ∎

Theorem 12.2.12 (Termination of fixed-point pipelines)

If there is a function $\mu : \mathcal{P} \to \mathbb{N}$ such that every pass that reports a change strictly decreases it ($s(P) \ne P \Rightarrow \mu(s(P)) < \mu(P)$, and passes report a change only when they make one), then the fixed-point pipeline of $w$ stabilizes on every $P$ after at most $\mu(P) + 1$ rounds. Without such a measure it can run forever.

Proof

Every round except the last contains at least one change, and each change strictly decreases $\mu$; passes that change nothing leave $\mu$ unchanged. So after $r$ non-final rounds $\mu \le \mu(P) - r$, and since $\mu \ge 0$, at most $\mu(P)$ rounds contain a change; the next round changes nothing and the pipeline stabilizes. For the second claim, let $s$ rewrite every x * 2 into x + x and $t$ rewrite every x + x into x * 2, and let $P$ contain x * 2. In every round $s$ changes the program and $t$ changes it back, so every round reports a change and the pipeline never stabilizes, although the program after each round is $P$ again. This is why production pipelines insist on one canonical form per operation (InstCombine turns mul x, 2 into shl x, 1 and never the reverse, a change that lowers a suitable measure) and still bound their iterations (devirt<4>, instcombine<max-iterations=1>). ∎

Theorem 12.2.13 (Optimality of Algorithm 12.2.7)

Algorithm 12.2.7 returns a word $w \in \Sigma^{\le L}$ with $m(w(P)) = \min_{v \in \Sigma^{\le L}} m(v(P))$.

Proof

Invariant (induction on $d$): after round $d$, seen contains every program $v(P)$ with $\lvert v \rvert \le d$. Round $d+1$ applies every $s \in \Sigma$ to every program in frontier, which holds all programs first reached at depth $d$; a program reached at depth $d+1$ is $s(Q)$ for some $Q$ reachable at depth $\le d$, and if $Q$ was first reached earlier, $s(Q)$ was already generated then (passes are deterministic functions). So every program of depth $\le L$ is in seen, and best minimizes $m$ over all of them, each realized by the word stored with it. ∎

The course -O1 pipeline is not LLVM's -O1

pebblec -O1 runs only the steps chapters register (PEBBLE_COURSE_PIPELINE_STEP); with the reference solution of this chapter that is function(pebble-strength). -O1 for clang/opt is LLVM's 100-entry default<O1>. Only while no step is registered (a skeleton build before your E2) does pebblec -O1 fall back to default<O1> (pebble/lib/Driver/CoursePipeline.cpp). So the moment your E2 registers its step, pebblec -O1 output becomes less optimized — no mem2reg, no InstCombine, only your strength reduction — and later chapters add their passes one by one. That is expected, not a bug; use pebblec -O2 (LLVM's default<O2>) when you want LLVM's optimizer. Chapter 24 is where you design the full course pipeline.

5. Complexity¶

Let $n$ be the length of a pipeline text, $\lvert \Sigma \rvert$ the number of passes, $L$ the length bound, and $D_d$ the number of distinct programs first reached at depth $d$.

Technique	Time (worst)	Time (typical)	Space	Notes
Plugin loading and parsing (Alg. 12.2.3)	$O(n + e \cdot r)$ for $e$ elements and $r$ callbacks	microseconds	the pass objects	callbacks are tried in order until one accepts
Default pipeline (Alg. 12.2.5)	built once; running it is the cost of its passes	O2 has 119 top-level entries (§7)	—	size levels reuse O2 with attributes
Phase-order search (Alg. 12.2.7)	$\lvert \Sigma \rvert \cdot \sum_{d < L} D_d$ pass runs, $\le \sum_{d \le L} \lvert \Sigma \rvert^{d}$	far below the bound: many passes are no-ops on a given program, and many orders reach the same program (§3: 6 orders, 2 outcomes)	all distinct programs	Kulkarni et al. make exhaustive enumeration feasible for whole functions of a retargetable compiler by exactly this deduplication [KWTD06]

Justification. Proposition 12.2.9 gives the parse. For the search, each distinct program at depth $d < L$ is expanded once with $\lvert \Sigma \rvert$ passes; without deduplication, the number of words is $\sum_{d \le L} \lvert \Sigma \rvert^{d} = \Theta(\lvert \Sigma \rvert^{L})$. Pathological family: if every pass changes every program into a new one (for instance, each $s_i$ appends a distinct no-op instruction), no two words give the same program and $D_d = \lvert \Sigma \rvert^{d}$: the search degenerates to full enumeration, $\Theta(\lvert \Sigma \rvert^{L})$ pass runs. For LLVM's O2 with more than 60 distinct passes and $L$ in the hundreds, exhaustive search is out of the question — hence hand-designed templates.

Pass plugins and extension points¶

Static linking of "plugins" (LLVM_${name}_LINK_INTO_TOOLS, and the course's pebble_passes linked into pebblec): the same registration code without dlopen [LLVM-WNPM]. Trade-off: rebuild to change.
-passes-ep-* options of opt insert textual pipelines at extension points without a plugin (§7). Trade-off: they are parsed before plugins are loaded, so they only accept built-in passes.
clang's -fpass-plugin= loads a plugin into the compiler driver's pipeline. Trade-off: only EP callbacks are reachable; there is no textual pipeline in clang.

Optimization pipelines¶

LTO pipelines (buildThinLTOPreLinkDefaultPipeline, buildLTODefaultPipeline): split the same work between compile and link time [LLVM-PBP]. Trade-off: summaries and a second pipeline.
Size attributes instead of Os pipelines (LLVM 23): one pipeline, cost models that read optsize. Trade-off: opt -passes='default<Os>' is an error (§7).
Profile-guided pipelines (PGO PGOOptions): the same template with instrumentation or profile-use passes inserted (Lesson 12.3).

Phase ordering¶

Genetic search over pass sequences [CSS99]: finds better sequences than the fixed one for code size. Trade-off: thousands of compilations per program.
Exhaustive distinct-instance search (Algorithm 12.2.7) [KWTD06]. Trade-off: exact but only for small $\Sigma$ and small functions.
Fixed-point grouping and canonical forms (Theorem 12.2.12): repeat cheap passes, bound the repetitions. Trade-off: compile time, and some orders still lose.

7. In real compilers¶

Pass plugins and extension points¶

llvm/include/llvm/Plugins/PassPlugin.h — PassPluginLibraryInfo, LLVM_PLUGIN_API_VERSION [LLVM-PassPlugin]; llvm/include/llvm/Passes/PassBuilder.h — registerPipelineParsingCallback, registerPeepholeEPCallback, registerOptimizerLastEPCallback [LLVM-PB]; llvm/tools/opt/NewPMDriver.cpp — registerEPCallbacks is called before the plugins' registerPassBuilderCallbacks [LLVM-NewPMDriver]; the course registry pebble/lib/Passes/Registry.cpp (registerAll) and plugin entry pebble/lib/Passes/Plugin.cpp.

A plugin's registrations, and an extension point used four times

Reproduce (opt 23.1.2, the course plugin built by ./course test 12 --solution; $SOL is that build: SOL=$PWD/build/ci-solutions-linux from the repository root, ci-solutions-macos on macOS):

echo 'define void @f() { ret void }' > e.ll
opt -load-pass-plugin=$SOL/lib/PebblePasses.so -passes='print<pebble-passes>' \
    -disable-output e.ll 2>&1 | grep -E 'registry|ch12'
for o in O1 O2 O3; do
  echo "$o: $(opt -passes="default<$o>" -passes-ep-peephole='instnamer' -print-pipeline-passes \
               -disable-output e.ll | tr ',' '\n' | grep -c instnamer)"
done
opt -load-pass-plugin=$SOL/lib/PebblePasses.so -passes='default<O2>' \
    -passes-ep-peephole='pebble-strength' -print-pipeline-passes -disable-output e.ll 2>&1 | head -c 120; echo

Output:

Pebble pass registry:
  ch12 module pass pebble-bbcount
  ch12 function analysis pebble-stats
  ch12 function pass print<pebble-stats>
  ch12 function pass pebble-strength
O1: 4
O2: 4
O3: 4
Could not parse -passes-ep-peephole pipeline: unknown function pass 'pebble-strength' in pipeline 'pebble-strength'... I

What to notice: the plugin's four Chapter 12 registrations are parsing callbacks (Definition 12.2.2; other chapters' lines are filtered out). The Peephole extension point is invoked after four of the eight InstCombine runs of the O-pipelines (next box) — a callback there runs four times per function. opt's own -passes-ep-* flags are parsed in registerEPCallbacks before the plugin registers its names, so they cannot name plugin passes; a plugin that wants to join the O-pipelines must call registerPeepholeEPCallback itself.

Optimization pipelines¶

llvm/lib/Passes/PassBuilderPipelines.cpp — buildPerModuleDefaultPipeline, buildModuleSimplificationPipeline, buildFunctionSimplificationPipeline, buildO1FunctionSimplificationPipeline, buildModuleOptimizationPipeline, invokePeepholeEPCallbacks [LLVM-PBP]; llvm/lib/Passes/PassBuilder.cpp — the default<Os> rejection (LLVM 23.1.2). GCC: gcc/passes.def for the order and default_options_table in gcc/opts.cc for which -f flags each -O level enables (gcc-15) [GCC-Opts].

How big -O1, -O2 and -O3 are, and what -Os became

Reproduce (clang 23.1.2, opt 23.1.2):

echo 'define i32 @f(i32 %x) { ret i32 %x }' > t.ll
for o in O1 O2 O3; do
  opt -passes="default<$o>" -print-pipeline-passes -disable-output t.ll > pipe.$o.txt
  echo "$o: $(tr ',' '\n' < pipe.$o.txt | wc -l) elements"
done
norm() { tr ',' '\n' < "$1" | sed -E 's/<[^>]*>//g; s/^.*\(//; s/[()]//g' | sort -u; }
norm pipe.O1.txt > n1; norm pipe.O2.txt > n2; norm pipe.O3.txt > n3
echo "in O2, not O1: $(comm -13 n1 n2 | tr '\n' ' ')"
echo "in O3, not O2: $(comm -13 n2 n3 | tr '\n' ' ')"
opt -passes='default<Os>' -disable-output t.ll 2>&1
printf 'int f(int x){return x*8;}\n' > os.c
clang-23 -Os -S -emit-llvm -o - os.c | grep -o 'attributes #0 = { [a-z ]*optsize'

Output:

O1: 100 elements
O2: 119 elements
O3: 122 elements
in O2, not O1: aggressive-instcombine constraint-elimination correlated-propagation dfa-jump-threading dse extra-simple-loop-unswitch-passes gvn jump-table-to-switch jump-threading mldst-motion move-auto-init openmp-opt-cgscc slp-vectorizer speculative-execution 
in O3, not O2: argpromotion callsite-splitting chr 
LLVM ERROR: The optimization level "Os" is no longer supported. Use O2 in conjunction with the optsize attribute instead.
attributes #0 = { mustprogress nofree norecurse nosync nounwind optsize

What to notice: "elements" are comma-separated entries of the textual pipeline (nested ones included, so the count is a size measure, not a pass count). -O2 adds GVN, jump threading, DSE and the SLP vectorizer to -O1's set; -O3 adds only three passes (and more aggressive options such as unrolling thresholds, invisible here). -Os is -O2 plus the optsize attribute on every function (Definition 12.2.4).

Phase ordering¶

LLVM: the order is fixed in PassBuilderPipelines.cpp, with repetitions (eight InstCombine runs at -O2) and bounded fixed points (devirt<4>, instcombine<max-iterations=1>); GCC: gcc/passes.def repeats pass_ccp, pass_fre and pass_forwprop several times, with may_iterate parameters on FRE (gcc-15).

The same pass, many times, in LLVM's -O2

Reproduce (opt 23.1.2):

echo 'define i32 @f(i32 %x) { ret i32 %x }' > t.ll
opt -passes='default<O2>' -print-pipeline-passes -disable-output t.ll \
  | tr ',' '\n' | sed -E 's/<[^>]*>//g; s/^.*\(//; s/[()]//g' \
  | sort | uniq -c | sort -rn | head -6

Output:

      8 simplifycfg
      8 instcombine
      4 sroa
      4 licm
      3 require
      2 vector-combine

What to notice: a fixed template answers the phase-ordering problem by repeating the cheap, canonicalizing passes (SimplifyCFG, InstCombine) between the expensive ones, so that each expensive pass sees canonical input whichever pass ran before it — the practical form of Theorem 12.2.12.

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Pass plugins and extension points	Any pass, at named points of the default pipelines or by name in textual pipelines	`dlopen` + one callback per name; no LLVM rebuild	"unknown pass name" if unregistered; `print<pebble-passes>` lists registrations	Low: one registration line per pass (course registry)	Research passes, out-of-tree tools (Polly, Enzyme, the course plugin)
Optimization pipelines (-O1/-O2/-O3/-Os)	Hand-designed, balanced for code in general; not tuned per program	O1: 100 elements; O2: 119; O3: 122 (§7)	`-print-pipeline-passes` shows the exact pipeline, re-runnable with `-passes=`	High, but done once by compiler developers	Every `clang -O<n>` compilation
Phase ordering (search)	Optimal for the searched program, metric and length bound (Theorem 12.2.13)	Exponential in $L$ in the worst case; pruned by distinct outcomes	Per-program best sequence	Medium (a driver around the compiler)	Research, auto-tuning, embedded code size; informs fixed pipelines

Choose plugins and extension points when you add passes to LLVM without forking it — use EP callbacks to join the default pipelines, names to test in isolation. Choose the default pipelines when you compile code; change them only with measurements. Choose phase-order search when a hot function or a size budget justifies thousands of compilations, or to learn which orderings matter before fixing a pipeline.

9. Assessment¶

Quiz: pipe-ep-count (number), pipe-o2-not-o1 (set), pipe-os, plugin-ep-parse, phase-commute (number), phase-search-bound (number).
Drill: none — pipelines are read from -print-pipeline-passes, not computed by hand, and the phase-ordering search is exercised by the "Try it" below. The pass-manager drill pm-invalidation covers what a pipeline does to analyses.
Try it: re-run the §3 table with your own pebble-strength (build/<preset>/lib/PebblePasses.so) and add instcombine as a fourth pass: how many of the 24 orders reach the minimum?
Flashcards: tags plugins, pipelines, phase-ordering.
Exercise: E2 registers pebble-strength as the first course -O1 step (PEBBLE_COURSE_PIPELINE_STEP(1210, ...)).
Find where LLVM does it: in llvm/lib/Passes/PassBuilderPipelines.cpp, which function builds the function simplification pipeline used at -O1 only?

References¶

See the chapter references.

Technique	Time (worst)	Time (typical)	Space	Notes
Plugin loading and parsing (Alg. 12.2.3)	\(O(n + e \cdot r)\) for \(e\) elements and \(r\) callbacks	microseconds	the pass objects	callbacks are tried in order until one accepts
Default pipeline (Alg. 12.2.5)	built once; running it is the cost of its passes	O2 has 119 top-level entries (§7)	—	size levels reuse O2 with attributes
Phase-order search (Alg. 12.2.7)	\(\lvert \Sigma \rvert \cdot \sum_{d < L} D_d\) pass runs, \(\le \sum_{d \le L} \lvert \Sigma \rvert^{d}\)	far below the bound: many passes are no-ops on a given program, and many orders reach the same program (§3: 6 orders, 2 outcomes)	all distinct programs	Kulkarni et al. make exhaustive enumeration feasible for whole functions of a retargetable compiler by exactly this deduplication [KWTD06]

Lesson 12.2 — Pipelines, plugins and extension points, and the phase-ordering problem¶

1. Problem and motivation¶

Pass plugins and extension points¶

Optimization pipelines¶

Phase ordering¶

2. Definitions and algorithms¶

Pass plugins and extension points¶

Optimization pipelines¶

Phase ordering¶

3. Worked example¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

Pass plugins and extension points¶

Optimization pipelines¶

Phase ordering¶

7. In real compilers¶

Pass plugins and extension points¶

Optimization pipelines¶

Phase ordering¶

8. Comparison¶

9. Assessment¶

References¶