Codegentarget

Instruction Selection

Mapping IR operations onto instructions the machine actually has. Our backend selects `lea rax, [rbx+rbx]` for `x * 2` rather than `imul` — not because it is fewer bytes, but because it is three-operand and does not touch the flags.

The question

How does a compiler decide which machine instruction implements an IR operation?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

Low-level IR on the way in — three-address operations over virtual registers, where every operation is an abstract one (add, mul, load) with no commitment to an encoding. Machine IR on the way out: real target opcodes, still over virtual registers. This intermediate form exists to answer "which instruction" separately from "which register", because answering both at once produces a search space nobody can navigate.

What this phase may assume or do

A pattern may replace an IR subtree only if the chosen instruction computes the same value for every input the IR operation admits, including at the boundaries. x * 2 may become an addition only because signed and unsigned doubling agree on all bit patterns at the same width; x / 2 may *not* become an arithmetic shift for signed x, because shifting rounds toward negative infinity and C-family division rounds toward zero, so -3 / 2 would give -2 instead of -1. The selector must also preserve any side effect the IR operation had — a trapping division cannot become a non-trapping sequence, and an instruction that clobbers the flags cannot be inserted between a comparison and the branch that reads it.

Key points

The mismatch between three-address IR and two-operand destructive x86 arithmetic is a genuine selection problem, and it is why mov instructions appear that have no source-level origin.
lea is chosen for x * 2 because it is three-operand and does not write the flags — structural properties, not raw speed.
x86 integer division has fixed operands in rdx:rax, so selection constrains register allocation directly. The phases are not independent.
A pattern table carries a cost model, and the model — instructions, cycles, bytes, register pressure — is a design choice that changes the output.
A selection can be locally optimal and globally bad, because the cost of extra register pressure is paid by a later phase.

Three-address IR meets a two-address machine

targetTwo-operand destructive arithmetic is x86-64 (and 32-bit x86 before it). AArch64, RISC-V, MIPS and PowerPC all have three-operand arithmetic — add x0, x1, x2 reads two registers and writes a third — so this particular mov never appears there. x86 partially recovers the property with the three-operand VEX encodings for vector instructions and with lea for integers, which is the next section.

The most basic selection problem on x86-64 has nothing to do with clever instructions. It is that the IR says d = a + b — three distinct operands — and the machine's add takes two, writing its result over its first operand. There is no instruction that reads two registers and writes a third.

So the selector must materialise the missing operand: copy a into d, then add b into d. Two instructions where the IR had one, and the copy is pure overhead created by the shape of the instruction set. Whether it survives depends on the register allocator: if d and a end up in the same physical register the mov becomes mov rax, rax and is deleted by [[peephole-optimization]]. Making that happen deliberately is [[coalescing-and-rematerialization]].

This is why the same C function compiles to visibly more instructions on x86-64 than on AArch64 in unoptimized builds, and to roughly the same number once the allocator has had a chance to coalesce. The instruction set shape leaks into the instruction count.

Three-address IR lowered to two-address x86-64

Before

%3 = add %1, %2

After

mov  rax, rcx    ; rax <- %1
add  rax, rdx    ; rax <- rax + %2

Legal only when

Only if %1 is dead after this instruction, or its value has already been copied somewhere else that is still live. The mov-then-add sequence destroys the destination, so if %1 is used again later and the allocator assigned it to rax, the copy must go to a different register instead — which is the constraint the allocator is actually solving.

Illegal when

If the destination register also holds a value that is live afterwards, this sequence silently corrupts it. It is also illegal to insert between a cmp and the conditional branch that consumes its result, because add writes the flags: the branch would then test the addition instead of the comparison.

The lea trick, and why it is not about speed

targetAll three sequences are x86-64. On AArch64, x * 2 is lsl w0, w0, #1 and x + 7 is add w0, w1, #7 — three-operand already, no trick required — and division is sdiv w0, w1, w2 with no fixed register pair. The lea pattern has no meaning on any architecture whose arithmetic is already three-operand and whose flags are only written when the instruction says so.

Our backend has a pattern that fires on x * 2 with a constant right operand and emits lea rax, [rbx+rbx] instead of imul rax, rbx, 2. lea — load effective address — computes an address and stores it in a register without dereferencing anything. Fed two registers it is simply an adder that happens to live in the addressing unit.

The reason to prefer it is not that multiplication is slow; on a modern core imul by a constant is a few cycles and heavily pipelined. It is that lea has two structural properties that arithmetic instructions on x86 do not. It is three-operand, so it can write a destination different from both sources and save the mov from the previous section. And it does not write the flags register, so it can be scheduled into the gap between a comparison and its branch without destroying the comparison.

That second property is the one worth internalising. On x86 the flags are a single architectural resource that almost every arithmetic instruction overwrites, which makes them a scheduling bottleneck. An instruction that computes arithmetic without touching them is genuinely more flexible, and the selector is buying flexibility for the scheduler and the allocator rather than raw latency.

Three selections our backend actually makes, from src/compilers/sim/codegen.ts

1; %4 = %3 * 2
2  lea  rax, [rbx+rbx]     ; three-operand, no flags written
3 
4; %5 = %3 + 7   (destination differs from source)
5  lea  rax, [rbx+7]       ; avoids the mov a two-operand add would need
6 
7; %6 = %3 / %4
8  mov  rax, rbx
9  cqo                     ; sign-extend rax into rdx:rax
10  idiv rcx                ; quotient in rax, remainder in rdx

The third is the interesting one: x86 integer division has *fixed* operands. It reads the dividend from the rdx:rax pair and clobbers both. Selection here is not choosing between candidates — it is emitting a fixed sequence and telling the register allocator that two specific registers are unavailable across it. Instruction selection and register allocation are not as separable as the phase list suggests.

A pattern table is a cost model in disguise

A selector is fundamentally a table: IR shapes on the left, instruction sequences on the right, and a cost on each entry. Selection is then a search for the cheapest cover of the IR with patterns from the table. What "cheapest" means is a modelling decision, and it is where selectors differ.

Counting instructions is the crudest model and surprisingly serviceable. Counting cycles requires a latency table per microarchitecture and goes stale with every CPU generation. Counting bytes matters when instruction cache pressure dominates, which is why -Os builds make visibly different selections. Modelling register pressure is the one that matters most and is hardest, because the cost of a selection that needs an extra live value is not paid here — it is paid later, in spill code, by a phase that has already lost the ability to choose differently.

None of these models is right. A selector is a heuristic making a local choice about a global cost, which is why [[peephole-optimization]] exists downstream to clean up what the local view missed.

One IR operation, several selections, and what each is optimising fortarget

IR	Selection	Bought	Paid
%d = %a * 2target	`lea rd, [ra+ra]`	Three-operand, no flag write, one instruction	Uses the address-generation unit, which some cores have fewer of than ALUs
%d = %a * 2target	`shl rd, 1` after a `mov`	Very short encoding	Two instructions, writes the flags, destructive
%d = %a * 2target	`imul rd, ra, 2`	Obvious, one instruction, three-operand form exists	Higher latency than an add on most cores; writes the flags
%d = %a * 8target	`lea rd, [ra*8]`	The scale field handles 2, 4 and 8 for free	Only powers of two up to 8; 16 needs something else
%d = %a + 0target	nothing at all	Zero instructions	Requires the selector to prove the operand is already in the destination

How it works

The steps, in the order the compiler takes them.

The IR is lowered until every operation has at least one implementable pattern — no construct remains that the target cannot express.
The selector walks the IR, matching each operation or subtree against the pattern table; larger patterns that cover several IR nodes at once are preferred when the cost model says so.
A matched pattern emits one or more machine instructions over virtual registers, together with any constraints the instruction imposes — fixed registers, clobbered registers, flag effects.
Operations with no matching pattern are expanded into a fixed sequence — a library call for 128-bit division, a load-modify-store for an unsupported atomic width.
The result is machine IR: real opcodes, virtual registers, and a set of constraints handed to the register allocator.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A pattern fires on a shape it does not actually implement — signed division selected as an arithmetic shift — and the program returns the wrong answer only for negative inputs, which no test with positive fixtures will ever catch.
An instruction that writes the flags is selected into the gap between a comparison and its branch, and a conditional goes the wrong way. The symptom is a branch that takes the wrong path in optimized builds only.
The selector emits an instruction from an ISA extension the deployment target lacks, and the binary faults with an illegal instruction on older hardware while working perfectly on the build machine.
A pattern that saves one instruction requires an extra simultaneously-live value, and a hot loop that previously fitted in registers begins spilling. The function gets measurably slower after a "better" selection.
A large machine-generated expression tree makes a dynamic-programming selector run in time quadratic in the tree size, and one file takes minutes to compile while every other file takes milliseconds.

When it helps

Reading disassembly: recognising lea as arithmetic, a shift as a multiply by a power of two, or xor eax, eax as "set to zero" stops most of the "why is the compiler doing that" questions.
Writing a backend for a new target: the pattern table is the bulk of the work and the part that determines code quality.
Understanding why a source-level "optimization" changed nothing: the selector was already producing the same instructions for both spellings.

When it hurts

Trying to predict selection from the source. Selection happens after the middle-end has rewritten the code, so the operation being selected often no longer resembles anything you wrote.
Assuming a shorter instruction sequence is faster. On an out-of-order core, latency, port pressure and dependence chains dominate instruction count, and the hardware issues several instructions per cycle regardless of how many there are.

What it costs

Every one of these is paid by something.

A larger pattern table buys better code and costs implementation and maintenance surface: every pattern is a correctness obligation that must hold for every input, and a wrong pattern is a miscompilation rather than a slowdown.
Optimal tiling by dynamic programming buys provably cheapest coverage under the cost model and costs compile time proportional to the tree size times the table size — which is why maximal munch, a greedy approximation, is what most production selectors actually run.
Selecting to minimise instructions buys code size and can cost register pressure, which is paid later as spill code that the selector never sees.

What else you could do

What a different compiler or language does instead, and when that is better.

Macro expansion: one fixed instruction sequence per IR operation, no matching at all. This is what template JITs and simple teaching compilers do. Compilation is instant and the code contains obvious redundancy that a peephole pass then partially removes.
BURG-style generated selectors: write the patterns and costs declaratively and generate a bottom-up optimal tiler from them. LLVM's TableGen and GCC's machine description files are industrial versions — see [[tree-pattern-matching]].
Selection over a DAG rather than a tree, which finds shared subexpressions the tree view would duplicate, at the cost of an NP-hard covering problem that must then be approximated.
Superoptimization: search all short instruction sequences for one that matches the required behavior, verified by an SMT solver. Produces sequences no human wrote, and is used in practice to *generate peephole tables* rather than to compile whole programs.

See it for yourself

The flag, dump or tool that shows you this directly.

See the selection: clang -O2 -S -o - file.c and look for arithmetic done by lea, shifts standing in for multiplication, and xor used to zero a register.
See it before and after: llc -print-after=isel file.ll prints LLVM machine IR immediately after instruction selection, still in virtual registers.
Read the pattern table itself: LLVM's lib/Target/X86/X86InstrArithmetic.td is the declarative pattern description that generates the selector.
Compare targets on the same source: Compiler Explorer with --target=aarch64-linux-gnu beside a native x86-64 build shows which instructions were a target artefact and which were the program.
Our own selector is emitAssembly in src/compilers/sim/codegen.ts, and its selection decisions are listed explicitly in the selections array shown by /compilers/codegen.

Plausible wrong readings

Stated the way a confident engineer states them.

"lea is a memory instruction, so using it for arithmetic is a hack." lea computes an address and never accesses memory. Using it for arithmetic is exactly what the instruction is for once you see it as a three-operand adder.
"The compiler picked imul so multiplication must be cheap here." The compiler picked an instruction that implements the operation under its constraints. Cost is one input among several, and the model may be a generation out of date.
"Selection is a lookup table, so it cannot be wrong." Every entry in the table is a claim that two things compute the same value for all inputs. Those claims are where miscompilations live.
"If I write the shift myself instead of the multiply, I will get better code." On any optimizing compiler you will usually get the same code, and on a signed division you will get *different* semantics — which is a bug you introduced.

Misconceptions

The claim, and what is actually true.

Each IR instruction becomes one machine instruction.

Some become none, some become one, and some become a fixed multi-instruction sequence. Division on x86-64 becomes three or four, and the count depends on the target.

The selector chooses the fastest available instruction.

It chooses the cheapest cover under a cost model that usually counts instructions or an approximate latency, and that ignores the register pressure the choice creates.

Instruction selection and register allocation are independent phases.

Fixed-register instructions like x86 division, and calling conventions that pin arguments to specific registers, mean selection hands the allocator constraints it must obey. Some backends solve both together for exactly this reason.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

The IR says "multiply this by two". The machine has several instructions that could do it and one obvious one. Selection picks. On x86-64 the answer is often an address-computation instruction, because it can write to a different register than it reads and does not disturb the flags — two things the obvious multiply cannot claim.

practical

When disassembly surprises you, ask what constraint the instruction satisfies rather than what it computes. lea for arithmetic means the selector wanted a third operand or wanted the flags intact. xor eax, eax means it wanted a zero without an immediate and without writing a dependence on the previous value. A mov before every arithmetic instruction means you are looking at unoptimized x86 and the allocator has not coalesced yet.

advanced

The honest way to see selection is as a covering problem over a DAG with a cost function that lies. Tree tiling is solvable optimally in linear time by dynamic programming; the IR is not a tree, so the tree algorithm is applied to a forest obtained by cutting the DAG at shared values, and the cuts are themselves a heuristic. On top of that, the cost model cannot see register pressure, which is often the dominant term. This gap — locally optimal tiling against a globally wrong cost — is why peephole passes, coalescing and rematerialization all exist downstream, and why integrated approaches such as PBQP-based selection keep being reinvented.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

targetEvery instruction named here is x86-64. The two-operand destructive form, the flags register as a shared resource, the lea trick and the fixed rdx:rax division operands are all x86 facts. AArch64 has three-operand arithmetic, optional flag setting (adds versus add) and a plain sdiv, so none of the four apply.

implementationThat x * 2 selects lea is true of our backend and typical of Clang and GCC at optimization levels above -O0. It is not guaranteed: at -O0 both usually emit the obvious imul, and the choice can flip between compiler versions as cost tables are retuned for newer cores.

simplifiedOur selector matches single IR instructions, not subtrees, so it cannot fire the multi-node patterns a real selector lives on — a load folded into an arithmetic operand, or a multiply-add fused into one instruction. [[tree-pattern-matching]] is the lesson that covers what we are leaving out.

If you were asked this in an interview

The IR says d = a + b and x86 add takes two operands. What does the backend emit, and what makes the extra instruction disappear later?
Why might a compiler use lea to perform an addition when add exists?
Give an example of an instruction selection that is legal for unsigned operands and a miscompilation for signed ones.

Connections

Computer Architectureinstruction-set-architecture instruction-decode instruction-level-parallelism registers

Domains that do not exist yet

Testing & Reliability Engineering — Establishing that two implementations agree on all inputs, not just the tested ones
Every selection pattern is an equivalence claim over the whole input domain. Proving those claims is what solver-aided peephole verification does, and the general technique of exhaustive equivalence testing is owned there.