Theory test — Chapter 23

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

Question 1 mca-rthroughput · number · 1 pt · 01-machine-models

A loop body has four independent instructions vdivpd; vdivpd; vmulpd; vmulpd (256-bit) on
Skylake: 4 micro-ops, dispatch width \(W = 6\). Each vdivpd holds the non-pipelined FP divider
(capacity 1) for 8 cycles; the multiplies use ports with plenty of capacity. What block
reciprocal throughput (cycles per iteration) does llvm-mca report, by Definition 23.1.10?

Answer format: a number

Question 2 forbidden-latencies · set · 1 pt · 01-machine-models

On the lab's toy machine, div reserves the multiplier in cycles 0–3 after issue and mul
reserves it in cycle 0 only. Give the set of forbidden latencies \(F(\mathtt{div}, \mathtt{mul})\):
the distances \(d \ge 0\) such that a mul issued \(d\) cycles after a div collides with it.

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

Question 3 operand-latency · number · 1 pt · 01-machine-models

In LLVM's per-operand model, vdivpd has write latency 14. A consumer reads the quotient through
an operand whose ReadAdvance is 2. What latency does TargetSchedModel::computeOperandLatency
give the dependence edge (Proposition 23.1.9)?

Answer format: a number

Question 4 find-skl-divider · number · 1 pt · 01-machine-models

Find it in LLVM: open llvm/lib/Target/X86/X86SchedSkylakeClient.td (LLVM 23.1.2) and find the
SKLWriteResPair for WriteFDiv64Y. For how many cycles does one 256-bit vdivpd hold the
SKLFPDivider resource (its ReleaseAtCycles entry)?

Answer format: a number

Question 5 tables-vs-automaton · single · 1 pt · 01-machine-models

Why do GCC (genautomata) and LLVM's VLIW packetizer compile reservation tables into finite
automata instead of checking the tables directly?

1. Automata can express hazards that reservation tables cannot
2. A fit query becomes one table lookup in the current state instead of a scan over every reservation of the operation
3. Automata also compute operand latencies
4. Reservation tables cannot describe non-pipelined units

Answer format: one letter

Question 6 dag-edges-running · set · 1 pt · 02-dependence-dags

The running block of Lesson 23.2 (toy machine):

a: r1 = load A[0]      f: r6 = mul r5, r3
b: r2 = load A[1]      g: r1 = load B[1]
c: r3 = load B[0]      h: store A[r2], r5
d: r4 = mul r1, r2     i: r7 = sub r6, r1
e: r5 = add r3, r3     j: r4 = add r4, r7

Give every edge of its canonical dependence DAG (true, anti, output and memory edges; merged
parallel edges count once), written x->y.

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

Question 7 edge-latency-output · number · 1 pt · 02-dependence-dags

Instruction \(i\) is a div (latency 6) writing r3; the next definition of r3 is \(j\), an
add (latency 1). What latency does the output edge \(i \to j\) need (Definition 23.2.3)?

Answer format: a number

Question 8 soundness-anti · single · 1 pt · 02-dependence-dags

An anti edge \(u \to v\) (u reads r, v redefines r) has latency 0 on the lab's machine. Why is 0
enough, and why can the edge not be dropped?

1. Operands are read at issue and results land at least one cycle later, so v may issue in u's cycle; without the edge v could issue earlier and u would read the new value
2. 0 is enough because anti dependences never matter on in-order machines
3. The edge can be dropped whenever v has a longer latency than u
4. Anti edges need the latency of v, but the scheduler rounds it down

Answer format: one letter

Question 9 heights-running · mapping · 1 pt · 02-dependence-dags

For the running block of dag-edges-running (latencies: load 3, mul 3, add/sub 1, store 1),
give the height \(h(v)\) of a, c, e, f, i and j (Definition 23.2.8).

Keys: a, c, e, f, i, j

Answer format: one value per key

Question 10 cp-bound · number · 1 pt · 02-dependence-dags

The running block has critical path 9 and uses the single memory unit 5 times; issue width 2 for
10 instructions. What is the combined lower bound \(\max(\mathrm{CP}, \mathrm{RB})\) on its schedule
length (Corollary 23.2.13)?

Answer format: a number

Question 11 find-buildschedgraph · text · 1 pt · 02-dependence-dags

Find it in LLVM: buildSchedGraph, which builds the dependence DAG of a MachineInstr scheduling
region (with the memory chains and the -dag-maps-huge-region cap), is a member function of which
class?

Answer format: a short answer

Question 12 td-trace-running · mapping · 1 pt · 03-list-scheduling

Schedule the running block top-down with critical-path priority (td-cp, Algorithm 23.3.2; toy
machine: issue 2, alu ×2, mem ×1, mul ×1). Give the issue cycles of a, b, c, d, g and j.

Keys: a, b, c, d, g, j

Answer format: one value per key

Question 13 td-succ-length · number · 1 pt · 03-list-scheduling

On the same block, what length does top-down list scheduling with the successor-count priority
(td-succ: most DAG successors first, then height) produce?

Answer format: a number

Question 14 graham-ratio · number · 1 pt · 03-list-scheduling

Graham's bound (Theorem 23.3.3): on \(m\) identical units, any list schedule has length at most
\((2 - 1/m)\) times the optimum. What is this ratio for \(m = 2\)?

Answer format: a number (±0.01)

Question 15 np-hard-sched · single · 1 pt · 03-list-scheduling

Which statement about optimal basic-block scheduling (Theorem 23.3.4) is correct?

1. It is NP-hard with precedence constraints and a number of units that is part of the input, while unit-latency trees (Hu) and two units with unit latencies (Coffman–Graham) are polynomial
2. It is polynomial for any DAG when all latencies are 1
3. It is NP-hard only for machines with more than 8 units
4. It is undecidable, which is why compilers use heuristics

Answer format: one letter

Question 16 reverse-latency · number · 1 pt · 03-list-scheduling

In the reversed instance of Definition 23.3.5, the edge c → e of the running block (c is a load
with latency 3, e an add with latency 1, \(\ell(c, e) = 3\)) becomes e → c. What is its latency?

Answer format: a number

Question 17 maxlive-running · number · 1 pt · 03-list-scheduling

The td-cp schedule of the running block (a 1, b 2, c 0, d 5, e 3, f 4, g 5, h 6, i 8, j 9;
live-out r4) needs how many registers, i.e. what is its MaxLive (Definition 23.3.9)?

Answer format: a number

Question 18 pressure-tradeoff · single · 1 pt · 03-list-scheduling

On the lab corpus, the ★ pressure scheduler (Algorithm 23.3.10, \(K\) = the in-order MaxLive) has
total MaxLive 1079 against 1224 for td-cp, and total length 4298 against 4110. What is the right
reading?

1. It trades about 4.6 % longer schedules for about 12 % fewer registers, which pays off when the difference is spills
2. It is simply worse than td-cp
3. It is always better: fewer registers and shorter schedules
4. Its schedules are invalid whenever they are longer than td-cp's

Answer format: one letter

Question 19 find-trycandidate · text · 1 pt · 03-list-scheduling

Find it in LLVM: which GenericScheduler member function in llvm/lib/CodeGen/MachineScheduler.cpp
compares two scheduling candidates criterion by criterion (physical-register bias, excess
pressure, critical pressure, latency, …)?

Answer format: a short answer

Question 20 trace-select-running · sequence · 1 pt · 04-region-scheduling

Profiled region: A→B 70, A→C 30, B→D 70, C→D 20, C→E 10, D→F 60, D→G 30, E→G 10, F→H 60,
G→H 40 (entry count 100). Give the first trace chosen by mutual-most-likely selection
(Algorithm 23.4.3; ties between seeds go to the earlier block).

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

Question 21 side-entrances · set · 1 pt · 04-region-scheduling

Which edges are side entrances of the trace A B D F H in that region? Write them as X->Y.

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

Question 22 compensation-rule · single · 1 pt · 04-region-scheduling

Trace scheduling moves z = y * 2 from D up into B, across the join at D (side entrance C→D).
What repair does Algorithm 23.4.5 make?

1. None: moving upward is speculation and needs no copy
2. Copy z = y * 2 onto the side entrance C→D, because the path entering from C no longer executes it
3. Copy it onto the side exit D→G
4. Forbid the move: operations may never move above a join

Answer format: one letter

Question 23 tail-dup-blocks · set · 1 pt · 04-region-scheduling

Superblock formation (Algorithm 23.4.6) makes the trace A B D F H single-entry by tail
duplication. Which blocks are duplicated?

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

Question 24 treegions-running · number · 1 pt · 04-region-scheduling

How many treegions (Definition 23.4.8) does the same region form?

Answer format: a number

Question 25 speculation-legal · multi · 1 pt · 04-region-scheduling

A superblock or treegion scheduler wants to move an operation \(x\) of a later block above a
branch (upward across a split). Which conditions must hold for the move to be legal without
compensation code?

1. \(x\) cannot trap (or the target has non-faulting speculative forms)
2. \(x\)'s destination is not live on the other path out of the branch (or can be renamed)
3. \(x\) is not a store or another side effect
4. \(x\) is on the critical path

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

Question 26 find-bookkeeping · text · 1 pt · 04-region-scheduling

Find it in GCC: which source file of GCC 15 still generates trace-scheduling-style bookkeeping
copies (generate_bookkeeping_insn)?

Answer format: a short answer

Question 27 pred-running · mapping · 1 pt · 05-if-conversion

The if-conversion region of Lesson 23.5: A: br cA, B, C; B: br cB, D, E;
C: br cC, E, F; D: jmp F; E: jmp F; F: exit. For each block, under how many of the
\(2^3 = 8\) assignments of \((c_A, c_B, c_C)\) does it execute (the size of its exact predicate's
truth set)?

Keys: A, B, C, D, E, F

Answer format: one value per key

Question 28 pred-count · number · 1 pt · 05-if-conversion

How many predicate registers does the RK (control-dependence) assignment need for that region
(Definition 23.5.4)?

Answer format: a number

Question 29 cd-sets · mapping · 1 pt · 05-if-conversion

For the same region, give the control-dependence set of D, E and F. Write the edge (X, true) as
X+ and (X, false) as X-, and the empty set as {}.

Keys: D, E, F

Answer format: one value per key (a set: {x, y})

Question 30 ifcvt-threshold · number · 1 pt · 05-if-conversion

Skylake's model has MispredictPenalty = 14. EarlyIfConversion converts a diamond only if the
critical path to the select grows by less than a limit derived from that penalty. What is that
limit, in cycles?

Answer format: a number

Question 31 hyperblock-set · set · 1 pt · 05-if-conversion

Hyperblock formation (Algorithm 23.5.6) on the Lesson 23.4 region (counts A 100, B 70, C 30,
D 90, E 10, F 60, G 40, H 100) with \(\theta_f = 0.25\), \(\theta_s = 2\), where E contains a call (a
hazard). Which blocks form the hyperblock \(H\)?

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

Question 32 nullify-vs-speculate · single · 1 pt · 05-if-conversion

EarlyIfConversion produces selects and executes both arms unconditionally; IfConverter on ARM
predicates the instructions. Which instructions can the select-based form NOT if-convert?

1. Arithmetic whose result is only used after the join
2. Stores, calls and instructions that may trap, because the select form executes them on both paths
3. Instructions that define a flag register
4. Any instruction that has more than two operands

Answer format: one letter

Question 33 find-shouldconvert · text · 1 pt · 05-if-conversion

Find it in LLVM: in llvm/lib/CodeGen/EarlyIfConversion.cpp, which member function of
EarlyIfConverter implements the trace-based profitability test?

Answer format: a short answer

Question 34 resmii-running · number · 1 pt · 06-software-pipelining

The running loop of Lesson 23.6 on the toy machine: a: r1 = load A[i], b: r2 = load B[i],
c: r3 = mul r1, r2, d: r4 = mul r6, r9, e: r6 = add r4, r3, f: store C[i], r6.
What is its ResMII?

Answer format: a number

Question 35 recmii-running · number · 1 pt · 06-software-pipelining

What is the RecMII of the same loop?

Answer format: a number

Question 36 ims-evictions · sequence · 1 pt · 06-software-pipelining

Iterative modulo scheduling (Algorithm 23.6.9) of the running loop at \(\mathit{II} = 4\). HeightR is
a 8, b 8, c 5, d 5, e 2, f 1. List the evicted operations in the order they are evicted.

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

Question 37 ims-sigma · mapping · 1 pt · 06-software-pipelining

Give the final \(\sigma\) of that IMS run for c, d, e and f (normalized so that \(\min \sigma = 0\)).

Keys: c, d, e, f

Answer format: one value per key

Question 38 sms-order · sequence · 1 pt · 06-software-pipelining

Swing modulo scheduling (Algorithm 23.6.10) of the same loop. The only recurrence set is {d, e}.
Give SMS's node order.

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

Question 39 mve-unroll · number · 1 pt · 06-software-pipelining

For the IMS schedule (a 0, b 1, c 4, d 7, e 10, f 11; \(\mathit{II} = 4\)), how many times would
modulo variable expansion unroll the kernel, \(u = \max_v \lceil \mathrm{lifetime}(v) / \mathit{II} \rceil\),
with a lifetime measured from the definition's issue to its last use's issue (Definition 23.6.11)?

Answer format: a number

Question 40 rotating-offset · number · 1 pt · 06-software-pipelining

In the lab's rotating-register code for the running loop, value e gets base register \(b_e = 9\),
e is in stage \(s_e = 2\), and there are \(S = 3\) stages. r6 is live out. Which rotating register
\(q_x\) does the exit copy r6 = mov qx read (Algorithm 23.6.12)? Give \(x\).

Answer format: a number

Question 41 find-recmii-distance · number · 1 pt · 06-software-pipelining

Find it in LLVM: SwingSchedulerDAG::calculateRecMII in llvm/lib/CodeGen/MachinePipeliner.cpp
divides each circuit's latency by a distance. What distance does it assume for every circuit?

Answer format: a number

Question 42 sdag-default-source · single · 1 pt · 07-llvm-schedulers

On a subtarget that enables the MachineScheduler (x86-64, AArch64 at -O2), which SelectionDAG
scheduler does createDefaultScheduler pick?

1. list-burr (register reduction)
2. list-ilp
3. source: keep the IR order and let MachineScheduler do the real work
4. list-hybrid

Answer format: one letter

Question 43 burr-su-number · number · 1 pt · 07-llvm-schedulers

In list-burr's numbering (Algorithm 23.7.2), a product t = a[i] * b[i] of two loads has
Sethi–Ullman number 2. What is the Sethi–Ullman number of xor applied to two such products?

Answer format: a number

Question 44 bot-available-running · set · 1 pt · 07-llvm-schedulers

If GenericScheduler schedules the running block of Lesson 23.2 bottom-up
(-misched-prera-direction=bottomup), which instructions are in Bot.Available at the start,
i.e. have no successors in the DAG of dag-edges-running?

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

Question 45 bidirectional-valid · single · 1 pt · 07-llvm-schedulers

GenericScheduler schedules from both ends of a region at once (top zone and bottom zone). Why is
the result always a valid order (Theorem 23.7.7)?

1. Because each zone only schedules nodes whose predecessors (top) or successors (bottom) are already placed in that zone, and the two partial orders meet in the middle
2. Because the bottom zone is discarded if the zones disagree
3. Because MachineScheduler only schedules nodes without dependences
4. Because the register allocator repairs the order afterwards

Answer format: one letter

Question 46 postra-antidep · single · 1 pt · 07-llvm-schedulers

What does -break-anti-dependencies=critical do in LLVM's legacy post-RA scheduler?

1. It removes all anti edges from the DAG without changing the code
2. It renames the register of an anti dependence on the critical path to a free physical register, so the edge disappears (Algorithm 23.7.9)
3. It inserts copies before every anti dependence
4. It reruns register allocation

Answer format: one letter

Question 47 find-createdefaultscheduler · text · 1 pt · 07-llvm-schedulers

Find it in LLVM: in which source file is createDefaultScheduler, the function that picks the
SelectionDAG scheduler, defined? Give the file name.

Answer format: a short answer

Question 48 false-deps-running · number · 1 pt · 08-scheduling-and-register-allocation

In the running block, g: r1 = load B[1] reuses r1, which a defined and d read. How many
DAG edges exist only because of that reuse (compare with the block where g writes a fresh r8)?

Answer format: a number

Question 49 ips-modes · single · 1 pt · 08-scheduling-and-register-allocation

How does Goodman and Hsu's integrated prepass scheduling (IPS, Algorithm 23.8.4) decide between its
two priority modes?

1. It alternates the modes every cycle
2. It uses latency-first scheduling (CSP) while enough registers are free, and switches to register reduction (CSR) when the free registers fall below a threshold
3. It schedules twice and keeps the shorter schedule
4. It always minimizes registers first

Answer format: one letter

Question 50 parallelizable-pairs · set · 1 pt · 08-scheduling-and-register-allocation

In the renamed running block (g writes r8, i reads r8), which of these pairs of
value-defining operations are parallelizable, i.e. have no DAG path between them in either
direction: a-g, a-d, c-e, d-f, e-f, b-c? Answer with the pairs written as in the list.

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

Question 51 regrename-effect · number · 1 pt · 08-scheduling-and-register-allocation

A renaming pass (GCC regrename, or an anti-dependence breaker) gives g the fresh register r8
in the running block. What schedule length does td-cp then reach?

Answer format: a number

Question 52 ph-chains · sequence · 1 pt · 09-code-layout

Pettis–Hansen chain merging (Algorithm 23.9.2) on the region of trace-select-running, followed by
the layout rule (entry chain first, then chains by decreasing count of their head). Give the final
layout.

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

Question 53 fallthrough-weight · number · 1 pt · 09-code-layout

What is the fall-through weight (Definition 23.9.1) of that layout?

Answer format: a number

Question 54 exttsp-edge · number · 1 pt · 09-code-layout

In that layout with sizes A 16, B 8, C 24, D 16, E 32, F 8, G 16, H 8 bytes, the edge D→G
(count 30) is a forward jump from the end of D over F, H, C and E. What is its ext-TSP
contribution (Definition 23.9.5), to two decimals?

Answer format: a number (±0.01)

Question 55 layout-np · single · 1 pt · 09-code-layout

Why do both Pettis–Hansen and ext-TSP placement use greedy chain merging?

1. Maximizing fall-through weight is NP-hard (Theorem 23.9.4), and so is maximizing the ext-TSP score (Corollary 23.9.7)
2. Because an optimal layout always exists among the greedy ones
3. Because branch predictors ignore layout
4. Because the profile is too inaccurate for anything else

Answer format: one letter

Question 56 find-exttsp-distance · number · 1 pt · 09-code-layout

Find it in LLVM: in llvm/lib/Transforms/Utils/CodeLayout.cpp, beyond how many bytes does a
forward jump stop contributing to the ext-TSP score (the ForwardDistance option's default)?

Answer format: a number

Question 57 tailmerge-size · number · 1 pt · 09-code-layout

Two predecessors of a return block end with the same 7 machine instructions (four calls and their
argument moves) after different setups. How many instructions does tail merging save, not counting
the one jump it adds?

Answer format: a number

Question 58 branchfold-single · single · 1 pt · 09-code-layout

Which transformation is branch folding (not tail merging)?

1. Redirecting a jump to an empty block that only jumps on, straight to the final target, and deleting the empty block
2. Keeping one copy of two identical block tails
3. Moving a cold block to the end of the function
4. Replacing a branch by a select

Answer format: one letter

Question 59 cmp-elim-flags · single · 1 pt · 10-machine-peepholes-and-post-link

In SSA MIR, %4 = SUB64rr %3, %1, implicit-def dead $eflags is followed by TEST64rr %4, %4 and a
je. Why may PeepholeOptimizer delete the TEST64rr?

1. Because je does not read the flags
2. Because SUB64rr already sets ZF from the same result and nothing in between writes EFLAGS; the SUB's flag definition becomes live instead of dead
3. Because TEST64rr is always redundant after arithmetic
4. Because MachineCSE found an identical TEST

Answer format: one letter

Question 60 peephole-deleted · number · 1 pt · 10-machine-peepholes-and-post-link

In the same MIR, a successor block recomputes %5 = MOV64ri 12345678901, which the entry block
(dominating it) already computed as %2. After PeepholeOptimizer and MachineCSE, how many
machine instructions of the function are gone?

Answer format: a number

Question 61 licm-hoistable · set · 1 pt · 10-machine-peepholes-and-post-link

A loop body (SSA MIR, x86-64) contains:

i1: %7 = MOV64ri 12345678901          ; no operands
i2: %8 = ADD64rr %6, %7, implicit-def dead $eflags   ; %6 is the loop's phi
i3: %9 = LEA64r %2, 1, %2, 0, $noreg  ; %2 is defined before the loop
i4: %10 = MOV64rm %1, 1, $noreg, 0, $noreg   ; load; the loop also stores through %1

Which of them can early MachineLICM hoist into the preheader?

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

Question 62 sink-target · single · 1 pt · 10-machine-peepholes-and-post-link

In the entry block, %4 = IMUL64rr %2, %2 is used only after a loop, while the entry also has an
early-return path. What does MachineSink do?

1. Nothing: an instruction in the entry block cannot move
2. Splits the critical edge from the entry to the loop and moves the multiply into the new block, so the early-return path no longer executes it
3. Moves the multiply into the loop body
4. Duplicates the multiply into both successors

Answer format: one letter

Question 63 bolt-vs-propeller · multi · 1 pt · 10-machine-peepholes-and-post-link

Which statements are true?

1. BOLT disassembles and rewrites the final binary
2. Propeller turns the profile into basic-block cluster directives and re-runs code generation and linking
3. Both need a profile of the optimized binary, typically from hardware sampling such as LBR
4. Propeller cannot split hot and cold code

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

Question 64 propeller-cluster · sequence · 1 pt · 10-machine-peepholes-and-post-link

Function f has machine blocks 0 (entry), 1 (the unlikely then) and 2 (the likely else, the
return path). The profile shows block 1 cold. Give the block IDs of the hot cluster in the order
the cluster directive lists them.

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

Question 65 find-bbsections · text · 1 pt · 10-machine-peepholes-and-post-link

Find it in LLVM: which file in llvm/lib/CodeGen/ reads the -fbasic-block-sections=list= cluster
file and assigns blocks to sections?

Answer format: a short answer