Lesson 21.5 — LLVM's SelectionDAG: build, combine, legalize, select, schedule

Techniques: DAG building and combining, type and operation legalization, matcher-table selection, SelectionDAG scheduling · Lab: labs/ch21-mir (tasks 1, 5, 6) · Prerequisites: Lessons 21.1–21.4, Ch 9 (LLVM IR types) · Time: 5–7 hours

LLVM's default instruction selector at -O1 and above on most targets is SelectionDAG. For each basic block it builds a DAG of target-independent nodes from the IR, simplifies it, rewrites every type and operation the target cannot execute into ones it can, covers the result with the target's patterns, and linearizes the chosen machine nodes into MachineInstrs. Every idea of Lessons 21.1–21.4 appears: greedy maximal munch ordered by pattern complexity, DAG matching with a single-use fold rule, and a precompiled matcher table. This lesson follows a[i] = p[3], a 128-bit add and a population count through the phases. You can watch the phases with llc flags even though the internal DAG dumps need a debug build.

flowchart LR
  IR[LLVM IR block] --> B[build<br/>SelectionDAGBuilder]
  B --> C1[combine 1]
  C1 --> LT[legalize types]
  LT --> C2[combine]
  C2 --> LV[legalize vectors]
  LV --> LO[legalize ops]
  LO --> C3[combine 2]
  C3 --> S[select<br/>matcher table]
  S --> SC[schedule]
  SC --> MI[MachineInstrs<br/>SSA MIR]

1. Problem and motivation

The input is a function in LLVM IR, after CodeGenPrepare has sunk address computations next to their uses so that one block contains what one instruction may need. The output is the function as SSA-form MIR: machine instructions of the target over virtual registers. SelectionDAG solves four subproblems in sequence. Representation: the DAG exposes every data and ordering dependence of a block, so patterns can match across IR instructions. Canonicalization: the combiner puts the DAG in forms the patterns expect. Legalization: operations on types or with semantics the target lacks are rewritten into supported ones before any pattern runs. Selection and scheduling: patterns cover the DAG, and a scheduler turns the covered DAG back into a list. The price is compile time (Lesson 21.6's GlobalISel was started partly to cut it) and a block-at-a-time view.

DAG building and combining

Building the SelectionDAG is a one-to-many translation of IR instructions into target-independent ISD nodes, done by SelectionDAGBuilder. The combiner is LLVM's descendant of Davidson–Fraser combining (Lesson 21.1): a worklist of rewrites on the DAG (mul x, 8 → shl x, 3, (x + y) − y → x) that runs four times at different legality levels. It is where much of the back end's "peephole" knowledge lives [LLVM-CodeGenDoc, LLVM-SDCombiner].

Type and operation legalization

A target supports only some value types (x86-64: i8–i64; AArch64: i32 and i64 in general registers) and some operations on them. Legalization rewrites the DAG until every node's types are legal (type legalization: promote i8 to i32, expand i128 into two i64) and every operation on those types is legal for the target (operation legalization: expand srem, call __divti3, custom-lower ctpop). The TargetLowering of each target declares its choices [LLVM-TargetLowering, LLVM-LegalizeTypes].

Matcher-table selection

The actual selection is maximal munch over the legal DAG (Lesson 21.1, §7): TableGen compiles the target's patterns into one byte-coded matcher table, ordered by pattern complexity, and SelectionDAGISel::SelectCodeCommon interprets it at every node [LLVM-SDISel].

SelectionDAG scheduling

After selection the block is still a DAG of machine nodes. A list scheduler orders them into a sequence of MachineInstrs that respects every data, chain and glue dependence. Its heuristic depends on the target: a subtarget that enables the MachineScheduler (x86-64 and AArch64 among them) gets the source scheduler, which keeps IR order where dependences allow, and the target's register-pressure (list-burr) or ILP preference applies only to subtargets that do not (createDefaultScheduler in SelectionDAGISel.cpp, LLVM 23.1.2) [LLVM-CodeGenDoc]. The detailed scheduling that uses the machine model happens later, in the MachineScheduler (Ch 23).

2. Definitions and algorithms

Definition 21.5.1 (SelectionDAG)

For a basic block \(B\), the SelectionDAG is a DAG whose nodes are operations \(o \in \mathrm{ISD} \cup \mathrm{Target}\) with a list of result value types (i64, f32, v4i32, and the special types Other for chains and Glue) and a list of operands, each a (node, result number) pair. Edges are of three kinds: data edges carry values; chain edges (type Other) order side effects (loads, stores, calls) in their original order; glue edges force two nodes to be scheduled adjacently (a compare and the branch that reads its flags). A distinguished root node, usually a TokenFactor of all final chains, keeps the block's effects alive. Values that cross blocks enter as CopyFromReg and leave as CopyToReg of virtual registers.

Definition 21.5.2 (MachineInstr, MIR)

A machine instruction is an opcode of the target (MOV64mr) or a generic pseudo (COPY, PHI) with a list of operands: register operands (a virtual register %n with a register class such as gr64, or a physical register $rdi; each a definition or a use, with flags such as killed, dead, implicit), immediates, basic-block references, global addresses and memory operands. After instruction selection the function is in SSA-form MIR: every virtual register has exactly one definition, and PHIs merge values at joins. [MIR-LangRef] specifies the textual serialization that llc -stop-after prints.

The running example as MIR

llc -mtriple=x86_64-linux-gnu -stop-after=finalize-isel selects a[i] = p[3] into %3:gr64 = MOV64rm %2, 1, $noreg, 24, $noreg and MOV64mr %0, 8, %1, 0, $noreg, killed %3. The five operands after the opcode are an x86 address: base, scale, index, displacement, segment. So MOV64mr %0, 8, %1, 0 stores to \(\%0 + 8 \cdot \%1 + 0\) (task 1 of the MIR exploration).

DAG building and combining

Algorithm 21.5.3 (Building the SelectionDAG of a block)

• Input: a basic block of LLVM IR; the registers assigned to values used across blocks.
• Output: its SelectionDAG.
• Precondition: values defined in other blocks have been assigned virtual registers (FunctionLoweringInfo).
• Postcondition: every IR instruction's effect is represented. Side effects are ordered by one chain in program order. Every value used outside the block is copied to its register.
• Invariant: NodeMap[v] is the DAG value computing IR value \(v\); Chain is the last side-effecting node.

function BuildDAG(block):
    Chain ← EntryToken
    for each instruction I in block, in order:
        operands ← [ Get(v) for v in operands(I) ]
        switch I:
            load:  n ← LOAD(Chain, operands); Chain ← n.chain
            store: n ← STORE(Chain, value, address); Chain ← n
            call:  n ← target's LowerCall(Chain, operands); Chain ← n.chain
            GEP:   n ← ADD/MUL/SHL nodes computing base + Σ index·size
            other: n ← the ISD node for the opcode (ADD, SHL, ...)
        NodeMap[I] ← n
        if I is used in another block: Chain ← CopyToReg(Chain, reg(I), n)
    Root ← TokenFactor(Chain, all pending CopyToRegs); lower the terminator

function Get(v):
    if v in NodeMap: return NodeMap[v]
    if v is a constant: return Constant(v)
    return CopyFromReg(EntryToken, reg(v))        # defined in another block

Algorithm 21.5.4 (DAG combining)

• Input: a SelectionDAG; a legality level (before legalization, after type legalization, after vector legalization, after operation legalization).
• Output: an equivalent, simpler DAG.
• Precondition: every combine rule is a semantics-preserving rewrite. At a legality level after legalization, rules may only create legal nodes.
• Postcondition: no rule applies to any live node (a fixed point), and the DAG computes the same values and effects.
• Invariant: every node that may match a rule is on the worklist or has been visited since its last change. Replaced nodes are deleted when they lose their last use.

function Combine(DAG, level):
    W ← all nodes, in topological order
    while W is not empty:
        N ← pop(W)
        if N has no uses: delete N; push its operands onto W; continue
        R ← generic rules for opcode(N)             # visitADD, visitMUL, ...
        if R = none: R ← target's PerformDAGCombine(N)
        if R ≠ none and R ≠ N:
            replace all uses of N by R
            push R and the users of R onto W       # they may now match
            delete N and push its dead operands onto W

Proposition 21.5.5 (Combining preserves meaning; it terminates only under a measure)

If every rule preserves the values and effects of the node it replaces, Algorithm 21.5.4 returns an equivalent DAG. If moreover every rule strictly decreases a well-founded measure \(\mu\) of the DAG (for example, the multiset of node "costs" under the multiset ordering), it terminates. Without such a measure it need not: two rules that undo each other loop forever.

Proof

Equivalence by induction on the number of rewrites. Each rewrite replaces all uses of \(N\) by an \(R\) computing the same value (and, for chained nodes, the same effect in the same chain position). The rest of the DAG reads the same values, so the whole DAG's meaning is unchanged. Deleting nodes without uses does not change the meaning, except for chained nodes, which remain reachable from the root through the chain. Termination. Each rewrite decreases \(\mu\) by assumption, and deleting dead nodes also decreases it. Every loop iteration either rewrites, deletes, or pops without change, and a pop without change shrinks \(W\). So the pair (\(\mu\), \(\lvert W \rvert\)) decreases lexicographically, and a well-founded order admits no infinite descent. Non-termination: rules \(x \cdot 2 \to x + x\) and \(x + x \to x \cdot 2\) would reinsert each other's result forever. LLVM avoids such pairs by fixing canonical forms (shifts over multiplications by powers of two), a convention rather than a checked property.

Type and operation legalization

Definition 21.5.6 (Legalization actions)

A target assigns (i) to every value type a type action: Legal, PromoteInteger (to the next larger legal integer type), ExpandInteger (into two halves), SoftenFloat, ExpandFloat, ScalarizeVector, SplitVector or WidenVector; and (ii) to every pair (operation, legal type) an operation action: Legal, Promote (perform in a larger type), Expand (rewrite into other operations), LibCall (call a runtime routine) or Custom (call the target's LowerOperation hook). These are TargetLoweringBase::LegalizeTypeAction and LegalizeAction in llvm/include/llvm/CodeGen/TargetLowering.h, set by setOperationAction in each target's constructor [LLVM-TargetLowering].

Algorithm 21.5.7 (Type legalization)

• Input: a DAG whose nodes may produce or consume illegal types.
• Output: an equivalent DAG in which every value has a legal type.
• Precondition: every illegal type has a type action whose results are "closer to legal" (Theorem 21.5.9): a promotion lands on a legal type, and an expansion or split halves the width.
• Postcondition: no value of illegal type is used (Theorem 21.5.9).
• Invariant: each processed node's illegal results have been replaced by legal ones or by pairs of values of smaller types, which are recorded in maps (PromotedIntegers, ExpandedIntegers, …) and used by the node's users.

function LegalizeTypes(DAG):
    W ← nodes in topological order (operands before users)
    while W is not empty:
        N ← pop(W)
        for each result type T of N that is illegal:
            switch TypeAction(T):
                PromoteInteger: N' ← the same operation on the promoted type, operands
                                promoted (sign/zero/any-extend as the operation needs);
                                record Promoted[N] ← N'
                ExpandInteger:  (Lo, Hi) ← ExpandIntRes_<op>(N)      # e.g. ADD →
                                record Expanded[N] ← (Lo, Hi)       # UADDO + UADDO_CARRY
                SplitVector, WidenVector, SoftenFloat, ...: analogous
            push the new nodes onto W
        for each operand of N whose producer was replaced:
            rewrite the operand to use the recorded replacement (an operand-side rule,
            e.g. an i128 STORE becomes two i64 STOREs)
    remove the dead original nodes

Algorithm 21.5.8 (Operation legalization)

• Input: a type-legal DAG.
• Output: an equivalent DAG in which every node is Legal for its types.
• Precondition: the target's Expand, Promote and Custom lowerings only produce nodes whose legalization is "smaller" (Theorem 21.5.9).
• Postcondition: every node has action Legal (or is a target node, which is legal by definition).
• Invariant: nodes are processed users-last. A replacement's new nodes are legalized before the users of the node they replace.

function LegalizeOps(DAG):
    for each node N in topological order:
        switch OperationAction(opcode(N), type(N)):
            Legal:   continue
            Promote: R ← extend operands, perform in the promoted type, truncate
            Expand:  R ← ExpandNode(N)       # e.g. SREM → SUB(a, MUL(SDIV(a, b), b))
            LibCall: R ← a call to the runtime routine (RTLIB), with the ABI's lowering
            Custom:  R ← target's LowerOperation(N); if R is empty: act as for Expand
        replace N by R; legalize the new nodes of R first (recursively)

Theorem 21.5.9 (Legalization terminates with a legal DAG under a ranking)

Suppose there is a rank \(\rho\) from (operation, type) pairs to a well-founded order such that every non-Legal action replaces a node \(N\) by nodes of strictly smaller rank, and every type action replaces a value of illegal type \(T\) by values whose types are legal or of smaller width (\(T\) promotes to a legal type). Then Algorithms 21.5.7 and 21.5.8 terminate, and afterwards every node is legal.

Proof

Consider the multiset of ranks of all non-legal nodes (for types: the multiset of widths of illegal values). Every step removes one element and adds only strictly smaller elements, or none. By the Dershowitz–Manna theorem, the multiset ordering over a well-founded order is well-founded, so only finitely many steps are possible, and the algorithms stop. They stop only when no non-legal node or illegal value remains: the worklists are exhausted, and every node was either Legal or replaced. For type legalization the base case is concrete: promotion lands on a legal type in one step, and expansion halves a width, which can happen only \(\log_2(\text{width}/64)\) times for integers (i256 → two i128 → four i64). The hypothesis is not automatic. A target that expands operation \(A\) into \(B\) and \(B\) into \(A\) violates it, and LLVM's legalizer asserts or loops on such a target.

Legalizing a 128-bit add on x86-64

add i128 %a, %b: the type i128 is illegal on x86-64 and its action is ExpandInteger. DAGTypeLegalizer::ExpandIntRes_ADDSUB splits both operands into (lo, hi) halves and builds lo = UADDO(a.lo, b.lo), which produces a sum and a carry, and hi = UADDO_CARRY(a.hi, b.hi, carry). Both are on the legal type i64. The operation legalizer then finds x86 patterns for them, which select ADD64rr and ADC64rr (task 5 of the MIR exploration).

Matcher-table selection

Algorithm 21.5.10 (Matcher-table interpretation, SelectCodeCommon)

• Input: a legal DAG; the target's matcher table (a byte array generated by TableGen); the target's Select hook.
• Output: every node replaced by machine nodes (opcodes of the target).
• Precondition: the patterns in the table are sorted by decreasing complexity (Lesson 21.1 §7).
• Postcondition: for every node, the first pattern in table order that matches (with all its predicates, ComplexPattern callbacks and fold legality checks) has replaced it. If none matches and Select did not handle the node, compilation aborts with "Cannot select".
• Invariant: nodes are selected from the root towards the leaves (DoInstructionSelection walks the topologically sorted DAG backwards), so a node's users are selected before it and folds into users are already decided.

function DoInstructionSelection(DAG):
    for each node N in reverse topological order:
        if N is dead or already a machine node: continue
        if target's Select(N) handled it: continue       # custom C++ for hard cases
        SelectCodeCommon(N, MatcherTable)

function SelectCodeCommon(N, T):
    pc ← 0; scopes ← []; recorded ← []
    loop:
        op ← T[pc]
        switch op:
            OPC_Scope:        push (pc of next alternative, |recorded|) onto scopes
            OPC_SwitchOpcode: jump to the case for opcode(N) or fail
            OPC_CheckOpcode, OPC_CheckType, OPC_CheckPredicate, OPC_CheckComplexPat:
                              test the current node; on failure goto Fail
            OPC_RecordChild_i, OPC_MoveChild_i, OPC_MoveParent: navigate and record operands
            OPC_CheckFoldableChainNode: fail unless IsProfitableToFold and IsLegalToFold
            OPC_EmitInteger, OPC_EmitConvertToTarget: create operands
            OPC_MorphNodeTo:  replace N (and folded nodes) by the machine node; return
        continue
    Fail:
        if scopes is empty: report "Cannot select: N"; abort
        (pc, k) ← pop(scopes); truncate recorded to k; resume at pc

Proposition 21.5.11 (What the matcher table computes)

For a node \(N\), Algorithm 21.5.10 selects the pattern that comes first in the TableGen order (decreasing complexity, then TableGen's tie-break) among those that match \(N\) and pass their predicates and fold checks. So it is maximal munch (Algorithm 21.1.8) on the DAG with "complexity" as the size and with the fold rule of Algorithm 21.4.6.

Proof

The table is a decision tree whose leaves are pattern emissions. DAGISelEmitter builds it from the list of patterns sorted by getPatternComplexity, merges common prefixes into OPC_Scope alternatives in that order, and factors opcode tests into OPC_SwitchOpcode. The factoring (in DAGISelMatcherOpt.cpp) only merges or reorders tests that belong to mutually exclusive patterns, so it does not change which pattern matches first. The interpreter tries the alternatives of each scope in order and backtracks on failure, so it reaches a pattern's emission only if no earlier alternative on the same path succeeded. The first emission reached is therefore the first matching pattern in sorted order. Fold checks are ordinary failing tests. If every alternative fails, the scope stack empties and the selector reports failure, the "Cannot select" of the postcondition.

SelectionDAG scheduling

Algorithm 21.5.12 (Bottom-up list scheduling of the selected DAG)

• Input: the selected DAG of a block; a priority function (source order, register reduction, ILP, …).
• Output: a sequence of machine instructions.
• Precondition: the DAG is acyclic, which Algorithm 21.5.10's IsLegalToFold guarantees (Lesson 21.4 §4).
• Postcondition: the sequence is a topological order of the data, chain and glue edges, with glued nodes adjacent (Proposition 21.5.13).
• Invariant: Available holds exactly the unscheduled nodes whose users have all been scheduled. The sequence built so far, reversed, is a suffix of a valid order.

function ListScheduleBottomUp(DAG, priority):
    Seq ← []; Available ← { nodes with no users }          # the root
    while Available is not empty:
        N ← the node in Available with the best priority(N)
        remove N (and every node glued to it, as one unit) from Available
        prepend the unit to Seq
        for each operand M of the unit:
            if all users of M are now scheduled: add M to Available
    return Seq

Proposition 21.5.13 (Any list schedule is a valid order)

Algorithm 21.5.12 schedules every node exactly once, in an order where every node comes after all its operands (data, chain and glue) and glued nodes are adjacent. Every such order computes the block's values and performs its effects in the original order.

Proof

A node enters Available only when all its users are scheduled, and it is prepended, so it ends up before all of them. That is a topological order of the edges reversed, which is a topological order of the DAG. Every node becomes available eventually: the DAG is acyclic, so by induction on the longest path to the root, every node's users are all scheduled at some point. Glued units are emitted together by construction. Meaning: data edges ensure every operand is computed before its use. The chain is a single path through all side-effecting nodes (Definition 21.5.1), so a topological order keeps them in program order. Nodes without edges between them are independent pure computations, and their relative order does not matter.

3. Worked example

DAG building and combining

f(x, y) = ((x * 8) + y) − y (the comb.ll box of §7). Building gives SUB(ADD(MUL(x, 8), y), y). Combine 1 runs visitSUB first, bottom-up in topological order:

step	node	rule applied	result
1	MUL(x, 8)	multiply by a power of two → shift	SHL(x, 3)
2	ADD(SHL(x, 3), y)	none	—
3	SUB(ADD(s, y), y)	\((a + b) - b \to a\) (visitSUB)	SHL(x, 3)
4	the dead ADD	deleted, operands pushed	—
5	worklist empty	fixed point	SHL(x, 3)

Selection then covers SHL(x, 3) with x86's LEA64r (scale 8, no base), which is leaq (,%rdi,8). With -combiner-disabled the same function needs imulq, addq and subq.

Type and operation legalization

The four functions of the wide.ll box in §7, on both targets:

function	node	x86-64: type action → op action	AArch64: type action → op action	selected
add128	ADD i128	ExpandInteger → UADDO / UADDO_CARRY on i64 (legal)	same	ADD64rr + ADC64rr; ADDSXrr + ADCXr
div128	SDIV i128	ExpandInteger → libcall (ExpandIntRes_SDIV)	same	call __divti3 on both
add8	ADD i8	i8 Legal → ADD Legal	PromoteInteger to i32 → ADD i32 Legal	ADD8rr; ADDWrr
pop	CTPOP i64	Legal type → CTPOP Custom (no POPCNT): bit-twiddling sequence	Legal type → CTPOP Custom (no CSSC): NEON CNT + ADDV	16 x86 instructions; CNTv8i8 + ADDVv8i8v

The operation actions come from the X86TargetLowering and AArch64TargetLowering constructors (setOperationAction(ISD::CTPOP, MVT::i64, Custom) in both, under !Subtarget.hasPOPCNT() and !Subtarget->hasCSSC()).

Try it

./course drill legalization --seed 4 --difficulty hard --solution asks for type and operation actions on both targets and explains each from the constructors. Task 5 of labs/ch21-mir has you read the same results from llc.

Matcher-table selection

Selecting STORE(ADD(a, SHL(i, 3)), LOAD(ADD(p, 24))) on x86-64, visiting nodes from the root:

step	node	first matching pattern (complexity)	effect
1	STORE	(st GR64:$src, addr:$dst) → MOV64mr (22)	addr is a ComplexPattern: selectAddr folds ADD(a, SHL(i, 3)) into base a, index i, scale 8
2	LOAD	(ld addr:$src) → MOV64rm	selectAddr folds ADD(p, 24) into base p, displacement 24
3	ADD, SHL, ADD	—	now dead (all their uses were folded), so they are deleted, not selected

The result is two instructions, MOV64rm and MOV64mr, as in the MIR box of Definition 21.5.2.

SelectionDAG scheduling

dot(p, q) = p[0]·q[0] + p[1]·q[1] (the sched.ll box). Selection folds each q load into an IMUL64rm. The selected DAG has two independent chains {MOV64rm p[0], IMUL64rm q[0]} and {MOV64rm p[1], IMUL64rm q[1]}, joined by ADD64rr. -pre-RA-sched=source keeps IR order (both loads, then both multiplies). list-burr (register reduction) and list-ilp put the p loads first and then swap the two multiplies, because the multiply of p[1] consumes the value loaded last and so frees its register sooner. linearize emits each chain completely before the other. All four are topological orders (Proposition 21.5.13).

4. Invariants and correctness

DAG building and combining

Proposition 21.5.5 is the correctness condition. It puts the burden on each combine being sound, which is where LLVM's miscompilations tend to live. Many combines mirror InstCombine rewrites, which Alive2 can check at the IR level (Ch 13), but the DAG rules themselves are not verified. The termination half relies on canonical forms: the combiner has no built-in termination proof, and a generic combine and a target combine that undo each other make it loop, a known class of LLVM bugs.

Type and operation legalization

Theorem 21.5.9 gives termination and legality under the ranking hypothesis. A second invariant is semantic: promotion must extend operands the way the operation needs (signed division promotes with sign extension, unsigned with zero extension, addition with "any" extension, since the high bits do not affect the low bits of a sum). Getting this wrong is a classic legalizer bug: promoting sdiv i8 with zero extension gives wrong results for negative operands.

Matcher-table selection

Proposition 21.5.11 says the selector is complete relative to the patterns: every legal node that some pattern (or Select) covers is selected. A legal node that no pattern covers aborts with "Cannot select", and the §7 box triggers this on purpose. Soundness is per pattern: each pattern must compute the same value as the DAG it replaces. TableGen type-checks patterns (Lesson 21.8) but cannot prove them correct.

SelectionDAG scheduling

Proposition 21.5.13. Glue is the one non-obvious edge. On x86, a CMP sets EFLAGS and a JCC reads it, with no virtual register in between. Glue keeps them adjacent so nothing that clobbers EFLAGS can be scheduled between them.

5. Complexity

Variables: \(n\) nodes in a block's DAG, \(e\) edges, \(\lvert T \rvert\) the matcher table size in bytes, \(k\) the number of combine rules tried per node.

Technique	Time (worst)	Time (typical)	Space	Justification
DAG building	\(O(n + e)\)	linear	\(O(n + e)\)	one visit per IR instruction
DAG combining	unbounded without a measure (Proposition 21.5.5)	\(O(k n)\) per combine run, 4 runs	\(O(n)\) worklist	each node is revisited when its operands change
Type and operation legalization	\(O(n \cdot \mathrm{expansion})\); an \(i2^k\) value expands into \(2^{k-6}\) i64s	linear	\(O(n)\)	Theorem 21.5.9's measure bounds the steps
Matcher-table selection	\(O(n \cdot \lvert T \rvert)\) per node in the worst case (backtracking over all scopes)	\(O(n \cdot d)\), \(d\) the table depth reached	the table, 627 KB for x86	OPC_SwitchOpcode makes the first test a jump
List scheduling	\(O(n \log n)\) with a priority queue	\(O(n \log n)\)	\(O(n)\)	each node enters and leaves Available once

A pathological family. A block with \(m\) independent chains of memory operations, or a huge switch lowered into one block, makes the DAG as large as the block. Since SelectionDAG works per block, an enormous block (generated code with thousands of statements) costs superlinear time in the combiner's use lists and in the findNonImmUse searches of fold checks. LLVM caps some of these searches (-has-predecessor-max-steps) for exactly this reason.

Real-world scale. The x86 matcher table generated from LLVM 23.1.2's .td files is 626,914 bytes and contains 27,595 pattern entries (the §7 box). SelectionDAG is typically one of the most expensive parts of llc at -O2. Compile-time reduction was one of the stated goals of GlobalISel [LLVM-GISel].

6. Variants and refinements

DAG building and combining

• Target combines (PerformDAGCombine): targets add rewrites that only make sense for them (x86 LEA formation, AArch64 CSEL tricks). This adds power at the price of ordering interactions with generic rules.
• Per-level legality gates: combines check LegalOperations / LegalTypes so that post-legalization combines never create illegal nodes. This is safe, but some combines are then missed late.
• Combining on MIR instead (GlobalISel combiners, Lesson 21.6): the same rules on generic MIR. Cross-block combines become possible.

Type and operation legalization

• Vector legalization (LegalizeVectors, split, widen, scalarize): the vector analogue of type legalization, run between the two type-legalization phases.
• Custom lowering (LowerOperation): an escape hatch for operations a target can do cleverly (AArch64 CTPOP through NEON). It is powerful but opaque to the generic legalizer's reasoning.
• Legalize before combining vs after: SelectionDAG legalizes types, then combines, then legalizes operations. GlobalISel legalizes in one pass with a rule table (Lesson 21.6). The latter is simpler to reason about but loses combines between the steps.

Matcher-table selection

• AddedComplexity: a target raises a pattern's rank to prefer it (priority munch). Easy to use, easy to get wrong.
• ComplexPattern (addr on x86): a C++ matcher for sub-DAGs that do not fit the pattern language (addressing modes). It is flexible but invisible to TableGen's type inference.
• Custom Select: C++ selection for nodes whose patterns TableGen cannot express. Large targets use it for many opcodes (x86's X86DAGToDAGISel::Select is a long switch).

SelectionDAG scheduling

• Scheduler choice (-pre-RA-sched=source|list-burr|list-ilp|list-hybrid|fast|linearize): source is the default at -O0 and on every subtarget that enables the MachineScheduler (x86-64 and AArch64: llc 23.1.2 without -pre-RA-sched emits exactly the source order of the box below); the target's Sched::RegPressure, Hybrid or ILP preference picks list-burr, list-hybrid or list-ilp only on subtargets without it.
• Defer to MachineScheduler: most targets now schedule seriously after selection with the machine model (Ch 23), so on those targets this scheduler mainly linearizes the DAG in IR order.

7. In real compilers

DAG building and combining

SelectionDAGBuilder::visit in llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp builds the DAG. DAGCombiner::Run, DAGCombiner::combine and the visit* functions (visitADD, visitMUL, …) in DAGCombiner.cpp combine it. SelectionDAGISel::CodeGenAndEmitDAG in SelectionDAGISel.cpp runs the phases in the order of the diagram at the top of this lesson (LLVM 23.1.2) [LLVM-SDISel, LLVM-SDCombiner].

The DAG combiner at work, and without it

Reproduce (llc 23.1.2; -combiner-disabled is a hidden llc option):

cat > comb.ll <<'EOF'
define i64 @f(i64 %x, i64 %y) {
  %a = mul i64 %x, 8
  %b = add i64 %a, %y
  %c = sub i64 %b, %y
  ret i64 %c
}
EOF
llc -O2 -mtriple=x86_64-linux-gnu comb.ll -o - | grep -vE '^\s*\.|^#|^$|# -- '
llc -O2 -mtriple=x86_64-linux-gnu -combiner-disabled comb.ll -o - | grep -vE '^\s*\.|^#|^$|# -- '

Output (complete after the filter):

f:                                      # @f
    leaq    (,%rdi,8), %rax
    retq
f:                                      # @f
    imulq   $8, %rdi, %rax
    addq    %rsi, %rax
    subq    %rsi, %rax
    retq

What to notice: the first run is the §3 trace. The combiner turns the multiply into a shift and cancels + y − y, and selection then picks lea for the shift (an addressing mode used as arithmetic). With the combiner disabled, the selector faithfully covers every node: imul with an immediate, add, sub. The selector does no algebra of its own; canonical forms and simplifications are the combiner's job.

The SelectionDAG phases, observed with -time-passes

Reproduce (llc 23.1.2; wide.ll is the input of the next box; the timings vary from run to run, so the grep keeps only the phase names):

llc -O2 -mtriple=x86_64-linux-gnu -time-passes wide.ll -o /dev/null 2>&1 \
  | sed -n '/Instruction Selection and Scheduling/,/  Total$/p' | grep -oE '[A-Z][A-Za-z0-9 ]+$' | sort

Output (complete):

DAG Combining 1
DAG Combining 2
DAG Combining after legalize types
DAG Legalization
Instruction Creation
Instruction Scheduling
Instruction Scheduling Cleanup
Instruction Selection
Instruction Selection and Scheduling
Total
Type Legalization
Vector Legalization

What to notice: these are the NamedRegionTimers of CodeGenAndEmitDAG, one per box of the pipeline diagram: combine, legalize types, combine, legalize vectors, legalize operations ("DAG Legalization"), combine 2, select, schedule, and "Instruction Creation" (emitting MachineInstrs). The combine after vector legalization is missing because nothing was vector-legalized in this file.

Type and operation legalization

SelectionDAG::LegalizeTypes and the DAGTypeLegalizer in llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp and LegalizeIntegerTypes.cpp (ExpandIntRes_ADDSUB, PromoteIntRes_SimpleIntBinOp), SelectionDAG::Legalize and SelectionDAGLegalize::LegalizeOp in LegalizeDAG.cpp. The actions are set in X86TargetLowering::X86TargetLowering (llvm/lib/Target/X86/X86ISelLowering.cpp) and AArch64TargetLowering::AArch64TargetLowering (LLVM 23.1.2) [LLVM-LegalizeTypes, LLVM-X86ISelLowering].

Four legalization outcomes on two targets

Reproduce (llc 23.1.2; the grep keeps function names and instructions, dropping copies and call-frame pseudos):

cat > wide.ll <<'EOF'
define i128 @add128(i128 %a, i128 %b) {
  %s = add i128 %a, %b
  ret i128 %s
}
define i128 @div128(i128 %a, i128 %b) {
  %q = sdiv i128 %a, %b
  ret i128 %q
}
define i8 @add8(i8 %a, i8 %b) {
  %s = add i8 %a, %b
  ret i8 %s
}
define i64 @pop(i64 %x) {
  %p = call i64 @llvm.ctpop.i64(i64 %x)
  ret i64 %p
}
declare i64 @llvm.ctpop.i64(i64)
EOF
for t in x86_64-linux-gnu aarch64-linux-gnu; do
  echo "== $t"
  llc -O2 -mtriple=$t -stop-after=finalize-isel wide.ll -o - \
    | grep -E '^name:|^    (%[0-9]+:|[A-Z])' | grep -vE 'COPY|ADJCALLSTACK|IMPLICIT_DEF|INSERT_SUBREG' \
    | sed -E 's/, implicit.*//; s/ :: .*//'
done

Output (complete):

== x86_64-linux-gnu
name:            add128
    %4:gr64 = ADD64rr %0, %2
    %5:gr64 = ADC64rr %1, %3
    RET 0, $rax, $rdx
name:            div128
    CALL64pcrel32 target-flags(x86-plt) &__divti3, csr_64
    RET 0, $rax, $rdx
name:            add8
    %4:gr8 = ADD8rr %3, killed %2
    RET 0, $al
name:            pop
    %1:gr64 = SHR64ri %0, 1
    %2:gr64 = MOV64ri 6148914691236517205
    %3:gr64 = AND64rr %1, killed %2
    %4:gr64 = SUB64rr %0, killed %3
    %5:gr64 = MOV64ri 3689348814741910323
    %6:gr64 = AND64rr %4, %5
    %7:gr64 = SHR64ri %4, 2
    %8:gr64 = AND64rr %7, %5
    %9:gr64 = ADD64rr %6, killed %8
    %10:gr64 = SHR64ri %9, 4
    %11:gr64 = ADD64rr %9, killed %10
    %12:gr64 = MOV64ri 1085102592571150095
    %13:gr64 = AND64rr %11, killed %12
    %14:gr64 = MOV64ri 72340172838076673
    %15:gr64 = IMUL64rr %13, killed %14
    %16:gr64 = SHR64ri %15, 56
    RET 0, $rax
== aarch64-linux-gnu
name:            add128
    %4:gpr64 = ADDSXrr %0, %2
    %5:gpr64 = ADCXr %1, %3
    RET_ReallyLR implicit $x0
name:            div128
    BL &__divti3, csr_aarch64_aapcs
    RET_ReallyLR implicit $x0
name:            add8
    %2:gpr32 = ADDWrr %0, %1
    RET_ReallyLR implicit $w0
name:            pop
    %2:fpr64 = CNTv8i8 killed %1
    %3:fpr8 = ADDVv8i8v killed %2
    RET_ReallyLR implicit $x0

What to notice: each row of the §3 table. ExpandInteger turns the 128-bit add into add + add-with-carry on both machines (ADCXr reads the carry flag ADDSXrr sets), and the 128-bit division into a call. i8 is a legal type on x86 (ADD8rr on 8-bit registers) but is promoted to i32 on AArch64 (ADDWrr). CTPOP is Custom on both: x86's lowering without POPCNT is the classic bit-parallel count (the constants are 0x5555…, 0x3333…, 0x0f0f… and 0x0101…), while AArch64's goes through the vector unit (CNT counts bits per byte, ADDV sums the bytes). (RET_ReallyLR implicit $x0 for add128 is cut by the sed after the first implicit, which is why $x1 does not show.)

Matcher-table selection

TableGen's DAGISelEmitter (llvm/utils/TableGen/DAGISelEmitter.cpp), DAGISelMatcherGen.cpp and DAGISelMatcherOpt.cpp build the table. SelectionDAGISel::SelectCodeCommon interprets it, and SelectionDAGISel::DoInstructionSelection drives it (LLVM 23.1.2) [LLVM-DAGISelEmitter, LLVM-SDISel].

The real x86 matcher table, and a node no pattern covers

Reproduce (llvm-tblgen and llc 23.1.2; the first part fetches the X86 target and llvm/include at the tag, about 80 MB on disk, and needs network access to GitHub):

git clone --filter=blob:none --no-checkout --depth 1 --branch llvmorg-23.1.2 \
  https://github.com/llvm/llvm-project llvm-src
cd llvm-src && git sparse-checkout set llvm/lib/Target/X86 llvm/include/llvm && git checkout -q && cd ..
llvm-tblgen -gen-dag-isel -I llvm-src/llvm/include -I llvm-src/llvm/lib/Target/X86 \
  llvm-src/llvm/lib/Target/X86/X86.td -o X86GenDAGISel.inc
grep -c 'Src:' X86GenDAGISel.inc
grep 'Total Array size' X86GenDAGISel.inc
grep -B1 'Dst: (ADD64rm:' X86GenDAGISel.inc | grep 'Src:' | sed -E 's/:\{ \*:\[(i64|iPTR)\] \}//g; s/^ +//' | head -2
cat > bad.ll <<'EOF'
declare void @llvm.x86.sse2.pause()
define void @spin() {
  call void @llvm.x86.sse2.pause()
  ret void
}
EOF
llc -O2 -mtriple=aarch64-linux-gnu bad.ll -o /dev/null 2>&1 | head -1

Output (complete):

27595
  }; // Total Array size is 626914 bytes
// Src: (add GR64:$src1, (ld addr:$src2)<<P:Predicate_unindexedload>><<P:Predicate_load>>) - Complexity = 25
// Src: (add (ld addr:$src2)<<P:Predicate_unindexedload>><<P:Predicate_load>>, GR64:$src1) - Complexity = 25
LLVM ERROR: Cannot select: intrinsic %llvm.x86.sse2.pause

What to notice: the real table holds 27,595 patterns in 627 KB of bytecode. ADD64rm is the load-folding tile of Lesson 21.4, with complexity 25 (a load inside an add), so it is tried before the plain ADD64rr. The fold is still subject to IsProfitableToFold at the OPC_CheckFoldableChainNode step. The last line is Proposition 21.5.11's failure case: an x86-only intrinsic reaching the AArch64 selector matches no pattern, and llc aborts.

SelectionDAG scheduling

ScheduleDAGSDNodes (ScheduleDAGSDNodes.cpp) builds scheduling units from the selected DAG. The list schedulers are in ScheduleDAGRRList.cpp (source, list-burr, list-hybrid, list-ilp) and ScheduleDAGFast.cpp (fast, linearize). InstrEmitter creates the MachineInstrs (LLVM 23.1.2) [LLVM-SDISel].

Four pre-RA schedulers on the same selected DAG

Reproduce (llc 23.1.2; -enable-misched=false keeps the later machine scheduler from reordering; the output is right after instruction selection anyway):

cat > sched.ll <<'EOF'
define i64 @dot(ptr %p, ptr %q) {
  %p1 = getelementptr inbounds i64, ptr %p, i64 1
  %q1 = getelementptr inbounds i64, ptr %q, i64 1
  %a0 = load i64, ptr %p, align 8
  %b0 = load i64, ptr %q, align 8
  %a1 = load i64, ptr %p1, align 8
  %b1 = load i64, ptr %q1, align 8
  %m0 = mul i64 %a0, %b0
  %m1 = mul i64 %a1, %b1
  %s = add i64 %m0, %m1
  ret i64 %s
}
EOF
for s in source list-burr list-ilp linearize; do
  echo "== $s"
  llc -O2 -mtriple=x86_64-linux-gnu -pre-RA-sched=$s -enable-misched=false \
    -stop-after=finalize-isel sched.ll -o - | sed -n '/^body/,$p' \
    | grep -v "COPY\|^\s*$\|body\|bb.0\|liveins\|^\.\.\."
done

Output (complete):

== source
    %2:gr64 = MOV64rm %0, 1, $noreg, 0, $noreg :: (load (s64) from %ir.p)
    %3:gr64 = MOV64rm %0, 1, $noreg, 8, $noreg :: (load (s64) from %ir.p1)
    %4:gr64 = IMUL64rm %2, %1, 1, $noreg, 0, $noreg, implicit-def dead $eflags :: (load (s64) from %ir.q)
    %5:gr64 = IMUL64rm %3, %1, 1, $noreg, 8, $noreg, implicit-def dead $eflags :: (load (s64) from %ir.q1)
    %6:gr64 = ADD64rr %4, killed %5, implicit-def dead $eflags
    RET 0, $rax
== list-burr
    %2:gr64 = MOV64rm %0, 1, $noreg, 0, $noreg :: (load (s64) from %ir.p)
    %3:gr64 = MOV64rm %0, 1, $noreg, 8, $noreg :: (load (s64) from %ir.p1)
    %4:gr64 = IMUL64rm %3, %1, 1, $noreg, 8, $noreg, implicit-def dead $eflags :: (load (s64) from %ir.q1)
    %5:gr64 = IMUL64rm %2, %1, 1, $noreg, 0, $noreg, implicit-def dead $eflags :: (load (s64) from %ir.q)
    %6:gr64 = ADD64rr %5, killed %4, implicit-def dead $eflags
    RET 0, $rax
== list-ilp
    %2:gr64 = MOV64rm %0, 1, $noreg, 0, $noreg :: (load (s64) from %ir.p)
    %3:gr64 = MOV64rm %0, 1, $noreg, 8, $noreg :: (load (s64) from %ir.p1)
    %4:gr64 = IMUL64rm %3, %1, 1, $noreg, 8, $noreg, implicit-def dead $eflags :: (load (s64) from %ir.q1)
    %5:gr64 = IMUL64rm %2, %1, 1, $noreg, 0, $noreg, implicit-def dead $eflags :: (load (s64) from %ir.q)
    %6:gr64 = ADD64rr %5, killed %4, implicit-def dead $eflags
    RET 0, $rax
== linearize
    %2:gr64 = MOV64rm %0, 1, $noreg, 0, $noreg :: (load (s64) from %ir.p)
    %3:gr64 = IMUL64rm %2, %1, 1, $noreg, 0, $noreg, implicit-def dead $eflags :: (load (s64) from %ir.q)
    %4:gr64 = MOV64rm %0, 1, $noreg, 8, $noreg :: (load (s64) from %ir.p1)
    %5:gr64 = IMUL64rm %4, %1, 1, $noreg, 8, $noreg, implicit-def dead $eflags :: (load (s64) from %ir.q1)
    %6:gr64 = ADD64rr %3, killed %5, implicit-def dead $eflags
    RET 0, $rax

What to notice: the same five selected instructions (each q load folded into IMUL64rm) in three different orders. Every order respects the data dependences (Proposition 21.5.13), and the virtual register numbers follow emission order, which is why they change between runs. linearize emits one product completely before the other and keeps one fewer value live at a time.

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
DAG building and combining	exposes all dependences of a block; canonicalizes and simplifies (Proposition 21.5.5)	linear build; combine linear per run in practice, 4 runs	good code depends on it (the -combiner-disabled box); combine bugs are silent miscompiles	high: thousands of rules in DAGCombiner.cpp	every SelectionDAG target
Type and operation legalization	makes any IR type and operation executable (Theorem 21.5.9)	linear in practice	predictable per target; custom lowerings can be very good (NEON CNT)	high per target: action tables plus LowerOperation	every SelectionDAG target; the legalization drill
Matcher-table selection	greedy munch by complexity on DAGs (Proposition 21.5.11)	\(O(n \cdot d)\); x86 table 627 KB	near-optimal on common code; "Cannot select" when uncovered	patterns are declarative (TableGen); Select for the rest	every SelectionDAG target
SelectionDAG scheduling	any topological order; heuristics for pressure or ILP	\(O(n \log n)\)	modest effect since MachineScheduler runs later	low (choose a scheduler)	linearization before register allocation

• Choose SelectionDAG when you write an LLVM back end today and want the most mature path: every in-tree target supports it, and its combiner and legalizer carry decades of target knowledge.
• Prefer GlobalISel (Lesson 21.6) when compile time matters, you need to select across basic blocks, or your target (AArch64, AMDGPU, RISC-V) has invested in it.

9. Assessment

Technique	Quiz ids (solutions/quizzes/ch21.yaml)	Drill	Flashcard tag	Exercises
DAG building and combining	sdag-phase-order, combiner-disabled	none: combines are rule-specific; the quiz asks for the phase order and a combine's effect	sdag-combine	E5 task 6
Type and operation legalization	legalize-x86-i128, legalize-a64-i8	./course drill legalization	legalization	E5 task 5
Matcher-table selection	llvm-where-selectcodecommon, matcher-order	./course drill munch-tiling (the same greedy principle)	matcher-table	E5 tasks 1–2
SelectionDAG scheduling	sched-topological, sched-glue	none: any topological order is valid, so the quiz checks the constraints instead	sdag-schedule	—

Looking for the DAG in -print-after-all

-print-after-all prints IR before instruction selection and MIR after it, never the SelectionDAG itself: the DAG exists only inside the X86 DAG->DAG Instruction Selection pass. Its dumps (-debug-only=isel) and graph views (-view-isel-dags) need an LLVM built with assertions and, for the views, a GUI. With a release llc, observe the phases through their effects instead: -print-isel-input (the IR that enters), -stop-after=finalize-isel (the MIR that leaves), and flags such as -combiner-disabled and -pre-RA-sched, as in the boxes above.

References

See the chapter references.