Theory test — Chapter 21¶
59 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 21 # interactive
./course quiz template 21 -o answers/ch21.yaml # or fill in a file ...
./course quiz grade 21 # ... and grade it
macro-cost-running · number · 1 pt · 01-macro-expansion-and-maximal-munchMacro-expand (MOVE (TEMP x) (ADD (MEM (ADD (TEMP p) (CONST 8))) (CONST 1))) for Tessera
with the macro table of the lab (MOVE r1 mv 1, TEMP r6 free, CONST r7 li 1, ADD r8
add 1, MEM r17 ld … 0(…) 2). What is the total cost?
macro-instructions · number · 1 pt · 01-macro-expansion-and-maximal-munchHow many Tessera instructions does macro expansion emit for
(STORE (ADD (TEMP b) (CONST 16)) (MEM (ADD (TEMP p) (TEMP q))))
(STORE uses r2 st v, 0(a); the other macro rules as in the lab)?
munch-trace-running · sequence · 1 pt · 01-macro-expansion-and-maximal-munchRun maximal munch (largest pattern, ties to the lower rule number) on
(STORE (TEMP a) (MEM (ADD (TEMP p) (CONST 8)))) with the Tessera grammar. Relevant rules:
r2 stmt: STORE(reg, reg) (2), r5 stmt: STORE(reg, MEM(reg)) (4), r6 reg: TEMP (0),
r7 reg: CONST (1), r8 reg: ADD(reg, reg) (1), r9 reg: ADD(reg, CONST) (1),
r17 reg: MEM(reg) (2), r18 reg: MEM(ADD(reg, CONST)) (2). List the rules munch chooses,
in the order it chooses them (root first, then operands left to right).
munch-optimal-vs-optimum · single · 1 pt · 01-macro-expansion-and-maximal-munchIn the previous question munch produced addi r1, p, 8; movm (a), (r1) (cost 5) and the
best tiling costs 4. In Appel's terms (Definition 21.1.9), munch's tiling is:
- optimum and optimal
- optimal (no two adjacent tiles can be merged into one cheaper rule) but not optimum
- optimum but not optimal
- neither: Theorem 21.1.13 fails on this tree
llvm-where-complexity · text · 1 pt · 01-macro-expansion-and-maximal-munchFind it in LLVM 23: DAGISelEmitter::run sorts the SelectionDAG patterns (maximal munch's
"largest first" order) by a score. Which PatternToMatch member function returns that score
(in llvm/utils/TableGen/Common/CodeGenDAGPatterns.cpp)?
combine-order · number · 1 pt · 01-macro-expansion-and-maximal-munchLesson 21.1 §3 combines the macro code of a[i] = p[3] (li r1, 3; sll r2, i, r1; add r3, a, r2; li r4, 24; add r5, p, r4; ld r6, 0(r5); st r6, 0(r3)). Suppose the combiner
first tries the link ld r6, 0(r5) → st r6, 0(r3) (forming movm (r3), (r5), cost 4)
and only then the other links in the lesson's order. What is the final cost?
combine-single-use · single · 1 pt · 01-macro-expansion-and-maximal-munchWhy does the combiner (Definition 21.1.10) only merge a producer i into a consumer j when j is the only reader of i's result?
- Because the recognizer can only match expressions of depth two.
- Because i's result is still needed by another reader; merging i into j would compute it twice (i must stay) and the combined instruction is rarely cheaper than the original pair.
- Because register allocation has already assigned i's destination.
- Because GCC's RTL cannot represent multi-use values.
dp-labels-running · mapping · 1 pt · 02-optimal-tree-tilingLabel (STORE (TEMP a) (MEM (ADD (TEMP p) (CONST 8)))) with Algorithm 21.2.3 over Tessera
(rules as in munch-trace-running, plus r20 reg: MEM(ADD(reg, reg)) (2)). Nodes in
postorder: n1 TEMP a, n2 TEMP p, n3 CONST 8, n4 ADD, n5 MEM, n6 STORE. Give C(n, reg) for
n3, n4, n5 and C(n6, stmt).
n3, n4, n5, n6dp-root-choice · text · 1 pt · 02-optimal-tree-tilingIn the tree of dp-labels-running, which rule does Reduce (Algorithm 21.2.4) use at the root?
iburg-tie · mapping · 1 pt · 02-optimal-tree-tilingAn iburg-generated labeler (Algorithm 21.2.11: rules tried in file order, a rule replaces the
current best only if strictly cheaper) labels the ADD node of
(MOVE (TEMP y) (ADD (MUL (TEMP a) (TEMP b)) (SHL (TEMP c) (CONST 2)))) with Tessera:
r8 reg: ADD(reg, reg) (1), r12 reg: MUL(reg, reg) (3), r13 reg: ADD(MUL(reg, reg), reg)
(3), r15 reg: SHL(reg, CONST) (1), r16 reg: ADD(reg, SHL(reg, CONST)) (1). Give the
winning rule and C(ADD, reg).
rule, costdynamic-cost-context · single · 1 pt · 02-optimal-tree-tilingWhich dynamic cost keeps the tree DP exact (Proposition 21.2.12)?
- A cost that is 0 when the parent node will fold this load into its addressing mode.
- A cost that is LBURG_MAX unless the node's constant is in the range 1..8.
- A cost that depends on how many registers are free when the node is evaluated.
- A cost that depends on the rule chosen for the node's sibling.
burs-state-count · number · 1 pt · 03-burs-automataTake Lesson 21.3's grammar G_s without r7: r1 stmt: STORE(reg, reg) (2), r2 reg: TEMP (0),
r3 reg: CONST (1), r4 reg: ADD(reg, reg) (1), r5 reg: ADD(reg, CONST) (1),
r6 reg: MEM(reg) (2). Normal form adds the helper c: CONST (0). How many δ-states does
Algorithm 21.3.4 produce?
burs-normalize · mapping · 1 pt · 03-burs-automataTake G_s without r5 (keep r7 reg: MEM(ADD(reg, CONST)) (2)), in normal form with helpers
c: CONST (0) and d: ADD(reg, c) (0). What is the δ-state of the node ADD(TEMP p, CONST 8)?
Give the normalized cost of each nonterminal defined there.
reg, dburg-representers · number · 1 pt · 03-burs-automataFor the 6-state automaton of burs-state-count (G_s without r7), how many entries does the
compressed MEM transition table need (Algorithm 21.3.10: one entry per representer state of
MEM's only operand position)?
burg-vs-iburg · single · 1 pt · 03-burs-automataWhat does a BURG-generated labeler do at compile time that an iburg-generated labeler does differently?
- BURG labels each node with one table lookup and no cost arithmetic; iburg adds and compares costs at every node.
- BURG supports dynamic costs; iburg does not.
- BURG finds optimum tilings on DAGs; iburg only on trees.
- BURG emits code top-down without labeling.
dag-decomposition-cost · number · 1 pt · 04-dag-coveringBasic block D3: MOVE(TEMP x, MEM(q)) and MOVE(TEMP y, MEM(q)) with the shared node
q = ADD(TEMP p, CONST 16). Cut the DAG into trees at q (Algorithm 21.4.5) and tile each tree
optimally with Tessera (r9 addi 1, r17 ld 0(r) 2, r18 ld c(r) 2, r1 mv 1). Total cost?
dag-np-complete · single · 1 pt · 04-dag-coveringWhat does Theorem 21.4.4 say about DAG covering?
- Minimum-cost covering of DAGs is NP-complete in general, even for one fixed grammar with costs 0 and 1; trees remain linear-time.
- It is NP-complete only when registers are limited.
- It is polynomial with the tree DP applied at every shared node.
- It is undecidable for grammars with chain rules.
noltis-fix · number · 1 pt · 04-dag-coveringD2': three statements MOVE(TEMP x, ADD(m, TEMP c)), MOVE(TEMP y, ADD(m, TEMP d)),
MOVE(TEMP z, ADD(m, TEMP e)) share m = MUL(TEMP a, TEMP b). Tessera: r12 mul 3,
r13 madd 3 (ADD(MUL(reg, reg), reg)), r8 add 1, r1 mv 1. Run NOLTIS
(Algorithm 21.4.9). What is the cost of the final cover?
noltis-overlap · mapping · 1 pt · 04-dag-coveringFor D3 of dag-decomposition-cost (q = ADD(TEMP p, CONST 16) inside both loads), the first
NOLTIS pass tiles each load with r18 ld c(r) (2). Give ω(q) (Definition 21.4.8), κ(q), and
the decision (fix or keep).
omega, kappa, decisionpbqp-r1 · mapping · 1 pt · 04-dag-coveringPBQP on a shared MUL node m with choices {r12, h} (r12 produces reg, cost 3; h is the helper
inside madd, cost 0), so c_m = (r12: 3, h: 0). Its neighbour a (an ADD) has choices
{r8, r13} with costs c_a = (r8: 2, r13: 3), and the edge matrix is 0 on (r8, r12) and
(r13, h), ∞ elsewhere. Apply R1 to a (a has degree 1). Give the new c_m.
r12, hpbqp-optimal-when · single · 1 pt · 04-dag-coveringWhen is the PBQP solver's result (Algorithm 21.4.12) guaranteed to be an optimum?
- Always: PBQP is solved exactly in polynomial time.
- When the graph can be reduced with R0, R1 and R2 only (for example, a series-parallel graph); once RN fires it is a heuristic.
- Only when all cost matrices are zero.
- Only when the DAG is a tree and no chain rules exist.
sdag-phase-order · sequence · 1 pt · 05-selectiondagPut these SelectionDAG phases of one block in execution order (the combine run right after
type legalization is left out): LO (legalize operations), S (select), B (build), LV (legalize
vector operations), C2 (last combine), SC (schedule), C1 (first combine), LT (legalize types).
combiner-disabled · single · 1 pt · 05-selectiondagf(x, y) = (x * 8 + y) − y compiles to leaq (,%rdi,8), %rax normally, and to imulq,
addq, subq with -combiner-disabled. What does this show?
- The matcher table contains algebraic identities that the combiner switches off.
- The selector covers the DAG it is given without doing algebra; canonicalization and simplification (x·8 → x ≪ 3, (a + b) − b → a) are the DAG combiner's job.
- Without the combiner, type legalization is skipped.
- -combiner-disabled switches from SelectionDAG to FastISel.
legalize-x86-i128 · set · 1 pt · 05-selectiondagdefine i128 @s(i128 %a, i128 %b) { %r = sub i128 %a, %b ret i128 %r } on x86-64 with
SelectionDAG: which machine opcodes (besides COPY and RET) are selected after type
legalization expands i128? (MIR spelling)
legalize-a64-i8 · mapping · 1 pt · 05-selectiondagmul i8 on AArch64 with SelectionDAG. Give the type action for i8 (legal, promote, expand),
the type it becomes, and the selected opcode.
action, type, opcodellvm-where-selectcodecommon · text · 1 pt · 05-selectiondagFind it in LLVM 23: which SelectionDAGISel member function interprets the TableGen-generated matcher table?
matcher-order · sequence · 1 pt · 05-selectiondagA target's patterns for add on GPR (no AddedComplexity): (a) (add GPR:$s, GPR:$t),
(b) (add GPR:$s, (imm):$c), (c) (add GPR:$s, (shl GPR:$t, (imm):$k)). In which order does
the generated matcher try them at an add node?
sched-topological · sequence · 1 pt · 05-selectiondagA selected DAG has dependences A → C, B → C, B → E, C → D, E → D (u → v: u must come first),
and C is glued to D (C immediately before D). A top-down list scheduler always takes the
ready unit whose name comes first alphabetically. What order does it produce?
sched-glue · single · 1 pt · 05-selectiondagWhat does a glue edge between two SelectionDAG nodes guarantee?
- That the two nodes are selected by the same pattern.
- That the scheduler keeps them adjacent, in order, for example a compare and the branch that reads its flags.
- That both nodes run on the same execution unit.
- That the nodes are in the same basic block.
fastisel-fallback · set · 1 pt · 06-globalisel-and-fastiselx86-64, llc -O0 -fast-isel-report-on-fallback on five functions: a (add i64), b (fadd
double), c (add i128), d (call to llvm.ctpop.i32), e (add <2 x i64>). For which does
FastISel fall back to SelectionDAG?
fastisel-o0-fold · single · 1 pt · 06-globalisel-and-fastiselWhich local fold does FastISel perform in the sum loop at -O0 (Lesson 21.6 §3)?
- It folds the single-use load into the add (ADD64rm) with tryToFoldLoad, and the single-use compare into the branch.
- It folds the whole loop into a vector instruction.
- It eliminates the PHIs.
- None: FastISel never folds.
gisel-pass-order · sequence · 1 pt · 06-globalisel-and-fastiselOrder GlobalISel's four core passes by their -stop-after names: legalizer,
instruction-select, irtranslator, regbankselect.
gisel-bank · mapping · 1 pt · 06-globalisel-and-fastiselAArch64, -global-isel -stop-after=regbankselect: %2 = G_FADD %0, %1 on f64, and
%1 = G_FPTOSI %0(f64) producing i64. Which bank does each result get (gpr or fpr)?
fadd, fptosigisel-mul-to-shl · number · 1 pt · 06-globalisel-and-fastiselThe GlobalISel combine rule mul_to_shl fires on %7 = G_MUL %1, %6 with
%6 = G_CONSTANT i64 32. What constant does the new G_SHL shift by?
gisel-combine-where · text · 1 pt · 06-globalisel-and-fastiselFind it in LLVM 23: in which TableGen file are the generic GlobalISel combine rules such as mul_to_shl defined (file name)?
isle-priority-winner · mapping · 1 pt · 07-rewrite-based-selectionCranelift AArch64 lowering of iadd v1, v2 where v2 = iconst 5 and v1 is not a constant,
shift or multiply. The iadd rules (priority): iadd_ishl_right (7), iadd_imul_right (7),
iadd_ishl_left (6), iadd_imm12_left (5), iadd_imm12_right (4), iadd_extend_right (0),
iadd_base_case (−1). Which rule is used, and what is its priority?
rule, priorityisle-overlap · single · 1 pt · 07-rewrite-based-selectionWhat does ISLE's overlap checker reject?
- Two rules of different priority that match the same term.
- Two rules of the same priority whose left-hand sides can both match some term (unless one subsumes the other in an allowed way), because the choice between them would be arbitrary.
- Any rule with an extractor.
- Rules whose right-hand side is larger than the left-hand side.
egraph-extract-cost · number · 1 pt · 07-rewrite-based-selectionSaturate the e-graph of (x * 4) + (y * 4) with the rules x·2^k → x ≪ k and
x·a + y·a → (x + y)·a. Costs: mul 3, shl 1, add 1, constants and variables 0. What is the
cost of the cheapest term extracted for the root class?
egraph-dag-hard · single · 1 pt · 07-rewrite-based-selectionWhy is extraction from an e-graph easy when costs are tree costs but hard for the real cost of a program?
- Tree-cost extraction is a bottom-up minimum per class (like the tiling DP), but when shared subterms are paid for once (DAG cost), extraction is NP-hard, like DAG covering.
- Because e-graphs can contain cycles, which makes every extraction undecidable.
- Because rewrite rules are not confluent.
- It is not: both are linear-time.
tblgen-let-override · mapping · 1 pt · 08-target-descriptionclass Inst<string m, int c> { string M = m; int Cost = c; int Size = 4; }
class Short { int Size = 2; }
def A : Inst<"a", 1>, Short;
let Cost = 5 in {
def B : Inst<"b", 2> { let Cost = 9; let Size = 8; }
}
let Size = 6 in
def C : Inst<"c", 3>, Short { let Cost = 7; }
Give the elaborated values of A.Size, B.Cost, C.Size and C.Cost.
A.Size, B.Cost, C.Size, C.Costtblgen-complexity · number · 1 pt · 08-target-descriptionWhat complexity does llvm-tblgen -gen-dag-isel print for the pattern (sub (mul GPR:$a, GPR:$b), (imm):$c) (no AddedComplexity)?
gcc-recog-order · number · 1 pt · 08-target-descriptionA machine description has, in file order: insn 0 (set (match_operand:DI 0 "register_operand") (plus:DI (match_operand:DI 1 "register_operand") (match_operand:DI 2 "register_operand")));
insn 1 the same with operand 2 "const_int_operand" and condition INTVAL (operands[2]) > 0;
insn 2 the same with operand 2 "nonmemory_operand" and no condition. Which insn code does
recog return for (set (reg:DI 100) (plus:DI (reg:DI 101) (const_int -4)))?
gcc-no-mem-mem · single · 1 pt · 08-target-descriptionWhy does GCC never produce a memory-to-memory mov on x86-64 (the movm of Tessera)?
- Because
*movdi_internal's condition rejects two memory operands, so recog fails and combine keeps two instructions. - Because the register allocator splits it.
- Because RTL cannot express a store of a load.
- Because x86-64 has no 64-bit loads.
lburg-addr-nonterminals · set · 1 pt · 08-target-descriptionIn lcc's x86 lburg description (src/x86linux.md), besides baseaddr (the address of a global), which three nonterminals describe addressing modes, the tree-grammar analogue of TableGen's ComplexPattern?
adl-instruct-parts · single · 1 pt · 08-target-descriptionWhat does a HotSpot ADL instruct block specify?
- Only the assembly syntax.
- A match rule (the ideal-graph tree it covers), a cost, an encoding and a pipeline class, from which ADLC generates the DP labeler and the emitter.
- A calling convention.
- A register allocation hint.
cc-sysv-i128 · mapping · 1 pt · 09-calling-conventions-and-framesvoid f(i64 a0, i64 a1, i64 a2, i64 a3, i64 a4, i128 a5, i64 a6) under the System V x86-64
convention. Give the locations of a4, a5 and a6 (a register, lo:hi pair, or stack+off).
a4, a5, a6cc-aapcs-even · mapping · 1 pt · 09-calling-conventions-and-framesThe same signature as cc-sysv-i128 under AAPCS64 (Linux). Locations of a4, a5 and a6?
a4, a5, a6frame-red-zone · number · 1 pt · 09-calling-conventions-and-framesA leaf function on x86-64 Linux stores to and loads from a local long a[6] (48 bytes,
align 8). llc -O2 uses the red zone. At what offset from %rsp is a[0]?
frame-align · number · 1 pt · 09-calling-conventions-and-framesA non-leaf x86-64 function saves one callee-saved register with pushq %rbx and has a
20-byte local array (align 4); it calls other functions. How many bytes does the prologue
subtract from %rsp (subq $N, %rsp)?
pei-csr · set · 1 pt · 09-calling-conventions-and-framesh(x, y, z) = g(x) + g(y) + z + x on x86-64 (g external). The register allocator keeps every
value that lives across a call in a callee-saved register. Which callee-saved registers does
PEI push (llc -O2)? (write them without %)
shrinkwrap-points · mapping · 1 pt · 09-calling-conventions-and-framesCFG: entry → B, E; B → C, D; C → D; D → E; E returns. Only C and D use a callee-saved
register. No loops. Give the save point S and the restore point R that Algorithm 21.9.10
computes.
S, Rllvm-where-shrinkwrap · text · 1 pt · 09-calling-conventions-and-framesFind it in LLVM 23: which file in llvm/lib/CodeGen/ computes the save and restore points for shrink-wrapping?
mc-modrm-decode · mapping · 1 pt · 10-mc-layer-and-object-filesDecode the x86-64 bytes 48 8b 54 8b 10 (opcode 8b = MOV r64, r/m64). Register numbers:
rax 0, rcx 1, rdx 2, rbx 3, rsp 4, rbp 5, rsi 6, rdi 7. Give the destination register, the
base, the index, the scale and the displacement.
dest, base, index, scale, dispmc-rbp-disp · number · 1 pt · 10-mc-layer-and-object-filesHow many bytes does movq (%r13), %rcx take on x86-64?
relax-cascade · number · 1 pt · 10-mc-layer-and-object-filesAssemble for x86-64 (short jmp: 2 bytes, reaches −128..127 from its end; near jmp: 5 bytes):
jmp .L1; jmp .L2; .space 124; .L1: .space 20; .L2: ret. How many bytes is the section?
relax-least · single · 1 pt · 10-mc-layer-and-object-filesWhat does Theorem 21.10.7 guarantee for start-short relaxation when every span-dependent operand is a label?
- It returns the least consistent assignment, which minimizes the section size and every label address, after at most n + 1 rounds.
- It returns the greatest consistent assignment.
- It is optimal even with alignment directives.
- It never relaxes an instruction that could have stayed short in some consistent assignment, but may need exponentially many rounds.
llvm-where-relax · text · 1 pt · 10-mc-layer-and-object-filesFind it in LLVM 23: which MCAssembler member function performs one fused forward sweep of layout and relaxation over the sections, and is repeated by MCAssembler::layout until nothing changes?
reloc-addend · number · 1 pt · 10-mc-layer-and-object-filesWhat addend does the ELF relocation for movl $7, x(%rip) (x in another file) have on x86-64?
reloc-link-value · number · 1 pt · 10-mc-layer-and-object-filesA callq g has its 4-byte field at address 0x401021 after linking (relocation
R_X86_64_PLT32 g − 4), and g is at 0x401100 in the same executable. What value (decimal)
does the linker write into the field?