Instruction selection

Deep dive

How it works

Parts:

• Pattern set — each target instruction as a small tree of IR operators with leaves that are "any value in a register" or an immediate; carries a cost (cycles, bytes, or both).
• Matcher — decides which patterns fit at a node (hand code, a generated decision table, or rewrite rules).
• Cover chooser — maximal munch (greedy top-down) or DP labelling (bottom-up, then top-down reduce).
• Emitter — walks the chosen cover and creates machine instructions on virtual registers, handed to register allocation.

1. Lower the IR block to expression trees. Values used more than once, side effects (stores, calls) and block edges cut a DAG into trees.
2. Match: for each node collect the patterns whose root and interior operators fit the subtree; each leaves some child subtrees uncovered.
3. Choose (munch): top-down, take the matching pattern covering the most nodes, recurse into the uncovered children. One pass, no backtracking, but a big pattern can cost more than two small ones.
4. Choose (DP, Aho-Ganapathi-Tjiang): bottom-up, cost(n) = min over matching p of cost(p) + sum cost(uncovered child). Store the winning pattern per node. Each node is labelled once.
5. Reduce: top-down from the root along the stored choices; emit children first, then the instruction.
6. Generators: BURS (Pelegri-Llopart, Graham) precomputes cost differences into automaton states so labelling is table lookups; iburg (Fraser, Hanson, Proebsting) keeps the DP and generates the matcher code from a grammar with costs.
7. DAGs: LLVM SelectionDAG builds a DAG per basic block, legalizes types and operations, combines, then matches with a TableGen-generated matcher; shared nodes are matched once, so the cover is greedy rather than optimal. GlobalISel instead selects generic machine instructions over the whole function (translate, legalize, register-bank select, select).
8. Rewrite rules: Cranelift's ISLE (a DSL compiled to Rust) states lowering as term-rewriting rules from IR terms to machine-instruction constructors, with priorities and extractors for conditions like "constant fits in 12 bits".

IR tree          Add            munch: Lea3 covers 6 nodes, cost 3
                /   \           DP:    Lea covers 4 nodes (cost 1)
             Add     8                  + AddImm (cost 1) = 2
            /   \
           a    Mul
                / \
               b   4

Code

Optimal tiling by labelling, a maximal-munch baseline, and an exact check on a hand example. The toy ISA has lea (x + y*scale, cost 1), a slow three-component lea3 (cost 3), add, add imm, mul, load and load [x+imm] (cost 4). Compiled and run with asserts.

use std::collections::HashMap;

pub enum T { Reg(&'static str), Imm(i64), Add(Box<T>, Box<T>), Mul(Box<T>, Box<T>), Load(Box<T>) }
use T::*;
fn b(t: T) -> Box<T> { Box::new(t) }

#[derive(Clone, Copy, Debug, PartialEq)]
pub enum P { Reg, MovImm, Add, AddImm, Mul, Load, LoadOff, Lea, Lea3 }
pub const PATS: [(P, u32); 9] = [ // (pattern, cost); order = tie-break
    (P::Reg, 0), (P::MovImm, 1), (P::Add, 1), (P::AddImm, 1), (P::Mul, 3),
    (P::Load, 4), (P::LoadOff, 4), (P::Lea, 1), (P::Lea3, 3), // Lea3: slow 3-component lea
];

fn imm(t: &T) -> bool { matches!(t, Imm(_)) }
fn scale(t: &T) -> bool { matches!(t, Imm(1 | 2 | 4 | 8)) }

/// If `p` matches at `t`: (subtrees left to cover, nodes covered).
fn m<'a>(p: P, t: &'a T) -> Option<(Vec<&'a T>, usize)> {
    Some(match (p, t) {
        (P::Reg, Reg(_)) => (vec![], 1),
        (P::MovImm, Imm(_)) => (vec![], 1),
        (P::Add, Add(x, y)) => (vec![x, y], 1),
        (P::AddImm, Add(x, c)) if imm(c) => (vec![x], 2),
        (P::Mul, Mul(x, y)) => (vec![x, y], 1),
        (P::Load, Load(x)) => (vec![x], 1),
        (P::LoadOff, Load(a)) => match &**a { Add(x, c) if imm(c) => (vec![x], 3), _ => return None },
        (P::Lea, Add(x, s)) => match &**s { Mul(y, k) if scale(k) => (vec![x, y], 4), _ => return None },
        (P::Lea3, Add(l, d)) if imm(d) => match &**l {
            Add(x, s) => match &**s { Mul(y, k) if scale(k) => (vec![x, y], 6), _ => return None },
            _ => return None },
        _ => return None,
    })
}

/// Bottom-up cost labelling (iburg style): best[node] = (cost, pattern), each node labelled once.
pub fn label(t: &T, best: &mut HashMap<*const T, (u32, P)>) -> u32 {
    if let Some(&(c, _)) = best.get(&(t as *const T)) { return c; }
    let mut win: Option<(u32, P)> = None;
    for &(p, pc) in &PATS {
        if let Some((kids, _)) = m(p, t) {
            let c = pc + kids.iter().map(|k| label(k, best)).sum::<u32>();
            if win.map_or(true, |(w, _)| c < w) { win = Some((c, p)); }
        }
    }
    best.insert(t as *const T, win.unwrap());
    win.unwrap().0
}

/// Maximal munch: top-down, take the matching pattern that covers most nodes.
pub fn munch_cost(t: &T) -> (u32, Vec<P>) {
    let (p, pc) = PATS.iter().copied()
        .filter_map(|(p, c)| m(p, t).map(|(_, n)| (n, p, c))).max_by_key(|&(n, _, _)| n)
        .map(|(_, p, c)| (p, c)).unwrap();
    let (kids, _) = m(p, t).unwrap();
    let mut seq = vec![];
    let mut cost = pc;
    for k in kids { let (c, s) = munch_cost(k); cost += c; seq.extend(s); }
    seq.push(p);
    (cost, seq)
}

/// Emit the DP choice in post-order (operands before the instruction using them).
pub fn emit(t: &T, best: &HashMap<*const T, (u32, P)>, out: &mut Vec<P>) {
    let p = best[&(t as *const T)].1;
    for k in m(p, t).unwrap().0 { emit(k, best, out); }
    out.push(p);
}

Hand example a + b*4 + 8: DP picks lea t,[a+b*4]; add t,8 (cost 2); munch grabs the 6-node lea3 (cost 3).

fn main() {
    let e1 = Add(b(Add(b(Reg("a")), b(Mul(b(Reg("b")), b(Imm(4)))))), b(Imm(8)));
    let mut best = HashMap::new();
    assert_eq!(label(&e1, &mut best), 2);
    let mut seq = vec![]; emit(&e1, &best, &mut seq);
    assert_eq!(seq, [P::Reg, P::Reg, P::Lea, P::AddImm]);
    let (mc, mseq) = munch_cost(&e1);
    assert_eq!(mc, 3); assert_eq!(*mseq.last().unwrap(), P::Lea3);
    assert!(2 <= mc);
}

Complexity and constants

• Labelling: each node tried against every pattern whose root operator matches, O(n * patterns) with an operator index; reduction O(n).
• Munch: O(n) but may cost more than DP; neither beats the other on shared subtrees.
• Cost drivers: pattern lookups and per-node label storage. Keep it cheap: index patterns by root operator, dense label array, never re-match a node.

Efficiency

• Cost: compile time is linear in IR size times the patterns tried per node; memory is one label (cost, pattern id) per node; bound by pointer chasing over the IR and by matcher table size. Runtime effect: instructions executed and bytes of code.
• Levers:
  • Operator-indexed patterns or a compiled decision tree — tries only plausible patterns (iburg, LLVM DAGISel matcher table) — large instruction sets.
  • Fusing address arithmetic into the load/store addressing mode — fewer instructions and no temporary register — x86 [base+index*scale+disp], AArch64 scaled and extended offsets.
  • Fusing multiply-add (madd) and shifted operands (add x0, x1, x2, lsl #3) — one instruction instead of two — AArch64.
  • Table-driven BURS states — labelling becomes lookups, no cost arithmetic at compile time (Pelegri-Llopart, Graham) — when compile speed dominates and the pattern set is fixed.
• Naive → standard → state of the art: one instruction per IR op, fixed template · fastest compile, code needs a peephole pass → maximal munch or DP tiling over trees from generated patterns · linear time, good code → DAG or whole-function selection with rewrite rules and priorities (SelectionDAG, GlobalISel, ISLE) · more compile time, shared values fused, rules verifiable.

Implementation notes

• Cut trees at multi-use values (use counts come free on SSA): duplicating a cheap load into two users is wrong if memory changes between them; only fuse when the producer has a single use and no intervening side effect.
• Costs are a model, not truth: use size at -Os, latency or throughput otherwise; target-specific cases (slow 3-component lea on some x86 cores) belong in the cost table, which is why lea3 costs more here.
• Do flags and fixed registers in selection (x86 div, shifts by cl, flag-setting adds) by emitting constraints for register allocation.
• Leave scheduling for after selection (instruction scheduling) and clean leftovers with peephole optimization.
• Immediate ranges are part of the pattern (12-bit add immediate on AArch64, 32-bit displacement on x86-64): guard with a predicate or fall back to materialising the constant.

Pitfalls

• Greedy largest-pattern choice loses to two cheaper instructions when costs are not proportional to size.
• Assuming optimality on DAGs: shared subtrees covered by two patterns duplicate work.
• Fusing a load or an operation with side effects across a store or call reorders memory.

Variants and alternatives

In production

• Language compilers: LLVM uses SelectionDAG for most targets and GlobalISel as its replacement (docs); Cranelift/Wasmtime use ISLE (post); GCC selects with machine descriptions (define_insn, internals) and RTL combine.
• GPU compilers: the AMDGPU and NVPTX back ends are LLVM code generators (AMDGPU, NVPTX).
• Databases: PostgreSQL's JIT for expression evaluation and tuple deforming is built on LLVM, whose back end selects the machine code (docs).
• Browsers: V8 baseline tiers emit fixed templates instead of selecting patterns.

Implementations

Sources

• Alfred V. Aho, Mahadevan Ganapathi, Steven W. K. Tjiang, Code generation using tree matching and dynamic programming, ACM TOPLAS 1989. paper
• Eduardo Pelegri-Llopart, Susan L. Graham, Optimal code generation for expression trees: an application of BURS theory, POPL 1988. paper
• Christopher W. Fraser, David R. Hanson, Todd A. Proebsting, Engineering a simple, efficient code-generator generator, ACM LOPLAS 1992. paper
• M. Anton Ertl, Optimal code selection in DAGs, POPL 1999. paper
• LLVM, The LLVM Target-Independent Code Generator. docs · Global Instruction Selection. docs · TableGen. docs
• Chris Fallin, Cranelift's instruction selector DSL, ISLE, 2023. post · code