Theory test — Chapter 22

53 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 22                                   # interactive
./course quiz template 22 -o answers/ch22.yaml  # or fill in a file ...
./course quiz grade 22                             # ... and grade it

Question 1 interference-edges · set · 1 pt · 01-the-problem

The running example of Lesson 22.1 (a phi operand from P is used at the end of P):

B0: a = arg
    jmp B1
B1: i = phi B0:0 B2:i2
    s = phi B0:a B2:s2
    c = lt i 10
    br c B2 B3
B2: t = mul s i
    u = add t a
    s2 = xor u i
    i2 = add i 1
    jmp B1
B3: r = add s a
    ret r

Which values interfere with s (Definition 22.1.5)?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 2 dead-def-interferes · single · 1 pt · 01-the-problem

In x = add y z the value x is never used. Which statement is true under Definition
22.1.5?

1. x interferes with nothing, because it is never live
2. x interferes with every value live just after the instruction, because the instruction still writes its register
3. x interferes with y and z only
4. x interferes with every value in the function

Answer format: one letter

Question 3 subreg-alias · single · 1 pt · 01-the-problem

On x86-64, eax is the low half of rax. How does LLVM decide that a value in eax and a
value in rax conflict?

1. They are in the same register class
2. They share a register unit (TargetRegisterInfo::regunits), and interference is checked per unit
3. The coalescer merges them before allocation
4. They never conflict: sub-registers are allocated separately

Answer format: one letter

Question 4 maxlive-classes · mapping · 1 pt · 01-the-problem

Values are either i64 (class GPR) or f64 (class FPR):

a:i64 = arg
b:f64 = arg
c:f64 = fmul b b
d:i64 = add a a
e:f64 = fadd c b
f:i64 = fptosi e
g:i64 = add f d
ret g

Give MaxLive per class (Definition 22.1.7, over the definition points of Definition 22.1.4).

Keys: GPR, FPR

Answer format: one value per key

Question 5 caller-saved-crossing · set · 1 pt · 01-the-problem

B0: x = arg
    y = arg
    z = mul x y
    w = add x 1
    call z
    v = add w y
    ret v

call z clobbers the caller-saved registers. Which values must be spilled or placed in a
callee-saved register (SPEC R4: live across the call and not defined by it)?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 6 regmask-meaning · single · 1 pt · 01-the-problem

What does a register-mask operand on a call in LLVM MIR express?

1. The registers the callee reads as arguments
2. The registers preserved by the call; every other register is clobbered
3. The registers the allocator may not use anywhere in the function
4. The registers that hold the return value

Answer format: one letter

Question 7 belady-trace · sequence · 1 pt · 02-local-allocation

Reference string c a b d c b a d c a, K = 2 registers, initially empty. Apply Belady's
MIN (evict the value used furthest in the future; never again = infinitely far). Give the
evicted values in order.

Answer format: items in order, e.g. A B C

Question 8 belady-loads · number · 1 pt · 02-local-allocation

Same string c a b d c b a d c a, K = 2. How many loads (misses) does MIN need?

Answer format: a number

Question 9 fast-backward · text · 1 pt · 02-local-allocation

Find it in LLVM: in llvm/lib/CodeGen/RegAllocFast.cpp (llvmorg-23.1.2), which member
function of RegAllocFastImpl allocates one basic block, walking it backwards?

Answer format: a short answer

Question 10 fast-spill-cost · number · 1 pt · 02-local-allocation

In the lab, ch22-regalloc running.ll --function=run --method=local --gpr=3 --metrics
reports the weighted spill cost of local allocation on the running example
(loads and stores weighted by 10^loop depth). What is it?

Answer format: a number

Question 11 chaitin-simplify-order · sequence · 1 pt · 03-graph-coloring

The running example's interference graph (Lesson 22.1): edges a–c, a–i, a–i2, a–s, a–s2,
a–t, a–u, c–i, c–s, i–s, i–s2, i–t, i–u, i2–s2; r is isolated. With k = 4, simplify by
repeatedly removing the alphabetically first node of degree < 4 (order: a < c < i < i2
< r < s < s2 < t < u). Give the removal order.

Answer format: items in order, e.g. A B C

Question 12 chaitin-spill-choice · text · 1 pt · 03-graph-coloring

Same graph with k = 3 and spill costs a 13, i 50, s 21, c/t/u/s2/i2 20, r 2. When
simplification is stuck, Chaitin spills the node with the smallest cost/degree. Which
value is spilled?

Answer format: a short answer

Question 13 simplify-lemma · single · 1 pt · 03-graph-coloring

Why may a node of degree < k be removed during simplification?

1. Because it cannot interfere with a spilled node
2. Because whatever colours its fewer than k neighbours get, one of the k colours is left for it
3. Because nodes of low degree are always cheap to spill
4. Because the graph is chordal

Answer format: one letter

Question 14 briggs-square · mapping · 1 pt · 03-graph-coloring

The square a–b–c–d–a with k = 2. How many values does each allocator actually spill?

Keys: Chaitin, Briggs

Answer format: one value per key

Question 15 briggs-never-worse · single · 1 pt · 03-graph-coloring

Why does optimistic colouring never spill more values than Chaitin's allocator on the same graph and costs?

1. It uses a better spill metric
2. It simplifies in the same order and only postpones the spill decision to select, where a potential spill may still find a colour
3. It coalesces more moves
4. It colours in dominance order

Answer format: one letter

Question 16 aggressive-harm · single · 1 pt · 04-coalescing

What can go wrong when two non-interfering move-related nodes are merged without a test?

1. The program computes a different result
2. The merged node may have k or more significant neighbours, so a k-colourable graph can become uncolourable and values get spilled
3. The copy is executed twice
4. Nothing; merging only removes edges

Answer format: one letter

Question 17 aggressive-llvm · single · 1 pt · 04-coalescing

LLVM's RegisterCoalescer coalesces aggressively before allocation. What keeps this from
causing many spills?

1. It uses the George test
2. Greedy's live-range splitting can split a merged interval again where pressure is high
3. It only coalesces copies inside loops
4. RegAllocFast runs afterwards

Answer format: one letter

Question 18 briggs-verdict · mapping · 1 pt · 04-coalescing

Running-example graph (edges as in chaitin-simplify-order). Does the Briggs test
(Definition 22.4.3: the merged node has fewer than k neighbours of degree ≥ k) accept the
move pairs below? Answer yes or no, for k = 3 and for k = 4.

Keys: i-i2/k3, s-s2/k3, i-i2/k4, s-s2/k4

Answer format: one value per key

Question 19 george-verdict · mapping · 1 pt · 04-coalescing

Same graph, k = 3. The George test merges x into y if every neighbour of x interferes with
y or has degree < k (Definition 22.4.5). Answer yes or no.

Keys: i2 into i, i into i2, s2 into s, s into s2

Answer format: one value per key

Question 20 irc-freeze · single · 1 pt · 04-coalescing

What does the freeze step of iterated register coalescing do?

1. Spills a move-related node
2. Gives up coalescing the moves of a low-degree move-related node, so it can be simplified
3. Merges all remaining moves aggressively
4. Fixes the colours of pre-coloured nodes

Answer format: one letter

Question 21 irc-moves-k4 · mapping · 1 pt · 04-coalescing

Run IRC on the running example with k = 4 (moves: i–i2 and s–s2 from the back-edge phis,
s–a from the entry edge). How does each move end: coalesced, constrained or frozen?

Keys: i-i2, s-s2, s-a

Answer format: one value per key

Question 22 ls-spill-running · text · 1 pt · 05-linear-scan

Poletto–Sarkar on the running example's hulls a [1,20], i [5,16], s [5,20], c [7,8],
t [11,12], u [13,14], s2 [15,19], i2 [17,19], r [21,22] with K = 3. Intervals with the same
start are handled alphabetically, and when several intervals end furthest, the
alphabetically last one is spilled. Which value is spilled?

Answer format: a short answer

Question 23 ls-no-spill-depth · number · 1 pt · 05-linear-scan

With the same hulls, what is the smallest K for which Poletto–Sarkar spills nothing?

Answer format: a number

Question 24 ls-hull-false-conflict · single · 1 pt · 05-linear-scan

A value x is live in [2, 6] and [30, 34] (a hole in between); y is live in [10, 20].
What does hull-based linear scan conclude, and which technique avoids it?

1. No conflict; nothing to avoid
2. A false conflict (hull [2, 34] contains [10, 20]); binpacking into lifetime holes (Traub et al.) lets y use x's register
3. A real conflict, so y must be spilled
4. A conflict that only coalescing can remove

Answer format: one letter

Question 25 second-chance-meaning · single · 1 pt · 05-linear-scan

In second-chance binpacking, what is the "second chance"?

1. A spilled value is reloaded into a register at its next use and may stay there, instead of living in memory for the rest of its life
2. The allocator runs twice
3. Every interval is tried with two registers
4. A value that fails colouring is retried with linear scan

Answer format: one letter

Question 26 wm-free-until · mapping · 1 pt · 05-linear-scan

Wimmer–Mössenböck TryAllocateFreeReg for the interval current = [10, 25] (no holes),
with freeUntil r0 = 12, r1 = 20, r2 = 8. Which register does it take, and before which
position is it split?

Keys: register, split

Answer format: one value per key

Question 27 wm-blocked-choice · single · 1 pt · 05-linear-scan

In AllocateBlockedReg (Wimmer–Mössenböck), which register is chosen when all are occupied?

1. The register whose occupant has the lowest spill cost
2. The register whose next use (by the intervals holding it) is furthest away
3. The register with the lowest number
4. A callee-saved register

Answer format: one letter

Question 28 wf-loop-extension · single · 1 pt · 05-linear-scan

In Wimmer–Franz's one-pass interval building on SSA, what happens to a value that is live
at the start of a loop header when the header is processed?

1. Its range is extended over the whole contiguous loop, up to the loop's last block
2. It is spilled
3. The loop is processed a second time
4. It is split at the loop header

Answer format: one letter

Question 29 wf-order · single · 1 pt · 05-linear-scan

Which block order does Wimmer–Franz interval building require?

1. Any order
2. Every block after its dominator, and the blocks of each loop contiguous
3. Postorder
4. Blocks sorted by frequency

Answer format: one letter

Question 30 ssa-chordal-why · single · 1 pt · 06-ssa-based-allocation

Why is the interference graph of a strict SSA program chordal?

1. Because SSA programs have no loops
2. Because interfering values are ordered by dominance of their definitions, and the reversed dominance order of definitions is a perfect elimination order
3. Because phis are removed before allocation
4. Because every value has one use

Answer format: one letter

Question 31 ssa-color-trace · mapping · 1 pt · 06-ssa-based-allocation

Colour the running example (program in interference-edges) with Algorithm 22.6.6 and
K = 4: blocks in dominator-tree preorder B0, B1, B2, B3; at block entry live-in colours are
taken; phis then each result get the lowest free colour, after releasing the colours of
operands used for the last time at that instruction. Give every value's colour.

Keys: a, i, s, c, t, u, s2, i2, r

Answer format: one value per key

Question 32 decoupled-spill-choice · single · 1 pt · 06-ssa-based-allocation

What does "decoupled" mean in SSA-based allocation?

1. Spilling and coalescing run on different threads
2. Spilling first reduces the pressure to at most K at every point; colouring then never spills (Theorem 22.6.7)
3. Each class is allocated separately
4. Spill code is placed after colouring

Answer format: one letter

Question 33 maxlive-after-spill · set · 1 pt · 06-ssa-based-allocation

The running example has MaxLive 4. Spilling which single value (spill-everywhere, reloads
through a scratch register outside the K) brings MaxLive down to 3?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 34 phi-permutation · number · 1 pt · 06-ssa-based-allocation

After SSA colouring, the phis of a block require the parallel copy (r0, r1, r2) ← (r1, r2,
r0) on an edge. With one free scratch register, how many moves are needed?

Answer format: a number

Question 35 ssa-input-allocator · single · 1 pt · 06-ssa-based-allocation

Which production allocator takes SSA with block parameters as input and emits the phi (block-parameter) moves itself?

1. LLVM's greedy allocator
2. Cranelift's regalloc2
3. GCC's IRA
4. HotSpot C2

Answer format: one letter

Question 36 pbqp-rii-cost · mapping · 1 pt · 07-pbqp-and-ilp

PBQP with two choices per node (0, 1). Node u has cost vector (1, 3) and exactly two
neighbours v and w with C_uv = [[∞, 0], [0, ∞]] (u and v interfere) and
C_uw = [[0, 2], [2, 0]] (a copy costing 2 if u and w differ). RII removes u and adds to the
v–w matrix Δ(j, k) = min over i of c_u(i) + C_uv(i, j) + C_uw(i, k). Give Δ.

Keys: v0-w0, v0-w1, v1-w0, v1-w1

Answer format: one value per key

Question 37 pbqp-ri-exact · single · 1 pt · 07-pbqp-and-ilp

Why is the RI reduction (a node of degree 1) exact?

1. Because degree-1 nodes are always spilled
2. Because the node's best choice depends only on its neighbour's choice, so folding min over its choices into the neighbour's vector loses nothing
3. Because the solver backtracks
4. Because the graph is chordal

Answer format: one letter

Question 38 ilp-constraint · single · 1 pt · 07-pbqp-and-ilp

In the 0-1 ILP of Definition 22.7.6, which constraint forbids two interfering values u, v in the same register r?

1. x_{u,r} + x_{v,r} ≤ 1
2. x_{u,r} = x_{v,r}
3. s_u + s_v ≥ 1
4. d_{uv} ≥ x_{u,r} − x_{v,r}

Answer format: one letter

Question 39 ilp-objective-running · number · 1 pt · 07-pbqp-and-ilp

The ILP of Definition 22.7.6 for the running example with K = 3: spill costs from Lesson
22.3 (a 13, i 50, s 21, others 20, r 2), affinities i–i2 and s–s2 with weight 10 and s–a
with weight 1. What is the optimal objective value HiGHS reports?

Answer format: a number

Question 40 appel-george-split · single · 1 pt · 07-pbqp-and-ilp

How do Appel and George make optimal spilling practical?

1. They solve colouring by ILP and spill heuristically
2. They decide optimally by ILP where each value is in a register or in memory (at most K in registers at each point), then assign registers by coalescing heuristics
3. They use PBQP
4. They restrict the problem to straight-line code

Answer format: one letter

Question 41 greedy-stage-order · sequence · 1 pt · 08-llvm-greedy

Order the live-range stages of LLVM's greedy allocator (LiveRangeStage) from first to
last: RS_Spill, RS_New, RS_Split2, RS_Done, RS_Assign, RS_Split.

Answer format: items in order, e.g. A B C

Question 42 greedy-cascade · single · 1 pt · 08-llvm-greedy

Interval A (cascade 3, weight 8) wants a register held by B (cascade 3, weight 5). May A evict B?

1. Yes, because A's weight is higher
2. No: an interval may only evict intervals with a strictly lower cascade
3. Yes, if B is a spill product
4. Only at -O0

Answer format: one letter

Question 43 find-evict-advisor · text · 1 pt · 08-llvm-greedy

Find it in LLVM: which source file in llvm/lib/CodeGen/ (llvmorg-23.1.2) defines
DefaultEvictionAdvisor::canEvictInterferenceBasedOnCost, the rule of Definition 22.8.1?

Answer format: a short answer

Question 44 split-kinds · single · 1 pt · 08-llvm-greedy

For a global live range (spanning several blocks) in stage RS_Split, which split does greedy try first?

1. Instruction split
2. Region split, using SpillPlacement over edge bundles
3. Local split
4. Spill everywhere

Answer format: one letter

Question 45 find-spill-placement · text · 1 pt · 08-llvm-greedy

Find it in LLVM: which source file in llvm/lib/CodeGen/ implements the Hopfield-network
analysis that greedy's region splitting uses to decide in which edge bundles a value
should be in a register?

Answer format: a short answer

Question 46 rewriter-identity · single · 1 pt · 08-llvm-greedy

After allocation, $rax = COPY $rax appears. What does VirtRegRewriter do with it?

1. Keeps it for debugging
2. Deletes it (or turns it into a KILL when it carries extra liveness information)
3. Turns it into a spill
4. Asks the allocator to reassign

Answer format: one letter

Question 47 mcp-forward · single · 1 pt · 08-llvm-greedy

After allocation, $rcx = COPY $rax is followed by $rdx = ADD64rr $rdx, $rcx and $rcx
is dead afterwards; $rax is not redefined in between. What can MachineCopyPropagation do?

1. Nothing: copies are never touched after allocation
2. Forward $rax into the ADD's operand and delete the now dead copy
3. Replace the ADD by a copy
4. Move the copy before the previous definition of $rax

Answer format: one letter

Question 48 spill-weight-running · number · 1 pt · 09-spilling-and-rematerialization

In the running example with f(B) = 10^loop depth, s has UD = 21 and live segments of
total length 5 slots (two slots per instruction, so 25 instructions = 50 slots). Compute
w(s) = UD / (|s| + 50) to three decimals (Definition 22.9.1, α = 1).

Answer format: a number (±0.001)

Question 49 loop-frequency · number · 1 pt · 09-spilling-and-rematerialization

A loop is entered from the function entry with probability 3/4, and its back edge is taken
with probability 7/8. What is the relative frequency f(B) of the loop body (per execution of
the entry block)?

Answer format: a number

Question 50 remat-when · multi · 1 pt · 09-spilling-and-rematerialization

A spilled value x has a use at point p. In which cases may x be recomputed at p
instead of reloaded (Definition 22.9.4, Theorem 22.9.6)?

1. x = const 42
2. x = add y 4, and y is live at p with the same value it had at x's definition
3. x = load q from memory that a store may modify between x's definition and p
4. x = call rand
5. x = lea @global

Answer format: letters, e.g. a, c

Question 51 find-remat · text · 1 pt · 09-spilling-and-rematerialization

Find it in LLVM: which member function of InlineSpiller (llvm/lib/CodeGen/InlineSpiller.cpp,
llvmorg-23.1.2) tries to rematerialize a spilled value before one instruction instead of
reloading it?

Answer format: a short answer

Question 52 hoist-dp · set · 1 pt · 09-spilling-and-rematerialization

Dominator tree (block: frequency): r: 1 with children X: 0.8 and Y: 0.2; X has children
X1: 0.3, X2: 0.5, X3: 0.1. The spilled value is defined in r and the initial stores are in
X1, X2 and Y; every block is a candidate. Run Algorithm 22.9.9 with LLVM's margin μ = 0.9
(hoist into n when the subtree's store cost > μ · f(n) if it has several stores, > f(n) if
one). In which blocks are the stores at the end?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 53 go-spill-sink · single · 1 pt · 09-spilling-and-rematerialization

In Go's placeSpills, a value y defined before a loop is restored only in a call block
inside the loop. Where is its spill placed?

1. In the call block, next to the restore
2. Right after y's definition, because the search does not move a spill into a deeper loop
3. At the function entry
4. In every predecessor of the call block

Answer format: one letter