Skip to content

Theory test — Chapter 8

41 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 8                                   # interactive
./course quiz template 8 -o answers/ch08.yaml  # or fill in a file ...
./course quiz grade 8                             # ... and grade it
Question 1 tac-count-quads · number · 1 pt · 01-linear-irs

Algorithm 8.1.4 translates the two Tiny statements

x = (a + b) * c - d;
y = a && b;

into three-address code (each statement computes straight into its variable). How many
TAC instructions does it emit for these two statements (labels are not instructions)?

Answer format: a number
Question 2 triples-reorder · number · 1 pt · 01-linear-irs

A triple table: (0) add a, b; (1) sub a, b; (2) mul (0), (1); (3) add (2), c.
You exchange the execution order of triples 0 and 1 by physically moving them in the
table (plain triples, no indirection). How many argument references must be rewritten?

Answer format: a number
Question 3 stack-heights · sequence · 1 pt · 01-linear-irs

Give the stack height at entry to each instruction (positions 0–8) as computed by
Algorithm 8.1.6:

0  push 2
1  load x
2  add
3  load y
4  jz L
5  push 1
6  store x
   L:
7  load x
8  ret
Answer format: items in order, e.g. A B C
Question 4 verify-reject · single · 1 pt · 01-linear-irs

Which of these stack programs does height verification (Algorithm 8.1.6) reject?

  1. push 1; jz L; push 5; L: push 7; add; ret
  2. push 1; push 2; add; ret
  3. push 0; jz L; push 3; ret; L: push 4; ret
  4. load x; neg; ret
Answer format: one letter
Question 5 stack-to-register-count · number · 1 pt · 01-linear-irs

The stack code of (a + b) * (c - d) has 7 instructions. How many register
instructions remain after Algorithm 8.1.9 and copy propagation, if leaves may be
used directly as operands (as in Lua's RK operands)?

Answer format: a number
Question 6 lua-rk · single · 1 pt · 01-linear-irs

In Lua 5.4's listing, what does MODK 3 2 0 (with constant 0 = 3) compute?

  1. R[3] := R[2] % K[0], i.e. R[3] := i % 3 when R[2] holds i
  2. R[3] := K[2] % R[0]
  3. push R[2] % 3 on the operand stack
  4. R[2] := R[3] % 0
Answer format: one letter
Question 7 leaders-listing · set · 1 pt · 02-cfgs-and-orders

Give the leaders (instruction numbers) of this listing:

 0  i = 0
   loop:
 1  c = lt i, 10
 2  ifz c goto done
 3  r = rem i, 2
 4  if r goto odd
 5  s = add s, i
 6  goto next
   odd:
 7  s = sub s, 1
   next:
 8  i = add i, 1
 9  goto loop
   done:
10  if s goto out
11  s = 1
   out:
12  return s
Answer format: items separated by commas or spaces, e.g. {a, b}
Question 8 leader-unreferenced-label · single · 1 pt · 02-cfgs-and-orders

A label U: precedes instruction 6, but no instruction jumps to U, and instruction 5 is x = add x, 1. Is instruction 6 a leader?

  1. No: only jump targets and instructions after jumps start blocks, so 5 and 6 stay in one block
  2. Yes: every labeled instruction starts a basic block
  3. Only if 6 is a jump
  4. It depends on the DFS order
Answer format: one letter
Question 9 critical-edges-set · set · 1 pt · 02-cfgs-and-orders

CFG (successors in order): A→B, C; B→D, E; C→E; D→F; E→F, B; F (exit).
Which edges are critical? Write them as X->Y.

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 10 split-count · number · 1 pt · 02-cfgs-and-orders

After splitting every critical edge of the CFG of the previous question (6 blocks), how many blocks does the CFG have?

Answer format: a number
Question 11 llvm-where-critical · text · 1 pt · 02-cfgs-and-orders

Find where LLVM does it: which function in llvm/lib/Analysis/CFG.cpp (LLVM 23.1.2) decides whether the successor edge of a terminator is critical? (name only)

Answer format: a short answer
Question 12 rpo-sequence · sequence · 1 pt · 02-cfgs-and-orders

CFG (successors visited in the listed order): A→B, C; B→D, E; C→E; D→F; E→F, B; F.
Give the reverse postorder of a DFS from A.

Answer format: items in order, e.g. A B C
Question 13 llvm-where-rpo · text · 1 pt · 02-cfgs-and-orders

Find where LLVM does it: which class template in llvm/include/llvm/ADT/PostOrderIterator.h iterates a function's blocks in reverse postorder?

Answer format: a short answer
Question 14 hir-desugar-while · single · 1 pt · 03-trees-and-dags

What does rustc's AST-to-HIR lowering turn while c { b } into?

  1. loop { if c { b } else { break } }
  2. if c { loop { b; if !c { break } } }
  3. a MIR goto loop
  4. nothing: while is kept in HIR
Answer format: one letter
Question 15 ast-vs-dag-size · mapping · 1 pt · 03-trees-and-dags

Let e0 = a and e(k+1) = e(k) + e(k). For e3, give the number of nodes of its syntax
tree and of its expression DAG.

Keys: tree, dag
Answer format: one value per key
Question 16 lvn-redundant · set · 1 pt · 03-trees-and-dags

Run local value numbering (Algorithm 8.3.5; add and mul are commutative) on this block.
Which instructions (numbers) are redundant?

0  t1 = add a, b
1  t2 = mul t1, c
2  t3 = add b, a
3  a = sub a, 1
4  t4 = add a, b
5  t5 = mul t3, c
6  t6 = add t2, t5
Answer format: items separated by commas or spaces, e.g. {a, b}
Question 17 lvn-nodes · number · 1 pt · 03-trees-and-dags

How many nodes does the DAG of the block in the previous question have (leaves plus operator nodes)?

Answer format: a number
Question 18 llvm-where-earlycse-commutative · text · 1 pt · 03-trees-and-dags

Find where LLVM does it: llvm/lib/Transforms/Scalar/EarlyCSE.cpp hashes instructions through a small wrapper struct whose hash swaps the operands of commutative binary operators. What is the struct called?

Answer format: a short answer
Question 19 phi-parallel-swap · mapping · 1 pt · 04-ssa-and-block-arguments

Block B1 starts with a1 = phi [1, B0], [b1, B2] and b1 = phi [2, B0], [a1, B2], and B2
branches back to B1 without changing anything. With the parallel-copy semantics of
Definition 8.4.2, what are a1 and b1 when control enters B1 for the third time
(B0→B1, then B2→B1 twice)?

Keys: a1, b1
Answer format: one value per key
Question 20 pruned-phi-count · number · 1 pt · 04-ssa-and-block-arguments

The TAC of gcd.tiny is

  a = 1071
  b = 462
L.0:
  t.0 = ne b, 0
  ifz t.0 goto L.1
  t = rem a, b
  a = b
  b = t
  goto L.0
L.1:
  return a

How many phi functions (block parameters) does pruned, minimal SSA of this listing have?

Answer format: a number
Question 21 phi-to-args-mapping · mapping · 1 pt · 04-ssa-and-block-arguments

In phi form, block J has x = phi [x1, T], [x0, E] and y = phi [5, T], [y0, E], and its
predecessors are T and E. In block-argument form, J becomes J(x, y). What argument lists
do the branches pass? Write each list as a b.

Keys: T, E
Answer format: one value per key
Question 22 multi-edge-args · single · 1 pt · 04-ssa-and-block-arguments

Block B0 ends with cbr c, B1(1), B1(2) and B1 is B1(x): ret x. What happens when you convert to phi form?

  1. It cannot be converted directly: a phi has one entry per predecessor block, so one of the two edges must be split first
  2. It becomes x = phi [1, B0], [2, B0], which LLVM accepts
  3. It becomes x = phi [1, B0], since the second edge is redundant
  4. Block arguments and phis are identical, so nothing special happens
Answer format: one letter
Question 23 mlir-where-phi · text · 1 pt · 04-ssa-and-block-arguments

Find where LLVM does it: in mlir/lib/Target/LLVMIR/ModuleTranslation.cpp (LLVM 23.1.2), which function fills in the LLVM phi nodes created for MLIR block arguments?

Answer format: a short answer
Question 24 gcm-late-placement · single · 1 pt · 05-graph-irs

In a sea-of-nodes graph, the floating node x = mul n, 3 has the function parameter n as
its only input (early block: Start) and is used only inside the loop body, which is at
loop depth 1. Where does global code motion (Algorithm 8.5.3) place it?

  1. In Start (or the latest block of loop depth 0 that dominates the loop), outside the loop
  2. In the loop body, next to its use
  3. In the loop header
  4. Nowhere: floating nodes are never placed
Answer format: one letter
Question 25 son-why-v8-left · multi · 1 pt · 05-graph-irs

Which reasons does V8's 2025 blog give for replacing TurboFan's sea of nodes with the CFG-based Turboshaft?

  1. In JavaScript most nodes end up on the effect or control chain, so the graph mirrors a CFG anyway
  2. The graphs are hard to inspect and debug
  3. Poor cache locality and slow compilation; the CFG compiler halved compile time
  4. Sea of nodes cannot represent loops
Answer format: letters, e.g. a, c
Question 26 pdg-control-dep · mapping · 1 pt · 05-graph-irs

CFG: A→B, E; B→C, D; C→D; D→E; E (exit). For B, C and D, give the set of blocks it is
control dependent on (Definition 8.5.4).

Keys: B, C, D
Answer format: one value per key (a set: {x, y})
Question 27 rvsdg-theta · single · 1 pt · 05-graph-irs

How does an RVSDG represent a while loop?

  1. As a θ node whose single acyclic region computes the next values and a repeat predicate
  2. As a back edge between two γ nodes
  3. As a cycle of value edges in the top-level region
  4. As a phi node with a Loop control input
Answer format: one letter
Question 28 egraph-classes · number · 1 pt · 05-graph-irs

An e-graph holds exactly the terms g(f(a)) and g(f(b)) (6 e-classes: a, b, f(a), f(b),
g(f(a)), g(f(b))). You merge the classes of a and b and then rebuild. How many e-classes
remain?

Answer format: a number
Question 29 egraph-extraction · single · 1 pt · 05-graph-irs

After saturation, the root e-class contains a, (* e0 e7) and (/ e2 e1). Extraction with the cost function 'number of nodes' returns which term?

  1. a
  2. (/ (* a 2) 2), the input, because extraction prefers the original term
  3. (* a 1)
  4. It is undefined, because the e-graph is cyclic
Answer format: one letter
Question 30 cps-admin-redexes · number · 1 pt · 06-functional-irs

How many administrative redexes does the naive (Plotkin-style) CPS transform of (x + y) * z create (Definition 8.6.2)?

Answer format: a number
Question 31 cps-tail-calls · single · 1 pt · 06-functional-irs

Which statement about a program in continuation-passing style is true?

  1. Every call is a tail call; results are passed to continuations instead of being returned
  2. Continuations must be first-class closures, so CPS always allocates on the heap
  3. CPS cannot express loops
  4. CPS programs need phi functions at joins
Answer format: one letter
Question 32 anf-join-why · single · 1 pt · 06-functional-irs

Why does the lab's ANF use join points for if statements?

  1. Without them, the code after the if must be copied into both branches, which grows exponentially for a chain of ifs
  2. Because ANF forbids nested lets
  3. Because if cannot appear in tail position in ANF
  4. To make variables mutable
Answer format: one letter
Question 33 anf-size-chain · number · 1 pt · 06-functional-irs

A program is a chain of 5 statements if c_i {} else {} followed by return x. Translated
to ANF without join points (the rest is copied into both branches of each if), how many
copies of return x does the term contain?

Answer format: a number
Question 34 kelsey-nesting · mapping · 1 pt · 06-functional-irs

CFG in block-argument SSA: A→B; B→C, F; C→D, E; D→B; E→B; F returns. In Kelsey's
translation (Algorithm 8.6.7), inside which block's term is each block's join point
defined? Give the enclosing block for B, C, D, E and F.

Keys: B, C, D, E, F
Answer format: one value per key
Question 35 scope-is-dominance · single · 1 pt · 06-functional-irs

In the SSA ≡ ANF correspondence (Theorem 8.6.12), which SSA rule becomes "every name is used inside its lexical scope"?

  1. Every definition dominates its uses
  2. Every name is defined exactly once
  3. Phi operands must be constants
  4. Every block ends in exactly one terminator
Answer format: one letter
Question 36 mlir-partial-conversion · single · 1 pt · 07-multi-level-and-pipelines

You run mlir-opt euler1.mlir --convert-to-llvm without --convert-scf-to-cf first. What does the output contain?

  1. llvm operations, plus the scf.for / scf.if / scf.yield operations, which no pattern converted (a partial conversion)
  2. An error: scf operations are illegal
  3. Only llvm operations: --convert-to-llvm lowers every dialect
  4. Only the original arith and scf operations
Answer format: one letter
Question 37 mlir-where-conversion · text · 1 pt · 07-multi-level-and-pipelines

Find where LLVM does it: in mlir/lib/Transforms/Utils/DialectConversion.cpp (LLVM 23.1.2), which function runs a conversion that may leave legal-but-unconverted operations in place?

Answer format: a short answer
Question 38 pipeline-match · mapping · 1 pt · 07-multi-level-and-pipelines

Name the main mid-level IR (one word) that each compiler runs its mid-end analyses on: rustc (where the borrow checker runs), swiftc, gcc (tree optimizers).

Keys: rustc, swiftc, gcc
Answer format: one value per key
Question 39 mir-asserts-count · number · 1 pt · 07-multi-level-and-pipelines

rustc at opt-level 0 turns the Rust running example (if i % 3 == 0 || i % 5 == 0 { s += i; } i += 1; inside the loop) into MIR. Using Algorithm 8.7.6 and Rust's rules for %
(a check for division by zero and one for MIN % -1), how many assert terminators does the
function's MIR contain?

Answer format: a number
Question 40 pir-phis-gcd · number · 1 pt · 07-multi-level-and-pipelines

The hand-written PIR gcd of Lesson 8.7 is lowered with one alloca per local and then sroa. How many phi instructions does the resulting LLVM function @gcd have?

Answer format: a number
Question 41 pir-not-ssa · single · 1 pt · 07-multi-level-and-pipelines

Which statement about PIR is true?

  1. PIR locals are mutable storage; SSA is built by the shared back end (alloca + mem2reg, and your Ch 16 pass)
  2. PIR is in SSA form with block arguments, like SIL
  3. PIR has phi functions, like LLVM IR
  4. PIR has no control-flow graph; it is a tree
Answer format: one letter