Flashcards — Chapter 16¶
77 cards. Review them with spaced repetition in the terminal (./course flash 16) or export them to Anki (./course flash export 16). Here, click a card to reveal its back.
minimal-ssa¶
Minimal SSA: where are the phis for v?
At DF⁺(defs(v)), the iterated dominance frontier of the blocks that assign v (the entry counts, for the initial value).
Minimal SSA: what is "minimal" about it?
It is the least placement determined by definition sites alone (Theorem 16.1.10): every phi merges two different definitions. It can still contain dead phis.
Minimal SSA: cost of placement?
One DF⁺ per variable: O(n + m) with Sreedhar–Gao, or the worklist over precomputed frontiers, whose total size can be Θ(n²).
Phi semantics: sequential or parallel?
Parallel: all phis of a block read their operands (from the incoming edge) before any writes its result. Sequential execution breaks swaps.
semi-pruned-ssa¶
Semi-pruned SSA: which variables get phis?
Only global names: variables that are upward-exposed (read before written) in some block. Block-local temporaries get none.
Semi-pruned SSA: what dead phis can remain?
Phis of global names at frontier blocks where the name is not live (y at B in the running example).
Semi-pruned SSA: cost over minimal?
One linear scan for upward-exposed uses; no liveness analysis.
pruned-ssa¶
Pruned SSA: placement formula?
Φ_pruned(v) = DF⁺(defs(v)) ∩ {B : v ∈ LiveIn(B)}.
Pruned SSA: key theorem?
Pruned = minimal minus the dead phis (Theorem 16.1.14); pruned ⊆ semi-pruned ⊆ minimal.
Pruned SSA: cost?
Liveness per variable (or a backward live-in walk per alloca, as in LLVM) plus the filtered IDF.
cytron¶
Cytron et al.: the two phases?
(1) phi placement at DF⁺ of definition blocks; (2) renaming by a dominator-tree preorder walk with one stack per variable.
Cytron renaming: invariant?
At every point the top of v's stack is the definition of v that reaches that point; a block pops what it pushed when its dominator subtree is done (Lemma 16.2.5).
Cytron renaming: how are phi operands filled?
At the end of each block, for each successor S, the operand for this edge of each phi in S is the current top of the variable's stack.
Cytron: complexity?
O(Σ|DF| + phis + uses) overall; frontiers can be quadratic (nested repeat-until loops), phis stay linear in practice.
sreedhar-gao¶
Sreedhar–Gao: what graph does it walk?
The DJ graph: dominator-tree (D) edges plus the other CFG edges (J edges), with nodes processed deepest level first from a priority queue.
Sreedhar–Gao: how does LLVM make it pruned?
IDFCalculator::setLiveInBlocks: a node outside the live-in set is never added to DF⁺ (the result equals DF⁺ ∩ LiveIn).
Sreedhar–Gao: complexity?
O(n + m) per set of definition blocks, with no frontier materialized (Theorem 16.2.7).
braun¶
Braun et al.: what does readVariable do in an unsealed block?
Creates an incomplete phi, records it, and returns it; sealBlock fills its operands later.
Braun et al.: when is a phi trivial?
When all its operands, ignoring the phi itself, are one value v; it is replaced by v and its users are re-checked.
Braun et al.: why the SCC pass?
On irreducible CFGs a set of phis can reference only each other and one outside value; each phi alone is non-trivial. Tarjan SCCs on the phi graph find and remove them.
Braun et al.: which phis survive (Theorem 16.3.8)?
No set of survivors is redundant (Definition 16.3.1), and every survivor lies in the pruned placement. Each survivor is reached by at least two distinct non-phi values through phi chains, but that alone does not guarantee survival: a redundant pair behind a real merge phi is removed.
Braun et al.: dominance needed?
None: no dominator tree, no frontiers, no liveness. Used by Cranelift, Go (small functions) and LLVM's SSAUpdater.
aycock-horspool¶
Aycock–Horspool: the algorithm?
Place a phi for every variable at every join block (maximal SSA), rename, then apply R1/R2 until nothing changes: φ(x,…,x) and φ(x|y,…,x|y) → y.
Aycock–Horspool: result quality?
Its phis lie in minimal SSA on reducible CFGs (Theorem 16.3.9); dead phis stay, redundant SCCs stay on irreducible CFGs.
Aycock–Horspool: cost?
The start is n_join × |V| phis (quadratic, Proposition 16.3.10), then repeated sweeps.
mem2reg¶
mem2reg: which allocas are promotable?
Entry-block allocas whose users are only non-volatile loads, stores into them and lifetime markers, all of one type (Definition 16.4.1).
mem2reg: the two fast paths?
rewriteSingleStoreAlloca (one store: loads it dominates take the value) and promoteSingleBlockAlloca (all uses in one block).
mem2reg: how is the general case placed and cleaned?
Live-in blocks by a backward walk (ComputeLiveInBlocks), IDFCalculator with live-in blocks (pruned), renaming, then simplifyInstruction on the new phis.
sroa¶
SROA: what does it do?
Splits an aggregate alloca into slices and partitions by byte ranges, rewrites them into scalar allocas, and promotes those with mem2reg's code.
SROA: why is it needed?
Struct locals are accessed with memcpy, GEPs and differently typed loads, so they are not promotable as a whole.
SROA: cost?
About O(u log u) per alloca for sorting slices (u = uses); the most expensive of the three promotion tools.
ssaupdater¶
SSAUpdater: when is it used?
When a transformation creates extra definitions of one value (loop rotation, jump threading, LCSSA, LICM promotion) and uses must be rewired to the reaching one.
SSAUpdater: how does it find the value at a use?
GetValueInMiddleOfBlock walks predecessors backwards like Braun's readVariable and places phis on the explored subgraph, reusing an existing matching phi.
SSAUpdaterBulk vs SSAUpdater?
Bulk: many variables at once with live-in blocks + IDFCalculator (needs a dominator tree); SSAUpdater: one value, on demand, cost proportional to the explored region.
phi-nodes¶
Phi nodes: what ties them to the CFG?
Each incoming entry names its predecessor block; the verifier requires exactly one entry per predecessor edge (checked in Verifier::visitBasicBlock).
Phi nodes: cost of CFG edits?
Deleting, splitting or redirecting an edge must update every phi of the target block: O(phis) per edit.
Phi nodes: where must they be?
Grouped at the top of the block, before any other instruction; they execute as one parallel copy on entry.
block-arguments¶
Block arguments: what are they?
Blocks declare parameters and every branch passes arguments; the branch is the parallel copy (Kelsey's SSA = CPS correspondence).
Block arguments: which edits are local?
Adding or deleting an edge touches only the branch in the predecessor; deleting a parameter touches every predecessor.
Block arguments: who uses them?
MLIR, Swift SIL and Cranelift. They are equivalent to phi nodes (Theorem 8.4.10).
upsilon-phi¶
Upsilon/phi: what does Upsilon(v, ^x) do?
Writes v into the shadow variable of phi x; x = Phi() at the merge reads the shadow. Blocks carry no SSA edge data.
Upsilon/phi: why no lost copy or swap?
Upsilons write shadows, never names that other code reads; the Phi reads them once at the merge (Theorem 16.5.8).
Upsilon/phi: cost?
CFG edits are O(1) for SSA; validating that every path to a Phi passes an Upsilon needs a dataflow pass. Used by WebKit B3 and DFG.
naive-copies¶
Naive destruction (Cytron): what does it do?
For each edge P → B, append copies param = arg at the end of P, before its branch.
Naive destruction: when is it wrong?
With a lost copy (a copy for one edge clobbers a name live on another path) or a swap (a copy reads a name an earlier copy of the same edge wrote).
Naive destruction: when is it correct?
With no lost-copy and no swap edge, in particular on conventional SSA whose phi operands are names (Theorem 16.6.6). Cost O(phi arguments).
briggs¶
Critical edge?
An edge whose source has several successors and whose target has several predecessors; copies on it have no block of their own.
Briggs et al.: fix for the lost copy?
Split the critical edge (or copy at the start of a single-predecessor target) so the copies run only on their edge.
Briggs et al.: fix for the swap?
Treat the edge's copies as one parallel copy and order them, using a temporary for cycles.
sreedhar-cssa¶
Sreedhar Method I?
Isolate every phi: a fresh name per operand copied at the end of each predecessor, a fresh result copied at block entry; the result is CSSA, fixed by renaming classes.
Sreedhar Method III?
Insert copies only for phi resources whose live ranges really interfere, choosing among result/operand copies by liveness at L0 and Li (the four cases).
Sreedhar CSSA: what property makes destruction trivial?
No two names of one phi congruence class interfere, so each class can become one variable (Theorem 16.6.8).
boissinot¶
Boissinot et al.: main idea?
Isolate phis with parallel copies, coalesce aggressively with value-based interference, sequentialize the rest optimally.
Boissinot et al.: value-based interference?
Names interfere only if their live ranges intersect and their values differ (a copy and its source do not interfere).
Boissinot et al.: interference check cost?
Linear in the two classes' sizes, by walking members in dominance order with a stack; no interference graph (Algorithm 16.7.4).
parallel-copy¶
Parallel copy: minimum number of moves with one spare location?
Non-trivial copies + pure cycles (Theorem 16.7.6).
Parallel copy: what is a pure cycle?
A cycle in the copy graph with no edge leaving it; a cycle with a copy hanging off it needs no temporary.
Parallel copy: key trick of the sequentializer?
After d ← s, redirect later readers of s to d (loc[s] = d), so s becomes free; cost O(k) per edge.
coalescing¶
Coalescing: aggressive vs conservative?
Aggressive merges whenever there is no interference (SSA destruction); conservative (Briggs/George) only if the graph stays K-colorable (register allocation).
Coalescing: is optimal coalescing easy?
No: NP-complete in general, even on SSA; the visiting order is a heuristic (LLVM: loop depth, GCC: cost).
Coalescing: invariant?
No congruence class ever contains two interfering names; merging only after the class-interference test fails (Theorem 16.7.8).
ssi¶
e-SSA: what is a π-assignment?
A copy x' = π(x) on an outgoing edge of a branch that tests x, carrying the edge's predicate; dominated uses are renamed to x'.
SSI: what is a σ-function?
The dual of a phi at a branch: (x¹,…,xᵏ) = σ(x) gives each successor edge its own name; placed at the iterated post-dominance frontier of uses.
e-SSA in LLVM: cost and form?
PredicateInfo inserts no-op bitcasts before the branch, only where some use is dominated by the edge; O(n + m + u log u).
gated-ssa¶
Gated SSA: the three gating functions?
γ(p, t, f) at merges, μ(init, iter) at loop headers, η(P, v) at loop exits.
Gated SSA: how is a γ tree built?
Recursively from idom(M) over the branch structure; an edge into M gives its operand, an edge that cannot reach M gives ⊥; memoize and fold equal or ⊥ sides.
Gated SSA: cost?
O(|R|) per merge with memoization and sharing; exponential if every path is expanded (Proposition 16.8.20).
memory-ssa¶
Memory SSA: the three access kinds?
MemoryDef (may write: defines a new memory version from the previous), MemoryUse (reads a version), MemoryPhi (merges versions); liveOnEntry is M0.
Memory SSA: how is it built?
As minimal SSA for one variable M: MemoryPhis at IDF of the blocks with MemoryDefs (no live-in filter in LLVM), then one renaming walk.
Memory SSA: does MemoryUse(n) name the clobbering store?
No: it names the reaching version; the walker (getClobberingMemoryAccess) asks alias analysis to find the real clobber, capped at 100 steps.
array-ssa¶
Array SSA: what does a store A[k] := v become?
A partial array [k ↦ v] and a definition φ that merges it with the previous array by timestamps.
Array SSA: heap arrays?
One array H_f per field f indexed by object reference: p.f = v is H_f[p] := v (Jikes RVM, redundant load elimination).
Array SSA: cost?
Cytron per array with one extra definition per store; timestamps are an analysis device, not executed.
hashed-ssa¶
HSSA: μ and χ?
χ: a may-definition a_j = χ(a_i); μ: a may-use; inserted from alias information at stores through pointers and calls.
HSSA: zero version?
A version with no real occurrence whose value comes from a χ (through φs); all are numbered 0 and not tracked.
HSSA: what is hashed?
Every expression, bottom-up, into one table: identical operator and operand nodes give the same node, so equal expressions are found for free.
HSSA: why is it costly without virtual variables?
s stores that may each hit V variables need s·V χs (Proposition 16.8.21).