Why is instruction selection usually described as tiling the intermediate representation with machine instructions?
answer
- many small operations, one instruction
- patterns with costs, not a dictionary
- cover the graph, no gaps
- cheapest cover over a tree
- leaves register constraints behind
basics
~20 sBecause one machine instruction can implement several operations of the intermediate form at once. Selection covers the operation graph with patterns, each pattern standing for one instruction and carrying a cost, and looks for a cheap cover rather than a one-to-one translation.
solid answer
~40 sThe intermediate form is deliberately simple: small operations such as add, multiply and load. Real instruction sets are not — one instruction may multiply and add together, or fold a base, an index, a scale and an offset into a single memory access. So the mapping is many-to-one, and the pass is framed as **covering**: each available instruction is a pattern, or tile, matching a shape of operations and carrying a cost; selection chooses a set of tiles that covers the whole graph with no gaps and no overlaps. Over a tree, dynamic programming finds a minimum-cost cover; over a graph with shared values it is harder, and a greedy largest-match-first walk is common. Selection also leaves constraints behind — instructions that demand particular registers — which allocation must then respect.
go deeper
Recall that the intermediate form's operations are simpler than real machine instructions, so the final mapping is not one for one.
Explain covering with costed patterns, and why one instruction absorbing several operations is what makes the problem a search rather than a lookup.
Connect it to the rest of the back end: the constraints selection hands the allocator, and why instruction choice, scheduling and allocation cannot all be optimal at once.
Weigh the cost model itself — what latency, size and pressure should be worth to each other, and how much compile time a better cover is allowed to consume.
## Two vocabularies that do not line up The machine-independent part of a pipeline works on a small, regular instruction set of its own: add, multiply, compare, load, store, branch. Keeping it small is what makes the optimisation passes tractable — folding, elimination and motion each have a handful of cases to reason about. A real target's instruction set is neither small nor regular. It typically contains instructions that do several of those small operations in one step: - an instruction that multiplies two values and adds a third; - an addressing mode that computes a base plus an index times a scale plus an offset as part of a load; - an instruction that compares and branches together; - an instruction that shifts one operand as part of an arithmetic operation. So translation is not a dictionary lookup. A **single** machine instruction may implement **several** nodes of the intermediate form, and frequently there are many correct ways to do it. ## Covering, and why it is called tiling Each instruction the target offers is described as a **pattern**: a small shape of intermediate operations it can implement, with a cost attached — roughly its latency, or its size, or a blend. Selection then has to cover the operation graph so that every node is inside exactly one tile and no tile is missing an operand its shape requires. The picture is a floor covered with tiles of different shapes: many tilings fit, and the cheapest one is wanted. 1. **Over an expression tree**, a bottom-up dynamic program is exact: for each node compute the cheapest cover of the subtree rooted there, for each way a tile could match at that node, and combine upwards. 2. **Over a graph with shared values**, where one computed value feeds two consumers, exactness gets much harder, because a tile that absorbs the shared node may force it to be recomputed for the other consumer. 3. **Greedy selection** takes the largest tile that matches at the current node and moves on — the same longest-match instinct used elsewhere in the pipeline. It is fast, simple, and usually close enough. | approach | shape it handles | result | |---|---|---| | bottom-up dynamic programming | expression trees | minimum cost for that tree | | greedy largest-tile-first | trees and graphs | fast, near-optimal in practice | | cost-driven search over a graph | shared values | better, and markedly slower | ## What selection is not It is easy to confuse selection with the optimisation passes before it. The distinction is worth holding: - **Optimisation** decides *what work the program does*: which computations exist at all, how often they run, where they run. - **Selection** takes that decided work and chooses *which instructions express it*. It does not delete work, hoist it or reorder it. That is also why selection sits late. It maps onto one target's instruction set, so everything downstream of it is target-specific, and structural information the earlier passes needed has usually already been lowered away by the time it runs. ## What it hands to the rest of the back end Selection is not the last word. It leaves two things behind for the passes after it: - **Register constraints.** Some instructions require their operands or results in particular registers, and calling conventions pin others. Those become fixed nodes the allocator must colour around rather than choose freely. - **Scheduling latitude.** The chosen instructions have latencies and resource requirements, and the order they are issued in is a separate decision — one that, like motion, can lengthen live ranges and cost a spill. The three back-end concerns — which instructions, in which order, using which registers — are mutually dependent, and every real compiler picks an order to decide them in and accepts that the result is not jointly optimal. Selection first is the usual choice, because the cost model needs to know which instructions exist before anything else can be weighed.
- Why is selecting a minimum-cost cover harder on a graph than on an expression tree?Because a value with two consumers can be absorbed into a tile chosen for one of them, and the other consumer then either recomputes it or forces a different tiling. On a tree every node has exactly one consumer, so subtree costs compose cleanly and a bottom-up dynamic program is exact. Sharing breaks that composition, so practical selectors use heuristics.
- What does instruction selection leave for the register allocator to deal with?Constraints. Some chosen instructions demand their operands or results in specific registers, and the calling convention fixes which registers survive a call. Those appear as pre-coloured nodes in the interference graph, which the colouring must work around rather than assign freely, and they can force a spill that an unconstrained graph would not have needed.
saying these in an interview costs you the question
- Thinks each intermediate operation maps to exactly one instruction.
- Believes selection also removes or reorders work.
- Says tiles are chosen without any cost model.
- Assumes a greedy cover is always minimum-cost.
- Ignores the register constraints selection creates.