Skip to content

Lesson 0.1 — Pipeline shapes: multi-pass, single-pass, query-based, multi-level

Techniques: multi-pass pipelines, single-pass compilation, query-based incremental compilation, multi-level IR (MLIR) · Pebble uses: a multi-pass pipeline (front end → PIR → LLVM IR → LLVM passes → machine code) · Lab: the one-pass bytecode compiler of labs/ch00-exec · Prerequisites: none · Time: 4–6 hours

A compiler is one function from source text to machine code, but nobody writes it as one function. Run clang on a five-line C file and ask it how it plans the work:

clang-23 -ccc-print-phases sum.c

            +- 0: input, "sum.c", c
         +- 1: preprocessor, {0}, cpp-output
      +- 2: compiler, {1}, ir
   +- 3: backend, {2}, assembler
+- 4: assembler, {3}, object
5: linker, {4}, image

Six phases, each consuming the previous one's output. That is one shape a compiler can take. This lesson compares four shapes: the multi-pass pipeline above, the single-pass compiler that emits code while it reads tokens, the query-based compiler that computes only what is asked for and remembers it, and the multi-level IR compiler that lowers a program through a stack of dialects. First we pin down what any of them must guarantee.

1. Problem and motivation

The problem. Given a translation from a source language \(L_S\) to a target language \(L_T\) that is correct (Definition 0.1.4), organize its computation. The organization decides memory use, compile time, how easy it is to add a language or a target, how well the compiler serves an IDE that recompiles on every keystroke, and which optimizations are possible at all.

Multi-pass pipelines

The first optimizing compiler, FORTRAN I (1957), was split into six sections that ran one after another, because an IBM 704 could not hold the whole compiler in memory [BBB+57]. Memory stopped being the reason long ago; the split stayed because it is the unit of modularity: each pass reads one well-defined representation and writes another, so passes can be tested, reordered, reused and replaced independently. Clang, GCC, rustc, swiftc and pebblec are all multi-pass: pebblec runs Lex → Parse → Sema → LowerToPIR → PIR→LLVM → LLVM's -O pipeline → the LLVM back end (see the tour). Correctness of such a pipeline reduces to correctness of each pass (Theorem 0.1.6).

Single-pass compilation

A single-pass compiler reads the source once, front to back, and emits target code as it goes, keeping only a symbol table and a small amount of state. Wirth designed Pascal so that it could be compiled this way ("declare before use") [Wir71]; Turbo Pascal (1983) and the Tiny C Compiler (TCC) made one-pass compilation famous for speed. TCC's own documentation says its parser "does only one pass", with two small exceptions [TCC-Doc]. The price is optimization: code for a statement is emitted before the compiler has seen the rest of the function.

Query-based incremental compilation

An IDE asks a compiler thousands of small questions per minute ("what is the type of x?", "where is f defined?") about a program that changes one keystroke at a time. A pipeline that recompiles everything is too slow. A query-based compiler turns every intermediate result into a memoized function of its inputs, records which results each computation read, and after an edit recomputes only what may have changed. rustc's query system [RUSTC-Query], rust-analyzer's salsa library [Salsa], Swift's request evaluator [SWIFT-Req] and Roslyn's immutable, incrementally rebuilt syntax trees and compilations [ROSLYN-Overview] are production instances; the idea descends from self-adjusting computation and demand-driven incremental computation such as Adapton [HPHF14], and Mokhov, Mitchell and Peyton Jones formalize the same machinery for build systems [MMP18].

Multi-level IR (MLIR)

A compiler for tensors, hardware description or quantum circuits needs abstractions (loops over tiles, dataflow graphs, gates) that LLVM IR cannot express without losing information. MLIR [LAB+21] makes the IR itself extensible: a program is a mix of operations from many dialects, and compilation is progressive lowering — rewriting high-level operations into lower-level ones, dialect by dialect, until only the llvm dialect remains and can be translated to LLVM IR. Flang, IREE, CIRCT and many ML compilers are built this way.

2. Definitions and algorithms

The four shapes compute the same thing. This section first defines what (Definitions 0.1.1–0.1.5), then how each shape does it.

Definition 0.1.1 (Language, behaviors)

A language \(L\) is a set of programs together with a behavior function \(\mathrm{Beh} : L \to \mathcal{P}(\mathcal{O} \cup \{\mathrm{ub}\})\), where \(\mathcal{O}\) is a fixed set of observable behaviors (for example: terminates with exit status \(k\) after printing the string \(w\); runs forever after printing \(w\); traps after printing \(w\)) and \(\mathrm{ub}\) is a distinguished element meaning "has undefined behavior". A program is deterministic if \(\lvert \mathrm{Beh}(p) \rvert = 1\).

Behaviors of the running example

The C function sum of this lesson, called from a main that prints sum(10), has \(\mathrm{Beh} = \{\text{prints } \texttt{45}\text{, exits with } 0\}\). The C program int main(void) { int x; return x; } reads an uninitialized variable, so its behavior set contains \(\mathrm{ub}\).

Definition 0.1.2 (Refinement)

Let \(p \in L_S\) and \(q \in L_T\) be programs whose behaviors are observed in the same set \(\mathcal{O}\). Then \(q\) refines \(p\), written \(q \preceq p\), if

\[ \mathrm{ub} \in \mathrm{Beh}(p) \quad\lor\quad \mathrm{Beh}(q) \subseteq \mathrm{Beh}(p). \]

In words: either the source program is allowed to do anything, or every behavior of the target is a behavior of the source.

Lemma 0.1.3 (Refinement is a preorder)

\(\preceq\) is reflexive and transitive: \(p \preceq p\), and \(r \preceq q \land q \preceq p \Rightarrow r \preceq p\).

Proof

Reflexivity: \(\mathrm{Beh}(p) \subseteq \mathrm{Beh}(p)\). Transitivity: assume \(r \preceq q\) and \(q \preceq p\). Case 1: \(\mathrm{ub} \in \mathrm{Beh}(p)\); then \(r \preceq p\) by the first disjunct. Case 2: \(\mathrm{ub} \notin \mathrm{Beh}(p)\); then \(q \preceq p\) gives \(\mathrm{Beh}(q) \subseteq \mathrm{Beh}(p)\), so \(\mathrm{ub} \notin \mathrm{Beh}(q)\), so \(r \preceq q\) gives \(\mathrm{Beh}(r) \subseteq \mathrm{Beh}(q) \subseteq \mathrm{Beh}(p)\). The two cases are exhaustive.

Definition 0.1.4 (Compiler, correctness)

A compiler from \(L_S\) to \(L_T\) is a partial function \(C : L_S \rightharpoonup L_T\) (undefined on programs it rejects). \(C\) is correct if \(C(p) \preceq p\) for every \(p\) in its domain. Refinement, not equality, is the right notion: a correct compiler may resolve nondeterminism (pick one evaluation order that C leaves unspecified) and may do anything on programs with undefined behavior.

Definition 0.1.5 (Pass, pipeline)

A pass is a compiler \(P_i : L_{i-1} \rightharpoonup L_i\) between two representations (source text, tokens, syntax trees, PIR, LLVM IR, machine code, …). A pipeline of passes \(P_1, \dots, P_k\) is the composition \(C = P_k \circ \dots \circ P_1 : L_0 \rightharpoonup L_k\), defined on \(p\) exactly when every intermediate result is defined. A pass with \(L_{i-1} = L_i\) is an IR-to-IR transformation (an optimization).

Theorem 0.1.6 (Correct passes compose)

If every pass \(P_1, \dots, P_k\) is correct, the pipeline \(P_k \circ \dots \circ P_1\) is correct.

Proof

By induction on \(k\). For \(k = 1\) there is nothing to prove. For \(k > 1\) let \(p \in \mathrm{dom}(P_k \circ \dots \circ P_1)\) and \(p' = (P_{k-1} \circ \dots \circ P_1)(p)\). By the induction hypothesis \(p' \preceq p\); by correctness of \(P_k\), \(P_k(p') \preceq p'\). Lemma 0.1.3 (transitivity) gives \(P_k(p') \preceq p\).

Theorem 0.1.6 on the clang pipeline

The phases printed at the top of the lesson are passes between \(L_0\) (C source), \(L_1\) (preprocessed C), \(L_2\) (LLVM IR), \(L_3\) (x86-64 assembly), \(L_4\) (object code) and \(L_5\) (executable). Inside phase 2, opt's default<O2> pipeline is itself a composition of about 120 IR-to-IR passes. If each of the roughly 125 translations refines its input, the executable refines the C program. A miscompilation is therefore always one pass whose output does not refine its input — which is exactly how LLVM developers bisect miscompiles (opt -opt-bisect-limit=N, Ch 12).

Multi-pass pipelines

A multi-pass compiler runs the passes of Definition 0.1.5 one after another over the whole program. Real pass managers add one refinement: analyses (dominator trees, loop nests, alias information) are computed on demand, cached, and invalidated by passes that change what they describe.

Definition 0.1.7 (Analysis, preservation)

An analysis is a function \(A\) from IR to facts (for example the dominator tree of a function). A transformation pass \(P\) preserves \(A\) if \(A(P(m)) = A(m)\) for every module \(m\) on which \(P\) is defined. A pass reports a set \(\mathrm{Pres}(P)\) of analyses it claims to preserve; the report is truthful if \(P\) preserves every analysis in it.

Algorithm 0.1.8 (Pass manager with cached analyses)

  • Input: a module \(m_0\); a sequence of passes \(P_1, \dots, P_k\), each of which may request analyses of its input and reports \(\mathrm{Pres}(P_i)\).
  • Output: \(m_k = P_k(\dots P_1(m_0))\), or the first rejection.
  • Precondition: every report \(\mathrm{Pres}(P_i)\) is truthful (Definition 0.1.7); analyses are deterministic functions of the module.
  • Postcondition: \(m_k\) is exactly the pipeline's result, and every analysis result a pass received equals the analysis of the module that pass was given.
  • Invariant (cache validity, Lemma 0.1.15): before each pass runs, every entry \((A, r)\) in the cache satisfies \(r = A(m)\) for the current module \(m\).
function RunPipeline(m, passes):
    cache ← empty map from analysis to result
    for P in passes:
        m' ← P.run(m, request = GetAnalysis)     # P may call GetAnalysis(A) many times
        if m' is "reject": return reject
        for A in keys(cache):
            if A ∉ P.preserved(): remove A from cache
        m ← m'
    return m

function GetAnalysis(A):                         # uses the enclosing m and cache
    if A ∉ keys(cache): cache[A] ← A.compute(m)
    return cache[A]

LLVM's new pass manager (llvm/include/llvm/IR/PassManager.h, PassManager<IRUnitT>, AnalysisManager) implements exactly this, at four granularities (module, CGSCC, function, loop) with proxies between them; passes return a PreservedAnalyses set (Ch 12).

The clang driver plans a multi-pass pipeline

Reproduce (clang 23.1.2 on x86-64 Linux; the -### paths depend on your install):

cat > sum.c <<'EOF'
int sum(int n) {
  int s = 0;
  for (int i = 0; i < n; i++)
    s += i;
  return s;
}
EOF
clang-23 -ccc-print-phases -c sum.c
clang-23 -### -c sum.c

Output (the -### job is abridged: … replaces include paths and the working directory):

         +- 0: input, "sum.c", c
      +- 1: preprocessor, {0}, cpp-output
   +- 2: compiler, {1}, ir
+- 3: backend, {2}, assembler
4: assembler, {3}, object
clang version 23.1.2 (https://github.com/conda-forge/clangdev-feedstock 790b452829aae3c1261820656dab09eb6850b87f)
Target: x86_64-conda-linux-gnu
Thread model: posix
InstalledDir: /opt/llvm-23/bin
 (in-process)
 "/opt/llvm-23/bin/clang-23" "-cc1" "-triple" "x86_64-conda-linux-gnu" "-emit-obj" "-disable-free" "-clear-ast-before-backend" "-disable-llvm-verifier" "-discard-value-names" "-main-file-name" "sum.c" "-mrelocation-model" "pic" "-pic-level" "2" "-pic-is-pie" "-mframe-pointer=all" … "-o" "sum.o" "-x" "c" "sum.c"

What to notice: with -c the linker phase disappears from the plan (compare the six-phase plan at the top of the lesson). The driver (clang) only plans; the phases 1–4 run inside one clang -cc1 job, in process, with -emit-obj: a multi-pass pipeline need not be multi-process. -clear-ast-before-backend frees the syntax tree once LLVM IR exists — the passes are sequential, so an earlier representation can be dropped.

The middle end is itself a pipeline of passes

Reproduce (clang 23.1.2, opt 23.1.2):

clang-23 --target=x86_64-linux-gnu -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm sum.c -o sum.ll
opt -passes='default<O0>' -print-pipeline-passes -disable-output sum.ll
opt -passes='default<O2>' -print-pipeline-passes -disable-output sum.ll | tr ',' '\n' | wc -l
opt -passes='mem2reg,instcombine,simplifycfg' -print-after-all -disable-output sum.ll 2>&1 | grep '^; \*\*\*'

Output (complete):

function(ee-instrument<>),always-inline,coro-cond(coro-early,cgscc(coro-split),coro-cleanup,globaldce),alloc-token,lower-comment-string,function(annotation-remarks),verify
119
; *** IR Dump After PromotePass on sum ***
; *** IR Dump After InstCombinePass on sum ***
; *** IR Dump After SimplifyCFGPass on sum ***

What to notice: even -O0 runs a pipeline of mandatory passes (always-inline, coroutine lowering, the verifier). default<O2> splits into 119 lines at its commas — roughly one line per pass or pass-manager adaptor. -print-after-all prints the IR after every pass (only the headers are kept here): the way to watch Theorem 0.1.6's intermediate programs \(p'\) one by one.

Single-pass compilation

In a single-pass compiler, the parser is the code generator: every grammar rule emits target code as soon as it has recognized its part of the input. Two things make that possible. The language must let every decision be made from what has already been read (Definition 0.1.9), and forward jumps — whose targets have not been generated yet — are emitted with a hole that is patched later (backpatching).

Definition 0.1.9 (One-pass translatable; declare before use)

A translation scheme is one-pass if the code emitted for the token at position \(j\) depends only on tokens \(1, \dots, j + k\) for a fixed lookahead \(k\), plus the state built from them, except for the targets of jumps to code not yet emitted. A language is declare-before-use if every identifier's declaration precedes all of its uses in the source text; declare-before-use (with forward declarations for mutual recursion) is what makes name resolution, type checking and layout one-pass.

Algorithm 0.1.10 (One-pass translation with backpatching)

  • Input: a token stream for the Tiny language of the lab (SPEC): assignments, while, if/else, return.
  • Output: stack code code[0..n) (the instruction set of Lesson 0.2, Algorithm 0.2.5).
  • Precondition: the token stream is syntactically valid; recursive descent with one token of lookahead decides every rule.
  • Postcondition: every jump in code targets the first instruction of the construct the language semantics prescribes (loop head, loop exit, else-branch, end of if).
  • Invariant (Lemma 0.1.17): every jump emitted so far either has its final target, or its index is on exactly one pending list, the one belonging to the innermost enclosing construct whose exit has not been emitted yet.
function Stmt():                                   # emits code for one statement
    if tok = 'while':
        advance(); top ← len(code)                  # the loop head is known now
        Expr()                                      # emits the condition
        exitHole ← Emit(jz, HOLE)                   # target unknown: pending
        Block()                                     # emits the body
        Emit(jmp, top)                              # backward jump: target known
        Patch(exitHole, len(code))                  # the exit is here
    elif tok = 'if':
        advance(); Expr(); elseHole ← Emit(jz, HOLE); Block()
        if tok = 'else':
            advance(); endHole ← Emit(jmp, HOLE)
            Patch(elseHole, len(code)); Block(); Patch(endHole, len(code))
        else:
            Patch(elseHole, len(code))
    else:                                          # x = e ;
        x ← ident(); expect('='); Expr(); expect(';'); Emit(store, x)

function Block(): expect('{'); while tok ≠ '}': Stmt(); expect('}')
function Emit(op, arg): append (op, arg) to code; return len(code) − 1
function Patch(i, target): code[i].arg ← target
# Expr() is recursive descent over the precedence levels of the grammar; each rule
# calls its operand rules and THEN emits the operator (postorder, Algorithm 0.2.5).

The lab's reference bytecode compiler is this algorithm run over the syntax tree instead of the tokens, which shows that one-pass emission and a separate parser are independent choices.

TCC emits code in source order, in one pass

Reproduce (tcc 0.9.27 from Ubuntu 24.04 apt-get install tcc; llvm-objdump 23.1.2):

tcc -c sum.c -o sum-tcc.o
llvm-objdump -d --no-show-raw-insn sum-tcc.o

Output (complete):

sum-tcc.o:  file format elf64-x86-64

Disassembly of section .text:

0000000000000000 <sum>:
       0:       pushq   %rbp
       1:       movq    %rsp, %rbp
       4:       subq    $0x10, %rsp
       b:       movq    %rdi, -0x8(%rbp)
       f:       movl    $0x0, %eax
      14:       movl    %eax, -0xc(%rbp)
      17:       movl    $0x0, %eax
      1c:       movl    %eax, -0x10(%rbp)
      1f:       movl    -0x10(%rbp), %eax
      22:       movl    -0x8(%rbp), %ecx
      25:       cmpl    %ecx, %eax
      27:       jge 0x4c <sum+0x4c>
      2d:       jmp 0x3f <sum+0x3f>
      32:       movl    -0x10(%rbp), %eax
      35:       movl    %eax, %ecx
      37:       addl    $0x1, %eax
      3a:       movl    %eax, -0x10(%rbp)
      3d:       jmp 0x1f <sum+0x1f>
      3f:       movl    -0xc(%rbp), %eax
      42:       movl    -0x10(%rbp), %ecx
      45:       addl    %ecx, %eax
      47:       movl    %eax, -0xc(%rbp)
      4a:       jmp 0x32 <sum+0x32>
      4c:       movl    -0xc(%rbp), %eax
      4f:       leave
      50:       retq

What to notice: the code appears in the order of the source text for (init; cond; inc) body: the condition (0x1f), then the increment i++ (0x32) — jumped over by jmp 0x3f because it was emitted before the body was read — then the body (0x3f), which jumps back to the increment. The forward jumps jge 0x4c and jmp 0x3f were backpatched (Algorithm 0.1.10). Every variable lives in a stack slot and is reloaded for every use: without a second pass, TCC never learns that i could stay in a register.

Query-based incremental compilation

A query-based compiler replaces "run pass \(P_i\) on everything" by "answer query \(q(k)\)", where \(q\) is one of a few hundred query kinds (type_of, optimized_mir, codegen_unit, …) and \(k\) a key (a definition, a module, a file). Answers are memoized in a database; after an edit the database must decide which memoized answers are still valid.

Definition 0.1.11 (Query system, dependency graph, fingerprint)

A query system is a set of input nodes (source files, compiler flags) and derived nodes \(v = q(k)\), each with a provider — a deterministic function that computes \(\mathrm{val}(v)\) from the values of the nodes it reads. Executing a provider records the sequence \(\mathrm{deps}(v)\) of nodes it read, in order. The recorded graph \((V, \{ (u, v) \mid u \in \mathrm{deps}(v) \})\) is the dependency graph; it is acyclic (a cycle is a compile error, "cycle detected when computing …"). A fingerprint \(\mathrm{fp}(v)\) is a hash of \(\mathrm{val}(v)\) with \(\mathrm{fp}(v) = \mathrm{fp}(v')\) assumed to imply equal values (a collision-free hash). After an edit, a node is green if its value is known to equal its previous value, and red if it was recomputed and its fingerprint changed.

Algorithm 0.1.12 (Demand-driven evaluation with red-green marking)

  • Input: the previous session's dependency graph \(G_{\mathrm{old}}\) with values and fingerprints; the new values of the input nodes; a demanded node \(v\).
  • Output: \(\mathrm{val}(v)\) in the new session.
  • Precondition: providers are deterministic and read other nodes only through the system (so \(\mathrm{deps}\) is complete); fingerprints are collision-free.
  • Postcondition: the returned value equals what a from-scratch compilation computes (Theorem 0.1.19); every node marked green in this session has the same value as in the previous one.
  • Invariant: a node is marked green only after every node in its old \(\mathrm{deps}\) has been marked green, in recorded order.
function Get(v):
    if v is colored in this session: return val(v)            # red or green: done
    if v ∈ G_old and TryMarkGreen(v): return val_old(v)       # reuse, no execution
    return Execute(v)

function TryMarkGreen(v):                                     # v existed last session
    for u in deps_old(v), in recorded order:
        if u is green: continue
        if u is red: return false
        if u is an input: mark u green if unchanged else red; if red: return false
        elif u ∈ G_old and TryMarkGreen(u): continue
        else:
            Execute(u)                                        # recompute u ...
            if u is red: return false                         # ... it really changed
    mark v green; val(v) ← val_old(v); return true

function Execute(v):
    val(v), deps(v) ← run provider of v, calling Get() for every node it reads
    mark v green if v ∈ G_old and fp(val(v)) = fp_old(v) else red   # early cutoff
    return val(v)

The line marked early cutoff is the heart of the design: a recomputed node whose value did not change is green, so nothing that depends on it is recomputed. rustc implements TryMarkGreen as DepGraph::try_mark_green in compiler/rustc_query_system/src/dep_graph/graph.rs [RUSTC-DepGraph]; Mokhov et al. call the same mechanism a verifying trace with early cutoff [MMP18].

rustc's dependency graph is a graph of queries

Reproduce (rustc 1.94.1; RUSTC_BOOTSTRAP=1 unlocks -Z flags on a stable toolchain):

cat > lib.rs <<'EOF'
pub mod a {
    pub fn sum(n: u32) -> u32 { (0..n).sum() }
}
pub mod b {
    pub fn answer() -> u32 { 42 }
}
EOF
rm -rf inc
RUSTC_BOOTSTRAP=1 rustc --crate-type=lib -C opt-level=0 -C codegen-units=16 -C incremental=inc -Z incremental-info lib.rs 2> first.txt
head -14 first.txt
RUSTC_BOOTSTRAP=1 rustc --crate-type=lib -C opt-level=0 -C codegen-units=16 -C incremental=inc -Z incremental-info lib.rs 2>&1 | grep 'session directory'

Output (head: the top of the statistics table; last command: complete):

[incremental]
[incremental] DepGraph Statistics
[incremental] ------------------------------------------------------------------------------------------
[incremental]
[incremental] Total Node Count: 3142
[incremental] Total Edge Count: 7405
[incremental]
[incremental]  Node Kind                           | Node Frequency   | Node Count  | Avg. Edge Count  |
[incremental] ------------------------------------------------------------------------------------------
[incremental]  impl_trait_header                   |            22.5% |         707 |              1.0 |
[incremental]  impl_parent                         |            22.4% |         705 |              1.0 |
[incremental]  implementations_of_trait            |             5.4% |         171 |              1.0 |
[incremental]  associated_item                     |             3.6% |         114 |              1.0 |
[incremental]  def_kind                            |             2.6% |          81 |              1.0 |
[incremental] session directory: 10 files hard-linked
[incremental] session directory: 0 files copied

What to notice: every node kind is the name of a query (def_kind, layout_of, type_of, …): even a six-line crate executes about 3 100 query invocations with 7 400 recorded dependency edges (Definition 0.1.11). On the second build nothing changed, so the previous session's artifacts are reused: its files are hard-linked into the new session instead of being regenerated.

Multi-level IR (MLIR)

Definition 0.1.13 (Dialect, conversion target, rewrite pattern)

An MLIR program is a tree of operations; each operation belongs to a dialect (scf structured control flow, cf unstructured branches, arith, llvm, …). A conversion target \(T\) classifies every operation as legal or illegal. A rewrite pattern \(\pi\) matches one operation and replaces it by a sequence of operations. A pattern is correct if its replacement refines the matched operation in every context (Definition 0.1.2 lifted to program fragments).

Algorithm 0.1.14 (Dialect conversion)

  • Input: a program \(m\); a conversion target \(T\); a set of rewrite patterns \(\Pi\).
  • Output: a program in which every operation is legal for \(T\), or failure.
  • Precondition: every pattern in \(\Pi\) is correct; there is a measure \(\mu\) from operations to a well-founded order such that every pattern replaces an operation \(o\) by operations each of strictly smaller \(\mu\) (e.g. "dialect level": \(\mu(\texttt{scf}) = 3 > \mu(\texttt{cf}) = \mu(\texttt{arith}) = 2 > \mu(\texttt{llvm}) = 1\)).
  • Postcondition: on success, the result refines \(m\) and contains only legal operations.
  • Invariant: the current program refines \(m\) (Theorem 0.1.20).
function Convert(m, T, Π):
    worklist ← all operations of m that are illegal for T, in pre-order
    while worklist ≠ ∅:
        o ← pop(worklist)
        π ← first pattern in Π (highest benefit first) that matches o
        if no such π: return failure("failed to legalize operation o")
        new ← π.rewrite(o)                    # replaces o in m
        push every illegal operation of new onto worklist
    return m

Progressive lowering of a loop in MLIR

Reproduce (mlir-opt and mlir-translate 23.1.2, conda-forge package mlir 23.1.2):

cat > sum.mlir <<'EOF'
func.func @sum(%n: index) -> index {
  %c0 = arith.constant 0 : index
  %c1 = arith.constant 1 : index
  %s = scf.for %i = %c0 to %n step %c1 iter_args(%acc = %c0) -> (index) {
    %next = arith.addi %acc, %i : index
    scf.yield %next : index
  }
  return %s : index
}
EOF
mlir-opt --convert-scf-to-cf sum.mlir
mlir-opt --convert-scf-to-cf --convert-to-llvm sum.mlir | mlir-translate --mlir-to-llvmir

Output (complete):

module {
  func.func @sum(%arg0: index) -> index {
    %c0 = arith.constant 0 : index
    %c1 = arith.constant 1 : index
    cf.br ^bb1(%c0, %c0 : index, index)
  ^bb1(%0: index, %1: index):  // 2 preds: ^bb0, ^bb2
    %2 = arith.cmpi slt, %0, %arg0 : index
    cf.cond_br %2, ^bb2, ^bb3
  ^bb2:  // pred: ^bb1
    %3 = arith.addi %1, %0 : index
    %4 = arith.addi %0, %c1 : index
    cf.br ^bb1(%4, %3 : index, index)
  ^bb3:  // pred: ^bb1
    return %1 : index
  }
}

; ModuleID = 'LLVMDialectModule'
source_filename = "LLVMDialectModule"

define i64 @sum(i64 %0) {
  br label %2

2:                                                ; preds = %6, %1
  %3 = phi i64 [ %8, %6 ], [ 0, %1 ]
  %4 = phi i64 [ %7, %6 ], [ 0, %1 ]
  %5 = icmp slt i64 %3, %0
  br i1 %5, label %6, label %9

6:                                                ; preds = %2
  %7 = add i64 %4, %3
  %8 = add i64 %3, 1
  br label %2

9:                                                ; preds = %2
  ret i64 %4
}

!llvm.module.flags = !{!0}

!0 = !{i32 2, !"Debug Info Version", i32 3}

What to notice: one program, three levels. The structured loop scf.for (whose trip count and induction variable are explicit — what loop tiling needs) becomes basic blocks with block arguments in cf, then the llvm dialect, then LLVM IR, where the block arguments turn into phi nodes. Each step is one application of Algorithm 0.1.14 with a different conversion target.

3. Worked examples

Running example. The loop s = 0; i = 0; while i < 2 { s = s + i; i = i + 1; } return s; (in C: the sum function above). Each technique processes it differently.

Multi-pass pipelines

The artifact after each phase of clang -O2 for the C version (the real-world boxes of this lesson and of Lesson 0.3 show every one of them in full):

pass representation out size for sum.c what changed
preprocessor C text without directives 6 lines nothing to expand here
front end (lex, parse, sema, IR generation) LLVM IR, -O0 style 3 alloca, 5 blocks each variable is a stack slot
mem2reg LLVM IR 2 phi in for.cond slots promoted to SSA values
instcombine LLVM IR add nuw nsw flags proved from the loop bounds
… about a hundred more passes of default<O2> LLVM IR no loop indvars (IndVarSimplify) rewrote the loop's exit value as a closed form; the dead loop was then deleted
back end (llc) x86-64 assembly 11 instructions imulq + shrq compute the closed form
assembler ELF relocatable object .text = 26 bytes (llvm-readelf -S) instructions encoded

The first four rows are the -print-after-all output above; the closed form is Lesson 0.3's clang-23 -O2 -emit-llvm box.

Single-pass compilation

Algorithm 0.1.10 on the Tiny running example. Each row is a point where the parser emits or patches; pending is the list of jumps whose target is still a hole.

step tokens just consumed action code emitted (index: instruction) pending holes
1 s = 0 ; Expr, Emit store 0: push 0, 1: store s {}
2 i = 0 ; Expr, Emit store 2: push 0, 3: store i {}
3 while top ← 4 — {}
4 i < 2 Expr (postorder) 4: load i, 5: push 2, 6: lt {}
5 { exitHole ← Emit(jz, HOLE) 7: jz ? {7}
6 s = s + i ; Expr, Emit store 8: load s, 9: load i, 10: add, 11: store s {7}
7 i = i + 1 ; Expr, Emit store 12: load i, 13: push 1, 14: add, 15: store i {7}
8 } Emit(jmp, top) 16: jmp 4 {7}
9 — Patch(7, 17) 7: jz 17 {}
10 return s ; Expr, Emit ret 17: load s, 18: ret {}

The backward jump (step 8) needs no patching: its target was recorded in step 3. The one forward jump waits on the pending list for exactly steps 5–9, i.e. while the loop body is being read — the invariant of Lemma 0.1.17. The final code is identical to the lab compiler's output (./course drill dispatch prints the same listing for a similar loop).

Query-based incremental compilation

A query graph for the Rust crate of the real-world box (a::sum and b::answer), simplified to eight nodes. First session: everything executes. Then the edit 42 → 43 in b::answer.

flowchart TD
  F([source file]) --> H[hir_crate]
  H --> SA[fn_sig a::sum]
  H --> SB[fn_sig b::answer]
  H --> MA[optimized_mir a::sum]
  H --> MB[optimized_mir b::answer]
  MA --> CA[codegen_unit a]
  MB --> CB[codegen_unit b]
  SB --> MB

Second session, demand codegen_unit a then codegen_unit b (Algorithm 0.1.12):

step call node examined action result
1 Get(CG a) CG a TryMarkGreen: first dep is MIR a —
2 TryMarkGreen(MIR a) hir_crate not an input, existed → TryMarkGreen(hir_crate) —
3 TryMarkGreen(hir_crate) source file input changed red input → TryMarkGreen(hir_crate) fails
4 Execute(hir_crate) hir_crate re-parse and lower the file; fingerprint differs (the literal changed) red
5 back in TryMarkGreen(MIR a) hir_crate is red return false —
6 Execute(MIR a) MIR a recompute; reads hir_crate; body of sum identical, fingerprint equal green (early cutoff)
7 back in TryMarkGreen(CG a) MIR a green all deps green → mark CG a green, reuse object file green, no codegen
8 Get(CG b) CG b TryMarkGreen(MIR b): deps hir_crate (red) → Execute(MIR b) —
9 Execute(MIR b) MIR b fingerprint differs (returns 43) red
10 Execute(CG b) CG b regenerate the object file for module b red

Only one codegen unit is rebuilt. Without early cutoff at step 6, the red hir_crate would force both codegen units to be rebuilt. (Real rustc splits hir_crate into per-owner opt_hir_owner_nodes queries (rustc 1.94.1) precisely so that an edit to one function does not even force re-executing the queries of the others.)

Multi-level IR (MLIR)

Algorithm 0.1.14 on sum.mlir, first conversion (--convert-scf-to-cf; target: scf illegal, everything else legal):

step worklist operation pattern new operations illegal new ops
0 [scf.for] — — — —
1 [] scf.for ForLowering cf.br, block ^bb1(%0, %1), arith.cmpi, cf.cond_br, body block ^bb2 with arith.addi ×2 and cf.br, exit block ^bb3 none (the scf.yield was folded into the back-edge cf.br)
2 [] — done: no illegal operations — —

The second conversion (--convert-to-llvm) makes arith, cf and func illegal and rewrites each remaining operation one-for-one into the llvm dialect (arith.addi → llvm.add, cf.cond_br → llvm.cond_br, …); mlir-translate then prints LLVM IR.

Try it

./course drill phases --seed 3 --difficulty medium asks which pipeline phase produces a given artifact; ./course drill dispatch --seed 1 --difficulty easy --solution prints the one-pass compiler's output for a loop like the one above.

4. Invariants and correctness

Multi-pass pipelines

Lemma 0.1.15 (Cache validity)

If every pass's preservation report is truthful, then at the start of every iteration of the loop of Algorithm 0.1.8, every cached pair \((A, r)\) satisfies \(r = A(m)\).

Proof

By induction on the iterations. Initialization: the cache is empty. Maintenance: during P.run, GetAnalysis either returns a cached \(r\) (valid by the hypothesis, since \(m\) has not changed yet) or stores \(A(m)\), also valid. After the run, the module becomes \(m' = P(m)\). An entry \((A, A(m))\) that survives has \(A \in \mathrm{Pres}(P)\), so by truthfulness \(A(m') = A(m)\): still valid. Removed entries are irrelevant. Hence the invariant holds for \(m'\) at the start of the next iteration.

Theorem 0.1.16 (Pass manager correctness)

Under the precondition of Algorithm 0.1.8, RunPipeline returns \(P_k(\dots P_1(m_0))\), and it terminates if every pass and analysis terminates.

Proof

Each pass receives exactly the analyses of its input module (Lemma 0.1.15), so it computes the same result as if it computed every analysis itself; the loop applies \(P_1, \dots, P_k\) in order, so it returns their composition. The loop runs \(k\) times and each iteration calls terminating functions. With Theorem 0.1.6, correct passes give a correct pipeline. When it breaks: a pass that modifies the CFG but claims to preserve the dominator tree leaves a stale tree in the cache; a later pass then reasons with wrong dominance and can miscompile. LLVM guards against this with -verify-analysis-invalidation and the verifier passes (Ch 12).

Single-pass compilation

Lemma 0.1.17 (Backpatch invariant)

During Algorithm 0.1.10, every emitted jump whose argument is HOLE is held in exactly one local variable (exitHole, elseHole or endHole) of an activation of Stmt that has not returned yet, and it is patched before that activation returns.

Proof

By inspection of Stmt, by induction on the nesting depth of the statement being compiled. A hole is created only by Emit(…, HOLE) and its index stored in a local of the current activation. Every path through the while branch and both paths through the if branch call Patch on every hole they created before returning (the while branch: one hole, patched after Block; if with else: two, both patched; if without else: one, patched). Nested statements run inside Block() and, by the induction hypothesis, patch their own holes before returning; they never touch the enclosing activation's locals. So no hole outlives its activation.

Theorem 0.1.18 (Backpatching yields correct jump targets)

When Algorithm 0.1.10 finishes, no HOLE remains, and every jump targets the instruction prescribed by the semantics: jz of a while targets the first instruction after the loop's jmp, the loop's jmp targets the first instruction of the condition, jz of an if targets the else-branch (or the end), and jmp of an if targets the end.

Proof

No hole remains by Lemma 0.1.17 applied to the outermost activations, all of which returned. For targets: top is len(code) just before Expr() emits the condition's first instruction, so jmp top targets it. Patch(exitHole, len(code)) runs right after Emit(jmp, top), so the target is the instruction following that jmp. The if cases are the same argument with Patch placed immediately before Block() of the else-branch and after it. Instructions are only ever appended, so an index, once read from len(code), keeps naming the same instruction.

Query-based incremental compilation

Theorem 0.1.19 (Early cutoff is sound)

Under the precondition of Algorithm 0.1.12, for every node \(v\) reached in the new session, Get(v) returns the value that a from-scratch compilation with the new inputs computes.

Proof

By induction on the height of \(v\) in the new session's dependency graph (inputs have height 0). Inputs: their values are read directly. Derived \(v\), two cases. (a) \(v\) is executed: its provider is deterministic and reads its dependencies through Get, which by the induction hypothesis returns from-scratch values, so \(v\) gets the from-scratch value. (b) \(v\) is marked green by TryMarkGreen: then every \(u\) in \(\mathrm{deps}_{\mathrm{old}}(v)\) was marked green, in the recorded order, so each has the same value as in the previous session (for executed \(u\) this uses the collision-free fingerprint; for inputs, equality of contents). A deterministic provider that reads the same values in the same order makes the same control-flow decisions and therefore reads exactly the same sequence of nodes again and returns \(\mathrm{val}_{\mathrm{old}}(v)\); by the induction hypothesis applied to those nodes, this is the from-scratch value. The order matters: a provider may decide which node to read next from a value it read before, and checking dependencies in recorded order ensures every checked node is one the new execution would really read. Termination: every node is colored at most once per session, and the dependency graph is finite and acyclic. When it breaks: a provider that reads state outside the system (a global variable, the clock, an untracked file) has incomplete \(\mathrm{deps}\), and case (b) can then reuse a stale value — the classic "incremental compilation bug" that rustc hunts with -Z incremental-verify-ich.

Multi-level IR (MLIR)

Theorem 0.1.20 (Dialect conversion terminates and refines)

Under the precondition of Algorithm 0.1.14, Convert terminates, and if it succeeds its result refines \(m\) and contains no illegal operation.

Proof

Termination: map the worklist to the multiset of \(\mu\)-values of its operations. Each iteration removes one operation \(o\) and adds operations of strictly smaller \(\mu\); by the Dershowitz–Manna theorem the multiset ordering over a well-founded order is well founded, so the loop runs finitely often. Refinement: each rewrite replaces an operation by a correct replacement; refinement of fragments in every context lifts to the whole program, and a finite sequence of refinements is a refinement by Lemma 0.1.3. Legality: every illegal operation ever created enters the worklist, and success means the worklist emptied with every operation rewritten. When it breaks: two patterns that rewrite \(a \to b\) and \(b \to a\) violate the measure; MLIR's real driver bounds the number of iterations of its greedy rewriter (GreedyRewriteConfig::maxIterations) and reports non-convergence rather than looping forever.

5. Complexity

Variables: \(n\) = size of the program (tokens or IR operations), \(k\) = number of passes, \(a\) = number of distinct analyses, \(c\) = cost of the most expensive analysis on the whole program, \(\lvert V \rvert, \lvert E \rvert\) = nodes and edges of the previous session's query graph, \(\delta\) = number of nodes whose value really changed.

Technique Time (worst) Time (typical) Space Variables
Multi-pass \(\sum_i T_{P_i}(n) + k \cdot a \cdot c\) dominated by a few expensive passes (inlining, instruction selection, register allocation) \(O(n)\) for the current representation (plus the previous one during a pass) \(n, k, a, c\)
Single-pass \(O(n)\) \(O(n)\), tiny constant \(O(d + s)\): nesting depth \(d\) plus symbol table size \(s\) \(n\)
Query-based first build: as multi-pass; rebuild: \(O(\lvert V \rvert + \lvert E \rvert)\) verification + cost of re-executed providers proportional to the edit's impact \(\delta\) when early cutoff succeeds \(O(\lvert V \rvert + \lvert E \rvert)\) persisted graph and results \(\lvert V \rvert, \lvert E \rvert, \delta\)
Multi-level IR \(O(\sum \text{pattern applications})\) per conversion, bounded by the measure \(\mu\) linear in the number of operations per lowering step \(O(n)\) \(n\), number of lowering steps

Proposition 0.1.21 (Costs)

(a) Algorithm 0.1.8 computes each analysis at most \(k\) times, at most once per pass. (b) Algorithm 0.1.10 runs in \(O(n)\) time. (c) One session of Algorithm 0.1.12 examines every node and every recorded edge of the previous graph at most once in TryMarkGreen, so its bookkeeping costs \(O(\lvert V \rvert + \lvert E \rvert)\) plus the providers it executes.

Proof

(a) An analysis is computed only inside P.run, when it is absent from the cache, and it then stays cached until the end of that pass (entries are removed only after P.run returns, and the module does not change while the pass runs), so each of the \(k\) passes computes it at most once. (b) Each token is consumed once; each Emit appends one instruction and each Patch writes one (constant time), and the number of instructions is linear in the number of tokens because each grammar rule emits a bounded number of instructions. (c) A node is colored at most once per session, and TryMarkGreen(v) iterates over \(\mathrm{deps}_{\mathrm{old}}(v)\) only while \(v\) is uncolored and returns after coloring it or finding a red dependency; so each edge is scanned at most once.

Pathological inputs.

  • Multi-pass: a pipeline that alternates a CFG-changing pass with a dominator-hungry pass, \((P_{\mathrm{cfg}}, P_{\mathrm{dom}})^{k/2}\), recomputes the dominator tree \(k/2\) times: \(\Theta(k \cdot n \log n)\) with a Lengauer–Tarjan-class algorithm (Ch 15), instead of once. LLVM's pipelines are ordered to avoid this.
  • Single-pass: the language can force a second pass. C's goto to a label later in the function is fine (backpatch), but a Pascal-style nested procedure that uses a variable declared after it cannot be compiled in one pass without forward declarations — the reason Pascal requires them.
  • Query-based: an edit to something everything depends on, such as a #[derive] on a widely used type or a change to compiler flags (an input of every node), turns the whole graph red; the rebuild then costs more than a clean build by the \(O(\lvert V \rvert + \lvert E \rvert)\) verification overhead.
  • MLIR: a pattern set without a decreasing measure (two patterns rewriting each other's output) does not terminate; the greedy driver's iteration cap turns this into a failure.

At scale. On a 5 000-function generated C file, the one-pass TCC compiled in 0.02 s, clang -O0 in 0.96 s and clang -O2 in 8.6 s on the course container (the "one pass is fast" box in §7; your numbers will differ, the ratios much less).

6. Variants and refinements

Multi-pass pipelines

  • Pass managers with analysis caching — LLVM's new pass manager [LLVM-NPM] versus the legacy one it replaced in LLVM 13–14: the new one caches per IR unit and invalidates precisely; trade-off: more boilerplate per pass (PreservedAnalyses).
  • Link-time optimization (LTO, ThinLTO) — moves the IR pipeline after linking so it sees the whole program; trade-off: link time and memory (ThinLTO keeps most work parallel by summaries).
  • Pass reordering and phase-ordering search — the order of passes matters (phase-ordering problem); production compilers fix one order tuned on benchmarks; research uses search or learning to pick per program.

Single-pass compilation

  • One-and-a-half passes — TCC makes a pre-pass only for initializers of unknown size and reversed argument order [TCC-Doc]; many "one-pass" compilers do a quick pre-scan for declarations. Trade-off: tiny extra time for a friendlier language.
  • Baseline JITs as one-pass compilers — V8's Sparkplug [V8-Sparkplug] and HotSpot's template interpreter generate machine code in one linear pass over bytecode (Lesson 0.3). Trade-off: code quality for compile speed.
  • Single-pass with a small optimizer — Wirth-style compilers keep a descriptor for the value on top of an expression stack (constant, variable, register) and delay emission until the consumer is known, which recovers constant folding and immediate operands.

Query-based incremental compilation

  • Durability levels (salsa) — inputs are tagged with how often they change (standard library: rarely); a change to a volatile input then skips verifying nodes that only read durable ones [Salsa]. Trade-off: extra bookkeeping per node.
  • Swift's request evaluator [SWIFT-Req] — requests with cycle detection and caching, adopted incrementally inside a traditional compiler; trade-off: only part of the compiler is demand-driven.
  • Red-green syntax trees (Roslyn) — immutable "green" nodes shared between versions plus lazily created "red" facades with parent pointers; an edit rebuilds only the path to the root [ROSLYN-Overview].
  • Build systems as query systems — Shake, Bazel and Buck2 use the same verifying-trace/early-cutoff machinery at file granularity [MMP18].

Multi-level IR (MLIR)

  • Greedy pattern rewriting vs dialect conversion — the greedy driver applies canonicalization patterns until a fixed point; dialect conversion is goal-directed by legality (Algorithm 0.1.14). Trade-off: generality vs predictability.
  • The transform dialect — encodes the lowering schedule itself as MLIR operations, so it can be scripted per workload; trade-off: another language to learn.
  • ClangIR (CIR) — an MLIR dialect for C/C++ that keeps source-level structure longer before lowering to LLVM IR, enabling C++-aware analyses.

7. In real compilers

Multi-pass pipelines

LLVM

clang/lib/Driver/Driver.cpp — Driver::BuildActions builds the phase graph printed by -ccc-print-phases (Driver::PrintActions), Driver::BuildJobs turns it into the jobs printed by -### [CLANG-Driver]. llvm/lib/Passes/PassBuilderPipelines.cpp — PassBuilder::buildPerModuleDefaultPipeline defines default<O2>; buildO0DefaultPipeline the -O0 one [LLVM-Pipelines] (LLVM 23.1.2).

  • GCC gcc/passes.def (GCC 15) lists every pass with NEXT_PASS (...), e.g. pass_build_ssa_passes, pass_expand; gcc/passes.cc runs them (execute_pass_list) [GCC-Passes].
  • pebblec pebble/lib/Driver/ — the course driver runs the front end, pir::verifyModule, PIR→LLVM and driver::getCoursePipeline() (pebble/lib/Driver/CoursePipeline.cpp) at -O1.

Find where LLVM does it. Open llvm/lib/Passes/PassBuilderPipelines.cpp at llvmorg-23.1.2 and find buildPerModuleDefaultPipeline. Question: which function does it return early for OptimizationLevel::O0? (quiz llvm-where-o0-pipeline)

GCC's pass list: tree, IPA and RTL passes

Reproduce (gcc 13.3.0, Ubuntu 24.04 — the GCC that ran here; the passes.def pointer above is pinned at gcc-15.1.0, whose list has 381 NEXT_PASS lines, so the count differs by version):

gcc -O2 -c -fdump-passes sum.c 2>&1 | wc -l
gcc -O2 -c -fdump-passes sum.c 2>&1 | grep -E '^\s*(tree|rtl|ipa)-' | awk '{print $1}' | cut -d- -f1 | sort | uniq -c

Output (complete):

364
     33 ipa
     86 rtl
    214 tree

What to notice: GCC's pipeline has three families of passes over three representations — tree passes on GIMPLE, ipa passes on the whole program's call graph, and rtl passes on the register-transfer language near the machine (Lesson 0.4). Same shape as LLVM's: a long composition of IR-to-IR passes between a front end and a back end.

Single-pass compilation

  • TCC tccgen.c (tag release_0_9_27) — gen_op emits machine code for a binary operator as soon as both operands are on its value stack (vpushi pushes a constant); block compiles a statement [TCC-Src].
  • Turbo Pascal — proprietary; its successor Delphi and the Free Pascal compiler still compile units in one pass over each routine's body.
  • C's heritage — C requires a declaration before a call because its first compilers were one-pass; clang enforces it (box below).

Declare before use: C's one-pass heritage

Reproduce (clang 23.1.2):

printf 'int f(void) { return g(); }\nint g(void) { return 1; }\n' > fwd.c
clang-23 --target=x86_64-linux-gnu -fsyntax-only fwd.c

Output (complete):

fwd.c:1:22: error: call to undeclared function 'g'; ISO C99 and later do not support implicit function declarations [-Wimplicit-function-declaration]
    1 | int f(void) { return g(); }
      |                      ^
1 error generated.

What to notice: g is defined, two lines later. A one-pass compiler must know g's type when it reaches the call (Definition 0.1.9); C's rule encodes that. Adding the prototype int g(void); before f makes the file compile.

One pass is fast: TCC vs clang on 5 000 functions

Reproduce (tcc 0.9.27, clang 23.1.2, Python 3.11; x86-64 Linux, 4 cores):

python3 -c "
for k in range(5000):
    print(f'int f{k}(int n) {{ int s = 0; for (int i = 0; i < n; i++) s += i * {k}; return s; }}')
" > big.c
time tcc -c big.c -o big-tcc.o
time clang-23 --target=x86_64-linux-gnu -O0 -c big.c -o big-O0.o
time clang-23 --target=x86_64-linux-gnu -O2 -c big.c -o big-O2.o
llvm-size big-tcc.o big-O0.o big-O2.o

Output (the time lines abridged to real; timings vary from run to run):

real    0m0.019s
real    0m0.956s
real    0m8.603s
   text    data     bss     dec     hex filename
 444919       0       0  444919   6c9f7 big-tcc.o
 480018       0       0  480018   75312 big-O0.o
 299626       0       0  299626   4926a big-O2.o

What to notice: the one-pass compiler is about 50 times faster than clang's unoptimizing multi-pass pipeline and 450 times faster than -O2, and its code is about as large as -O0's; the optimizing pipeline's code is a third smaller. That is the trade-off of §8 in numbers, and the reason baseline JITs (Lesson 0.3) are one-pass.

Query-based incremental compilation

  • rustc compiler/rustc_query_system/src/dep_graph/graph.rs — DepGraph::try_mark_green (Algorithm 0.1.12) [RUSTC-DepGraph]; queries are declared in compiler/rustc_middle/src/query/mod.rs (rustc 1.94.1).
  • Swift include/swift/AST/Evaluator.h — class Evaluator caches request results and detects cycles; design in docs/RequestEvaluator.md [SWIFT-Req] (swift-6.1-RELEASE).
  • Roslyn src/Compilers/Core/Portable/Syntax/GreenNode.cs — the shared immutable green nodes of red-green trees [ROSLYN-Overview].
  • rust-analyzer / salsa — #[salsa::tracked] functions are queries; revisions and durabilities implement early cutoff [Salsa].

Multi-level IR (MLIR)

  • MLIR mlir/lib/Transforms/Utils/DialectConversion.cpp — mlir::applyPartialConversion, class OperationLegalizer (Algorithm 0.1.14) [MLIR-DialectConversion]; mlir/lib/Conversion/SCFToControlFlow/SCFToControlFlow.cpp — ForLowering::matchAndRewrite produced the cf loop above (LLVM 23.1.2).
  • Flang lowers Fortran through its FIR dialect; IREE lowers ML models through linalg, flow, stream, hal; CIRCT lowers hardware descriptions.

Find where MLIR does it. Open mlir/lib/Conversion/SCFToControlFlow/SCFToControlFlow.cpp and find the pattern that lowers scf.for. Question: what is the name of the pattern struct? (quiz llvm-where-scf-for)

8. Comparison

Technique Power / precision Speed (asymptotic · practical) Output / error quality Implementation effort Typical use
Multi-pass pipelines any optimization; whole-function and (with LTO) whole-program views \(\sum_i T_{P_i}(n)\) · clang -O2: 8.6 s on 5 000 functions best code; errors reported per phase, all at once high, but modular (one pass at a time) production AOT compilers (Clang, GCC, rustc, pebblec)
Single-pass compilation local decisions only; no global optimization \(O(n)\) · TCC: 0.02 s on 5 000 functions (≈ 50× clang -O0) naive code (every variable in memory); stops at first error in the simplest designs lowest: one recursive-descent parser fast compilers (TCC, Turbo Pascal), baseline JITs, small DSLs
Query-based incremental compilation same as the batch pipeline it replaces rebuild \(\approx O(\lvert V \rvert + \lvert E \rvert)\) + impact of the edit same output; enables precise IDE answers very high: purity discipline everywhere IDEs and incremental builds (rustc, rust-analyzer, Swift, Roslyn)
Multi-level IR (MLIR) domain abstractions survive until lowered (loops, tensors, hardware) linear per lowering step · depends on the pattern sets depends on the dialects; verifier per dialect high infrastructure cost, low per new abstraction ML, HPC, hardware and new-language compilers (IREE, Flang, CIRCT)

Choose a multi-pass pipeline when code quality matters and a batch compile is acceptable — the default for an AOT compiler, and Pebble's choice. Choose single-pass when compile speed dominates (a baseline JIT, a scripting language, bootstrapping a toolchain) and the language is declare-before-use. Choose query-based when the same program is recompiled after small edits or queried by an IDE, and you can enforce that every computation reads only through the query system. Choose MLIR when the source domain has abstractions worth optimizing that LLVM IR would erase, or you need several lowering paths to different hardware.

9. Assessment

Technique Quiz ids (solutions/quizzes/ch00.yaml) Drill Flashcard tag Exercises
Multi-pass pipelines refinement-compose, refinement-ub, pass-manager-recompute, llvm-where-o0-pipeline ./course drill phases multi-pass E1
Single-pass compilation backpatch-trace, single-pass-tcc-order ./course drill dispatch (listing of a one-pass compile) single-pass lab L3
Query-based incremental compilation query-early-cutoff, query-red-green — (a random dependency graph plus an edit would only re-drill Algorithm 0.1.12's bookkeeping; the quiz traces one instance in full) query-based —
Multi-level IR (MLIR) mlir-progressive, llvm-where-scf-for — (MLIR is surveyed here and treated in Ch 8; its lowering steps are traced in the quiz) mlir —

Pitfall

"Multi-pass" does not mean "many processes" or "many reads of the source file". Clang runs preprocessing, parsing, semantic analysis, IR generation, optimization and code generation in one -cc1 process, reading the source once; the passes are over in-memory representations.

References

See the chapter references.