Instruction Selection as Tree Tiling

The last phase of a compiler that still knows what the source program meant is also the first phase that must speak in the vocabulary of a particular processor. Between those two points sits instruction selection, and the standard way to describe it is as a covering problem: the intermediate representation is a forest of expression trees, each machine instruction corresponds to a small tree pattern, and selection chooses a set of patterns whose union covers every node exactly once.

That framing is useful because it separates three questions that are easy to conflate. Which patterns exist is a property of the instruction set. Which covers are legal is a property of the operands and the register file. Which legal cover is chosen is a property of a cost model. Getting the first two right is correctness; getting the third right is quality.

Patterns Are Partial Trees

A pattern is a tree fragment with operands left open. On a load-store architecture, the pattern for a register-register add is a node labelled add with two register leaves. The pattern for a load is a node labelled load whose child is an address expression. The pattern for a load with a scaled index is larger: a load over an add over a mul by a constant that happens to be a legal scale factor.

The intermediate representation supplies the input tree. In a three-address form the tree has to be rebuilt from definitions, because the flat instruction list has already split the expression into separate named results. A definition with exactly one use can be folded into the use site, which reconstitutes the subtree the pattern matcher wants. A definition with two uses cannot be folded without duplicating work, so it stays as a leaf that the pattern matches as a register. This reconstruction step is where instruction selection and redundancy elimination interfere with each other, a conflict taken up in Maximal Munch and Dynamic-Programming Tiling.

Patterns are usually written declaratively rather than as code. A machine description lists, for each instruction, the operator it implements, the shape of its operands, the register class of its result, and any immediate range it accepts. Table generators turn those descriptions into a matcher, so that adding an instruction means adding a pattern rather than editing the selector. GCC machine descriptions and the LLVM instruction definitions serve this role in two large production compilers, and both have accumulated special cases where a pattern could not express the constraint and hand-written code had to take over.

A toy description makes the shape concrete. The notation below is illustrative, not any real tool’s syntax:

add   r, r, r          cost 1
addi  r, r, imm12      cost 1     ; imm12 in [-2048, 2047]
load  r, [r + imm12]   cost 3     ; base register plus signed offset
lea   r, [r + r<<s]    cost 1     ; s in {0,1,2,3}
mul   r, r, r          cost 3

Each line is a pattern with a fixed arity. The lea pattern covers two IR nodes at once — an add whose child is a shift — together with the leaves those nodes consume, which is the entire point: one machine instruction replaces the pair.

Covering and Cost

A cover assigns every node of the input tree to exactly one pattern, such that each pattern’s internal nodes are matched by that pattern and no pattern overlaps another. The root of the tree must be covered by some pattern, and the leaves of every chosen pattern must themselves be roots of other patterns or leaves of the input.

The number of covers grows quickly. For a chain of additions over distinct leaves, a selector with patterns of arity one, two, and three has a tiling count that satisfies a three-term linear recurrence, so it grows exponentially in the length of the chain. That count is why the covering is computed with dynamic programming over the tree rather than by enumeration: at each node, the cheapest cover of the subtree rooted there is the minimum over all patterns rooted at that node of the pattern’s cost plus the sum of the cheapest covers of the subtrees hanging below it. Because the subproblems are the subtrees, and because a tree has no sharing, the recursion is a straightforward post-order traversal with a table of best costs per node.

The cost model is where the honesty of the exercise lives. Counting instructions is the simplest metric and it is wrong in interesting ways. A single instruction that reads memory and adds has a longer latency than a register add, so an instruction count treats a slow operation as cheap. A pattern that uses an immediate avoids a materialization, which saves an instruction and a register simultaneously. On a machine with a branch delay slot, filling the slot with a useful instruction costs nothing while leaving it empty costs a nop. Cost is therefore usually a small vector — instructions, cycles, and sometimes bytes — and the comparison between covers is a weighted sum whose weights are guesses about the target microarchitecture.

There is a second reason the cost model cannot be exact. The cover is chosen before register allocation, and the cost of a cover depends on how many registers it needs and how long it holds them. Two covers with equal instruction counts can differ substantially in pressure, and the selector cannot know which will spill. This is the same phase-ordering problem that reappears in scheduling, and it is the reason production compilers revisit selection decisions after allocation in limited ways rather than trusting the first pass completely.

Legality Is Not Cost

A pattern that matches structurally may still be illegal. Three constraints recur.

The first is register class. A pattern may require its operand in a specific class — an address register, a floating-point register, a pair of adjacent registers for a wide value. If the IR value is in a different class, the selector must insert a copy, and the copy is a real instruction that the cost model did not account for.

The second is immediate range. The pattern for addi accepts a 12-bit signed immediate on several RISC architectures. A constant of 5000 does not fit, so the pattern fails even though the tree shape matches. The selector has three options: materialize the constant in a register and use the register form, split the constant into a shifted high part and a low part with two instructions, or let the constant be placed in a literal pool in memory and load it. Each is legal; which is cheapest depends on whether the constant is reused, which is a property of the whole function rather than of the tree being tiled.

The third is side effects and trapping. A load pattern is legal only if the address is known not to fault, or if faulting at that point is acceptable. Folding an address computation into a load ties the arithmetic to the access: the computation now executes exactly where the load does, so it can no longer be hoisted out of a loop or above a branch on its own, and if the load is speculated the arithmetic is speculated with it. If the address can be invalid, that changes which programs trap and where the trap is reported. Selectors handle this by refusing to fold loads across control flow unless the load is marked as safe to speculate, a condition discussed in If-Conversion, Predication, and the Limits of Speculation.

Legality checks also depend on the operand being a compile-time constant. A mul by a power of two can become a shift, and a mul by a small constant can become a shift-and-add sequence, but only when the multiplier is visible at selection time. When the multiplier arrives in a register, the pattern for a general multiply is the only legal choice, and the optimization has to wait for a later pass that can prove the value constant.

What the Tile Cannot See

Tiling is a local decision procedure. It sees one tree, and it prices each pattern in isolation. Several costs are invisible from that vantage point.

Register pressure is the largest. A cover that keeps intermediate results in registers is cheaper than one that spills, but spilling is decided later, and the selector’s cost model usually has no term for it. Compilers approximate by preferring covers that produce fewer live values, which is a heuristic with no guarantee.

Instruction cache behaviour is the second. A cover with more, smaller instructions may occupy more bytes than a cover with fewer, larger ones, and on a fetch-bound workload the byte count matters more than the instruction count. Some cost models include a size term for exactly this reason, weighted by a profile-derived estimate of which functions are hot.

Scheduling freedom is the third. Fusing three IR nodes into one instruction reduces the instruction count but also removes two scheduling slots: the fused operation is now a single indivisible unit with one latency. A cover that leaves the operations separate gives the scheduler more to interleave. This tension is the same one that makes VLIW compilers prefer unfused, explicitly parallel code, and it explains why the boundary between instruction selection and scheduling is drawn differently on different targets.

The practical resolution in most compilers is to make selection produce correct code with a reasonable cost model, then let scheduling and register allocation repair the damage. Selection is hard to undo later because it commits to opcodes, so its mistakes are the expensive ones. That asymmetry, rather than any property of the tiling algorithm itself, is why machine descriptions are maintained so carefully.