Theory test — Chapter 11¶
51 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 11 # interactive
./course quiz template 11 -o answers/ch11.yaml # or fill in a file ...
./course quiz grade 11 # ... and grade it
sdt-temporaries · mapping · 1 pt · 01-ssa-generation-strategiesThe reference lowering (spec §15) compiles let x = a * (b + 1); (all int) in a function
with parameters a, b. The final result is assigned straight to x (destination-driven).
How many unnamed temporaries does it create, and how many assert statements?
temporaries, assertsmem2reg-phi-blocks · set · 1 pt · 01-ssa-generation-strategiesA front end lowered a loop by syntax-directed translation with one alloca for x:
B0: store 0 -> x; br H
H: br (i < n), Body, X
Body: br c, T, E
T: x = x + 1 (load, add, store); br J
E: br J
J: br H
X: use x
x is stored in B0 and T. In which blocks does mem2reg place a phi for x (pruned SSA:
iterated dominance frontier, restricted to blocks where x is live on entry)?
llvm-where-mem2reg-livein · text · 1 pt · 01-ssa-generation-strategiesIn llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp (LLVM 23.1.2), which function computes
the blocks where an alloca is live on entry, so that PromoteMem2Reg::run places only pruned
phis? Give the function name.
braun-trivial-phi · single · 1 pt · 01-ssa-generation-strategiesDuring on-the-fly SSA construction a loop header gets %p = phi [%a, %entry], [%p, %latch]
when it is sealed. What happens to it (Algorithm 11.1.9)?
- It stays: a phi in a loop header is never trivial
- It is replaced by %a, because its only operand other than itself is %a
- It is replaced by poison, because one operand is the phi itself
- It becomes an incomplete phi until the latch is sealed
braun-phi-count · mapping · 1 pt · 01-ssa-generation-strategiesBraun et al.'s construction (Algorithm 11.1.9) generates var i = 0; while i < n { i = i + 1; }
where n is a parameter. The header is still unsealed when its condition reads i and n.
How many phis are created in the header, and how many remain after sealing and
trivial-phi removal?
created, remainingjc-targets · mapping · 1 pt · 02-short-circuit-loweringif (p || q) && !(r && s) { T } else { F } is compiled with jumping code (Algorithm 11.2.2;
each atom is one comparison and one conditional branch; a subexpression's block is named
after its first atom). Give each atom's true target and false target (an atom or T/F).
p-true, p-false, q-true, q-false, r-true, r-false, s-true, s-falsejc-blocks-edges · mapping · 1 pt · 02-short-circuit-loweringFor the jumping code of (p || q) && !(r && s), how many basic blocks (entry and the T and F
blocks included, no join) and how many CFG edges does it have?
blocks, edgesbool-values-legal · multi · 1 pt · 02-short-circuit-loweringWhich conditions may be compiled with the boolean-value strategy (evaluate every operand, combine
with and/or) without changing a Pebble program's behavior? (a: [int; 4], f prints.)
- i < 4 && a[i] > 0
- x > 0 && y < 10
- d != 0 && n / d > 1
- done || f() > 0
- !(u == v) || w >= 3
bool-values-ops · mapping · 1 pt · 02-short-circuit-lowering(p && (q || !r)) || s is compiled with the boolean-value strategy (Algorithm 11.2.6), one
instruction per operator node. How many icmp, and, or and not (xor) instructions?
icmp, and, or, notllvm-where-fold-branch · text · 1 pt · 02-short-circuit-loweringIn llvm/lib/Transforms/Utils/SimplifyCFG.cpp, which function folds a conditional branch into a
predecessor that branches to a common destination, turning jumping code into an or/and of
the conditions (the %or.cond of Lesson 11.2)?
jt-density · number · 1 pt · 03-switch-loweringA switch on x has eight cases 1, 2, 3, 5, 8, 13, 21, 34, each to a different destination.
LLVM (-O2, density threshold 10 %) lowers it as one jump table. How many entries does the
table have?
jt-range-check · single · 1 pt · 03-switch-loweringA jump table covers values min … max. Which single check sends every other value of x (signed
i64) to the default?
- icmp sgt x, max
- icmp ugt (sub x, min), (max − min)
- icmp slt x, min and icmp sgt x, max, both needed
- icmp ugt x, max
bst-depth · number · 1 pt · 03-switch-loweringA sparse switch with 13 cases is lowered as a balanced binary search over the sorted values
(Algorithm 11.3.4). By Theorem 11.3.5, at most how many comparisons execute on any path?
bst-signed · single · 1 pt · 03-switch-loweringA switch on a signed i64 has cases −5, −1, 3 and 7. The tree first compares with the median
pivot 3 (x < 3 goes left). Which comparison is correct?
- icmp ult x, 3
- icmp slt x, 3
- either: the case values are sorted
- icmp ule x, 3
bits-mask · mapping · 1 pt · 03-switch-loweringLLVM lowers switch x { 1, 3, 5 → A; 2, 6 → B; default → D } with bit tests. Because 0 < min
and max < 64, it skips the subtraction (LowBound = 0, Lesson 11.3 §6) and tests 1 << x.
Give the two masks in decimal.
A, Bbits-suitable · multi · 1 pt · 03-switch-loweringWhich of these switches does LLVM at -O2 lower (entirely) as one bit-test cluster?
- 1, 2, 3 → A
- 0, 10, 20 → A; 30, 40 → B
- 0, 100 → A; 200 → B
- 0 → A; 1 → B; 2 → C; 3 → D; 5 → A; 7 → B
llvm-switch-clusters · mapping · 1 pt · 03-switch-loweringLLVM lowers the switch with cases 0, 1 → A; 2, 3 → B; 5 → C; 100 → A; 101 → B; 102 → C;
103 → A; 1000 → B (Algorithm 11.3.7: rangeify, jump-table dynamic program with at least 4
clusters per table, bit tests). How many clusters does the final partition have, and how many
of them are jump tables and bit-test clusters?
clusters, tables, bitsllvm-where-jt-vs-bits · text · 1 pt · 03-switch-loweringIn llvm/lib/CodeGen/SwitchLoweringUtils.cpp, which SwitchLowering member function refuses to
build a jump table for a range that bit tests could handle? (It asks
TargetLowering::isSuitableForBitTests.)
lvalue-order · mapping · 1 pt · 04-places-values-and-loopsfn bump(k: &mut int) -> int { k = k + 1; return k; }
...
var xs = [0, 0, 0, 0];
var k = 2;
xs[k] = bump(&mut k) * 10;
After the assignment, what are xs[2], xs[3] and k?
xs2, xs3, klvalue-copies · mapping · 1 pt · 04-places-values-and-loopsWith bump as above and var x = 5;, the reference lowering compiles print(x + bump(&mut x) + x);.
How many times does it copy x into a temporary before the call (materialization,
Definition 11.4.2), and what does it print?
copies, printsrotate-branch-count · mapping · 1 pt · 04-places-values-and-loopsA loop runs n = 5 iterations. Count the conditional branches and unconditional jumps executed by
the loop's control flow in the top-tested form and in the rotated form (Theorem 11.4.8).
top-condbr, top-jumps, rotated-condbr, rotated-jumpsrotate-preheader · single · 1 pt · 04-places-values-and-loopsWhy does loop rotation copy the test in front of the loop (the guard) instead of just moving it
to the bottom?
- To give the loop a preheader for LICM, the copy itself is optional
- Because a do-while runs the body at least once, and the original loop may run zero times
- Because LLVM requires every loop to have two exits
- To keep the loop in LCSSA form
llvm-where-rotate-limit · mapping · 1 pt · 04-places-values-and-loopsIn llvm/lib/Transforms/Scalar/LoopRotation.cpp (LLVM 23.1.2), what is the command-line option
that bounds the size of a header loop-rotate will duplicate, and its default?
option, defaultabi-direct-rust · single · 1 pt · 05-aggregates-and-the-abirustc compiles fn mixed(m: Mixed) -> Mixed for struct Mixed { a: i32, b: f64 } with the Rust
ABI (Lesson 11.5 box). How is m passed?
- As a pointer to a caller copy
- byval, on the stack
- As its two fields directly,
double %0, i32 %1(reordered, double first) - Coerced to { i32, double } like Clang
abi-direct-regs · mapping · 1 pt · 05-aggregates-and-the-abiContinuing abi-direct-rust on x86-64: which registers carry the two scalar arguments
double %0, i32 %1, and which registers carry the returned { double, i32 }?
arg-double, arg-int, ret-double, ret-intsret-noalias · single · 1 pt · 05-aggregates-and-the-abiPebble's code generator marks the hidden result pointer ptr noalias sret(%Pair). Why is
noalias correct?
- Because Pebble has no pointers
- Because the caller always passes fresh storage (%call.result) and copies it to the destination after the call, so nothing else the callee can reach points to it
- Because LLVM requires noalias on every sret parameter
- Because the callee never reads its parameters
sret-steps · sequence · 1 pt · 05-aggregates-and-the-abiOrder the caller's and callee's steps for q = swap(p) with p, q: Pair under Pebble's
convention (Algorithm 11.5.2). Steps: copy-arg (memcpy p into a temporary),
call (call swap with %call.result and the temporary), callee-writes (swap writes its result
through the sret pointer), copy-result (memcpy %call.result into q).
byval-vs-copy · single · 1 pt · 05-aggregates-and-the-abiWhat is the difference between passing ptr byval(%T) and passing a plain ptr to a caller-made
copy?
- None: both are lowered identically
- With byval the call sequence makes the copy in the argument area (stack), invisible to IR optimizations; with a caller copy it is an ordinary alloca + memcpy the optimizer can remove
- byval passes the value in registers, the caller copy on the stack
- byval is only for results, caller copies for arguments
byval-aarch64 · mapping · 1 pt · 05-aggregates-and-the-abiClang compiles void take(struct Big b) with struct Big { long a, b, c; } (24 bytes). How is
the parameter passed on x86-64 and on AArch64 (AAPCS64)? Answer byval or pointer-to-copy.
x86-64, aarch64abi-classify-mixed · mapping · 1 pt · 05-aggregates-and-the-abiClassify struct S { float a; int b; double c; }; (16 bytes) under the System V x86-64 ABI
(Algorithm 11.5.4) and give Clang's coerced type for passing it (write the type without spaces
inside braces, e.g. {i32,double}).
eightbyte0, eightbyte1, coercedclang-where-integer-coerce · text · 1 pt · 05-aggregates-and-the-abiIn clang/lib/CodeGen/Targets/X86.cpp, which X86_64ABIInfo function chooses i32 rather than
i64 for an INTEGER eightbyte that holds only an int?
trap-assume · single · 1 pt · 06-safety-checksPIR o = saddo a, b; assert !o, overflow; r = add a, b is compiled with a trap block calling
pebble_trap (noreturn nounwind). What may LLVM assume about r in code after the check?
- Nothing: the add wraps
- That a + b did not overflow, because every path to that code took the Ok edge (Lemma 11.6.4)
- Only that r is not poison
- That r ≥ a
swift-where-cond-fail · text · 1 pt · 06-safety-checksIn Swift's lib/IRGen/IRGenSIL.cpp (swift-6.1-RELEASE), which IRGenSILFunction method lowers the
SIL instruction behind every Swift overflow and bounds trap?
unwind-invoke · single · 1 pt · 06-safety-checksUnder Rust's default panic=unwind, when does a call to a function that may panic become an
invoke in the caller's LLVM IR?
- Always
- When the caller has a cleanup (e.g. a value with a destructor) live across the call, or a catch
- Only when the callee is in another crate
- Never: panics use setjmp/longjmp
unwind-abort · single · 1 pt · 06-safety-checksWhat changes when the same Rust program is compiled with -C panic=abort?
- Overflow checks are removed
- Panics abort the process: no landing pads or cleanup code are emitted, and calls need not be invokes
- Panics become error returns
- Nothing observable
error-return-cost · number · 1 pt · 06-safety-checksRust's a.checked_add(b) compiles to llvm.sadd.with.overflow and returns Option<i64> as
{ i64, i64 } (tag = zext (not f), payload = the sum). How many conditional branches does the
callee (checked_add itself, inlined or not) execute?
error-return-branch · single · 1 pt · 06-safety-checksUnder the error-return policy, a function three calls deep fails, and every level propagates the
error with ?. What does the program execute on the way back?
- An unwinder walks three frames using tables
- A longjmp to the outermost handler
- An ordinary return and one tag test + branch at each of the three levels
- Nothing: the failure is ignored
eh-callsite-lookup · mapping · 1 pt · 07-exception-handlingA function's call-site table (offsets from the function start; ranges are half-open):
| range | landing pad |
|---|---|
| [0x10, 0x18) | L1 |
| [0x18, 0x30) | none |
| [0x30, 0x38) | L2 |
An exception passes through this frame. For each return address, where does the unwinder go
next: L1, L2, or caller (keep unwinding into the caller)?
0x14, 0x22, 0x34llvm-where-callsite-table · text · 1 pt · 07-exception-handlingIn llvm/lib/CodeGen/AsmPrinter/EHStreamer.cpp, which function builds the list of call-site
entries, including the "no landing pad" gaps, from the EH_LABELs around each invoke?
sjlj-site-index · mapping · 1 pt · 07-exception-handlingLesson 11.7's safe (an invoke @parse whose handler calls log through a second invoke) is
compiled with llc -exception-model=sjlj. Which call-site index is stored into the function
context before the call to parse, and before the call to log?
parse, logsjlj-cost · single · 1 pt · 07-exception-handlingWhy is SjLj exception handling not "zero-cost"?
- The unwinder must decode DWARF CFI
- Every call of a function with handlers registers and unregisters a context (two runtime calls) and stores a call-site index before each invoke, even if nothing throws
- Throwing is slower than with tables
- It needs a garbage collector
swifterror-register · mapping · 1 pt · 07-exception-handlingSwift returns errors in a register reserved by its calling convention (swifterror in LLVM IR).
Which register on x86-64 and which on AArch64?
x86-64, aarch64errors-cost-depth · mapping · 1 pt · 07-exception-handlingA recursion of depth d = 6 (six frames, each with a handler or error check) returns normally,
with nothing thrown. How many extra runtime calls does SjLj EH execute, how many extra error
tests do explicit error returns execute, and how many extra instructions do zero-cost tables
execute?
sjlj-calls, error-tests, tablescc-free-vars · set · 1 pt · 08-closure-conversionfn outer(a, b, c) {
let d = a + 1
let g = fun x -> x + d + b // a function value
return apply(g, c)
}
What is FV(fun x -> x + d + b) (Definition 11.8.1)?
cc-env-field · mapping · 1 pt · 08-closure-conversionClosure conversion (Algorithm 11.8.2) turns the lambda of cc-free-vars into the record
MakeRecord(code, [captures in sorted order]), with the code pointer in field 0. In which field
is each captured variable?
b, dll-fixpoint · mapping · 1 pt · 08-closure-conversionLocal non-escaping functions of outer(a, b, c):
fn f(x) = x + a + h(x - 1)
fn g(y) = f(y) * b
fn h(z) = z * c
Give each function's extra parameters E after Algorithm 11.8.4's fixed point.
f, g, hgo-where-direct-closure · text · 1 pt · 08-closure-conversionIn Go's src/cmd/compile/internal/walk/closure.go (go1.24.7), which function rewrites a directly
called function literal into a plain call with the captured variables as extra leading
arguments?
rt-libcall-choice · mapping · 1 pt · 09-runtime-and-linkingclang 23 at -O2 on x86-64 Linux: which operations become inline instructions (inline) and
which become calls to a runtime or library function (call)?
long * long, long / long, __int128 * __int128, __int128 / __int128, fmod(double, double)llvm-where-libcall · text · 1 pt · 09-runtime-and-linkingIn llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp, which DAGTypeLegalizer function
expands a too-wide signed division into the __divti3 libcall?
link-archive-order · single · 1 pt · 09-runtime-and-linkingOn Linux, cc -o hello libpebble_runtime.a hello.o -lm fails with "undefined reference to
pebble_print_str", while cc -o hello hello.o libpebble_runtime.a -lm works. Why?
- The archive is corrupt
- GNU ld searches an archive once, when it reaches it, and links only members that define symbols undefined at that point. Before hello.o nothing is undefined, so no member is pulled
- hello.o must always be the first argument
- -lm must come first
llvm-where-emit-file · text · 1 pt · 09-runtime-and-linkingIn llvm/lib/CodeGen/CodeGenTargetMachineImpl.cpp, after adding the code-generation passes,
which function does addPassesToEmitFile call to attach the AsmPrinter with the object writer?