Code Generation & Register Allocation

After the front-end parses source code and the middle-end optimizes it, the back-end translates the IR into target-specific machine code. The canonical three-phase back-end is:

1. Instruction Selection — map IR operations to target instructions
2. Register Allocation — assign virtual registers to physical registers (or memory)
3. Code Emission — emit actual assembly or binary encoding

These phases are not fully independent: instruction selection choices affect register pressure, which affects allocation quality, which can force re-selection. Production compilers (LLVM, GCC) iterate and interact these phases. But the conceptual separation is clean and pedagogically essential.

The IR entering the back-end is typically in Static Single Assignment (SSA) form: every variable is defined exactly once, and phi-nodes merge values at join points. SSA makes liveness analysis and interference computation particularly elegant. When we exit SSA (to emit real code), we must insert copy instructions or use parallel copy semantics to implement phi-nodes — this is called SSA deconstruction.

Why not compile directly from AST to assembly? Because the AST is too high-level (expressions nested arbitrarily) and the gap to assembly is too large. The IR — a flat sequence of simple three-address operations like t3 = t1 + t2 — is the right granularity: low enough to see register pressure, high enough to do machine-independent optimization.

; LLVM IR (simplified) for: return a*b + c
define i32 @f(i32 %a, i32 %b, i32 %c) {
  %t1 = mul i32 %a, %b   ; virtual reg t1 = a * b
  %t2 = add i32 %t1, %c  ; virtual reg t2 = t1 + c
  ret i32 %t2
}

Instruction selection asks: given an IR operation (or tree of operations), which machine instruction(s) implement it? Modern ISAs have complex addressing modes and multi-operation instructions (e.g., x86's lea rax, [rax + 4*rbx + 8] can add, scale, and offset in one instruction), so naive one-to-one mapping wastes performance.

Tree pattern matching / tree tiling is the dominant approach, pioneered by Aho, Ganapathi, and Tjiang (1989) and formalized as BURS (Bottom-Up Rewrite Systems). The idea:

• Represent each IR computation as an expression tree (leaves are registers/constants, internal nodes are operations).
• Each machine instruction corresponds to a tile — a pattern that matches a subtree and replaces it with a single result register.
• Instruction selection = tiling the tree with non-overlapping tiles that cover every node.
• Optimal tiling (minimum cost) can be solved in O(n) by dynamic programming over the tree using Aho-Corasick style matching.

Maximal Munch: a greedy heuristic — at each node, choose the largest (most instructions absorbed) tile that matches. Not always optimal, but fast and usually within a few percent.

Why does this matter? Consider x = a[i*4] on x86. A naive compiler emits: shl ecx, 2; add ecx, eax; mov eax, [ecx]. A tile-aware compiler emits: mov eax, [eax + 4*ecx] — one instruction instead of three.

For RISC architectures (ARM, RISC-V), tiles are smaller (the ISA is simpler), but peephole patterns still matter. For CISC (x86), the tiling problem is richer and the gains larger.

# Expression tree for: a + b*4
#      ADD
#     /   \
#    a    MUL
#         / \
#        b   4
#
# Tile options on x86:
#   Tile 1: [ADD node + MUL(x, const)] → lea rax, [a + 4*b]   (cost 1)
#   Tile 2: MUL(b,4) → shl rbx, 2;  then ADD → add rax, rbx  (cost 2)
#
# BURS dynamic programming:
#   cost(leaf b)    = 0
#   cost(leaf 4)    = 0
#   cost(MUL(b,4))  = min(shl: 1, imul: 1) = 1
#   cost(ADD(a, MUL(b,4))) = min(
#       lea [a+4*b]: 1,           # single tile covers full tree
#       add(a) + cost(MUL): 2    # two tiles
#   ) = 1   → choose lea

Register allocation needs to know, at every program point, which values are live — meaning they will be used in the future and therefore must be kept in a register (or memory). This is liveness analysis, a classic backward dataflow analysis.

Definitions:

• A variable v is live at point p if there exists a path from p to a use of v that does not pass through a definition of v.
• LiveIn[B] = the set of variables live at the start of basic block B.
• LiveOut[B] = the set of variables live at the end of B.

Dataflow equations (backwards):

LiveOut[B] = ∪ { LiveIn[S] : S is a successor of B }
LiveIn[B]  = Use[B] ∪ (LiveOut[B] \ Def[B])

where Use[B] = variables used in B before any definition, Def[B] = variables defined in B.

Algorithm: initialize all sets to empty, then iterate until a fixed point. Convergence is guaranteed because sets only grow (monotone) and are bounded.

Live range: the set of program points where a variable is live. Two variables interfere if their live ranges overlap — they cannot share a physical register. This interference relationship is the key input to register allocation.

SSA simplification: In SSA form, each variable has exactly one definition, and live ranges are simpler to compute. Moreover, the interference graph of an SSA program is always a chordal graph, a fact that enables optimal coloring in polynomial time (Hack, Goos, Hack 2006). Production compilers exploit this.

# Three-address code, liveness computed backward:
#
# B1: a = 1          Def: {a}      Use: {}
#     b = 2          Def: {b}      Use: {}
#     c = a + b      Def: {c}      Use: {a,b}
#     d = c * 2      Def: {d}      Use: {c}
#     return d       Use: {d}
#
# Work backward from 'return d':
#   after  return d:   Live = {}
#   before return d:   Live = {d}
#   before d = c*2:    Live = {c}         (d killed, c needed)
#   before c = a+b:    Live = {a, b}      (c killed, a,b needed)
#   before b = 2:      Live = {a}         (b killed)
#   before a = 1:      Live = {}          (a killed)
#
# Live ranges: a=[line1..line3], b=[line2..line3], c=[line3..line4], d=[line4..line5]
# Interferences: a∩b (both live at line 3 start) → a and b interfere

The interference graph (also called the register conflict graph) is the central data structure for register allocation. It encodes which pairs of virtual registers cannot share a physical register.

Construction:

• Each virtual register is a node.
• Add an edge (u, v) if u and v are simultaneously live at any program point — i.e., if their live ranges overlap.
• For a definition d = ..., the defined variable d interferes with everything live at that point (since it is now live).

Special case — move instructions: If v1 = v2 (a copy), then v1 and v2 are related but do not necessarily interfere (v2's range ends at the copy if not used elsewhere). We tag these edges as move-related, and during coloring we try to assign them the same color (coalescing) to eliminate the copy instruction entirely.

Degree of a node = number of interfering neighbors = the number of other registers it conflicts with. High-degree nodes are under register pressure.

Chromatic number: the minimum number of colors needed to color the interference graph = the minimum number of physical registers needed. If the graph's chromatic number exceeds the available registers (k), some values must be spilled to memory.

The interference graph for SSA-form code is always chordal (every cycle of length ≥ 4 has a chord), and chordal graphs have a polynomial-time optimal coloring algorithm (perfect elimination ordering). This is one reason SSA has revolutionized register allocation.

# From the liveness example above:
# Virtual regs: a, b, c, d
# Interference edges:
#   a -- b  (both live at line 3)
#   (c does not overlap a or b: a,b dead before c is born)
#   (d does not overlap c: c dead before d born)
#
# Graph:
#   a --- b    c    d
# (a-b interfere; c,d are isolated; chromatic number = 2)
# 2 physical registers suffice for this code!
#
# Contrast with: t1 = a+b; t2 = c+d; t3 = t1*t2; return t3+e
# Here a,b,c,d,e,t1,t2 all need registers simultaneously → high pressure

Graph coloring register allocation, introduced by Chaitin et al. (1981) at IBM, is the intellectual core of modern register allocation. The insight: allocating k physical registers is equivalent to k-coloring the interference graph — assign a color (register) to each node so no two adjacent nodes share a color.

Chaitin's algorithm (simplified):

1. Build the interference graph from liveness analysis.
2. Simplify: find a node with degree < k (not heavily used). Remove it from the graph onto a stack. Repeat. Such a node can always be colored later, regardless of how its neighbors are colored.
3. Spill: if no node has degree < k, pick a node to spill (heuristic: minimize spill cost = use count / degree). Mark it for spilling, remove it from the graph, continue simplifying.
4. Color: pop nodes from the stack. Assign each node a color not used by its (already-colored) neighbors. If all k colors are taken, this is an actual spill — insert load/store around uses.
5. Repeat if spills were inserted (spilling adds new variables, changing the interference graph).

Why degree < k is the key invariant: a node with fewer than k neighbors can always receive a color — at least one of the k colors will be free among its neighbors. This is the analog of the greedy coloring argument.

Spill cost heuristics are crucial: prefer to spill rarely-used or cheap-to-reload values (constants, function arguments already in memory). Spilling a loop variable is catastrophic; spilling a value used once outside a loop is cheap.

Coloring NP-completeness: graph k-coloring for k ≥ 3 is NP-complete in general. Chaitin proved register allocation is NP-complete. But the interference graphs that arise from real programs are far from worst-case — they are sparse, often chordal (from SSA), and Chaitin's greedy approach works well in practice.

def chaitin_color(graph, k):
    """
    graph: dict {node: set of neighbors}
    k: number of physical registers
    Returns: dict {node: register_number} or marks spills
    """
    stack = []
    spilled = set()
    g = {n: set(nbrs) for n, nbrs in graph.items()}  # mutable copy

    while g:
        # Find a node with degree < k
        low = [n for n in g if len(g[n]) < k]
        if low:
            node = low[0]
        else:
            # Must spill: pick cheapest (heuristic: highest degree here)
            node = max(g, key=lambda n: len(g[n]))
            spilled.add(node)
        # Remove node from graph
        stack.append(node)
        for nbr in g[node]:
            g[nbr].discard(node)
        del g[node]

    # Color in reverse order
    coloring = {}
    for node in reversed(stack):
        if node in spilled:
            coloring[node] = 'SPILL'
            continue
        used = {coloring[nbr] for nbr in graph[node] if nbr in coloring}
        for color in range(k):
            if color not in used:
                coloring[node] = color
                break
        else:
            coloring[node] = 'SPILL'  # actual spill
    return coloring

Real-world register allocators go well beyond basic Chaitin coloring. Three refinements are critical:

1. Coalescing eliminates copy instructions. If v1 = v2 is a copy and v1, v2 do not interfere, we can coalesce them — merge them into a single node in the interference graph, assigned the same register. The copy instruction disappears. But aggressive coalescing can increase the degree of the merged node, potentially causing spills that wouldn't have occurred (conservative coalescing — Briggs et al. 1994 — only coalesces when the result node would have < k high-degree neighbors, preserving colorability). George and Appel (1996) further refined this.

2. Spilling mechanics: When a value is spilled, the compiler:

• Allocates a spill slot on the stack (a word of memory in the stack frame).
• Inserts a store (mov [rbp-offset], reg) after each definition.
• Inserts a load (mov reg, [rbp-offset]) before each use. Spilled values need only a physical register for the instant of use, not for their entire live range. This adds new (short-lived) virtual registers, requiring another iteration of allocation — iterative spilling.

3. Rematerialization: sometimes it is cheaper to recompute a value than to spill and reload it. Classic candidates:

• Integer constants: mov eax, 42 costs less than a load from memory.
• Addresses of static data, function arguments passed by value. The allocator marks such values as rematerializable and, instead of inserting a load on spill, inserts the recomputing instruction. This can dramatically reduce memory traffic in loops.

Modern allocators (LLVM's RegAlloc) combine all three: iterative coloring with conservative coalescing, splitting live ranges (see next concept), and rematerialization.

# Coalescing example:
#   t1 = a + b
#   t2 = t1       <- copy: t2 and t1 don't interfere → merge
#   return t2
# After coalescing: t1 and t2 become one virtual reg → no copy emitted

# Spill example:
# Suppose 'x' is spilled to [rbp-8]:
#   Before:  %x = add %a, %b       (x's live range is long)
#   After:   %x_def = add %a, %b
#            store [rbp-8], %x_def  # spill store
#            ...(x not in register)...
#            %x_use = load [rbp-8]  # spill reload
#            use %x_use

# Rematerialization:
#   %c = 42          <- constant, always rematerializable
#   ... long range ...
#   use %c
# Instead of: load %c_reload, [rbp-8]
# Emit:       mov %c_reload, 42    (one instruction, no memory access)

A live range can sometimes be so long — spanning many basic blocks — that it interferes with many other values, causing spills. Live range splitting breaks a long live range into shorter pieces separated by loads/stores, reducing interference and register pressure.

When to split:

• A value is live across a loop but only used inside a few iterations: split at loop boundary.
• A high-degree node causes many other spills: split it into multiple nodes with fewer interferences.

Splitting in linear scan: The linear scan algorithm (Poletto and Sarkar, 1999), used in early JIT compilers and LLVM's fast regalloc, processes live intervals in order of start point. When registers are full, it either spills the interval with the latest endpoint or splits the current interval. Linear scan is O(n) in practice and suitable for JIT (GraalVM, early V8).

SSA-based splitting: In SSA, inserting a new phi-node effectively splits a live range at a join point. Splitting is clean in SSA because each new piece gets a fresh name.

The fundamental trade-off: more splits → fewer interferences → fewer spills of other values, but more load/store instructions. Good splitting heuristics balance these costs, guided by loop nesting depth (splits outside loops are cheap; splits inside loops are expensive).

Modern compilers like LLVM's greedy register allocator use local region splitting: identify a region (e.g., a loop) where a value causes pressure, split around that region, and re-attempt allocation. This can turn a cascade of spills into a single controlled split.

# Before splitting: x has a live range from line 1 to line 100
# x interferes with 15 other values across a big loop → causes 3 spills
#
# After splitting at loop boundary (lines 40-60):
#   x1: live from 1..39     (outside loop, no pressure)
#   store [rbp-8], x1        # split point: save before loop
#   x2: live from 40..60    (inside loop, short — few interferences)
#   store [rbp-8], x2        # split point: save after loop
#   x3: live from 61..100   (outside loop, no pressure)
#
# Now x1, x2, x3 have shorter live ranges → fewer interferences → no cascade

Every function call needs a chunk of memory to hold its local state: local variables, saved registers, the return address, and space to pass/receive arguments. This is the activation record (also called the stack frame), and they stack up on — you guessed it — the call stack.

On x86-64 (the dominant 64-bit convention), the stack grows downward (toward lower addresses). The stack pointer rsp always points to the top (lowest address) of the current frame. The frame pointer rbp (optional in optimized code) anchors the frame at its base, making local variable addressing stable even as rsp changes.

Canonical x86-64 frame layout (from high to low address):

[caller's frame ...]          <- higher addresses
[argument 7+]                 <- args beyond 6th (caller-allocated)
[return address]              <- pushed by 'call' instruction
[saved rbp]                   <- callee saves rbp (frame pointer)
[saved callee-save regs]      <- rbx, r12-r15 (callee must preserve)
[local variables]             <- compiler-allocated
[red zone (128 bytes)]        <- signal/interrupt scratch (leaf functions)
rsp →                         <- current stack top

Alloca and variable-length arrays force dynamic frame sizes, requiring rbp as a stable reference — one reason -fomit-frame-pointer cannot be used with alloca.

Why compilers care about frames: the size of the frame directly affects cache behavior. A function that uses 10 locals fits its frame in one or two cache lines; one that spills 50 registers thrashes the L1 cache. Minimizing spills is partly about minimizing frame size.

# x86-64 assembly for a simple function prologue/epilogue:
# int sum(int a, int b, int c) { int t = a+b; return t+c; }

sum:
    push   rbp              # save caller's frame pointer
    mov    rbp, rsp         # set our frame pointer
    sub    rsp, 16          # allocate 16 bytes for locals (aligned to 16)

    # args: edi=a, esi=b, edx=c  (System V AMD64 ABI)
    mov    DWORD PTR [rbp-4], edi   # spill a (if needed)
    mov    DWORD PTR [rbp-8], esi   # spill b (if needed)
    mov    DWORD PTR [rbp-12], edx  # spill c (if needed)

    mov    eax, DWORD PTR [rbp-4]   # t = a + b
    add    eax, DWORD PTR [rbp-8]
    mov    DWORD PTR [rbp-4], eax   # store t
    add    eax, DWORD PTR [rbp-12]  # return t + c

    leave                   # mov rsp, rbp; pop rbp
    ret                     # pop return address, jump there

A calling convention is the contract between caller and callee specifying: which registers carry arguments, where the return value goes, which registers the callee must preserve, and how the stack must be aligned. The Application Binary Interface (ABI) is the broader contract including data layout, name mangling, and exception handling.

System V AMD64 ABI (Linux, macOS, BSDs — the dominant 64-bit Unix ABI):

• Integer/pointer arguments: rdi, rsi, rdx, rcx, r8, r9 (first 6); remaining on stack.
• Floating-point arguments: xmm0–xmm7 (first 8 SSE/AVX args).
• Return value: rax (integer/pointer), xmm0 (float), rdx:rax (128-bit).
• Caller-saved (clobbered freely by callee): rax, rcx, rdx, rsi, rdi, r8–r11, xmm0–xmm15.
• Callee-saved (callee must restore): rbx, rbp, r12–r15.
• Stack alignment: rsp must be 16-byte aligned before a call instruction (the call pushes 8 bytes, so at function entry rsp ≡ 8 mod 16; callee aligns to 16 in its prologue).

Microsoft x64 ABI (Windows) differs: first 4 args in rcx, rdx, r8, r9; a 32-byte shadow space must be allocated by the caller above the return address even if not used. This is a common source of bugs in cross-platform assembly.

Why callee-saved registers matter for register allocation: the allocator may choose to use rbx (callee-saved) to hold a long-lived value, but must emit a save/restore pair in the prologue/epilogue. This costs code size and cycles. The allocator weighs using callee-saved vs. caller-saved registers based on how many saves are needed — preferring caller-saved when possible.

Leaf function optimization: functions that call no other functions (leaf functions) need not save any callee-saved registers they don't use, need no frame pointer, and can use the 128-byte red zone below rsp without adjusting the stack pointer at all.

# Illustrating the ABI: caller's view
# C:  long r = foo(1, 2, 3, 4, 5, 6, 7);
# arg 7 goes on the stack; args 1-6 go in registers

mov    edi, 1          # arg 1 → rdi
mov    esi, 2          # arg 2 → rsi  
mov    edx, 3          # arg 3 → rdx
mov    ecx, 4          # arg 4 → rcx
mov    r8d, 5          # arg 5 → r8
mov    r9d, 6          # arg 6 → r9
push   7               # arg 7 → stack (must be 8-byte aligned)
call   foo
add    rsp, 8          # clean up arg 7 from stack
# return value now in rax

SSA form is beautiful for analysis but cannot run directly on real hardware: phi-nodes (%x = phi [%a, pred1], [%b, pred2]) have no hardware equivalent. Before emitting assembly, the compiler must deconstruct SSA — replace phi-nodes with explicit move instructions or parallel copies.

Naive deconstruction: for each phi-node %x = phi [%a, B1], [%b, B2], insert %x = %a at the end of B1 and %x = %b at the end of B2. But inserting sequential copies can introduce lost-copy and swap problems.

Lost-copy problem: if B1 has %y = %x after the inserted copy %x = %a, the intended semantics (copy of the old %x) is lost.

Swap problem: if phi-nodes %a' = phi [%b, B] and %b' = phi [%a, B] both have predecessor B, sequential copies %a' = %b; %b' = %a implement a swap incorrectly — the second copy uses the already-overwritten %a'.

Parallel copy semantics: phi-nodes execute as a simultaneous parallel assignment. The standard solution is:

1. Represent all insertions as a parallel copy (all RHS values are the old values).
2. Serialize the parallel copy using a sequentialization algorithm (handle cycles with a temp register; handle chains in topological order).

This is equivalent to sorting a permutation: most are chains (no temp needed), and cycles require one temp. The algorithm runs in O(n) for n copies.

After SSA deconstruction, the code is in conventional SSA-free form and can be directly register-allocated and emitted.

# SSA phi-nodes:
#   B1 → B3:  %a3 = phi [%a1, B1], [%a2, B2]
#              %b3 = phi [%b1, B1], [%b2, B2]
#
# From B1, parallel copy: { a3 ← a1, b3 ← b1 }  (no interference → chain)
# Serialize: a3 = a1; b3 = b1  (order doesn't matter, no cycle)
#
# Swap case from B:
#   %a' = phi [%b, B]  → a' ← b
#   %b' = phi [%a, B]  → b' ← a
# Parallel copy: { a' ← b, b' ← a }  — CYCLE!
# Serialize with temp:
#   tmp = a
#   a' = b
#   b' = tmp
# (Exactly like swapping two variables)

Let us trace the full back-end journey for a tiny C function: int dot(int a, int b, int c, int d) { return a*c + b*d; }

Step 1 — IR (Three-Address Code):

t1 = a * c
t2 = b * d
t3 = t1 + t2
return t3

Step 2 — Instruction Selection (x86-64, MaxMunch):

• t1 = a*c → imul edi, edx (reuse edi for a, multiply by c in edx)
• t2 = b*d → imul esi, ecx
• t3 = t1+t2 → add edi, esi
• return → mov eax, edi; ret

Step 3 — Liveness:

• After imul edi,edx: live = {t1(edi), b(esi), d(ecx)}
• After imul esi,ecx: live = {t1(edi), t2(esi)}
• After add edi,esi: live = {t3(edi)}

Step 4 — Interference graph:

• t1 and b interfere (both live after first imul)
• t1 and d interfere similarly
• t1 and t2 interfere
• Others don't overlap

Step 5 — Register allocation (k=6 caller-saved registers available):

• All nodes have degree ≤ 2, all < 6 → simplify all without spills.
• Coloring: a→rdi, c→rdx (args), b→rsi, d→rcx (args), t1→rdi (reuse after a freed), t2→rsi, t3→rdi.

Step 6 — Emitted assembly (optimized, no frame pointer for leaf):

dot:
    imul  edi, edx      ; t1 = a*c (a in edi, c in edx)
    imul  esi, ecx      ; t2 = b*d (b in esi, d in ecx)
    add   edi, esi      ; t3 = t1 + t2
    mov   eax, edi      ; return value → eax
    ret

Five instructions, no stack activity, no spills — exactly what a modern compiler (clang -O2) produces.

// Verify in your browser: https://godbolt.org
// Source:
int dot(int a, int b, int c, int d) { return a*c + b*d; }
// Compiler: x86-64 clang -O2
// Output:
// dot(int, int, int, int):
//         imul    edi, edx
//         imul    esi, ecx
//         add     edi, esi
//         mov     eax, edi
//         ret