Skip to content

Theory test — Chapter 24

47 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 24                                   # interactive
./course quiz template 24 -o answers/ch24.yaml  # or fill in a file ...
./course quiz grade 24                             # ... and grade it
Question 1 stage-order-witness · sequence · 1 pt · 01-pipeline-design

The abstract pass table of Lesson 24.1 (also ./course drill pass-order):

Passes (needs absent -> removes -> then adds):
  mem2reg       needs none of {-},  removes {A}, adds {-}
  loop-simplify needs none of {-},  removes {P}, adds {-}
  gvn           needs none of {A},  removes {R}, adds {D}
  sccp          needs none of {A},  removes {C}, adds {UD}
  simplifycfg   needs none of {-},  removes {U}, adds {-}
  licm          needs none of {AP}, removes {I}, adds {R}
  dce           needs none of {-},  removes {D}, adds {-}

A pass whose "needs absent" facts are present does nothing; a pass whose "removes" facts are all
absent does nothing. Facts: A allocas, P loops without preheader, R redundancies, C constant
branches, U unreachable blocks, D dead instructions, I loop-invariant code.

Start from \(\{A, P, R, D, I\}\) and run one round of the sequence
licm, mem2reg, loop-simplify, licm, gvn, dce. List, in order, the passes that changed the
fact set.

Answer format: items in order, e.g. A B C
Question 2 enabling-edges · mapping · 1 pt · 01-pipeline-design

With the pass table of stage-order-witness, pass \(p\) enables \(q\) (Definition 24.1.2) when
\(p\) removes a fact that \(q\) needs absent, or \(p\) adds a fact that \(q\) removes. For each of
mem2reg, loop-simplify, sccp, licm, give the set of passes it enables (write [] for none).

Keys: mem2reg, loop-simplify, sccp, licm
Answer format: one value per key (a set: {x, y})
Question 3 gate-mem2reg-twice · single · 1 pt · 01-pipeline-design

The reference -O1 design runs pebble-mem2reg in its first stage and again in the fixpoint
stage after inlining. Why is the second run not redundant?

  1. mem2reg is not idempotent, so a second run promotes allocas the first one missed
  2. Inlining copies the callee's entry-block allocas into the caller, so the SSA canonical form (no promotable allocas) is broken again and must be re-established before gvn and sccp
  3. The first run only handles integer allocas; the second handles aggregates
  4. The pass manager invalidates the dominator tree after inlining, and mem2reg rebuilds it
Answer format: one letter
Question 4 canonical-form-breakers · set · 1 pt · 01-pipeline-design

In the table of stage-order-witness, which passes can re-introduce a fact after another
pass removed it (that is, which passes have a non-empty "adds" column)?

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 5 fixpoint-rounds · number · 1 pt · 01-pipeline-design

With the table of stage-order-witness, start from \(\{R, C\}\) and iterate the stage
gvn, sccp, simplifycfg, dce until a round changes nothing. Counting the final unchanged round,
as Algorithm 24.1.7 does (pebble-o1 stops after the round whose hash equals the previous one),
how many rounds run?

Answer format: a number
Question 6 find-devirt-iterations · number · 1 pt · 01-pipeline-design

Find it in LLVM: buildInlinerPipeline in llvm/lib/Passes/PassBuilderPipelines.cpp (LLVM 23.1.2)
wraps the inliner's CGSCC pipeline in createDevirtSCCRepeatedPass(..., MaxDevirtIterations).
What is the default value, the N of devirt<N> that
opt -passes='default<O2>' -print-pipeline-passes prints?

Answer format: a number
Question 7 redundant-check-table · mapping · 1 pt · 02-compile-time-vs-run-time

Pebble, with a: [int; 16], s and t arbitrary ints, y an arbitrary int, d = (y & 7) + 1:

for i in 0..16 {
    s = s + a[i];        // C1: bounds check on a[i];   C4: overflow check on s + a[i]
    t = t &+ a[i + 1];   // C2: bounds check on a[i + 1]
    s = s / d;           // C3: division checks (d == 0, and MIN / -1)
}

For each check say whether static check elimination (Algorithm 24.2.3, with SCEV facts about
i and the range of d) can remove it: yes or no.

Keys: C1, C2, C3, C4
Answer format: one value per key
Question 8 versioning-exit-phi · single · 1 pt · 02-compile-time-vs-run-time

Loop versioning (Algorithm 24.2.5) clones a loop \(L\) into \(L_\pi\) and \(L\) and branches on the
run-time test \(\pi\). A value \(v\) defined in the loop and used after it existed once before
versioning. What must be inserted so that the code after the loops still has one definition of \(v\)?

  1. Nothing: LLVM allows a use to have two reaching definitions when they are clones
  2. A phi in the block where the two versions' exits join, with one incoming value per version (each version's own LCSSA phi)
  3. A store of \(v\) to a stack slot in both versions and a load after the join
  4. A select on \(\pi\) after the join, since \(\pi\) was computed before the loops
Answer format: one letter
Question 9 dominating-condition-check · single · 1 pt · 02-compile-time-vs-run-time
if d == 0 { return 0; }
...                      // no assignment to d
q = x / d;               // PIR: assert d != 0, div_by_zero

Neither SCEV's range of d nor any loop fact proves d != 0 here. Which fact removes the
check, and where does LLVM's ScalarEvolution::isKnownPredicateAt get it (Algorithm 24.2.3)?

  1. None: without a range for d the check must stay
  2. The dominating branch: the check's block is only reached on the d != 0 edge of the if, which isKnownPredicateAt finds by isBasicBlockEntryGuardedByCond after isKnownPredicate (the context-free SCEV facts) fails
  3. Constant folding of d to a non-zero value
  4. The nsw flag on the division
Answer format: one letter
Question 10 deopt-stackmap-locations · mapping · 1 pt · 02-compile-time-vs-run-time

A deoptimization point (Algorithm 24.2.7) must record where the unoptimized code's state lives
at that point: i is in register %rbx; n was constant-folded to 1024 by the speculative
compile; window was spilled to the stack slot at [%rbp - 24]. In LLVM's stack-map record
format, which location kind does each get: Register, Constant, or Indirect?

Keys: i, n, window
Answer format: one value per key
Question 11 speculation-break-even · number · 1 pt · 02-compile-time-vs-run-time

A speculatively optimized function saves 5 cycles per call, net of its guard, whenever the
assumption holds; when the guard fails the call costs 2000 cycles more than the unoptimized
version (the deoptimization). What is the smallest number of successful calls per failure
at which speculation pays (total cycles saved strictly greater than cycles lost)?

Answer format: a number
Question 12 find-loop-versioning · text · 1 pt · 02-compile-time-vs-run-time

Find it in LLVM: in llvm/lib/Transforms/Utils/LoopVersioning.cpp (LLVM 23.1.2),
LoopVersioning::versionLoop creates the second copy of the loop by calling which utility
function?

Answer format: a short answer
Question 13 lookup-materializes · set · 1 pt · 03-jit-designs

An eager LLJIT session: module M defines main, f and g, where main calls f and
nothing calls g. It is added with addIRModule to a fresh JITDylib. Which functions have been
compiled to machine code after lookup("main") returns (Algorithm 24.3.3)?

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 14 lazy-compiled-set · set · 1 pt · 03-jit-designs

The same module through LLLazyJIT::addLazyIRModule: main calls f; f calls g only
when its argument is negative, and main passes 3; h is never called. After running main
once, which functions have been compiled (Proposition 24.3.8)?

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 15 stub-pointer-states · sequence · 1 pt · 03-jit-designs

For a lazily reexported function f, the stub jumps through a pointer \(p_f\). Give, in order,
what \(p_f\) points to (a) right after addLazyIRModule, (b) while the first call is being
resolved, (c) after the first call has returned. Use the tokens trampoline, body,
null (each may appear once or not at all).

Answer format: items in order, e.g. A B C
Question 16 reopt-tier-table · mapping · 1 pt · 03-jit-designs

ORC's ReOptimizeLayer instruments every function with a call counter and re-optimizes a
function when the counter reaches CallCountThreshold (default 10). After a run in which
f was called 12 times, g 3 times and h exactly 10 times, which functions were
re-optimized: yes or no for each?

Keys: f, g, h
Answer format: one value per key
Question 17 find-reoptimize-threshold · number · 1 pt · 03-jit-designs

Find it in LLVM: in llvm/include/llvm/ExecutionEngine/Orc/ReOptimizeLayer.h (LLVM 23.1.2),
what is the value of ReOptimizeLayer::CallCountThreshold, the call count at which
reoptimizeIfCallFrequent re-optimizes a function?

Answer format: a number
Question 18 find-lazy-callthrough · text · 1 pt · 03-jit-designs

Find it in LLVM: in llvm/lib/ExecutionEngine/Orc/LazyReexports.cpp (LLVM 23.1.2),
LazyCallThroughManager::resolveTrampolineLandingAddress cannot find the implementation symbol
(the lookup fails). Which address does it hand to the trampoline to jump to (the member it returns
from reportCallThroughError)?

Answer format: a short answer
Question 19 dwarf-expression-eval · number · 1 pt · 04-debug-info

Evaluate the DWARF location expression DW_OP_breg3 (rbx) +16; DW_OP_constu 8; DW_OP_plus
with %rbx = 0x1000 (Algorithm 24.4.5). The variable is in memory: at which address
(decimal)?

Answer format: a number
Question 20 loclist-from-events · mapping · 1 pt · 04-debug-info

Instructions are numbered 0..11. Variable x: defined into %rax at 0; spilled to the frame
slot fp-16 at 3 (the register copy stays valid); a call at 5 clobbers %rax (caller-saved);
reloaded into %rcx at 8. The location list after LiveDebugValues (Algorithm 24.4.7; the
drill dwarf-location's model) gives one location per instruction. Where is x at instructions
2, 6 and 9? Write rax, rcx, fp-16 or none.

Keys: 2, 6, 9
Answer format: one value per key
Question 21 dibuilder-required-flags · multi · 1 pt · 04-debug-info

Which module-level pieces must pebble-debugify (Algorithm 24.4.6) add for llc to emit DWARF
at all, rather than silently dropping the metadata? Choose all that apply.

  1. A DICompileUnit in the !llvm.dbg.cu named metadata
  2. The module flag Debug Info Version = 3
  3. A DIBuilder::finalize() call before the module is printed or compiled
  4. A DW_TAG_variable for every global, even when there are none
  5. The -g flag stored in !llvm.ident
Answer format: letters, e.g. a, c
Question 22 debugify-variable-count · number · 1 pt · 04-debug-info

A function has the entry-block allocas %count.addr, %sum.addr, %_3, %_4, and the named
SSA definitions %count.next, %count.addr.phi2, %x.addr.phi1, %_5. Applying
pebble-debugify's naming rule (Algorithm 24.4.6: name.addr... and name.suffix denote the
Pebble variable name; _N temporaries are skipped; one DILocalVariable per (function,
variable)), how many DILocalVariables does the pass create for this function?

Answer format: a number
Question 23 records-vs-intrinsics · single · 1 pt · 04-debug-info

Before LLVM 19, #dbg_value was the intrinsic call call void @llvm.dbg.value(...). What
problem did the record form (LLVM 19+) fix?

  1. Intrinsic calls could be optimized away by dead-code elimination, losing variable locations
  2. Intrinsic calls were instructions, so passes that count, scan or split on instructions behaved differently with -g than without, and the record form takes them out of the instruction list
  3. Intrinsic calls could not express DW_OP_stack_value, so values in registers were unlocatable
  4. Intrinsic calls did not carry a !dbg location, so the line table had gaps
Answer format: one letter
Question 24 find-dibuilder-finalize · text · 1 pt · 04-debug-info

Find it in LLVM: in llvm/lib/IR/DIBuilder.cpp (LLVM 23.1.2), DIBuilder::finalize (through
finalizeSubprogram) collects the variables and labels created for each DISubprogram into which
list of the subprogram?

Answer format: a short answer
Question 25 rc-trace-freed · mapping · 1 pt · 05-memory-management

Naive reference counting (Algorithm 24.5.3; the drill refcount-trace): every new reference
retains, every overwritten or scope-ending reference releases, an object is freed when its
count reaches 0. Objects are named O1, O2, ... in allocation order.

1: a = new Object()
2: b = a
3: a = new Object()
4: b = nil
5: c = a
6: c = new Object()
(end of scope: a, b, c released in name order)

For O1, O2 and O3, at which statement is the object freed? Write the statement number, or 0 for
"at the end of the scope".

Keys: O1, O2, O3
Answer format: one value per key
Question 26 rc-cycle · single · 1 pt · 05-memory-management

a = new Node(); b = new Node(); a.next = b; b.next = a; a = nil; b = nil. Under reference
counting, what happens to the two nodes?

  1. Both are freed when b = nil runs, since no variable references them
  2. Neither is freed: each holds a reference to the other, so both counts stay at 1
  3. The first is freed and the second leaks
  4. Both are freed at the end of the scope by the scope's releases
Answer format: one letter
Question 27 gc-roots-at-call · set · 1 pt · 05-memory-management

Straight-line code before a precise, moving collector (the drill gc-roots):

1: p1 = alloc()       ; base pointer
2: p2 = gep p1, 8     ; derived from p1
3: p3 = alloc()
4: x1 = load p3
5: call f1()          ; SAFEPOINT 1
6: store x1, p2
7: call f2()          ; SAFEPOINT 2
8: ret p1

Which pointer values must the stack map record as live at safepoint 1 (Definition 24.5.5)?

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 28 stackmap-pairs · single · 1 pt · 05-memory-management

Why does RewriteStatepointsForGC record every live pointer as a (base, derived) pair in the
statepoint rather than just the derived pointer?

  1. So that the collector can free the derived pointer's object separately from the base's
  2. Because a moving collector relocates objects, and a derived (interior) pointer must be adjusted by the same delta as the base it points into, which it can only find by knowing the base
  3. Because LLVM cannot represent interior pointers in stack maps
  4. To let the collector verify that the derived pointer is in bounds
Answer format: one letter
Question 29 borrow-error-kind · single · 1 pt · 05-memory-management
let mut v = vec![1, 2, 3];
let first = &v[0];
v.push(4);
println!("{first}");

Which check of the borrow checker (Algorithm 24.5.8) rejects this program, and with which error?

  1. The initialization check: v is used after being moved (E0382)
  2. The borrow-conflict check: v.push needs a mutable borrow of v while the shared borrow first is still live, because it is used afterwards (E0502)
  3. The drop check: first outlives v (E0597)
  4. No error: first is a copy of the integer
Answer format: one letter
Question 30 nll-last-use · single · 1 pt · 05-memory-management

Non-lexical lifetimes (rustc 2018+) make let r = &v; use(r); v.push(1); compile. What changed
relative to lexical lifetimes?

  1. A shared borrow may now coexist with a mutable one inside the same block
  2. A borrow is live only until its last use in the control-flow graph (a liveness computation on MIR), not until the end of its lexical scope, so r is dead when v.push runs
  3. push no longer takes &mut self
  4. The compiler inserts an implicit clone of v before the push
Answer format: one letter
Question 31 region-free-order · sequence · 1 pt · 05-memory-management

Region-based allocation (Definition 24.5.9; Tofte and Talpin): regions are nested and freed as a
whole when they end. letregion r1 { x = new(r1); letregion r2 { y = new(r2); z = new(r2) } w = new(r1) }. List the four objects in the order they are freed, listing objects of one region
in allocation order.

Answer format: items in order, e.g. A B C
Question 32 region-space-leak · single · 1 pt · 05-memory-management

In a pure region system, a loop that allocates a new value per iteration and keeps only the last
one puts every value into the same region (the loop's, or an enclosing one). What is the
consequence, and what did Tofte and Talpin's implementation add for it?

  1. The values are freed one per iteration by the region's reference count
  2. All iterations' values stay allocated until the region ends: a space leak proportional to the trip count; the ML Kit added storage-mode analysis so that a region can be reset at each iteration when nothing in it is live
  3. The region overflows and the program traps
  4. The compiler rejects the loop as ill-typed
Answer format: one letter
Question 33 find-elaborate-drops · text · 1 pt · 05-memory-management

Find it in rustc: in compiler/rustc_mir_transform/src/elaborate_drops.rs (rustc 1.94),
ElaborateDrops::run_pass runs which dataflow analysis (the one whose results decide whether a
drop is statically needed, statically unneeded, or needs a run-time drop flag)? Give the name
of the analysis struct for the "maybe initialized" direction.

Answer format: a short answer
Question 34 funclet-color-table · mapping · 1 pt · 06-exception-handling-survey

Funclet IR of Lesson 24.6's worked example, blocks named B1..B5:

B1: invoke @may_throw() to label B4 unwind label B2
B2: %cs = catchswitch within none [label B3] unwind label B5
B3: %cp = catchpad within %cs [...]          ... catchret from %cp to label B4
B4: %r = phi ...  ; call ~Guard ; ret
B5: %cl = cleanuppad within none []          ... cleanupret from %cl unwind to caller

Give each block's color (Algorithm 24.6.2): none (the function body), catch (the funclet
of %cp) or cleanup (the funclet of %cl).

Keys: B1, B2, B3, B4, B5
Answer format: one value per key
Question 35 unwind-map-states · mapping · 1 pt · 06-exception-handling-survey

In the MSVC tables Clang emitted for that function (Lesson 24.6 §7), state 0 is the cleanup
(~Guard), state 1 is the try body (TryLow = TryHigh = 1) and state 2 is the catch handler
(CatchHigh = 2). The $stateUnwindMap$ gives, for each state, the state it unwinds to
(-1 = the caller). Give ToState for states 0, 1 and 2.

Keys: 0, 1, 2
Answer format: one value per key
Question 36 wasm-try-structure · sequence · 1 pt · 06-exception-handling-survey

In the WebAssembly assembly Clang emitted for the same function (Lesson 24.6 §7), four
instructions realize the structure of Definition 24.6.4: catch (the catch __cpp_exception
of the handler), delegate (around __cxa_end_catch), catch_all (the cleanup), and
rethrow-to-caller (the cleanup's final rethrow). In which order do they appear in the
function, top to bottom?

Answer format: items in order, e.g. A B C
Question 37 wasm-personality-call · single · 1 pt · 06-exception-handling-survey

Why does WasmEHPrepare insert a call to _Unwind_CallPersonality (through the
__wasm_lpad_context global) into every C++ catch handler, when the Itanium model calls the
personality from libunwind?

  1. WebAssembly has no function pointers, so libunwind cannot call the personality
  2. The WebAssembly engine, not libunwind, unwinds the stack and lands in the catch; nothing has run the personality to select the matching clause, so the generated code must call it after landing and read the selector back
  3. The personality must run before the throw in WebAssembly, so it is called from the throwing code
  4. It is an optimization: calling the personality directly avoids the two-phase search
Answer format: one letter
Question 38 nounwind-marked-set · set · 1 pt · 06-exception-handling-survey

A module with an Itanium personality: leaf (arithmetic only, no calls); a invokes leaf
with a catch-all landing pad that returns -1; b invokes the external declaration may_throw
(no attributes) with a cleanup landing pad that ends in resume; c calls b; d invokes
may_throw with a catch-all landing pad that returns -1. After
opt -passes='cgscc(function-attrs)', which functions carry nounwind (Algorithm 24.6.7)?

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 39 invoke-to-call-witness · single · 1 pt · 06-exception-handling-survey

simplifycfg rewrote invoke i32 @leaf(i32 %x) to label %ok unwind label %lpad into
%r = call i32 @leaf(i32 %x); br label %ok and deleted %lpad. What single fact justifies the
rewrite (Proposition 24.6.9)?

  1. %lpad only returned a constant, so it could be folded
  2. leaf is nounwind: no execution of the call unwinds, so the two forms agree on every execution and the pad has no remaining predecessor
  3. The personality function is __gxx_personality_v0, which never runs landing pads for catch ptr null
  4. invoke and call are interchangeable when the callee is defined in the same module
Answer format: one letter
Question 40 find-instr-breaks-nonthrowing · text · 1 pt · 06-exception-handling-survey

Find it in LLVM: in llvm/lib/Transforms/IPO/FunctionAttrs.cpp (LLVM 23.1.2),
InstrBreaksNonThrowing calls I.mayThrow(...) with one boolean argument set to true. What is
that parameter's name?

Answer format: a short answer
Question 41 conversion-mode-outcome · mapping · 1 pt · 07-whats-next

A module holds func.func (no legality action set), arith.addi and arith.constant (the
arith dialect is marked Illegal; patterns to llvm.* exist), scf.for (no action, no
pattern) and llvm.fadd (llvm is Legal). After applyPartialConversion succeeds
(Definition 24.7.1, Algorithm 24.7.2), what happened to each of func.func, arith.addi,
scf.for, llvm.fadd: converted or kept?

Keys: func.func, arith.addi, scf.for, llvm.fadd
Answer format: one value per key
Question 42 legality-actions · mapping · 1 pt · 07-whats-next

Name the ConversionTarget legality action for each requirement, using the tokens Legal,
Dynamic, Illegal, Recursive:
(a) every arith.addi on 32-bit integers is legal, other widths are not;
(b) every operation of the llvm dialect is legal;
(c) no arith.constant may remain;
(d) whatever is nested inside a gpu.module is left alone, even arith operations.

Keys: a, b, c, d
Answer format: one value per key
Question 43 compcert-pass-kind · mapping · 1 pt · 07-whats-next

In CompCert's driver/Compiler.v (3.15), transf_rtl_program composes passes with @@ (a
total pass) or @@@ (a partial pass returning res, which may fail). Which operator precedes
each of Tailcall, Inlining, Renumber, CSE, Allocation? Write @@ or @@@.

Keys: Tailcall, Inlining, Renumber, CSE, Allocation
Answer format: one value per key
Question 44 fsim-measure-case · single · 1 pt · 07-whats-next

In fsim_properties (Definition 24.7.4), when the source takes one step, the target may take
zero steps. What additional condition does the record require in that case, and why?

  1. The trace of the source step must be empty and the index must decrease in a well-founded order, so that the target cannot stutter forever while the source runs
  2. The target must have already terminated
  3. The source step must be an external call, whose trace the target replays later
  4. Nothing more: any number of target steps, including zero, is allowed unconditionally
Answer format: one letter
Question 45 alive-verdict-meaning · single · 1 pt · 07-whats-next

alive-tv --func=f --disable-undef-input before.ll after.ll prints "Transformation seems to be
correct!". What has been established (Proposition 24.7.6)?

  1. That after.ll's f computes the same value as before.ll's on every input, including inputs that trigger undefined behavior in the source
  2. That on every input, and for the unrolling bound and memory model used, every behavior of the target f is a behavior of the source f, or the source has undefined behavior on that input — refinement, not equivalence
  3. That the pass that produced after.ll is correct on all programs
  4. That the two functions are syntactically equal after canonicalization
Answer format: one letter
Question 46 alive-false-alarm · single · 1 pt · 07-whats-next

After pebble-o1 (which inlines), validating pebble_main reports "Source is more defined than
target" with i64 %#0 = function did not return! and no input values. What is going on
(Algorithm 24.7.5 step 4)?

  1. The inliner miscompiled f; the fuzzer would find the same bug
  2. The source still calls f, whose body Alive2 does not inline, so the call is an unknown function that may not return, while the target computed the value; the verdict is an artifact of the tool's assumption about unknown calls, not a miscompilation
  3. pebble_main has undefined behavior because f is internal
  4. The two modules have different target triples
Answer format: one letter
Question 47 find-operation-legalizer · text · 1 pt · 07-whats-next

Find it in MLIR: in mlir/lib/Transforms/Utils/DialectConversion.cpp (LLVM 23.1.2),
OperationLegalizer::legalize finds that an operation is recursively legal. Into which set of
the rewriter's implementation does it put the operations nested inside it, so that they are
skipped?

Answer format: a short answer