instruction selection

The optimizer's IR speaks in abstract operations — add, multiply, load, compare — that are not tied to any one chip. But a real processor has a specific, often quirky menu of instructions, sometimes with a single instruction that does several abstract operations at once. Instruction selection is the back-end step that picks, for each chunk of IR, which actual machine instructions of the target processor will implement it.

Think of it as pattern matching the abstract IR against the target's instruction set. The selector looks at patterns of IR operations and finds the best machine instruction (or short sequence) that produces the same effect. Often it can fuse several abstract operations into one real instruction: on x86-64, the abstract pattern base + index * 4 + offset for an array address maps to a single load with a complex addressing mode, and a multiply-then-add can become one fused multiply-add (FMA) instruction where available. The goal is to cover the whole IR with machine instructions while minimizing total cost (cycle count, code size), which compilers approximate with cost-driven pattern matchers (often built from a target description).

It matters because the same IR maps to very different instructions on different processors — this stage is a big part of why a back end is target-specific and why the same C compiles to dissimilar assembly on x86 versus ARM. When you read disassembly and see one instruction doing what looked like two operations in your source, that fusion is instruction selection at work. A caveat: instruction selection is constrained by what the chip actually offers and by correctness — it can only pick an instruction whose behavior exactly matches the IR's meaning (including flag effects and overflow behavior), so a 'clever' instruction that is subtly different cannot be used even if it looks faster.