A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Code generation transforms optimized IR into executable machine code. For each IR instruction, emit corresponding assembly or bytecode. This involves instruction selection (choosing target instructions), operand allocation (assigning registers/memory), and instruction scheduling (reordering for performance). Modern code generators use pattern matching, templates, or dynamic programming to select instructions.
After the front end parses and analyzes source code and the middle end optimizes an intermediate representation (IR), the back end has one job: turn that IR into instructions the target machine can execute. This is code generation, and it is harder than it sounds because IR is designed for portability and ease of manipulation — it does not map one-to-one to any real instruction set. The code generator must bridge that gap while producing efficient output.
The first sub-problem is *instruction selection*: for each IR operation (or group of operations), choose which machine instruction(s) to emit. Many IR patterns can be matched by multiple sequences of machine instructions with different costs. For example, a multiply-and-add operation in the IR might be expressible as two instructions (MUL then ADD) or as a single fused multiply-add instruction if the target supports it. The compiler models this as a tree-pattern-matching problem — the IR is treated as a tree, and a library of patterns (each corresponding to a machine instruction) is applied greedily or via dynamic programming to find the lowest-cost cover.
The second sub-problem is *register allocation*: the IR assumes an unlimited supply of temporary variables, but real machines have a fixed, small set of registers. Register allocation assigns IR temporaries to physical registers, and when there are not enough registers, decides which values to *spill* — write to the stack and reload later. Spilling is expensive because memory accesses are slow, so minimizing spills is critical. Register allocation is modeled as a graph-coloring problem: temporaries that are "live" at the same time cannot share a register, and coloring the interference graph with K colors (where K is the number of registers) finds a valid assignment or identifies which temporaries must be spilled.
The third sub-problem is *instruction scheduling*: modern processors have pipelines and can execute multiple instructions simultaneously, but only if there are no data or resource hazards between them. The compiler reorders instructions (subject to data-flow dependencies) to keep the pipeline busy. A load from memory, for example, might stall the pipeline for many cycles waiting for the result — a scheduler can move other independent instructions into that gap. Scheduling after register allocation is common because the register assignment affects which instructions can be reordered.
The output of code generation is assembly or object code for a specific target architecture (x86, ARM, RISC-V, WebAssembly, etc.). This is why the back end is the component that must be rewritten when porting a compiler to a new target — the front end (parsing, type checking) and middle end (IR optimizations) remain the same. LLVM's success largely comes from providing a high-quality, target-independent IR and a shared code generation framework that handles much of this complexity, allowing front ends for many languages to benefit from one well-engineered back end.