Flashcards — Chapter 0¶
93 cards. Review them with spaced repetition in the terminal (./course flash 0) or export them to Anki (./course flash export 0). Here, click a card to reveal its back.
multi-pass¶
What does it mean for a target program q to refine a source program p?
Either p may exhibit undefined behavior (ub ∈ Beh(p)), or every observable behavior of q is a behavior of p: Beh(q) ⊆ Beh(p). (Definition 0.1.2)
Why is a pipeline of correct passes correct?
Refinement is transitive (Lemma 0.1.3): if P2(P1(p)) ⪯ P1(p) and P1(p) ⪯ p then P2(P1(p)) ⪯ p; induction over the passes (Theorem 0.1.6).
Invariant of a pass manager with cached analyses?
Before each pass runs, every cached analysis result equals the analysis of the current IR — maintained because passes report truthfully which analyses they preserve.
How many times can Algorithm 0.1.8 compute one analysis for k passes?
At most k times: at most once per pass, because a result computed during a pass stays cached until that pass returns (Proposition 0.1.21).
Which LLVM function builds the default<O2> pipeline?
PassBuilder::buildPerModuleDefaultPipeline in llvm/lib/Passes/PassBuilderPipelines.cpp (buildO0DefaultPipeline for -O0).
single-pass¶
What is backpatching?
Emitting a forward jump with a hole and filling in its target when the target is emitted (Algorithm 0.1.10).
Which language rule makes one-pass compilation possible?
Declare before use (with forward declarations for mutual recursion): every decision at a token depends only on what has been read (Definition 0.1.9).
Backpatch invariant?
Every hole is held by exactly one active Stmt activation and is patched before that activation returns (Lemma 0.1.17).
Cost and memory of a one-pass compiler?
O(n) time; memory O(nesting depth + symbol table) — but no global optimization (every variable stays in memory in TCC's output).
query-based¶
What is early cutoff in a query-based compiler?
A recomputed node whose fingerprint equals its previous one is marked green, so nodes depending on it are not recomputed.
What does try_mark_green check?
That every dependency recorded last session is green, in the recorded order (recomputing dependencies when needed); then the node's old value is reused without executing it.
When is red-green reuse unsound?
When a provider reads state outside the query system (globals, clock, untracked files): its recorded dependencies are incomplete (Theorem 0.1.19's precondition).
Bookkeeping cost of one incremental session?
O(|V| + |E|) over the previous dependency graph, plus the providers actually re-executed.
mlir¶
What is progressive lowering in MLIR?
Rewriting operations of high-level dialects (scf, linalg) into lower ones (cf, arith, llvm) step by step, each step a dialect conversion with its own legality target.
Why does dialect conversion terminate?
If every pattern replaces an operation by operations of strictly smaller measure (e.g. dialect level), the multiset of measures decreases (Dershowitz–Manna) — Theorem 0.1.20.
What replaces phi nodes in MLIR's cf dialect and in Cranelift?
Block arguments: a block declares parameters and each branch passes values to them.
tree-walker¶
What is a tree-walking interpreter?
An interpreter that evaluates the syntax tree recursively, one case per construct — a big-step semantics read as code (Algorithm 0.2.3).
Tiny: what are 7 / 0, 7 % 0 and INT64_MIN / -1?
0, 7 and INT64_MIN — total definitions that keep a == (a/b)*b + a%b.
Cost of a tree walker?
Θ(N) node visits, each a function call + switch on the node kind + pointer loads; the slowest engine in the lab (≈ 1.6–1.9× slower than the switch VM).
How is the tree walker's correctness proved?
Structural induction on expressions; induction on derivation height for statements (while has a premise for the same loop in a later state) — Theorem 0.2.11.
stack-vm¶
Stack code for a + b * c?
load a, load b, load c, mul, add (postorder: left operand, right operand, operator).
Stack depth recurrence of postorder code?
D(leaf) = 1, D(−e) = D(e), D(l ⊕ r) = max(D(l), 1 + D(r)); for && / ||: max(D(l), D(r)).
Ershov number of l ⊕ r?
max(E(l), E(r)) if they differ, else E(l) + 1 — the minimum stack depth when either operand may go first.
How many stack instructions for an expression with ℓ leaves and o operators?
ℓ + o (one per leaf, one per operator); the register VM needs only o.
register-vm¶
What is three-address code?
Instructions of the form r ← a ⊕ b with at most one operator; operands are registers (variables, temporaries) or constants.
Instructions for s = s + i: stack VM vs register VM?
Stack: load s, load i, add, store s (4). Register: s ← s + i (1), with destination passing.
What did Shi et al. measure for register vs stack VMs?
Translating JVM stack code to register code eliminated more than 47% of executed VM instructions for roughly 25% larger code, and cut run time by 32.3% with switch dispatch on a Pentium 4 (VEE 2005 abstract).
Which production VMs are register-based?
Lua 5.x (lvm.c, iABC format), V8 Ignition (with an accumulator), Dalvik.
dispatch¶
What is direct threaded code?
Each instruction stores its handler's address; each handler ends with its own indirect jump to the next handler (Bell 1973).
Switch-dispatch mispredictions in the last-target model?
M_sw = 1 + #{i ≥ 2 : t_i ≠ t_{i−1}} — the one shared site hits only when an opcode repeats.
Why does threaded dispatch predict better (Ertl–Gregg)?
Each handler has its own branch site that sees only that opcode's successors, which often repeat in loops.
How does CPython dispatch?
Token threading with computed goto (USE_COMPUTED_GOTOS, Python/opcode_targets.h) when compiled with GCC/clang; switch otherwise.
What are superinstructions and replicated handlers?
Superinstructions fuse frequent sequences (LOAD_FAST__LOAD_FAST); replication gives each static instruction its own handler copy so its dispatch site predicts well.
aot¶
What is AOT compilation?
Translating the whole program to machine code before it runs; compile time is paid once, at build time.
What does profile-guided optimization change and not change?
It changes choices between correct translations (layout, inlining); it never changes the set of behaviors, so a bad profile only costs speed.
What did clang -O2 do to the sum loop?
IndVarSimplify rewrote the exit value in closed form (n(n−1)/2, computed in 33-bit arithmetic) and the loop was deleted.
method-jit¶
Break-even number of runs for compiling?
N* = c / Δ, with c the compile cost and Δ = r_interp − r_compiled per run.
Competitive ratio of 'compile after about c/Δ calls'?
At most 2 (ski rental): extra cost ≤ 2·min(NΔ, c); no deterministic rule beats 2 − Δ/c.
Which LLVM class does the lab's JIT use?
orc::LLJIT (llvm/lib/ExecutionEngine/Orc/LLJIT.cpp): addIRModule, then lookup, then toPtr.
tracing-jit¶
What is a trace in a tracing JIT?
A straight-line recording of the operations one hot loop iteration executed, with guards for every check made on the way.
What happens when a trace guard fails?
A side exit rebuilds the interpreter state from the trace's registers (exit map) and resumes interpretation at that point.
Pathology of tracing JITs?
Branchy loops: b independent ifs give 2^b paths, so many traces (trace explosion).
What is meta-tracing (PyPy)?
Tracing the language's interpreter (written in RPython, with jit_merge_point hints) rather than the program: a JIT derived from an interpreter.
tiered¶
What is deoptimization?
Transferring execution from optimized code whose speculation failed to an equivalent frame of a lower tier, using exact metadata.
HotSpot tier levels in -XX:+PrintCompilation?
0 interpreter; 1–3 C1 (3 = with full profiling); 4 C2. '%' marks OSR compilations.
V8's tiers?
Ignition (bytecode interpreter) → Sparkplug (baseline, one pass) → Maglev (fast optimizing) → TurboFan (optimizing).
What must optimizing tiers avoid for deoptimization to be sound?
Moving side effects before a guard: the interpreter would re-execute them after deoptimizing.
transpiler¶
What is a transpiler?
A compiler whose target is a high-level language compiled or interpreted further (TypeScript → JS, Nim → C, Cfront C++ → C).
What does tsc --target ES5 do to let/const, arrows and classes?
let/const → var, arrow functions → function expressions, classes → constructor functions plus prototype methods; types are erased.
Why is naive let → var desugaring wrong in loops?
let creates a binding per iteration; closures capturing it see different values, which a single var would merge.
futamura¶
First Futamura projection?
[mix] is a compiled version of p: specializing an interpreter to a program compiles it.
Second and third Futamura projections?
Defining equation of a specializer mix?
[ [[mix]](q, s) ] = [q] for all programs q, static inputs s, dynamic inputs d.
How did clang -O2 perform the first projection?
Inlining the interpreter, fully unrolling its loop over the constant program, and folding the dispatch left x*(x+3)+1.
retargeting¶
m × n vs m + n?
Direct compilers for m languages and n targets: m·n. Through a shared IR: m front ends + n back ends = m + n.
Is clang's LLVM IR target-independent?
No: type sizes (long), data layout, ABI lowering and target features are decided by the front end and recorded in the module.
What was UNCOL?
Strong et al.'s 1958 proposal of a universal intermediate language between all languages and machines — the m + n argument.
llvm-three-phase¶
LLVM's three phases?
Front end (source → LLVM IR), optimizer (IR → IR), back end (IR → machine code); LLVM IR is the only interface between them.
How does llc find the back end for a triple?
TargetRegistry::lookupTarget(triple) returns the registered Target; it creates a TargetMachine.
How many targets did llc 23.1.2 register in the course container?
48 (llc --version, 'Registered Targets').
gcc¶
GCC's three IRs, in order?
GENERIC (front-end trees) → GIMPLE (three-address, then SSA) → RTL (register-transfer lists), with targets described in .md files.
What does gimplification do?
Flattens nested expressions into three-address statements with fresh temporaries and turns control constructs into labels and gotos.
Where does GCC switch from GIMPLE to RTL?
pass_expand (see gcc/passes.def).
cranelift¶
What is ISLE?
Cranelift's DSL for instruction-selection rules: (rule prio (lower pattern) result), compiled into decision trees; small enough to verify with SMT.
What is Cranelift built for?
Fast compilation for JIT/AOT in Wasm runtimes (Wasmtime) and as a rustc debug back end; back ends x86-64, aarch64, s390x, riscv64.
When is rule-based lowering correct?
When every rule's output refines its pattern and the rules cover every instruction (Theorem 0.4.10).
tdiagram¶
T-diagram compile rule?
Compiling X (written in L) with C(L, M, I), I executable, gives X written in M; source and target of X are unchanged (Theorem 0.5.4).
What does compiling C(Pebble, ARM, Pebble) with C(Pebble, x86, x86) give?
C(Pebble, ARM, x86): a cross-compiler that runs on x86 and emits ARM code.
When is a language executable on host H?
If it is H, or an available interpreter for it is written in an executable language (finite chain) — Definition 0.5.3.
self-hosting¶
What is a self-hosting compiler?
One written in the language it compiles (Go, Rust, GCC, OCaml); building it needs an existing compiler (bootstrap).
Why must stage 2 equal stage 3?
If stage 1 is a correct build of a correct, deterministic compiler source s, both stages are [s] (Theorem 0.5.14).
Go's bootstrap stages?
toolchain1 = new compiler built by the old Go; toolchain2 built by toolchain1; toolchain3 built by toolchain2 (src/cmd/dist/build.go).
trusting-trust¶
Thompson's two triggers?
T1: when compiling login, insert a backdoor. T2: when compiling the compiler, reinsert T1 and T2 — so clean sources stay infected.
Does stage2 = stage3 detect Thompson's trojan?
No: a self-reproducing, deterministic trojan makes every stage infected and stages can still match (Theorem 0.5.15).
What does Thompson's lecture conclude?
You cannot trust code you did not totally create yourself: source inspection cannot find a trojan that lives only in binaries.
ddc¶
Diverse double-compiling in two steps?
stage1 = trusted compiler c_T (source s_A); stage2 = stage1(s_A); compare stage2 with the binary under test c_A bit for bit.
What does a DDC match prove, and under what assumption?
c_A is the faithful self-compilation of s_A, assuming c_T has no trojan aimed at s_A and compilation is deterministic (Theorem 0.5.16).
Why did gcc- and clang-built TCC produce identical stage-2 objects?
Both stage-1 binaries are correct builds of the same deterministic source, so both compute [tcc.c].
preprocessor¶
What stops #define N N + 1 from expanding forever?
Hide sets: tokens produced by expanding N carry N in their hide set and are never expanded as N again.
Output of clang -E for N with #define N N + 1?
N + 1
Why does macro expansion terminate?
Each expansion replaces a token by tokens with strictly larger hide sets, bounded by the number of macros — a well-founded multiset measure (Theorem 0.6.11).
assembler¶
What is a relocation?
A record (section, offset, type, symbol, addend) telling the linker which bytes to patch once the symbol's address is known.
Value of R_X86_64_PC32 / PLT32?
S + A − P; with A = −4 the rip-relative operand then points at S.
Why does an assembler need two passes (or relaxation)?
Forward references: label addresses are known only after all instruction lengths are; jumps with short and long forms need iteration.
linker¶
What errors does only the linker report?
Undefined references and multiple definitions of strong symbols: each object compiled fine alone.
Linker resolution rule for strong and weak symbols?
At most one strong definition (else error); a strong one beats weak ones; with only weak ones the first wins.
Why does cc -lm main.o fail but cc main.o -lm work?
Archives are searched only where they appear on the command line, for symbols undefined at that point.
loader¶
What do PLT and GOT do?
A call to an imported function goes to a PLT stub that jumps through a GOT slot; with lazy binding the slot first points to the resolver.
What does 'error while loading shared libraries' mean?
The dynamic linker could not find a NEEDED library at startup; the program linked fine; exit status 127.
Which segment names the dynamic linker?
PT_INTERP, e.g. /lib64/ld-linux-x86-64.so.2 on x86-64 Linux.
crt¶
What runs before main?
_start (crt1/Scrt1.o) → __libc_start_main → .init_array constructors → main; then exit runs atexit handlers and .fini_array.
Which crt files does clang add on Linux, in order?
Scrt1.o, crti.o, crtbeginS.o, (your objects), -lgcc -lc ..., crtendS.o, crtn.o.
How can a program skip destructors?
By calling _exit (or crashing): only exit() runs atexit handlers and .fini_array.