Flashcards — Chapter 17¶
67 cards. Review them with spaced repetition in the terminal (./course flash 17) or export them to Anki (./course flash export 17). Here, click a card to reveal its back.
kildall-cp¶
Kildall's constant propagation: what is the fact at each program point?
An environment mapping every variable to the flat lattice ⊥ < c < ⊤ (Definition 17.1.3), solved by round-robin or worklist iteration over the CFG. Every edge is assumed executable.
Kildall's CP: why does it find no constants in the running example?
It assumes every edge is executable, so x = 2 from the never-executed if.then reaches the join and x becomes ⊤. The loop makes i and j ⊤ in pass 2.
Kildall's CP: cost?
O(|Vars|² · n · e): the environment lattice has height 2·|Vars|, and each join costs |Vars|.
sparse-cp¶
Sparse simple CP (SSC): what does it propagate along?
SSA def-use edges only: one lattice value per SSA value. Phis join all operands, and every block counts as executable.
Sparse simple CP vs Kildall on SSA?
Same constants (Theorem 17.1.11), at O(U + I) instead of an environment per program point.
sccp¶
SCCP: the two worklists?
CFG edges (drained first) and SSA uses. A block's instructions are visited when its first incoming edge becomes executable, and its phis again on each new edge.
SCCP: why does it prove x = 1 in the running example?
cmp1 = ne x.0, 1 is 0 while x.0 = 1, so the edge into if.then is never marked executable, and x.1's phi ignores the 2 on that edge. The optimistic guess is consistent: a fixed point.
SCCP vs CP + DCE iterated?
SCCP finds at least as much, and sometimes strictly more (Theorem 17.1.12): it solves constants and executable edges as one least fixed point.
SCCP: bound on lattice changes?
Each value changes at most twice (⊥ → c → ⊤) and each edge is marked once: O(U + e + I) work (Theorem 17.1.9).
lvi-cvp¶
LazyValueInfo: what question does it answer?
What range does value v have at the start of block B (or on edge P→B)? Demand-driven and cached, with branch conditions refining ranges on edges.
Correlated value propagation: examples of rewrites?
sdiv → udiv when both operands are non-negative, adding nsw/nuw, narrowing divisions, folding compares, all from LVI ranges at the use.
LVI's cap per query (LLVM 23)?
MaxProcessedPerValue = 500 (block, value) pairs, after which the query returns overdefined.
constant-range¶
ConstantRange: what is [ℓ, u) when u < ℓ (unsigned)?
A wrapped interval: ℓ … 2^w − 1, 0 … u − 1. Its size is (u − ℓ) mod 2^w.
ConstantRange addition?
[ℓ1, u1) + [ℓ2, u2) = [ℓ1 + ℓ2, u1 + u2 − 1), or full if the size wrapped (overflow) (Algorithm 17.2.3).
ConstantRange union: where does precision go?
One interval per value: the union of [0, 2) and [10, 12) is [0, 12). The gap is lost, because wrapped intervals are not a lattice (no least upper bound).
known-bits¶
Known bits: the domain?
A pair of masks (Zero, One) with Zero & One = 0: bits known 0, known 1, or unknown. It captures parity-like facts that ranges cannot.
Known bits of a sum?
Ripple-carry abstraction: a sum bit is known when both input bits and the carry are known. The carry is known when two of the three are known 1 (or 0) (Algorithm 17.2.5).
Known bits vs ranges?
Incomparable: "multiple of 16" is exact in known bits and nearly full as a range; "x < 100" is the reverse. LLVM keeps both.
demanded-bits¶
Demanded bits: direction and meaning?
Backward: which bits of each value can influence an observable result (a return, store, call or branch)? For example, trunc to i8 demands 0xFF of its operand.
BDCE: what does it do?
It replaces an instruction none of whose bits are demanded by 0, deletes it, and drops nsw/nuw/exact on users whose operands changed (Theorem 17.2.12).
marksweep-dce¶
Mark–sweep DCE: roots and effect?
Roots: side effects, returns and every branch. It marks operands' definitions transitively and deletes the rest, including dead cycles. The CFG is unchanged.
Mark–sweep vs use-count (worklist) DCE?
Use-count DCE deletes only values with zero uses, so it cannot remove a dead phi cycle. Mark–sweep assumes everything is dead until marked.
adce¶
ADCE: when is a branch live?
When some useful block is control dependent on it (it lies in the block's post-dominance frontier), or when it is a root (no path to an exit, or a back edge without mustprogress).
ADCE: what happens to a dead branch?
It becomes br to its nearest useful post-dominator. The skipped blocks become unreachable and are deleted.
ADCE and loops in LLVM?
adce-remove-loops defaults to false: back-edge branches are roots, so ADCE never deletes a possibly infinite loop. loop-deletion handles loops with mustprogress.
dse¶
Dead store: definition?
A store whose location is overwritten on every path before any possible read, or whose location is never read before its lifetime ends (a non-escaping alloca).
DSE and ADCE: which order?
DSE first. A store is an ADCE root, so the branch around it stays live until DSE deletes the store.
early-cse¶
EarlyCSE: how does it handle memory?
A generation counter. It increments on every instruction that may write memory and at every block with more than one predecessor. A load is reused only from the same generation.
EarlyCSE: data structure for scoping?
A scoped hash table over the dominator tree: push a scope on entering a node and pop it on leaving, so only dominators' expressions are visible.
dvnt¶
DVNT: in one sentence?
Hash-based value numbering over a dominator-tree walk with a scoped table. It also replaces meaningless phis (all operands equal) and redundant phis (the same as an earlier phi).
DVNT: what does it miss?
Siblings (neither dominates the other) and loop-carried congruences: a back-edge operand has no number when the phi is hashed (pessimistic).
llvm-gvn¶
LLVM GVN: leaders?
Global value numbers in RPO, plus a leader table per number. An instruction is replaced only by a leader whose block dominates it (findLeader).
LLVM GVN: equality propagation?
After br (icmp eq a, b), in the region dominated by the true edge, b is treated as a (propagateEquality).
awz¶
AWZ congruence?
The coarsest partition of values in which congruent values have the same label and pairwise congruent operands. It is computed optimistically, by splitting a single class per label.
AWZ vs hash-based VN?
AWZ finds everything DVNT finds and more (Theorem 17.5.12): loop phis, siblings, joins. There is no algebra and no constant folding.
AWZ with Hopcroft splitting: cost?
O(E log N): each value moves to a class at most half as large as its old one O(log N) times.
optimistic-vn¶
Optimistic RPO value numbering (Simpson)?
Iterate hash-based VN in RPO from ⊤ ("matches anything") until the numbers stop changing. It gives the same partition as AWZ (Theorem 17.5.14) and can fold constants during hashing.
Herbrand equivalence vs congruence?
Herbrand: equal symbolic terms on every path. Congruence implies it, but not conversely: phi(a+b, c+d) and phi(a,c) + phi(b,d) are Herbrand-equivalent and have different labels.
newgvn¶
NewGVN?
LLVM's implementation of Gargi's predicated GVN: sparse (touched instructions), optimistic about reachability, with constants, predicates (PredicateInfo) and memory (MemorySSA) in one fixed point.
Why is NewGVN not LLVM's default?
It has had fewer years of tuning than GVN's load handling and PRE. It is an option (-enable-newgvn), not in default<O2>.
gvn-hoist-sink¶
GVN-hoist?
It moves computations with one value number from all successor regions into a common dominator where the value is very busy. It saves code size without adding evaluations (Theorem 17.5.16).
GVN-sink?
It merges equal-shaped instructions from all predecessors into the join, with phis for the operands that differ.
morel-renvoise¶
Morel–Renvoise: shape of the system?
Bidirectional bit vectors (placement-possible PPIN/PPOUT). Insertions go at block ends, so it misses critical-edge cases and converges slowly.
Why is MR not optimal?
It cannot insert on critical edges, and it hoists as early as PPOUT allows, which lengthens live ranges (Proposition 17.6.15).
lcm¶
LCM: the four problems?
Availability (forward), anticipability (backward), EARLIEST from both, LATER/LATERIN (forward). All are unidirectional and rapid.
LCM: INSERT and DELETE?
INSERT(i,j) = LATER(i,j) − LATERIN(j); DELETE(b) = UEEXPR(b) − LATERIN(b) (b ≠ entry).
LCM optimality?
Computationally optimal (never more evaluations on any path, fewest among safe placements) and lifetime optimal (places as late as possible) (Theorems 17.6.13–17.6.14).
ssapre¶
SSAPRE: the six steps?
Φ-Insertion, Rename, DownSafety, WillBeAvail, Finalize, CodeMotion: PRE per expression on the program's SSA form.
SSAPRE: what is a Φ?
A phi of the expression's hypothetical temporary at DF⁺ of occurrences and operand definitions. Versions make redundancy explicit.
gvn-pre¶
GVN-PRE: what does it add to lexical PRE?
Value numbers and phi-translation: it finds redundancies of values whose expressions have different names on different paths.
Phi-translation?
Rewriting an expression anticipated at a join into the corresponding expression at the end of a predecessor, by replacing phi-defined operands with that predecessor's incoming values.
load-pre¶
LLVM load PRE: when does it insert a load?
When a load is available in all but (by default) one predecessor, the address is available there, and the load is safe (anticipated on every path, or dereferenceable) (PerformLoadPRE).
simplifycfg¶
SimplifyCFG-lite rules?
R1 constant branches, R2 unreachable blocks, R3 merging a block into its single predecessor ending in br, all to a fixed point. The number of blocks plus edges strictly decreases.
SimplifyCFG in LLVM 23 default<O2>?
8 instances: after almost every pass that changes the CFG. It is LLVM's most frequently run pass.
switch-lookup¶
Switch to lookup table: the check?
idx = x − c1; idx <u size. One unsigned comparison covers both ends of the range (Theorem 17.7.10).
Switch to lookup table: when?
The case destinations lead without side effects to one join whose phis select constants, the range is dense enough, and the target finds a table profitable.
jump-threading¶
Jump threading: threadable edge?
A predecessor P of block B on which B's branch condition is a known constant (via a phi constant or LVI). P is redirected to a copy of B that jumps straight to the known successor.
Jump threading limit in LLVM?
jump-threading-threshold = 6 instructions duplicated per block. By default it does not thread across loop headers (that would create irreducible loops).
phase-ordering¶
Phase-ordering problem?
The result depends on the order of passes; a pass can enable or disable others. Production compilers use fixed, hand-tuned pipelines that repeat cheap cleanup passes.
Why does default<O2> prove run returns 1?
IndVarSimplify rewrites the exit values of i and j to smax(n, 0), so GVN sees two identical muls. A loop pass fixes a scalar ordering problem.
combined-analysis¶
Click–Cooper theorem?
A combined analysis (one fixed point over all facts, monotone in each) is at least as precise as any phase ordering of the separate analyses (Theorem 17.8.6), and sometimes strictly more precise (Proposition 17.8.7).
A program only a combined analysis optimizes?
if (i != j) i += 2; else i += 1; j += 1; in a loop. The branch folds only if i ≡ j, and i ≡ j holds only if the branch folds. NewGVN and GCC's FRE prove return 0.
equality-saturation¶
Equality saturation?
Apply rewrite rules non-destructively in an e-graph until nothing new is added (saturation), then extract the cheapest represented term. At saturation the rule order no longer matters (Theorem 17.8.9).
E-graph congruence invariant?
No two e-classes contain the same canonical e-node (the same operator with the same child classes). Rebuilding restores it after merges.
egg's rebuilding?
Defer congruence repair to once per round and re-canonicalize only the parents of merged classes. It reaches the same fixed point as eager congruence closure with less work.
aegraph¶
Cranelift aegraph?
An acyclic e-graph: pure instructions leave the CFG, ISLE rules fire eagerly once at creation, classes hold ≤ 5 e-nodes, and elaboration puts one node per needed class back (with GVN, LICM and remat).
Aegraph vs full equality saturation?
No saturation guarantee (a rewrite enabled only by a later union is never tried), in exchange for near single-pass compile time.