Flashcards — Chapter 15¶
85 cards. Review them with spaced repetition in the terminal (./course flash 15) or export them to Anki (./course flash export 15). Here, click a card to reveal its back.
iterative-dom¶
Iterative dominators: what are the dataflow equations?
Dom(entry) = {entry}; Dom(n) = {n} ∪ ⋂ Dom(p) over predecessors p. Initialise every other set to 'all nodes' and iterate to the greatest fixed point.
Iterative dominators: why visit nodes in reverse postorder?
In RPO every node except a back-edge target is visited after all its predecessors, so one pass propagates along forward edges; the pass count is bounded by loop-connectedness d(G) + 2 (Kam–Ullman).
Iterative dominators with bit vectors: cost?
O(N) bits per set, O(E·N / w) word operations per pass, (d+2) passes — roughly O(N²) space and O(d·E·N/w) time. Fine for tiny CFGs, the reference oracle.
Dataflow characterization of dominance (Theorem 15.1.8)?
Dom is the greatest solution of X(r) = {r}, X(n) = {n} ∪ ⋂ X(p) over reachable predecessors: Dom solves the equations, and every solution is contained in Dom (induction on path length). Hence iterate downward from ⊤.
chk¶
Cooper–Harvey–Kennedy: what does the algorithm store?
Only idom[n] per node (a tree as an array), processed in reverse postorder; Dom(n) is the path from n up the idom chain.
CHK: how does intersect(a, b) work?
Two fingers walk up the idom array: while a ≠ b, move whichever has the smaller postorder number up to its idom. They meet at the nearest common ancestor.
CHK: complexity and practice?
Worst case O(N²) per pass (long intersect walks) × (d+2) passes, but fast on real CFGs; used by GCC's iterate_fix_dominators and Cranelift's simple dominator tree.
CHK invariant (Lemma 15.1.24): what does the doms[] chain of a processed node b satisfy?
Dom(b) ⊆ chain(b) ⊆ DFS-tree ancestors of b, and chains only shrink. At the last pass the chains solve the dominator equations, so they equal Dom. Mid-pass a chain can be strictly smaller than the iterative algorithm's set, because updating doms[a] shrinks all chains through a at once.
lengauer-tarjan¶
Lengauer–Tarjan: define the semidominator sdom(w).
The DFS-smallest v such that there is a path v = v0 … vk = w where every interior vi has DFS number greater than w's.
Lengauer–Tarjan: how is idom(w) derived from sdom?
Let u be the node with minimum sdom on the tree path sdom(w)+ … w. If sdom(u) = sdom(w) then idom(w) = sdom(w); otherwise idom(w) = idom(u) (fixed up in a final preorder pass).
Lengauer–Tarjan: complexity of simple vs balanced LINK/EVAL?
Simple (path compression only): O(E log N). Balanced (size/child linking): O(E α(E,N)). The simple version is usually faster in practice.
Where does the semidominator sit (Lemma 15.1.14)?
sdom(w) is a proper DFS-tree ancestor of w, and idom(w) is an ancestor-or-self of sdom(w) (Lengauer–Tarjan, Lemmas 3 and 4). So the idom lies on the tree path at or above sdom(w).
semi-nca¶
Semi-NCA: key idea?
Compute semidominators as in Lengauer–Tarjan, then idom(w) = NCA of parent(w) and sdom(w) in the partially built dominator tree, walking up from parent(w) until reaching a node with DFS number ≤ sdom(w).
Semi-NCA: why does processing in DFS preorder work for the NCA step?
When w is processed, all nodes with smaller DFS numbers — including parent(w) and sdom(w) and their tree ancestors — already have final idoms.
Semi-NCA: complexity, and who uses it?
O(N²) worst case (NCA walks), near-linear in practice; LLVM's SemiNCAInfo::runSemiNCA (GenericDomTreeConstruction.h) uses it for both full builds and incremental updates.
Semi-NCA lemma (Lemma 15.1.18)?
idom(w) = NCA, in the dominator tree, of parent(w) and sdom(w). Processing w in preorder, climb from parent(w) through final idoms until the node number is ≤ sdom(w).
dominators¶
Define 'a dominates b' and 'immediate dominator'.
a dom b iff every path from entry to b passes through a. idom(b) is the unique strict dominator of b that every other strict dominator of b dominates — its parent in the dominator tree.
How does a dominator tree answer 'a dominates b?' in O(1)?
Number a DFS of the tree with in/out times; a dom b iff in(a) ≤ in(b) and out(b) ≤ out(a). LLVM's DomTreeNode DFSNumIn/DFSNumOut do this after updateDFSNumbers().
LLVM: what does DT.dominates(A, B) return when B is unreachable?
true — unreachable blocks are dominated by everything (block-level query). properlyDominates(A,B) is A ≠ B && dominates(A,B).
Dominator tree theorem (Theorem 15.1.6): why is idom(n) unique?
The strict dominators of n form a chain: on a simple path r ⇝ n the earlier of two strict dominators dominates the later. The chain's last element, dominated by all the others, is idom(n); the edges idom(n) → n form a tree whose root paths are exactly the Dom sets.
dbs-insert¶
Incremental insertion of edge x→y (y already reachable): when does the dominator tree change?
Only if x is reachable and NCA(x, y) ≠ idom(y). Affected nodes: y and every w with depth(w) > depth(NCA)+1 reachable from y along a path whose nodes are all at least as deep as w.
DBS insertion: what is the new idom of each affected node?
NCA(x, y) — every affected node is re-hung directly below the nearest common ancestor of the new edge's endpoints; unaffected nodes keep their idoms.
DBS insertion: where in LLVM and what complexity?
SemiNCAInfo::InsertReachable, driven by a priority queue on depth; cost is roughly proportional to the edges of the affected region (times a log), not to N.
dbs-delete¶
Deleting edge x→y: how does LLVM decide what to do?
If y dominates x, nothing changes. Otherwise, if x ≠ idom(y) or y has proper support (HasProperSupport: some remaining predecessor p with NCA(y, p) ≠ y), y stays reachable → DeleteReachable; else DeleteUnreachable.
Deletion: how does LLVM repair the tree?
DeleteReachable: DFS from NCA(x, y) visiting only nodes deeper than it, rerun Semi-NCA on that subtree and reattach it under NCA's idom. DeleteUnreachable: drop the nodes that became unreachable and rebuild the part of the tree they affected.
Deletion: complexity?
Proportional to the size of the rebuilt subtree (Semi-NCA on it); worst case O(N) nodes per deletion, often far smaller.
Deletion is local (Lemma 15.2.5): which nodes can change after deleting u → v, v still reachable?
Only proper descendants of z = NCA(u, v) in the old tree, and z still dominates them. So LLVM rebuilds just z's subtree with Semi-NCA (Georgiadis et al. 2016, Lemma 2.6).
domtree-updater¶
DomTreeUpdater Eager vs Lazy?
Eager applies each update to DT/PDT immediately; Lazy queues updates and flushes them in one batch when a tree is next queried (or on flush()).
What does a batch of CFG updates need before it is applied?
LegalizeUpdates: cancel insert/delete pairs of the same edge and deduplicate, then apply in an order computed by the Semi-NCA batch updater (applyUpdates).
When does LLVM recompute from scratch instead of applying a batch?
If n ≤ 100 blocks, when updates > n; otherwise when updates > n/40 (heuristic in SemiNCAInfo::ApplyUpdates).
cytron-df¶
Define the dominance frontier DF(x).
The set of y such that x dominates a predecessor of y but does not strictly dominate y — where x's dominance ends.
Cytron: how is DF computed bottom-up on the dominator tree?
DF(x) = DF_local(x) ∪ ⋃ DF_up(z) for children z. DF_local: successors y with idom(y) ≠ x. DF_up(z): y ∈ DF(z) with idom(y) ≠ x.
Cytron DF: cost?
O(N + E + Σ|DF|) — linear in the output, but Σ|DF| can be Θ(N²) (e.g. nested repeat-until ladders).
chk-df¶
CHK dominance frontiers: what is the 'runner' loop?
For each join node b (≥ 2 preds) and each pred p: runner = p; while runner ≠ idom(b): add b to DF(runner); runner = idom(runner).
CHK runners: why are only join nodes considered?
If b has one predecessor p, then p = idom(b) and the runner loop does nothing; frontiers only arise at merges.
CHK runners: cost?
O(E + Σ|DF|): each step of a runner adds one frontier entry. Same output bound as Cytron but simpler code, no tree traversal.
Runner characterization of dominance frontiers (Lemma 15.3.7)?
Y ∈ DF(X) iff X is on the dominator-tree path from a predecessor of Y up to, but excluding, idom(Y). Consequences: only join nodes are in frontiers, and CHK's runners compute exactly the frontiers.
idf-worklist¶
Iterated dominance frontier DF⁺(S): definition and use?
Limit of DF₁ = DF(S), DFᵢ₊₁ = DF(S ∪ DFᵢ). For S = blocks defining variable v, DF⁺(S) is where SSA construction places φ-nodes for v.
IDF by worklist: algorithm?
Worklist = S. Pop x; for each y ∈ DF(x) not yet in the result: add y and push y (the new φ is itself a definition of v).
IDF by worklist: cost?
O(Σ|DF(x)| over visited x) per variable — needs precomputed DF sets, which can be quadratic in total.
dj-graph¶
What is a DJ graph?
The dominator tree's D-edges plus the CFG's J-edges: edges x→y where x does not strictly dominate y (x ≠ idom(y)).
Sreedhar–Gao IDF: how does it avoid computing DF sets?
Process defining nodes from deepest dominator-tree level up (priority queue); from each, walk its D-subtree, and for each J-edge to y with level(y) ≤ level(root) add y to IDF (and enqueue it). Each node is visited once.
Sreedhar–Gao: complexity and LLVM location?
O(N + E) per query. LLVM's IDFCalculatorBase::calculate (GenericIteratedDominanceFrontier.h), priority queue keyed by (level, DFS-in number); used by mem2reg and SSAUpdaterBulk.
post-dominance¶
Define post-dominance.
b post-dominates a iff every path from a to the exit passes through b. Computed as dominance on the reverse CFG from a (virtual) exit.
Post-dominators: what if there are several exits or infinite loops?
Add a virtual exit joined to all roots. LLVM's roots are: all blocks without successors, plus for each reverse-unreachable region (infinite loop) one node chosen by FindRoots' FurthestAway heuristic; RemoveRedundantRoots prunes extras.
Post-dominators: cost?
Same as the forward tree algorithm on the reversed graph (Semi-NCA in LLVM) plus O(N+E) root finding.
control-dependence¶
Define 'b is control dependent on edge a→s'.
b post-dominates s but b does not strictly post-dominate a — a's branch decides whether b runs.
FOW construction of control dependence?
For each CFG edge a→s where s is not a post-dominator of a: walk from s up the post-dominator tree until reaching ipdom(a); every node visited is control dependent on a→s.
Control dependence vs post-dominance frontiers?
b is control dependent on a iff a ∈ PDF(b) (the dominance frontier on the reverse CFG). ADCE uses ReverseIDFCalculator for this; cost O(N + E + output).
Control dependence vs frontiers (Theorem 15.4.6)?
Y is control dependent on X iff X ∈ PDF(Y), the dominance frontier of Y in the reverse CFG with the virtual exit (Cytron et al. 1991).
dfs-edges¶
DFS edge classification: the four kinds?
Tree (to an unvisited node), back (to an ancestor on the stack, incl. self-loops), forward (to a proper descendant already visited), cross (to a node in a finished, unrelated subtree).
How do pre/post numbers classify u→v after DFS?
back: pre(v) ≤ pre(u) and post(v) ≥ post(u); forward/tree: pre(u) < pre(v), post(v) < post(u); cross: pre(v) < pre(u) and post(v) < post(u).
Why is the set of back edges not a property of the graph?
It depends on DFS successor order — in irreducible graphs different orders yield different back-edge sets (in reducible graphs they are exactly the edges whose target dominates the source).
natural-loops¶
Define a natural loop.
For a back edge t→h with h dom t: the loop is h plus all nodes that reach t without passing through h. Loops with the same header are merged.
How is a natural loop body found?
Backward walk (worklist) from each latch over predecessors, stopping at the header. LLVM's LoopInfo does this in discoverAndMapSubloop, processing headers in dominator-tree postorder so inner loops come first.
Natural loops: invariant and cost?
Two natural loops are either disjoint or nested (or share a header and are merged), giving a forest. Cost O(N + E) per loop body, O(N·E) worst case overall; LoopInfo ignores irreducible cycles.
Natural loops are single-entry and nest (Theorem 15.5.5)?
The header h dominates every node of body(h), so edges from outside enter only at h; two natural loops with different headers are disjoint or one contains the other.
tarjan-loops¶
Tarjan's loop nesting (1974): what problem does it solve?
Builds the loop nesting forest of a reducible graph in near-linear time by processing headers in reverse preorder and collapsing found loops with union-find.
Tarjan loop nesting: the key union-find trick?
Each found loop body is unioned into its header, so a later (outer) loop's backward walk jumps from any inner node straight to the inner header via FIND.
Tarjan loop nesting: complexity?
O(E α(E,N)) with union-find; Havlak's algorithm is its extension to irreducible graphs.
havlak¶
Havlak's loop forest: how does it handle irreducible cycles?
A header w collects back-edge predecessors; other predecessors from outside w's DFS subtree ('non-back-preds') mark w irreducible; the loop is the DFS-subtree region reached backwards, with the DFS-earliest entry as header.
Havlak: invariant about headers?
Each loop has exactly one header — the entry with the smallest DFS preorder number; other entries are not headers. Results depend on DFS order.
Havlak vs LLVM CycleInfo?
Same forest given the same DFS: CycleInfo (GenericCycleImpl.h) is Havlak-style with union-find; its DFS explores the last successor first. Cost near-linear, O(E α) with Ramalingam's fix.
steensgaard¶
Steensgaard's loop forest: construction?
Find the non-trivial SCCs of the graph; each is a loop, and its headers are all nodes with a predecessor outside the SCC. Remove the edges into headers from inside, recurse on the SCCs.
Steensgaard vs Havlak on an irreducible cycle?
Steensgaard treats every entry node as a header (several headers per loop), Havlak picks one (DFS-earliest). Steensgaard's result is DFS-order independent.
Steensgaard: complexity?
O(N·(N+E)) worst case — one Tarjan SCC pass per nesting level.
t1-t2¶
T1 and T2 transformations?
T1: remove a self-loop. T2: if node n has a unique predecessor m, merge n into m. A CFG is reducible iff T1/T2 reduce it to a single node.
T1/T2: is the limit graph unique?
Yes — T1/T2 are confluent, so any application order gives the same limit graph; irreducible iff that limit has more than one node.
T1/T2: cost?
Naive repeated scanning is O(N·E); with worklists and union-find merging, near-linear.
intervals¶
Allen–Cocke interval I(h)?
Maximal single-entry subgraph with header h: repeatedly add any node all of whose predecessors are already in I(h).
Derived sequence of a CFG?
G₀ = G; Gᵢ₊₁ = interval graph of Gᵢ (each interval collapsed to one node). It reaches a fixed point; G is reducible iff that limit is a single node.
Intervals: cost and use?
O(N+E) per derivation, up to O(N) derivations. Historically used for interval-based dataflow analysis (Allen–Cocke 1976).
reducibility-dfs¶
DFS test for reducibility?
Do any DFS; the graph is reducible iff every retreating (back) edge t→h has h dominating t.
Why is the DFS back-edge test DFS-order independent?
In a reducible graph the retreating edges are the same for every DFS (the dominator back edges); if any DFS finds a retreating edge whose target doesn't dominate its source, the graph is irreducible.
DFS reducibility test: cost and LLVM location?
O(N + E) given a dominator tree. LLVM: containsIrreducibleCFG (CFG.h), which walks blocks in RPO using LoopInfo to recognise loop back edges.
Characterizations of reducibility (Theorem 15.6.4)?
Equivalent: T1/T2 reduces G to one node; for some (equivalently every) DFS every retreating edge u → v has v dom u; removing the dominance back edges leaves a DAG; every cycle contains a node dominating all of its nodes; no (*) subgraph (Hecht–Ullman 1974).
node-splitting¶
Node splitting: what does it do?
Duplicates a node with multiple predecessors so each copy has fewer entries, converting an irreducible CFG to an equivalent reducible one.
Node splitting: cost?
Code size can grow exponentially in the worst case (Carter, Ferrante, Thomborson, POPL 2003), so compilers avoid it or bound it.
What does LLVM do instead of node splitting?
FixIrreducible inserts a guard/dispatch block (a new header branching on which entry was taken); WebAssembly's lowering similarly uses dispatch blocks. No code duplication.
loop-simplify¶
Loop-simplify form: three guarantees?
A preheader (single out-of-loop predecessor of the header, branching only to it), a single backedge (one latch), and dedicated exit blocks (every exit's preds are in the loop).
Why do transforms want a preheader?
A single place to hoist loop-invariant code (LICM) or insert setup, executed exactly once before the loop.
LoopSimplify: cost?
Linear in the loop's size per loop — each requirement is fixed by splitting at most a few edges (SplitBlockPredecessors); it updates DT/LoopInfo incrementally.
lcssa¶
What is LCSSA (loop-closed SSA)?
Every value defined in a loop and used outside is used only via φ-nodes in the loop's exit blocks.
Why LCSSA helps loop transforms?
Out-of-loop uses all go through the exit φs, so rewriting a loop (unroll, unswitch, vectorise) only needs to update those φs, not arbitrary uses.
LCSSA: construction and LLVM location?
For each out-of-loop use, insert φs in the exit blocks (and IDF-placed φs beyond) with SSAUpdater. LLVM: formLCSSAForInstructions (LCSSA.cpp); cost grows with the number of out-of-loop uses and exit blocks.