Skip to content

Theory test — Chapter 14

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 14                                   # interactive
./course quiz template 14 -o answers/ch14.yaml  # or fill in a file ...
./course quiz grade 14                             # ... and grade it
Question 1 lattice-height-map · number · 1 pt · 01-lattices-and-fixed-points

Proposition 14.1.8 gives the heights of the standard constructions. What is the height of the
lattice \(\mathit{Vars} \to \mathbb{Z}_\bot^\top\) (constant propagation) for a program with
5 variables, ordered pointwise?

Answer format: a number
Question 2 lattice-is-lattice · multi · 1 pt · 01-lattices-and-fixed-points

Which of these posets (given by their covering relations, read "x < y") are lattices?

  1. bot < a < b < top, bot < c < top (the pentagon N5)
  2. bot < a, bot < b, a < c, a < d, b < c, b < d, c < top, d < top (the bow tie)
  3. bot < v0, bot < v1, bot < v2 (three maximal elements, no top)
  4. bot < a, bot < b, bot < c, a < top, b < top, c < top (the diamond M3)
Answer format: letters, e.g. a, c
Question 3 llvm-where-lattice-merge · text · 1 pt · 01-lattices-and-fixed-points

In LLVM 23, open llvm/include/llvm/Analysis/ValueLattice.h and read ValueLatticeElement::mergeIn.
When two different integer constants are merged and range merging is allowed, which lattice tag
does the result have? (Give the enumerator name.)

Answer format: a short answer
Question 4 tarski-least-fixpoint · single · 1 pt · 01-lattices-and-fixed-points

Let \(f\) be a monotone function on a complete lattice \(L\). Which set does Knaster–Tarski say the
least fixed point is the meet of?

  1. \(\{x \mid x \sqsubseteq f(x)\}\) (the post-fixed points)
  2. \(\{x \mid f(x) \sqsubseteq x\}\) (the pre-fixed points)
  3. \(\{f^{k}(\bot) \mid k \ge 0\}\)
  4. \(\{x \mid f(x) = x\}\), but only when \(f\) is distributive
Answer format: one letter
Question 5 monotone-distributive · multi · 1 pt · 01-lattices-and-fixed-points

On the constant-propagation lattice \(\{x, y\} \to \mathbb{Z}_\bot^\top\), consider the transfer function
of z = x + y. Which statements are true?

  1. It is monotone.
  2. It is distributive.
  3. \(f([x{=}2, y{=}3] \sqcup [x{=}3, y{=}2])\) gives \(z = \top\) while \(f([x{=}2,y{=}3]) \sqcup f([x{=}3,y{=}2])\) gives \(z = 5\).
  4. Because it is not distributive, Kildall's algorithm may fail to terminate on it.
Answer format: letters, e.g. a, c
Question 6 kleene-iterations-interval · number · 1 pt · 01-lattices-and-fixed-points

For i = 0; while (i < 10) { i = i + 1; } the interval at the loop head satisfies
\(H = [0,0] \sqcup ((H \sqcap [-\infty, 9]) + 1)\). Plain Kleene iteration (no widening) computes
\(H_1 = F(\bot), H_2 = F(H_1), \dots\) and stops at the first \(k\) with \(H_k = H_{k-1}\)
(with \(H_0 = \bot\)). How many applications of \(F\) does it perform, counting the final one that
confirms the fixed point?

Answer format: a number
Question 7 kleene-stop-early · single · 1 pt · 01-lattices-and-fixed-points

A liveness solver stops Kleene iteration after \(k\) steps, before the fixed point, and reports
\(F^{k}(\bot)\). What can be said about the result?

  1. It over-approximates the least fixed point, so it is sound but imprecise.
  2. It under-approximates the least fixed point, so some live variables may be missing — unsound.
  3. It equals the greatest fixed point.
  4. Nothing: it may be incomparable with the least fixed point.
Answer format: one letter
Question 8 framework-instance · mapping · 1 pt · 02-monotone-frameworks

Describe live-variable analysis as a monotone-framework instance. Give, for each key, one of the
listed values: direction (forward / backward), join (union / intersection), boundary
(the value at the exits: empty / universe), init (the starting value of every other point: empty / universe).

Keys: direction, join, boundary, init
Answer format: one value per key
Question 9 kildall-updates · number · 1 pt · 02-monotone-frameworks

Constant propagation on: A: if c < d → B, C; B: x = 2; y = 3 → D; C: x = 3; y = 2 → D;
D: z = x + y → E; E: ret z. Run Kildall's algorithm (Algorithm 14.2.10) with a FIFO worklist
initialized to A, B, C, D, E; removing a node applies its function and joins the result into each
successor, adding the successor if its IN changed. How many times is IN of some node changed
(strictly raised) during the run?

Answer format: a number
Question 10 llvm-where-sparse-solver · text · 1 pt · 02-monotone-frameworks

In LLVM 23, open llvm/include/llvm/Analysis/SparsePropagation.h. What is the name of the class
template whose Solve method runs the propagation to a fixed point?

Answer format: a short answer
Question 11 mop-vs-mfp-const · mapping · 1 pt · 02-monotone-frameworks

Same program as in kildall-updates: A: if c < d → B, C; B: x = 2; y = 3 → D;
C: x = 3; y = 2 → D; D: z = x + y → E; E: ret z. Give the value of z at the entry of E in
the MOP solution and in the MFP solution (a number, or top).

Keys: MOP, MFP
Answer format: one value per key
Question 12 distributive-exact · multi · 1 pt · 02-monotone-frameworks

For which of these analyses is the MFP solution always equal to the MOP solution?

  1. reaching definitions
  2. live variables
  3. constant propagation over \(\mathit{Vars} \to \mathbb{Z}_\bot^\top\)
  4. available expressions
  5. interval analysis (without widening, on a loop-free program)
Answer format: letters, e.g. a, c
Question 13 mop-undecidable · single · 1 pt · 02-monotone-frameworks

What does Kam and Ullman's undecidability result (Theorem 14.2.14) say?

  1. MFP is undecidable for monotone frameworks with infinite lattices.
  2. No algorithm computes MOP for every instance of every monotone framework; the proof reduces Post's correspondence problem to a constant-propagation-like framework.
  3. MOP is undecidable even for distributive frameworks on finite lattices.
  4. Kildall's algorithm may not terminate on monotone frameworks.
Answer format: one letter
Question 14 rd-in-running · set · 1 pt · 03-classic-analyses

The running example (definitions numbered in order):
A: d1 x = a*b; d2 i = 0; d3 s = 0 → B; B: if i < n → C, F; C: d4 t = a*b; if t < s → D, E;
D: d5 s = s+t; d6 a = t-1 → E; E: d7 u = a*b; d8 i = i+1 → B; F: ret s.
Give OUT[E] for reaching definitions.

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 15 llvm-where-reaching-defs · text · 1 pt · 03-classic-analyses

In LLVM 23, open llvm/lib/CodeGen/ReachingDefAnalysis.cpp. Which method handles a block the
second time LoopTraversal visits it because it is part of a loop?

Answer format: a short answer
Question 16 live-in-running · set · 1 pt · 03-classic-analyses

Running example: A: x = a*b; i = 0; s = 0 → B; B: if i < n → C, F; C: t = a*b; if t < s → D, E;
D: s = s+t; a = t-1 → E; E: u = a*b; i = i+1 → B; F: ret s. Give IN[D] for live variables.

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 17 ssa-liveness-phi · single · 1 pt · 03-classic-analyses

Block H contains %x = phi i32 [ %a, %P ], [ %b, %Q ], with predecessors P and Q; %a and %b are
defined elsewhere and not used anywhere else. Under the SSA liveness convention of Definition 14.3.9
(and Liveness.h), which statement is true?

  1. %a and %b are both live-in to H.
  2. %a is live-out of P (not of Q), %b is live-out of Q (not of P); neither is live-in to H because of the phi, and %x is not live-in to H.
  3. %a and %b are live-out of both P and Q.
  4. %x is live-in to H because it is defined there.
Answer format: one letter
Question 18 ae-in-running · set · 1 pt · 03-classic-analyses

Running example: A: x = a*b; i = 0; s = 0 → B; B: if i < n → C, F; C: t = a*b; if t < s → D, E;
D: s = s+t; a = t-1 → E; E: u = a*b; i = i+1 → B; F: ret s. Expressions are right-hand sides
with a variable operand. Give IN[E] for available expressions (write {} for the empty set).

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 19 vbe-in-running · set · 1 pt · 03-classic-analyses

Running example: A: x = a*b; i = 0; s = 0 → B; B: if i < n → C, F; C: t = a*b; if t < s → D, E;
D: s = s+t; a = t-1 → E; E: u = a*b; i = i+1 → B; F: ret s. Give IN[D] for very busy
expressions.

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 20 classic-directions · mapping · 1 pt · 03-classic-analyses

Give the direction and merge of each classic analysis as forward-may, forward-must,
backward-may or backward-must.

Keys: reaching-definitions, liveness, available-expressions, very-busy-expressions
Answer format: one value per key
Question 21 cp-height · number · 1 pt · 03-classic-analyses

The running example has the 8 variables a b i n s t u x. Simple constant propagation uses the
lattice \(\mathit{Vars} \to \mathbb{Z}_\bot^\top\). At most how many times can the fact at one program
point strictly increase during Kildall's algorithm?

Answer format: a number
Question 22 uninit-is-vs-may · mapping · 1 pt · 03-classic-analyses
int never(void)      { int y; return y + 1; }
int sometimes(int c) { int x; if (c) x = 1; return x; }
int both(int c)      { int z; if (c) z = 1; else z = 2; return z; }

Compiled at -O0, what does pebble-uninit (E5) report for the loads of y, x, z? Answer
is, may or none.

Keys: y, x, z
Answer format: one value per key
Question 23 llvm-where-uninit-worklist · text · 1 pt · 03-classic-analyses

In LLVM 23, open clang/lib/Analysis/UninitializedValues.cpp and find runUninitializedVariablesAnalysis.
Which worklist class does it use to order the blocks?

Answer format: a short answer
Question 24 rr-passes-postorder · mapping · 1 pt · 04-iterative-solvers

Reaching definitions on the running example (A → B; B → C, F; C → D, E; D → E; E → B), solved by
round-robin in RPO (A B F C D E) and in postorder. How many passes does each need, counting the
final pass that changes nothing?

Keys: rpo, postorder
Answer format: one value per key
Question 25 d-plus-two · number · 1 pt · 04-iterative-solvers

CFG (successors in listed order): A → B; B → C; C → D, E; D → C; E → B, F. Depth-first search from
A gives the back edges D → C and E → B. By the Kam–Ullman theorem (Theorem 14.4.6), at most how
many round-robin passes in RPO does any gen/kill problem need on this CFG, counting the confirming pass?

Answer format: a number
Question 26 llvm-where-stacklifetime-order · single · 1 pt · 04-iterative-solvers

In LLVM 23, llvm/lib/Analysis/StackLifetime.cpp, StackLifetime::calculateLocalLiveness iterates
while (Changed). In which order does each pass visit the blocks, and what does the TODO there say?

  1. Reverse postorder via ReversePostOrderTraversal; the TODO asks for bit vectors.
  2. Depth-first preorder, depth_first(&F); the TODO suggests switching to a worklist instead of traversing the entire graph.
  3. A priority worklist; the TODO asks for widening.
  4. Postorder via post_order(&F); the TODO asks for SCC ordering.
Answer format: one letter
Question 27 worklist-fifo-pops · sequence · 1 pt · 04-iterative-solvers

Liveness on the running example (A → B; B → C, F; C → D, E; D → E; E → B; F exits) with a FIFO
worklist, following Dataflow.h: the queue starts with every node in RPO of the reverse graph,
F B E D C A; pop the front, recompute IN; if it changed, append each predecessor (in listed order:
preds of B are A, E; of E are C, D) not already queued. Give the sequence of popped nodes.

Answer format: items in order, e.g. A B C
Question 28 bitvector-genkill · text · 1 pt · 04-iterative-solvers

Facts f1 f2 f3 f4 are bits 1–4, written left to right. A block has gen = 0101, kill = 1100, and
IN = 1010. What is OUT = gen | (IN & ~kill), as a 4-bit string?

Answer format: a short answer
Question 29 bitvector-words · number · 1 pt · 04-iterative-solvers

A reaching-definitions universe has 300 definitions, stored in 64-bit words. How many word
operations does one block transfer gen | (in & ~kill) take (count AND-NOT and OR as one
operation each per word)?

Answer format: a number
Question 30 intervals-running · mapping · 1 pt · 05-elimination-methods

Allen–Cocke intervals (Algorithm 14.5.4) of the running example's CFG: A → B; B → C, F; C → D, E;
D → E; E → B. For each node give the header of the interval that contains it.

Keys: A, B, C, D, E, F
Answer format: one value per key
Question 31 genkill-closure · mapping · 1 pt · 05-elimination-methods

In the gen/kill algebra (Lemma 14.5.2), the body of the running example's loop summarizes to
\((G, K) = (\{d4, d5, d6, d7, d8\}, \{d2\})\). Give its closure \((G, K)^{*}\) as sets G and K.

Keys: G, K
Answer format: one value per key (a set: {x, y})
Question 32 structural-schemas · single · 1 pt · 05-elimination-methods

What does Sharir's structural analysis do when it meets an irreducible (improper) region?

  1. It rejects the program.
  2. It collapses the region into an "improper region" node whose summary is computed by iterating inside the region.
  3. It splits nodes until the graph is reducible, always.
  4. It treats the region as a while loop.
Answer format: one letter
Question 33 elimination-irreducible · single · 1 pt · 05-elimination-methods

CFG: r → a, r → b, a → b, b → a. What happens to Allen–Cocke interval analysis?

  1. One interval {r, a, b}; derived graph is one node.
  2. Intervals {r}, {a}, {b}; the derived graph equals the original, so the derived sequence never reaches one node: the graph is irreducible and needs node splitting or iteration.
  3. Intervals {r}, {a, b}.
  4. The algorithm loops forever.
Answer format: one letter
Question 34 path-expression-interpret · mapping · 1 pt · 05-elimination-methods

Reaching definitions on the running example (A: d1 x, d2 i, d3 s; C: d4 t; D: d5 s, d6 a;
E: d7 u, d8 i; B only tests). Interpret the path expression of the single path
B → C → D → E → B (edges \(a_2 a_4 a_6 a_7\)) as the composition \(f_E \circ f_D \circ f_C \circ f_B\) of
gen/kill functions. Give the resulting sets G and K.

Keys: G, K
Answer format: one value per key (a set: {x, y})
Question 35 genkill-compose · mapping · 1 pt · 05-elimination-methods

Compose gen/kill functions: \(f_1 = (G_1, K_1) = (\{d1, d2\}, \{d3\})\) runs first, then
\(f_2 = (\{d3\}, \{d1\})\). Give \(f_2 \circ f_1\) as sets G and K.

Keys: G, K
Answer format: one value per key (a set: {x, y})
Question 36 defuse-quadratic · mapping · 1 pt · 06-sparse-analysis

A switch with 4 cases each assigns x; after the switch there are 5 uses of x. How many
def-use chains link them without SSA, and how many SSA edges are there once a phi merges the 4
definitions (count phi-operand edges and phi-to-use edges)?

Keys: without-ssa, with-ssa
Answer format: one value per key
Question 37 sparse-vs-dense-cost · single · 1 pt · 06-sparse-analysis

Why is sparse constant propagation over SSA edges cheaper than dense (per-block) constant propagation?

  1. It computes a less precise result.
  2. A value's lattice cell changes at most height-many times and each change is sent only to its uses, so the cost is \(O(h \cdot \text{uses})\) instead of copying whole environments through every block.
  3. It ignores loops.
  4. It uses bit vectors.
Answer format: one letter
Question 38 sccp-executable · mapping · 1 pt · 06-sparse-analysis

A: x = 1; if x < 2 → B, C; B: y = 2 → D; C: y = 3 → D; D: z = y (in SSA, y at D is a phi of
the two definitions). Give the value of z found by SCCP (Wegman–Zadeck) and by dense constant
propagation that treats both branches as executable (a number, or top).

Keys: SCCP, CP
Answer format: one value per key
Question 39 sparse-liveness-marks · number · 1 pt · 06-sparse-analysis
define i32 @sum_to(i32 %n) {
entry:
  br label %for.cond
for.cond:
  %s.0 = phi i32 [ 0, %entry ], [ %add, %for.inc ]
  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
  %cmp = icmp slt i32 %i.0, %n
  br i1 %cmp, label %for.body, label %for.end
for.body:
  %add = add nsw i32 %s.0, %i.0
  br label %for.inc
for.inc:
  %inc = add nsw i32 %i.0, 1
  br label %for.cond
for.end:
  ret i32 %s.0
}

Sparse liveness (Algorithm 14.6.4, lab L1) counts one mark each time a value is newly added to a
block's live-in set. What is the total number of marks for this function?

Answer format: a number
Question 40 llvm-where-sccp-edge · single · 1 pt · 06-sparse-analysis

In LLVM 23, llvm/lib/Transforms/Utils/SCCPSolver.cpp, SCCPInstVisitor::markEdgeExecutable:
when an edge becomes executable into a block that was already executable, which instructions of the
destination are revisited?

  1. All instructions of the block.
  2. Only the PHI nodes of the destination block.
  3. Only the terminator.
  4. None; the block is skipped because it is already executable.
Answer format: one letter
Question 41 seg-meet-nodes · set · 1 pt · 06-sparse-analysis

Running example CFG: A → B; B → C, F; C → D, E; D → E; E → B. A forward problem has non-identity
transfer functions only at A and D. Which nodes are the meet nodes of its sparse evaluation graph,
\(\mathrm{DF}^{+}(\{A, D\})\)?

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 42 memoryssa-seg · single · 1 pt · 06-sparse-analysis

In what sense is LLVM's MemorySSA a sparse evaluation graph?

  1. It stores one bit vector per block for memory.
  2. Blocks with stores/calls are the interesting nodes (MemoryDef), MemoryPhis sit at the iterated dominance frontier of those blocks, and each MemoryUse points directly to its nearest dominating definition — a sparse graph for "which memory state reaches here".
  3. It runs alias analysis sparsely.
  4. It is a special case of IFDS.
Answer format: one letter
Question 43 galois-best-transformer · text · 1 pt · 07-abstract-interpretation

In the interval domain, the best abstract transformer of \(f(x) = x \cdot x\) is
\(\alpha \circ f \circ \gamma\). What is it on \([-2, 3]\)? Write the interval as [lo, hi].

Answer format: a short answer
Question 44 interval-mul · text · 1 pt · 07-abstract-interpretation

What is \([-2, 3] \times [4, 5]\) in the interval domain? Write [lo, hi].

Answer format: a short answer
Question 45 congruence-join · text · 1 pt · 07-abstract-interpretation

Congruences \(a\mathbb{Z} + b\) (Definition 14.7.5). What is \((6\mathbb{Z} + 1) \sqcup (6\mathbb{Z} + 4)\)?
Write it as aZ+b.

Answer format: a short answer
Question 46 interval-add-wrap · single · 1 pt · 07-abstract-interpretation

%y = add i8 %x, 1 where %x is in \([0, 127]\). What must a sound interval analysis (E6-R2) give
for %y, without and with the nsw flag?

  1. \([1, 128]\) in both cases
  2. Without nsw: \([1, 127]\); with nsw: top
  3. Without nsw: top (\([-128, 127]\)), because 127 + 1 wraps to −128; with nsw: \([1, 127]\), because overflow would be poison
  4. Top in both cases
Answer format: one letter
Question 47 llvm-where-add-nowrap · text · 1 pt · 07-abstract-interpretation

In LLVM 23, open llvm/include/llvm/IR/ConstantRange.h. Which method returns the range of an add
that carries no-wrap flags (its extra argument says which: nsw, nuw)?

Answer format: a short answer
Question 48 octagon-vs-interval · single · 1 pt · 07-abstract-interpretation

i = 0; j = 0; while (i < 10) { i = i + 1; j = j + 1; }. After widening and narrowing, what do
the interval and the octagon domains know about j at the loop exit?

  1. Both: \(j = 10\)
  2. Intervals: \(j \in [0, +\infty]\); octagons: \(j = 10\), because they keep \(i - j = 0\) and \(i = 10\) at the exit
  3. Intervals: \(j \in [0, 10]\); octagons: \(j = 10\)
  4. Both: \(j \in [0, +\infty]\)
Answer format: one letter
Question 49 polyhedra-cost · single · 1 pt · 07-abstract-interpretation

Which statement about the cost of relational domains is right?

  1. Octagons and polyhedra both cost \(O(1)\) per operation.
  2. Octagon operations cost \(O(v^2)\) space and \(O(v^3)\) time for strong closure; polyhedra in double description can be exponential in the number of variables (constraints ↔ generators).
  3. Polyhedra are cheaper than octagons because they have fewer constraints.
  4. Octagons are exponential, polyhedra cubic.
Answer format: one letter
Question 50 widening-iterates · text · 1 pt · 07-abstract-interpretation

i = 0; while (i < 100) { i = i + 1; }. The loop head iterates \(H_{k+1} = H_k \nabla F(H_k)\) from
\(H_0 = \bot\), with the standard interval widening. What is the stable value of \(H\) at the end of
the ascending phase? Write [lo, hi] (use +inf for \(+\infty\)).

Answer format: a short answer
Question 51 narrowing-exit · mapping · 1 pt · 07-abstract-interpretation

Continue widening-iterates: one narrowing step \(H \mathbin{\Delta} F(H)\) from \(H = [0, +\infty]\). Give
the upper bound of the loop-head interval after narrowing, and the value of i at the loop exit
(numbers).

Keys: head-upper-bound, exit
Answer format: one value per key
Question 52 seminaive-derivations · mapping · 1 pt · 08-datalog-and-ifds

path(X, Y) :- edge(X, Y). and path(X, Z) :- path(X, Y), edge(Y, Z). on the chain
n0 → n1 → … → n7 (8 nodes). With the counters of the lab spec (a derivation = one successful body
instantiation, duplicates included), how many derivations do semi-naive and naive evaluation make?

Keys: semi-naive, naive
Answer format: one value per key
Question 53 datalog-stratification · number · 1 pt · 08-datalog-and-ifds

How many strata does this program need?
path(X,Y) :- edge(X,Y). path(X,Z) :- path(X,Y), edge(Y,Z).
node(X) :- edge(X,Y). node(Y) :- edge(X,Y).
unreach(X,Y) :- node(X), node(Y), !path(X,Y).

Answer format: a number
Question 54 ifds-realizable · single · 1 pt · 08-datalog-and-ifds

main calls f at call sites c1 and c2; f returns to r1 and r2 respectively. Which
supergraph path is not realizable?

  1. main → c1 → entry(f) → exit(f) → r1
  2. main → c1 → entry(f) → exit(f) → r2
  3. main → c2 → entry(f) → exit(f) → r2
  4. main → c1 → entry(f) → exit(f) → r1 → c2 → entry(f) → exit(f) → r2
Answer format: one letter
Question 55 ifds-distributive · multi · 1 pt · 08-datalog-and-ifds

Which of these problems can be solved exactly by IFDS (finite fact set, distributive flow functions over union)?

  1. possibly-uninitialized variables
  2. taint analysis (which variables may carry untrusted data)
  3. full constant propagation over \(\mathbb{Z}_\bot^\top\)
  4. reaching definitions
Answer format: letters, e.g. a, c