Codegentypical

Tree Pattern Matching

Instruction selection implemented properly: tile the IR tree with instruction-shaped patterns. Maximal munch is greedy and fast; dynamic programming is optimal for the cost model; BURG-style generators write the matcher for you from a declarative table.

The question

How is instruction selection actually implemented, rather than described?

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

What the program is here

The IR viewed as a forest of expression trees — each root a value that is used more than once or that has a side effect, each leaf a register or a constant. Instructions are also trees: lea rd, [ra+rb*4] is an add(reg, mul(reg, 4)) shaped tile. Selection is then a covering of the program forest by instruction tiles, which is why this representation exists: it turns "which instruction" into a graph problem with known algorithms.

What this phase may assume or do

A tile may cover a set of IR nodes only if the instruction it represents computes exactly the value the covered subtree computes, for every input, and produces exactly the covered subtree's side effects in the same order. A tile that covers a memory load and an addition is legal only if the instruction really does perform the load — folding a load into an operand is illegal if the load may fault and the arithmetic is on a path where the fault must not occur, and illegal if the memory is volatile or shared and the number of accesses is observable.

Key points

Both the program and the instruction set are trees, so selection is a tiling problem — cover the program tree with instruction-shaped tiles.
Maximal munch is greedy, one pass, and near-optimal in practice; the DP tiler is provably optimal for the cost model and costs a second pass plus per-node cost tables.
Optimal covering is only cheap on trees. Real IR is a DAG, DAG covering is NP-complete, and production selectors cut the DAG into trees and accept the loss.
Large tiles are how addressing modes and fused operations get used at all; a one-node-one-instruction selector can never emit them.
The pattern table is written declaratively and the matcher is generated, so that the selector, assembler and scheduler all derive from one description.

Instructions are trees too

The insight that makes this tractable is that an instruction has a shape. add rd, rs is a two-node tree: an addition over two register leaves. lea rd, [rb + ri*4 + 8] is a five-node tree, an addition of a register, a scaled register and a constant. A fused multiply-add is add(mul(a, b), c). Once instructions are trees and the program is a tree, selection is tiling: cover every node of the program tree with instruction tiles, exactly once, matching shapes.

A big tile covers more program nodes with one instruction, which is usually — not always — cheaper. That is the entire tension. The greedy answer, *maximal munch*, walks from the root and always takes the largest tile that matches, then recurses on the tile's uncovered leaves. It is one pass, it is trivial to implement, and it is not optimal: taking the biggest bite at the top can leave the remaining fragments requiring more instructions than a smaller first bite would have.

The expression a[i] + 8 as an IR tree, with two possible tilings

AST — only what later phases match on

add— Tiling A covers this node alone with `add rd, 8`. Tiling B covers it together with everything below it, using one `lea`.

├── load— A memory access. Folding it into an operand is legal only if the instruction genuinely performs one access and the access cannot fault where a fault would be observable.

│ └── add

│ ├── reg a

│ └── mul— A multiply by 4 — exactly the scale field of an x86 addressing mode, which is why array indexing folds so well on this target.

│ ├── reg i

│ └── const 4

└── const 8— Fits the displacement field of an x86 addressing mode, so it costs nothing to fold. A constant that did not fit would force a separate instruction.

Read it asEight nodes. A naive one-node-one-instruction selector emits five instructions. A selector with an addressing-mode tile emits two: one mov rd, [ra + ri*4] for the load and one add rd, 8, or even a single lea when the value wanted is the address rather than the contents. The difference is entirely in how large the available tiles are.

Greedy versus optimal

typicalThat DP tiling is near-linear holds for trees. Real IR is a DAG — a value used twice is one node with two parents — and optimal DAG covering is NP-complete. Production selectors cut the DAG into trees at multiply-used values and run the tree algorithm on the pieces, which is a heuristic, not the optimum. LLVM's SelectionDAG does exactly this; its newer GlobalISel path replaces the whole approach with a matcher over generic machine instructions.

Maximal munch is greedy: largest matching tile at each step, top down. Its appeal is that it is a single recursive walk with no bookkeeping, and on most real code it produces coverage within a few percent of optimal. Its failure case is real but uncommon: a tile that covers many nodes may leave behind an operand that now needs to be materialised into a register, when a smaller tile would have left an operand that was already there.

The optimal answer is dynamic programming over the tree, and it is the same shape as every other tree DP. For each node, compute the minimum cost to produce its value in each possible storage class, given the minimum costs already computed for its children. Because a tile's cost depends only on its own cost plus the costs of the subtrees at its leaves, the optimal substructure property holds, and one bottom-up pass followed by one top-down emission pass gives a provably cheapest cover under the cost model.

"Under the cost model" is doing the work in that sentence. The DP is optimal for the numbers you gave it, and the numbers do not include register pressure, cache behavior or how the out-of-order engine will schedule the result. An optimal tiling of a wrong model is not an optimal program.

Three ways to implement selectiontypical

Approach	How it works	Cost	What it gives up
Macro expansion	One fixed sequence per IR node, no matching	O(n), trivial to write	All large tiles. Addressing modes and fused operations are never used.
Maximal munch	Largest matching tile from the root, recurse on leaves	O(n) times the table scan, one pass	Optimality. A greedy first bite can be locally largest and globally worse.
Dynamic programming	Cheapest cost per node per storage class, bottom up, then emit top down	O(n) times table size, two passes and a cost array per node	Compile time and simplicity. Also still bounded by a cost model that cannot see register pressure.

Nobody writes the matcher by hand

A pattern table for a real target has hundreds to thousands of entries and must be kept consistent with the instruction encodings, the scheduling model and the assembler. Writing the matching code by hand is both enormous and a maintenance trap, so the industry generates it. That is what BURG — bottom-up rewrite generator — and its descendants do: you write patterns and costs declaratively, and a tool generates a linear-time tiler as tables plus a small driver.

The modern versions are LLVM's TableGen, which reads .td files describing instructions, patterns, costs and constraints and generates the selector, the assembler, the disassembler and the scheduling model from the same source; and GCC's machine description files, which do the analogous job with Lisp-shaped s-expressions. In both cases the important property is that the pattern is written once and several tools are derived from it, so a new instruction cannot be selectable but not encodable.

This is the same argument as [[parser-generators]], one phase later: a declarative description plus a generator beats hand-written matching code when the description is large, changes often, and must stay consistent with other artefacts derived from it. And it has the same downside — when the generated matcher does the wrong thing, you are debugging generated code against a declarative spec, which is a genuinely worse experience than debugging a recursive function.

The shape of a declarative pattern entry (schematic, not any real tool's syntax)

1pattern  add(reg:a, mul(reg:i, const:4))
2  emits  lea  rd, [a + i*4]
3  cost   1
4  needs  target supports scaled-index addressing
5  flags  none written
6 
7pattern  add(reg:a, reg:b)
8  emits  mov  rd, a
9         add  rd, b
10  cost   2
11  flags  ZF SF OF CF written

The flags line is not decoration. It is what lets a later scheduler know that the second pattern cannot be moved between a comparison and its branch while the first can. A pattern description that records only the value computed, and not the effects, produces a selector that is correct and a scheduler that is wrong.

How it works

The steps, in the order the compiler takes them.

The IR is split into expression trees at every value with more than one use and at every operation with a side effect, since those must be materialised anyway.
Each instruction is described as a pattern tree with a cost and a set of effects — registers clobbered, flags written, memory touched.
Maximal munch: at the current root, scan the table for matching patterns, take the one covering the most nodes, emit it, and recurse on the subtrees hanging off its leaves.
Dynamic programming: bottom up, compute for each node the minimum cost of producing its value in each storage class; top down, emit the instructions that achieved those minima.
A generator turns the declarative table into either a state machine over the tree or an indexed table lookup, so the matching itself is linear in the number of nodes.

How it breaks

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

A pattern folds a load into an operand on a path where the load may fault but the arithmetic is guarded, and the program segfaults on input that the source code carefully checked for.
A pattern records the value it computes but not the flags it writes, and a comparison-and-branch pair silently becomes a branch on the wrong condition.
Two patterns overlap and the table order decides which fires, so a compiler upgrade that reorders the table changes the generated code for reasons no changelog mentions.
A DP selector on a machine-generated expression with tens of thousands of nodes takes minutes on one translation unit while the rest of the build takes seconds.
A tile is added for a new instruction without updating the scheduling model, and the scheduler assumes a latency of one for something that takes twenty cycles. The code is correct and mysteriously slow.

When it helps

Targets with rich addressing modes or fused operations — x86-64, ARM with its shifted-operand forms — where the difference between one-node tiles and large tiles is a large fraction of the instruction count.
Retargeting: a declarative table plus a generator is what makes adding a target a bounded amount of work rather than an open-ended one.
Understanding why a compiler emitted one instruction for what looked like four operations in your source.

When it hurts

Load-store RISC targets with few addressing modes, where most tiles are one node anyway and the tiling machinery buys very little over macro expansion.
When the cost model is stale. An optimal cover under 2010 latencies is not optimal on a 2026 core, and the DP will confidently produce it anyway.

What it costs

Every one of these is paid by something.

Optimal DP tiling buys the cheapest cover under the model and costs a second pass plus a cost array on every node — real compile time and real memory on large functions.
Larger tiles buy fewer instructions and cost pattern-table size, and each new pattern is a correctness obligation over all inputs plus an effects description that must stay consistent with the scheduler.
Generating the matcher declaratively buys consistency across selector, assembler and scheduler, and costs debuggability: a wrong selection is now a bug in a table interpreted by generated code rather than in a function you can step through.

What else you could do

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

Peephole-based selection, as in GCC's original design: expand naively, then apply a large table of local rewrites. The rewrites are easier to verify individually and the result depends on rewrite order in ways that are hard to reason about.
LLVM GlobalISel: lower to generic machine instructions first, then legalize, then select with a matcher over that. It handles whole functions rather than per-block DAGs and avoids the DAG-cutting heuristic, at the cost of a longer pipeline.
Selection by rewriting on an e-graph, where all equivalent forms are represented simultaneously and extraction picks the cheapest. Avoids the phase-ordering problem entirely and is far more expensive; it is used in production for tensor and kernel compilers rather than for general-purpose ones.
For a small language on a simple target, plain macro expansion plus [[peephole-optimization]] is genuinely adequate and takes an afternoon rather than a quarter.

See it for yourself

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

Read a real pattern table: LLVM's llvm/lib/Target/X86/X86InstrInfo.td and X86InstrArithmetic.td are the declarative descriptions that generate the x86 selector.
Watch the DAG being built and covered: llc -view-isel-dags file.ll renders the selection DAG before and after matching, if Graphviz is installed.
GCC's equivalent: the machine description in gcc/config/i386/i386.md, and -fdump-rtl-combine to see the peephole-style combination pass that follows expansion.
See the effect of large tiles directly: compile a[i] + 8 for x86-64 and for a load-store target such as RISC-V and count the instructions. The difference is addressing-mode tiles.

Plausible wrong readings

Stated the way a confident engineer states them.

"Maximal munch is optimal because it takes the biggest tile." Biggest first is a greedy heuristic. It can leave a remainder that costs more than a smaller first tile would have.
"The DP tiler produces the fastest code." It produces the cheapest cover for the costs it was given, and those costs do not model register pressure or the out-of-order engine.
"Tiling works on the IR, so it sees the whole function." It works on expression trees cut out of the IR. Anything spanning a multiply-used value or a basic-block boundary is outside the tile.
"A pattern is just a rewrite, so a wrong one makes the code slower." A wrong pattern makes the code *incorrect*. Patterns are equivalence claims, and the selector believes them.

Misconceptions

The claim, and what is actually true.

Pattern matching here is the same as pattern matching in a functional language.

The language feature matches one value against a set of shapes. This matches a whole tree against a set of overlapping shapes and then has to choose a minimum-cost cover among all the ways that succeed. The choice is the hard part, and the language feature has no equivalent of it.

Adding a pattern can only improve the output.

A new tile changes which cover is cheapest, which changes register pressure elsewhere, which can make the function slower. Backend teams measure after adding patterns for exactly this reason.

The selector sees the whole function.

Classic tiling sees one expression tree at a time. Anything crossing a block boundary or a multiply-used value is invisible to it, which is precisely the limitation newer whole-function selectors were built to remove.

Go deeper

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

overview

Instructions have shapes, and so do the little expression trees inside a program. Selection covers the program with instruction-shaped tiles. Bigger tiles mean fewer instructions, which is how a single x86 instruction can do an index calculation, a memory load and an addition all at once.

practical

This explains most "why is the assembly shorter than my source" moments. Array indexing collapses into an addressing mode; a multiply by a small power of two disappears into a scale field; a constant offset becomes a displacement. When it does *not* collapse, look for the reason a tile could not fire: an index that is not a power-of-two scale, a displacement too large for the field, or a load the compiler could not prove safe to fold.

advanced

The theory is clean and the practice is not. Tree tiling by DP is optimal and linear; real IR is a DAG, DAG covering is NP-complete, and cutting the DAG into trees at shared values is a heuristic whose quality nobody can characterise. On top of that, the cost function is a local scalar in a problem whose dominant global term — register pressure — is invisible to it. Every serious attempt to fix this properly, from PBQP-based integrated selection and allocation to e-graph extraction, trades a large amount of compile time for a few percent of code quality, which is why the theoretically unsatisfying version is what ships in every mainstream compiler.

How much this depends on

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

typicalTree tiling with a generated matcher describes LLVM (SelectionDAG and TableGen) and GCC (machine descriptions plus combine). It does not describe baseline JIT tiers, which use fixed templates, nor the Go compiler, whose rules are written as a large set of declarative rewrite rules applied to an SSA form rather than as a tree tiler.

targetThe addressing-mode tile [a + i*4 + 8] is x86-64, where base-plus-scaled-index-plus-displacement is a single addressing mode with scales of 1, 2, 4 and 8. AArch64 has [x0, x1, lsl #2] with a narrower set of forms, and RISC-V has only register-plus-immediate, so on RISC-V the same expression genuinely needs more instructions.

simplifiedOur own selector matches one IR instruction at a time and never covers a subtree, so it demonstrates selection decisions and not tiling. The multi-node tiles in this lesson are what a production selector does and what ours deliberately does not, which is why the tree above is drawn rather than generated.

If you were asked this in an interview

Explain maximal munch, and construct a case where it produces more instructions than necessary.
Why is optimal instruction selection cheap on a tree and intractable on a DAG, and what do real compilers do about it?
What besides the computed value must a pattern description record, and what breaks if it does not?

Connections

DSAdag dfs binary-tree

Computer Architectureinstruction-set-architecture instruction-decode