Skip to content

Theory test — Chapter 13

55 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 13                                   # interactive
./course quiz template 13 -o answers/ch13.yaml  # or fill in a file ...
./course quiz grade 13                             # ... and grade it
Question 1 scope-ebb · set · 1 pt · 01-scopes-and-constant-folding

CFG with entry A and edges A→B, A→C, B→D, C→D, C→E, D→F, E→F. Which blocks form the
extended basic block rooted at A (Definition 13.1.1)?

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 2 scope-classify · mapping · 1 pt · 01-scopes-and-constant-folding

CFG: A→B, A→C, B→D, C→D. The expression a + b (operands defined in the entry block A) is
recomputed at four places. For each, give the smallest scope (local, superlocal, regional,
global) in which it is already available and can be replaced:

  • r1: computed twice inside block C;
  • r2: computed in A and again in B;
  • r3: computed in A and again in D;
  • r4: computed in B and in C (not in A) and again in D.
Keys: r1, r2, r3, r4
Answer format: one value per key
Question 3 fold-values · mapping · 1 pt · 01-scopes-and-constant-folding

What does pebble-constfold (exercise E1) turn each instruction into? Answer with the folded
constant (signed decimal, true/false for i1), poison, or unchanged.

  • a: add nsw i8 100, 100
  • b: shl i8 1, 8
  • c: sdiv exact i8 -7, 2
  • d: ashr i8 -7, 1
  • e: udiv i8 7, 0
  • f: icmp samesign ult i8 -1, 1
  • g: sdiv i8 -7, 2
Keys: a, b, c, d, e, f, g
Answer format: one value per key
Question 4 fold-fp · single · 1 pt · 01-scopes-and-constant-folding

A front end folds (1.0 + 1e16) - 1e16 in IEEE double with round-to-nearest-even.
What is the correctly folded result, and why must a folder not reassociate it?

  1. 1.0, because addition is associative
  2. 0.0, because 1 + 1e16 rounds to 1e16 (a tie between neighbours 2 apart, broken to the even significand); reassociating would give 1.0
  3. 2.0, because the spacing of doubles near 1e16 is 2
  4. It cannot be folded: the result depends on the host's rounding mode
Answer format: one letter
Question 5 peephole-trace · sequence · 1 pt · 02-peephole-engines

Run pebble-peephole (rules R1–R17 of exercise E2, FIFO worklist, Algorithm 13.2.4) on

define i8 @f(i8 %x) {
  %a = sub nsw i8 %x, 3
  %b = add nsw i8 %a, 5
  %c = mul nsw i8 4, %b
  %d = or i8 %c, 0
  ret i8 %d
}

Give the names of the rules that fire, in order (e.g. sub-const add-add-const …).

Answer format: items in order, e.g. A B C
Question 6 instsimplify-contract · single · 1 pt · 02-peephole-engines

Which transformation may InstSimplify perform, but not only InstCombine (Definition 13.2.3)?

  1. mul i32 %x, 8 → shl i32 %x, 3
  2. sub i32 %x, %x → 0
  3. add i32 %x, %x → shl i32 %x, 1
  4. udiv i32 %x, 7 → a multiply-high and a shift
Answer format: one letter
Question 7 pattern-match-bind · mapping · 1 pt · 02-peephole-engines

With Value *X, *Y; const APInt *C;, the pattern
match(I, m_Sub(m_Value(X), m_Shl(m_Value(Y), m_APInt(C)))) is applied to %r in

%s = shl i32 %q, 4
%r = sub i32 %p, %s

What are X, Y and C after a successful match? (Give value names without %, and C as a number.)

Keys: X, Y, C
Answer format: one value per key
Question 8 find-patternmatch · text · 1 pt · 02-peephole-engines

In LLVM 23's llvm/include/llvm/IR/PatternMatch.h, which matcher do you use for "the same value
that an earlier m_Value(X) in this pattern bound", as in X + X? (Give the function name.)

Answer format: a short answer
Question 9 dsl-decision-tree · sequence · 1 pt · 02-peephole-engines

Use the decision tree built in Lesson 13.2 §3 for the four add rules R1, R2, R9, R11
(nodes n0–n6; n0 tests the root, n1 position 1, n2/n3/n4 position 2, n5/n6 position 1.2).
Which nodes does the input add (add y, 5), 3 visit before reaching a leaf? (e.g. n0 n1 …)

Answer format: items in order, e.g. A B C
Question 10 matchpd-fp · single · 1 pt · 02-peephole-engines

GCC 15's match.pd rule for (minus @0 @0) folds x - x to 0 for int at -O2, but for
double only with options such as -ffinite-math-only. Why?

  1. Floating-point subtraction is not commutative
  2. For x = NaN or x = ±∞, x − x is NaN, not 0 (and under directed rounding the zero can be −0.0)
  3. genmatch cannot generate code for floating-point types
  4. x − x overflows for large doubles
Answer format: one letter
Question 11 superopt-shortest · number · 1 pt · 03-superoptimization

Enumerative superoptimization (Algorithm 13.3.3) over i4 with instruction set
\(I = \{\mathsf{add}, \mathsf{shl}\}\) and constant set \(K = \{1\}\) (operands: x, 1, earlier
results). What is the length of a shortest program computing \(5x \bmod 16\)?

Answer format: a number
Question 12 gso-signum · single · 1 pt · 03-superoptimization

The GNU superoptimizer finds Massalin's four-instruction branch-free signum
(addl d0,d0; subxl d1,d1; negxl d0; addxl d1,d1 on the 68020). What does it rely on to
accept a candidate, according to its README and Lesson 13.3?

  1. An SMT proof of equivalence for all 32-bit inputs
  2. Simulation on a set of test values only, so a result might (rarely) be wrong
  3. Exhaustive enumeration of all 2^32 inputs
  4. A Coq proof generated for each sequence
Answer format: one letter
Question 13 stoke-accept · number · 1 pt · 03-superoptimization

STOKE (Algorithm 13.3.5) with \(\beta = 0.5\) proposes a rewrite whose cost is 3 higher than the
current one (\(\Delta = +3\)). With what probability is it accepted? (Two decimals.)

Answer format: a number (±0.01)
Question 14 stoke-cost · number · 1 pt · 03-superoptimization

STOKE's correctness term \(\mathrm{eq}(R; T)\) is the total number of differing output bits over
the tests (Algorithm 13.3.5). Target: \(s(x) = 3x \bmod 16\) on i4, tests \(T = \{1, 3, 5\}\).
Candidate \(R\): shl x, 1. What is \(\mathrm{eq}(R; T)\)?

Answer format: a number
Question 15 cegis-iterations · number · 1 pt · 03-superoptimization

Run CEGIS (Algorithm 13.3.6) as in Lesson 13.3 §3, but for udiv i8 %x, 5: template
\(t_{C,s}(x) = \mathrm{trunc}((\mathrm{zext}_{16}(x) \cdot C) \gg s)\) with \(C < 2^9\),
\(8 \le s \le 16\); Synth returns the lexicographically smallest \((s, C)\) consistent with \(E\),
Verify the smallest counterexample; \(E\) starts as \(\{0\}\). How many times is Synth called?

Answer format: a number
Question 16 souper-magic · mapping · 1 pt · 03-superoptimization

Souper's test infers udiv i16 %x, 515 as trunc((zext32(x) * 65155) >> 25). What does the same
method (equivalently, the smallest-shift magic number of Algorithm 13.7.7) give for
udiv i16 %x, 1000? Give the multiplier C and the total shift s.

Keys: C, s
Answer format: one value per key
Question 17 generalize-rule · single · 1 pt · 03-superoptimization

A superoptimizer found the concrete i8 rule (x >>u 2) << 2 → x & -4. Which generalization,
with \(C\) a symbolic shift amount \(0 \le C < N\), is valid for every \(C\) and width \(N\)
(Algorithm 13.3.8)?

  1. (x >>u C) << C → x & ((1 << C) - 1)
  2. (x >>u C) << C → x & (-1 << C)
  3. (x >>u C) << C → x & -C
  4. (x >>u C) << C → x & ~C
Answer format: one letter
Question 18 infer-precondition · single · 1 pt · 03-superoptimization

For the generalized rule icmp eq (and x, C1), C2 → false, which precondition is the
weakest precondition WP (Definition 13.3.7): sound, and true for every \((C1, C2)\) where the
rule is valid?

  1. C2 != 0
  2. C1 != C2
  3. (C2 & ~C1) != 0
  4. C2 >u C1
Answer format: one letter
Question 19 canon-form · text · 1 pt · 04-canonicalization-and-rewriting

What does pebble-peephole (R1–R17) leave of %r = icmp uge i8 7, %x? Write the resulting
instruction's right-hand side as icmp <pred> i8 %x, <constant>.

Answer format: a short answer
Question 20 find-getcomplexity · mapping · 1 pt · 04-canonicalization-and-rewriting

In LLVM 23, InstCombiner::getComplexity (llvm/include/llvm/Transforms/InstCombine/InstCombiner.h)
ranks operands so that commutative instructions put the more complex one first. What does it
return for each value?

  • a: poison
  • b: i32 5
  • c: the argument %x
  • d: %n = sub i32 0, %x
Keys: a, b, c, d
Answer format: one value per key
Question 21 newman · single · 1 pt · 04-canonicalization-and-rewriting

A rule set is terminating, and every critical pair is joinable. What can you conclude?

  1. Nothing about confluence: local confluence never implies confluence
  2. It is confluent, so every input has a unique normal form (critical-pair lemma + Newman's lemma)
  3. It is confluent only if it also has no overlapping rules
  4. It terminates in polynomial time
Answer format: one letter
Question 22 measure-step · mapping · 1 pt · 04-canonicalization-and-rewriting

The termination measure of Theorem 13.4.9 is \(\mu = (I, S, A, M)\). For

%a = sub i8 %x, 3
%b = add i8 %a, 5
%c = mul i8 4, %b
ret i8 %c

\(\mu = (4, 2, 0, 0)\). Give \(I, S, A, M\) after R8 (sub-const) rewrites %a to add i8 %x, -3.

Keys: I, S, A, M
Answer format: one value per key
Question 23 critical-pair · single · 1 pt · 04-canonicalization-and-rewriting

R2 (x op 0 → x) and R9 (add (add x, C1), C2 → add x, C1 + C2) overlap on
%r = add i32 %t, 0 with %t = add nsw i32 %y, 5 (the outer add has no flags). What are the two
results, and is the critical pair joinable?

  1. Both give add nsw i32 %y, 5: joinable
  2. R2 gives %t (add nsw %y, 5), R9 gives add i32 %y, 5 without nsw: not joinable, although both refine the source
  3. R2 gives %y, R9 gives add %y, 5: not joinable, and R2's result is wrong
  4. They do not overlap, because R9 needs C2 ≠ 0
Answer format: one letter
Question 24 lvn-trace · mapping · 1 pt · 05-value-numbering-and-dags

Run local value numbering with the extensions of Algorithm 13.5.3 (commutativity, identities,
folding; i8) on this block (inputs a, b, c):

t1 = mul a, b
t2 = add c, 0
t3 = mul b, a
t4 = sub t1, t3
t5 = add t2, t4
t6 = add 3, 4
t7 = mul t6, a
t8 = add c, t4

For t2–t8, give what each is replaced by (a name or a constant), or kept.

Keys: t2, t3, t4, t5, t6, t7, t8
Answer format: one value per key
Question 25 lvn-flags · single · 1 pt · 05-value-numbering-and-dags

A block contains %a = add nsw i32 %x, %y and later %b = add i32 %x, %y. LVN replaces %b by
%a. What else must it do?

  1. Nothing: flags are not part of the key
  2. Drop nsw from %a (keep only the flags both instructions have)
  3. Add nsw to every user of %b
  4. Refuse the replacement: instructions with different flags are never equal
Answer format: one letter
Question 26 lvn-memory · mapping · 1 pt · 05-value-numbering-and-dags

LVN with memory versions (Algorithm 13.5.5, no alias analysis), block:

l1 = load p
t1 = add l1, a
store t1, q
l2 = load p
l3 = load q
l4 = load p
x = call g(a)      ; memory(none)
y = call g(a)      ; memory(none)
call f             ; may write memory
l5 = load q

For l2, l3, l4, y, l5 give the value each is replaced by, or kept.

Keys: l2, l3, l4, y, l5
Answer format: one value per key
Question 27 find-earlycse-generation · text · 1 pt · 05-value-numbering-and-dags

In LLVM 23's llvm/lib/Transforms/Scalar/EarlyCSE.cpp, what is the name of the unsigned member
of the EarlyCSE class that plays the role of Algorithm 13.5.5's memory version?

Answer format: a short answer
Question 28 dag-nodes · number · 1 pt · 05-value-numbering-and-dags

Build the DAG (Algorithm 13.5.7) of this non-SSA block:

x = a * b
y = b * a
a = x + c
z = a * b
w = y + c

How many nodes does it have in total (leaves and interior nodes)?

Answer format: a number
Question 29 find-csemap · text · 1 pt · 05-value-numbering-and-dags

In LLVM 23's llvm/include/llvm/CodeGen/SelectionDAG.h, what is the name of the
FoldingSet<SDNode> member through which SelectionDAG::getNode finds an existing identical
node instead of creating a new one?

Answer format: a short answer
Question 30 dce-order · sequence · 1 pt · 05-value-numbering-and-dags

Run Algorithm 13.5.10 with \(W\) a stack, initially the trivially dead instructions pushed in
program order, and operands pushed in operand order:

%a = add i32 %x, 1
%b = mul i32 %a, 2
%c = sub i32 %b, %a
%d = xor i32 %x, 5
%e = add i32 %x, 7
ret i32 %e

In which order are instructions deleted?

Answer format: items in order, e.g. A B C
Question 31 dce-cycle · single · 1 pt · 05-value-numbering-and-dags

In a loop, %s = phi i32 [0, %entry], [%s.next, %loop] and %s.next = add i32 %s, 1 have no other
users. What does worklist DCE (pebble-dce, LLVM dce) do with them?

  1. Deletes both: they compute nothing observable
  2. Keeps both: each has a use (the other), so neither is trivially dead; removing dead cycles needs aggressive (mark-and-sweep) DCE
  3. Deletes the add and keeps the phi
  4. Reports an error: SSA values must not form cycles
Answer format: one letter
Question 32 ranks-map · mapping · 1 pt · 06-reassociation

Ranks of Definition 13.6.2 (blocks numbered in reverse postorder from 1; successors in listed
order) for

define i32 @f(i32 %a, i32 %b, i32 %n, ptr %p) {
entry:
  br label %loop
loop:
  %i = phi i32 [ 0, %entry ], [ %i1, %body ]
  %s = phi i32 [ 0, %entry ], [ %s1, %body ]
  %c = icmp slt i32 %i, %n
  br i1 %c, label %body, label %exit
body:
  %v = load i32, ptr %p
  %t1 = add i32 %v, 5
  %t2 = add i32 %t1, %i
  %t3 = add i32 %t2, %a
  %t4 = add i32 %t3, 3
  %s1 = add i32 %t4, %b
  %i1 = add i32 %i, 1
  br label %loop
exit:
  ret i32 %s
}

Give the ranks of a, i, v, t2, i1.

Keys: a, i, v, t2, i1
Answer format: one value per key
Question 33 reassoc-order · sequence · 1 pt · 06-reassociation

For the same function (ranks-map), pebble-reassociate rebuilds the tree rooted at %s1
(Algorithm 13.6.3). List the operands of the new left-deep chain from the innermost add
outwards, with the folded constant last (e.g. x y 3).

Answer format: items in order, e.g. A B C
Question 34 tree-height · number · 1 pt · 06-reassociation

What is the minimal height of a binary tree of adds over 11 leaves that are all available at
time 0 (Corollary 13.6.11)?

Answer format: a number
Question 35 thr-greedy · number · 1 pt · 06-reassociation

Algorithm 13.6.5 (repeatedly combine the two earliest-ready values) on six leaves with arrival
times (0, 0, 0, 0, 0, 3). What is the completion time of the resulting tree?

Answer format: a number
Question 36 naf-trace · sequence · 1 pt · 07-strength-reduction-and-division

Compute NAF(119) with Algorithm 13.7.2. Give the digits least significant first
(e.g. 1 0 -1 …).

Answer format: items in order, e.g. A B C
Question 37 mul-lea · single · 1 pt · 07-strength-reduction-and-division

On x86-64, clang-23 -O2 compiles x * 45 into two lea instructions. Which decomposition is
that?

  1. 45 = 2⁶ − 2⁴ − 2² + 1 (the NAF): three leas would be needed
  2. 45 = 9 × 5: lea (x, x, 8) computes 9x, then lea (y, y, 4) computes 5y
  3. 45 = 32 + 13: a shift plus one lea
  4. 45 = 48 − 3: one lea and one sub
Answer format: one letter
Question 38 magic-7 · mapping · 1 pt · 07-strength-reduction-and-division

Unsigned udiv i8 %x, 7 by Algorithm 13.7.7 (smallest ℓ by the exact criterion). Give ℓ, the
magic m, and whether the add fix-up is needed (yes/no).

Keys: l, m, add
Answer format: one value per key
Question 39 magic-criterion · mapping · 1 pt · 07-strength-reduction-and-division

For udiv i8 %x, 98, give the smallest post-shift ℓ allowed by Granlund–Montgomery's
sufficient condition \(e \le 2^\ell\) (Theorem 13.7.4) and by the exact criterion
\(e \cdot n_c < 2^{N+\ell}\) (Theorem 13.7.6).

Keys: gm, exact
Answer format: one value per key
Question 40 find-divconst · text · 1 pt · 07-strength-reduction-and-division

In LLVM 23's llvm/include/llvm/Support/DivisionByConstantInfo.h, which bool field of
UnsignedDivisionByConstantInfo says that the magic number needs N + 1 bits, so the code uses
the add fix-up?

Answer format: a short answer
Question 41 refine-closure · set · 1 pt · 08-refinement-ub-and-fast-math

Source: %f = freeze i2 %x; %r = and i2 %f, 1; ret i2 %r. On the input %x = poison, which
outcomes may a refining target produce? Choose among 0, 1, 2, 3, poison, UB.

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 42 refine-direction · single · 1 pt · 08-refinement-ub-and-fast-math

Which rewrite is a refinement (source ⇒ target) on i8?

  1. add i8 %x, 1 ⇒ add nsw i8 %x, 1
  2. add nsw i8 %x, 1 ⇒ add i8 %x, 1
  3. udiv i8 %x, %y ⇒ udiv i8 %x, 1 when you do not know y
  4. %r = add i8 %x, %y ⇒ %r = poison
Answer format: one letter
Question 43 freeze-dup · single · 1 pt · 08-refinement-ub-and-fast-math

Source A: %f = freeze i4 %x; %g = freeze i4 %x; %r = sub i4 %f, %g.
Source B: %f = freeze i4 %x; %r = sub i4 %f, %f. Which of these rewrites are valid?

  1. A ⇒ ret 0 is valid, and B ⇒ A is valid
  2. A ⇒ ret 0 is valid, but B ⇒ A is invalid
  3. A ⇒ ret 0 is invalid, but B ⇒ A is valid
  4. Both are invalid
Answer format: one letter
Question 44 select-branch · single · 1 pt · 08-refinement-ub-and-fast-math

A pass turns %r = select i1 %c, i32 %x, i32 %y into br i1 %c, … with a phi. What happens for
%c = poison, and what repairs it?

  1. Nothing changes: both give poison
  2. The select gives poison but the branch on poison is immediate UB; branching on freeze %c repairs it
  3. Both are UB, so the rewrite is valid
  4. The branch picks the true side deterministically; no repair is needed
Answer format: one letter
Question 45 flags-r9 · mapping · 1 pt · 08-refinement-ub-and-fast-math

R9 (add-add-const) on i8, where both adds carry nsw nuw. Which flags does the result keep?
(Give a set per case; [] for none.)

  • A: (x + 100) + 27
  • B: (x + 100) + 28
  • C: (x + -1) + -1
Keys: A, B, C
Answer format: one value per key (a set: {x, y})
Question 46 flags-mul-min · single · 1 pt · 08-refinement-ub-and-fast-math

R10 (mul-pow2) on %r = mul nuw nsw i8 %x, -128. What does pebble-peephole produce?

  1. shl nuw nsw i8 %x, 7
  2. shl nuw i8 %x, 7
  3. shl nsw i8 %x, 7
  4. Nothing: -128 is not a power of two
Answer format: one letter
Question 47 find-flags-dropped · text · 1 pt · 08-refinement-ub-and-fast-math

Which llvm::Instruction member function (declared in llvm/include/llvm/IR/Instruction.h)
clears all poison-generating flags of an instruction, the fallback the InstCombine guide
recommends when keeping a flag would need a proof?

Answer format: a short answer
Question 48 fp-nsz · single · 1 pt · 08-refinement-ub-and-fast-math

Which floating-point rewrite is valid without any fast-math flag in LLVM IR?

  1. fadd double %x, 0.0 ⇒ %x
  2. fadd double %x, -0.0 ⇒ %x
  3. fmul double %x, 0.0 ⇒ 0.0
  4. fsub double %x, %x ⇒ 0.0
Answer format: one letter
Question 49 fp-contract · single · 1 pt · 08-refinement-ub-and-fast-math

clang-23 -O2 compiles double f(double a, double b, double c) { return a * b + c; } to a call of
llvm.fmuladd.f64, but not with -ffp-contract=off. What does fmuladd permit?

  1. Nothing: it is always computed as a fused multiply-add with one rounding
  2. The back end may fuse the multiply and add into one rounding (an FMA) or keep two roundings; clang's C default -ffp-contract=on allows this contraction within an expression
  3. Arbitrary reassociation of a * b + c
  4. Ignoring NaNs and infinities
Answer format: one letter
Question 50 smt-query · single · 1 pt · 09-verifying-transformations

Alive2's refinement check for a source with nondeterminism (e.g. freeze) is an SMT query of the
form of Definition 13.9.2. Which quantifier structure does it have?

  1. ∀ inputs ∃ source choices: the values are equal
  2. ∃ inputs, poison masks and target choices, ∀ source choices: the source is defined and the target's outcome is not allowed; unsat means valid
  3. ∃ inputs: source ≠ target; sat means valid
  4. ∀ inputs ∀ choices: source = target
Answer format: one letter
Question 51 alive-checks · single · 1 pt · 09-verifying-transformations

alive-tv checks %r = add nsw i8 %x, %x ⇒ %r = shl nuw i8 %x, 1. Which part of the
refinement check (Algorithm 13.9.3: UB, then poison, then value) fails?

  1. UB: the target has undefined behavior
  2. Poison: the target is poison where the source is not (e.g. x = −64: source −128, target poison)
  3. Value: the two compute different numbers
  4. None: the rewrite is valid
Answer format: one letter
Question 52 bounded-width · number · 1 pt · 09-verifying-transformations

The width-generic rule and iN %x, 1023 ⇒ %x is checked by bounded enumeration. What is the
smallest width N at which it is invalid?

Answer format: a number
Question 53 bounded-inputs · number · 1 pt · 09-verifying-transformations

How many inputs does ch13-rewrite-check (lab Part B) enumerate for functions with arguments
(i4 %x, i3 noundef %y, i2 %z)?

Answer format: a number
Question 54 tv-vs-verified · multi · 1 pt · 09-verifying-transformations

Which statements about translation validation (TV, e.g. Alive2 run after each opt pass) and a
verified compiler (CompCert) are true?

  1. TV checks one run of the compiler on one input program; a verified compiler's proof covers every run
  2. TV may answer 'unknown' (timeouts, unsupported features); CompCert either compiles with a guarantee or fails
  3. TV requires the optimizer itself to be proved correct
  4. Csmith found no wrong-code bugs in the verified parts of CompCert
Answer format: letters, e.g. a, c
Question 55 compcert-theorem · single · 1 pt · 09-verifying-transformations

What does CompCert's main correctness theorem (transf_c_program_correct) state?

  1. Every C program compiles successfully
  2. If compilation succeeds, there is a backward simulation: every behavior of the generated assembly is a behavior of the source C program (for programs without undefined behavior)
  3. The generated code is as fast as GCC -O2
  4. The assembly and the C program have identical sets of behaviors, including undefined ones
Answer format: one letter