Lesson 21.6 — GlobalISel and FastISel

Techniques: FastISel; the GlobalISel pipeline (IRTranslator, Legalizer, RegBankSelect, InstructionSelect); GlobalISel combiners · Lab: labs/ch21-mir (tasks 3, 4, 8) · Prerequisites: Lesson 21.5 (SelectionDAG, MIR) · Time: 4–5 hours

SelectionDAG is thorough but slow, and it sees one basic block at a time. LLVM has two other selectors that trade differently. FastISel is built for -O0: it walks the IR once and emits machine instructions directly, one IR instruction at a time. It handles the common cases and hands anything harder to SelectionDAG. GlobalISel replaces the DAG with generic MIR: machine instructions with target-independent opcodes (G_ADD, G_LOAD) over typed virtual registers. It lowers them in four passes (translate, legalize, choose register banks, select) that run on the whole function, and combiners between them do the simplification work. On AArch64, GlobalISel is the default at -O0, and it selects a[i] = p[3] into the same two instructions SelectionDAG does. On x86-64 it is still incomplete, and there it produces four instructions for the same input.

1. Problem and motivation

The problem is the same as in Lesson 21.5: LLVM IR in, SSA-form MIR out. The constraints differ. At -O0 the goal is compile speed and debuggability: selection should be close to linear with a small constant and keep IR instructions recognizable. For optimized builds, SelectionDAG's per-block view blocks selection across blocks (folding a compare into a branch in another block, choosing register banks with a global view), and building and throwing away a DAG per block is expensive [LLVM-GISel].

FastISel

FastISel appeared in LLVM 2.x (2008) as a fast path for -O0. It selects most instructions by table lookup on (IR opcode, type), with small hand-written target hooks for loads, stores, calls and addresses (X86FastISel, AArch64FastISel). It falls back to SelectionDAG for anything it does not handle. In the terms of Lesson 21.1, it is macro expansion with a few local folds [LLVM-FastISel].

GlobalISel pipeline

GlobalISel was proposed in 2015 (Quentin Colombet's design at the LLVM Developers' Meeting) and became AArch64's -O0 default in LLVM 7. Its goals, stated in the documentation, are performance (faster than SelectionDAG), granularity (the whole function as the unit, not a block), and modularity (separate, reusable passes that can be tested one at a time on MIR). It reuses SelectionDAG's TableGen patterns for its final selection step [LLVM-GISel, Col25, Ch. 14–17].

GlobalISel combiners

The DAG combiner's work (canonicalize, fold, simplify) is done in GlobalISel by combiner passes run before and after legalization. Their rules are written as TableGen GICombineRules with a match part (MIR patterns plus C++ predicates) and an apply part [LLVM-GISel-Combine]. Because they operate on MIR with use-def chains across the whole function, they can combine across block boundaries.

2. Definitions and algorithms

Definition 21.6.1 (Generic MIR, LLTs, register banks)

Generic MIR is MIR whose instructions may use target-independent generic opcodes (G_ADD, G_PTR_ADD, G_LOAD, G_CONSTANT, …, listed in llvm/include/llvm/Target/GenericOpcodes.td) and whose virtual registers carry a low-level type (LLT) instead of a register class: a scalar of \(n\) bits (printed i64 or s64), a pointer in address space \(a\) (p0), or a vector. A register bank is a set of register classes that can hold the same values without copies (AArch64: gpr and fpr). During selection a virtual register goes from %5:_(i64) (type only) to %5:gpr(i64) (type and bank) to %5:gpr64 (register class, generic type gone). An instruction is selected when its opcode is a target opcode.

Definition 21.6.2 (Legalizer rule table)

For each generic opcode and each type index, a target declares an ordered list of rules \((\text{predicate on types}, \text{action})\), with actions Legal, NarrowScalar, WidenScalar, FewerElements, MoreElements, Bitcast, Lower, Libcall, Custom or Unsupported. The action of an instruction is that of the first rule whose predicate holds for its types. Example (AArch64, getActionDefinitionsBuilder({G_ADD, G_SUB, …})): .legalFor({i32, i64, v8i8, …}).widenScalarToNextPow2(0).clampScalar(0, s32, s64). So G_ADD on i32 or i64 is legal, i8 is widened to i32, and i128 is narrowed.

FastISel

Algorithm 21.6.3 (FastISel with fallback)

• Input: a basic block of LLVM IR; the target's FastISel hooks.
• Output: machine instructions for the block.
• Precondition: the function's arguments and the block's PHI inputs could be lowered (otherwise the whole function falls back).
• Postcondition: every instruction is selected, by FastISel or by SelectionDAG (Proposition 21.6.4).
• Invariant: the instructions after the current position (the block is walked bottom-up) are selected. Values defined in the block have virtual registers in ValueMap.

function FastSelectBlock(block):
    BI ← end(block)
    while BI ≠ begin(block):
        I ← instruction before BI
        if I is dead or was folded into a later instruction: BI ← BI − 1; continue
        if SelectInstruction(I):                       # table lookup + target hooks
            BI ← BI − 1
            if the instruction before I is a load with one use and
               target's TryToFoldLoad(load, I) succeeds:     # e.g. into ADD64rm
                skip the load
            continue
        if I is a call: select I alone with SelectionDAG; BI ← BI − 1; continue
        select [begin(block), BI) with SelectionDAG        # hand over the rest
        return

function SelectInstruction(I):
    if I is a terminator: first emit copies for successor PHIs, or fail
    return SelectOperator(I) or target's FastSelectInstruction(I)

Proposition 21.6.4 (FastISel with fallback is complete and correct)

If every target hook emits code equivalent to the instruction it selects, then Algorithm 21.6.3 produces a correct selection for every block that SelectionDAG can select.

Proof

Each instruction is handled by exactly one of three paths: FastISel (correct by the hypothesis on hooks), a single-instruction SelectionDAG block for a call, or SelectionDAG for the remaining prefix. SelectionDAG is correct and complete for the prefix whenever it can select the block at all. The values that cross between the parts go through virtual registers recorded in ValueMap, which both selectors read and write, so the parts compose like separately selected blocks. Folding a load into its single user is correct because the load is immediately before the user (no intervening store) and has no other use.

GlobalISel pipeline

Algorithm 21.6.5 (The GlobalISel pipeline)

• Input: a function in LLVM IR; the target's CallLowering, LegalizerInfo, RegisterBankInfo and InstructionSelector.
• Output: selected SSA MIR (no generic opcodes, register classes on all virtual registers).
• Precondition: the target implements the four components for the constructs in the function (otherwise -global-isel-abort decides between an error and a fallback to SelectionDAG).
• Postcondition: after each pass its invariant holds for the whole function: translated → legal → banked → selected (Theorem 21.6.6).
• Invariant: each pass only moves instructions forward along that order and verifies its postcondition (the MachineVerifier checks it in assertion builds).

function GlobalISel(F):
    IRTranslator(F)          # IR → generic MIR, one IR instruction at a time;
                             # calls and arguments through CallLowering (the ABI)
    PreLegalizerCombiner(F)  # optional: canonicalize (mul by 2^k → shl, ...)
    Legalizer(F)
    PostLegalizerCombiner(F) # optional
    RegBankSelect(F)
    InstructionSelect(F)

function Legalizer(F):
    W ← all instructions
    while W not empty:
        MI ← pop(W)
        switch Action(MI):                          # Definition 21.6.2
            Legal: continue
            NarrowScalar(T'): split each value into pieces of type T' (G_UNMERGE_VALUES),
                              operate on the pieces (G_ADD → G_UADDO + G_UADDE),
                              rebuild (G_MERGE_VALUES)
            WidenScalar(T'):  G_ANYEXT/G_SEXT/G_ZEXT the operands to T', operate, G_TRUNC
            Lower:            rewrite in terms of other generic instructions
            Libcall:          emit a call; Custom: target's legalizeCustom(MI)
        push the new instructions onto W
        ArtifactCombine: fold G_TRUNC(G_ANYEXT x) → x, G_UNMERGE(G_MERGE ...) → ..., and so on

function RegBankSelect(F):
    for each instruction MI (in a reverse post-order of the blocks):
        M ← the target's cheapest instruction mapping for MI (a bank per operand), given
            the banks already assigned to its operands (Greedy mode: compare several)
        for each operand whose assigned bank differs from M: insert a repair COPY
        assign M's banks to MI's definitions

function InstructionSelect(F):
    for each block, for each instruction MI from last to first:
        if MI is generic:
            select(MI) via the TableGen-imported patterns (GIMatchTable), which may fold
            single-use generic definitions (e.g. G_PTR_ADD, G_SHL) into MI's operands,
            or via the target's C++ select(); on failure: fall back or abort

Theorem 21.6.6 (Legalizer termination and the pipeline's guarantees)

(a) If every non-Legal action produces instructions that are strictly smaller in a well-founded order (narrowing and widening move types towards the legal set, lowerings use "simpler" opcodes, as in Theorem 21.5.9), the Legalizer terminates, and afterwards every instruction is Legal. (b) After RegBankSelect every virtual register has exactly one bank, and every instruction's operands are in banks its mapping accepts. (c) After InstructionSelect no generic opcode remains, or the function was sent to the fallback.

Proof

(a) As in Theorem 21.5.9: the multiset of (rank of each non-legal instruction) decreases under the multiset ordering at every step, and the artifact combines only delete instructions or replace a pair by a simpler one. The loop ends only with an empty worklist, and every popped instruction was either legal or replaced. (b) Each definition is assigned the bank of the chosen mapping exactly once, because instructions are visited once and each virtual register has one definition (SSA). A use whose bank differs from what the mapping needs gets a repair COPY into a new virtual register of the right bank, so every operand ends up in an accepted bank. (c) InstructionSelect visits every instruction. For a generic one it either replaces it with target instructions (a pattern or C++ select) or reports failure, which, depending on -global-isel-abort, is an error or a fallback to SelectionDAG for the whole function.

GlobalISel combiners

Definition 21.6.7 (GlobalISel combine rule)

A combine rule is a pair (match, apply): match is a MIR pattern rooted at a definition ((G_MUL $d, $op1, $op2)) together with a C++ predicate that may compute data (matchinfo), and apply rewrites the matched instructions using that data. A combiner is a pass that applies a set of rules to a worklist until no rule matches. Examples in llvm/include/llvm/Target/GlobalISel/Combine.td: mul_to_shl (G_MUL x, 2^k → G_SHL x, k), sub_to_add (G_SUB x, C → G_ADD x, −C).

Algorithm 21.6.8 (Combiner pass)

• Input: generic MIR; a rule set; a position in the pipeline (pre- or post-legalizer).
• Output: equivalent generic MIR.
• Precondition: each rule preserves semantics. After legalization, rules must produce legal instructions (the post-legalizer combiners check legality).
• Postcondition: no rule matches any instruction (a fixed point), as for Algorithm 21.5.4.
• Invariant: every instruction that may match is on the worklist. An observer adds created and changed instructions (and the users of changed registers) to it.

function Combiner(F, rules):
    W ← all instructions, in a post-order of the blocks
    repeat:
        changed ← false
        while W not empty:
            MI ← pop(W)
            if MI is trivially dead: erase MI; continue
            for each rule r whose root opcode is opcode(MI), in priority order:
                if r.match(MI, info): r.apply(MI, info); changed ← true; break
    until not changed (or a pass-specific iteration limit is reached)

3. Worked example

FastISel

The sum loop of task 6 (labs/ch21-mir/inputs/sum.ll) at -O0. The loop block has phi, phi, getelementptr, load, add, add, icmp and br. FastISel walks it bottom-up:

step	IR instruction	outcome
1	br i1 %c, …	the target hook sees that %c is an icmp with one use and emits CMP64rr + JCC_1 together (the compare is marked folded)
2	%c = icmp slt	skipped: folded in step 1
3	%i1 = add i64 %i, 1	ADD64ri32 (immediate form, from the table)
4	%s1 = add i64 %s, %x	selected as an add; the instruction before it is %x = load with one use, so tryToFoldLoad rewrites it to ADD64rm with the address
5	%x = load	skipped: folded
6	%p = getelementptr	skipped: folded into the address of step 4
7	the two phis	not selected by FastISel. PHIs are created from the IR phis, and each predecessor's terminator copies the incoming values

The result has ADD64rm, ADD64ri32, CMP64rr and JCC_1 in the loop, one instruction per IR operation except where a local fold applies (the §7 box shows it).

GlobalISel pipeline

a[i] = p[3] on AArch64 with -global-isel (the outputs are in §7):

after	the address a + 8·i	the load	register classes
IRTranslator	%6 = G_CONSTANT 8; %7 = G_MUL %1, %6; %8 = G_PTR_ADD %0, %7	%5 = G_LOAD %4 with %4 = G_PTR_ADD %2, 24	_ (types only)
pre-legalizer combiner	%10 = G_CONSTANT 3; %7 = G_SHL %1, %10 (mul_to_shl)	unchanged	_
Legalizer	unchanged: everything is legal on i64/p0	unchanged	_
RegBankSelect	all operands gpr	gpr	banks only
InstructionSelect	folded into STRXroX %5, %0, %1, 0, 1 (register offset, shift 3)	LDRXui %2, 3 (unsigned offset 24/8)	gpr64, gpr64sp

InstructionSelect visits G_STORE first (bottom-up). Its imported pattern (store GPR64:$Rt, (ro_Xindexed64 GPR64sp:$Rn, GPR64:$Rm, ro_Xextend64:$extend)) matches through the single-use G_PTR_ADD and G_SHL, which then become dead.

Legalizer on wide.ll (AArch64):

function	before (IRTranslator)	rule (Definition 21.6.2)	after
add8	G_TRUNCs to i8, %4:_(i8) = G_ADD, G_ANYEXT to i32	widenScalarToNextPow2/clampScalar(0, s32, s64): widen to i32	%8:_(i32) = G_ADD %2, %3; the G_TRUNC/G_ANYEXT pairs are cancelled by the artifact combiner
add128	G_MERGE_VALUES of two i64 halves, then G_ADD on i128	clampScalar: narrow to i64	%13, %19 = G_UADDO %2, %4 and %15, %18 = G_UADDE %3, %5, %19 (the carry %19 links them)

GlobalISel combiners

mul_to_shl on the IRTranslator output above: the match pattern (G_MUL $d, $op1, $op2) matches %7 = G_MUL %1, %6, and matchCombineMulToShl checks that %6 is a constant power of two (8) and stores \(\log_2 8 = 3\) in matchinfo. The apply creates %10 = G_CONSTANT i64 3 and rewrites the instruction to %7 = G_SHL %1, %10. The old G_CONSTANT 8 becomes dead and is erased on its next pop. A second pass over the worklist finds no match: fixed point.

Try it

Tasks 3 and 4 of labs/ch21-mir walk the same pipeline with -stop-after=irtranslator, legalizer, regbankselect and instruction-select, and ./course drill legalization --difficulty medium practices the actions GlobalISel's rule tables express differently from SelectionDAG's.

4. Invariants and correctness

FastISel

Proposition 21.6.4. The subtle part is the bottom-up walk combined with local folding: when FastISel selects the add in step 4, it may fold the preceding load only if nothing between them could change memory. That holds because the load is immediately before the add. It also relies on the load having a single use, or the other user would read a value that no longer exists. tryToFoldLoad and the hasOneUse test in SelectAllBasicBlocks check both conditions.

GlobalISel pipeline

Theorem 21.6.6 gives each pass's postcondition. The artifact combiner is what makes the Legalizer's local rewrites compose: widening an i8 G_ADD inserts extends and truncates around it, and without cancelling them, a chain of i8 operations would carry an extend and a truncate at every step. The artifact combines are equalities (G_TRUNC(G_ANYEXT x) = x when the types match), so they preserve meaning.

GlobalISel combiners

The same argument as Proposition 21.5.5: each rule must preserve meaning, and the pass terminates only if the rules decrease a measure. GlobalISel combiners additionally cap the number of iterations over the function. A rule pair that fights still stops, just without reaching a fixed point.

5. Complexity

Variables: \(n\) IR instructions in the function, \(m\) generic MIR instructions (\(m = O(n)\) except for large expansions), \(R\) legalizer rules per opcode, \(b\) register banks.

Technique	Time (worst)	Time (typical)	Space	Justification
FastISel	\(O(n)\) plus the fallback's cost	linear, small constant	\(O(n)\) value map	one table lookup or hook per instruction
GlobalISel pipeline	\(O(m \cdot R)\) legalizing plus \(O(m \cdot b)\) bank mapping plus selection	linear passes over the function	the MIR itself; no per-block DAG	each pass visits each instruction a bounded number of times (Theorem 21.6.6's measure)
GlobalISel combiners	unbounded without a measure; capped by an iteration limit	linear per iteration	worklist \(O(m)\)	as Algorithm 21.5.4

A pathological family for FastISel. A block whose first instruction is not supported (say, an unsupported intrinsic at the top) and whose other instructions are all simple. FastISel walks bottom-up, selects everything down to the failing instruction, and then hands only the prefix (one instruction) to SelectionDAG, which is cheap. A failing instruction at the bottom (an unsupported terminator) hands the entire block to SelectionDAG, and FastISel's work on the block is wasted. The cost of a block is between the two extremes, depending on where the first failure is.

Real-world scale. The GlobalISel documentation lists compile-time performance as a main goal and reports AArch64 -O0 as the production use that motivated the switch [LLVM-GISel]. On x86-64 in LLVM 23.1.2, GlobalISel still falls back for common operations: the §7 box shows it giving up on a 128-bit division and on ctpop.

6. Variants and refinements

FastISel

• Target hooks (X86FastISel::X86SelectAddress, fastSelectInstruction): fold addresses and compares locally for better -O0 code at low cost.
• Fall back per instruction vs per block: calls are selected alone, everything else hands over the prefix. The trade-off is between code quality and FastISel's own complexity.
• Replace with GlobalISel at -O0 (AArch64 since LLVM 7): one selector for all levels instead of FastISel plus SelectionDAG. The price is the maturity of the GlobalISel port.

GlobalISel pipeline

• RegBankSelect modes (Fast: first valid mapping; Greedy: compare mappings by cost including repair copies): speed versus fewer cross-bank copies.
• Localizer: moves constant materializations next to their uses before selection, so their live ranges are short and folding into immediates is possible. It appears in the AArch64 pass list of §7.
• Fallback (-global-isel-abort=0/1/2): error, or fall back to SelectionDAG silently or with a warning. This lets a target adopt GlobalISel incrementally.

GlobalISel combiners

• Pre- vs post-legalizer vs post-legalizer lowering: canonicalize early, clean up legalization artifacts late, and do target-specific lowering last (AArch64 has all three).
• Rules in TableGen vs C++: GICombineRule with MIR patterns gives generated matchers and fewer bugs. The escape hatch is C++ match/apply bodies, which most rules still use for their predicates.

7. In real compilers

FastISel

FastISel::selectInstruction, FastISel::selectOperator and FastISel::tryToFoldLoad in llvm/lib/CodeGen/SelectionDAG/FastISel.cpp. The bottom-up walk with fallback is in SelectionDAGISel::SelectAllBasicBlocks (SelectionDAGISel.cpp), and the x86 hooks are in X86FastISel.cpp (X86SelectAddress, fastSelectInstruction) (LLVM 23.1.2) [LLVM-FastISel].

FastISel at -O0: a local load fold, and two fallbacks

Reproduce (llc 23.1.2, from the repository root):

cd labs/ch21-mir/inputs
for f in true false; do
  echo "== fast-isel=$f"
  llc -O0 -mtriple=x86_64-linux-gnu -fast-isel=$f -stop-after=finalize-isel sum.ll -o - \
    | sed -n '/^  bb.1.loop/,/^  bb.2/p' | grep -vE 'successors|^\s*$|^  bb\.'
done
llc -O0 -mtriple=x86_64-linux-gnu -fast-isel-report-on-fallback fb.ll -o /dev/null
llc -O0 -mtriple=x86_64-linux-gnu -pass-remarks-missed=sdagisel fb.ll -o /dev/null

Output (complete):

== fast-isel=true
    %0:gr64_nosp = PHI %9, %bb.0, %10, %bb.1
    %1:gr64 = PHI %9, %bb.0, %12, %bb.1
    %12:gr64 = ADD64rm %1, %5, 8, %0, 0, $noreg, implicit-def $eflags :: (load (s64) from %ir.p)
    %10:gr64 = ADD64ri32 %0, 1, implicit-def $eflags
    CMP64rr %10, %7, implicit-def $eflags
    JCC_1 %bb.1, 12, implicit $eflags
== fast-isel=false
    %0:gr64_nosp = PHI %6, %bb.0, %3, %bb.1
    %1:gr64 = PHI %6, %bb.0, %2, %bb.1
    %8:gr64 = MOV64rm %4, 8, %0, 0, $noreg :: (load (s64) from %ir.p)
    %2:gr64 = ADD64rr %1, killed %8, implicit-def dead $eflags
    %3:gr64 = INC64r %0, implicit-def dead $eflags
    %9:gr64 = SUB64rr %3, %5, implicit-def $eflags
    JCC_1 %bb.1, 12, implicit $eflags
    JMP_1 %bb.2
warning: Instruction selection used fallback path for mul128
warning: Instruction selection used fallback path for vadd
remark: <unknown>:0:0: FastISel didn't lower all arguments: i128 (i128, i128) (in function: mul128)
remark: <unknown>:0:0: FastISel missed terminator:   ret i128 %m (in function: mul128)
remark: <unknown>:0:0: FastISel didn't lower all arguments: <4 x i32> (<4 x i32>, <4 x i32>) (in function: vadd)

What to notice: FastISel's loop is the §3 trace: ADD64rm from tryToFoldLoad, ADD64ri32 from the table, and CMP64rr/JCC_1 from the branch hook. SelectionDAG at -O0 does not fold the load: IsProfitableToFold returns false at -O0 (Lesson 21.4 §7). SelectionDAG also emits an explicit JMP_1 to the fall-through block, which is removed later. The last lines show the fallback of Proposition 21.6.4: i128 and vector arguments are beyond FastISel's argument lowering, so those whole functions go to SelectionDAG.

GlobalISel pipeline

IRTranslator::runOnMachineFunction and IRTranslator::translate (llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp), Legalizer::legalizeMachineFunction with LegalizerHelper::legalizeInstrStep, narrowScalar and widenScalar (Legalizer.cpp, LegalizerHelper.cpp), RegBankSelect::assignInstr (RegBankSelect.cpp) and InstructionSelect::selectInstr (InstructionSelect.cpp). AArch64's parts are in llvm/lib/Target/AArch64/GISel/ (AArch64LegalizerInfo.cpp, AArch64RegisterBankInfo.cpp, AArch64InstructionSelector.cpp) (LLVM 23.1.2) [LLVM-GlobalISelSrc].

a[i] = p[3] through GlobalISel on AArch64

Reproduce (llc 23.1.2, from the repository root):

cd labs/ch21-mir/inputs
for p in irtranslator legalizer regbankselect instruction-select; do
  echo "== $p"
  llc -O2 -mtriple=aarch64-linux-gnu -global-isel -stop-after=$p store.ll -o - | sed -n '/^body/,$p' | sed 's/[[:space:]]*$//'
done

Output (complete):

== irtranslator
body:             |
  bb.1 (%ir-block.0):
    liveins: $x0, $x1, $x2

    %0:_(p0) = COPY $x0
    %1:_(i64) = COPY $x1
    %2:_(p0) = COPY $x2
    %3:_(i64) = G_CONSTANT i64 24
    %4:_(p0) = nuw nusw inbounds G_PTR_ADD %2, %3(i64)
    %5:_(i64) = G_LOAD %4(p0) :: (load (i64) from %ir.q)
    %6:_(i64) = G_CONSTANT i64 8
    %7:_(i64) = nsw G_MUL %1, %6
    %8:_(p0) = nusw inbounds G_PTR_ADD %0, %7(i64)
    %9:_(p0) = COPY %8(p0)
    G_STORE %5(i64), %9(p0) :: (store (i64) into %ir.e)
    RET_ReallyLR
...
== legalizer
body:             |
  bb.1 (%ir-block.0):
    liveins: $x0, $x1, $x2

    %0:_(p0) = COPY $x0
    %1:_(i64) = COPY $x1
    %2:_(p0) = COPY $x2
    %3:_(i64) = G_CONSTANT i64 24
    %4:_(p0) = nuw nusw inbounds G_PTR_ADD %2, %3(i64)
    %5:_(i64) = G_LOAD %4(p0) :: (load (i64) from %ir.q)
    %10:_(i64) = G_CONSTANT i64 3
    %7:_(i64) = nsw G_SHL %1, %10(i64)
    %8:_(p0) = nusw inbounds G_PTR_ADD %0, %7(i64)
    G_STORE %5(i64), %8(p0) :: (store (i64) into %ir.e)
    RET_ReallyLR
...
== regbankselect
body:             |
  bb.1 (%ir-block.0):
    liveins: $x0, $x1, $x2

    %0:gpr(p0) = COPY $x0
    %1:gpr(i64) = COPY $x1
    %2:gpr(p0) = COPY $x2
    %3:gpr(i64) = G_CONSTANT i64 24
    %4:gpr(p0) = nuw nusw inbounds G_PTR_ADD %2, %3(i64)
    %5:gpr(i64) = G_LOAD %4(p0) :: (load (i64) from %ir.q)
    %10:gpr(i64) = G_CONSTANT i64 3
    %7:gpr(i64) = nsw G_SHL %1, %10(i64)
    %8:gpr(p0) = nusw inbounds G_PTR_ADD %0, %7(i64)
    G_STORE %5(i64), %8(p0) :: (store (i64) into %ir.e)
    RET_ReallyLR
...
== instruction-select
body:             |
  bb.1 (%ir-block.0):
    liveins: $x0, $x1, $x2

    %0:gpr64sp = COPY $x0
    %1:gpr64 = COPY $x1
    %2:gpr64sp = COPY $x2
    %5:gpr64 = LDRXui %2, 3 :: (load (i64) from %ir.q)
    STRXroX %5, %0, %1, 0, 1 :: (store (i64) into %ir.e)
    RET_ReallyLR
...

What to notice: Definition 21.6.1's three stages of a virtual register: %5:_(i64), %5:gpr(i64), %5:gpr64. The IRTranslator translates the GEP literally (G_MUL by the element size). The G_MUL → G_SHL change you see "after the legalizer" was made by the combiner that runs before it (next technique), and the legalizer had nothing to do because i64 and p0 operations are legal. InstructionSelect folds the single-use G_PTR_ADD/G_SHL chains into the addressing modes of LDRXui and STRXroX, the same two instructions SelectionDAG selects (Lesson 21.5).

GlobalISel on x86-64: incomplete patterns and fallbacks

Reproduce (llc 23.1.2, from the repository root):

cd labs/ch21-mir/inputs
llc -O2 -mtriple=x86_64-linux-gnu -global-isel -stop-after=instruction-select store.ll -o - \
  | sed -n '/^body/,$p' | sed 's/[[:space:]]*$//'
llc -O2 -mtriple=x86_64-linux-gnu -global-isel -global-isel-abort=2 wide.ll -o /dev/null

Output (complete):

body:             |
  bb.1 (%ir-block.0):
    liveins: $rdi, $rdx, $rsi

    %0:gr64 = COPY $rdi
    %1:gr64 = COPY $rsi
    %2:gr64 = COPY $rdx
    %5:gr64 = MOV64rm %2, 1, $noreg, 24, $noreg :: (load (s64) from %ir.q)
    %7:gr64_nosp = nsw SHL64ri %1, 3, implicit-def dead $eflags
    %8:gr64 = nusw inbounds LEA64r %0, 1, %7, 0, $noreg
    MOV64mr %8, 1, $noreg, 0, $noreg, %5 :: (store (s64) into %ir.e)
    RET 0
...
warning: Instruction selection used fallback path for div128
warning: Instruction selection used fallback path for pop

What to notice: x86's GlobalISel selector does fold p + 24 into the load, but it does not match the scaled-index form of the store address. It emits a shift, an LEA and a plain store: four instructions where SelectionDAG needs two (task 4 of the MIR exploration). With -global-isel-abort=2, functions it cannot legalize or select (__int128 division, ctpop) fall back to SelectionDAG with a warning. This is the incremental adoption path of §6.

GlobalISel combiners

The combiner driver is Combiner in llvm/lib/CodeGen/GlobalISel/Combiner.cpp, the generic rules are in llvm/include/llvm/Target/GlobalISel/Combine.td (mul_to_shl, sub_to_add, trivial_combines), their C++ halves are in CombinerHelper.cpp (matchCombineMulToShl), and AArch64 instantiates them in AArch64PreLegalizerCombiner.cpp and AArch64Combine.td (LLVM 23.1.2) [LLVM-GISel-Combine].

The pre-legalizer combiner turns G_MUL by 8 into G_SHL by 3

Reproduce (llc 23.1.2; -stop-after accepts the combiner's pass name, which -debug-pass=Structure lists):

cd labs/ch21-mir/inputs
llc -O2 -mtriple=aarch64-linux-gnu -global-isel -stop-after=aarch64-prelegalizer-combiner \
  store.ll -o - | sed -n '/^body/,$p' | sed 's/[[:space:]]*$//'
curl -sL https://raw.githubusercontent.com/llvm/llvm-project/llvmorg-23.1.2/llvm/include/llvm/Target/GlobalISel/Combine.td \
  | sed -n '/^def mul_to_shl/,/>;/p'

Output (complete):

body:             |
  bb.1 (%ir-block.0):
    liveins: $x0, $x1, $x2

    %0:_(p0) = COPY $x0
    %1:_(i64) = COPY $x1
    %2:_(p0) = COPY $x2
    %3:_(i64) = G_CONSTANT i64 24
    %4:_(p0) = nuw nusw inbounds G_PTR_ADD %2, %3(i64)
    %5:_(i64) = G_LOAD %4(p0) :: (load (i64) from %ir.q)
    %10:_(i64) = G_CONSTANT i64 3
    %7:_(i64) = nsw G_SHL %1, %10(i64)
    %8:_(p0) = nusw inbounds G_PTR_ADD %0, %7(i64)
    G_STORE %5(i64), %8(p0) :: (store (i64) into %ir.e)
    RET_ReallyLR
...
def mul_to_shl : GICombineRule<
  (defs root:$d, unsigned_matchinfo:$matchinfo),
  (match (G_MUL $d, $op1, $op2):$mi,
         [{ return Helper.matchCombineMulToShl(*${mi}, ${matchinfo}); }]),
  (apply [{ Helper.applyCombineMulToShl(*${mi}, ${matchinfo}); }])>;

What to notice: the rule is Definition 21.6.7: a MIR match pattern rooted at G_MUL, a C++ predicate that fills matchinfo (the shift amount), and an apply. In the output, %6 = G_CONSTANT 8 is gone (erased as dead), %10 = G_CONSTANT 3 is new, and %7 keeps its number because the instruction was rewritten in place. The redundant %9 = COPY %8 was also removed by another trivial combine (copy propagation).

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
FastISel	one IR instruction at a time plus local folds; falls back for the rest (Proposition 21.6.4)	linear, smallest constant	-O0 quality; debuggable 1:1 mapping	moderate per target (hooks)	-O0 on x86-64 and other SelectionDAG targets
GlobalISel pipeline	whole-function generic MIR; legal → banked → selected (Theorem 21.6.6)	linear passes, no per-block DAG	on AArch64 comparable to SelectionDAG; on x86-64 still incomplete (4 instructions vs 2 on the store box; fallbacks)	high: four target components, but reusable and testable in MIR	AArch64 (-O0 default), AMDGPU, RISC-V, Apple GPU; experimental x86
GlobalISel combiners	canonicalization and simplification on MIR, across blocks	linear per iteration, capped	quality depends on the rule set	rules in TableGen plus C++ helpers	pre-/post-legalizer passes of every GlobalISel target

• Choose FastISel when you need -O0 speed on a SelectionDAG target and good debug info. It stays as long as SelectionDAG is the target's main selector.
• Choose GlobalISel when you write a new target, need cross-block selection or register-bank decisions, or want each stage testable on MIR (llc -run-pass=legalizer on a .mir file).

9. Assessment

Technique	Quiz ids (solutions/quizzes/ch21.yaml)	Drill	Flashcard tag	Exercises
FastISel	fastisel-fallback, fastisel-o0-fold	none: FastISel is a table plus hooks; the MIR exploration exercises it	fastisel	E5 task 8
GlobalISel pipeline	gisel-pass-order, gisel-bank	./course drill legalization (actions), plus E5	globalisel	E5 tasks 3–4
GlobalISel combiners	gisel-mul-to-shl, gisel-combine-where	none: rule-specific, quizzed on the mul_to_shl example	gisel-combiner	E5 task 3

Reading -stop-after=legalizer as the legalizer's work

The pipeline runs several passes before the Legalizer (IRTranslator, the pre-legalizer combiner, the Localizer, a load/store optimizer). A change visible after -stop-after=legalizer may come from any of them, as G_MUL → G_SHL does here. To attribute a change to one pass, stop before and after it (-stop-before=legalizer, -stop-after=legalizer) or run the pass alone on a .mir file with llc -run-pass=legalizer.

References

See the chapter references.