Code Generation: Instruction Selection, Scheduling, and Emission

Compilers Compilers 8 min read 1604 words Beginner ExcellentWiki Editorial Team

Code generation is the compiler backend phase that transforms an optimized intermediate representation (IR) into target machine code — assembly instructions, binary object code, or executable images. It is the phase where abstract computations become concrete operations bound to a specific instruction set architecture (ISA). The code generator makes decisions about which instructions to use, how to allocate scarce registers, and in what order to schedule operations for maximum pipeline utilization. This article covers the three central problems of code generation: instruction selection, instruction scheduling, and register allocation, along with practical peephole optimization and machine code emission.

Instruction Selection: Mapping IR to Machine Instructions

Instruction selection is the problem of choosing target machine instructions that implement each IR operation. A three-address code like a = b + c might map to a single ADD R1, R2, R3 on a RISC machine, or to a sequence of loads and an addition on a stack-based architecture. The goal is to produce correct, compact, and fast code.

Tree Tiling and Maximal Munch

The classic approach treats the IR as a tree and tiles it with instruction patterns. Each machine instruction is modeled as a tree pattern with a cost. The maximal munch algorithm greedily covers the tree with the largest possible tile at each step, starting from the root. This simple heuristic produces good results and runs in linear time.

For example, an addressing mode that supports load R1, [R2 + offset] is a single tile covering both an addition and a memory access. Tiling this expression as one instruction saves a cycle compared to generating separate add and load sequences. The Dragon Book devotes a chapter to code generation and presents maximal munch as the foundational algorithm.

Dynamic Programming for Optimal Tiling

Maximal munch is fast but not optimal. For compilers targeting performance-critical code, dynamic programming (DP) finds the optimal tiling — the lowest-cost covering of the IR tree. DP computes the minimum cost for each subtree bottom-up, considering all matching tiles. BURG (Bottom-Up Rewrite Generator) is a tool that generates optimal instruction selectors from tree grammar specifications. LLVM uses a variant of DP-based selection for some targets, while GCC’s older approach involved hand-written patterns in machine description files.

Pattern Matching with Instruction Grammars

Modern backends, particularly LLVM’s, use TableGen to describe instruction patterns declaratively. Each instruction has a pattern field listing the DAG (Directed Acyclic Graph) fragment it implements. The instruction selector walks the target-independent DAG and matches it against target-specific patterns. If multiple patterns match, the selection DAG considers legality, profitability, and target features (e.g., whether SSE4 is available).

The LLVM instruction selection framework is documented in the LLVM Language Reference Manual and in conference talks by its original developers. It processes SelectionDAG nodes through legalization, DAG combining, and pattern matching before emitting machine instructions.

Register Allocation

Register allocation assigns the unlimited virtual registers used in IR to the finite set of physical registers available on the target. It is one of the most impact-optimization stages in any compiler — poor register allocation can double the number of loads and stores in a function.

Graph Coloring Register Allocation

Graph coloring models interference: each virtual register is a node, and an edge connects two nodes if their live ranges overlap. The problem reduces to coloring this interference graph with K colors, where K is the number of available registers. If the graph is not K-colorable, some values must spill to memory.

Chaitin’s algorithm, described in his 1982 paper “Register Allocation via Graph Coloring,” was the first practical implementation. Briggs and Cooper improved it with optimistic coloring and rematerialization. GCC’s register allocator uses an improved graph coloring scheme, while LLVM’s early allocators used linear scan.

Register Allocation: Graph Coloring and Linear Scan Algorithms covers this topic in depth, including allocation for irregular register files and SSA-based splitting.

Instruction Scheduling

Instruction scheduling reorders instructions to maximize instruction-level parallelism (ILP). Modern processors execute multiple instructions per cycle, but only if there are no data hazards, structural hazards, or control hazards between them. The scheduler’s job is to reorganize the instruction stream to minimize pipeline stalls.

List Scheduling

List scheduling is the standard algorithm. It builds a data-dependency graph (DAG) for a basic block — each instruction is a node, and edges represent true dependencies (read-after-write), anti-dependencies (write-after-read), and output dependencies (write-after-write). The scheduler assigns a priority to each node (often the height in the DAG or the critical path length) and repeatedly schedules the ready node with the highest priority.

Modern processors include scheduling models that describe instruction latencies, pipeline stages, and resource consumption. LLVM’s MachineScheduler uses itinerary data from TableGen to model target pipelines. GCC’s scheduler similarly relies on define_insn_reservation declarations in machine description files.

Software Pipelining

Software pipelining schedules loops so that iterations overlap. The modulo scheduling algorithm computes a schedule for one iteration, then staggers successive iterations to fill the pipeline continuously. The result is near-optimal throughput for loops that dominate execution time. Intel’s compilers and GCC’s -fmodulo-sched flag enable software pipelining for loops measured as hot during profile-guided optimization.

Peephole Optimization

Peephole optimization is a simple, effective technique that examines a small window of instructions (the peephole) and replaces patterns with better sequences. It runs after instruction selection and scheduling, catching local inefficiencies that earlier passes missed.

Common peephole optimizations include:

Strength reduction — replacing multiply by constant with shift-and-add sequences
Redundant load/store elimination — removing store R1, [addr]; load R2, [addr] when R1 and R2 are the same register
Jump-to-jump elimination — collapsing jmp L1 where L1 is another unconditional jump
Dead instruction removal — deleting instructions whose results are never used

The Dragon Book describes peephole optimization in a section on code generation, noting that it can be applied iteratively until no patterns match. LLVM’s peephole optimizer runs as part of the machine code layer.

Machine Code Emission

The final stage of code generation writes binary machine code to object files. This involves:

Encoding — converting each instruction mnemonic to its binary opcode with operand encoding
Relocation — recording fixups for symbols whose addresses are unknown until link time
Object format assembly — constructing ELF, Mach-O, or COFF sections, symbols, and relocations

LLVM’s MC layer (Machine Code) handles emission. It parses assembly into MCInst objects, then uses target-specific AsmBackend and MCCodeEmitter classes to write binary. The design separates assembly parsing from binary encoding, allowing reuse of the instruction description tables.

Target-Specific Considerations

Each target architecture presents unique code generation challenges:

x86-64 has a variable-length instruction encoding (1–15 bytes) with complex addressing modes. The instruction selector must navigate a large instruction space — there are often multiple instructions that could implement the same IR operation, with different code size and performance tradeoffs. The 16 general-purpose registers (15 available after stack pointer) are further restricted by register class constraints: some instructions only work with specific registers for byte operations or shifts.

ARM64 uses a fixed-length 32-bit instruction encoding with 31 general-purpose registers. Its orthogonal register set simplifies register allocation compared to x86. The CBZ/CBNZ (compare and branch if zero/nonzero) instructions enable efficient branch-on-condition patterns that the scheduler can optimize.

RISC-V is similar to ARM64 in its fixed-length encoding and orthogonal registers, but its compressed instruction set (RVC) provides 16-bit instruction variants for common operations. The code generator must decide when to use compressed vs. standard instructions, balancing code size against instruction count.

Debugging Code Generation

Debugging the code generator is challenging because the output is a binary that must be inspected at the assembly or machine-code level. Tools and techniques include:

Assembly dumps — clang -S -o - source.c shows the generated assembly. The -fverbose-asm flag annotates assembly with source line numbers and compiler comments
LLVM’s debug flags — -print-after-all and -print-before-all dump the IR before and after each pass. -stop-after=<pass-name> halts compilation at a specific pass, useful for isolating code generation issues
GCC’s RTL dumps — -fdump-rtl-all generates RTL dumps at each backend stage. The -da flag prints RTL after each pass
Machine code analyzers — llvm-mca simulates the CPU pipeline on the generated assembly, reporting throughput, latency, and resource pressure. This helps identify scheduling problems without running on real hardware
Binary inspection — objdump -d disassembles the binary. readelf -a shows relocations and section layout

A common debugging workflow: compile with -O2, use -fverbose-asm to annotate assembly, identify the unexpected instruction sequence, then use -print-after-all to find which optimization pass introduced the problem.

FAQ

What is the difference between instruction selection and scheduling? Instruction selection chooses which instructions implement IR operations. Instruction scheduling reorders those instructions to improve pipeline utilization. They are independent phases — selection runs first, then scheduling rearranges the selected instructions.

How does a retargetable compiler handle code generation? Compilers like GCC and LLVM use machine description files (GCC .md files, LLVM TableGen .td files) that describe instruction formats, latencies, and register files. The code generator is parameterized by these descriptions, allowing it to target multiple ISAs from a shared framework.

What happens when there are not enough registers? The register allocator spills some values to memory, inserting load and store instructions. Excessive spilling degrades performance. Techniques like live range splitting and rematerialization reduce spill costs.

Can code generation be done incrementally? Yes. Just-in-time compilers, such as those in Java HotSpot and V8, generate code for individual methods on demand. They use lightweight instruction selection and linear scan register allocation to minimize compilation time.