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

At the base of the tower, infinite virtual values must be packed into finite registers, and abstract instructions must conform to the constraints of real CPUs and ABI specifications.

Intermediate Representation (IR) assumes infinite virtual values, 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 Make Operations Representable First

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.

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

The calling convention specifies:

• 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.

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]). $$

A value is live if it will be used on a future path and has not been redefined in between. 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.

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. Simplify nodes of low degree;
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 Scanning

Copy:

v2 = copy v1

If v1 and v2 do not conflict, they can be assigned to the same physical register and the copy operation can be eliminated. However, excessive coalescing may merge live ranges and increase node degrees, potentially leading to spills. Therefore, a conservative approach is necessary.

Linear scanning 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 by leveraging 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 anti-optimizations collectively form a reversible performance decision.