Code Generation – Register Allocation, Graph Colouring and Instruction Scheduling Explained

1. Role of the Code Generator

The code generator is the final phase of the compiler. It takes the optimised intermediate representation (typically 3AC or SSA) and produces assembly language or machine code for a specific target architecture (x86, ARM, RISC-V, etc.).

The code generator must solve three interrelated problems simultaneously:

1. Instruction selection: Which machine instructions implement each IR operation?
2. Register allocation: Which values live in registers vs memory?
3. Instruction ordering: In what order to emit instructions to maximise performance?

These problems are interdependent and collectively NP-Hard in general, so compilers use heuristics.

2. Instruction Selection

Instruction selection maps each IR operation to one or more machine instructions. For a RISC-like machine, a 3AC instruction often maps to one machine instruction. For CISC machines (like x86), more complex patterns may map to a single instruction.

Simple Mapping (RISC)

Tree-Pattern Matching

Modern code generators represent IR as expression trees and cover the tree with tiles — patterns corresponding to machine instructions. The goal is to cover the tree with tiles that minimise total cost (fewer instructions, cheaper instructions). This is solved optimally using dynamic programming (tree DP) in O(n) time.

Macro Expansion

A simpler approach: expand each IR instruction into a fixed sequence of machine instructions using templates. Fast but produces non-optimal code. Often used for initial code generation, with peephole optimisation applied afterward.

3. Simple Code Generation Algorithm

A classic simple code generator processes one basic block at a time, maintaining two data structures:

• Register descriptor: For each register, which variable’s current value it holds
• Address descriptor: For each variable, where its current value is (register, memory, both)

getReg(instruction)

For each instruction, decide which registers to use:

1. If an operand is already in a register, use that register
2. If a free register is available, use it
3. If no free register: find the register holding a variable whose next use is furthest in the future. Spill it (save to memory) and reuse that register.

At the end of a basic block, write back to memory all variables that are live (needed after the block) and whose value only exists in a register.

4. Register Allocation

Real machines have a small, fixed number of registers (typically 8–32). IR temporaries are unlimited. Register allocation assigns IR values to physical registers, deciding which values to keep in registers and which to spill to memory.

This is one of the most critical optimisations — memory accesses are 10–100× slower than register operations on modern hardware. Minimising spills is essential for performance.

Allocation vs Assignment

• Register allocation: Deciding which variables get a register at all
• Register assignment: Deciding which physical register each variable gets

5. Graph Colouring Register Allocation

The standard algorithm for register allocation models the problem as graph colouring. It was introduced by Chaitin et al. (1981) and is used in GCC, LLVM, and virtually every optimising compiler.

Interference Graph

Build a graph where:

• Each node represents an IR value (variable or temporary)
• An edge connects two nodes if the corresponding values are simultaneously live at any program point — they cannot share a register

Graph Colouring

Assign colours (physical registers) to graph nodes such that no two adjacent nodes share a colour. If the graph can be coloured with k colours (k = number of available registers), then all values fit in registers simultaneously. The colouring directly gives the register assignment.

Chaitin’s Algorithm

1. Build the interference graph
2. Simplify: Repeatedly remove nodes with fewer than k neighbours (they can always be coloured). Push them onto a stack.
3. Spill: If all remaining nodes have k or more neighbours, select one to spill (mark it for memory). Remove it and continue simplifying.
4. Select (colour): Pop nodes from the stack and assign colours — always possible for nodes removed in step 2.
5. Rewrite: For spilled variables, insert load/store instructions around each use/definition.
6. Repeat until no more spills occur.

Graph colouring is NP-Complete in general, but Chaitin’s simplification heuristic works well in practice.

6. Register Spilling

When there are not enough registers to hold all live values simultaneously, some values must be spilled — stored in memory (typically the stack frame) and reloaded when needed.

Spill cost heuristics — which variable to spill:

• Spill the variable used least frequently in the future (next-use farthest)
• Spill the variable with the cheapest spill cost (infrequently accessed variables)
• Prefer to spill variables outside loops rather than those inside tight loops
• Do not spill a variable that is used in the next instruction

Spilling inserts LOAD (before use) and STORE (after definition) instructions. Too many spills significantly degrade performance — good register allocation minimises spills.

7. Instruction Scheduling

Modern CPUs are pipelined — multiple instructions execute simultaneously in different pipeline stages. Some instructions have latency: a result is not available for several cycles after the instruction is issued. If the next instruction depends on the result, the CPU stalls.

Instruction scheduling reorders instructions to fill stall slots, improving pipeline throughput without changing semantics. Two types:

• Local (basic block) scheduling: Reorder instructions within a basic block
• Global scheduling: Move instructions across basic blocks (e.g., trace scheduling, software pipelining)

List Scheduling Algorithm

1. Build a dependency graph for the basic block (edges = data dependencies)
2. Topological order the graph (the scheduler must respect data dependencies)
3. At each cycle, choose a ready instruction (all its dependencies satisfied) using a priority heuristic (e.g., prefer instructions with longest critical path remaining)
4. Issue the chosen instruction

8. Runtime Storage Organisation

The code generator also manages the runtime memory layout — how variables are allocated during execution.

Activation Records (Stack Frames)

Each function call creates an activation record (stack frame) on the call stack, containing:

• Return address
• Saved register values (caller-saved or callee-saved)
• Local variables and temporaries
• Parameters passed from the caller
• Frame pointer (FP) and stack pointer (SP)

Calling Convention

A calling convention defines who (caller or callee) saves which registers, how parameters are passed (registers vs stack), and how return values are communicated. Common examples: x86-64 System V ABI (first 6 integer args in RDI, RSI, RDX, RCX, R8, R9), ARM AAPCS (first 4 args in R0–R3).

9. Common Misconceptions

10. Frequently Asked Questions