Flashcards — Chapter 21¶
96 cards. Review them with spaced repetition in the terminal (./course flash 21) or export them to Anki (./course flash export 21). Here, click a card to reveal its back.
macro-expansion¶
Macro expansion: what is it?
Cover every IR node with one fixed template for its operator (one rule per node), emitting code children first. No choice, no search.
Macro expansion: cost and speed?
Θ(n) time for n nodes, one pass. Its code cost is the sum of the macro rules' costs: the worst of the three selectors (lab: 70 866 vs 53 632 for DP on 2005 programs).
Where is macro expansion still used, and why?
Baseline/JIT compilers where compile time dominates: Wasmtime's Winch, V8's Sparkplug and Liftoff, and LLVM's FastISel at -O0 (with a few local folds).
maximal-munch¶
Maximal munch: the rule?
Top-down: at each node take the matching rule with the largest pattern (most operator nodes) for the needed nonterminal, ties to the lower rule number; recurse into its operand nodes.
Maximal munch: optimal or optimum?
Optimal (locally: no two adjacent tiles can be merged into a cheaper single rule, Theorem 21.1.13) but not optimum: a big tile at the root can hide a cheaper split below (Proposition 21.1.14).
Maximal munch: complexity?
O(n·R·p): at each of n nodes try R rules of pattern size ≤ p. Linear in the tree for a fixed grammar.
How does LLVM's SelectionDAG realize maximal munch?
TableGen sorts patterns by complexity (getPatternComplexity: 3 per node plus extras plus AddedComplexity), and the matcher table tries them in that order from each node.
peephole-combining¶
Peephole combining (Davidson–Fraser): the idea?
Expand naively into register transfers, then merge a producer i into its single-use consumer j when the combined transfer j[i] is recognized as one cheaper machine instruction.
Why is combining order-dependent?
Each combination consumes links; merging ld into st first (movm) can block folding +24 into the load. Lesson 21.1: one order reaches cost 5, another 6.
GCC's combine pass: what checks a candidate?
The generated recognizer recog (from define_insn patterns): combine keeps a merged RTL only if recog accepts it; it tries 2, 3 and 4 linked instructions.
dp-tiling¶
DP tiling: what is the label C(v, A)?
The minimum cost of deriving the subtree at v from nonterminal A (∞ if impossible), with rule(v, A) a rule that attains it.
DP tiling: the two passes?
Label bottom-up (Algorithm 21.2.3: for each rule matching at v, c(r) + sum of operand labels; then chain closure), then Reduce top-down from the start nonterminal reading rule(v, A).
Why is the tree DP optimum?
Derivations of disjoint subtrees are independent, so the best derivation of t_v for A combines best derivations of the operands (Lemma 21.2.6); induction on height (Theorem 21.2.7).
DP tiling complexity?
O(n·R·p) plus chain closure per node: linear in tree size for a fixed grammar.
Aho–Johnson with k registers?
Tabulate cost per (subtree, number of free registers) assuming contiguous evaluation; linear in the tree for fixed k (Algorithm 21.2.5, generalizing Sethi–Ullman).
iburg-lburg¶
twig, iburg, lburg: what do they generate?
A DP labeler and reducer from a tree grammar with costs: twig (Aho–Ganapathi–Tjiang 1989, top-down matching), iburg (1992, C code with switch per operator), lburg (lcc's variant).
iburg: how are ties resolved?
Rules are tried in file order and a rule replaces the best only if strictly cheaper, so the earlier rule wins a tie.
Dynamic costs: what is allowed?
A cost may be a function of the subtree t_v (constants, equal children) or ∞ as a predicate (LBURG_MAX); a cost that depends on the context breaks the DP (Proposition 21.2.12).
HotSpot C2's instruction selector?
ADLC generates a DP labeler (the DFA class) from the .ad description; Matcher::ReduceInst reduces from the chosen rules.
burs¶
BURS: what is a δ-state?
The labels of a node normalized by their minimum, with the best rules: {A ↦ (C(v, A) − min, rule)}. Equal states behave identically above.
BURS: when does the automaton exist?
Iff the grammar is BURS-finite: the normalized cost differences are bounded (Theorem 21.3.7). Then labeling is one table lookup per node.
A grammar that is not BURS-finite?
a: MEM(a) cost 1 and b: MEM(b) cost 2 both needed: along MEM^k(TEMP) the difference C(b) − C(a) = k grows without bound (Proposition 21.3.8).
BURS normal form?
Every rule is a chain rule A → B or a base rule A → o(B1..Bk); inner pattern nodes get helper nonterminals with cost-0 base rules (Definition 21.3.1).
burg¶
BURG (Proebsting): what does the generator do?
Worklist state construction: compute δ(op, s1, s2) for every tuple of known states, intern new states, until closed; then emit tables and a labeler.
Representer states / index maps?
Project a state onto the nonterminals that position i of operator o can use, renormalize; distinct projections are representers. Tables are indexed by representers, which shrinks them drastically (Chase 1987).
BURG vs iburg trade-off?
BURG: no cost arithmetic at compile time, constant work per node, but constant costs only and a finite automaton; iburg: DP at compile time, dynamic costs allowed.
dag-decomposition¶
Why is DAG covering hard?
Minimum-cost covering of DAGs is NP-complete even for a fixed grammar with costs 0/1 (reduction from 3-SAT, Theorem 21.4.4); shared nodes must be consistent with every tile.
Tree decomposition of a DAG?
Cut at every shared node (compute it once into a register), then tile each tree optimally. Optimum among covers that materialize shared nodes, not in general (Proposition 21.4.7).
LLVM's greedy DAG matcher and sharing?
A pattern may only swallow a node with one use (the fold rule); address arithmetic is the exception, duplicated into every memory operand by matchAddress.
noltis¶
NOLTIS: the algorithm?
Tile the DAG as if it were a tree (DP), then for each shared node compare overlap cost ω (extra cost of recomputing it inside tiles) with CSE cost κ; fix nodes with κ < ω and run the DP again.
NOLTIS: guarantees?
Valid cover in linear time (Proposition 21.4.10); not optimum in general, but Koes–Goldstein measured it optimal on 99.7 % of basic blocks.
NOLTIS on a shared address q = p + 8 used by two loads?
ω = 0 (ld c(r) costs the same as ld 0(r)), κ = 1: keep the overlap and fold q into both loads.
pbqp-ilp¶
PBQP for instruction selection?
One variable per node (its rule), cost vector per node, cost matrix per edge for incompatible nonterminals; minimize the sum (Eckstein–König–Scholz 2003; Ebner et al. 2008).
PBQP reductions R0, R1, R2, RN?
Remove nodes of degree 0, 1, 2 folding their costs into neighbours (exact, Theorem 21.4.13); RN decides a higher-degree node heuristically.
ILP formulation of DAG covering?
0/1 variables y(v, r); minimize Σ c(r)·y; each root covered; each used rule's operands produced by some chosen rule. Exact, but exponential in the worst case.
sdag-combine¶
SelectionDAG phases in order?
Build → combine 1 → legalize types (→ combine) → legalize vectors → legalize ops → combine 2 → select → schedule.
What does the DAG combiner do?
A worklist of target-independent rewrites (mul by 2^k → shl, (a+b)−b → a, …) plus target hooks, run four times at different legality levels (DAGCombiner.cpp).
What does a SelectionDAG node carry?
An opcode, a list of result value types (including Other for chains and Glue), and operands that are (node, result number) pairs.
legalization¶
Type legalization actions?
Legal, PromoteInteger (i8 → i32), ExpandInteger (i128 → two i64), SoftenFloat, Split/Widen vectors, Scalarize.
Operation legalization actions?
Legal, Promote, Expand (into other nodes), LibCall (e.g. __divti3), Custom (target C++ lowering), set by setOperationAction in each target's TargetLowering constructor.
add i128 on x86-64 after legalization?
ExpandInteger: UADDO on low halves + UADDO_CARRY on high halves, selected as ADD64rr + ADC64rr.
Why does legalization terminate?
Each step replaces an illegal node by nodes smaller under a ranking (narrower types, simpler ops) (Theorem 21.5.9).
matcher-table¶
SelectionDAG matcher table?
A byte-coded decision table generated by TableGen from all patterns, sorted by complexity, with shared prefixes merged into scopes; interpreted by SelectionDAGISel::SelectCodeCommon.
What happens when no pattern matches?
If target code in Select() does not handle the node either, llc aborts with "Cannot select".
Pattern complexity in TableGen?
3 per node including immediate leaves (register leaves 0), plus extras for predicates and ComplexPatterns (addr), plus AddedComplexity: e.g. (add GPR, (shl GPR, imm)) = 9.
sdag-schedule¶
SelectionDAG scheduling: what is it?
Linearize the selected DAG of a block into MachineInstrs: a bottom-up list scheduler (source order by default on targets that enable the MachineScheduler, such as x86-64 and AArch64; register reduction or ILP otherwise) that respects data, chain and glue edges.
What does glue mean?
The two nodes must be adjacent and in order (e.g. compare and branch on EFLAGS); the scheduler treats glued nodes as one unit.
Is every SelectionDAG schedule correct?
Every topological order of data, chain and glue edges (with glued nodes adjacent) is correct (Proposition 21.5.13); the variants (source, list-burr, list-ilp, linearize) differ in register pressure and ILP.
fastisel¶
FastISel: what is it?
LLVM's -O0 selector: bottom-up, one IR instruction at a time with table-generated and target hooks, a few local folds; falls back to SelectionDAG for what it cannot handle.
FastISel's local folds?
tryToFoldLoad folds a single-use load into its user (ADD64rm); a single-use icmp is folded into the branch (CMP + JCC).
When does FastISel fall back?
On types or operations it does not handle (i128 values, vectors, many intrinsics); per block, via SelectionDAGISel::SelectAllBasicBlocks. -fast-isel-report-on-fallback lists them.
globalisel¶
GlobalISel's four passes?
IRTranslator (IR → generic MIR with LLTs) → Legalizer → RegBankSelect → InstructionSelect, with combiners in between.
What is an LLT?
A low-level type of generic MIR: a scalar of n bits (s64/i64), a pointer in an address space (p0), or a vector; no register class yet.
What does RegBankSelect decide?
The register bank (gpr, fpr on AArch64) of every virtual register, from how values are produced and used; costs of cross-bank copies guide it.
GlobalISel's goals vs SelectionDAG?
Performance (faster selection), granularity (the whole function, not a block), modularity (separate testable MIR passes); it reuses SelectionDAG patterns for InstructionSelect.
gisel-combiner¶
GlobalISel combine rule?
A TableGen GICombineRule with a match part (MIR pattern + C++ predicate filling matchinfo) and an apply part; defined in Combine.td, C++ in CombinerHelper.cpp.
mul_to_shl?
G_MUL x, 2^k → G_SHL x, k: matchCombineMulToShl checks the power of two and stores k.
When do GlobalISel combiners run?
Pre-legalizer and post-legalizer combiner passes (target-instantiated, e.g. AArch64PreLegalizerCombiner) run to a fixed point over a worklist.
isle¶
ISLE: what is a rule?
(rule priority (lhs pattern) rhs): a typed term-rewriting rule from CLIF (or mid-end terms) to machine instructions via extractors and constructors.
ISLE: which rule fires?
Among the rules whose left-hand side matches, the one of maximum priority; equal priorities must not overlap (checked by the ISLE compiler).
How does Cranelift lower a function with ISLE?
Instructions in reverse order; each lowered by the compiled ISLE decision trie; loads with one use can be sunk into the user's addressing mode.
Why was ISLE introduced?
Handwritten lowering in Rust was long and error-prone (miscompilations); a DSL is verifiable (Crocus) and serves both lowering and mid-end rewrites.
egraph-isel¶
E-graph: what is it?
A set of e-classes of equivalent e-nodes f(c1..ck); rewriting adds equalities without destroying the original term; saturation applies rules until nothing changes.
Extraction from an e-graph?
Choose one e-node per class to minimize cost; with tree costs a bottom-up per-class minimum (like the tiling DP), with DAG costs (shared once) NP-hard.
Cranelift's aegraph?
An acyclic e-graph mid-end: rewrite rules in ISLE (opts/*.isle), extract the cheapest form per value, elaborate back into the CFG before lowering (Fallin 2023).
Denali?
Joshi–Nelson–Randall 2002: saturate an e-graph with axioms, then ask a SAT solver for the shortest instruction sequence: the first e-graph-based selector (a superoptimizer).
tablegen¶
TableGen: what is it?
A declarative language of classes and records with templates, let overrides and multiclasses; separate llvm-tblgen back ends (-gen-dag-isel, -gen-instr-info, -gen-callingconv…) give records meaning.
TableGen elaboration order?
(1) parent classes in order (later override earlier), (2) the record body, (3) enclosing top-level let (overrides inherited fields, not body fields), (4) resolve references.
TableGen pattern type inference?
Each node starts with the legal types (register classes); type profiles (SDTypeProfile: SameAs, IsInt…) intersect the sets to a fixpoint; an empty set is an error ("Type set is empty").
gcc-md¶
GCC define_insn?
(name, RTL template with match_operand predicates and constraints, condition, output template, attributes); its file index is the insn code.
GCC recog?
Generated by genrecog as a decision tree; returns the first template in file order that matches and whose condition holds (Proposition 21.8.7), or −1.
GCC constraints and alternatives?
Comma-separated alternatives per operand ("=r,m" with "rm,r"); register allocation later picks one alternative per instruction.
grammar-desc¶
lburg rule format?
nonterminal: PATTERN "assembly template" cost, where cost may be a C expression (dynamic cost) such as range(a, 1, 1).
Addressing modes in a tree grammar?
Nonterminals such as base, index and addr (lcc x86) derived with chain and base rules; the analogue of TableGen ComplexPatterns and ADL operand classes.
HotSpot ADL instruct?
match rule, ins_cost, ins_encode, ins_pipe (and format): ADLC generates C2's DFA labeler and emitters from them.
calling-convention¶
SysV x86-64 integer argument registers?
rdi, rsi, rdx, rcx, r8, r9; FP in xmm0–xmm7; separate counters per class; the rest on the stack in 8-byte slots.
SysV rule for i128 arguments?
Two INTEGER eightbytes in consecutive GPRs if two are free; otherwise on the stack (16-aligned) and not split; later integer args may still use the free register.
AAPCS64 rule for 128-bit integers?
Round NGRN up to even and use an even/odd pair (x2:x3); if it does not fit, NGRN = 8 and it goes to the stack, and all later integer args go to the stack too.
How does LLVM encode calling conventions?
In TableGen CallingConv records (CCIfType, CCAssignToReg, CCAssignToStack, CCCustom) compiled to CCAssignFns, driven by CCState::AnalyzeFormalArguments/AnalyzeCallOperands.
frame-lowering¶
What is the red zone?
SysV x86-64: 128 bytes below %rsp that signal handlers do not clobber; leaf functions use it for locals without moving %rsp. Kernels disable it (noredzone).
Stack alignment at calls on x86-64?
%rsp ≡ 0 (mod 16) at each call; at entry %rsp ≡ 8 because of the return address, so pushes plus the allocation must add up to 8 mod 16.
Frame pointer trade-off?
Keeping %rbp/x29 as frame pointer costs a register and two instructions but makes stack walking for profilers and debuggers simple; -frame-pointer=all forces it.
pei-shrinkwrap¶
What does prologue/epilogue insertion (PEI) do?
After RA: save the used callee-saved registers, lay out frame objects, emit prologue/epilogue with CFI, eliminate call-frame pseudos, replace frame indices by sp/fp offsets.
Shrink-wrapping: save and restore points?
S = nearest common dominator of the blocks using CSRs/frame, R = their nearest common post-dominator, with S dom R, R pdom S, and neither in a loop that leaves the region (Chow 1988).
Why can't the save point be inside a loop?
The prologue would run on every iteration and push repeatedly; the stack would grow without bound.
mc-encoding¶
What is an MCInst?
An opcode plus operands (register, immediate, or symbolic MCExpr); no basic block, no def/use flags: the input of the encoder and the asm printer.
x86 ModRM special cases?
rm = 100 (rsp, r12) means a SIB byte follows; mod = 00 with rm = 101 (rbp, r13) means RIP-relative, so (%rbp) is encoded as 0(%rbp) with a zero disp8.
What is a fixup?
A record (offset, kind, expression) that the encoder emits for a symbolic operand: which bytes to fill later and how (e.g. reloc_branch_4byte_pcrel, fixup_aarch64_pcrel_call26).
relaxation¶
Span-dependent instruction?
An instruction with short and long forms whose valid form depends on the distance to its target (x86 jmp eb rel8 vs e9 rel32) (Szymanski 1978).
Start-short relaxation: result?
With label operands (monotone spans), iterating from all-short and lengthening what does not fit reaches the least consistent assignment: minimal size, ≤ n + 1 rounds (Theorem 21.10.7).
Why is start-long not optimal?
Two jumps in each other's span can each fit short only if the other is short; starting long, neither can shrink alone (mutual.s: 134 vs 128 bytes).
Relaxation in LLVM MC?
MCAssembler::layout repeats relaxOnce (a fused forward sweep over fragments) until stable; X86AsmBackend relaxes JMP_1/JCC_1 to JMP_4/JCC_4 when !isInt<8>.
relocations¶
What is a relocation?
(offset P, type, symbol S, addend A): the linker computes the type's formula (e.g. S + A − P) with final addresses and patches the field.
Why is the addend of a call -4?
The CPU adds the displacement to the address of the next instruction, P + 4; the ELF formula subtracts P, so A = −4 corrects the reference point.
REL vs RELA?
RELA (x86-64 and AArch64 ELF) stores the addend in the relocation record; REL (COFF, Mach-O, i386 ELF) stores it in the patched field.
When does the assembler resolve a fixup itself?
When its value cannot change at link time: a PC-relative reference within one section to a symbol that cannot be preempted, or an absolute constant; otherwise it emits a relocation.