Instruction Selection

The simple code generator assumed a cosy one-to-one world: each three-address operation became one target instruction. Real machines are not so tidy. A modern ISA offers dozens of instructions, many of them doing several IR operations at once — a load with a scaled-index addressing mode computes an address and fetches memory in a single opcode; a fused multiply-add does a multiply and an add. Instruction selection is the art of covering the IR with the best such instructions.

The clean way to think about it is tree tiling. Express the computation as an expression tree; give each machine instruction a tile — a little tree pattern it can implement, with a cost. Selecting instructions is then covering the whole tree with non-overlapping tiles so that every node is covered exactly once, minimising total cost. Each tile laid down becomes one emitted instruction; the edges crossing a tile's boundary become the registers that flow between instructions.

Tiles are patterns with a price

A tile is a fragment of tree — an operator with some children — annotated with the instruction it emits and its cost (cycles, or code size). A few tiles for a typical machine:

Tile (tree pattern)	Instruction	Covers	Cost
+(r, r)	`ADD Rd, Rs, Rt`	1 node	1
\times(r, r)	`MUL Rd, Rs, Rt`	1 node	1
+(r,\ \times(r,r))	`MADD Rd, Rs, Rt, Ru`	2 nodes	1
\text{MEM}(+(r, \text{const}))	`LD Rd, c(Rs)`	2 nodes	1
\text{MEM}(+(r,\ \times(r,\text{const})))	`LD Rd, (Rs,Rt,c)`	3 nodes	1

The last two are the payoff of a CISC addressing mode: a single load instruction that swallows an entire address-arithmetic subtree — a multiply-by-scale, an add of a base, a constant displacement — for the price of one. A big tile that covers three nodes at cost 1 beats three little tiles at cost 3. Instruction selection is largely a hunt for these big, cheap tiles.

Maximal munch: grab the biggest tile you can

The simplest good algorithm is maximal munch. Starting at the root, choose the largest tile that matches there — the one covering the most nodes — emit its instruction, then recurse on each subtree left dangling below the tile's leaves. It is greedy and top-down, and it runs in linear time. Below, the tree for a + b \times c is tiled: the multiply is a natural tile, but a machine with a fused multiply-add can cover the + and the \times with one big MADD tile. Reveal the tiling:

Each dashed region is one tile — one emitted instruction. The value produced by a tile leaves through its top edge as a register that the tile above consumes. Where the two-node MADD tile lands, it replaces what would have been a separate MUL then ADD — one instruction instead of two. That is exactly the win instruction selection exists to capture.

Greedy is fast; dynamic programming is optimal

Maximal munch is locally optimal — the biggest tile at each step — but not necessarily globally optimal. Grabbing a fat tile high in the tree can force awkward, expensive tiles below it, for a worse total than a slightly smaller top tile would have allowed. When you truly want the minimum-cost tiling, use dynamic programming.

compute, bottom-up, for every node the minimum cost to tile the subtree rooted there and leave its result in a register;
a node's cost is the minimum, over all tiles matching at that node, of the tile's cost plus the already-computed costs of the subtrees hanging off the tile's leaves;
because subtree costs are reused, the whole tree is tiled optimally in linear time — optimality without the exponential search.

This is the idea behind tools like BURS (bottom-up rewrite systems) and code generators such as iburg/burg: you write the tiles as a cost-annotated tree grammar, and the tool produces a linear-time, provably optimal tiler by dynamic programming over the tree. Modern compilers largely automate instruction selection this way rather than by hand-written case analysis.

A maximal-munch tiler you can run

Here is maximal munch in code. Each node is tiled by the largest matching pattern; the fused MADD tile is tried before the plain ADD, so it wins wherever a + sits directly above a \times. We tile the tree for a + b \times c and print the emitted instructions, then compare the instruction count against a small-tiles-only run.

interface Tree { op: string; name?: string; left?: Tree; right?: Tree; } const leaf = (name: string): Tree => ({ op: "leaf", name }); // a + b * c const tree: Tree = { op: "+", left: leaf("a"), right: { op: "*", left: leaf("b"), right: leaf("c") }, }; let rc = 0; const fresh = () => `R${++rc}`; // Maximal munch: at each node take the LARGEST matching tile, recurse on its leaves. function munch(n: Tree, out: string[], useFused: boolean): string { if (n.op === "leaf") { const d = fresh(); out.push(`LD ${d}, ${n.name}`); return d; } // Big tile first: + directly above * => fused multiply-add (2 nodes, 1 instruction). if (useFused && n.op === "+" && n.right?.op === "*") { const rx = munch(n.left!, out, useFused); const ry = munch(n.right.left!, out, useFused); const rz = munch(n.right.right!, out, useFused); const d = fresh(); out.push(`MADD ${d}, ${rx}, ${ry}, ${rz} ; ${d} = ${rx} + ${ry}*${rz}`); return d; } // Small tiles. const a = munch(n.left!, out, useFused); const b = munch(n.right!, out, useFused); const d = fresh(); out.push(`${n.op === "*" ? "MUL" : "ADD"} ${d}, ${a}, ${b}`); return d; } rc = 0; const fused: string[] = []; munch(tree, fused, true); console.log("Maximal munch WITH the MADD tile:"); fused.forEach((i) => console.log(" " + i)); console.log(` -> ${fused.length} instructions`); rc = 0; const small: string[] = []; munch(tree, small, false); console.log("Small tiles only (MUL then ADD):"); small.forEach((i) => console.log(" " + i)); console.log(` -> ${small.length} instructions`);

The fused run emits one fewer arithmetic instruction: the big tile paid off. Swap the tree for something whose shape doesn't match MADD and the big tile simply never fires — which is the whole point of pattern matching: tiles apply only where the tree actually has their shape.

Because an addressing mode is a big tile. Writing LD R1, 8(R2) quietly performs an add (R2 + 8) and a memory dereference in one instruction — it covers a \text{MEM}(+(r, \text{const})) subtree. An x86 lea or a scaled-index load like mov eax, [rbx + rcx*4 + 8] covers an even bigger subtree: a multiply-by-4, two adds, and (for a load) a dereference — four IR operations, one instruction. The selector's job is to notice those subtrees in the IR and reach for the fat instruction instead of emitting the arithmetic longhand. This is why CISC machines lean so heavily on a good tiling selector, and why RISC machines — with simpler, smaller tiles — make selection almost trivial but push the cleverness into scheduling and allocation instead.

"Always grab the biggest tile" feels like it must be best, but it is a greedy heuristic and greed can misfire. Suppose the biggest tile at the root covers four nodes but leaves behind two subtrees that can only be tiled by three costly instructions each; a slightly smaller top tile might have left cheaply-tileable subtrees and won on total cost. Maximal munch never reconsiders — it commits to the local maximum and recurses. When you need the genuine minimum, use the dynamic-programming tiler: it computes the optimal cost of every subtree once, bottom-up, and combines them, so a locally smaller tile is chosen whenever it leads to a globally cheaper cover. Greedy is fine for many machines and always linear; DP costs a little more machinery and buys provable optimality.