Theory test — Chapter 0

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

Question 1 refinement-compose · single · 1 pt · 01-pipeline-shapes

Passes P1: C → LLVM IR and P2: LLVM IR → LLVM IR are both correct (each output refines its
input, Definition 0.1.4). What can you conclude about the pipeline P2 ∘ P1, and why?

1. Nothing, because the passes work on different languages
2. It is correct, because refinement is transitive (Lemma 0.1.3, Theorem 0.1.6)
3. It is correct only if P1 and P2 are deterministic
4. It is correct only if neither pass sees a program with undefined behavior

Answer format: one letter

Question 2 refinement-ub · single · 1 pt · 01-pipeline-shapes

A source program p reads an uninitialized variable, so ub ∈ Beh(p). Which target programs q
satisfy q ⪯ p?

1. Only programs with the same output as p on the test inputs
2. Only programs that also contain undefined behavior
3. Every program
4. No program, so a correct compiler must reject p

Answer format: one letter

Question 3 pass-manager-recompute · number · 1 pt · 01-pipeline-shapes

Algorithm 0.1.8 runs passes P1 … P6. P1, P3 and P5 request the dominator tree; P6 does not.
P1, P3, P5 and P6 preserve it; P2 and P4 do not. How many times is the dominator tree
computed?

Answer format: a number

Question 4 llvm-where-o0-pipeline · text · 1 pt · 01-pipeline-shapes

In llvm/lib/Passes/PassBuilderPipelines.cpp (LLVM 23.1.2), buildPerModuleDefaultPipeline
returns early for OptimizationLevel::O0. Which PassBuilder member function does it call
then? (name only)

Answer format: a short answer

Question 5 backpatch-trace · mapping · 1 pt · 01-pipeline-shapes

Algorithm 0.1.10 (one-pass, with backpatching) compiles
if x < 1 { y = 1; } else { y = 2; } return y;
into 11 instructions numbered 0–10: load x, push 1, lt, jz ?, push 1, store y, jmp ?, push 2, store y, load y, ret. Give the patched targets of the two jumps.

Keys: jz, jmp

Answer format: one value per key

Question 6 single-pass-tcc-order · single · 1 pt · 01-pipeline-shapes

In TCC's code for for (i = 0; i < n; i++) s += i; (Lesson 0.1 box) the increment i++ is
emitted before the body, and the condition jumps over it into the body. Why?

1. TCC optimizes the loop by rotating it
2. A single-pass compiler emits code in source order, and i++ appears before the body in the source
3. x86 requires increments before loop bodies
4. The preprocessor reorders the for statement

Answer format: one letter

Question 7 query-red-green · set · 1 pt · 01-pipeline-shapes

A query graph from the previous session (deps in recorded order): A = parse(F);
B = sig(f) reads A; C = body(f) reads A; D = sig(g) reads A; E = typeck(g) reads D, B;
G = codegen(f) reads C, B; H = codegen(g) reads E. The edit changes only the body of f,
so A's value changes, B's and D's recomputed values are unchanged, and C's changes.
After demanding G and H with Algorithm 0.1.12, which nodes' providers were EXECUTED?
(Input F is not a provider.)

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

Question 8 query-early-cutoff · single · 1 pt · 01-pipeline-shapes

In the previous question, why is typeck(g) NOT re-executed although parse(F) changed?

1. Because typeck(g) is an input
2. Because its recorded dependencies sig(g) and sig(f) were recomputed with unchanged fingerprints, so they are green
3. Because the red-green algorithm never re-executes type checking
4. Because H was demanded after G

Answer format: one letter

Question 9 mlir-progressive · sequence · 1 pt · 01-pipeline-shapes

In Lesson 0.1's MLIR box, give the levels the sum loop passes through, from the input to
the final output. Use the tokens: cf, llvm-dialect, llvm-ir, scf.

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

Question 10 llvm-where-scf-for · text · 1 pt · 01-pipeline-shapes

In mlir/lib/Conversion/SCFToControlFlow/SCFToControlFlow.cpp (LLVM 23.1.2), what is the
name of the rewrite-pattern struct that lowers scf.for?

Answer format: a short answer

Question 11 tree-walk-eval-count · number · 1 pt · 02-interpreters

How many times does the tree walker of Algorithm 0.2.3 call Eval (once per expression node
visited) on the program x = 3; while x > 0 { x = x - 1; } return x;?

Answer format: a number

Question 12 llvm-where-interpreter · text · 1 pt · 02-interpreters

In llvm/lib/ExecutionEngine/Interpreter/Execution.cpp (LLVM 23.1.2), which member function
of class Interpreter contains the main loop that executes instructions one after another?

Answer format: a short answer

Question 13 bigstep-division · mapping · 1 pt · 02-interpreters

Under Tiny's semantics (Definition 0.2.2), give the values:
A = 7 / 0, B = 7 % 0, C = (-7) / 2, D = (-7) % 2, E = (-9223372036854775807 - 1) / (-1).

Keys: A, B, C, D, E

Answer format: one value per key

Question 14 stack-code-order · sequence · 1 pt · 02-interpreters

Give the stack code of Algorithm 0.2.5 for (a - b) * c, instructions separated by commas
(instruction names: load, push, add, sub, mul).

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

Question 15 stack-depth · number · 1 pt · 02-interpreters

What is the maximum stack depth D(e) of the postorder stack code for a - (b - (c - d))?

Answer format: a number

Question 16 ershov-number · number · 1 pt · 02-interpreters

What is the Ershov number E(e) of a - (b - (c - d)) — the minimum stack depth if, at each
operator, either operand may be evaluated first?

Answer format: a number

Question 17 register-count · number · 1 pt · 02-interpreters

How many three-address instructions does Algorithm 0.2.7 emit for (a + b) * (c - d * e)
(no destination register)?

Answer format: a number

Question 18 register-vs-stack · single · 1 pt · 02-interpreters

Compared with a stack VM for the same programs, a register VM typically…

1. executes more instructions, each smaller
2. executes fewer instructions, each larger (Shi et al.: ~47% fewer, code ~25% larger)
3. executes the same number of instructions but predicts branches better
4. needs no operands at all

Answer format: one letter

Question 19 dispatch-switch-misses · number · 1 pt · 02-interpreters

An interpreter executes the opcode trace A B A A B B A. Under the last-target model
(Definition 0.2.9), how many dispatches mispredict with SWITCH dispatch?

Answer format: a number

Question 20 dispatch-threaded-misses · number · 1 pt · 02-interpreters

Same trace A B A A B B A. How many dispatches mispredict with THREADED dispatch (each handler
has its own dispatch site; the first dispatch comes from an entry site)?

Answer format: a number

Question 21 threading-kinds · mapping · 1 pt · 02-interpreters

Match each dispatch scheme to its description (Definition 0.2.8):
a = the code holds handler addresses and every handler jumps to the next one itself;
b = one indirect jump through a jump table in a loop, shared by all handlers;
c = the code holds addresses of cells that contain handler addresses;
d = the code holds opcodes, and every handler ends with a jump through the opcode table.
Keys: switch, direct, indirect, token.

Keys: switch, direct, indirect, token

Answer format: one value per key

Question 22 aot-o2-closed-form · single · 1 pt · 03-aot-jit-transpilers

What happened to the loop of sum.c in clang's -O2 LLVM IR (Lesson 0.3 box)?

1. It was unrolled four times
2. It was vectorized
3. It was replaced by a closed-form computation of the sum (scalar evolution), with no loop left
4. Nothing: -O2 keeps loops unchanged

Answer format: one letter

Question 23 jit-breakeven · number · 1 pt · 03-aot-jit-transpilers

A program runs in 0.50 ms interpreted and 0.02 ms compiled; compiling it costs 9.6 ms. After
how many runs N* = c / Δ does compiling break even?

Answer format: a number

Question 24 ski-rental-ratio · number · 1 pt · 03-aot-jit-transpilers

With c = 1000 µs and Δ = 1 µs, the threshold policy compiles on call k = ⌊c/Δ⌋ + 1 = 1001.
For N = 1500 calls, what is its extra cost (above running compiled code for every call), in µs?

Answer format: a number

Question 25 llvm-where-lljit · text · 1 pt · 03-aot-jit-transpilers

In llvm/lib/ExecutionEngine/Orc/LLJIT.cpp (LLVM 23.1.2), which LLJITBuilderState member
function fills in defaults (target machine, linking layer, …) before an LLJIT is constructed?

Answer format: a short answer

Question 26 trace-guards · single · 1 pt · 03-aot-jit-transpilers

What happens when a guard in a compiled trace fails?

1. The program aborts with an error
2. The trace is recompiled and restarted from the loop header
3. A side exit rebuilds the interpreter state at that point and the interpreter continues from there
4. The guard is ignored and the trace continues

Answer format: one letter

Question 27 tracing-vs-method · single · 1 pt · 03-aot-jit-transpilers

Which code shape is worst for a tracing JIT compared with a method JIT?

1. A tight numeric loop with a stable path
2. A loop body with many independent, unpredictable if-statements
3. A function called once
4. A loop that calls a small function every iteration

Answer format: one letter

Question 28 hotspot-tiers · mapping · 1 pt · 03-aot-jit-transpilers

In HotSpot's -XX:+PrintCompilation output, give the tier level number for:
interpreter, c1-full-profile (C1 with full profiling), c2.

Keys: interpreter, c1-full-profile, c2

Answer format: one value per key

Question 29 deopt-purpose · single · 1 pt · 03-aot-jit-transpilers

Why do optimizing JITs need deoptimization?

1. To free memory used by compiled code
2. To fall back to a lower tier when a speculative assumption (type, branch, callee) turns out false, without restarting the function
3. To recompile at a higher optimization level
4. To handle exceptions thrown by the interpreter

Answer format: one letter

Question 30 transpiler-es5 · multi · 1 pt · 03-aot-jit-transpilers

Which transformations did tsc --target ES5 apply to the Lesson 0.3 example?

1. let/const became var
2. the arrow function became a function expression
3. the class became a constructor function with a prototype method
4. the type annotations were kept as comments
5. the loop was unrolled

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

Question 31 transpiler-definition · single · 1 pt · 03-aot-jit-transpilers

What distinguishes a transpiler from other compilers?

1. It never checks the program for errors
2. Its target is a high-level language that another compiler or interpreter processes further
3. It runs at run time
4. It cannot be correct in the sense of Definition 0.1.4

Answer format: one letter

Question 32 futamura-second · single · 1 pt · 03-aot-jit-transpilers

If mix is a specializer and int an interpreter for L, what is [mix]?

1. A compiled version of int
2. A compiler from L to mix's language
3. A compiler generator
4. An interpreter for mix

Answer format: one letter

Question 33 futamura-residual · text · 1 pt · 03-aot-jit-transpilers

Specialize the Lesson 0.3 stack interpreter (Algorithm 0.3.10) to the static program
ARG, PUSH 2, MUL, PUSH 1, ADD. Give the residual expression in x (write it as x*2+1 or
similar).

Answer format: a short answer

Question 34 m-times-n · number · 1 pt · 04-retargeting

For 5 source languages and 7 target machines, how many translators does a shared-IR design need?

Answer format: a number

Question 35 ir-target-dependent · single · 1 pt · 04-retargeting

Why should you not compile clang's --target=x86_64-linux-gnu LLVM IR for AArch64 with
llc -mtriple=aarch64-linux-gnu?

1. llc cannot read IR produced by clang
2. The IR already encodes x86-64 decisions — type sizes, data layout, ABI lowering, target CPU and features
3. LLVM IR has no branches that AArch64 can execute
4. It works identically; there is no reason

Answer format: one letter

Question 36 llvm-where-lookup-target · text · 1 pt · 04-retargeting

In llvm/include/llvm/MC/TargetRegistry.h (LLVM 23.1.2), which static member function of
TargetRegistry maps a target triple to a const Target *?

Answer format: a short answer

Question 37 three-phase-roles · mapping · 1 pt · 04-retargeting

Which LLVM phase makes each decision? Values: front-end, optimizer, back-end.
long-size (C long is i64 vs i32); loop-rotation (moving the test to the bottom);
register-allocation; sext-w (RISC-V sign extension of 32-bit values).

Keys: long-size, loop-rotation, register-allocation, sext-w

Answer format: one value per key

Question 38 gcc-irs-order · sequence · 1 pt · 04-retargeting

Give GCC's three intermediate representations in the order a function passes through them.

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

Question 39 gimple-three-address · number · 1 pt · 04-retargeting

How many fresh temporaries does Algorithm 0.4.5 (gimplification) create for the expression (a + b) * (c - d)?

Answer format: a number

Question 40 cranelift-block-params · single · 1 pt · 04-retargeting

In the CLIF of Lesson 0.4, what plays the role of LLVM's phi nodes?

1. Stack slots
2. Block parameters, with values passed by each branch (jump block3(v14, v10))
3. Global values (gv0, gv1)
4. Nothing: CLIF is not in SSA form

Answer format: one letter

Question 41 cranelift-isle · single · 1 pt · 04-retargeting

In Cranelift's x64 lower.isle, two rules match iadd: iadd_base_case_32_or_64_lea with
priority −5 and a load-sinking rule with priority −4. If both match, which is used?

1. The one with priority −5, because it is more general
2. The one with priority −4, because higher priority is tried first
3. Both, emitting two instructions
4. Neither; ISLE reports an ambiguity

Answer format: one letter

Question 42 tdiagram-cross · text · 1 pt · 05-bootstrapping-and-trust

On an x86 host, you compile the source of C(Oak, RISCV, Oak) with the binary
C(Oak, x86, x86). Give the result as S->T in I.

Answer format: a short answer

Question 43 tdiagram-interp · single · 1 pt · 05-bootstrapping-and-trust

You have C(C, x86, x86), the source of a bytecode VM R(BC, C), and a boot compiler
C(Oak, BC, BC) as bytecode. What must you do before the boot compiler can compile anything?

1. Nothing: bytecode runs anywhere
2. Compile the VM with the C compiler, obtaining R(BC, x86), so that BC becomes executable on the host
3. Compile the boot compiler with the C compiler
4. Rewrite the boot compiler in C

Answer format: one letter

Question 44 stage2-stage3 · single · 1 pt · 05-bootstrapping-and-trust

In a 3-stage bootstrap, the stage-2 and stage-3 compilers are bit-identical. What does this show?

1. That the compiler source is correct
2. That the stage-1 build compiled the source consistently (no miscompilation of the compiler by stage 1, and deterministic output) — but not that the source is correct or trojan-free
3. That the bootstrap compiler was correct
4. Nothing at all

Answer format: one letter

Question 45 llvm-where-bootstrap · text · 1 pt · 05-bootstrapping-and-trust

According to llvm/docs/AdvancedBuilds.md (LLVM 23.1.2), which CMake option enables a
multi-stage (bootstrap) clang build?

Answer format: a short answer

Question 46 trusting-trust-triggers · multi · 1 pt · 05-bootstrapping-and-trust

Which behaviors does Thompson's trojaned compiler binary have?

1. When compiling login, it inserts a backdoor
2. When compiling the compiler's own source, it inserts both triggers into the output
3. It modifies the compiler's source file on disk
4. It can be found by reading the compiler's source code

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

Question 47 trusting-trust-stages · number · 1 pt · 05-bootstrapping-and-trust

Starting from a trojaned binary b0 and the CLEAN compiler source, you build b1 = b0(src),
b2 = b1(src), b3 = b2(src). How many of b1, b2, b3 contain the trojan?

Answer format: a number

Question 48 ddc-conclusion · single · 1 pt · 05-bootstrapping-and-trust

Diverse double-compiling: stage1 = c_T(s_A), stage2 = stage1(s_A), and stage2 is bit-identical
to the compiler binary c_A under test. What follows?

1. c_A is correct
2. c_A is exactly the faithful self-compilation of s_A, so it contains no trojan absent from s_A — assuming c_T is trustworthy and compilation deterministic
3. c_T contains no trojan
4. s_A contains no bugs

Answer format: one letter

Question 49 ddc-determinism · single · 1 pt · 05-bootstrapping-and-trust

Which of these would make DDC report a mismatch even without any trojan?

1. The compiler source uses DATE in its version string (and SOURCE_DATE_EPOCH is not set)
2. The trusted compiler generates slower code than c_A
3. The trusted compiler is from a different vendor
4. Stage 1 is larger than c_A

Answer format: one letter

Question 50 macro-hideset · text · 1 pt · 06-toolchain

With #define X Y + 1 and #define Y X * 2, what does the preprocessor produce for X?
(tokens separated by single spaces)

Answer format: a short answer

Question 51 phase-attribution · mapping · 1 pt · 06-toolchain

Which phase reports or produces each item? Values: preprocess, lex, parse, sema, codegen,
assemble, link, load, run.
A = "fatal error: 'missing.h' file not found"; B = "use of undeclared identifier 'y'";
C = "undefined reference to `sum'"; D = "error while loading shared libraries: libsum.so";
E = "invalid suffix 'x' on integer constant"; F = "Floating point exception" from 10 / z.

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

Answer format: one value per key

Question 52 reloc-value · number · 1 pt · 06-toolchain

An R_X86_64_PLT32 relocation with addend A = −4 is applied at P = 0x1157 for a symbol at
S = 0x1180. What 32-bit value does the linker write (give it in decimal)?

Answer format: a number

Question 53 llvm-where-elf-writer · text · 1 pt · 06-toolchain

In llvm/lib/MC/ELFObjectWriter.cpp (LLVM 23.1.2), which type (declared with struct)
computes the symbol table and writes the section headers of an ELF object?

Answer format: a short answer

Question 54 link-errors · single · 1 pt · 06-toolchain

main.c declares int sum(int); and calls it; you run clang main.c -o prog without sum.c.
Which component reports the error?

1. The preprocessor
2. The compiler's semantic analysis
3. The linker, as "undefined reference to `sum'"
4. The loader, at run time

Answer format: one letter

Question 55 loader-exit-127 · single · 1 pt · 06-toolchain

./prog2 fails with "error while loading shared libraries: libsum.so: cannot open shared
object file" and exit status 127. Which statement is true?

1. The program was linked incorrectly and must be recompiled
2. The dynamic linker could not find a NEEDED library at startup; setting LD_LIBRARY_PATH (or a runpath) fixes it
3. main returned 127
4. libsum.so contains a bug

Answer format: one letter

Question 56 crt-order · sequence · 1 pt · 06-toolchain

Order these steps of a dynamically linked C program's life: main, _start, exit,
__libc_start_main, init_array, fini_array.

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

Question 57 startup-sequence · single · 1 pt · 06-toolchain

Which object file provides _start for clang's default PIE executables on Linux?

1. crtbeginS.o
2. Scrt1.o
3. crti.o
4. libc.so.6

Answer format: one letter