Lesson 0.4 — Retargeting: the m × n problem, LLVM, GCC and Cranelift

Techniques: the m × n problem and shared IRs (UNCOL), LLVM's three-phase design, GCC's GENERIC/GIMPLE/RTL pipeline, Cranelift · Pebble uses: LLVM's three-phase design (Pebble front end → PIR → LLVM IR → any LLVM back end) · Lab: your first.ll (labs/ch00-first-ir) runs on whatever machine lli runs on · Prerequisites: Lesson 0.1 · Time: 3–5 hours

The same eleven lines of LLVM IR, compiled by the same llc for three machines:

llc -O2 -mtriple=x86_64-linux-gnu sumloop.ll -o -     # addl / incl / cmpl / jl
llc -O2 -mtriple=aarch64-linux-gnu sumloop.ll -o -    # add / add / cmp / b.lt
llc -O2 -mtriple=riscv64-linux-gnu sumloop.ll -o -    # addw / addiw / blt

This lesson is about the design that makes that possible — and about how GCC and Cranelift organize the same problem differently.

1. Problem and motivation

The problem. Given \(m\) source languages and \(n\) target machines, provide a correct compiler for every pair while writing as little code as possible, and without losing code quality on any pair.

The m × n problem and shared IRs (UNCOL)

Writing one compiler per (language, machine) pair costs \(m \cdot n\) compilers. In 1958 Strong et al. proposed UNCOL, a UNiversal Computer Oriented Language: every language is translated into it and every machine translates out of it, so \(m + n\) translators suffice [SWT+58]. UNCOL itself failed — no single language could serve every source and every machine in the 1950s — but the argument (Theorem 0.4.2) underlies every modern retargetable compiler. Pebble relies on it twice: any front end that prints PIR reaches LLVM (Lesson 0.1's tour), and LLVM reaches every machine it has a back end for.

LLVM's three-phase design

Lattner and Adve designed LLVM around a typed, SSA-based, target-independent-ish IR with a textual, binary and in-memory form [LA04]. The three phases — front end, optimizer, back end — communicate only through that IR [Lat11]. Clang, rustc, swiftc, Flang, Julia, Zig and pebblec share LLVM's optimizer and its ~48 registered back ends.

GCC's GENERIC, GIMPLE and RTL

GCC predates LLVM and is also retargetable, but through two shared IRs: language front ends produce GENERIC trees, which are lowered to GIMPLE (three-address code, then SSA) for the middle end, which is expanded to RTL (register-transfer lists) for the back end; each target is described by a machine description (.md files) of RTL patterns [GCC-Int]. Historically GCC's components were deliberately intertwined; modularity came later.

Cranelift

Cranelift is a code generator written in Rust for WebAssembly runtimes (Wasmtime) and as an alternative rustc back end, designed for fast compilation with good-enough code and for verifiability [CL-Docs]. Its IR (CLIF) uses block parameters instead of phi nodes, its mid-end optimizes with an e-graph, and its instruction selection is written in a DSL (ISLE) whose rules are small enough to verify formally [VPF+24].

2. Definitions and algorithms

Definition 0.4.1 (Translation network)

Let \(\mathcal{S} = \{S_1, \dots, S_m\}\) be source languages and \(\mathcal{T} = \{T_1, \dots, T_n\}\) targets. A translation network is a set \(N\) of translators, each a compiler \(A \rightharpoonup B\) between two languages (sources, targets, or intermediate languages). \(N\) serves the pair \((S_i, T_j)\) if \(N\) contains a path \(S_i \to L_1 \to \dots \to T_j\) of translators; its compiler is their composition. A shared IR design is the network \(\{S_i \to I\}_{i} \cup \{I \to T_j\}_{j}\) for one intermediate language \(I\).

Theorem 0.4.2 (m × n versus m + n)

(a) The direct design \(\{S_i \to T_j\}_{i,j}\) has \(m \cdot n\) translators. (b) A shared IR design serves all \(m \cdot n\) pairs with \(m + n\) translators. (c) Every modular network that serves all pairs — one with no translator directly from a source language to a target — has at least \(m + n\) translators. (d) If every translator is correct, every served pair's compiler is correct.

Proof

(a) One translator per pair. (b) The pair \((S_i, T_j)\) is served by the path \(S_i \to I \to T_j\), and there are \(m\) front ends and \(n\) back ends. (c) Serving \((S_i, T_1)\) requires a path leaving \(S_i\), hence at least one translator whose source is \(S_i\); these are distinct for distinct \(i\) (a translator has one source language), giving \(m\) translators. Symmetrically each \(T_j\) needs a translator whose target is \(T_j\), giving \(n\). In a modular network no translator has both a source in \(\mathcal{S}\) and a target in \(\mathcal{T}\), so the two groups are disjoint: at least \(m + n\). (Without modularity the groups may overlap, and the counting argument alone gives only \(\max(m, n)\); but then a translator is tied to one source and one target, which is the coupling a shared IR exists to remove.) (d) By Theorem 0.1.6 applied to the path.

Counting for this course

Pebble (C++ front end), a future Rust front end for Pebble, C (clang) and Rust (rustc): 4 front ends. x86-64, AArch64, RISC-V 64 and WebAssembly: 4 targets. Direct compilers: 16. Through LLVM IR: 8 translators, and in practice only the 4 front ends are written by language teams, because LLVM already ships the back ends.

The m × n problem and shared IRs (UNCOL)

Definition 0.4.3 (Target independence of an IR program)

An IR program \(q\) is target-independent if \(\mathrm{Beh}(q)\) (Definition 0.1.1) is the same for every target the IR supports. A front end is target-independent if its output is. In practice neither holds for C: the sizes of long and pointers, struct layout, calling-convention lowering and the target datalayout string are decided by the front end, so a module records its triple (architecture–vendor–OS–environment) and data layout.

Algorithm 0.4.4 (Compiling through a shared IR)

• Input: a program \(p \in S_i\); a target triple \(t\).
• Output: code for \(t\).
• Precondition: a front end for \(S_i\) and a back end for \(t\) are registered; the front end is invoked for \(t\) (Definition 0.4.3).
• Postcondition: the output refines \(p\) (Theorem 0.4.2 (d)).
• Invariant: between phases, the program exists only as IR; no phase reads another phase's internal data.

function Compile(p, S_i, t):
    ir ← FrontEnd[S_i](p, target_info(t))     # sizes, ABI, data layout for t
    ir ← Optimize(ir)                          # target-independent passes (+ t's cost model)
    be ← Registry.lookup(t.arch)               # error if no back end registered
    return be.Codegen(ir, t)                   # instruction selection, RA, emission

The front end is not target-independent: long in three ABIs

Reproduce (clang 23.1.2):

printf 'long twice(long x) { return 2 * x; }\n' > long.c
for t in x86_64-linux-gnu i686-linux-gnu x86_64-windows-msvc; do
  echo "== $t"
  clang-23 --target=$t -O2 -S -emit-llvm long.c -o - | grep -E '^define|datalayout'
done

Output (complete):

== x86_64-linux-gnu
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
define dso_local range(i64 -9223372036854775808, 9223372036854775807) i64 @twice(i64 noundef %0) local_unnamed_addr #0 {
== i686-linux-gnu
target datalayout = "e-m:e-p:32:32-p270:32:32-p271:32:32-p272:64:64-i128:128-f64:32:64-f80:32-n8:16:32-S128"
define dso_local range(i32 -2147483648, 2147483647) i32 @twice(i32 noundef %0) local_unnamed_addr #0 {
== x86_64-windows-msvc
target datalayout = "e-m:w-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
define dso_local noundef range(i32 0, -1) i32 @twice(i32 noundef %0) local_unnamed_addr #0 {

What to notice: C's long is i64 on 64-bit Linux (LP64) but i32 on 32-bit Linux and on 64-bit Windows (LLP64): the front end made a target decision, and the data layout (p:32:32 = 32-bit pointers) is baked into the module. LLVM IR is a shared IR for code generation, not a portable distribution format (Definition 0.4.3). (The range attributes record that \(2x\) is even, so it can never equal one particular odd value: range expresses a single, possibly wrapping, interval, so each target excludes one odd value — the maximum on Linux, \(-1\) in range(i32 0, -1) on Windows.)

LLVM's three-phase design

In LLVM, Algorithm 0.4.4's registry is TargetRegistry: each back end registers a Target at startup, and TargetRegistry::lookupTarget(Triple, Error) finds it; Target::createTargetMachine builds a TargetMachine, whose addPassesToEmitFile sets up the code-generation pipeline (TargetPassConfig: instruction selection, scheduling, register allocation, emission). Each back end is mostly generated from TableGen descriptions (llvm/lib/Target/X86/X86.td, RISCV.td).

One IR, three machines

Reproduce (llc 23.1.2; comment and directive lines filtered out):

cat > sumloop.ll <<'EOF'
define i32 @sum(i32 %n) {
entry:
  br label %loop
loop:
  %i = phi i32 [ 0, %entry ], [ %i.next, %body ]
  %s = phi i32 [ 0, %entry ], [ %s.next, %body ]
  %done = icmp sge i32 %i, %n
  br i1 %done, label %exit, label %body
body:
  %s.next = add i32 %s, %i
  %i.next = add i32 %i, 1
  br label %loop
exit:
  ret i32 %s
}
EOF
for t in x86_64-linux-gnu aarch64-linux-gnu riscv64-linux-gnu; do
  echo "== $t"
  llc -O2 -mtriple=$t sumloop.ll -o - | sed -n '/^sum:/,/^\.Lfunc_end0:/p' | grep -v '^\s*\.cfi\|^\s*[#/]\|^\s*$'
done

Output (complete):

== x86_64-linux-gnu
sum:                                    # @sum
    xorl    %eax, %eax
    xorl    %ecx, %ecx
    cmpl    %edi, %ecx
    jge .LBB0_3
    .p2align    4
.LBB0_2:                                # %body
    addl    %ecx, %eax
    incl    %ecx
    cmpl    %edi, %ecx
    jl  .LBB0_2
.LBB0_3:                                # %exit
    retq
.Lfunc_end0:
== aarch64-linux-gnu
sum:                                    // @sum
    mov w9, wzr
    mov w8, wzr
    cmp w9, w0
    b.ge    .LBB0_2
.LBB0_1:                                // %body
    add w8, w8, w9
    add w9, w9, #1
    cmp w9, w0
    b.lt    .LBB0_1
.LBB0_2:                                // %exit
    mov w0, w8
    ret
.Lfunc_end0:
== riscv64-linux-gnu
sum:                                    # @sum
    mv  a1, a0
    li  a2, 0
    li  a0, 0
    sext.w  a1, a1
    blez    a1, .LBB0_2
.LBB0_1:                                # %body
    addw    a0, a0, a2
    addiw   a2, a2, 1
    blt a2, a1, .LBB0_1
.LBB0_2:                                # %exit
    ret
.Lfunc_end0:

What to notice: the phi nodes became registers (%eax/w8/a0 for s), the loop was rotated so the test sits at the bottom — target-independent decisions, identical in all three. The machine-specific parts differ: x86 compares into flags then jumps (cmpl/jl), AArch64 likewise with its own condition codes, RISC-V has compare-and-branch (blt) and must sign-extend 32-bit values (sext.w, addw). This IR has no triple and no data layout, so it is target-independent (Definition 0.4.3) — clang's output would not be.

llc knows 48 targets; rustc reuses LLVM

Reproduce (llc 23.1.2, rustc 1.94.1):

llc --version | sed -n '/Registered Targets:/,$p' | tail -n +2 | wc -l
llc --version | sed -n '/Registered Targets:/,$p' | grep -E ' (aarch64|riscv64|wasm32|x86-64|nvptx64) '
rustc -vV | grep LLVM

Output (complete):

48
    aarch64     - AArch64 (little endian)
    nvptx64     - NVIDIA PTX 64-bit
    riscv64     - 64-bit RISC-V
    wasm32      - WebAssembly 32-bit
    x86-64      - 64-bit X86: EM64T and AMD64

LLVM version: 21.1.8

What to notice: one llc binary contains 48 registered back ends (Algorithm 0.4.4's registry), from CPUs to GPUs (nvptx64) to virtual machines (wasm32). rustc ships its own LLVM (21.1.8 here, not the course's 23.1.2): the front end and the shared IR version travel together.

GCC's GENERIC, GIMPLE and RTL

Algorithm 0.4.5 (Gimplification: flattening to three-address code)

• Input: a GENERIC expression tree \(e\) (arbitrarily nested), a statement list \(L\).
• Output: a GIMPLE operand for \(e\), with statements appended to \(L\).
• Precondition: side effects have been ordered by the front end (sequence points).
• Postcondition: every appended statement has at most one operator and its operands are variables, temporaries or constants (three-address form).
• Invariant: every temporary is assigned exactly once before its use.

function Gimplify(e, L):
    if e is a variable or a constant: return e
    if e = op(e1, ..., ek):
        for j in 1..k: a_j ← Gimplify(e_j, L)          # operands first, left to right
        t ← new temporary D.nnnn
        append "t = op(a_1, ..., a_k)" to L
        return t
# control constructs become labels and gotos: while (c) b  ⇒  goto L2; L1: b; L2: if (c) goto L1; else goto L3; L3:

This is Algorithm 0.2.7 (three-address code) under another name: GIMPLE is GCC's register-machine code. expand then turns each GIMPLE statement into RTL, choosing patterns from the machine description; later RTL passes (combine, register allocation, scheduling) work on machine-level RTL.

GCC's three levels on one function

Reproduce (gcc 13.3.0, Ubuntu 24.04 — the GCC that ran here; the source pointers in §7 are pinned at gcc-15.1.0, which was not run. The pass-numbered dump file names depend on the GCC version):

gcc -O2 -c -fdump-tree-gimple -fdump-tree-optimized -fdump-rtl-expand sum.c
cat sum.c.*t.gimple
grep -v '^;;' sum.c.*t.optimized | sed -n '/^int sum/,$p'
sed -n '/insn 15 /,/insn 18 /p' sum.c.*r.expand | head -12

Output (complete):

int sum (int n)
{
  int D.2748;
  int s;

  s = 0;
  {
    int i;

    i = 0;
    goto <D.2746>;
    <D.2745>:
    s = s + i;
    i = i + 1;
    <D.2746>:
    if (i < n) goto <D.2745>; else goto <D.2743>;
    <D.2743>:
  }
  D.2748 = s;
  return D.2748;
}


int sum (int n)
{
  int i;
  int s;

  <bb 2> [local count: 118111600]:
  if (n_4(D) > 0)
    goto <bb 3>; [89.00%]
  else
    goto <bb 4>; [11.00%]

  <bb 3> [local count: 955630225]:
  # s_9 = PHI <s_6(3), 0(2)>
  # i_11 = PHI <i_7(3), 0(2)>
  s_6 = s_9 + i_11;
  i_7 = i_11 + 1;
  if (n_4(D) != i_7)
    goto <bb 3>; [89.00%]
  else
    goto <bb 4>; [11.00%]

  <bb 4> [local count: 118111600]:
  # s_10 = PHI <s_6(3), 0(2)>
  return s_10;

}


(insn 15 14 16 5 (parallel [
            (set (reg/v:SI 83 [ <retval> ])
                (plus:SI (reg/v:SI 83 [ <retval> ])
                    (reg/v:SI 82 [ i ])))
            (clobber (reg:CC 17 flags))
        ]) "sum.c":4:7 -1
     (nil))
(insn 16 15 18 5 (parallel [
            (set (reg/v:SI 82 [ i ])
                (plus:SI (reg/v:SI 82 [ i ])
                    (const_int 1 [0x1])))
            (clobber (reg:CC 17 flags))

What to notice: GIMPLE is flattened, goto-based three-address code (Algorithm 0.4.5: the for became labels and a conditional goto); the optimized GIMPLE is in SSA form (s_9 = PHI <…>, Ch 16) — GCC keeps the loop (unlike clang's closed form in Lesson 0.3). RTL is machine-flavored: SI is a 32-bit mode, and the x86 add pattern records that it clobbers the flags register — a fact that only exists at the RTL level.

Cranelift

Definition 0.4.6 (CLIF and ISLE lowering rules)

CLIF is an SSA IR in which each block declares block parameters and each branch passes arguments to them (instead of phi nodes). An ISLE lowering rule has the form (rule prio (lower pattern) result): when pattern matches the CLIF instruction being lowered (including its operands' defining instructions and types), result builds machine instructions. Rules with higher prio are tried first.

Algorithm 0.4.7 (Rule-based instruction selection)

• Input: a CLIF function; a rule set \(R\) for the target.
• Output: machine instructions on virtual registers (register allocation follows).
• Precondition: every rule is correct (its machine code refines the matched CLIF); for every well-typed CLIF instruction some rule matches (coverage).
• Postcondition: the machine code refines the CLIF function.
• Invariant: every CLIF value that is used by an already-lowered instruction has a register (or was folded into the user's pattern).

function Lower(f, R):
    for block b in reverse postorder, instruction i in b, from last to first:
        if i has side effects, or some already-lowered instruction uses its result
           without having folded i into its own pattern:
            r ← highest-priority rule in R whose pattern matches i (with operands)
            emit r's result instructions; mark operands r folded in as covered

Cranelift IR from Wasmtime

Reproduce (Wasmtime 37.0.2 release binary for x86-64 Linux, which embeds Cranelift):

cat > sum.wat <<'EOF'
(module
  (func (export "sum") (param $n i32) (result i32)
    (local $i i32) (local $s i32)
    (block $exit
      (loop $top
        (br_if $exit (i32.ge_s (local.get $i) (local.get $n)))
        (local.set $s (i32.add (local.get $s) (local.get $i)))
        (local.set $i (i32.add (local.get $i) (i32.const 1)))
        (br $top)))
    (local.get $s)))
EOF
mkdir -p clif
wasmtime compile --emit-clif clif sum.wat -o sum.cwasm
cat 'clif/wasm[0]--function[0].clif'

Output (complete):

;; Intermediate Representation of function <wasm[0]::function[0]>:
function u0:0(i64 vmctx, i64, i32) -> i32 tail {
    gv0 = vmctx
    gv1 = load.i64 notrap aligned readonly gv0+8
    gv2 = load.i64 notrap aligned gv1+16
    stack_limit = gv2

                                block0(v0: i64, v1: i64, v2: i32):
@0022                               v4 = iconst.i32 0
@0038                               v11 = iconst.i32 1
@0026                               jump block3(v4, v4)  ; v4 = 0, v4 = 0

                                block3(v5: i32, v9: i32):
@002c                               v7 = icmp sge v5, v2
@002c                               v8 = uextend.i32 v7
@002d                               brif v8, block2, block5

                                block5:
                                    v13 = iconst.i32 1
                                    v14 = iadd.i32 v5, v13  ; v13 = 1
@0033                               v10 = iadd.i32 v9, v5
@003d                               jump block3(v14, v10)

                                block2:
@0043                               jump block1(v9)

                                block1(v3: i32):
@0043                               return v3
}

What to notice: block3(v5: i32, v9: i32) is the loop header with two block parameters (Definition 0.4.6) — i and s — and jump block3(v14, v10) passes the next values, where LLVM IR would have two phi nodes (compare the MLIR box of Lesson 0.1, which uses the same idea). @00xx are byte offsets in the Wasm module, kept for debugging. vmctx and stack_limit show Cranelift serving a runtime: every function receives the Wasm instance and checks for stack overflow.

3. Worked examples

Running example. The sum loop, from the four vantage points.

The m × n problem and shared IRs (UNCOL)

Count translators for \(m\) languages and \(n\) targets:

\(m\)	\(n\)	direct \(m \cdot n\)	shared IR \(m + n\)	saving
2	2	4	4	0
3	3	9	6	3
4	4	16	8	8
10	48	480	58	422

The last row is roughly LLVM's situation (48 registered targets, Lesson box above): the shared IR pays off as soon as \(m, n \ge 3\) (for \(m = n = 2\) the designs tie).

LLVM's three-phase design

Algorithm 0.4.4 on sumloop.ll for -mtriple=riscv64-linux-gnu:

step	phase	input	output	target knowledge used
1	front end	(hand-written IR; no front end)	IR without triple	none
2	optimizer (-O2 in llc = codegen-level only)	IR	IR, loop rotated	cost model only
3	TargetRegistry::lookupTarget("riscv64-linux-gnu")	triple	Target for RISC-V	which back end
4	instruction selection	IR	RISC-V machine instructions on virtual registers	legal types: i32 is not legal, so ops are widened (addw, sext.w)
5	register allocation, emission	machine instructions	assembly	a0–a2 registers, calling convention (a0 = argument and result)

GCC's GENERIC, GIMPLE and RTL

Algorithm 0.4.5 on the body statement s += i and the loop:

step	GENERIC	GIMPLE appended	temporaries
1	s = s + i	s = s + i; (already three-address: operands are variables)	none
2	i++	i = i + 1;	none
3	for (…; i < n; …)	labels <D.2745>, <D.2746>, <D.2743>; goto <D.2746>; before the body; if (i < n) goto <D.2745>; else goto <D.2743>; after it	none
4	return s	D.2748 = s; return D.2748;	D.2748 (the return slot)

This is exactly the first GIMPLE dump above, including the test at the bottom of the loop.

Cranelift

Algorithm 0.4.7 on block5 of the CLIF above for x86-64 (instructions visited last to first):

step	CLIF instruction	lowered?	rule (from cranelift/codegen/src/isa/x64/lower.isle)	machine code
1	jump block3(v14, v10)	yes (side effect)	jump with block arguments	moves into the header's registers + jmp
2	v10 = iadd.i32 v9, v5	yes (used by step 1)	iadd_base_case_32_or_64_lea (priority −5; the load-sinking rules −4/−3 do not match: no loads)	a lea pseudo-instruction, emitted as add when equivalent
3	v14 = iadd.i32 v5, v13	yes	the same rule; to_amode_add folds the constant v13 into the address offset	lea 1(v5), i.e. add $1
4	v13 = iconst.i32 1	no — folded into step 3's pattern	—	—

4. Invariants and correctness

The m × n problem and shared IRs (UNCOL)

Theorem 0.4.2 (d) is the correctness statement: a pair's compiler is the composition of its front end and back end, correct by Theorem 0.1.6. The theorem's hidden hypothesis is that the IR's semantics is the same on both sides of the interface: if a front end assumes long is 64 bits and the back end's target has 32-bit long, each translator is "correct" for a different meaning of the IR. Definition 0.4.3 is what makes the hypothesis checkable: the module carries its triple and data layout, and LLVM warns when they do not match the target (next box).

When the IR is not for your target

Reproduce (clang 23.1.2, llc 23.1.2):

clang-23 --target=x86_64-linux-gnu -O2 -fno-discard-value-names -S -emit-llvm sum.c -o sum-O2.ll
llc -O2 -mtriple=aarch64-linux-gnu sum-O2.ll -o /dev/null 2>&1 | sort | uniq -c

Output (complete):

      2 '+cmov' is not a recognized feature for this target (ignoring feature)
      2 '+cx8' is not a recognized feature for this target (ignoring feature)
      2 '+fxsr' is not a recognized feature for this target (ignoring feature)
      2 '+mmx' is not a recognized feature for this target (ignoring feature)
      2 '+sse' is not a recognized feature for this target (ignoring feature)
      2 '+sse2' is not a recognized feature for this target (ignoring feature)
      2 '+x87' is not a recognized feature for this target (ignoring feature)
      2 'x86-64' is not a recognized processor for this target (ignoring processor)

What to notice: clang's IR carries x86 function attributes ("target-cpu"="x86-64", "target-features"="+cmov,…"): it was produced for x86-64. The AArch64 back end ignores them here and still generates code, but for code that depends on long or on struct layout the result would silently mean something else. For RISC-V the same command fails outright ("RV64 target requires an RV64 CPU"). Retarget by re-running the front end.

LLVM's three-phase design

Proposition 0.4.8 (Phase isolation)

If every LLVM pass reads and writes only the IR (and analyses computed from it), then replacing the front end or the back end cannot invalidate the correctness of the optimizer, and the optimizer's correctness can be tested on IR alone.

Proof

Correctness of the optimizer (Definition 0.1.4) quantifies over all IR programs; it mentions neither the front end nor the back end. Algorithm 0.4.4's invariant (phases communicate only through IR) means a different front end only changes which IR programs reach the optimizer, and a different back end only changes what happens after it. This is why LLVM's own tests are opt-level lit tests on .ll files, and why this course tests your passes the same way (Ch 12). The isolation is not total — the optimizer consults TargetTransformInfo for costs — but costs affect only which correct transformation is chosen.

GCC's GENERIC, GIMPLE and RTL

Lemma 0.4.9 (Gimplification preserves values)

If evaluating \(e\) in state \(\sigma\) yields \(v\) (and \(e\)'s side effects are ordered as the precondition requires), then executing the statements appended by Gimplify(e, L) from \(\sigma\) and then reading the returned operand yields \(v\), without changing any variable of the source program.

Proof

By structural induction on \(e\). Leaves: no statement, the operand is \(e\). Node \(op(e_1, \dots, e_k)\): by induction each \(a_j\) holds the value of \(e_j\) after its statements; later statements only assign fresh temporaries (the invariant), so \(a_j\) is unchanged until the final statement \(t = op(a_1, \dots, a_k)\), which computes \(v\) into the fresh \(t\). No source variable is assigned.

Cranelift

Theorem 0.4.10 (Rule-based lowering is correct if every rule is)

Under the precondition of Algorithm 0.4.7, the machine code refines the CLIF function.

Proof sketch (full treatment of rule verification: [VPF+24])

Every CLIF instruction is either lowered by a rule or folded into the pattern of a rule that is lowered (coverage + the invariant), so every computation is accounted for exactly once. Each rule's result refines the pattern it matched (rule correctness); patterns are trees of CLIF instructions and results are sequences of machine instructions on fresh virtual registers, so correct rules compose by substitution, and the whole function is the composition over the dataflow graph. Priorities choose among matching correct rules, so they cannot break correctness. VanHattum et al. check ISLE rules against formal semantics of CLIF and of the target ISA with an SMT solver, and report real bugs found and reproduced that way — the precondition is not a formality.

5. Complexity

Variables: \(m\) languages, \(n\) targets, \(\lvert I \rvert\) = size of the IR's semantics (number of instructions and rules), \(s\) = program size, \(r\) = number of ISLE rules.

Technique	Time (worst)	Time (typical)	Space	Variables
The m × n problem and shared IRs (UNCOL)	engineering cost \(m + n\) translators vs \(m \cdot n\)	—	IR must express every source and target concept	\(m, n\)
LLVM's three-phase design	\(O(\text{passes} \times s)\) + back end; instruction selection by DAG pattern matching is linear per basic block for tree patterns	llc -O2 compiles sumloop.ll in milliseconds	IR in memory + machine IR	\(s\)
GCC's GENERIC, GIMPLE and RTL	three lowerings, each \(O(s)\); 364 passes at -O2 in gcc 13.3	comparable to LLVM	three representations over a compile	\(s\)
Cranelift	lowering \(O(s \cdot r)\) worst (try rules), \(O(s)\) with ISLE's compiled decision trees	built for JIT and Wasm runtimes, where compile time is paid at run time: fewer, cheaper passes than LLVM	CLIF + VCode	\(s, r\)

Proposition 0.4.11 (Linear-time lowering with compiled matchers)

If ISLE compiles the rules into a decision tree that inspects a bounded number of operand definitions per instruction, Algorithm 0.4.7 runs in \(O(s)\) time.

Proof

Each CLIF instruction is examined once in the backward sweep; matching follows one path of the decision tree, whose depth is bounded by the largest pattern (a constant for a fixed rule set); each rule emits a bounded number of machine instructions. Summing over \(s\) instructions gives \(O(s)\).

Pathological inputs. (1) Shared IR: a source concept the IR cannot express (exact exception semantics of one language, GPU address spaces before LLVM had them) forces either IR extensions or a lossy encoding — UNCOL's historical failure mode, and MLIR's motivation (Lesson 0.1). (2) Lowering: a pattern set with overlapping low-priority rules degrades to trying many rules per instruction when not compiled into a decision tree. (3) Retargeting C: IR produced for one data layout and compiled for another (the box above) is wrong without any error.

At scale. Adding a target to LLVM means writing a back end (tens of thousands of lines, mostly TableGen), after which every one of LLVM's front ends reaches it; adding a language means writing a front end, after which all 48 targets are reachable (Theorem 0.4.2 in practice).

6. Variants and refinements

The m × n problem and shared IRs (UNCOL)

• Portable virtual machines (JVM bytecode, WebAssembly, .NET CIL) — a shared IR that is also a distribution format with a fixed semantics independent of the target; trade-off: the IR must be target-neutral by design, sacrificing some low-level control.
• Multi-level IRs (MLIR, Lesson 0.1) — many IRs in one framework so that no single one must express everything.

LLVM's three-phase design

• GlobalISel vs SelectionDAG — two instruction-selection frameworks inside LLVM's back ends; GlobalISel works on whole functions in machine IR, SelectionDAG on per-block DAGs (Ch 21).
• Bitcode as a distribution format — Apple's bitcode (now deprecated) and PNaCl tried to ship LLVM IR; Definition 0.4.3 explains why that is fragile.

GCC's GENERIC, GIMPLE and RTL

• LTO in GCC streams GIMPLE into object files (.gnu.lto_* sections), so the whole-program optimizer sees all units.
• libgccjit — GCC as a JIT/AOT library for other front ends (used by rustc_codegen_gcc); trade-off: a C API over GCC's internals.

Cranelift

• E-graph mid-end (aegraph) — rewrites represented in an e-graph so optimizations do not interfere through ordering (cranelift/codegen/src/egraph.rs, EgraphPass); trade-off: extraction cost.
• rustc_codegen_cranelift — Cranelift as a faster debug back end for Rust; trade-off: less optimized code.

7. In real compilers

The m × n problem and shared IRs (UNCOL)

• pebblec — docs/architecture.md and docs/pir/pir-spec.md: PIR is Pebble's shared IR between any front end (in-process C++ or an external executable printing PIR) and the shared PIR→LLVM lowering.
• LLVM — the same argument one level down: LLVM IR between clang/rustc/swiftc/flang/pebblec and 48 back ends.

Pebble's shared IR in action: PIR → LLVM IR → executable

Reproduce (course repository, pebblec and pir-run from a build with -DPEBBLE_USE_SOLUTION=all; LLVM 23.1.2):

cat > sum.pir <<'EOF'
pir 1.0
source "sum.pbl"

extern fn @pebble_print_int(i64)
extern fn @pebble_print_newline()

fn @sum(_0: i64 "n") -> i64 {
  let _1: i64 "s"
  let _2: i64 "i"
  let _3: bool
bb0:
  _1 = 0
  _2 = 0
  goto bb1
bb1:
  _3 = slt _2, _0
  br _3, bb2, bb3
bb2:
  _1 = add _1, _2
  _2 = add _2, 1
  goto bb1
bb3:
  return _1
}

fn @main() -> i64 {
  let _0: i64
bb0:
  _0 = call @sum(10)
  call @pebble_print_int(_0)
  call @pebble_print_newline()
  return 0
}
EOF
pir-run sum.pir
pebblec sum.pir --emit=llvm -O2 -o - | sed -n '/define/,$p'
pebblec sum.pir -O2 -o sum-pebble && ./sum-pebble

Output (complete):

45
define noundef i64 @pebble_main() local_unnamed_addr {
entry:
  tail call void @pebble_print_int(i64 45)
  tail call void @pebble_print_newline()
  ret i64 0
}
45

What to notice: the PIR could have come from any front end in any language (Lesson 0.1's tour). pir-run interprets it (Lesson 0.2's tree-walking idea on a CFG); pebblec lowers it to LLVM IR, where -O2 inlines sum and folds the loop to the constant 45, and LLVM's back end for the host produces the executable.

LLVM's three-phase design

LLVM

llvm/include/llvm/MC/TargetRegistry.h — TargetRegistry::lookupTarget (Algorithm 0.4.4's registry); llvm/tools/llc/llc.cpp drives it; llvm/lib/CodeGen/TargetPassConfig.cpp — TargetPassConfig::addMachinePasses assembles the back-end pipeline (LLVM 23.1.2) [LLVM-TargetRegistry, LLVM-CodeGen].

Find where LLVM does it. Open llvm/include/llvm/MC/TargetRegistry.h at llvmorg-23.1.2. Question: which static member function of TargetRegistry maps a target triple to a Target *? (quiz llvm-where-lookup-target)

GCC's GENERIC, GIMPLE and RTL

• GCC gcc/passes.def — pass_build_ssa_passes, pass_expand (the GIMPLE→RTL boundary) (GCC 15) [GCC-Passes]; gcc/config/i386/i386.md — the x86 machine description whose add patterns produce the (clobber (reg:CC 17 flags)) seen above [GCC-i386md].

Cranelift

• Cranelift cranelift/codegen/src/isa/x64/lower.isle — rules such as iadd_base_case_32_or_64_lea; cranelift/codegen/src/machinst/lower.rs drives lowering; cranelift/docs/ir.md specifies CLIF (Wasmtime v37.0.2) [CL-Src, CL-Docs].
• Wasmtime — compiles every Wasm function with Cranelift (the box above). Cranelift has four back ends: x86-64, aarch64, s390x and riscv64 (cranelift/README.md).

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
The m × n problem and shared IRs (UNCOL)	limited by what the IR can express	\(m + n\) translators instead of \(m \cdot n\)	as good as the IR's semantics is precise	one IR design + \(m + n\) translators	every retargetable compiler; PIR in this course
LLVM's three-phase design	rich SSA IR, ~120 -O2 passes, 48 targets	minutes-scale AOT builds · -O0 for fast compiles	excellent code; IR verifier catches broken passes	front end only, for a new language	Clang, rustc, swiftc, Flang, pebblec
GCC's GENERIC, GIMPLE and RTL	three IRs; RTL is very close to the machine	comparable to LLVM; 364 passes at -O2 (gcc 13.3)	excellent code	high (GCC internals, machine descriptions)	GCC's C/C++/Fortran/Ada/Go front ends
Cranelift	fewer optimizations; verified lowering rules	fast compilation by design (JIT/AOT for Wasm)	good, not best, code	moderate (Rust, ISLE DSL)	Wasmtime, rustc debug builds

Choose a shared IR always, once you have more than two languages or targets. Choose LLVM when you want the best code and the most targets for a new language (Pebble's choice). Choose GCC when you need its targets or its front ends (Ada, some embedded targets). Choose Cranelift when compile speed and a memory-safe, verifiable code generator matter more than peak performance: Wasm runtimes and debug builds.

9. Assessment

Technique	Quiz ids (solutions/quizzes/ch00.yaml)	Drill	Flashcard tag	Exercises
The m × n problem and shared IRs (UNCOL)	m-times-n, ir-target-dependent	— (the counting is closed-form; the quiz computes instances)	retargeting	—
LLVM's three-phase design	llvm-where-lookup-target, three-phase-roles	./course drill phases (back-end vs middle-end items)	llvm-three-phase	E1
GCC's GENERIC, GIMPLE and RTL	gcc-irs-order, gimple-three-address	— (GIMPLE is three-address code: ./course drill stack-code --difficulty medium counts its instructions)	gcc	—
Cranelift	cranelift-block-params, cranelift-isle	— (no randomized instance; the quiz reads CLIF)	cranelift	—

Pitfall

LLVM IR is target-independent in form but not in meaning: clang bakes the ABI, type sizes and target features into it. To compile C for another machine, rerun clang with --target=; do not feed one machine's .ll to another machine's llc.

References

See the chapter references.