Theory test — Chapter 17¶
61 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 17 # interactive
./course quiz template 17 -o answers/ch17.yaml # or fill in a file ...
./course quiz grade 17 # ... and grade it
kildall-passes · number · 1 pt · 01-constant-propagationKildall's dense constant propagation runs round-robin in reverse postorder (A, B, F, C, D, E)
on the running example before mem2reg (Lesson 17.1 §3):
A: x = 1; i = 0; j = 0 -> B
B: if i < n -> C, F
C: if x < 1 -> D, E
D: x = 2 -> E
E: i = i + 1; j = j + 1 -> B
F: t = i * 4; u = j * 4; r = t - u; s = r + x; ret s
How many passes over the blocks does it make, counting the final pass that changes nothing?
kildall-lattice-height · number · 1 pt · 01-constant-propagationKildall's analysis of the program in kildall-passes keeps an environment for the 7 variables
x, i, j, t, u, r, s at every program point, each in the flat constant lattice
\(L_c = \mathbb{Z}_{32} \cup \{\bot, \top\}\). What is the height of the lattice of environments,
i.e. the most times one OUT set can change?
sparse-cp-values · mapping · 1 pt · 01-constant-propagationRun simple sparse constant propagation (Algorithm 17.1.6: every block executable, phis join
all operands) on:
fn f(n):
entry:
a = add 2, 3
cbr n, l, r
l:
b = mul a, 2
br j
r:
c = add a, 5
br j
j:
p = phi [b, l], [c, r]
q = add p, 1
ret q
Give the final lattice value of each value: a constant, or top for overdefined.
a, b, c, p, qsparse-vs-dense · single · 1 pt · 01-constant-propagationOn a function in SSA form, how do the constants found by Kildall's dense CP and by sparse simple CP compare?
- Sparse CP finds strictly more, because it ignores non-executable edges.
- They find the same constants; sparse CP is just cheaper (one value per SSA name instead of an environment per point).
- Dense CP finds more, because it sees every program point.
- They are incomparable.
sccp-values · mapping · 1 pt · 01-constant-propagationRun SCCP (Algorithm 17.1.8) on the chapter's running example (Lesson 17.1):
while.cond: i.0 = phi [0, entry], [add, if.end]; x.0 = phi [1, entry], [x.1, if.end]
j.0 = phi [0, entry], [add2, if.end]; cmp = lt i.0, n; cbr cmp, while.body, while.end
while.body: cmp1 = ne x.0, 1; cbr cmp1, if.then, if.end
if.then: br if.end
if.end: x.1 = phi [2, if.then], [x.0, while.body]; add = add i.0, 1; add2 = add j.0, 1; br while.cond
while.end: mul = mul i.0, 4; mul3 = mul j.0, 4; sub = sub mul, mul3; add4 = add sub, x.0; ret add4
Give the final values of x.0, cmp1, x.1, i.0 and sub (a constant, or top).
x.0, cmp1, x.1, i.0, subsccp-vs-cpdce · single · 1 pt · 01-constant-propagationWhich statement is Theorem 17.1.12?
- SCCP finds exactly the constants of sparse CP followed by dead-code elimination.
- SCCP finds at least the constants and unreachable blocks that constant propagation and branch folding / DCE find when iterated in any order, and on some programs strictly more.
- Iterating CP and DCE to a fixed point always matches SCCP.
- SCCP is faster than CP + DCE but may find fewer constants.
llvm-where-sccp-lattice · text · 1 pt · 01-constant-propagationIn llvm/lib/Transforms/Utils/SCCPSolver.cpp, what is the class of the per-value lattice
element (the type markOverdefined and isConstant work on)?
lvi-edge-range · mapping · 1 pt · 02-range-and-bit-analysesentry:
%c = icmp ult i8 %x, 10
br i1 %c, label %then, label %else
then:
%y = add i8 %x, 1
With ConstantRange notation \([\ell, u)\) (half-open, unsigned), which range does LVI give
%x at the start of then, and which range does it give %y? Answer with the four bounds.
x_lower, x_upper, y_lower, y_upperllvm-where-lvi-cap · number · 1 pt · 02-range-and-bit-analysesIn llvm/lib/Analysis/LazyValueInfo.cpp, a constant bounds how many (block, value) pairs one
query may process before LVI gives up (and caches overdefined). What is its value?
range-add · mapping · 1 pt · 02-range-and-bit-analysesOver i8, compute \([0, 10) +^\sharp [5, 8)\) with Algorithm 17.2.3 (ConstantRange addition).
Give the result as its lower and upper bound.
lower, upperrange-union-loss · mapping · 1 pt · 02-range-and-bit-analysesOver i8, a phi joins the ranges \([0, 2)\) and \([10, 12)\). ConstantRange::unionWith returns
one wrapped interval. Which one (lower and upper bound), and how many values does it contain?
lower, upper, sizeknown-bits-and · mapping · 1 pt · 02-range-and-bit-analyses%a is an i8 with no known bits. %b = or i8 %a, 1 and %c = and i8 %b, 15. Give the
known-zero and known-one masks of %c as 8-digit binary strings (bit 7 first).
zero, oneknown-bits-vs-range · single · 1 pt · 02-range-and-bit-analysesWhich fact can KnownBits express exactly but a single ConstantRange cannot?
- x is between 0 and 100.
- x is a multiple of 16 (its low four bits are zero), with any high bits.
- x is not zero.
- x is negative.
demanded-bits-shl · mapping · 1 pt · 02-range-and-bit-analyses%v = shl i32 %h, 8
%r = and i32 %v, 65535
ret i32 %r
Give the demanded bits of %v and of %h as 8-digit hexadecimal masks (e.g. 0x000000ff).
v, hbdce-safety · single · 1 pt · 02-range-and-bit-analysesBDCE replaces a value none of whose bits are demanded by 0. Why must it also drop nsw/nuw/exact flags on some users?
- Because the flags are part of the demanded-bits lattice.
- Because a changed operand, even in undemanded bits, can make the flag's promise false, and a violated flag yields poison, which can spread to demanded bits.
- Because LLVM's verifier rejects flags on instructions with constant operands.
- It does not need to; flags never matter for BDCE.
marksweep-dead · set · 1 pt · 03-dead-code-eliminationRoots are print and ret; in classic mark–sweep DCE (Algorithm 17.3.2) every branch is a
root too. Which instruction values are deleted?
fn g(n):
entry:
a = add n, 1
d = mul n, 3
c = lt n, 10
cbr c, t, e
t:
u = add a, 2
br j
e:
w = sub a, 1
br j
j:
p = phi [u, t], [w, e]
print a
ret a
marksweep-cycles · single · 1 pt · 03-dead-code-eliminationA loop contains s = phi [0, entry], [s1, latch] and s1 = add s, 1, and nothing else uses s or s1. Which DCE removes them?
- Only worklist DCE of trivially dead instructions (use count 0), as in Ch 13.
- Mark–sweep DCE (and ADCE), because the marking starts from roots and never reaches the cycle; worklist DCE cannot, because each has a use.
- Neither: removing a phi changes the loop.
- Only ADCE, because it needs control dependence.
adce-dead · set · 1 pt · 03-dead-code-eliminationRun aggressive DCE (Algorithm 17.3.5, roots print and ret, branches live only through
control dependence) on the function g of question marksweep-dead. Which instruction values
are deleted?
adce-retarget · text · 1 pt · 03-dead-code-eliminationIn the ADCE result for g (question adce-dead), the dead cbr c, t, e in entry becomes an unconditional branch. To which block?
llvm-where-adce-loops · single · 1 pt · 03-dead-code-eliminationIn llvm/lib/Transforms/Scalar/ADCE.cpp, which option controls whether loops may be removed (back-edge branches are not roots), and what is its default?
adce-remove-control-flow, default falseadce-remove-loops, default falseadce-remove-loops, default trueadce-mustprogress, default true
dse-rule · set · 1 pt · 03-dead-code-elimination%a is an alloca that never escapes and is never loaded; %p and %q may alias.
store i32 1, ptr %a ; s1
store i32 2, ptr %p ; s2
%v = load i32, ptr %q
store i32 3, ptr %p ; s3
store i32 4, ptr %p ; s4
ret i32 %v
Which stores does Algorithm 17.3.7 delete?
dse-interplay · single · 1 pt · 03-dead-code-eliminationIn @inter (Lesson 17.3 §3), block a only stores into a local that is never loaded. Which pass order removes the whole diamond?
- ADCE, then DSE
- DSE, then ADCE
- Either order
- Neither: stores are always roots
earlycse-generations · set · 1 pt · 04-dominator-scoped-redundancyOne block, processed by EarlyCSE (Algorithm 17.4.4); %p and %q may alias:
%l1 = load i32, ptr %p
%l2 = load i32, ptr %p
store i32 7, ptr %q
%l3 = load i32, ptr %p
%l4 = load i32, ptr %q
%l5 = load i32, ptr %p
Which loads are replaced by an earlier value?
llvm-where-earlycse-generation · text · 1 pt · 04-dominator-scoped-redundancyIn llvm/lib/Transforms/Scalar/EarlyCSE.cpp, what is the name of the counter that is incremented when a block has more than one predecessor or an instruction may write memory?
dvnt-classes · set · 1 pt · 04-dominator-scoped-redundancyRun DVNT (Algorithm 17.4.5, the chapter's positional congruence, no commutativity) on:
fn h(a, b):
entry:
x = add a, b
c = lt a, b
cbr c, l, r
l:
y = add a, b
z = mul y, 2
br j
r:
w = add a, b
v = mul w, 2
br j
j:
p = phi [z, l], [v, r]
q = mul x, 2
s = add p, q
ret s
Which values get the same value number as x (not counting x itself)?
dvnt-siblings · single · 1 pt · 04-dominator-scoped-redundancyIn h (question dvnt-classes), why does DVNT not give z, v and q one value number?
- Because
mulis not a candidate. - Because the scoped hash table only holds expressions of dominators:
zlives in l's scope, which is gone when r and j are visited. - Because
yandwhave different value numbers. - Because phis block value numbering.
gvn-equality · single · 1 pt · 04-dominator-scoped-redundancyWhat does LLVM GVN's propagateEquality do after br i1 (icmp eq %a, %b), label %t, label %f?
- It replaces %b by %a everywhere in the function.
- In the blocks dominated by the edge into %t (when %t has that edge as its only predecessor), it treats %b as %a, so expressions over %b find leaders computed from %a.
- It deletes the branch.
- It adds a phi of %a and %b at %t.
gvn-leaders · single · 1 pt · 04-dominator-scoped-redundancyLLVM's GVN numbers instructions globally in reverse postorder. Which instructions may replace an instruction I with value number n?
- Any instruction with number n.
- Only a leader of n (an instruction with number n in its leader table) that dominates I.
- Only an instruction with number n in the same block.
- Only a phi.
awz-rounds · number · 1 pt · 05-partition-and-optimistic-gvnRun AWZ signature refinement (Algorithm 17.5.3) on h from question dvnt-classes. How many
rounds are there, counting round 0 (group by label) and the final round that splits nothing?
awz-classes · set · 1 pt · 05-partition-and-optimistic-gvnIn the AWZ result for h (question awz-rounds), which values are in the class of z?
rpo-vn-iterations · number · 1 pt · 05-partition-and-optimistic-gvnSimpson's optimistic RPO value numbering (Algorithm 17.5.6, as computed by scalaropt.rpo_vn)
on the running example run: how many iterations, counting the last one that changes nothing?
herbrand-vs-congruence · single · 1 pt · 05-partition-and-optimistic-gvnz = phi(a+b, c+d) and w = phi(a, c) + phi(b, d) at the same join. Which is true?
- They are congruent and Herbrand-equivalent.
- They are Herbrand-equivalent but not congruent: z is a phi and w is an add, so their labels differ.
- They are congruent but not Herbrand-equivalent.
- Neither.
newgvn-unreachable · single · 1 pt · 05-partition-and-optimistic-gvnWhat does NewGVN add to optimistic value numbering that AWZ partitioning lacks?
- Dominator scoping.
- Optimistic unreachability (as in SCCP), constant folding, predicates from branches and memory via MemorySSA, all in one sparse fixed point.
- Lazy code motion.
- Nothing; it is AWZ with hashing.
llvm-where-newgvn · text · 1 pt · 05-partition-and-optimistic-gvnIn llvm/lib/Transforms/Scalar/NewGVN.cpp, which member function processes the worklist of touched instructions and blocks until it is empty?
gvn-hoist-busy · single · 1 pt · 05-partition-and-optimistic-gvnGVN-hoist moves %x = mul %a, %b (block l) and %y = mul %a, %b (block r) into their common dominator entry. Which condition makes this safe without adding computations?
- The value is available at the end of entry.
- The value is very busy (anticipated) at the end of entry: every path from there computes it before its operands change, and the operands are available there.
- l and r post-dominate entry.
- The multiplications have nsw.
gvn-sink-phi · single · 1 pt · 05-partition-and-optimistic-gvnBoth predecessors of block j end with add %a, C and store of the sum to %p, with C = 1 in l and C = 2 in r. What does GVN-sink produce in j?
- Nothing: the instructions differ.
- One add and one store in j, with a phi selecting the constant:
phi [1, %l], [2, %r]. - Two adds in j.
- A select on the branch condition.
mr-critical-edge · single · 1 pt · 06-partial-redundancy-eliminationWhy can Morel–Renvoise miss a partial redundancy whose only good insertion point is a critical edge?
- Because it does not compute anticipability.
- Because it inserts only at block ends: the source block of the critical edge has another successor, so inserting there would add an evaluation on a path that had none.
- Because it cannot handle loops.
- Because it works on SSA.
mr-bidirectional · single · 1 pt · 06-partial-redundancy-eliminationWhat makes Morel–Renvoise's system slow to solve compared with lazy code motion?
- It uses more bits per expression.
- PPIN depends on successors and PPOUT on predecessors at once (bidirectional), so round-robin passes are not bounded by the loop connectedness as for LCM's four unidirectional problems.
- It needs SSA.
- It is solved per expression.
lcm-insert · mapping · 1 pt · 06-partial-redundancy-eliminationlabs/ch17-lcm/inputs/running.tac (blocks B0–B5; B2 computes t = mul a, b, B3 changes a,
B4 computes u = mul a, b):
B0: a = 3; b = 5; n = 4; x = mul a, b; i = 0; s = 20
B1: c = lt i, n; ifz c goto B5
B2: t = mul a, b; d = lt t, s; ifz d goto B4
B3: s = add s, t; a = sub t, 1
B4: u = mul a, b; i = add i, 1; goto B1
B5: return s
Lazy code motion inserts mul a, b on exactly one edge. Give its source and target block.
source, targetlcm-delete · set · 1 pt · 06-partial-redundancy-eliminationIn running.tac (question lcm-insert), which blocks have mul a, b in DELETE?
lcm-optimal · number · 1 pt · 06-partial-redundancy-eliminationThe original running.tac evaluates candidate expressions 24 times (the loop runs 4 times).
How many evaluations does the program perform after lazy code motion (ch17-lcm --transform,
checked by lcm_oracle.py check)?
ssapre-steps · sequence · 1 pt · 06-partial-redundancy-eliminationPut SSAPRE's six steps (Algorithm 17.6.8) in order:
Finalize, Rename, CodeMotion, PhiInsertion, WillBeAvail, DownSafety.
ssapre-phi · single · 1 pt · 06-partial-redundancy-eliminationIn SSAPRE, what is a Φ (capital phi) node?
- An ordinary SSA phi of a variable.
- A phi for a hypothetical temporary holding the expression's value, placed at the iterated dominance frontier of the occurrences, so that redundancy becomes a question of versions.
- A marker for a critical edge.
- A deleted occurrence.
gvnpre-phitrans · text · 1 pt · 06-partial-redundancy-eliminationWhat is the name of the GVN-PRE operation that rewrites an anticipated expression at the start of block s into the corresponding expression at the end of predecessor b, by replacing operands defined by s's phis with their incoming values from b?
gvnpre-vs-lexical · single · 1 pt · 06-partial-redundancy-eliminationWhich redundancy does GVN-PRE remove that lexical PRE (LCM) cannot?
a + bcomputed twice in one block.- An expression whose operands have different names on different paths but the same values, e.g.
x_3 * 2after a join wherex_3 = phi(x_1, x_2)andx_1 * 2was computed on one path. - Loads across stores.
- Loop-invariant code in a do-while loop.
load-pre-safety · single · 1 pt · 06-partial-redundancy-eliminationLLVM GVN's load PRE inserts a load of %p at the end of a predecessor where it is not available. What makes that insertion safe?
%pis an argument.- The load is anticipated on every path from the insertion point (or
%pis known dereferenceable there), so the inserted load cannot trap on a path that did not load%pbefore. - The load is volatile.
- The predecessor has one successor.
llvm-where-load-pre · text · 1 pt · 06-partial-redundancy-eliminationIn llvm/lib/Transforms/Scalar/GVN.cpp, which GVNPass member function decides whether a partially redundant load can be made fully redundant by inserting loads in predecessors?
simplifycfg-rounds · number · 1 pt · 07-cfg-simplificationAlgorithm 17.7.3 (R1 constant branches, R2 unreachable blocks, R3 block merging, repeated until
a round changes nothing) on:
entry: br i1 true, label %t, label %f
t: %x = add i32 %a, 1; br label %mid
mid: %y = mul i32 %x, 3; br label %join
f: %z = sub i32 %a, 1; br label %join
island: br label %join
join: %p = phi i32 [ %y, %mid ], [ %z, %f ], [ 0, %island ]; ret i32 %p
How many rounds run, counting the last one that changes nothing?
simplifycfg-merge · single · 1 pt · 07-cfg-simplificationWhen may block B be merged into block P (rule R3)?
- When B has one successor.
- When P is B's only predecessor, P ends in an unconditional branch to B, B is not the entry and B ≠ P.
- When P dominates B.
- When B is empty.
lookup-table-size · number · 1 pt · 07-cfg-simplificationA switch on %k has cases 3, 4, 6 and 9, each returning a constant, and a default returning 0.
Algorithm 17.7.5 converts it to a lookup table. How many entries does the table have?
lookup-range-check · single · 1 pt · 07-cfg-simplificationWhy does one unsigned comparison idx <u size with idx = x − c1 suffice as the range check c1 ≤ x ≤ ck?
- Because x is always non-negative.
- Because subtracting c1 modulo 2^w maps exactly the values c1…ck to 0…size−1, and every other value to an unsigned number ≥ size.
- Because LLVM adds a second check.
- Because the default case is unreachable.
jt-known-edge · mapping · 1 pt · 07-cfg-simplificationclassify after mem2reg (Lesson 17.7 §3):
entry: %cmp = icmp slt i32 %x, 0; br i1 %cmp, label %if.then, label %if.else
if.then: br label %if.end
if.else: br label %if.end
if.end: %neg.0 = phi i32 [ 1, %if.then ], [ 0, %if.else ]
%mul = mul nsw i32 %x, 2; store i32 %mul, ptr %out
%tobool = icmp ne i32 %neg.0, 0; br i1 %tobool, label %if.then1, label %if.end2
For each predecessor of if.end, to which successor does jump threading send it?
if.then, if.elsellvm-where-jt-threshold · number · 1 pt · 07-cfg-simplificationIn llvm/lib/Transforms/Scalar/JumpThreading.cpp, the option jump-threading-threshold limits the size of a block that may be duplicated. What is its default value?
phase-order-run · set · 1 pt · 08-phase-ordering-and-equality-saturationWhich of these opt 23.1.2 pipelines turn the running example run (after mem2reg) into
ret i32 1? Answer with the letters.
- (a)
sccp,gvn,instcombine - (b)
gvn,sccp,instcombine - (c)
sccp,gvn,instcombine,sccp,gvn,instcombine - (d)
sccp,newgvn,instcombine
phase-order-indvars · text · 1 pt · 08-phase-ordering-and-equality-saturationIn LLVM's default<O2>, GVN is the first pass that makes run return 1, thanks to a loop pass that ran shortly before it and rewrote the exit values of i and j to the same expression smax(n, 0). Which pass (its class name)?
combined-precision · single · 1 pt · 08-phase-ordering-and-equality-saturationWhat does Theorem 17.8.6 (Click–Cooper) state?
- Combined analyses are faster than separate ones.
- The least fixed point of the combined system is at least as precise as the result of any finite sequence of separate runs, each given the other analysis's latest facts, provided the transfer functions are monotone in both arguments.
- Any phase ordering reaches the combined fixed point if repeated long enough.
- Combined analyses are always strictly more precise.
combined-mutual · set · 1 pt · 08-phase-ordering-and-equality-saturationmutual (Lesson 17.8 §3):
int i = 0, j = 0;
for (int k = 0; k < n; k++) {
if (i != j) i = i + 2; else i = i + 1;
j = j + 1;
}
return i - j;
Which of these prove return 0? Answer with the letters.
- (a) SCCP alone
- (b) AWZ value numbering alone
- (c) SCCP then AWZ then SCCP, each given the other's results
- (d) the combined analysis (SCCP + AWZ as one fixed point)
- (e) LLVM
newgvn - (f) GCC 13
-O2(FRE with optimistic RPO value numbering)
eqsat-running-classes · mapping · 1 pt · 08-phase-ordering-and-equality-saturationEquality saturation (Algorithm 17.8.4) of (+ (- (* i 4) (* j 4)) x) with the rules
x → 1, j → i, (- ?a ?a) → 0, (+ 0 ?a) → ?a, (+ ?a ?b) → (+ ?b ?a). Give the number of
e-classes and e-nodes at the end, and the number of rounds (counting the last, which changes
nothing).
classes, nodes, roundseqsat-closure · single · 1 pt · 08-phase-ordering-and-equality-saturationWhy does saturation make the order of rewrites irrelevant (Theorem 17.8.9)?
- Because the rules are confluent.
- Because at saturation every class is closed under every rule, and replacing a subterm by an equal one in the same class keeps the whole term in its class, so every term reachable by any rewrite sequence is represented in the root class.
- Because extraction tries all orders.
- Because e-graphs are acyclic.
aegraph-licm · single · 1 pt · 08-phase-ordering-and-equality-saturationIn Cranelift's %sum example, imul_imm v1, 8 inside the loop becomes ishl v1, 3 in block0. Which part of the aegraph pipeline moves it out of the loop?
- A separate LICM pass after the e-graph pass.
- Elaboration: pure values live outside the CFG, and elaboration places each needed value at the shallowest loop level where its operands are available.
- The ISLE rewrite rule for imul.
- The register allocator.
cl-where-eclass-limit · number · 1 pt · 08-phase-ordering-and-equality-saturationIn cranelift/codegen/src/egraph.rs (wasmtime v37.0.2), the constant ECLASS_ENODE_LIMIT bounds the number of e-nodes in one e-class. What is its value?