Lesson 8.7 — Multi-level IRs and real pipelines: MLIR, Clang, rustc, swiftc, GCC, and PIR

Techniques: MLIR's multi-level dialects and progressive lowering; pipelines of IRs in production compilers (Clang: AST → ClangIR → LLVM IR; rustc: HIR → THIR → MIR → LLVM IR; swiftc: AST → SIL → LLVM IR; GCC: GENERIC → GIMPLE → RTL); PIR, the course's MIR/SIL-style mid-level IR · Pebble uses: AST → PIR → LLVM IR (Ch 11) · Lab: exercise P1: write the running example in PIR by hand · Prerequisites: Lessons 8.3–8.4, Lesson 0.1 (multi-pass pipelines) · Time: 4–6 hours

No production compiler has one IR. Each of Lessons 8.1–8.6 covers one design point; this lesson is about the chains that real compilers build from them, and about the framework (MLIR) that makes "a chain of IRs" a first-class design. It ends with PIR, the IR you write in Chapter 11.

1. Problem and motivation

The problem. Different analyses need different abstraction levels: borrow checking needs source-level places and lifetimes, loop tiling needs loops and array indices, instruction selection needs machine operations. Choose a sequence of IRs, and the lowerings between them, so that each analysis runs where its facts are explicit, and so that each lowering is simple enough to be correct.

MLIR dialects and progressive lowering

MLIR [LAB+21] generalizes "an IR" to a framework of dialects. Each dialect contributes operations, types and attributes (scf.for, arith.addi, llvm.srem), and one module can mix them. A compiler lowers progressively: each pass converts some operations of one dialect into operations of lower dialects, until only the target dialect (for example llvm) remains. The design lets a compiler keep domain structure (tensors, affine loops, hardware primitives) as long as it is useful, instead of lowering everything at once to LLVM IR [MLIR-LangRef]. Lesson 0.1 covered MLIR as a pipeline shape. Here the question is how conversions are organized and checked.

Pipelines of IRs in production compilers

• Clang keeps one typed AST and generates LLVM IR from it directly (clang/lib/CodeGen). ClangIR (CIR), an MLIR dialect, is being upstreamed into LLVM as a high-level IR between the AST and LLVM IR, for C/C++-specific analyses such as lifetime checking [CIR-Src].
• rustc lowers the AST to HIR (desugared, Lesson 8.3), type-checks it into THIR (a typed tree), and builds MIR: a CFG over typed locals and places, with explicit drops, borrows and overflow checks. The borrow checker, const evaluation and Miri run on MIR [Rustc-Guide; RUSTC-MIR].
• swiftc type-checks the AST and generates SIL, an SSA IR with block arguments and ownership annotations. SIL has a raw stage (mandatory diagnostic passes: definite initialization, critical-edge splitting) and a canonical stage for optimization, and IRGen lowers it to LLVM IR [SIL-Docs].
• GCC turns front-end GENERIC trees into GIMPLE (TAC, Lesson 8.1), which goes into SSA form for the tree optimizers, and expands it to RTL, a machine-level list IR, for the back end [GCC-Int].

PIR: a MIR-style mid-level IR

The course's own compiler uses PIR (pir-spec), modeled on MIR and SIL: typed locals (not SSA registers), basic blocks, places with projections, and explicit safety checks. A front end in any language only has to print PIR text. SSA construction is left to the shared back end (mem2reg, and your own pass in Ch 16) (PROPOSAL §5.8).

2. Definitions and algorithms

Definition 8.7.1 (Dialect, operation, region)

An MLIR operation has a name d.op (dialect d), a list of operands (SSA values), a list of results, attributes, and a list of regions. A region is a list of blocks with arguments (Definition 8.4.4). A dialect is a named set of operation and type definitions, each with a verifier. An operation's regions give structured control flow (scf.for, scf.if), and a region's values follow the dominance rule of Lesson 8.4, extended to regions: a value defined outside a region is visible inside it.

MLIR dialects and progressive lowering

Definition 8.7.2 (Conversion target, legality, partial and full conversion)

A conversion target classifies every operation as legal, illegal or dynamically legal (a predicate on the operation). A conversion pattern rewrites one matched operation into a sequence of operations. Full conversion succeeds only if every illegal operation is rewritten. Partial conversion rewrites what it can and leaves operations that are not explicitly illegal in place. A pass is a lowering from dialect set \(\mathcal{A}\) to \(\mathcal{B}\) if its target makes exactly the operations of \(\mathcal{B}\) legal.

Algorithm 8.7.3 (Dialect conversion by legalization)

• Input: an operation tree, a conversion target, patterns \(\{P_i\}\), each with a benefit.
• Output: the rewritten tree, or failure (full conversion) when an illegal operation cannot be legalized.
• Precondition: each pattern is semantics-preserving (it rewrites an operation into an equivalent sequence).
• Postcondition: (full) no illegal operation remains; (partial) no illegal operation remains that some pattern sequence could legalize.
• Invariant: every operation already processed is legal or has been replaced by operations queued for processing.

function Convert(root, target, patterns, full):
    W ← all operations of root in preorder
    while W is not empty:
        op ← pop front of W
        if target.isLegal(op): continue
        for P in patterns matching op, by decreasing benefit:
            if P.rewrite(op) succeeds:           # may create new operations
                W ← new operations + W; break
        else:                                     # no pattern applied
            if full or target.isIllegal(op): return failure
    return root

Pipelines of IRs in production compilers

Definition 8.7.4 (IR pipeline; level of a fact)

An IR pipeline is a sequence of IRs \(I_0, I_1, \dots, I_k\) (Definition 8.1.1) with lowerings \(T_j : I_{j-1} \to I_j\). A property of programs (a fact: "this borrow is live", "this loop has trip count \(n\)", "this value is in register rax") is expressible at level \(j\) if it is determined by the \(I_j\) program alone, that is, two source programs with the same \(I_j\) image agree on it.

Definition 8.7.5 (Checked operation)

A checked operation \(a \oplus_{\mathrm{c}} b\) has the source semantics "the mathematical result if it fits in the type, otherwise trap". An IR makes the check explicit if it represents \(a \oplus_{\mathrm{c}} b\) as three parts: an overflow predicate \(o = \oplus\mathrm{o}(a, b)\), an assertion assert !o that traps, and the wrapping operation \(a \oplus b\).

Algorithm 8.7.6 (Lowering checked arithmetic to explicit checks: MIR, PIR)

• Input: an expression \(a \oplus_{\mathrm{c}} b\) in a statement position, with atoms \(a\), \(b\) of an integer type of width \(w\).
• Output: mid-level IR statements and a new block boundary.
• Precondition: the IR has an overflow predicate for \(\oplus\) (PIR: saddo, ssubo, smulo; MIR: AddWithOverflow returning a pair) and an assert that traps.
• Postcondition: the output traps exactly when the source traps, and otherwise yields the same value (Theorem 8.7.10).
• Invariant: the destination is written only after the assertion has passed.

function LowerChecked(d = a ⊕c b):
    o ← NewLocal(bool)
    Emit(o = ⊕o a, b)                     # PIR: _o = saddo a, b
    Emit(assert !o, overflow)             # MIR: assert(!o) -> [success: next, unwind]
    Emit(d = ⊕ a, b)                      # the wrapping operation

PIR: a MIR-style mid-level IR

Definition 8.7.7 (PIR function)

A PIR function (pir-spec §6) has typed locals _0 … _{n-1} (parameters first), and blocks bb0 … bbm holding statements place = rvalue, calls and asserts, each block ending in exactly one terminator (goto, br, switch, return, trap, unreachable). Locals are mutable storage, not SSA values: a local may be assigned in several statements. A place is a local or global with projections (_1.f, _2[_3], (*_4).x). Rvalues have no side effects. The verifier rules V1–V20 (pir-spec §13) are its \(\mathrm{WF}\) (Definition 8.1.1).

Algorithm 8.7.8 (PIR to SSA through memory: alloca + mem2reg)

• Input: a verified PIR function.
• Output: LLVM IR in SSA form for its scalar locals.
• Precondition: the function is verified (V1–V20).
• Postcondition: the LLVM function behaves like the PIR function (Theorem 8.7.12); scalar locals whose address is never taken become SSA values with phis.
• Invariant: before mem2reg, local _k lives in the stack slot %_k.addr, and every read of _k is a load and every write a store of that slot.

function PIRToLLVM(f):
    for each local _k: emit in the entry block  %_k.addr = alloca T(_k)
    for each parameter _k: store the incoming argument into %_k.addr
    for each block bb and statement s:
        operands: load each local read by s from its slot
        emit the operation; store the result into the destination's slot
    terminators: br / switch / ret on loaded operands; assert c, k → br c, %ok, %trap
    then run mem2reg (SROA) on f:                  # Cytron et al., Ch 16
        every alloca whose address is used only by loads and stores becomes SSA values,
        with phis at the iterated dominance frontier of its stores

3. Worked example

MLIR dialects and progressive lowering on the running example

euler1.mlir (Lesson 8.4's MLIR box) goes through two lowerings. Counting operations per dialect after each stage (the real-world box below):

stage	pass	operations by dialect	legal after the pass
0	input	arith 11, func 1, scf 5	everything (no target yet)
1	--convert-scf-to-cf	arith 13, cf 7, func 1	scf illegal: scf.for/scf.if/scf.yield → blocks, cf.br with block arguments, cf.cond_br; the loop bound needs 2 more arith ops
2	--convert-to-llvm	llvm 22	only llvm legal: arith.addi → llvm.add, cf.br → llvm.br, func.func → llvm.func

Skipping stage 1 shows partial conversion at work. --convert-to-llvm alone converts arith and func but has no pattern for scf, so it leaves scf.for in place, holding llvm.srem operations inside its region (box below). The module is then a legal mixture of dialects, which is the point of Definition 8.7.2. mlir-translate would reject it, since only the llvm dialect translates to LLVM IR.

Pipelines of IRs on the running example

The same function through four production pipelines (all commands in §7):

compiler	IR	size for euler1	what is explicit at this level
Clang 23	AST (-ast-dump)	45 nodes	source structure, types, implicit casts (Lesson 8.3)
	LLVM IR at -O0	8 blocks, 31 instructions	memory for every variable (alloca/load/store)
rustc 1.94	HIR	while desugared to loop/if/break	names resolved (Lesson 8.3)
	MIR (--emit=mir, opt-level 0)	13 blocks (bb0–bb12), 23 locals (_0–_22)	overflow and division checks as assert terminators; moves and copies
GCC 14	GENERIC (-fdump-tree-original)	a C-like tree with gotos already inserted for the loop	the loop shape chosen by the front end
	GIMPLE (-fdump-tree-gimple)	12 statements plus labels	three-address code (Lesson 8.1)
	RTL (-fdump-rtl-expand, -O1)	35 instructions (insn, jump_insn), 5 labels	machine modes, registers, the flags register

Rust's MIR is the only one of these with the division checks. i % 3 needs two asserts in MIR, one for division by zero and one for MIN % -1. Both are removed later because the divisor is a constant, but MIR states them, so the borrow checker and Miri see Rust's semantics exactly.

PIR: a MIR-style mid-level IR on gcd

gcd in PIR, written by hand the way the Pebble front end lowers t = a % b with its checks (a division by zero cannot happen after the loop test, so only the -1 case needs care), is in the real-world box of §7. Algorithm 8.7.8 turns it into an alloca per local, and SROA then promotes them:

PIR local	LLVM at -O0	after sroa
_0 "a" (parameter)	%a.addr = alloca i64, store i64 %a	%a.addr.0 = phi i64 [ %a, %bb0 ], [ %b.addr.0, %bb5 ]
_1 "b" (parameter)	%b.addr	%b.addr.0 = phi i64 [ %b, %bb0 ], [ %t.addr.0, %bb5 ]
_2 "t"	%t.addr	%t.addr.0 = phi i64 [ 0, %bb3 ], [ %6, %bb4 ]
_3, _4 (bool)	alloca i8 + zext/trunc	values %0, %3; the zext/trunc pairs stay until instcombine

The PIR function has 7 blocks and 5 locals, and every local is assigned in more than one place or read in a loop. The SSA form has three phis, at bb1 (the loop header: a, b) and bb5 (the join of the -1 test: t). This is the division of labor of PROPOSAL §5.8: front ends emit locals, and SSA construction is shared.

Try it

Exercise P1: write multiples.pir (the running example with checked additions) and run pir-opt --verify-only, pir-run and pebblec --from-pir --emit=llvm. ./course test 8 runs its tests.

4. Invariants and correctness

MLIR dialects and progressive lowering

Theorem 8.7.9 (Progressive lowering is correct; conversion terminates under a decreasing measure)

(a) If every pattern is semantics-preserving (the replacement refines the operation, Definition 0.1.2), then every successful run of Algorithm 8.7.3 refines its input, and a pipeline of such conversions refines the original program. (b) If there is a well-founded measure \(\mu\) on operations such that every operation a pattern creates for \(op\) is legal or has \(\mu\) smaller than \(\mu(op)\), the algorithm terminates.

Proof

(a) Each successful iteration replaces one operation by a refinement of it in an otherwise unchanged context. Refinement is preserved by contexts: the semantics of an operation tree is compositional, so replacing a sub-term by a refinement refines the whole. Refinement is transitive (Theorem 0.1.6), so any finite sequence of rewrites, and any pipeline of passes, refines the input. Legal operations are left untouched. (b) Every operation enters the worklist once, either initially or as a pattern's output. Assign to each operation the multiset of \(\mu\)-values of the illegal operations in its "descendant" queue. A rewrite removes \(op\) and adds only legal operations or operations of smaller \(\mu\), so the multiset of \(\mu\) over pending illegal operations decreases in the multiset order, which is well founded when \(\mu\) is (Dershowitz–Manna). Legal operations are popped and discarded. Hence the loop terminates. MLIR's conversion driver additionally detects recursive application of the same pattern, which is the practical form of this measure [MLIR-DialectConv].

Pipelines of IRs in production compilers

Theorem 8.7.10 (Explicit checks preserve checked semantics)

For atoms \(a, b\) of width \(w\), the output of Algorithm 8.7.6 traps iff \(a \oplus b\) (computed over the integers) is outside the signed range of width \(w\), and otherwise assigns \(d\) the mathematical result.

Proof

By the definition of the overflow predicate (pir-spec §9.1: "true iff the signed result does not fit in \(w\) bits"), \(o\) is true iff the mathematical result is out of range. The assert !o traps exactly then (pir-spec §10). Otherwise execution continues to the wrapping operation, whose result is the mathematical result modulo \(2^w\), which equals the mathematical result because it is in range. The destination is written only in the second case, so a trap leaves \(d\) unchanged, which is observable only through side effects before the trap and is the same in the source.

Proposition 8.7.11 (Facts are lost, never gained, down a pipeline)

If each lowering \(T_j\) is a function (Definition 8.7.4), a fact expressible at level \(j\) is expressible at every earlier level \(i < j\). Conversely, there are facts expressible at level \(i\) that no later level expresses.

Proof

If two source programs have the same image in \(I_i\), they have the same image in \(I_j\) (apply \(T_{i+1}, \dots, T_j\)), so they agree on every fact determined by \(I_j\). Hence a level-\(j\) fact is determined at level \(i\). For the converse, lowering is typically not injective. Two Rust functions that differ only in a borrow that the borrow checker rejects for one of them lower to the same LLVM IR (MIR-to-LLVM code generation never looks at lifetimes; only the borrow checker's verdict differs), so "this borrow outlives its owner" is expressible in MIR but not in LLVM IR. The practical rule: run each analysis at the highest level at which its facts are still expressible, which is why rustc borrow-checks MIR, and why MLIR keeps loops as affine.for for as long as polyhedral transformations need them.

PIR: a MIR-style mid-level IR

Theorem 8.7.12 (Algorithm 8.7.8 is correct)

For a verified PIR function, the LLVM function produced by the alloca scheme behaves like the PIR function (pir-spec §17's acceptance test), and mem2reg preserves that behavior while making every promotable local an SSA value.

Proof sketch (full proofs: the alloca scheme is checked behaviorally in tests/pir/unit/CodeGenTest.cpp against pir-run; SSA construction is proved correct in [CFRWZ91] and in Ch 16)

Alloca scheme: by induction on execution steps, the contents of slot %_k.addr equal the PIR local _k. Each statement loads the locals it reads (values equal by hypothesis), computes the same operation, and stores into the destination's slot. Terminators test the same values. assert becomes a branch to a block that calls the trap function, which is the same observable behavior. mem2reg: an alloca whose address is used only by loads and stores in the function is a scalar variable in the sense of Lesson 8.4. SSA construction replaces each load by the value of the reaching store, with a phi where several stores reach, which is exactly the renaming correctness theorem of SSA construction.

5. Complexity

Variables: \(N\) = operations, \(P\) = patterns, \(k\) = pipeline length, \(m\) = blocks, \(L\) = locals.

Technique	Time (worst)	Time (typical)	Space	Justification
MLIR dialects and progressive lowering	\(O(N \cdot P)\) per conversion (each operation tries each pattern), times the length of rewrite chains	\(O(N)\) with pattern tables indexed by operation name	\(O(N)\)	Algorithm 8.7.3: each operation is visited once; patterns are indexed by root operation name in MLIR
Pipelines of IRs in production compilers	\(\sum_j T_j(n)\)	linear per stage	one IR alive at a time, or several (rustc keeps HIR, THIR per body, MIR)	a pipeline is a composition (Lesson 0.1)
PIR: a MIR-style mid-level IR	alloca scheme \(O(n)\); mem2reg \(O(n + m \cdot L)\) phis worst	near-linear	\(L\) allocas	one load/store per operand; phi placement as in Lesson 8.4

Pathological family. In MLIR, a pattern that rewrites op into an operation that another pattern rewrites back makes Algorithm 8.7.3 loop. The measure of Theorem 8.7.9(b) does not exist, and MLIR's driver reports a recursion instead. In the alloca scheme, a PIR function with \(L\) locals all assigned in each of \(m\) if-diamonds creates \(\Theta(mL)\) phis. That is the chain-of-diamonds family of Lesson 8.4.

At scale. rustc runs the borrow checker on MIR for every function. MIR is kept compact (locals and places, not SSA values), and the MIR for a function is built lazily, per body, through the query system (Lesson 0.1).

6. Variants and refinements

MLIR dialects and progressive lowering

• Greedy pattern rewriting (applyPatternsGreedily) applies canonicalization patterns to a fixed point without a legality target. It is used for simplification rather than lowering.
• One-shot --convert-to-llvm gathers the conversion patterns of every dialect that implements the ConvertToLLVMPatternInterface. It is convenient, but partial, as §3 shows.
• Type conversion (TypeConverter) changes the types of block arguments while converting operations. This is the part of dialect conversion that updates the successor operands of Lesson 8.4.

Pipelines of IRs in production compilers

• ClangIR (CIR) adds a high-level MLIR dialect between the Clang AST and LLVM IR, for analyses that need C/C++ semantics (lifetime checks, idiom recognition) [CIR-Src]. It is not enabled in the conda build used here (§7).
• rustc's MIR phases: built, analysis (borrow checking), runtime (drop elaboration done), and optimized MIR, each with stricter invariants. It is one IR with several levels.
• GCC's GIMPLE levels: high GIMPLE (with nested binds and exception regions), low GIMPLE, and SSA GIMPLE. Each lowering removes constructs.

PIR: a MIR-style mid-level IR

• Direct SSA from the front end (Braun et al. [BBH+13]; Cranelift's SSABuilder, Go): generate SSA while lowering and skip the alloca round trip. The cost is a more complex front end, which is what PIR avoids so that any language can produce it.
• SIL-style block arguments in PIR would let front ends emit SSA directly. PIR 1.x deliberately keeps locals. See PROPOSAL §5.8 and pir-spec §1 on versioning.
• Explicit checks vs trapping operations: PIR spells out saddo + assert + add, like MIR. Cranelift has trapping operations instead (uadd_overflow_trap). Explicit checks are easier to eliminate in an optimizer (Ch 18's bounds-check elimination), and trapping operations are more compact.

7. In real compilers

MLIR dialects and progressive lowering

MLIR (LLVM 23.1.2): applyPartialConversion and applyFullConversion in mlir/lib/Transforms/Utils/DialectConversion.cpp, with the interface in mlir/include/mlir/Transforms/DialectConversion.h [MLIR-DialectConv]. The scf lowering patterns ForLowering and IfLowering are in mlir/lib/Conversion/SCFToControlFlow/SCFToControlFlow.cpp [MLIR-SCF].

MLIR: two conversions, and a partial one

Reproduce (mlir-opt 23.1.2, conda-forge mlir 23.1.2; euler1.mlir from Lesson 8.4's MLIR box):

count() { grep -oE '\b(scf|cf|arith|func|llvm)\.[a-z_]+' | sed 's/\..*//' | sort | uniq -c | awk '{printf "%s:%s ", $2, $1}'; echo; }
echo -n "input:            "; count < euler1.mlir
echo -n "scf-to-cf:        "; mlir-opt euler1.mlir --convert-scf-to-cf | count
echo -n "+convert-to-llvm: "; mlir-opt euler1.mlir --convert-scf-to-cf --convert-to-llvm | count
mlir-opt euler1.mlir --convert-to-llvm

Output (complete):

input:            arith:11 func:1 scf:5 
scf-to-cf:        arith:13 cf:7 func:1 
+convert-to-llvm: llvm:22 
module {
  llvm.func @euler1(%arg0: i64) -> i64 {
    %0 = llvm.mlir.constant(0 : i64) : i64
    %1 = llvm.mlir.constant(1 : i64) : i64
    %2 = llvm.mlir.constant(3 : i64) : i64
    %3 = llvm.mlir.constant(5 : i64) : i64
    %4 = llvm.add %arg0, %1 : i64
    %5 = scf.for %arg1 = %1 to %4 step %1 iter_args(%arg2 = %0) -> (i64)  : i64 {
      %6 = llvm.srem %arg1, %2 : i64
      %7 = llvm.srem %arg1, %3 : i64
      %8 = llvm.icmp "eq" %6, %0 : i64
      %9 = llvm.icmp "eq" %7, %0 : i64
      %10 = llvm.or %8, %9 : i1
      %11 = scf.if %10 -> (i64) {
        %12 = llvm.add %arg2, %arg1 : i64
        scf.yield %12 : i64
      } else {
        scf.yield %arg2 : i64
      }
      scf.yield %11 : i64
    }
    llvm.return %5 : i64
  }
}

What to notice: the counts are the table of §3. The last command skipped --convert-scf-to-cf: arith and func became llvm, but scf.for, scf.if and scf.yield remain, with llvm.srem inside their regions. That is a partial conversion (Definition 8.7.2). The module is still valid MLIR, because each operation is verified by its own dialect.

Pipelines of IRs in production compilers

Clang generates LLVM IR from the AST in clang/lib/CodeGen/CGStmt.cpp. ClangIR's code generator is in clang/lib/CIR/CodeGen/CIRGenStmt.cpp (CIRGenFunction::emitForStmt, LLVM 23.1.2) [CIR-Src]. rustc builds MIR in compiler/rustc_mir_build/src/builder/mod.rs (build_mir_inner_impl, construct_fn) and defines it in compiler/rustc_middle/src/mir/mod.rs (Body, BasicBlockData) and mir/syntax.rs (TerminatorKind, Rvalue; rustc 1.94.1) [RUSTC-MIR]. swiftc generates SIL in lib/SILGen/SILGen.cpp and lowers it in lib/IRGen/IRGenSIL.cpp (swift-6.1-RELEASE) [SWIFT-SILGen]. GCC gimplifies in gcc/gimplify.cc and expands to RTL in gcc/cfgexpand.cc (pass_expand, expand_gimple_basic_block; gcc 15.1) [GCC-Expand].

rustc's MIR for the running example

Reproduce (rustc 1.94.1; euler1.rs from Lesson 8.3's HIR box):

rustc --crate-type=lib -C opt-level=0 --emit=mir -o - euler1.rs

Output (complete):

// WARNING: This output format is intended for human consumers only
// and is subject to change without notice. Knock yourself out.
// HINT: See also -Z dump-mir for MIR at specific points during compilation.
fn euler1(_1: i64) -> i64 {
    debug n => _1;
    let mut _0: i64;
    let mut _2: i64;
    let mut _4: bool;
    let mut _5: i64;
    let mut _6: bool;
    let mut _7: i64;
    let mut _8: i64;
    let mut _9: bool;
    let mut _10: bool;
    let mut _11: bool;
    let mut _12: bool;
    let mut _13: bool;
    let mut _14: i64;
    let mut _15: i64;
    let mut _16: bool;
    let mut _17: bool;
    let mut _18: bool;
    let mut _19: bool;
    let mut _20: i64;
    let mut _21: (i64, bool);
    let mut _22: (i64, bool);
    scope 1 {
        debug s => _2;
        let mut _3: i64;
        scope 2 {
            debug i => _3;
        }
    }

    bb0: {
        _2 = const 0_i64;
        _3 = const 1_i64;
        goto -> bb1;
    }

    bb1: {
        _5 = copy _3;
        _4 = Le(move _5, copy _1);
        switchInt(move _4) -> [0: bb12, otherwise: bb2];
    }

    bb2: {
        _8 = copy _3;
        _9 = Eq(const 3_i64, const 0_i64);
        assert(!move _9, "attempt to calculate the remainder of `{}` with a divisor of zero", copy _8) -> [success: bb3, unwind continue];
    }

    bb3: {
        _10 = Eq(const 3_i64, const -1_i64);
        _11 = Eq(copy _8, const i64::MIN);
        _12 = BitAnd(move _10, move _11);
        assert(!move _12, "attempt to compute the remainder of `{} % {}`, which would overflow", copy _8, const 3_i64) -> [success: bb4, unwind continue];
    }

    bb4: {
        _7 = Rem(move _8, const 3_i64);
        _6 = Eq(move _7, const 0_i64);
        switchInt(move _6) -> [0: bb5, otherwise: bb8];
    }

    bb5: {
        _15 = copy _3;
        _16 = Eq(const 5_i64, const 0_i64);
        assert(!move _16, "attempt to calculate the remainder of `{}` with a divisor of zero", copy _15) -> [success: bb6, unwind continue];
    }

    bb6: {
        _17 = Eq(const 5_i64, const -1_i64);
        _18 = Eq(copy _15, const i64::MIN);
        _19 = BitAnd(move _17, move _18);
        assert(!move _19, "attempt to compute the remainder of `{} % {}`, which would overflow", copy _15, const 5_i64) -> [success: bb7, unwind continue];
    }

    bb7: {
        _14 = Rem(move _15, const 5_i64);
        _13 = Eq(move _14, const 0_i64);
        switchInt(move _13) -> [0: bb10, otherwise: bb8];
    }

    bb8: {
        _20 = copy _3;
        _21 = AddWithOverflow(copy _2, copy _20);
        assert(!move (_21.1: bool), "attempt to compute `{} + {}`, which would overflow", copy _2, move _20) -> [success: bb9, unwind continue];
    }

    bb9: {
        _2 = move (_21.0: i64);
        goto -> bb10;
    }

    bb10: {
        _22 = AddWithOverflow(copy _3, const 1_i64);
        assert(!move (_22.1: bool), "attempt to compute `{} + {}`, which would overflow", copy _3, const 1_i64) -> [success: bb11, unwind continue];
    }

    bb11: {
        _3 = move (_22.0: i64);
        goto -> bb1;
    }

    bb12: {
        _0 = copy _2;
        return;
    }
}

What to notice: a CFG over typed locals (_2 is s, _3 is i), like PIR. i % 3 becomes two assert terminators (division by zero, MIN % -1) before the Rem, each with an unwind edge. s += i becomes AddWithOverflow plus an assert, which is Algorithm 8.7.6 with a tuple result. copy/move operands make ownership explicit for the borrow checker. The debug s => _2 lines map locals back to source names.

GCC's GENERIC, and ClangIR's availability

Reproduce (gcc 14.2.0; clang 23.1.2 from conda-forge):

gcc-14 -O1 -c -fdump-tree-original=stdout euler1.c -o /dev/null
clang-23 -fclangir -emit-cir euler1.c -o -

Output (complete):

;; Function euler1 (null)
;; enabled by -tree-original


{
  long int s = 0;

    long int s = 0;
  {
    long int i = 1;

        long int i = 1;
    goto <D.2776>;
    <D.2775>:;
    if (i % 3 == 0 || i % 5 == 0)
      {
        s = s + i;
      }
    i++ ;
    <D.2776>:;
    if (i <= n) goto <D.2775>; else goto <D.2773>;
    <D.2773>:;
  }
  return s;
}
error: clang IR support not available, rebuild clang with -DCLANG_ENABLE_CIR=ON

What to notice: GENERIC is a tree (the if keeps its full || condition), but GCC's C front end has already turned the for into labels and gotos. The next stage, GIMPLE (Lesson 8.1's box), flattens the condition into three-address code. (The duplicated declaration lines are how this dump prints a declaration statement next to its DECL_EXPR.) The second command shows that ClangIR is an optional component of LLVM 23: this conda-forge build was configured without it. The source pointer above is where it lives.

The Swift compiler is not available in the course container. The SIL documentation at tag swift-6.1-RELEASE shows block arguments directly (quoted from docs/SIL.rst, section "Basic Blocks" [SIL-Docs]; not run here):

sil @iif : $(Builtin.Int1, Builtin.Int64, Builtin.Int64) -> Builtin.Int64 {
bb0(%cond : $Builtin.Int1, %ifTrue : $Builtin.Int64, %ifFalse : $Builtin.Int64):
  cond_br %cond : $Builtin.Int1, then, else
then:
  br finish(%ifTrue : $Builtin.Int64)
else:
  br finish(%ifFalse : $Builtin.Int64)
finish(%result : $Builtin.Int64):
  return %result : $Builtin.Int64
}

and states: "In SIL, basic blocks take arguments, which are used as an alternative to LLVM's phi nodes. Basic block arguments are bound by the branch from the predecessor block" [SIL-Docs].

PIR: a MIR-style mid-level IR

Pebble: the PIR text format, verifier and interpreter in pebble/include/pebble/PIR/ (Parser.h, Verifier.h, Interpreter.h), the tools pir-opt and pir-run in pebble/tools/, and the lowering to LLVM IR (Ch 11) behind pebblec --from-pir (pir-spec §16–17).

PIR: gcd by hand, verified, interpreted, lowered and promoted to SSA

Reproduce (the course tools built against LLVM 23.1.2: build/<preset>/bin/pir-opt, pir-run, pebblec; opt 23.1.2):

cat > gcd.pir <<'EOF'
pir 1.0

extern fn @pebble_print_int(i64)

fn @gcd(_0: i64 "a", _1: i64 "b") -> i64 {
  let _2: i64 "t"
  let _3: bool
  let _4: bool
bb0:
  goto bb1
bb1:
  _3 = ne _1, 0
  br _3, bb2, bb6
bb2:
  _4 = eq _1, -1
  br _4, bb3, bb4
bb3:
  _2 = 0
  goto bb5
bb4:
  _2 = srem _0, _1
  goto bb5
bb5:
  _0 = _1
  _1 = _2
  goto bb1
bb6:
  return _0
}

fn @main() -> i64 {
  let _0: i64
bb0:
  _0 = call @gcd(1071, 462)
  call @pebble_print_int(_0)
  return 0
}
EOF
pir-opt --verify-only gcd.pir && echo verified
pir-run gcd.pir; echo; echo exit=$?
pebblec --from-pir --emit=llvm -O0 gcd.pir -o - | opt -passes=sroa -S | sed -n '/define internal i64 @gcd/,/^}/p'

Output (complete):

verified
21
exit=0
define internal i64 @gcd(i64 %a, i64 %b) {
entry:
  br label %bb0

bb0:                                              ; preds = %entry
  br label %bb1

bb1:                                              ; preds = %bb5, %bb0
  %b.addr.0 = phi i64 [ %b, %bb0 ], [ %t.addr.0, %bb5 ]
  %a.addr.0 = phi i64 [ %a, %bb0 ], [ %b.addr.0, %bb5 ]
  %0 = icmp ne i64 %b.addr.0, 0
  %1 = zext i1 %0 to i8
  %2 = trunc i8 %1 to i1
  br i1 %2, label %bb2, label %bb6

bb2:                                              ; preds = %bb1
  %3 = icmp eq i64 %b.addr.0, -1
  %4 = zext i1 %3 to i8
  %5 = trunc i8 %4 to i1
  br i1 %5, label %bb3, label %bb4

bb3:                                              ; preds = %bb2
  br label %bb5

bb4:                                              ; preds = %bb2
  %6 = srem i64 %a.addr.0, %b.addr.0
  br label %bb5

bb5:                                              ; preds = %bb4, %bb3
  %t.addr.0 = phi i64 [ 0, %bb3 ], [ %6, %bb4 ]
  br label %bb1

bb6:                                              ; preds = %bb1
  ret i64 %a.addr.0
}

What to notice: the PIR has locals _0…_4 assigned in several places (_0 = _1, _1 = _2), so it is not SSA, and pir-opt accepts it. After the alloca scheme and sroa, each scalar local is SSA with phis: %b.addr.0 and %a.addr.0 at the loop header bb1, and %t.addr.0 at the join bb5. %a.addr.0 reads %b.addr.0, another phi of the same block, which is the parallel-copy semantics of Definition 8.4.2. PIR block names survive into LLVM IR (bb0…bb6), and the debug names "a", "b", "t" become value names. (pir-run prints 21 without a newline, hence the echo.)

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
MLIR dialects and progressive lowering	any abstraction as a dialect; mixed-level modules	\(O(N)\) per conversion with indexed patterns · two passes for euler1	per-dialect verifiers; partial conversions leave mixed modules	high framework cost, low per dialect	ML and HPC compilers (IREE, Triton), Flang, CIRCT, ClangIR
Pipelines of IRs in production compilers	each analysis at its level (Proposition 8.7.11)	sum of stages · rustc builds MIR per body, lazily	dumps per stage (-ast-dump, --emit=mir, -fdump-tree-*)	high: several IRs, each with a verifier	Clang, rustc, swiftc, GCC
PIR: a MIR-style mid-level IR	typed locals, places, explicit checks; SSA left to the back end	alloca scheme \(O(n)\) + mem2reg · gcd: 5 locals → 3 phis	text format with line/column verifier messages (V15: …)	low for front ends (print text); the shared back end does SSA	the Pebble compiler; any language front end targeting the course back end

Choose MLIR when your domain has abstractions worth keeping above LLVM IR (tensors, loops, hardware ops) and you would otherwise build a custom IR stack. Design a pipeline by listing the facts each analysis needs and placing it at the highest level where they are expressible. Choose a MIR-style IR with locals as the interface between front ends and a shared back end: it is the easiest target to generate and still a CFG, and SSA construction happens once, behind it.

9. Assessment

Technique	Quiz ids (solutions/quizzes/ch08.yaml)	Drill	Flashcard tag	Exercises
MLIR dialects and progressive lowering	mlir-partial-conversion, mlir-where-conversion	none: the dialect counts depend on MLIR's patterns, not on a small algorithm; the quiz traces them	mlir	—
Pipelines of IRs in production compilers	pipeline-match, mir-asserts-count	none: which compiler uses which IR is recall; the quiz asks it with computation on MIR	ir-pipelines	—
PIR: a MIR-style mid-level IR	pir-phis-gcd, pir-not-ssa	none: the hand-written PIR exercise is graded by tests	pir	P1

A mid-level IR with locals is not 'unoptimized SSA'

PIR and MIR locals are storage: _0 = _1 in a loop is a real copy between two mutable cells, and a reference &_1 makes _1 addressable. SSA construction must treat address-taken locals as memory (LLVM's sroa leaves such allocas alone). Converting naively, by renaming every assignment, is wrong as soon as a place projection or a reference is involved.

References

See the chapter references.