13.1 Instruction Selection

Instruction selection converts target-independent IR into operations supported by a particular instruction set architecture (ISA). The input may say add, load, compare, and branch; the output must choose x86-64, AArch64, or RISC-V instructions with legal operand classes, immediate ranges, and addressing modes.

This is not a one-to-one translation. One IR operation may need several machine instructions, while one machine instruction may implement several connected IR nodes. For example, AArch64 madd can compute a * b + c, and x86 lea can combine a base, scaled index, and displacement without a separate multiply and two adds.

Covering an IR tree with patterns

A selector describes machine instructions as patterns over IR. A simple integer-add pattern might match:

IR:      add(reg, reg)
target:  ADD dst, lhs, rhs
cost:    latency 1, size 4 bytes

A larger pattern can match add(mul(a,b), c) and emit a fused multiply-add when the target and numeric semantics allow it. Selection becomes a covering problem: choose patterns whose tiles cover every required IR node without overlapping illegally, while minimizing a cost.

For trees, dynamic programming can compute the cheapest cover bottom-up. For each node and desired result class, record the cheapest rule and its child requirements. The cost model may combine instruction count, encoded size, latency, throughput, and register pressure. A size-optimized build may choose a different cover from a speed-optimized build.

DAGs, shared values, and evaluation order

Real IR is a directed acyclic graph (DAG), not always a tree: one value can have several users. Naively duplicating a shared subtree for tree matching may recompute work or duplicate a trap. A selector must preserve sharing, effects, and the order constraints already present in the machine IR.

Instruction selection also respects register classes. An integer result may require a general-purpose register, floating point uses an FP/vector class, and some instructions require fixed registers. A rule is legal only if later allocation can satisfy its operand and result constraints—or if the selector inserts copies into the required classes.

Addressing modes are instruction tiles

Memory operands often make the biggest difference between ISAs. The expression below describes an effective address:

address = base + index * scale + displacement
value = load(address)

x86-64 can encode many combinations directly in a load, with scales 1, 2, 4, or 8. AArch64 supports several base-plus-immediate and shifted-register forms, but its immediate range depends on access width and instruction form. Base RISC-V loads use a base register plus a signed 12-bit displacement, so an indexed address normally requires prior arithmetic.

Legalization before and after selection

IR may contain types or operations the target cannot execute directly: 128-bit addition on a 64-bit target, an unsupported vector width, or an immediate too large for one instruction. Legalization decomposes them into supported pieces or runtime helper calls. Some compilers legalize generic IR first; others let selection rules expand illegal operations.

After selection, target-specific pseudo-instructions may remain. A pseudo such as “load arbitrary 64-bit constant” can later expand into one or several real instructions depending on the value. Keeping pseudos temporarily gives register allocation and scheduling a clearer semantic operation before final encoding constraints are fixed.

A good selector test records the input IR, selected machine instructions, target features, and cost. Test boundaries of immediate ranges, every register class, shared DAG nodes, trapping operations, and disabled CPU features. Correctness comes first: the cheapest illegal cover is not a candidate.