Instruction Selection

Instruction selection organizes operations from the IR into target instructions. One IR operation may expand into multiple instructions, and multiple IR computations may be merged into a single instruction. The goal is not only matching operation names but also ensuring that bit widths, sign extension, memory ordering, exceptions, and register constraints align with the semantics.

Understanding via Address Folding

Suppose you need to read a 32-bit value from base + index*4 + 8. The x86-64 addressing mode might directly accommodate the base, scaled index, and displacement, eliminating the need to compute the entire address into a temporary register first.

Whether this pattern is available depends on the scale factor, displacement range, and register constraints. If the address is also reused by multiple subsequent operations, computing the address separately might be more appropriate. LEA can compute certain address forms but does not read memory at that address; do not confuse them with load just because both write to square brackets.

Tree Covering: Selecting Combinations in a Constrained Model

Temporarily viewing pure expressions as trees, machine patterns cover a set of operations within the tree, leaving inputs that need to be generated by other patterns. Covering must implement all required operations and satisfy the representation requirements for boundary values, not just require each leaf to be covered once.

For example, add(mul(x,4),y) can be implemented using shift-and-add or a suitable LEA. Assigning a cost to each pattern creates a combinatorial optimization problem. However, cost might refer to instruction count, byte size, latency, or other estimates, which may not be consistent.

Three Selection Methods

DP states typically need to include the result category, such as whether a subtree generates a register value, an immediate, or a foldable memory operand. Using only a single number cost[node] may lose the different forms required by parent patterns.

The recurrence can be understood as:

cost(node, result_kind) = min(pattern cost + cost of required forms for each input).

After computing the costs, backtrack to find the patterns, and then generate code in dependency order. A root-first matching algorithm does not mean that machine instructions using results should be executed before those producing inputs; matching order and emission order need to be separated.

Methods like BURS can pre-calculate some tree rewriting matches, making runtime selection more efficient. This does not imply that any industrial DAG selector is solving for global optimality in the DP sense.

Giving costs a numerical value reveals whether "large patterns" are worth it

Consider add(mul(x,4),y), assuming x and y are already in registers and the result also needs to be in a register. The target machine has four legal instruction patterns: MUL4, SHL2, and ordinary ADD, as well as LEA4 which can cover the entire expression. Here, the cost is an artificially defined additive weight, not a cycle count table for any CPU model.

def select(cost):
    # The mul(x,4) subtree can be implemented by two patterns; leaves are in registers, cost is 0.
    child_cost, child = min((cost[op], (op,)) for op in ("MUL4", "SHL2"))
    candidates = [
        (child_cost + cost["ADD"], child + ("ADD",)),
        (cost["LEA4"], ("LEA4",)),
    ]
    return min(candidates)


assert select({"MUL4": 3, "SHL2": 1, "ADD": 1, "LEA4": 3}) == (2, ("SHL2", "ADD"))
assert select({"MUL4": 3, "SHL2": 1, "ADD": 1, "LEA4": 1}) == (1, ("LEA4",))

# Verify numerical results of both coverages using modulo 2^32 unsigned semantics.
mask = (1 << 32) - 1
for x in (0, 1, 1 << 30, mask):
    for y in (0, 7, mask):
        separate = (((x << 2) & mask) + y) & mask
        combined = (x * 4 + y) & mask
        assert separate == combined

With the first set of costs, LEA4, which covers the most nodes, yields a cost of 3, while the two small patterns combined only cost 2. In the second set, changing only the LEA4 cost to 1 reverses the choice. The "optimality" of dynamic programming must be understood alongside the pattern set and cost definition; this also shows that one cannot first assert an instruction is fastest and then deduce that the selector should choose it.

This small model only retains one state for register results. If the constant 4 can participate in a pattern as an immediate or be loaded into a register first, these two cases should be accounted for separately. The cost of the immediate form might be 0, but a parent pattern that only accepts registers cannot directly consume it; the instruction to materialize the constant must be added. You cannot unconditionally sum the lowest subtree numbers.

Does a larger instruction pattern always cost less?

Compare complete candidates producing the same result form. Leaves already in registers cost zero here, leaving three legal covers with invented weights. Changing LEA cost can change the optimum without changing the tree. General selectors need separate reg/imm/memory states; a parent cannot blindly reuse the lowest subtree number.

$$C(n,r)=\underset{p\Rightarrow (n,r)}{\min }\left(w(p)+\sum _{(c,r_c)\in \mathrm{inputs}(p)}C(c,r_c)\right)$$

DAGs and Side Effects: Work Beyond the Tree Model

Real IRs often have shared values. If x is used by two expressions, copying the DAG into two trees might duplicate calculations; if the duplication involves memory accesses or operations that might raise exceptions, legality depends on semantics. Multi-result instructions also need to correspond to multiple IR results simultaneously.

Dependencies between loads, stores, volatile accesses, atomics, and calls cannot be arbitrarily changed. Folding a normal load into an arithmetic instruction requires ensuring that access count, execution path, and memory semantics remain legal. Atomic operations, in particular, cannot be split into several normal reads/writes just because the target lacks a specific bit-width instruction.

Legalization: First, Express Operations in a Way the Target Supports

When the target does not support a certain integer width, vector type, or arithmetic operation, it can be extended, split, lowered to other operations, or a runtime helper function can be called. For example, wide integer addition can be split into low-bit addition and carry propagation; memory splitting also needs to consider endianness, alignment, and atomicity.

Type legalization and operation legalization may create new opportunities or requirements for each other, so backends often have multiple combining and lowering phases. LLVM's SelectionDAG and GlobalISel provide different representations and phase organizations; do not uniformly call SelectionDAG "industrial-grade global optimal DP". LLVM Code Generator, GlobalISel

Wide Integer Splitting: Cannot Just Add High and Low Halves Separately

Represent a 64-bit unsigned integer using two 32-bit words: low part a_lo and high part a_hi. When the low part sum exceeds 32 bits, a carry is generated, which must enter the high part calculation. The following model selects modulo 2^64 addition semantics; if the source language requires overflow checks, additional code must be generated to handle the final carry or corresponding overflow conditions.

mask32, mask64 = (1 << 32) - 1, (1 << 64) - 1


def add64_split(a, b):
    low_sum = (a & mask32) + (b & mask32)
    low, carry = low_sum & mask32, low_sum >> 32
    high = ((a >> 32) + (b >> 32) + carry) & mask32
    return (high << 32) | low


values = (0, 1, mask32, 1 << 32, mask64)
for a in values:
    for b in values:
        assert add64_split(a, b) == (a + b) & mask64
assert add64_split(mask32, 1) == 1 << 32

The last assertion is the easiest boundary to miss: the low half changes from all 1s to 0, and the high half must add 1. On targets supporting carry chains, instructions like ADD/ADC can be chosen; other targets might generate the carry via comparison and then add. Legalization provides the required semantics, and the specific instruction sequence is still determined by target capabilities.

This splitting is for pure register arithmetic and does not mean that a 64-bit atomic addition can be implemented as two normal 32-bit stores. The latter operation also handles atomicity observable by other threads, usually requiring target atomic sequences or runtime support. LLVM Legalizer

Where does the carry go when wide addition is split?

The low sum splits into retained bits and a carry to the high half. Two8-bit halves make that decomposition visible. The omitted-carry column is a counterexample, not an alternative correct implementation. Only the explicitly chosen modulo2¹⁶ contract permits discarding the final carry.

$$a_l+b_l=2^{8}c+l,0\le l<2^8,h=(a_h+b_h+c)\mathrm{mod}{2}^8$$

Results Determined Together with Register Allocation and Scheduling

Some x86 operations have input-output binding, and instructions like division also use implicit fixed registers. Even when using virtual registers during instruction selection, these hard constraints cannot be ignored.

Selecting a complex instruction might reduce the instruction count but increase critical path latency; early computation can hide latency but extend the value's live range, leading to spills. Load/store inserts by subsequent register allocation will further change final performance. Therefore, local pattern costs are only estimates, not complete proofs of actual processor time.

An Observable Compilation Experiment

unsigned load_element(const unsigned *a, unsigned long i) {
    return a[i + 2];
}

clang -O2 -S -masm=intel load_element.c -o load_element.s

On an x86-64 Linux target with common data layouts, you can observe whether the scale factor 4 and displacement 8 in the address are merged into the load instruction. Changing the element type, access form, or target architecture and comparing the generated results reveals the relationship between selection and target capabilities. Assembly specifics vary by version and options; do not hardcode them as the only answer.

Quick Reference

To check if a selection is reasonable, sequentially verify semantic equivalence, encoding legality, input/output register constraints, shared values and side effects, cost objectives, and the final result after register allocation.

Related chapters: Register Allocation, Target Code and ABI.

References

• LLVM Target-Independent Code Generator.
• LLVM GlobalISel.

Keywords: instruction selection, tree covering, DAG, maximal munch, BURS, legalization, addressing mode, cost model