Flashcards — Chapter 8¶
76 cards. Review them with spaced repetition in the terminal (./course flash 8) or export them to Anki (./course flash export 8). Here, click a card to reveal its back.
tac¶
What is a quadruple?
A three-address instruction stored as (op, arg1, arg2, result): the result has its own name, so instructions can be reordered freely. (Definition 8.1.2)
Why do triples make code motion expensive?
A triple's result is its position; references (k) name positions, so moving one instruction renumbers every reference to the shifted positions: Θ(n) worst case. (Proposition 8.1.11)
What do indirect triples add, and why?
An execution-order array π over the triple table: references still name table slots, so reordering only permutes π. (Definition 8.1.3)
How many TAC instructions does Algorithm 8.1.4 emit for an expression with o ordinary operators and q short-circuit operators (no destination)?
o + 5q: one per operator, and two tests, two constant assignments and one goto per && or ||. (Proposition 8.1.11)
stack-bytecode¶
What does a stack-height assignment h need to be consistent?
h(0) = 0, h(i) ≥ ρ(c_i) (enough operands), and h(j) = h(i) + δ(c_i) for every successor j of every reachable i. (Definition 8.1.5)
What does Algorithm 8.1.6 (stack-height verification) cost, and why is its answer unique?
O(n): each instruction enters the worklist once. Heights are forced along a shortest path from instruction 0, so a consistent assignment is unique on reachable code. (Theorem 8.1.13)
What does the JVM's max_stack correspond to?
The maximum of the consistent height assignment: verified code never exceeds it, so a frame can allocate a fixed operand array. (Corollary 8.1.14)
What is the typed version of stack-height consistency in WebAssembly?
The validator assigns a type to every stack slot; at a join (end of if, block) both paths must leave the declared result types, e.g. 'expected [i64] but got [i32]'.
register-bytecode¶
What does Lua's MODK A B C do?
R[A] := R[B] % K[C]: register operand and constant operand in one instruction, where stack code needs load, push, rem. (Definition 8.1.8)
How does stack code become register code?
Stack slot k at height h(i) becomes register s_k; each instruction reads and writes the registers at its heights (Algorithm 8.1.9), then copies are propagated within blocks.
For binary expression trees, what is the ratio of register to stack instructions?
o/(ℓ + o) with ℓ = o + 1 leaves, i.e. below 1/2; Shi et al. measured more than 47% fewer executed instructions on real JVM code. (Proposition 8.1.16)
What is an accumulator register machine (V8 Ignition)?
A register VM with one implicit accumulator operand and destination: Add r0 means acc = acc + r0. Shorter instructions, extra Lda/Sta moves.
leaders¶
What are the three leader rules?
Instruction 0; every jump target; every instruction immediately after a jump (goto, if, ifz, return). (Algorithm 8.2.3)
Is an instruction with a label always a leader?
No: only if some jump names the label. Unreferenced labels do not split blocks, so the leaders partition is maximal. (Theorem 8.2.9)
Why is the leaders partition the only maximal basic-block partition?
Every leader other than 0 is a jump target or follows a jump, so no basic block can contain it except at its start; any basic-block partition refines the leaders partition. (Theorem 8.2.9)
How long does the leaders algorithm take?
O(n) with a boolean array of leaders (O(n + m log m) if leaders are sorted): one pass plus a label table.
critical-edges¶
What is a critical edge?
An edge u→v where u has more than one successor and v more than one predecessor. (Definition 8.2.5)
Why can no existing block hold code that runs only on a critical edge?
The end of u also runs on u's other outgoing edge, and the start of v on v's other incoming edge. (Lemma 8.2.11)
How many blocks and edges does splitting all critical edges add?
One new block and one new edge per critical edge; afterwards no edge is critical. (Theorem 8.2.12)
How are critical edges split in a TAC listing?
Taken edge: retarget the jump to a new block crit: goto L. Fall-through edge: insert a goto right after the branch. (Algorithm 8.2.6)
dfs-orders¶
What is reverse postorder (RPO)?
The DFS postorder reversed: rpo(n) = |N_r| − 1 − post(n). (Definition 8.2.7)
What is the key property of RPO?
Every edge that is not a DFS back edge goes from an earlier to a later node: RPO is a topological order of the graph without its back edges. (Theorem 8.2.14)
Why is preorder not a substitute for RPO?
Cross edges point from a later-visited subtree to an earlier one in preorder, e.g. B7→B8 in the running example. (Corollary 8.2.15)
When is an edge a back edge during DFS?
When its target is still on the DFS stack (an ancestor of the source, or the source itself). (Lemma 8.2.13)
What does DFS cost, and why use an explicit stack?
Θ(m + e); recursion depth can reach the number of blocks, which is huge in generated code, so LLVM's po_iterator keeps an explicit stack.
ast-hir¶
What is the difference between an AST and an HIR?
An HIR is an AST after desugaring into a smaller core (e.g. while → loop/if/break in rustc) and name resolution, often with types. (Definition 8.3.2)
How does rustc desugar while c { b }?
loop { if c { b } else { break } }, tagged LoopSource::While for diagnostics. (Algorithm 8.3.3)
Why is desugaring while correct?
Each unrolling of the loop rule corresponds to one iteration with a true test, and the final false test to the break. (Theorem 8.3.6)
How much smaller can a DAG be than its tree?
Exponentially: e_{k+1} = e_k + e_k has 2^{k+1} − 1 tree nodes but k + 1 DAG nodes. (Proposition 8.3.9)
value-numbering¶
What is the key of an operation in local value numbering?
(op, VN(operand1), VN(operand2)), with the operand numbers sorted for commutative operators. (Definition 8.3.4)
What is the kill rule of local value numbering?
When x is reassigned, remove x from the holders of its old value number; a key whose value has no holder must be recomputed. (Algorithm 8.3.5)
Is local value numbering complete?
Only syntactically: it finds equal keys, not algebraic identities like x·2 = x + x. (Theorem 8.3.8)
What does local value numbering cost?
O(k) expected for a block of k instructions with hashing; Θ(k²) with a hash in which all keys collide.
phi-ssa¶
What is strict SSA?
Every name has one definition, and every use (phi operands at the end of the predecessor) is dominated by its definition. (Definition 8.4.1)
Why must phis be evaluated in parallel?
All phis of a block read their operands before any writes, otherwise swapping two values (x = φ(…, y), y = φ(…, x)) breaks. (Definition 8.4.2)
Where is a phi operand used?
At the end of the corresponding predecessor, not in the phi's block, which is what dominance must be checked against.
How many phis can minimal SSA need?
Θ(m·V) in the worst case (a chain of diamonds each assigning all V variables); linear in practice.
block-args¶
How do phi functions map to block arguments?
The i-th phi of B becomes B's i-th parameter; the branch P→B passes the i-th phi's entry for P. (Theorem 8.4.10)
What can block arguments express that phis cannot?
Two edges from the same block to the same target with different arguments, e.g. cbr c, B(1), B(2); converting to phi needs one edge split first. (Lemma 8.4.11)
What are the lab's SSA rules S1–S4?
S1 single definition; S2 definitions dominate uses; S3 argument counts match parameter counts; S4 unique blocks, existing targets, entry without parameters or predecessors. (Definition 8.4.4)
How does the naive block-argument SSA construction handle joins?
Every join block takes every source variable as a parameter and every edge passes the current values: valid but not minimal (81 parameters for the running example, 4 after pruning). (Algorithm 8.4.7)
sea-of-nodes¶
What is a floating node in a sea of nodes?
A pure node with only data inputs and no control input; its block is chosen by global code motion. (Definition 8.5.1)
How does global code motion choose a block?
Between early (deepest input block) and late (LCA of use blocks) on the dominator tree, the latest block of minimal loop depth. (Algorithm 8.5.3)
Why is GCM's schedule legal?
Every block on the dominator-tree path from early to late is dominated by all inputs and dominates all uses. (Theorem 8.5.9)
Why did V8 leave the sea of nodes?
Effect and control chains mirror the CFG anyway, graphs are hard to read, scheduling and visitation are hard, and it is cache-unfriendly; the CFG-based Turboshaft halved compile time.
dependence-graphs¶
When is block Y control dependent on block X?
X has an edge X→Z with Y post-dominating Z, and Y does not strictly post-dominate X. (Definition 8.5.4)
What are γ and θ nodes in an RVSDG?
γ: a conditional with one region per alternative; θ: a tail-controlled loop whose region's results feed the next iteration. Every region is acyclic. (Definition 8.5.5)
How many control-dependence edges can a PDG have?
O(m²) in the worst case (the post-dominator walk may add O(m) per CFG edge). (Algorithm 8.5.6)
When do isomorphic PDGs guarantee equivalent programs?
For structured programs without unrecorded aliasing (Horwitz–Prins–Reps 1988). (Theorem 8.5.11)
egraphs¶
What is the congruence invariant of an e-graph?
Two e-nodes with the same operator and canonically equal children are in the same e-class. (Definition 8.5.7)
What does egg's rebuilding change?
Congruence repair is deferred to the end of each saturation iteration and done in batches, instead of after every merge. (Algorithm 8.5.8)
Can equality saturation blow up?
Yes: with associativity and commutativity the e-graph for x1 + … + xk has at least 2^k − 1 classes, so saturation needs node limits. (§5 of Lesson 8.5)
Why is equality saturation sound?
Every merge joins classes equal by a sound rule or by congruence, and equality is an equivalence relation. (Theorem 8.5.12)
cps¶
What is continuation-passing style?
No function returns: each takes a continuation and calls it with its result, so evaluation order, intermediate values and control are explicit, and every call is a tail call. (Definition 8.6.1)
What is an administrative redex?
A β-redex created by the CPS transform itself, such as (λk. k x)(λa. …). The naive transform creates one per subterm application. (Definition 8.6.2)
How does the one-pass CPS transform avoid administrative redexes?
It passes meta-level continuations (compiler functions), so the reductions happen at compile time. (Algorithm 8.6.3, Theorem 8.6.8)
What does the CPS transform cost?
O(|e|): one emission per node with the one-pass transform.
anf¶
What is A-normal form?
Every operand is a variable or constant and every intermediate result is let-bound; with join points for merges. (Definition 8.6.4)
Why does ANF need join points?
Without them, the code after an if is duplicated into both branches: exponential size for a chain of ifs. With them, size is linear. (Theorem 8.6.9)
How are CPS and ANF related?
ANF = un-CPS(administrative normal form of CPS(e)). (Theorem 8.6.10, Flanagan et al. 1993)
ssa-anf¶
How does Kelsey's translation nest blocks?
Each block becomes a join point defined inside its immediate dominator, after that block's lets; loop headers become recursive join points. (Definition 8.6.6)
What SSA rule corresponds to lexical scoping in ANF?
Definitions dominate uses. (Theorem 8.6.12)
Why can an SSA or scoped-ANF interpreter use one flat environment?
In strict SSA the most recent value of a name is always the one that dominates the current use. (Corollary 8.6.13)
What does SSA-to-ANF translation cost?
O(n + m log m) given the dominator tree: each block is emitted once, children sorted by RPO.
mlir¶
What is partial conversion in MLIR?
A conversion that rewrites what its patterns can and leaves operations not explicitly illegal in place, giving a mixed-dialect module. (Definition 8.7.2)
When does dialect conversion terminate?
When every pattern produces only legal operations or operations of smaller measure μ (a well-founded measure); MLIR detects recursive pattern application. (Theorem 8.7.9)
What does progressive lowering mean?
Lower a module one dialect at a time (e.g. scf → cf → llvm), keeping higher abstractions as long as passes need them.
How does MLIR turn block arguments into LLVM phis?
connectPHINodes in ModuleTranslation.cpp: each block argument becomes a phi with one entry per incoming branch.
ir-pipelines¶
Why are facts lost, never gained, down a pipeline of IRs?
Lowerings are functions: two programs with the same image at an earlier level have the same image at every later level, so a later-level fact is already determined earlier; but lowering is not injective, so some earlier facts are lost. So run each analysis at the highest level where its facts are expressible. (Proposition 8.7.11)
Name the IR pipelines of rustc, swiftc and GCC.
rustc: HIR → THIR → MIR → LLVM IR; swiftc: AST → SIL → LLVM IR; GCC: GENERIC → GIMPLE → RTL.
How do rustc MIR and PIR represent a checked +?
An overflow predicate (AddWithOverflow / saddo), an assert that traps, and the wrapping add. (Algorithm 8.7.6)
What does a pipeline of IRs cost?
The sum of the stages; each stage is usually linear, and several IRs may be alive at once (rustc keeps HIR, THIR per body, MIR).
pir¶
Is PIR in SSA form?
No: PIR locals are mutable storage assigned by several statements; SSA is built by the shared back end (alloca + mem2reg, later your Ch 16 pass). (Definition 8.7.7)
How does PIR become SSA?
One alloca per local, loads and stores per statement, then mem2reg/SROA places phis for promotable allocas. (Algorithm 8.7.8)
Why is the alloca scheme for PIR correct?
By induction on steps, slot %_k.addr always holds local _k; mem2reg preserves behavior by SSA construction's correctness. (Theorem 8.7.12)
How many phis does gcd in PIR get after SROA?
Three: a and b at the loop header bb1, t at the join bb5; 5 locals, 7 blocks. (Lesson 8.7 §3)