8.2 Instruction Selection, ABI, and Register Allocation: Getting IR into a Real Machine

An intermediate representation can use virtual values without being limited by the physical register count, but the target CPU offers only a finite number of registers, constrained instruction encodings, and fixed calling conventions. Code generation isn't simply a lookup table replacement of each IR instruction with a machine instruction; it's a complex decision process balancing multiple interdependent constraints to select a valid set of machine operations.

Learning Objectives

• Understand the responsibilities of legalization, instruction selection, and scheduling;
• Explain how the ABI constrains parameters, return values, stack, and registers;
• Use liveness analysis to construct register conflicts;
• Compare graph coloring, linear scanning, spilling, and coalescing.

1. The Target Description Goes Beyond a Simple Opcode Table

The target backend must know:

• Register classes, aliases, and reserved registers;
• Operand shapes and ranges for immediate values;
• Supported data types and valid bit widths;
• Addressing modes;
• Instruction latency, throughput, and code size;
• Calling conventions, stack alignment, and relocations;
• Mapping of atomic operations and memory ordering.

The same IR add i64 may be implemented as a single instruction on a 64-bit target, but might be split into multiple instructions with carry propagation on narrower targets.

2. Legalization Makes Operations Representable

IR operations are not always natively supported by hardware. A legalizer can:

• Expand or split types;
• Expand operations into sequences of instructions or runtime calls;
• Materialize illegal immediate values into registers;
• Map high-level atomic operations to target instruction sequences.

For example, if the target architecture lacks an integer division instruction, the legalizer may invoke a helper function. If the target does not support an i128 add operation, it can be decomposed into two i64 operations plus a carry.

This C function implements unsigned addition modulo $2^{128}$ on a platform with uint64_t. Carry from the low half is added to the high half, and overflow beyond the high half is discarded. It does not implement a language rule that requires an overflow trap:

#include <stdint.h>

typedef struct { uint64_t hi, lo; } U128;

U128 add_u128(U128 a, U128 b) {
    uint64_t lo = a.lo + b.lo;
    uint64_t carry = lo < a.lo;
    uint64_t hi = a.hi + b.hi + carry;
    return (U128){ .hi = hi, .lo = lo };
}

During legalization, it is essential to preserve the semantics of sign extension, overflow, exceptions, and atomicity. A sequence that produces "approximately correct" results is insufficient.

3. Instruction Selection Is a Cost-Driven Coverage Problem

IR:

t0 = mul x, 4
t1 = add base, t0
t2 = load t1

Some targets support scaled addressing modes that can combine multiplication, addition, and load into a single instruction. Selectors can achieve this through:

• Tree/DAG pattern matching;
• Dynamic programming for minimum-cost coverage;
• Table-driven rewriting;
• Global or local search.

The cost is not merely the number of instructions. Factors such as code size, critical path, microarchitecture, register pressure, and scheduling opportunities all influence the optimal choice.

4. ABI Enables Independent Compilation Units to Collaborate

Calling conventions are one part of an ABI; data layout, linking, and unwinding impose additional requirements. Code generation must respect:

• Where parameters are placed in registers or stack slots;
• How return values are transmitted;
• Which registers are preserved by the caller or callee;
• Requirements for the stack pointer, frame pointer, and alignment;
• Layout of variadic parameters and aggregate types;
• Exception unwinding and debugging metadata.

A caller must preserve a needed value across a call if it resides in a caller-saved register that may be clobbered, or arrange another location. A callee that modifies a callee-saved register must restore it before returning. Neither rule requires saving every register unconditionally.

Even if a function executes quickly internally, violating callee-saved register preservation or stack alignment will corrupt state during cross-function calls. The ABI is an externally observable contract, not a detail that can be freely optimized or assumed.

5. Liveness is a backward data flow

For a basic block $B$:

$$LIVEOUT[B]=\bigcup _{S\in succ(B)}LIVEIN[S],$$$$LIVEIN[B]=USE[B]\cup (LIVEOUT[B]-DEF[B]).$$

USE[B] contains values used before their first definition in the block; DEF[B] contains definitions in the block. A current value is live if some future path uses it before redefining it. Static analysis usually conservatively approximates possible paths. In SSA form, values are single-defined, making def-use relationships clear; however, after passing through φ-functions, call constraints, and machine instructions with tied operands, physical register allocation remains complex.

An SSA φ input is used on its corresponding predecessor edge; putting all φ operands in the destination’s ordinary USE set creates spurious liveness on other paths. Early-clobber, tied operands, and call constraints need separate modeling.

A backward scan at the instruction level can start from the block's live-out set: first remove the current definitions, then add the current uses. If the live ranges of two virtual registers overlap, they typically cannot be assigned to the same physical register.

6. Conflict Graphs and Graph Coloring

Each virtual register is a node, with edges connecting values that are simultaneously live. A set of $K$ available registers corresponds to a $K$-coloring of the graph.

General graph coloring is computationally difficult, so the allocator uses heuristics:

1. In the simplified model, remove nodes of degree less than $K$ and push them onto a stack;
2. Identify potential spill candidates;
3. Pop the stack and attempt coloring;
4. When no color is available, insert a spill/reload, then recompute.

Real machines introduce additional complexity such as pre-colored nodes, register classes, subregister aliasing, fixed operands, and call clobbering, making the problem far richer than a simple $K$-coloring problem.

7. Spill Goes Beyond "Putting Something on the Stack"

Spill introduces additional load/store operations, increases stack frame and memory traffic. When selecting candidates for spill, consider:

• Frequency of use and loop depth;
• Length of the live range;
• Whether recomputation is cheaper than reloading;
• Potential positions where the live range can be split;
• The cost of crossing call points.

After inserting a spill, new temporary values and live ranges are created, which may require re-allocation. Spill slots can be reused when their lifetimes do not overlap.

8. Coalescing and Linear Scan

Copy:

v2 = copy v1

If v1 and v2 do not interfere and their register-class, precoloring, and other constraints are compatible, they may share a physical register and the copy can be removed. However, excessive coalescing may merge live ranges and increase node degrees, potentially leading to spills. Therefore, a conservative approach is necessary.

Linear scan allocates registers in the order of live intervals, making it well-suited for time-sensitive compilation scenarios. It is simple to implement and fast, but its quality depends heavily on how live intervals are constructed, split, and handled during spills. Graph coloring does not automatically outperform linear scanning; performance must be evaluated based on specific target architectures and workloads.

9. Instruction Scheduling and Register Pressure Are Interdependent

Scheduling reorders independent instructions to hide latency and respect data, memory, and resource dependencies. Early computation can increase parallelism and extend the lifetime of results, thereby increasing register pressure.

Thus, the choices made during selection, scheduling, and allocation are not strictly unidirectional: the backend may reschedule instructions at different stages, split live ranges, or employ pressure-aware cost models. Removing an instruction does not guarantee performance improvement, critical path dependencies and port contention may be more significant.

Common Misconceptions

• One IR instruction maps to one machine instruction: Instruction types, addressing modes, and target capabilities can lead to instruction merging or splitting.
• When registers are exhausted, simply spill any arbitrary variable: The choice of which variable to spill has a significant impact on runtime cost and subsequent pressure.
• Fewer instructions mean faster execution: Instruction latency, throughput, code layout, and cache behavior are equally critical.
• Correctness within a function is sufficient: ABI (Application Binary Interface), unwind semantics, and debugging information are also part of the code generation contract.

Exercise

1. Compute instruction-level liveness for a linear sequence IR and draw the conflict graph.
2. Allocate three live ranges using two physical registers, and compare the two possible spill choices.
3. Design a valid sequence to legalize an addition operation for a target that does not support i128.
4. List the responsibilities for caller-saved and callee-saved values before and after a function call.

Summary

Target code generation must simultaneously satisfy type validity, instruction constraints, ABI requirements, and cost models. Liveness transforms future uses into conflict relationships, and the allocator then produces an executable layout using a finite number of physical registers, spill operations, and register merging.

The next lesson compares AOT and JIT, focusing not on the idea that "runtime compilation is smarter," but on how profiling, speculation, guards, and deoptimization collectively form a reversible performance decision.