Code Generation: Instruction Selection & Register Allocation

Code Generation

Code generation is the compiler's back end: taking a target-independent intermediate representation with unlimited virtual registers and producing real instructions for a real machine with sixteen of them. Three problems dominate, and they're deeply intertwined.

Instruction selection maps IR operations onto target instructions, which is rarely one-to-one — x 8 should become a shift, x + y4 might become a single addressing-mode operation, and a multiply-add may be one instruction. Register allocation assigns unbounded virtual registers to a finite physical set, spilling to memory when it must; this is the most consequential decision in the back end, since a spill in an inner loop can cost more than any optimization saved. Calling conventions determine how arguments pass, who saves which registers, and how the stack frame is laid out — an ABI contract you don't get to invent.

For most engineers this is the least directly applicable stage and the most illuminating, because it explains what your code actually becomes.

TL;DR

The back end: instruction selection → register allocation → scheduling → emission.
Instruction selection is pattern matching over the IR; tree tiling or a peephole-style matcher.
Register allocation is graph coloring (better code, slower) or linear scan (faster, used by JITs).
Spilling is the cost of running out of registers — avoid it in loops above all else.
Calling conventions are an ABI you must follow exactly: argument registers, caller/callee-saved, stack alignment.
Peephole optimization cleans up local patterns after selection — cheap and surprisingly effective.
Instruction scheduling reorders to hide latency; matters far more on in-order cores.
Emitting LLVM IR instead gives you all of this, for every target, for free.

Quick Example

Lowering a small function all the way down:

Notice how much collapsed. The getelementptr plus load pair became one instruction because x86 addressing modes can scale and add; the multiply reads memory directly; and the whole loop body is six instructions with everything in registers. Getting that last property — nothing spilled in the loop — is the single biggest determinant of the loop's speed.

Core Concepts

Instruction selection

Approaches, in increasing sophistication:

The interesting complication is that the best selection depends on register pressure, which isn't known until allocation, which depends on selection. Compilers handle this with heuristics and occasional iteration rather than solving it properly.

Register allocation

The most impactful decision in the back end.

Graph coloring treats this as a classic graph problem: nodes are live ranges, edges are interference, colors are physical registers. Chaitin's algorithm simplifies the graph by repeatedly removing nodes with fewer than k neighbors (which are trivially colorable), then colors them back in reverse. When no such node exists, it picks one to spill to memory and retries.

Linear scan is the pragmatic alternative: sort live intervals by start position, sweep through, assign a free register, and spill the interval that ends furthest away when none is free. It produces somewhat worse code and runs in near-linear time, which is why JITs use it — compile time is runtime there. LLVM's default is a "greedy" allocator that sits between the two.

Spilling

A spill inside a hot loop can cost more than every other optimization saved. Allocators therefore weight spill candidates by loop depth — a value used inside a triple-nested loop is enormously more expensive to spill than one used once at function entry. Live range splitting (spilling a value only for the region where pressure is high) and rematerialization (recomputing a cheap constant instead of reloading it) both reduce the cost.

Calling conventions

An ABI contract, not a choice. Getting any of it wrong produces corruption that's very hard to debug.

Caller-saved means the caller must save it if it cares — the callee may clobber it freely. Callee-saved means the callee must restore it before returning. Allocators prefer caller-saved registers for short-lived values and callee-saved for values live across calls, since the latter avoids save/restore around every call.

Peephole optimization

A sliding window over the emitted instructions, rewriting local patterns:

Cheap to implement, mechanical, and it cleans up a great deal of the redundancy that instruction selection and register allocation leave behind. A peephole pass is usually one of the highest value-per-line components in a back end.

Instruction scheduling

Reordering independent instructions hides load latency and keeps functional units busy. List scheduling over a dependence DAG is the standard technique, weighting by critical-path length.

How much it matters depends heavily on the target. Modern out-of-order x86 cores reorder aggressively in hardware, so the compiler's scheduling has modest impact. In-order cores — many embedded ARM parts, GPUs, and older VLIW designs — depend on it entirely.

Best Practices

Target LLVM unless you have a reason not to

Emitting LLVM IR gives you instruction selection, register allocation, scheduling, and every target backend, all maintained by people who do this full time. Writing your own back end is worthwhile for compile speed (Go, Zig's self-hosted backend), for a very small target, or when the back end is the project.

Get the calling convention exactly right

Read the ABI document, not a blog post. Argument order, stack alignment at the call instruction, red zone rules, struct passing by value versus by reference, and varargs handling are all places where "mostly right" produces corruption that appears far from the cause.

Weight spill decisions by loop depth

A value spilled inside a nested loop costs orders of magnitude more than one spilled at function entry. Any allocator that doesn't weight by execution frequency will produce code with a pathologically slow inner loop.

Write a verifier and run it after every pass

Check that every use is dominated by its definition, every block ends in a terminator, register classes match, and the stack is balanced. Back-end bugs manifest as wrong answers or crashes far from the cause; a verifier turns them into an immediate assertion.

Keep a working simple path

An unoptimized "just correct" lowering for every construct, always available. When an optimization produces wrong code, being able to disable it and confirm the base path works isolates the bug in minutes rather than days.

Test against a reference

Differential testing — compile the same program at -O0 and -O2 and compare output — catches miscompilation reliably. Fuzzers like Csmith and YARPGen generate programs specifically for this, and they've found real bugs in GCC and LLVM.

Use rematerialization for cheap values

Recomputing a constant or a simple address is often cheaper than a reload from a spill slot. Marking values as rematerializable is a small amount of work that measurably reduces spill cost.

Measure on the actual target

Instruction counts are a poor proxy for speed. Cache behavior, branch prediction, and out-of-order execution mean a longer sequence is frequently faster. Benchmark on the real hardware with realistic input, and use hardware performance counters rather than intuition.

Common Mistakes

Ignoring stack alignment

The "sometimes" is what makes this vicious: it only faults when the callee happens to use an aligned SSE instruction.

Clobbering callee-saved registers

Allocating registers without loop weighting

Naive instruction selection

Scheduling before register allocation without care

No verification between passes

FAQ

Should I write my own back end or use LLVM?

LLVM, for almost every project. You get a mature optimizer, every major target, and decades of correctness work for the cost of emitting its IR. Write your own for compile speed (Go's back end exists largely because LLVM was too slow for their goals), for an unusual target, for a small embedded VM, or when learning is the point. Cranelift is a middle option: much faster than LLVM, less optimization, designed for JIT use.

How hard is register allocation?

Optimal allocation is NP-complete (graph coloring), so everyone uses heuristics. A working linear-scan allocator is a few hundred lines and produces reasonable code. A good graph-coloring allocator with live range splitting, rematerialization, and coalescing is a substantial project — LLVM's greedy allocator is thousands of lines and still an area of active work.

What is SSA destruction?

Converting out of SSA form before register allocation, since φ nodes aren't real instructions. The naive approach inserts copies at the end of each predecessor block. The subtleties — the "lost copy" and "swap" problems, where naive copy insertion produces wrong code with overlapping live ranges — are well documented and worth reading about before implementing.

Why is a longer instruction sequence sometimes faster?

Because instruction count isn't the cost model. A sequence that avoids a cache miss, a mispredicted branch, or a dependency stall beats a shorter one that doesn't. xor eax, eax is preferred over mov eax, 0 despite being the same length partly because it breaks a false dependency on the previous value. Always measure.

How do compilers handle vectorization?

Auto-vectorization recognizes loop patterns where iterations are independent and rewrites them to use SIMD instructions. It's fragile — aliasing, non-unit strides, early exits, and reductions all defeat it — which is why restrict/noalias, aligned data, and simple loop bodies matter for numeric code. Explicit SIMD intrinsics or portable SIMD libraries are the escape hatch when auto-vectorization won't fire and performance matters.

Do I need to know assembly?

To write a back end, yes — you're emitting it. To use a compiler well, a reading knowledge is genuinely valuable: being able to look at the generated code (Compiler Explorer makes this trivial) settles questions about whether an optimization fired that no amount of reasoning about the source will. Writing assembly by hand is rarely useful outside of very specific niches.