Instruction Selection

Mapping IR operations to target machine instructions is not a one-to-one mapping, but a tree covering problem: using instruction patterns to match IR expression trees to find the lowest-cost covering scheme. From greedy maximal munch to dynamic programming, to automaton-based BURS.

Overview

Intermediate Representation is machine-independent—add i32 %a, %b. However, the target machine has its own instruction set: x86-64 has addl %eax, %ebx, ARM64 has add w0, w1, w2. They consider not just opcodes, but also addressing modes, register constraints, and instruction combinations. Instruction selection is the process of mapping IR operations to sequences of target machine instructions. It is not a one-to-one mapping—one IR instruction may correspond to multiple machine instructions (complex operations are decomposed), or multiple IR instructions may correspond to one machine instruction (compound addressing modes or fused instructions).

Problem Modeling: Tree Tiling

IR is organized into expression trees (each tree represents a computation, e.g., a[i] = x + 2 can be expanded into a tree). Each instruction of the target machine is also described as a tree pattern:

Instruction selection = using instruction pattern trees to cover (tile) the IR tree, such that every leaf is covered by exactly one piece, and the total cost is minimized.

This is the tree tiling problem—each instruction i has a pattern tree p_i and an execution cost c_i. The goal is to find a covering scheme that minimizes the total cost.

Three Algorithms: Increasing Cost and Precision

1. Macro Expansion: Simplest

IR operation add → directly output addl %src, %dst. It does not utilize any target machine features, resulting in significantly worse code (e.g., load + add becomes two instructions, whereas CISC has add [addr], %reg). However, it is simple to implement and is used for JIT baseline compilation or scenarios where code size is not critical.

2. Maximal Munch: Greedy, Local Optimum

Starting from the root of the tree, select the largest pattern that can cover the current subtree (most nodes), and recurse on the remaining parts:

munch(node):
    for each pattern from largest to smallest:
        if pattern matches at node:
            emit instruction for that pattern
            for each leaf in pattern that is a subtree root:
                munch(that leaf)
            return

• Greedy does not guarantee global optimality, but in practice, it is close to optimal (because machine instruction patterns usually do not "grow large enough to consume all nodes of another instruction").
• Complexity is O(n), a single pass, making it suitable for JIT compilation (e.g., V8's baseline compiler).

3. Dynamic Programming: Global Optimum

Bottom-up, calculate the "minimum cost to cover the subtree rooted at each node":

for each node n in postorder:            ← Bottom-up
    for each pattern p that matches at n:
        cost = p.cost + sum(minCost(leaf) for leaf in p.leaves)
        minCost[n] = min(minCost[n], cost)

Then, backtrack from top to bottom to select the pattern used for each node

• Guarantees finding the global optimal cover (given the set of instruction patterns and cost model).
• Complexity is O(n × |patterns|). For most IR trees and instruction sets, |patterns| is in the hundreds, which is acceptable.
• BURS (Bottom-Up Rewrite System) incorporates DP into an automaton—precomputing a "tree match to state → replacement" transition table, achieving O(n) at runtime. However, BURS construction is complex. LLVM's SelectionDAG uses DP (not strict BURS) on most targets.

Additional Complexities in Instruction Selection

Multi-Output Instructions

divmod x, y produces a quotient and a remainder with a single instruction—two IR values, one machine instruction. The tree covering model needs to be extended to DAG covering (Directed Acyclic Graph, where the same node can be shared by multiple trees), making both greedy and DP approaches more complex.

Variable-Length Instruction Sets

x86-64 has multiple encodings for the same operation: addl $1, %eax (3 bytes) vs addl $1, (%esp) (4 bytes). Instruction selection considers not just "which instruction," but also "which variant to use"—addressing mode selection becomes part of instruction selection.

Legalization

Some IR instruction combinations are not directly supported by the target machine. Before or during instruction selection, legalization must be performed:

IR:  store 64-bit value to address in reg
ARM64: Supports 64-bit store → Legal
16-bit MCU: Does not support → Decompose into two 32-bit stores (legalize)

LLVM's SelectionDAG alternates between legalization and instruction selection—the LegalizeDAG pass decomposes unsupported operations into equivalent sequences, and SelectionDAG then selects instructions.

Interference with Instruction Scheduling and Register Allocation

After instruction selection, there is instruction scheduling (reordering to reduce pipeline stalls) and register allocation (mapping IR virtual registers to a limited number of physical registers). These three phases interfere with each other:

Instruction Selection: Selects instructions → Defines register usage
Instruction Scheduling: Reorders instructions → Changes live ranges
Register Allocation: May cause spilling → Inserts load/store → Changes instruction sequence

The latter two are detailed in Register Allocation. There is a phase ordering problem between instruction selection and register allocation: should registers be allocated first and then instructions selected (potentially selecting instructions that don't use that register), or should instructions be selected first and then registers allocated (potentially finding insufficient registers after selection)? LLVM's approach is to implicitly assume "infinite virtual registers" during the SelectionDAG phase for instruction selection, and let the register allocator handle spilling later.

References

• Cooper/Torczon: "Engineering a Compiler", Chapter 11 (Instruction Selection)
• Cattell (1978): Formalization and Automatic Derivation of Code Generators (early work on tree pattern matching)
• LLVM: lib/CodeGen/SelectionDAG/ — Industrial-grade DP-based instruction selection; lib/CodeGen/GlobalISel/ — Next-generation global instruction selection

Keywords: instruction selection, tree pattern matching, tiling, maximal munch, dynamic programming, BURS, macro expansion, legalization, lowering, SelectionDAG, GlobalISel, addressing mode, multi-output instruction, instruction scheduling interference