Theory test — Chapter 16¶
51 questions; you pass at 80 %. This page shows the questions only: take the test in the terminal, where every answer is graded and explained.
./course quiz 16 # interactive
./course quiz template 16 -o answers/ch16.yaml # or fill in a file ...
./course quiz grade 16 # ... and grade it
flavor-counts · mapping · 1 pt · 01-ssa-properties-and-flavorsThe running example (labs/ch16-ssa-construct/inputs/running.tac), blocks A–I:
A: i = 0 ; x = 1
B: y = add x, i ; ifz i goto E
C: x = add y, 2 ; t = lt x, 20 ; ifz t goto H
D: y = mul y, 2
E: t = gt y, 0 ; ifz t goto H
F: x = add x, y ; y = sub y, 7 ; goto G
G: t = rem x, 3 ; if t goto E
H: i = add i, 1 ; t = lt i, 4 ; if t goto B
I: return x
How many phis does Cytron's construction place in each flavor?
minimal, semi-pruned, prunedminimal-dead-phi · number · 1 pt · 01-ssa-properties-and-flavorsIn minimal SSA of the running example (previous question), how many of the 10 phis are
dead, i.e. never reach a non-phi use through phi chains?
phi-parallel · mapping · 1 pt · 01-ssa-properties-and-flavorsBlock H begins with a2 = phi [1, entry], [b2, H] and b2 = phi [2, entry], [a2, H].
Control arrives from H on the back edge with a2 = 3 and b2 = 7. Give the values of a2 and
b2 after H's phis execute, with the semantics of LLVM (and of block arguments).
a2, b2semi-pruned-global · set · 1 pt · 01-ssa-properties-and-flavorsWhich variables of the running example (see flavor-counts) are global in Briggs et
al.'s sense (upward-exposed in some block)?
pruned-theorem · single · 1 pt · 01-ssa-properties-and-flavorsWhich statement about pruned SSA is a theorem of Lesson 16.1?
- Pruned SSA has the fewest phis of any correct SSA form of the program.
- Pruned SSA's phis are exactly minimal SSA's phis minus the dead ones.
- Pruned SSA and semi-pruned SSA always place the same phis for global names.
- Pruned SSA can place a phi outside DF⁺(defs(v)).
llvm-where-livein · single · 1 pt · 01-ssa-properties-and-flavorsIn PromoteMem2Reg::ComputeLiveInBlocks (PromoteMemoryToRegister.cpp), a block both
loads from and stores to the alloca. How does LLVM decide whether the block is live-in?
- It is always live-in, because it contains a load.
- It scans the block from the top: if the first reference to the alloca is a store, the block is not live-in; if it is a load, it is.
- It asks the IDFCalculator.
- It is never live-in, because it defines the alloca.
cytron-rename-trace · mapping · 1 pt · 02-frontier-based-constructionPruned SSA of the running example (flavor-counts), with the oracle's naming: versions are
numbered per variable in dominator-tree preorder with children in RPO (A, B, C, D, E, F,
G, H, I), phis first; x.0 is A's x = 1, the phi for x at B is x.1, C defines x.2, the phi
at E is x.3, F defines x.4 and the phi at H is x.5. Which name of x does each block read?
(F: in x = add x, y; G: in t = rem x, 3; I: in return x.)
F, G, Icytron-phi-operands · mapping · 1 pt · 02-frontier-based-constructionSame program and naming as cytron-rename-trace. The phi x.5 at H has one operand per
predecessor C, E and G. Give each operand.
C, E, Gcytron-invariant · single · 1 pt · 02-frontier-based-constructionWhat is the invariant of Cytron's renaming walk (Lemma 16.2.5)?
- Every stack holds exactly one name per block visited so far.
- When the walk is at a point p, the top of v's stack is the name of the definition of v that reaches p (the most recent one on every path).
- The stacks are empty whenever the walk enters a join block.
- The top of v's stack is always the phi of the nearest DF⁺ block.
sg-live-in · set · 1 pt · 02-frontier-based-constructionAlgorithm 16.2.4 (Sreedhar–Gao with a live-in filter) runs for y in the running example
with S = defs(y) = {A, B, D, F} and live-in filter L = {C, D, E, F, G}. Which blocks does it
return?
llvm-where-phiblocks-sort · text · 1 pt · 02-frontier-based-constructionIn PromoteMem2Reg::run, after IDF.calculate(PHIBlocks) the phi blocks are sorted.
Which BasicBlock member function supplies the sort key?
braun-trivial · single · 1 pt · 03-construction-without-frontiersWhen is a phi trivial in Braun et al.'s sense (Definition 16.3.1)?
- When it has exactly one predecessor block.
- When all its operands, ignoring references to the phi itself, are the same single value.
- When its result is not used.
- When all its operands are constants.
braun-scc · mapping · 1 pt · 03-construction-without-frontiersThe corpus listing irreducible-two-entry (c is never assigned, so it is 0):
x = 5
if c goto R
L:
y = add y, 1
t = lt y, 3
ifz t goto X
R:
goto L
X:
return x
How many phis does Braun et al.'s construction leave with trivial-phi removal only, and
with the redundant-SCC pass (Algorithm 16.3.4) as well?
trivial-only, with-sccbraun-seal · single · 1 pt · 03-construction-without-frontiersWhen may Braun et al.'s algorithm seal a block?
- As soon as the block itself has been filled.
- As soon as all its predecessors have been filled, because no new predecessor edge can appear.
- Only after the whole function has been processed.
- When the dominator tree says the block has no back edges.
ah-count · number · 1 pt · 03-construction-without-frontiersAycock–Horspool on the running example (flavor-counts): a phi for each of the 4 variables
at each of the 3 join blocks, renaming with copy folding, then the two removal rules until
nothing changes. How many phis are left?
llvm-where-phi-simplify · text · 1 pt · 03-construction-without-frontiersAfter renaming, PromoteMem2Reg::run loops over the new phis and folds the redundant ones,
which is Aycock and Horspool's cleanup. Which LLVM function does it call on each phi?
mem2reg-table · mapping · 1 pt · 04-llvm-mem2reg-sroa-ssaupdaterclang -O0 compiles the fib loop of Lesson 16.4 (int a = 0, b = 1; for (int i = 0; i < n; i++) { int t = a; a = b; b = t + b; } return a;) with the allocas n.addr, a, b, i
and t. How many phis does mem2reg create for each?
n.addr, a, b, i, tllvm-where-single-store · text · 1 pt · 04-llvm-mem2reg-sroa-ssaupdaterPromoteMem2Reg::run tries two special cases before computing any frontier. What is the
name of the function that handles an alloca with exactly one store?
sroa-partitions · number · 1 pt · 04-llvm-mem2reg-sroa-ssaupdaterIn struct pair { int a, b; } code (Lesson 16.4), the alloca %p (8 bytes) has the slices
memcpy [0, 8), load p.a [0, 4), load p.b [4, 8) and memcpy [0, 8). Into how many partitions
does SROA split it?
sroa-why · single · 1 pt · 04-llvm-mem2reg-sroa-ssaupdaterWhy does mem2reg alone leave a struct local of struct pair in memory?
- Structs cannot be held in SSA registers in LLVM.
- The alloca is accessed through memcpy, GEPs and loads of different types, so it is not promotable (Definition 16.4.1); SROA first splits it into scalar allocas with only whole loads and stores.
- mem2reg only promotes allocas that have exactly one store.
- The struct escapes to a call.
ssaupdater-phi · single · 1 pt · 04-llvm-mem2reg-sroa-ssaupdaterLoop rotation clones the header, so %sq has two definitions: 0 in the new preheader and
%sq at the bottom of the loop. The use at the top of the body asks
GetValueInMiddleOfBlock(body). What does SSAUpdater produce?
- The value 0, because the preheader dominates the body.
- A new phi in the body: [0, preheader], [%sq, latch].
- A phi in every block of DF⁺ of both definitions, computed with frontiers.
- An error: SSAUpdater requires one definition per value.
ssaupdater-vs-bulk · single · 1 pt · 04-llvm-mem2reg-sroa-ssaupdaterHow does SSAUpdaterBulk differ from SSAUpdater?
- It handles many variables at once with live-in blocks and IDFCalculator, and needs a dominator tree; SSAUpdater answers one value at a time by walking predecessors.
- It works only on reducible CFGs.
- It produces minimal instead of pruned SSA.
- It removes phis instead of creating them.
llvm-where-phi-verify · text · 1 pt · 05-phi-block-arguments-upsilonIn llvm/lib/IR/Verifier.cpp, which Verifier member function checks "PHINode should have
one entry for each predecessor of its parent basic block!"?
blockargs-edge-edit · single · 1 pt · 05-phi-block-arguments-upsilonA pass deletes one edge P → B of a CFG. What must it update in each representation?
- Phi nodes: remove P's entry from every phi of B. Block arguments: drop P's branch operands for B; nothing in B changes.
- Nothing in either representation.
- Phi nodes: nothing. Block arguments: remove a parameter of B.
- Both: renumber every value of B.
upsilon-semantics · mapping · 1 pt · 05-phi-block-arguments-upsilonThe swap loop in upsilon/phi form (Lesson 16.5): entry does Upsilon(1, ^a); Upsilon(2, ^b); Upsilon(0, ^i); the loop does a = Phi(); b = Phi(); i = Phi(); i1 = Add(i, 1); ...; Upsilon(b, ^a); Upsilon(a, ^b); Upsilon(i1, ^i). What are a, b and i after the loop's Phis
execute for the second time?
a, b, iupsilon-destruction · single · 1 pt · 05-phi-block-arguments-upsilonWhy does leaving upsilon/phi form need no parallel copies and no edge splitting?
- Because B3 forbids critical edges.
- Each shadow variable becomes an ordinary variable: an Upsilon is a copy into it and a Phi a copy out of it. Upsilons write shadows, never the Phi results that other code reads, so no lost copy or swap can occur.
- Because Phis execute sequentially.
- Because the register allocator inserts the copies later.
naive-lost-copy-value · number · 1 pt · 06-ssa-destructionBriggs et al.'s lost-copy program in block-argument SSA returns 4:
entry: br H(1)
H(x2): x3 = add x2, 1 ; t = lt x3, 5 ; cbr t, H(x3), X()
X: ret x2
What does Cytron's naive translation return (copy x2 = x3 at the end of H, before the
branch)?
naive-cssa-correct · single · 1 pt · 06-ssa-destructionOn which inputs is naive destruction guaranteed correct (Theorem 16.6.6)?
- On every strict SSA program.
- On programs with no lost-copy and no swap edge, in particular conventional SSA whose phi operands are all names.
- Only on programs without loops.
- On any program after copy propagation.
briggs-which-problem · mapping · 1 pt · 06-ssa-destructionFor each problem, which fix does Briggs et al.'s analysis prescribe: split (split the
critical edge) or order (order the copies, with a temporary for cycles)?
lost-copy, swapllvm-where-split-all · text · 1 pt · 06-ssa-destructionIn llvm/lib/CodeGen/PHIElimination.cpp, what is the command-line option that forces
splitting of every critical edge during phi elimination?
sreedhar-method1-count · number · 1 pt · 06-ssa-destructionSreedhar's Method I on the lost-copy program (naive-lost-copy-value): one copy per phi
operand on each incoming edge plus one at the block entry, before any coalescing. How many
copies does the result contain?
sreedhar-method3-case · single · 1 pt · 06-ssa-destructionMethod III on the lost-copy phi x2 = φ(1, x3): the classes of x2 and x3 interfere; x2's
class is live out of H (into X); x3's class is not live on entry to H. Which copy does it
insert, and how many copies does the result have?
- Copy the operand x3 only; 3 copies.
- Copy the result x2 only (x2 := x2' at H's start); 2 copies in total.
- Copy both; 4 copies.
- No copy is needed; 1 copy.
boissinot-value-interference · single · 1 pt · 07-parallel-copies-and-coalescingIn strict SSA, b = a (a copy), and afterwards both a and b are used. Do a and b interfere
in Boissinot et al.'s value-based sense?
- Yes: their live ranges intersect.
- No: they intersect but hold the same value, V(b) = V(a).
- Only if the copy is in a loop.
- Yes, unless b is a phi.
coalesce-lost-copy · number · 1 pt · 07-parallel-copies-and-coalescingLab L2's coalesce method on the lost-copy program: how many copy instructions does the
output contain?
pcopy-moves · number · 1 pt · 07-parallel-copies-and-coalescingWith one spare location t, what is the minimum number of moves for the parallel copy
(a, b, c, d) ← (b, a, d, 5)?
pcopy-sequence · sequence · 1 pt · 07-parallel-copies-and-coalescingRun Algorithm 16.7.5 on (a, b, c) ← (b, c, a) with spare t (pending destinations in the order
a, b, c). Give the moves in order, each written dst=src.
pcopy-fanout · number · 1 pt · 07-parallel-copies-and-coalescingMinimum number of moves (spare t available) for (a, b, c) ← (b, a, a)?
llvm-where-joinvals · text · 1 pt · 07-parallel-copies-and-coalescingIn llvm/lib/CodeGen/RegisterCoalescer.cpp, which member function of JoinVals decides,
for one value number, between CR_Keep, CR_Erase, CR_Replace and CR_Impossible?
ssa-regalloc-preview · single · 1 pt · 07-parallel-copies-and-coalescingWhat property makes register allocation before leaving SSA attractive (Hack's thesis)?
- SSA programs never need spills.
- Interference graphs of strict SSA programs are chordal, so they can be colored optimally in polynomial time.
- Coalescing becomes polynomial.
- Phis disappear during coloring.
essa-pi-count · number · 1 pt · 08-ssa-extensionsHow many π-assignments does Algorithm 16.8.3 (and LLVM's PredicateInfo) insert here?
entry: c1 = lt x, n ; if c1 goto A ; goto R
A: c2 = gt x, 0 ; if c2 goto B ; goto R2
B: y = add x, n ; return y
R: return n
R2: return x
essa-renamed-uses · mapping · 1 pt · 08-ssa-extensionsSame program as essa-pi-count, with π names x1 = π(x) and n1 = π(n) on entry → A,
n2 = π(n) on entry → R, x2 = π(x1) on A → B and x3 = π(x1) on A → R2. Which name does each
use read? Keys: B.x and B.n (in y = add x, n), R.n, R2.x.
B.x, B.n, R.n, R2.xllvm-where-predicateinfo · text · 1 pt · 08-ssa-extensionsIn llvm/lib/Transforms/Utils/PredicateInfo.cpp, CreateSSACopy creates the π-copies.
Which LLVM instruction (opcode name) is the copy?
gsa-gamma-tree · single · 1 pt · 08-ssa-extensionsD branches on p to T and F; T branches on q to T1 and T2; T1 and F jump to M with x1 and x3;
T2 returns. What does Algorithm 16.8.6 give for the φ at M?
- γ(p, γ(q, x1, ⊥), x3), kept as written.
- γ(p, x1, x3)
- γ(q, x1, x3)
- γ(p, x3, x1)
gsa-eta-value · number · 1 pt · 08-ssa-extensionsIn gated SSA, s1 = μ(s0, s2) with s0 = 0 and s2 = s1 + i1, i1 = μ(0, i1 + 1), loop test
c = i1 < n, and at the exit s3 = η(¬c, s1). What is s3 for n = 4?
mssa-phi-blocks · set · 1 pt · 08-ssa-extensionsCFG: entry → A, B; A → C; B → C; C → D, E; D → E. MemoryDefs are in entry (a store), B (a
call) and D (a store); A, C and E only load. At which blocks does Memory SSA (Algorithm
16.8.8, like LLVM: no live-in filter) place MemoryPhis?
mssa-def-chain · sequence · 1 pt · 08-ssa-extensionsIn the print<memoryssa> output of Lesson 16.8 (1 = MemoryDef(liveOnEntry),
2 = MemoryDef(1), 3 = MemoryDef(2), 4 = MemoryPhi({%2,1},{%4,3})), follow the
defining accesses from access 3 to the entry. Write the accesses in order, with
liveOnEntry for M0.
llvm-where-mssa-phis · text · 1 pt · 08-ssa-extensionsMemorySSA::placePHINodes (llvm/lib/Analysis/MemorySSA.cpp) computes the MemoryPhi blocks
with which class?
array-ssa-load · single · 1 pt · 08-ssa-extensionsArray SSA: A[i] := 1, then conditionally A[j] := 2, then at the join x := A[i]. When
can the load be replaced by the constant 1?
- Always: the store A[i] := 1 dominates the load.
- Exactly when i ≠ j is known, because the dφ after A[j] := 2 takes element i from the new store only if j = i.
- Never.
- Only if the branch is not taken.
array-ssa-heap · single · 1 pt · 08-ssa-extensionsIn Fink, Knobe and Sarkar's heap Array SSA (Jikes RVM), what is p.f = v?
- A store H_f[p] := v into the heap array of field f, indexed by the object reference: it uses and defines H_f.
- A definition of a scalar variable p.f.
- A MemoryDef of the whole memory.
- A μ on every field.
hssa-chi-count · number · 1 pt · 08-ssa-extensionsA function has 4 stores through pointers, each of which may point to any of 3 address-taken
variables. How many χ-assignments for real variables does HSSA's step 2 insert (before zero
versioning)?
hssa-zero-version · single · 1 pt · 08-ssa-extensionsWhich versions does HSSA make zero versions?
- Versions with no real occurrence whose value comes from at least one χ, possibly through φs.
- Versions defined in the entry block.
- Every version defined by a φ.
- Versions with exactly one use.