Intermediate Representations

Imagine you want to build a compiler ecosystem supporting M source languages and N target architectures. Without an IR, you need M × N separate compilers — each one a complete, custom translation from one specific language to one specific machine. Add a new language? Write N new compilers. Add a new CPU? Write M new back ends. This is the combinatorial explosion that IRs solve.

With an IR, you write M front ends (each translating one source language to IR) and N back ends (each translating IR to one machine). Now adding a language means one front end, and adding a CPU means one back end. The total work is M + N instead of M × N. This is the reusability argument.

But IRs are not only about reuse. They also make analysis and optimization far easier. Source languages carry a huge amount of complexity — syntactic sugar, complex scoping rules, overloaded operators, implicit conversions. Machine code carries a different kind of complexity — register allocation, instruction selection, pipeline constraints. Optimizations like constant folding, dead code elimination, and loop transformation are much cleaner to implement when the program is expressed in a simple, uniform IR that strips away both kinds of incidental complexity.

Finally, IRs serve as a specification: they define precisely what a program means, separate from both the source syntax and the machine encoding. A well-designed IR is a contract between the front end and the back end. The LLVM IR, for instance, has a precise reference semantics — the optimizer is allowed to transform IR in any way that preserves the defined behavior, and undefined behavior in the IR is exactly the space the optimizer exploits for aggressive transformations.

# A compiler with IR: M front ends + N back ends
# Without IR: M × N translators

Source Languages:  C, Rust, Swift, Kotlin, Julia, Haskell  (M = 6)
Target Machines:   x86-64, ARM64, RISC-V, WebAssembly      (N = 4)

Without IR: 6 × 4 = 24 separate compiler pipelines
With IR:    6 + 4 = 10 components (front ends + back ends)

# Compilation pipeline with IR:
Source Code
   --> [Front End]   (parsing, type checking, semantic analysis)
   --> IR
   --> [Middle End]  (machine-independent optimizations on IR)
   --> IR (optimized)
   --> [Back End]    (instruction selection, register allocation, code gen)
   --> Machine Code

Three-address code (TAC) is the most widely used IR family. The key insight is simple: every instruction has at most three operands — at most two sources and one destination. This restriction forces complex expressions to be broken into a sequence of primitive steps, making the computation graph explicit.

Formally, a TAC instruction has one of these forms:

• x = y op z (binary operation)
• x = op y (unary operation)
• x = y (copy)
• goto L (unconditional branch)
• if x goto L (conditional branch)
• x = y[i] / y[i] = x (array access)
• call f, n / x = call f, n (function call)
• return x

Where x, y, z are either temporaries (compiler-generated variables) or program variables, and op is a primitive operation like +, *, <, etc.

Consider the expression a = b * c + d * e. In source code, this is a single statement. In TAC:

t1 = b * c
t2 = d * e
a  = t1 + t2

Now every operation is explicit and isolated. Each temporary t1, t2 is used exactly as needed. This makes it easy to identify available expressions, find dead code, and reason about data flow.

TAC is often implemented as a list of quadruples (op, arg1, arg2, result) or triples (op, arg1, arg2) where the result is identified by position. Quadruples are more common because they allow easy reordering of instructions.

The key property of TAC for analysis is that the def-use structure is explicit: for each temporary, you can immediately see where it is defined (assigned) and where it is used. This powers data-flow analysis.

// Source: x = (a + b) * (a + b) - c

// Three-Address Code (quadruples):
// (op,    arg1, arg2, result)
   ('+',   a,    b,    t1)    // t1 = a + b
   ('+',   a,    b,    t2)    // t2 = a + b  (redundant!)
   ('*',   t1,   t2,   t3)    // t3 = t1 * t2
   ('-',   t3,   c,    x)     // x  = t3 - c

// Common Subexpression Elimination can spot t1 == t2:
// ('+',   a,    b,    t1)    // t1 = a + b
// ('*',   t1,   t1,   t3)    // t3 = t1 * t1  (reuse t1)
// ('-',   t3,   c,    x)     // x  = t3 - c

// Translating an if-else from source:
// if (x > 0) y = 1; else y = -1;

   ('>',   x,    0,    t1)       // t1 = x > 0
   ('if',  t1,   -,    L1)       // if t1 goto L1
   ('=',   -1,   -,    y)        // y = -1
   ('goto',-,    -,    L2)       // goto L2
L1:
   ('=',   1,    -,    y)        // y = 1
L2:                               // continuation

Three-address code gives us an instruction-level view of the program. But many important analyses — like detecting unreachable code, proving loop termination bounds, or understanding what values flow where — require reasoning about the structure of control flow: which instructions can follow which.

A Control-Flow Graph (CFG) organizes TAC into basic blocks connected by directed edges.

A basic block is a maximal sequence of consecutive instructions such that:

1. Control enters only at the first instruction (no jumps into the middle).
2. Control leaves only at the last instruction (no jumps out of the middle).

Basic blocks are the nodes of the CFG. The edges represent possible control flow: there is an edge from block A to block B if execution can pass from A to B (i.e., A ends with a conditional branch to B, or A falls through to B, or A has an unconditional jump to B).

Two special nodes are often added: ENTRY (a virtual predecessor of the first block, with no instructions) and EXIT (a virtual successor of all blocks that can return or terminate).

The CFG is the substrate for data-flow analysis. Classic analyses that operate on CFGs include:

• Reaching Definitions: for each program point, which definitions of each variable might have been the last assignment?
• Live Variables: at each program point, which variables might be read in the future (and thus must not be overwritten carelessly)?
• Available Expressions: which computations have already been performed and whose result hasn't changed (enabling CSE)?
• Dominator analysis: block D dominates block B if every path from ENTRY to B goes through D. Dominators are the foundation of loop detection and SSA construction.

A loop in the CFG is identified by a back edge: an edge whose target dominates its source. The natural loop of a back edge (n → h) is the set of all nodes from which n can be reached going backwards in the CFG without going through h.

// Source code:
int sum = 0;
for (int i = 0; i < n; i++) {
    sum += i;
}
return sum;

// TAC:
//   sum = 0
//   i = 0
// L_cond:
//   t1 = i < n
//   if t1 goto L_body
//   goto L_exit
// L_body:
//   sum = sum + i
//   i = i + 1
//   goto L_cond
// L_exit:
//   return sum

// CFG basic blocks:
// B0 [ENTRY]: sum=0; i=0  -->  B1
// B1 [COND]:  t1=i<n; if t1 goto B2 else B3
//     --> B2 (true edge), B3 (false edge)
// B2 [BODY]:  sum=sum+i; i=i+1; goto B1
//     --> B1 (back edge — creates the loop!)
// B3 [EXIT]:  return sum

// Back edge: B2 -> B1  (B1 dominates B2, creating a natural loop)
// Natural loop: {B1, B2}  (B0 excluded because it's the pre-header)

Dominators are one of the most powerful concepts in compiler analysis. They encode a fundamental structural fact about the CFG: which blocks are necessarily executed before a given block.

Definition: Node D dominates node N (written D dom N) if every path from ENTRY to N passes through D. Every node dominates itself.

The immediate dominator of N, written idom(N), is the unique dominator of N that is dominated by all other dominators of N (the closest dominator). ENTRY has no immediate dominator.

The immediate dominator relationship forms a tree called the dominator tree. In this tree:

• The root is ENTRY.
• The parent of any node N is idom(N).
• N's ancestors are exactly its dominators.

Why do dominators matter?

1. Loop detection: A back edge n → h means h dominates n. The natural loop is the set of nodes that can reach n without going through h.
2. SSA construction: The concept of dominance frontier is the key to inserting φ-functions correctly (more on this shortly).
3. Code motion: Moving a computation out of a loop is safe only if the computation dominates all uses inside the loop.

Dominance Frontier: The dominance frontier of a node N, DF(N), is the set of nodes Y such that N dominates a predecessor of Y but N does not strictly dominate Y. Intuitively, DF(N) is the set of nodes 'just beyond the reach' of N's domination. This is exactly where φ-functions must be inserted when building SSA.

// Computing dominators (simple iterative algorithm)
// dom[n] = set of nodes that dominate n

function compute_dominators(cfg):
    dom[entry] = {entry}
    for each node n != entry:
        dom[n] = all_nodes   // start pessimistic
    
    changed = true
    while changed:
        changed = false
        for each node n != entry (in RPO):
            new_dom = {n} union (intersection of dom[p] for p in preds(n))
            if new_dom != dom[n]:
                dom[n] = new_dom
                changed = true

// Dominance frontier of node n:
function dominance_frontier(n):
    DF = {}
    for each node y in cfg:
        for each predecessor p of y:
            if n dominates p and n does not strictly dominate y:
                DF.add(y)
    return DF

// Example CFG: ENTRY -> B1 -> B2 -> B4
//                          \-> B3 -> B4
//              B4 -> EXIT
// idom(B4) = B1  (B1 dom B4, B2 and B3 don't dom B4)
// DF(B2) = {B4}  (B2 dom pred B2 of B4, but B2 !dom B4)

SSA is the single most important IR invariant in modern optimizing compilers. The SSA property is beautifully simple:

Every variable is defined (assigned) exactly once in the program text.

In ordinary TAC, a variable like x might be assigned in many places — inside loops, in different branches, at the top of a function. This makes analysis hard: when you see a use of x, you don't know which of the many definitions reaches it. Data-flow analysis must work hard to compute this 'reaching definitions' information.

In SSA form, this ambiguity is eliminated by renaming. Each original variable x becomes a family of new variables x₀, x₁, x₂, ..., one for each definition site. Now every use of x₂ unambiguously refers to the definition at x₂ = ....

But there's a problem: what happens when control flow merges? If x₁ is defined in the true branch of an if-statement and x₂ in the false branch, what name do we use after the merge point?

The answer is the φ-function (phi function). At a merge point (a CFG node with multiple predecessors), we insert:

x₃ = φ(x₁, x₂)

This says: 'x₃ equals x₁ if we came from the true branch, or x₂ if we came from the false branch.' The φ-function is not a real instruction — it is a notational device that the back end later eliminates by inserting copies on the incoming edges.

Why SSA makes optimizations easy:

• Constant propagation: If x₁ = 5, every use of x₁ can be replaced with 5 immediately — no data-flow analysis needed.
• Dead code elimination: If x₁ has no uses (and the defining instruction has no side effects), delete it.
• Value numbering: Two variables with the same definition are provably equal — CSE becomes a hash-table lookup.
• Register allocation: SSA variables have non-overlapping live ranges that correspond cleanly to registers in many cases.

The SSA construction algorithm (Cytron et al. 1991) works in two phases:

1. Φ-placement: For each variable v, insert φ-functions for v at the dominance frontiers of all definition sites of v (iteratively, since a φ-function is itself a definition).
2. Renaming: Walk the dominator tree, maintaining a stack of current version for each variable; rename definitions (push new version) and uses (substitute top-of-stack version).

// Source:
if (flag) {
    x = 1;
} else {
    x = 2;
}
y = x + 3;

// TAC (before SSA):
//   if flag goto L_true
// L_false:
//   x = 2
//   goto L_merge
// L_true:
//   x = 1
// L_merge:
//   y = x + 3

// SSA form (after renaming + phi insertion):
//   if flag goto L_true
// L_false:
//   x2 = 2
//   goto L_merge
// L_true:
//   x1 = 1
// L_merge:
//   x3 = phi(x2, x1)   // x3 = x2 if came from L_false, x1 if from L_true
//   y1 = x3 + 3

// ------- Loop example -------
// Source:
// i = 0;
// while (i < n) { i = i + 1; }

// SSA form:
//   i0 = 0
// L_cond:
//   i2 = phi(i0, i1)   // i2: from before loop OR from loop body
//   t1 = i2 < n
//   if t1 goto L_body
//   goto L_exit
// L_body:
//   i1 = i2 + 1
//   goto L_cond
// L_exit: ...

The real payoff of SSA is how dramatically it simplifies classical optimizations. Let us walk through several:

Sparse Conditional Constant Propagation (SCCP): In SSA, each variable has exactly one definition. Start by assuming all variables are 'unknown'. When you see x = 5, mark x as the constant 5. When you see y = x + 3 and x is the constant 5, mark y as 8. When you see phi(c1, c2) and both operands are the same constant c, the phi result is c. Propagate these facts through the use-def chain (which is trivial in SSA: just follow edges from definitions to uses). Branches over constants become dead branches; entire CFG regions can be eliminated. This algorithm runs in O(n) time in SSA — it would require iterative data-flow analysis over a CFG without SSA.

Global Value Numbering (GVN): Assign each SSA value a 'value number' based on how it is computed. Two values with identical value numbers are provably equal. t1 = a + b and t2 = a + b get the same value number; replace all uses of t2 with t1. In SSA, since each variable is defined once, value numbers can be computed in a single dominator-tree traversal.

Dead Code Elimination (DCE): Start from the set of values that have 'side effects' or are used in outputs. Any SSA value not reachable (via use-def chains) from this root set is dead and can be deleted. Because each SSA value has exactly one definition, deletion is unambiguous.

Loop-Invariant Code Motion (LICM): An expression inside a loop is loop-invariant if all its operands are defined outside the loop. In SSA, this is easy to check: operands defined outside the loop have definition sites that dominate the loop header but are not inside the loop. Hoist the computation to the loop pre-header.

All of these optimizations become clean, sparse graph algorithms on the SSA def-use graph, rather than iterative fixed-point computations over bit vectors.

// SSA enables sparse constant propagation:

// Before SCCP:
// x1 = 5
// y1 = x1 + 3       // x1 is const 5 -> y1 = 8
// if (y1 > 0) goto L1 else L2  // 8 > 0 is always true -> branch L2 dead
// L1: z1 = y1 * 2   // z1 = 16
// ...

// SCCP propagates: x1=5, y1=8, branch always taken to L1, z1=16
// After DCE: entire L2 block eliminated.

// GVN eliminates redundant computation:
// a1 = load(p)         // value# 1
// b1 = a1 + 1          // value# 2 = ADD(1, const 1)
// ... some code not touching p ...
// a2 = load(p)         // value# 1 again (same address, no intervening store)
// b2 = a2 + 1          // value# 2 again -> b2 = b1 (replace use)
// use(b2)              // -> use(b1)

// LICM example in SSA:
// n is defined before loop -> n1 = ...
// i2 = phi(i0, i1)       <- loop header
// t1 = n1 * 4            <- loop-invariant! n1 defined outside loop
// t2 = i2 + t1
// ... loop body ...
// i1 = i2 + 1

// After LICM:
// t1 = n1 * 4            <- hoisted to pre-header
// i2 = phi(i0, i1)       <- loop header
// t2 = i2 + t1           <- t1 now pre-computed

LLVM IR is the most widely-used industrial IR, serving as the backend for Clang (C/C++/ObjC), Rust, Swift, Julia, Kotlin/Native, and dozens of other languages. Understanding it concretely anchors the abstract concepts above.

LLVM IR exists in three equivalent forms:

• Human-readable text (.ll files): What we will study.
• Bitcode (.bc files): Compact binary, used for link-time optimization.
• In-memory data structures: Used by the LLVM API.

Key LLVM IR features:

1. Typed: Every value has a type. Primitive types: i1, i8, i32, i64, float, double. Derived: pointers (ptr), arrays ([10 x i32]), structs ({i32, float}), functions.

2. SSA: Every value is assigned exactly once using %name = ... syntax. Temporaries are either named (%x) or numbered (%1).

3. Explicit control flow: Functions are composed of basic blocks, each with a label and ending with a terminator instruction: ret, br, switch, invoke. This directly mirrors the CFG.

4. φ-nodes: Written %x = phi i32 [ %val1, %bb1 ], [ %val2, %bb2 ].

5. Memory model: Unlike pure SSA, memory is mutable. Local variables start as alloca (stack allocation), accessed via load/store. The mem2reg pass promotes alloca/load/store patterns to SSA values.

6. Undefined behavior is explicit: nsw (no signed wrap), nuw (no unsigned wrap) flags on arithmetic instructions tell the optimizer 'this operation cannot overflow — you can assume it doesn't.'

7. Infinite virtual registers: The register file is unlimited; the back end's register allocator maps these to physical registers.

You can produce LLVM IR yourself: clang -S -emit-llvm -O0 foo.c -o foo.ll, and examine it. With -O2, you will see the optimized IR. The difference is educational.

// Source C:
// int add(int a, int b) { return a + b; }
// int factorial(int n) {
//   if (n <= 1) return 1;
//   return n * factorial(n - 1);
// }

; LLVM IR:
define i32 @add(i32 %a, i32 %b) {
entry:
  %result = add nsw i32 %a, %b
  ret i32 %result
}

define i32 @factorial(i32 %n) {
entry:
  %cmp = icmp sle i32 %n, 1        ; signed less-or-equal
  br i1 %cmp, label %base, label %recurse

base:
  ret i32 1

recurse:
  %n_minus_1 = sub nsw i32 %n, 1
  %rec = call i32 @factorial(i32 %n_minus_1)
  %result = mul nsw i32 %n, %rec
  ret i32 %result
}

; Key observations:
; - Every basic block ends with a terminator (br or ret)
; - Every value assigned exactly once (%cmp, %n_minus_1, etc.)
; - Types are explicit (i32, i1)
; - nsw flag: optimizer can assume no signed overflow

; A phi-node example (iterative factorial in SSA):
; define i32 @fact_iter(i32 %n) {
; entry:
;   br label %loop
; loop:
;   %i   = phi i32 [ %n,  %entry ], [ %i_next,  %loop ]
;   %acc = phi i32 [ 1,   %entry ], [ %acc_next, %loop ]
;   %cmp = icmp sgt i32 %i, 1
;   br i1 %cmp, label %loop_body, label %done
; loop_body:
;   %acc_next = mul nsw i32 %acc, %i
;   %i_next   = sub nsw i32 %i, 1
;   br label %loop
; done:
;   ret i32 %acc
; }

A subtle but important practical question: how do compilers initially generate SSA? For simple cases, the front end can directly emit SSA. But for general programs with mutable local variables, there's a chicken-and-egg problem: the front end needs to know which version of a variable is live, but that's exactly what SSA is trying to encode.

LLVM's elegant solution is the alloca idiom: the front end unconditionally generates non-SSA code using explicit memory:

• Every mutable local variable x is allocated on the stack: %x.addr = alloca i32
• Every write to x becomes a store i32 %val, ptr %x.addr
• Every read from x becomes %val = load i32, ptr %x.addr

This is correct (all the right values are stored and loaded) but very slow — every variable access goes through memory. The mem2reg pass (short for 'memory to registers') then promotes these alloca patterns to SSA form, inserting φ-functions precisely where needed (using the dominance frontier algorithm). This pass is almost always the first optimization run.

Why is this design elegant? Because it decouples two hard problems: (1) the front end only needs to emit correct code, without worrying about SSA construction; (2) the optimizer handles the SSA promotion. The front end is simpler, and mem2reg is a well-tested, reusable component.

After mem2reg, the IR is in full SSA form and ready for the heavy optimization passes: SCCP, GVN, LICM, inlining, loop transformations, etc. This is why, in practice, LLVM IR at -O0 looks quite different from IR at -O2: the optimization passes have radically transformed the structure.

// clang generates at -O0 (before mem2reg):
// Source: int x = 5; x = x + 1; return x;

define i32 @f() {
entry:
  %x = alloca i32, align 4        ; stack slot for x
  store i32 5, ptr %x, align 4    ; x = 5
  %0 = load i32, ptr %x, align 4  ; read x
  %add = add nsw i32 %0, 1        ; x + 1
  store i32 %add, ptr %x, align 4 ; x = x + 1
  %1 = load i32, ptr %x, align 4  ; read x for return
  ret i32 %1
}

// After mem2reg (this is what -O1 and above produce):
define i32 @f() {
entry:
  %add = add nsw i32 5, 1   ; constant folded: 5 + 1 = 6
  ret i32 %add              ; (or just ret i32 6 after constant prop)
}
// The alloca is gone. x is now a pure SSA value.
// mem2reg + constant folding reduced the entire function to one instruction.

After all machine-independent optimizations are applied, the IR must be lowered to actual machine instructions. Lowering is the process of progressively closing the gap between the abstract IR and the concrete ISA. It is not one step but a sequence of transformations.

Instruction Selection: Map IR instructions to target machine instructions. This is not trivial because a single IR instruction might map to multiple machine instructions (e.g., div on x86 requires cdq to sign-extend and idiv to divide) or multiple IR instructions might map to a single machine instruction (e.g., a multiply-accumulate). The most principled approach is tree pattern matching: represent the IR as an expression tree and use dynamic programming to tile it with instruction patterns that have costs (latency, code size). LLVM uses a DAG-based instruction selection on a SelectionDAG representation.

Register Allocation: IR has an infinite supply of virtual registers. Real machines have a small, fixed set. Register allocation must assign virtual registers to physical ones, inserting spill code (store to stack, reload from stack) when there are not enough registers. The canonical formulation is graph coloring: build an interference graph where nodes are virtual registers and edges connect registers that are live at the same time (cannot share a physical register). Coloring this graph with k colors (k = number of registers) gives a valid allocation. This problem is NP-complete in general, but practical heuristics (Chaitin-Briggs, PBQP in LLVM) work well.

Instruction Scheduling: Modern CPUs execute multiple instructions in parallel (out-of-order execution, pipelining). The compiler can help by reordering instructions to expose parallelism and avoid hazards (e.g., a load result should not be used in the immediately following instruction if the CPU stalls on memory latency). Scheduling is also a graph problem on the data-dependence graph of instructions.

Peephole Optimization: A final pass examines small windows of instructions and applies local rewrites: replacing add reg, 0 with nothing, replacing mov reg, reg with nothing, etc.

LLVM implements all of this in its back end, with separate implementations per target architecture (x86, ARM, RISC-V, etc.). Each target provides instruction definitions in TableGen (.td files) that specify operands, encoding, latency, and pattern-matching rules.

// Lowering pipeline illustrated for: int f(int a, int b) { return a * b + a; }

// === LLVM IR (after optimization) ===
define i32 @f(i32 %a, i32 %b) {
  %mul = mul nsw i32 %a, %b
  %add = add nsw i32 %mul, %a
  ret i32 %add
}

// === After Instruction Selection (x86-64 MachineIR, pre-regalloc) ===
// (virtual registers: %vreg0=%a, %vreg1=%b)
//   IMUL32rr %vreg2, %vreg0, %vreg1   ; vreg2 = vreg0 * vreg1
//   ADD32rr  %vreg3, %vreg2, %vreg0   ; vreg3 = vreg2 + vreg0
//   MOV32rr  EAX, %vreg3              ; return value in EAX
//   RET

// === After Register Allocation (physical registers assigned) ===
//   IMUL32rr EDX, EDI, ESI   ; EDX = EDI * ESI  (a in EDI, b in ESI per ABI)
//   ADD32rr  EAX, EDX, EDI   ; EAX = EDX + EDI
//   RET

// === Final x86-64 Assembly ===
//   imul  edx, edi, esi
//   lea   eax, [rdx + rdi]   ; compiler may use LEA instead of ADD
//   ret
// (The compiler may even use: imul edi, esi; lea eax, [rdi + rdi*?] ...)
// The exact output depends on the instruction selector's cost model.

A single IR cannot be simultaneously high-level enough to preserve source language semantics and low-level enough to map cleanly to machine instructions. The solution, increasingly adopted in modern compiler infrastructure, is multi-level IR: a hierarchy of IRs, with progressive lowering from one level to the next.

LLVM itself has multiple levels:

• LLVM IR (machine-independent, SSA)
• SelectionDAG (type-lowered, target-specific nodes)
• MachineIR (machine instructions, virtual registers)
• MCInst (encoded machine instructions)

MLIR (Multi-Level Intermediate Representation), developed at Google and now part of the LLVM project, generalizes this idea dramatically. MLIR is a framework for building custom IRs, called dialects, each of which captures the semantics of a specific domain or abstraction level. Dialects can coexist in the same module, and lowering passes progressively convert from higher dialects to lower ones.

Example MLIR dialects:

• arith: arithmetic operations (portable, abstract)
• linalg: linear algebra operations (matrix multiply, convolution)
• vector: SIMD-style vector operations
• affine: affine loop nests (enabling polyhedral optimization)
• llvm: LLVM IR concepts (lowest level, maps to LLVM IR)

This is particularly important for ML compilers: a convolution operation in linalg can be lowered to vector (vectorized loops) and then to llvm for final code generation — with different optimization passes applied at each level, exploiting the semantic information available at each abstraction.

The key insight is that abstraction levels should be first-class citizens of the compiler infrastructure, not just an informal pipeline. MLIR makes the levels explicit and provides a common infrastructure (parsing, printing, verification, pass management) for all of them.

// MLIR example: a simple matrix multiplication in linalg dialect
// This is real MLIR syntax

func.func @matmul(%A: memref<4x4xf32>,
                  %B: memref<4x4xf32>,
                  %C: memref<4x4xf32>) {
  // High-level: linalg.matmul captures the semantic intent
  linalg.matmul ins(%A, %B : memref<4x4xf32>, memref<4x4xf32>)
                outs(%C : memref<4x4xf32>)
  return
}

// After lowering to affine loops:
// affine.for %i = 0 to 4 {
//   affine.for %j = 0 to 4 {
//     affine.for %k = 0 to 4 {
//       %a = affine.load %A[%i, %k]
//       %b = affine.load %B[%k, %j]
//       %c = affine.load %C[%i, %j]
//       %prod = arith.mulf %a, %b
//       %sum  = arith.addf %c, %prod
//       affine.store %sum, %C[%i, %j]
//     }
//   }
// }

// Then affine -> vector (vectorize inner loop)
// Then vector -> llvm (map to LLVM IR intrinsics)
// Then llvm -> machine code (standard LLVM back end)

// Each level enables different optimizations:
// linalg level: tiling, fusion, interchange
// affine level: dependence analysis, loop transformations
// vector level: SLP vectorization, unrolling
// llvm level: instruction selection, register allocation