Code
Generation

The back end is where portability ends and the silicon begins. By the close you will have walked optimised IR all the way to x86-64 and AArch64 assembly, naming every instruction and register chosen.

Optimisation (Part 07) left us with clean, machine-independent IR — unbounded virtual registers, abstract operations, no notion of the target. Code generation lowers this to a concrete instruction stream: real opcodes, real registers, a real stack frame, obeying a real ABI. Three subproblems dominate — and they interact, which is what makes the back end hard.

The ISA dictates everything downstream. A register is a small, fast, named store inside the CPU; an addressing mode is a rule for computing an operand's memory address. The deepest split is RISC vs CISC.

ISA choice reshapes the back end: CISC's memory operands make instruction selection matter more (one instruction can do a load + an add); RISC's load/store regularity makes scheduling and register pressure the main game. A good selector exploits exactly the addressing modes the target offers.

The three ISAs a modern back end is most likely to target. They differ in register count, encoding and addressing — each pushing codegen in a different direction.

Instruction selection maps IR operations to target instructions. It is rarely one-to-one. The mapping is both many-to-one (a multiply-by-4 plus add becomes a single lea) and one-to-many (a 64-bit divide may expand to a sequence). The selector must find a covering of the IR by available instructions — ideally the cheapest one.

mov rax, [rbx + rcx*4]   ; one instr

From dead-simple to provably optimal, selection techniques trade implementation effort against code quality.

Take a[i] = a[i] + 1 where a is a 4-byte array at base rbx and i is in rcx. The address tree MEM(+ (base, * (i, 4))) can be covered by tiles. On x86-64, a single addressing mode swallows the whole sub-tree.

A naive tiler would emit a lea to compute the address, a load, an add and a store. A good selector recognises the whole address sub-tree as one addressing-mode tile — and on x86 may fold the increment into a single memory-destination add.

Real selectors operate on a DAG, not a tree, so common sub-expressions are shared. LLVM has shipped two selectors; the newer one was built to fix the older's weaknesses.

The IR has unbounded virtual registers; the machine has k physical ones (16 on x86-64, 31 on AArch64). Register allocation maps virtual registers onto physical registers, and when there are not enough, spills some values to memory (stack slots).

Build the interference graph: one node per value, an edge between any two that interfere (overlapping live ranges). Assigning registers so that no two interfering values share one is exactly graph k-colouring — colour the nodes with k colours (registers) so no edge joins two same-coloured nodes. Chaitin (1981) made this the standard formulation.

The classic colouring allocator works by graph simplification. The key lemma: a node with fewer than k neighbours (low-degree) can always be coloured after its neighbours, so remove it and recurse.

Two refinements make colouring allocators competitive: removing pointless copies (coalescing) and breaking up troublesome ranges (splitting).

Graph colouring is powerful but slow — building and simplifying the interference graph is super-linear. JITs and -O0 need speed. Linear scan (Poletto & Sarkar, 1999) skips the graph entirely.

A beautiful result reshaped allocation theory: the interference graph of a program in SSA form is chordal — and chordal graphs are colourable in polynomial time.

Modern CPUs are pipelined: an instruction takes several cycles, and the next can start before the previous finishes — unless a hazard stalls it. Scheduling reorders instructions to hide latency and keep functional units busy, without changing the result.

Within a basic block, build the data-dependence DAG: nodes are instructions, edges are dependences (true RAW, plus anti/output and memory ordering), weighted by latency. List scheduling greedily picks, each cycle, a ready instruction (all predecessors done) of highest priority — usually longest path to the end (critical path).

The ABI (Application Binary Interface) is the contract that lets separately-compiled functions interoperate: who passes arguments where, who preserves which registers, how the stack is laid out. The back end must obey it exactly — it constrains the allocator and shapes every call.

Each call gets a stack frame: storage for spills, locals, callee-saved registers and outgoing arguments. The prologue sets it up; the epilogue tears it down. The stack grows down on x86-64.

push rbp           ; save caller's RBP
mov  rbp, rsp      ; set frame pointer
sub  rsp, 48       ; reserve locals+spills
                   ; (keep 16-byte aligned)
push rbx           ; save callee-saved used

pop  rbx           ; restore callee-saved
mov  rsp, rbp      ; or: leave
pop  rbp
ret

The calling convention is not advisory — it injects hard constraints straight into register allocation.

Let's take one small function all the way down. It sums squared differences — one parameter passed, a loop, a return value.

int sumsq(int *a, int n) {
    int s = 0;
    for (int i = 0; i < n; i++)
        s += a[i] * a[i];
    return s;
}

loop:
  %i   = phi i32 [0, %entry], [%i.n, %loop]
  %s   = phi i32 [0, %entry], [%s.n, %loop]
  %p   = getelementptr i32, i32* %a, i32 %i
  %x   = load i32, i32* %p
  %sq  = mul i32 %x, %x
  %s.n = add i32 %s, %sq
  %i.n = add i32 %i, 1
  %c   = icmp slt i32 %i.n, %n
  br i1 %c, label %loop, label %exit

Args arrive per the ABI: x86-64 a→RDI, n→ESI, return in EAX; AArch64 a→X0, n→W1, return in W0. Selection picks scaled loads and a fused multiply on ARM; allocation keeps the hot values in registers — no spills needed.

sumsq:
    xor   eax, eax        ; s = 0  (return reg)
    xor   ecx, ecx        ; i = 0
    test  esi, esi        ; n <= 0 ?
    jle   .done
.loop:
    mov   edx, [rdi+rcx*4] ; x = a[i]  (scaled)
    imul  edx, edx         ; x*x
    add   eax, edx         ; s += x*x
    add   ecx, 1           ; i++
    cmp   ecx, esi
    jl    .loop
.done:
    ret                    ; result in EAX

sumsq:
    mov   w8, wzr          // s = 0
    mov   w9, wzr          // i = 0
    cmp   w1, #0
    b.le  .done
.loop:
    ldr   w10, [x0, w9, sxtw #2] // x = a[i]
    madd  w8, w10, w10, w8       // s += x*x (FMA-int)
    add   w9, w9, #1             // i++
    cmp   w9, w1
    b.lt  .loop
.done:
    mov   w0, w8           // return s
    ret

xor eax,eax is the idiomatic zero on x86 (smaller, breaks dependences); wzr is the AArch64 zero register. madd fuses multiply-add into one instruction — selection exploited an ISA feature x86 lacks for integers. Both loops are leaf-free of spills, so neither needs a frame: pure red-zone/frameless code.

The final step turns the scheduled MachineInstr stream into bytes. Two paths: write assembly text and shell out to an external assembler, or emit an object file directly. LLVM's MC layer does both from one representation.

The compiler emits one object file at a time and cannot know the final address of anything outside it — an external function, a global, a string. It leaves a relocation: a note telling the linker "patch this field once you know the address". This is the bridge to Part 09.

call  printf       ; → R_X86_64_PLT32 reloc
lea   rax, [rip + msg] ; → R_X86_64_PC32