Lesson 12.1 — Pass-manager architectures: legacy and new LLVM, GCC, MLIR¶

Techniques: LLVM's legacy pass manager (declared AnalysisUsage, a static schedule); LLVM's new pass manager (lazy analysis caching, PreservedAnalyses, invalidation with dependencies, proxies and adaptors for module ↔ CGSCC ↔ function ↔ loop, instrumentation callbacks, optional and required passes); GCC's pass manager (passes.def, IR properties, TODO flags); MLIR's nested, operation-anchored pass manager (multithreading, dynamic pipelines) · Pebble implements: the analysis pebble-stats and its printer (E1), which the new pass manager caches and invalidates · Drill: pm-invalidation · Prerequisites: Ch 9 (LLVM IR), Ch 10 (the C++ API) · Time: 5–7 hours

A compiler optimizer is a sequence of passes, each a function from programs to programs, plus analyses that passes consult: dominator trees, loop nests, alias information. A pass manager decides when each analysis is computed, how long its result may be reused, in what order passes visit functions and loops, and how a user observes all this. The answer changes compile time by integer factors and, when it is wrong, silently miscompiles programs: a stale dominator tree used after a pass changed the CFG is a wrong-code bug that no test of the pass alone catches. This lesson compares four designs that production compilers use today and proves the property they all rely on: a cached result is only reused while it is still equal to what recomputing it would give.

1. Problem and motivation¶

The problem. Given a pipeline $p_1, \dots, p_k$ of passes and a set of analyses, run every pass on the IR units it is written for (modules, functions, loops, strongly connected components of the call graph) so that each pass sees the analysis results it asks for, those results are coherent with the current IR, and no analysis is computed more often than necessary.

LLVM legacy pass manager¶

LLVM's original pass manager, documented in "Writing an LLVM Pass" [LLVM-WLP], asks every pass to declare up front, in getAnalysisUsage, which analyses it requires and which it preserves. A scheduler inserts the required analyses before each pass, frees the ones a pass does not preserve, and pipelines function passes so that all of them run on one function before the next function is touched. The declaration is static: a pass must say whether it preserves the CFG before it knows whether it will change anything. It survives in LLVM 23 only in the code generator (llc), which is being ported ([LLVM-NPM]).

LLVM new pass manager¶

Chandler Carruth's redesign (developed in tree from 2014 on, the default for the optimization pipeline since LLVM 13, and the only optimizer pipeline in LLVM 23) inverts the protocol: analyses are computed lazily when a pass calls getResult, results are cached per IR unit, and after running, a pass returns a PreservedAnalyses value saying what it actually preserved on this run [LLVM-NPM, LLVM-WNPM]. Analyses may depend on other analyses and decide their own invalidation. IR units nest (module ⊃ CGSCC ⊃ function ⊃ loop) through adaptors and proxies. Every pass execution goes through instrumentation callbacks, which is how -print-after, -print-changed, -time-passes, -opt-bisect-limit and optnone are implemented. This is the pass manager the course's plugin PebblePasses uses.

GCC pass manager¶

GCC organizes its middle end as one static tree of passes written down in gcc/passes.def [GCC-PassesDef]. Instead of analyses with dependencies, GCC tracks IR properties ("the function is in SSA form", "there is a CFG", "loops are up to date") that each pass requires, provides and destroys, and TODO flags that ask the manager to clean up after a pass (update SSA, clean up the CFG, verify) ("Pass manager" in [GCC-Int]). Gates decide per function whether a pass runs.

MLIR pass manager¶

MLIR's IR is a nest of operations with regions, not a fixed module/function/loop hierarchy, so its pass manager anchors each pipeline on an operation type and nests pipelines along the IR structure [MLIR-PM]. Because operations marked IsolatedFromAbove cannot see values defined outside them, passes on sibling isolated operations can run on different threads; passes may also build and run pipelines dynamically.

2. Definitions and algorithms¶

Definition 12.1.1 (IR units, passes)

An IR unit is a module, a call-graph SCC, a function or a loop. Units nest: a module contains SCCs and functions, an SCC contains functions, a function contains loops. Let $\mathcal{P}$ be the set of programs. A pass on units of kind $U$ is a function $p : \mathcal{P} \times U \to \mathcal{P}$ that may change only the given unit (and, for a module pass, anything). A pipeline is a sequence of passes $\pi = p_1 \cdots p_k$; running it is the composition $p_k \circ \dots \circ p_1$ applied to every unit in the order the manager chooses.

Definition 12.1.2 (Analysis, result, cache)

An analysis $A$ on units of kind $U$ is a function $A : \mathcal{P} \times U \to R_A$ into a set of results. An analysis manager holds a partial map $\mathrm{cache} : \mathrm{Analyses} \times U \rightharpoonup \bigcup_A R_A$. The analysis $A$ requests $B$ if computing $A(P, u)$ calls getResult for $B(P, u)$ (or $B$ on an enclosing unit). $A$ depends on $B$, written $A \to B$, if $A$'s cached result stays correct only while $B$'s cached result does (typically because it keeps a reference to $B$'s result); such an $A$ also requests $B$. Both relations are acyclic. The converse fails: an analysis may request $B$ only to build its result and not depend on it afterwards (LoopInfo requests the dominator tree but, once built, is correct as long as the CFG is unchanged).

Definition 12.1.3 (PreservedAnalyses)

A preservation report is a triple $\mathrm{PA} = (K, S, X)$: a set $K$ of analyses that are preserved, a set $S$ of preserved analysis sets (such as CFGAnalyses or AllAnalysesOn<Function>), and a set $X$ of abandoned analyses. The special reports are $\mathrm{all} = (\{\ast\}, \emptyset, \emptyset)$, where $\ast$ preserves everything, and $\mathrm{none} = (\emptyset, \emptyset, \emptyset)$. The checker for $A$ answers $\mathrm{preserved}_{\mathrm{PA}}(A) \iff A \notin X \land (\ast \in K \lor A \in K)$ and $\mathrm{preservedSet}_{\mathrm{PA}}(A, s) \iff A \notin X \land (\ast \in K \lor s \in S)$. A pass run is truthful if every analysis it reports preserved (directly, by a set the analysis belongs to, or by $\ast$) would compute, on the new program, a result equal to its cached result on the old one.

Definition 12.1.4 (Invalidation predicate)

Every analysis $A$ supplies a predicate $\mathrm{inv}_A(\mathrm{PA}, \mathrm{Inv}) \in \{\mathsf{true}, \mathsf{false}\}$, where $\mathrm{Inv}(B)$ asks (and memoizes) whether a cached $B$ is invalidated. It is sound if $\neg \mathrm{inv}_A$ implies that $A$ is preserved by $\mathrm{PA}$ (directly or through a set $A$ belongs to) or is stateless (its result holds no information about the IR beyond its dependencies), and that $\mathrm{Inv}(B) = \mathsf{false}$ for every $B$ with $A \to B$. The default predicate is $\mathrm{inv}_A = \neg \mathrm{preserved}_{\mathrm{PA}}(A)$; an analysis with dependencies must override it.

The invalidation predicates of LLVM 23

Reading the invalidate methods of LLVM 23.1.2 [LLVM-Dominators, LLVM-SCEV, LLVM-BasicAA, LLVM-MSSA]: DominatorTree, PostDominatorTree and LoopInfo return $\neg(\mathrm{preserved}(A) \lor \mathrm{preservedSet}(A, \mathrm{AllAnalysesOn\langle Function\rangle}) \lor \mathrm{preservedSet}(A, \mathrm{CFGAnalyses}))$, so a pass that keeps the CFG keeps them without naming them. ScalarEvolution returns $\neg \mathrm{preserved}(\mathrm{SE}) \lor \mathrm{Inv}(\mathrm{AC}) \lor \mathrm{Inv}(\mathrm{DT}) \lor \mathrm{Inv}(\mathrm{LI})$. BasicAA is stateless: it returns $\mathrm{Inv}(\mathrm{AC}) \lor \mathrm{Inv}(\mathrm{DT}) \lor \mathrm{Inv}(\mathrm{TLI})$ and ignores its own preservation. AssumptionCache and TargetLibraryInfo return $\mathsf{false}$ always. LoopInfo does not consult the dominator tree, although computing it requests one: it requests DT but does not depend on it (Definition 12.1.2), so its predicate is sound without a dependency check.

LLVM legacy pass manager¶

Definition 12.1.5 (AnalysisUsage)

In the legacy manager each pass $p$ declares, before running, $\mathrm{Req}(p)$ (analyses that must be available), $\mathrm{Pres}(p)$ (analyses that stay valid after $p$ on every run), and the shorthands setPreservesCFG() (all CFG-only analyses) and setPreservesAll() (llvm/include/llvm/PassAnalysisSupport.h). An analysis is itself a pass whose result stays in the pass object.

Algorithm 12.1.6 (Legacy scheduling, PMTopLevelManager::schedulePass)

Input: passes $p_1, \dots, p_k$ with their AnalysisUsage.
Output: a flat schedule $s$ of passes (analyses included) and, after each element, the set of analyses to free.
Precondition: the Req relation is acyclic; every required analysis is registered.
Postcondition: before each $p_i$ in $s$, every $A \in \mathrm{Req}(p_i)$ occurs earlier in $s$ with no intervening pass that does not preserve it.
Invariant: avail is exactly the set of analyses whose most recent instance in $s$ has not been followed by a non-preserving pass.

function Schedule(p_1 .. p_k):
    s ← ⟨⟩; avail ← ∅
    for i ← 1 to k:
        Add(p_i)
    return s

function Add(p):
    for A in Req(p):                      # in declaration order
        if A ∉ avail:
            Add(A)                        # analyses are passes too; recursion is finite (acyclic)
    s ← s · ⟨p⟩
    if p is an analysis:
        avail ← avail ∪ {p}
    else:
        avail ← { A ∈ avail | A ∈ Pres(p) or (A is CFG-only and p preserves the CFG) }

At run time, FPPassManager::runOnFunction runs the whole function-level part of $s$ on one function before the next, and PMDataManager::removeNotPreservedAnalysis implements the last line.

LLVM new pass manager¶

Algorithm 12.1.7 (Lazy analysis cache, AnalysisManager::getResult and invalidate)

Input: requests getResult(A, u) from passes; a report $\mathrm{PA}$ after each pass on $u$.
Output: results $A(P, u)$.
Precondition: every $\mathrm{inv}_A$ is sound (Definition 12.1.4); passes are truthful (Definition 12.1.3).
Postcondition: every returned result equals $A(P, u)$ for the current program $P$ (Theorem 12.1.17).
Invariant: cache coherence (Definition 12.1.16): every cached $(A, u)$ equals $A(P, u)$.

function GetResult(A, u):
    if (A, u) ∈ dom(cache): return cache[A, u]
    r ← A.run(P, u)                        # may call GetResult(B, u) for A → B
    cache[A, u] ← r
    return r

function Invalidate(u, PA):                # called by the pass manager after each pass on u
    memo ← ∅                               # B ↦ true/false
    for (A, u) ∈ dom(cache), in any order:
        if Inv(A):
            delete cache[A, u]

function Inv(A):                           # the Invalidator handed to inv_A
    if A ∈ dom(memo): return memo[A]
    memo[A] ← inv_A(PA, Inv)               # may call Inv(B) for cached B with A → B
    return memo[A]

Algorithm 12.1.8 (Pass-manager run with instrumentation)

Input: a pipeline $p_1 \cdots p_k$ on one unit $u$; instrumentation callbacks $\mathcal{C}$.
Output: the transformed unit and the combined report $\mathrm{PA}_\pi$.
Precondition: as Algorithm 12.1.7.
Postcondition: each required pass ran; each optional pass ran iff every shouldRunOptionalPass callback agreed; the cache is coherent.
Invariant: after iteration $i$, $\mathrm{PA}_\pi$ is the intersection of the reports of $p_1..p_i$.

function Run(p_1 .. p_k, u):
    PA_π ← all
    for i ← 1 to k:
        if not p_i.isRequired() and not all(c.shouldRunOptionalPass(p_i, u) for c in C):
            for c in C: c.beforeSkippedPass(p_i, u)
            continue
        for c in C: c.beforeNonSkippedPass(p_i, u)
        PA ← p_i.run(u, AM)
        for c in C: c.afterPass(p_i, u, PA)
        AM.Invalidate(u, PA)               # Algorithm 12.1.7
        PA_π ← Intersect(PA_π, PA)         # keep only what every pass preserved
    return PA_π

optnone and -opt-bisect-limit are two such callbacks (OptNoneInstrumentation::shouldRun, OptPassGateInstrumentation::shouldRun in StandardInstrumentations.cpp [LLVM-SI]); a pass derived from RequiredPassInfoMixin is never skipped, one derived from OptionalPassInfoMixin may be.

Definition 12.1.9 (Adaptors and proxies)

An adaptor turns a pipeline on inner units into a pass on an outer unit: the ModuleToFunctionPassAdaptor runs a function pipeline on every function definition, the ModuleToPostOrderCGSCCPassAdaptor on every SCC of the call graph in post-order (callees first), CGSCCToFunctionPassAdaptor on each function of an SCC, and FunctionToLoopPassAdaptor on every loop, innermost first. A proxy is an analysis that gives inner passes access to another manager: InnerAnalysisManagerProxy<FAM, Module> is a module analysis whose result is the function analysis manager (its invalidation walks the inner caches); OuterAnalysisManagerProxy<MAM, Function> gives a function pass read-only access to cached module analyses.

Algorithm 12.1.10 (Module-to-function adaptor)

Input: module $M$, function pipeline $\pi$, module analysis manager MAM.
Output: the report for $M$.
Precondition: $\pi$ changes only the function it runs on.
Postcondition: $\pi$ ran on every definition, in module order; function caches are coherent; the module report preserves the function-level proxy but not module analyses unless all passes kept them.
Invariant: before processing $f$, every function before $f$ has been processed and its cache is coherent.

function ModuleToFunction(M, π):
    FAM ← MAM.GetResult(InnerProxy, M)
    PA_M ← all
    for f in functions(M), in order:
        if f is a declaration: continue
        PA_f ← Run(π, f)                   # Algorithm 12.1.8 on FAM
        PA_M ← Intersect(PA_M, PA_f)
    PA_M.preserveSet(AllAnalysesOn<Function>)   # FAM was kept up to date function by function
    PA_M.preserve(InnerProxy)
    return PA_M

Definition 12.1.11 (CGSCC walk)

Let $CG$ be the call graph (LLVM's LazyCallGraph). The CGSCC adaptor visits the SCCs of $CG$ in post-order (every SCC after the SCCs it calls), so that a function is simplified before it is inlined into its callers. A CGSCC pass may mutate the graph (inlining adds and removes edges, deleting a function removes a node); it records the changes in a CGSCCUpdateResult, and the adaptor re-runs the pipeline on SCCs that were split or merged. devirt<n> repeats the pipeline on an SCC up to $n$ times while indirect calls become direct.

GCC pass manager¶

Definition 12.1.12 (GCC pass data)

Each GCC pass is an opt_pass whose pass_data gives (gcc/tree-pass.h [GCC-TreePass]) its type (GIMPLE_PASS, RTL_PASS, SIMPLE_IPA_PASS, IPA_PASS), a name, and three property sets — properties_required, properties_provided, properties_destroyed — over bits such as PROP_cfg, PROP_ssa, PROP_loops, plus todo_flags_start and todo_flags_finish over bits such as TODO_update_ssa, TODO_cleanup_cfg, TODO_verify_il. gate(fun) decides whether the pass and its sub-passes run on fun; execute(fun) returns further TODO flags.

Algorithm 12.1.13 (GCC execute_one_pass, simplified from gcc/passes.cc)

Input: a pass $p$ and the current function with its property set $\Phi$.
Output: the updated function and $\Phi$; true iff the pass ran.
Precondition: properties_required$(p) \subseteq \Phi$ (checked when flag_checking).
Postcondition: $\Phi' = (\Phi \setminus \mathrm{destroyed}(p)) \cup \mathrm{provided}(p)$ and the finishing TODOs ran.
Invariant: $\Phi$ describes the IR: every property in $\Phi$ holds.

function ExecuteOnePass(p, fun):
    if not p.gate(fun): return false
    ExecuteTodo(p.todo_flags_start)
    assert p.properties_required ⊆ Φ        # verify_curr_properties
    todo ← p.execute(fun)
    Φ ← (Φ \ p.properties_destroyed) ∪ p.properties_provided
    ExecuteTodo(todo ∪ p.todo_flags_finish ∪ {TODO_verify_il})
    return true

function ExecutePassList(p):              # the passes.def tree
    while p ≠ null:
        if ExecuteOnePass(p, fun) and p.sub ≠ null:
            ExecutePassList(p.sub)
        p ← p.next

MLIR pass manager¶

Definition 12.1.14 (Operation-anchored pass managers)

An MLIR OpPassManager is anchored on an operation name (func.func, builtin.module) or is op-agnostic. A pass anchored on $T$ runs on operations of type $T$ and may modify only that operation and what it contains. Nesting follows the IR: builtin.module(func.func(cse,canonicalize)) runs cse then canonicalize on each function in the module. An anchor type must be IsolatedFromAbove: its regions use no value defined outside it.

Algorithm 12.1.15 (Nested adaptor, OpToOpPassAdaptor)

Input: an operation $o$ and nested pipelines $\pi_T$ keyed by anchor type.
Output: success or failure.
Precondition: every anchored operation is IsolatedFromAbove.
Postcondition: each $\pi_T$ ran to completion on each child of $o$ of type $T$.
Invariant: children being processed concurrently are disjoint subtrees of the IR.

function RunNested(o, pipelines):
    jobs ← [ (c, π_T) | c child op of o's regions (one level), π_T matches type(c) ]
    if multithreading enabled:
        parallelForEach(jobs, (c, π) ↦ RunPipeline(π, c))   # one analysis manager per child
    else:
        for (c, π) in jobs: RunPipeline(π, c)
    return all succeeded

function RunPipeline(π, c):
    for p in π:
        if p.runOnOperation(c) signalled failure: return failure
        invalidate analyses of c not marked preserved by p
    return success

A pass may also call runPipeline(dynamicPM, op) on an operation it owns: a dynamic pipeline, scheduled at run time, instrumented and analysis-managed like a static one.

3. Worked example¶

The running example of this chapter is a function with a loop, @count, and five passes P1–P5 that request analyses and report preservation as a drill instance would state them. The new pass manager starts with an empty cache.

step	pass	requests	returns	computed (Alg. 12.1.7)	invalidated	cache after
1	P1	{LI}	all	DT, LI (LI requests DT)	{}	{DT, LI}
2	P2	{PDT, SE}	all	PDT, TLI, AC, SE (SE requests TLI, AC, DT, LI; DT, LI cached)	{}	{AC, DT, LI, PDT, SE, TLI}
3	P3	{SE}	{CFG, AA}	{} (SE cached)	SE (not preserved by name; CFG does not cover it)	{AC, DT, LI, PDT, TLI}
4	P4	{LI, PDT}	{CFG, AA}	{}	{} (DT, PDT, LI kept by the CFG set)	{AC, DT, LI, PDT, TLI}
5	P5	{LI, PDT}	all	{}	{}	{AC, DT, LI, PDT, TLI}

Step 2: the dependencies are computed by the request, not the pass; DT and LI are reused.
Step 3: preserving AA preserves nothing here (it is not cached); SE is dropped because it is not named, although its dependencies survive.
Step 4: the CFG set is enough for DT, PDT and LI (Definition 12.1.4, the example).

The legacy schedule for the same pipeline, if every pass declared its most common behavior (P1, P2, P5 setPreservesAll; P3, P4 setPreservesCFG), is DT LI P1 PDT TLI AC SE P2 P3 P4 P5 with SE freed after P3 — the same work, but only because the declarations happened to match what the passes did. A pass that sometimes changes the CFG must declare that it never preserves it, and then every CFG analysis is recomputed after it on every function, even the functions it left untouched.

Caching and invalidation in LLVM's new pass manager

Reproduce (opt 23.1.2):

cat > inv.ll <<'EOF'
define i32 @f(i32 %x, i1 %c) {
entry:
  %m = mul i32 %x, 8
  br i1 %c, label %a, label %b
a:
  br label %b
b:
  %p = phi i32 [ %m, %entry ], [ 0, %a ]
  ret i32 %p
}
EOF
opt -passes='function(require<domtree>,instcombine,require<domtree>,simplifycfg,require<domtree>)' \
    -debug-pass-manager -disable-output inv.ll

Output (complete):

Running analysis: InnerAnalysisManagerProxy<AnalysisManager<Function>, Module> on [module]
Running pass: RequireAnalysisPass<DominatorTreeAnalysis, Function> on f (5 instructions)
Running analysis: DominatorTreeAnalysis on f
Running pass: InstCombinePass on f (5 instructions)
Running analysis: LastRunTrackingAnalysis on f
Running analysis: AssumptionAnalysis on f
Running analysis: TargetIRAnalysis on f
Running analysis: TargetLibraryAnalysis on f
Running analysis: OptimizationRemarkEmitterAnalysis on f
Running analysis: AAManager on f
Running analysis: BasicAA on f
Running analysis: ScopedNoAliasAA on f
Running analysis: TypeBasedAA on f
Running analysis: OuterAnalysisManagerProxy<AnalysisManager<Module>, Function> on f
Running pass: RequireAnalysisPass<DominatorTreeAnalysis, Function> on f (5 instructions)
Running pass: SimplifyCFGPass on f (5 instructions)
Invalidating analysis: DominatorTreeAnalysis on f
Invalidating analysis: LastRunTrackingAnalysis on f
Invalidating analysis: BasicAA on f
Invalidating analysis: AAManager on f
Running pass: RequireAnalysisPass<DominatorTreeAnalysis, Function> on f (3 instructions)
Running analysis: DominatorTreeAnalysis on f
Running pass: VerifierPass on [module]
Running analysis: VerifierAnalysis on [module]

What to notice: InstCombine rewrote mul %x, 8 into shl %x, 3 but reported the CFG set preserved, so the second require<domtree> reuses the cached tree (no "Running analysis" line). SimplifyCFG removed block a; the dominator tree is invalidated, and with it BasicAA (which depends on it) and AAManager (which depends on BasicAA) — the cascade of Definition 12.1.4 — while AssumptionAnalysis and TargetLibraryAnalysis are never invalidated. The dependencies were computed on demand by InstCombine's requests (Algorithm 12.1.7).

Try it

./course drill pm-invalidation --seed 4 --difficulty hard --solution reproduces the table above; other seeds give new pipelines.

4. Invariants and correctness¶

Definition 12.1.16 (Cache coherence)

A cache is coherent for program $P$ if for every $(A, u) \in \mathrm{dom}(\mathrm{cache})$, $\mathrm{cache}[A, u] = A(P, u)$, where equality is the analysis's own notion of equivalence (a stateless analysis's result is equal to any other of its results with equal dependencies).

Theorem 12.1.17 (Invalidation soundness)

Suppose every analysis's predicate $\mathrm{inv}_A$ is sound (Definition 12.1.4) and every pass run is truthful (Definition 12.1.3). Then the cache of Algorithm 12.1.7 is coherent after every step of Algorithm 12.1.8, and every GetResult returns $A(P, u)$ for the current $P$.

Proof

By induction on the number of GetResult and pass executions. Base: the cache is empty, hence coherent. GetResult: on a hit, coherence gives $\mathrm{cache}[A,u] = A(P,u)$; on a miss the result is computed from the current $P$ (and dependencies returned by GetResult, coherent by the induction hypothesis) and inserted, so coherence is kept. A pass run changes $P$ into $P'$ and reports $\mathrm{PA}$; Invalidate then removes every $A$ with $\mathrm{Inv}(A) = \mathsf{true}$. Let $A$ survive, so $\mathrm{inv}_A = \mathsf{false}$. By soundness, (i) $A$ is preserved by $\mathrm{PA}$ or stateless, and (ii) every dependency $B$ of $A$ survives. We show $\mathrm{cache}[A,u] = A(P',u)$ by induction along the acyclic dependency order. If $A$ is preserved, truthfulness gives $A(P', u) = A(P, u) = \mathrm{cache}[A,u]$. If $A$ is stateless, its result is determined by its dependencies, each of which survives and is, by the inner induction hypothesis, equal to its value on $P'$; so $A$'s result is equal to $A(P', u)$. Hence the cache is coherent for $P'$. Results of units the pass could not change are untouched and stay coherent because the pass is restricted to its unit (Definition 12.1.1). ∎

Lemma 12.1.18 (Invalidation is closed under dependencies)

With sound predicates, if $B$ is invalidated after a pass and $A \to^{+} B$ with $A$ cached, then $A$ is invalidated too.

Proof

By induction on the length of the dependency path $A \to A_1 \to \dots \to B$. If $A \to B$ directly, soundness requires $\mathrm{Inv}(B) = \mathsf{false}$ whenever $\mathrm{inv}_A = \mathsf{false}$; contrapositively $\mathrm{Inv}(B) = \mathsf{true}$ forces $\mathrm{inv}_A = \mathsf{true}$. For a longer path, $A_1$ is invalidated by the induction hypothesis and the one-step case applies to $A \to A_1$. ∎

Theorem 12.1.19 (Outer analyses are read-only for inner passes)

Let a function pass read a module analysis $M$ through OuterAnalysisManagerProxy. If the pass changes the function in a way that would change $M$'s result, coherence of the module cache is not restored by any function-level invalidation; it is restored only if $M$ registered an outer invalidation (registerOuterAnalysisInvalidation) or the enclosing adaptor does not report $M$ preserved.

Proof

Function-level Invalidate (Algorithm 12.1.7) iterates only over the function manager's cache, so $M$ is never inspected there. The only other invalidation of $M$ happens at module level after the adaptor returns $\mathrm{PA}_M$ (Algorithm 12.1.10): $M$ is dropped iff $\mathrm{inv}_M(\mathrm{PA}_M) = \mathsf{true}$. $\mathrm{PA}_M$ preserves the proxy and function analyses but not $M$ unless every inner report preserved $M$; so the module cache becomes coherent again exactly when the adaptor finishes, unless an inner pass claimed to preserve $M$. Between two inner passes, however, $M$ is stale; that is why the proxy returns only cached outer results (getCachedResult), never computes them, and why LLVM requires outer analyses used by inner passes to be immutable in practice, or to register invalidation dependencies. ∎

Proposition 12.1.20 (GCC property invariant)

If $\Phi$ describes the IR before ExecuteOnePass(p) and $p$'s declared property sets are correct (after execute, every property in provided holds, and every property not in destroyed that held before still holds, once the finishing TODOs ran), then $\Phi'$ describes the IR after it.

Proof

Let $\phi \in \Phi' = (\Phi \setminus \mathrm{destroyed}) \cup \mathrm{provided}$. If $\phi \in \mathrm{provided}$, it holds by correctness of provided. Otherwise $\phi \in \Phi$ and $\phi \notin \mathrm{destroyed}$: it held before (invariant) and is kept by correctness of destroyed, possibly after a TODO such as TODO_update_ssa repaired it — which is why TODOs run before the next pass. The gate only skips passes, which change nothing. ∎

Proposition 12.1.21 (MLIR parallel execution is deterministic)

If every pass anchored on $T$ reads and writes only the operation it runs on and its regions, and operations of type $T$ are IsolatedFromAbove, then running the nested pipelines on the children of $o$ in parallel gives the same IR as running them sequentially in any order.

Proof

Two distinct children $c_1, c_2$ are disjoint subtrees. By isolation, no operation inside $c_1$ uses a value defined in $c_2$ or above $c_1$, so no use-list shared by $c_1$ and $c_2$ can be changed by a pass on $c_1$; by the pass restriction nothing outside $c_1$ is written. Hence the write sets of the two jobs are disjoint and neither reads what the other writes: every interleaving is equivalent to a sequential order, and all sequential orders give the same result because the jobs commute. Shared uniqued state (types, attributes in the MLIRContext) is protected by locks and is insertion-only, so it does not change results. ∎

A lying PreservedAnalyses is a miscompile waiting to happen

If a pass changes code but returns PreservedAnalyses::all(), the stale result survives (the hypothesis of Theorem 12.1.17 fails). The course's test tests/ch12/lit/stats-cache.ll catches exactly this for pebble-strength: print<pebble-stats> would print the old opcode counts. The converse mistake — returning none() when nothing changed — is only slow.

5. Complexity¶

Let $k$ be the number of passes, $n$ the number of units (functions), $a$ the number of analyses, $c_A$ the cost of computing analysis $A$ on one unit, and $d$ the number of dependency edges.

Technique	Cost of analyses (worst)	Cost of analyses (typical)	Bookkeeping per pass	Space
Legacy PM	$k \cdot n \cdot \sum_A c_A$	analyses recomputed only after non-preserving passes, as declared	$O(a)$ set operations per scheduled pass, once, at schedule time	one result per analysis, freed when not preserved
New PM	$k \cdot n \cdot \sum_A c_A$	results recomputed only after a run that really changed them	$O(\lvert \mathrm{cache}_u \rvert + d)$ per pass per unit (memoized `Inv`)	cache per (analysis, unit) pair
GCC PM	$k \cdot n \cdot$ (cost of TODOs)	TODO work only where requested	$O(1)$ bit operations	one IR, properties as a bit mask
MLIR PM	as new PM	as new PM, divided by up to $\min(\#\text{threads}, \#\text{children})$ in wall time	analysis map per operation	one analysis manager per anchored operation

Justification. Invalidate visits each cached result once and, thanks to the memo, each dependency edge once: $O(\lvert \mathrm{cache}_u \rvert + d)$. The worst case of both LLVM managers is the pathological family $\pi_k = (\text{require}\langle A \rangle, q)^k$ where $q$ always returns none: every one of the $k$ requests misses, costing $k \cdot n \cdot c_A$ — and for $A = \mathrm{SE}$ also $k \cdot n \cdot (c_{\mathrm{DT}} + c_{\mathrm{LI}})$ through dependencies. Real scale: LLVM 23's default<O2> pipeline has 119 top-level elements (opt -passes='default<O2>' -print-pipeline-passes, Lesson 12.2); CGSCC iteration is bounded by devirt<4> (at most 4 repetitions per SCC) in that pipeline. For MLIR, Proposition 12.1.21 bounds the achievable parallelism by the number of isolated children, e.g. functions in a module.

LLVM legacy pass manager¶

LoopPass / CallGraphSCCPass managers nested inside the function and module managers (LPPassManager, CGPassManager): the same declaration scheme per unit kind [LLVM-WLP]. Trade-off: nesting is implicit in the pass type, so a pipeline's structure is hard to see.
Immutable passes (ImmutablePass, e.g. TargetLibraryInfoWrapperPass) are never freed. Trade-off: correct only for information that cannot change.

LLVM new pass manager¶

Eager invalidation (function<eager-inv> in the O-pipelines): drop all function analyses after the function pipeline, to save memory [LLVM-PBP]. Trade-off: recomputation if a later pipeline wants them.
abandon<A>() and analysis sets: finer statements than "preserved"; preservedWhenStateless lets stateless analyses survive unless explicitly abandoned.
Loop pipelines with LPMUpdater let loop passes add or delete loops while the adaptor walks them (LoopPassManager.h [LLVM-LPM]).

GCC pass manager¶

IPA passes in three stages (summary generation, propagation, transformation) so that LTO can stream summaries ("Inter-procedural optimization passes" in [GCC-Int]). Trade-off: every IPA pass must be written three times.
Pass instances and set_pass_param (NEXT_PASS (pass_ccp, true)): one pass runs several times with parameters. Trade-off: dump files are numbered per instance.

MLIR pass manager¶

Dynamic pipelines (Pass::runPipeline) for passes such as the inliner that simplify callees while they run ("Dynamic Pass Pipelines" in [MLIR-PM]). Trade-off: less static checking of the pipeline.
Op-agnostic pipelines (nestAny, any(...)): one pipeline for every isolated operation type. Trade-off: passes must use interfaces instead of concrete op types.
Crash reproducers (--mlir-pass-pipeline-crash-reproducer): the manager records the pipeline and the input that crashed — built-in test-case reduction support (Lesson 12.7).

7. In real compilers¶

LLVM legacy pass manager¶

llvm/lib/IR/LegacyPassManager.cpp — PMTopLevelManager::schedulePass, FPPassManager::runOnFunction, PMDataManager::removeNotPreservedAnalysis [LLVM-LegacyPM] (LLVM 23.1.2). opt 23.1.2 no longer accepts -enable-new-pm=0; llc still builds its code-generation pipeline with the legacy manager by default and has a partial -enable-new-pm port.

The legacy schedule of llc: analyses inserted and re-inserted

Reproduce (llc 23.1.2, opt 23.1.2):

printf 'define i32 @f(i32 %%x) {\n  %%r = sdiv i32 %%x, 4\n  ret i32 %%r\n}\n' > sd.ll
opt -enable-new-pm=0 -O2 sd.ll -o /dev/null 2>&1
llc -O2 -mtriple=x86_64-linux-gnu -debug-pass=Structure sd.ll -o /dev/null 2>&1 | sed -n '2,20p'

Output (the opt error, then the first lines of the structure):

opt: Unknown command line argument '-enable-new-pm=0'.  Try: 'opt --help'
opt: Did you mean '--enable-newgvn=0'?
Target Library Information
Runtime Library Function Analysis
Target Pass Configuration
Machine Module Information
Target Transform Information
Assumption Cache Tracker
Library Function Lowering Analysis
Type-Based Alias Analysis
Scoped NoAlias Alias Analysis
Create Garbage Collector Module Metadata
Profile summary info
Machine Branch Probability Analysis
Default Regalloc Eviction Advisor
Default Regalloc Priority Advisor
  ModulePass Manager
    FunctionPass Manager
      Dominator Tree Construction
      Basic Alias Analysis (stateless AA impl)
      Function Alias Analysis Results

What to notice: the schedule (Algorithm 12.1.6) is flat and precomputed; immutable passes come first; within the function pass manager, Dominator Tree Construction appears again and again (the full listing has 216 lines) because a declared non-preserving pass freed it — declared, not observed. The optimizer (opt) has no legacy mode left.

LLVM new pass manager¶

llvm/include/llvm/IR/PassManager.h — AnalysisManager, InnerAnalysisManagerProxy, OuterAnalysisManagerProxy, ModuleToFunctionPassAdaptor, RequiredPassInfoMixin, OptionalPassInfoMixin; llvm/include/llvm/IR/Analysis.h — PreservedAnalyses, CFGAnalyses [LLVM-PMH]; llvm/include/llvm/IR/PassManagerImpl.h — AnalysisManager::invalidate; llvm/include/llvm/Analysis/CGSCCPassManager.h — ModuleToPostOrderCGSCCPassAdaptor, DevirtSCCRepeatedPass [LLVM-CGSCC]; llvm/include/llvm/IR/PassInstrumentation.h — PassInstrumentationCallbacks [LLVM-PI]; llvm/lib/Passes/StandardInstrumentations.cpp — OptNoneInstrumentation::shouldRun [LLVM-SI] (LLVM 23.1.2).

An invalidation cascade, and an analysis that survives it

Reproduce (opt 23.1.2):

cat > cascade.ll <<'EOF'
define i32 @f(ptr %p, i32 %n) {
entry:
  br label %loop
loop:
  %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
  %v = load i32, ptr %p
  %i.next = add i32 %i, %v
  %c = icmp slt i32 %i.next, %n
  br i1 %c, label %loop, label %exit
exit:
  ret i32 %i
}
EOF
opt -passes='function(require<scalar-evolution>,require<memoryssa>,invalidate<domtree>,require<loops>)' \
    -debug-pass-manager -disable-output cascade.ll 2>&1 | grep -v VerifierPass

Output (complete, minus the verifier line):

Running analysis: InnerAnalysisManagerProxy<AnalysisManager<Function>, Module> on [module]
Running pass: RequireAnalysisPass<ScalarEvolutionAnalysis, Function> on f (7 instructions)
Running analysis: ScalarEvolutionAnalysis on f
Running analysis: TargetLibraryAnalysis on f
Running analysis: AssumptionAnalysis on f
Running analysis: TargetIRAnalysis on f
Running analysis: DominatorTreeAnalysis on f
Running analysis: LoopAnalysis on f
Running pass: RequireAnalysisPass<MemorySSAAnalysis, Function> on f (7 instructions)
Running analysis: MemorySSAAnalysis on f
Running analysis: AAManager on f
Running analysis: BasicAA on f
Running analysis: ScopedNoAliasAA on f
Running analysis: TypeBasedAA on f
Running analysis: OuterAnalysisManagerProxy<AnalysisManager<Module>, Function> on f
Running pass: InvalidateAnalysisPass<DominatorTreeAnalysis> on f (7 instructions)
Invalidating analysis: DominatorTreeAnalysis on f
Invalidating analysis: ScalarEvolutionAnalysis on f
Invalidating analysis: BasicAA on f
Invalidating analysis: AAManager on f
Invalidating analysis: MemorySSAAnalysis on f
Running pass: RequireAnalysisPass<LoopAnalysis, Function> on f (7 instructions)
Running analysis: VerifierAnalysis on [module]

What to notice: invalidate<domtree> returns "everything but DT preserved"; Lemma 12.1.18 then drops SE, BasicAA, AAManager and MemorySSA, which depend on DT. LoopAnalysis was computed from the dominator tree but survives — it requests DT without depending on it, and its invalidate checks only the CFG (Definition 12.1.2 and the example after Definition 12.1.4) — and require<loops> finds it cached. The drill pm-invalidation uses exactly these rules.

Required and optional passes: optnone and the pass gate

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):

cat > on.ll <<'EOF'
define i32 @opt_me(i32 %x) {
  %r = mul i32 %x, 8
  ret i32 %r
}
define i32 @leave_me(i32 %x) #0 {
  %r = mul i32 %x, 8
  ret i32 %r
}
attributes #0 = { noinline optnone }
EOF
opt -load-pass-plugin=$SOL/lib/PebblePasses.so \
    -passes='function(pebble-strength,print<pebble-stats>)' -debug-pass-manager -disable-output on.ll 2>&1 \
  | grep -E 'Skipping|Running pass|opcodes'

Output:

Running pass: (anonymous namespace)::StrengthPass on opt_me (2 instructions)
Running pass: (anonymous namespace)::StatsPrinter on opt_me (2 instructions)
  opcodes: ret=1 shl=1
Skipping pass (anonymous namespace)::StrengthPass on leave_me due to optnone attribute
Skipping pass: (anonymous namespace)::StrengthPass on leave_me
Running pass: (anonymous namespace)::StatsPrinter on leave_me (2 instructions)
  opcodes: mul=1 ret=1
Running pass: VerifierPass on [module]

What to notice: OptNoneInstrumentation answered shouldRunOptionalPass with false for the optional pebble-strength (an OptionalPassInfoMixin), which Algorithm 12.1.8 turns into a beforeSkippedPass; the printer is a RequiredPassInfoMixin and runs on both functions. The class names are the reference solution's: plugin passes are printed by C++ name, not by pipeline name.

The CGSCC adaptor visits callees first

Reproduce (opt 23.1.2):

cat > cg.ll <<'EOF'
define internal i32 @leaf(i32 %x) {
  %r = mul i32 %x, 4
  ret i32 %r
}
define i32 @root(i32 %x) {
  %a = call i32 @leaf(i32 %x)
  %b = add i32 %a, 1
  ret i32 %b
}
EOF
opt -passes='cgscc(inline,function(instcombine))' -debug-pass-manager -S cg.ll 2>&1 \
  | grep -E '^Running pass|^define|^  %|ret i32'

Output:

Running pass: InlinerPass on (leaf) (1 node)
Running pass: InstCombinePass on leaf (2 instructions)
Running pass: InlinerPass on (root) (1 node)
Running pass: InstCombinePass on root (3 instructions)
Running pass: VerifierPass on [module]
Running pass: PrintModulePass on [module]
define i32 @root(i32 %x) {
  %r.i = shl i32 %x, 2
  %b = or disjoint i32 %r.i, 1
  ret i32 %b

What to notice: Definition 12.1.11's post-order: the SCC (leaf) is simplified (mul → shl) before the inliner visits (root) and copies the simplified body (%r.i); the dead internal @leaf is then deleted. (The unfiltered output also shows eight "Invalidating analysis" lines on root after inlining changed its CFG-free body: the inliner reports nothing preserved.)

GCC pass manager¶

gcc/passes.def — the pass tree (INSERT_PASSES_AFTER (all_passes), PUSH_INSERT_PASSES_WITHIN (pass_all_optimizations), NEXT_PASS (pass_ccp, true)) [GCC-PassesDef]; gcc/tree-pass.h — pass_data, opt_pass, the PROP_* and TODO_* bits [GCC-TreePass]; gcc/passes.cc — execute_one_pass, execute_todo [GCC-Passes]; gcc/tree-ssa-ccp.cc — pass_data_ccp requires PROP_cfg | PROP_ssa and finishes with TODO_update_address_taken (gcc-15 branch).

GCC's pass tree with its gates evaluated

Reproduce (gcc 14.2.0 on x86-64 Linux — Ubuntu 24.04: sudo apt install gcc-14; macOS: brew install gcc@14, whose driver is also gcc-14; other GCC versions and targets print other pass lists and line counts):

printf 'int check(int x) { return x + 1 > x; }\n' > ub.c
gcc-14 -O2 -fdump-passes -c ub.c -o /dev/null 2>&1 | sed -n '17,40p'
gcc-14 -O2 -fdump-passes -c ub.c -o /dev/null 2>&1 | wc -l

Output:

   ipa-visibility                                      :  ON
   ipa-strubm                                          :  OFF
   ipa-build_ssa_passes                                :  ON
      tree-fixup_cfg1                                  :  ON
      tree-ssa                                         :  ON
      tree-walloca1                                    :  ON
      tree-warn-printf                                 :  OFF
      *nonnullcmp                                      :  OFF
      tree-early_uninit                                :  OFF
      tree-waccess1                                    :  ON
      tree-ubsan                                       :  OFF
      tree-nothrow                                     :  ON
      *rebuild_cgraph_edges                            :  ON
   ipa-opt_local_passes                                :  ON
      tree-fixup_cfg2                                  :  ON
      *rebuild_cgraph_edges                            :  ON
      tree-local-fnsummary1                            :  ON
      tree-einline                                     :  ON
      *infinite-recursion                              :  OFF
      tree-early_optimizations                         :  ON
         *remove_cgraph_callee_edges                   :  ON
         tree-early_objsz                              :  ON
         tree-ccp1                                     :  ON
         tree-forwprop1                                :  ON
378

What to notice: the nesting is the sub/next tree of Algorithm 12.1.13 (tree-early_optimizations has sub-passes); ON/OFF is each pass's gate at -O2; numbered names (ccp1, fixup_cfg2) are instances of one pass class (Section 6). A star marks passes without dump files. 378 lines for one function: GCC runs the same static tree for every function.

MLIR pass manager¶

mlir/lib/Pass/Pass.cpp — OpToOpPassAdaptor::runOnOperation, OpToOpPassAdaptor::runPipeline [MLIR-Pass]; mlir/include/mlir/Pass/Pass.h — Pass::runPipeline (inline; the dynamic-pipeline entry point); the documentation [MLIR-PM] (LLVM 23.1.2).

MLIR runs a nested pipeline one function at a time

Reproduce (mlir-opt 23.1.2 — macOS: Homebrew's llvm ships it in $(brew --prefix llvm)/bin; Linux: see the chapter's tools outside the course toolchain; this output came from the conda-forge mlir 23.1.2 package):

cat > m.mlir <<'EOF'
func.func @f(%x: i32) -> i32 {
  %c8 = arith.constant 8 : i32
  %a = arith.muli %x, %c8 : i32
  %b = arith.muli %x, %c8 : i32
  %s = arith.addi %a, %b : i32
  return %s : i32
}
func.func @g(%x: i32) -> i32 {
  %c0 = arith.constant 0 : i32
  %a = arith.addi %x, %c0 : i32
  return %a : i32
}
EOF
mlir-opt m.mlir -pass-pipeline='builtin.module(func.func(cse,canonicalize))' \
  -mlir-print-ir-after-all -mlir-disable-threading -o /dev/null 2>&1 | grep -E '^// -----|^func.func'

Output:

// -----// IR Dump After CSEPass: cse //----- //
func.func @f(%arg0: i32) -> i32 {
// -----// IR Dump After CanonicalizerPass: canonicalize{cse-between-iterations=false    max-iterations=10 max-num-rewrites=-1 region-simplify=normal test-convergence=false top-down=true} //----- //
func.func @f(%arg0: i32) -> i32 {
// -----// IR Dump After CSEPass: cse //----- //
func.func @g(%arg0: i32) -> i32 {
// -----// IR Dump After CanonicalizerPass: canonicalize{cse-between-iterations=false    max-iterations=10 max-num-rewrites=-1 region-simplify=normal test-convergence=false top-down=true} //----- //
func.func @g(%arg0: i32) -> i32 {

What to notice: the whole func.func pipeline runs on @f, then on @g (Algorithm 12.1.15), and each dump shows only the anchored function — passes cannot see outside it. Without -mlir-disable-threading the two functions are processed on different threads; Proposition 12.1.21 is why the result is the same. (Between the two dumps of @f, cse merged the two mulis.)

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
LLVM legacy PM	Static, declared preservation: must assume the worst case per pass	Recomputes after every declared non-preserving pass, even when nothing changed	`-debug-pass=Structure` shows the whole schedule up front	Low per pass (declare usage); complex manager	LLVM codegen (`llc`) in LLVM 23; LLVM optimizer before LLVM 13
LLVM new PM	Dynamic, per-run `PreservedAnalyses`; dependency-aware invalidation (Theorem 12.1.17)	Lazy; recomputes only what a run invalidated; $O(\lvert \mathrm{cache} \rvert + d)$ bookkeeping per pass	`-debug-pass-manager`, `-print-changed`, pass instrumentation	Moderate per pass (truthful reports, `invalidate` for dependent analyses)	LLVM 23 optimizer, `opt`, `clang`, the course plugin
GCC PM	Coarse: IR properties and TODO flags instead of per-analysis caching	Static tree; repairs (update SSA, cleanup CFG) on request	`-fdump-passes`, per-pass dumps `-fdump-tree-<pass>`	Low per pass (fill in `pass_data`)	GCC's GIMPLE, RTL and IPA pipelines
MLIR PM	Per-operation analysis managers; nesting follows the IR; op-agnostic pipelines	Parallel over isolated operations (Proposition 12.1.21)	`-mlir-print-ir-after-all`, `-mlir-timing`, crash reproducers	Moderate: declare anchors, keep passes local	MLIR-based compilers (Flang, CIRCT, IREE, Triton)

Choose the legacy PM when you maintain LLVM code-generation passes today; nothing new should target it. Choose the new PM when you write any LLVM optimization or analysis: it is the only optimizer pipeline, and its per-run preservation makes cheap passes cheap. Choose GCC's model when the compiler has few analyses and many IR-form invariants (SSA or not, CFG or not): properties are simple and checkable. Choose MLIR's model when the IR is a nest of isolated regions and compile time matters on many cores: anchoring gives parallelism for free.

9. Assessment¶

Quiz (./course quiz 12): pm-cache-trace (mapping), pm-cascade (set), pm-legacy-vs-new, pm-optional-required, pm-legacy-declare, pm-gcc-properties, pm-mlir-anchor, pm-cgscc-order (sequence), llvm-where-optnone (find it in LLVM), llvm-where-invalidate-scev.
Drill: ./course drill pm-invalidation (all difficulties; hard includes MemorySSA and PDT).
Flashcards: tags legacy-pm, new-pm, gcc-pm, mlir-pm.
Exercise: E1 (pebble-stats, cached and invalidated by the new pass manager; exercises.md).
Find where LLVM does it: open llvm/lib/Analysis/ScalarEvolution.cpp at llvmorg-23.1.2 and find ScalarEvolution::invalidate: which three analyses does it consult? Then open llvm/lib/Passes/StandardInstrumentations.cpp: which callback does OptNoneInstrumentation register?

References¶

See the chapter references.

Technique	Cost of analyses (worst)	Cost of analyses (typical)	Bookkeeping per pass	Space
Legacy PM	\(k \cdot n \cdot \sum_A c_A\)	analyses recomputed only after non-preserving passes, as declared	\(O(a)\) set operations per scheduled pass, once, at schedule time	one result per analysis, freed when not preserved
New PM	\(k \cdot n \cdot \sum_A c_A\)	results recomputed only after a run that really changed them	\(O(\lvert \mathrm{cache}_u \rvert + d)\) per pass per unit (memoized `Inv`)	cache per (analysis, unit) pair
GCC PM	\(k \cdot n \cdot\) (cost of TODOs)	TODO work only where requested	\(O(1)\) bit operations	one IR, properties as a bit mask
MLIR PM	as new PM	as new PM, divided by up to \(\min(\#\text{threads}, \#\text{children})\) in wall time	analysis map per operation	one analysis manager per anchored operation

Lesson 12.1 — Pass-manager architectures: legacy and new LLVM, GCC, MLIR¶

1. Problem and motivation¶

LLVM legacy pass manager¶

LLVM new pass manager¶

GCC pass manager¶

MLIR pass manager¶

2. Definitions and algorithms¶

LLVM legacy pass manager¶

LLVM new pass manager¶

GCC pass manager¶

MLIR pass manager¶

3. Worked example¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

LLVM legacy pass manager¶

LLVM new pass manager¶

GCC pass manager¶

MLIR pass manager¶

7. In real compilers¶

LLVM legacy pass manager¶

LLVM new pass manager¶

GCC pass manager¶

MLIR pass manager¶

8. Comparison¶

9. Assessment¶

References¶