Flashcards — Chapter 24¶
72 cards. Review them with spaced repetition in the terminal (./course flash 24) or export them to Anki (./course flash export 24). Here, click a card to reveal its back.
staged-pipeline¶
What is the enabling relation between two passes?
p enables q when p removes a fact that q needs absent (p establishes q's precondition) or p adds a fact that q removes (p creates q's opportunities). The enabling graph's topological order is a stage (Definition 24.1.2, Algorithm 24.1.4).
What does pebblec -O1 run in your build?
The course pipeline: every PEBBLE_COURSE_PIPELINE_STEP by order key, i.e. function(pebble-strength) (Ch 12, key 1210) then pebble-o1 (Ch 24, key 2400), which runs the stages of your designCoursePipeline.
Why is the inliner placed after a first scalar cleanup and before the fixpoint block?
Cleanup first so the inliner's cost model sees small callees (Lesson 20); inlining exposes the callee's allocas, constants and call sites to the caller, which only the passes run after it can use (constraints C3, C6 of E1).
Theorem 24.1.10 in one sentence
A round that runs the passes in a topological order of the enabling graph leaves no pass enabled by another pass of the same round; anything still enabled needs a second round (facts re-introduced by the passes' "adds").
canonicalization¶
What is a canonicalizing pass?
A cheap pass that establishes a form (no promotable allocas, loop-simplify + LCSSA, folded constants) that other passes assume; it is idempotent, so re-running it after a stage that may break the form is safe (Definition 24.1.3).
What is a canonicalization gate (Algorithm 24.1.5)?
Re-running the canonicalizing pass at the start of every stage whose passes need the form, instead of trusting that no earlier pass broke it; cost one cheap pass per stage, benefit no blocked pass (Proposition 24.1.8).
Name three forms your -O1 passes assume, and who establishes each
SSA (no promotable allocas): pebble-mem2reg; loop-simplify form and LCSSA: LLVM's loop-simplify and lcssa; rotated loops (latch is the exiting block): loop-rotate, before pebble-unroll.
Why does inlining break the SSA canonical form?
It copies the callee's entry-block allocas (and its loads/stores) into the caller, so gvn/sccp see memory again until mem2reg runs a second time.
fixpoint-iteration¶
How does pebble-o1 detect that a round changed nothing?
It hashes the module after each round and compares with the previous hash (Algorithm 24.1.7); a stage stops early at the first unchanged round, and never runs more than MaxRounds.
Why does a fixpoint stage terminate (Theorem 24.1.12)?
In the abstract model with an acyclic enabling graph, after round r every pass of rank < r is settled (never changes the facts again), so all passes are settled after d + 1 rounds and round d + 2 is stable, d = the longest enabling path; for the concrete compiler, and for cyclic graphs, the round limit MaxRounds is the only guarantee.
How does LLVM's devirt<4> differ from a hash-based fixpoint?
Its witness of change is a devirtualized indirect call (DevirtSCCRepeatedPass keeps value handles on the call sites) instead of a module hash, and its round limit is MaxDevirtIterations = 4.
What is the trade-off in the reference design's MaxRounds of 2–3?
Measured rounds per stage are 1–3 (1.4 on average over the benchmarks; 3 only on order.pbl's simplify stage); a higher limit only spends compile time on modules that reach the limit, a lower one leaves opportunities that the second round's gvn/sccp would take.
static-elimination¶
What is static check elimination?
Removing a run-time check whose condition is provable at compile time from facts (SCEV ranges, dominating conditions, prior checks); sound by Theorem 24.2.8 because the check's outcome is the same on every execution.
Which two sources does ScalarEvolution::isKnownPredicateAt combine?
The context-free SCEV facts (isKnownPredicate) and the conditions of branches that dominate the context block (isBasicBlockEntryGuardedByCond).
bench-checks: 14 → 12 → 3 traps at -O0/-O1/-O2. What do the three numbers mean?
The number of pebble_trap call sites left in the IR: -O0 keeps every check, your -O1 proves two with pebble-bce/sccp, LLVM's -O2 proves eleven with SCEV, dominating conditions and inlining.
multiversioning¶
What is loop versioning?
Cloning a loop into L_pi (optimized under predicate pi) and L (original), guarded by a run-time test of pi in the preheader; live-out values get a phi at the join of the two exits (Algorithm 24.2.5).
How does Clang implement target_clones("avx2","default")?
Two bodies plus a resolver calling __builtin_cpu_supports, exported as an IFUNC symbol; the dynamic loader runs the resolver once (IRELATIVE relocation) and every call goes through the chosen pointer.
Cost profile of multiversioning in one line
Compile time and code size grow with the number of variants (v·s); run time pays one test per region entry (IFUNC: once per process); it never deoptimizes because every variant is correct on its own.
speculation¶
What is a guard, and what is a deoptimization point?
A guard is a cheap test of a speculative assumption; a deoptimization point is where a failing guard transfers control to unoptimized code with the state map needed to rebuild its frame (Definition 24.2.6).
What does a statepoint/stack-map record hold for a deoptimization?
The instruction address and, for every live value the unoptimized code needs, a location kind and value: Register, Direct, Indirect (base+offset), Constant or ConstantIndex.
Theorem 24.2.10 (exactness of deoptimization) in one sentence
If the state map records every variable the unoptimized code reads at the point, and the guard is checked before any effect that depends on the assumption, the deoptimized execution continues exactly as the unoptimized program would.
lljit¶
What does lookup do in ORC (Algorithm 24.3.3)?
It searches the JITDylibs in link order for the symbols, materializes (compiles and links) every unit that provides a not-yet-materialized one, and returns their addresses; a unit is materialized at most once.
Why does pebble-jit publish the runtime with absoluteSymbols?
The runtime is linked into the statically linked driver, so DynamicLibrarySearchGenerator cannot find it via dlsym; absoluteSymbols defines the names with the process's own addresses, portably (no -rdynamic).
What is a JITDylib and why does each run get a fresh one?
A symbol table with a link order; a fresh one per module lets many modules define pebble_main without clashing, each resolving the runtime through the main dylib in its link order.
lazy-compilation¶
What is a lazy reexport (Definition 24.3.4)?
A stub for f that jumps through a pointer initially aimed at a trampoline; the first call enters the LazyCallThroughManager, which compiles f, writes its address into the pointer and jumps to it; later calls are one indirect jump.
Eager vs lazy on used/unused/also_unused/main: how many bodies are compiled?
Eager (addIRModule): 4, the whole module on the first lookup. Lazy (addLazyIRModule): 2, pebble_main and used, because a function is compiled on its first call (Proposition 24.3.8).
Where does the trampoline jump when the implementation symbol cannot be found?
To the LazyCallThroughManager's ErrorHandlerAddr (returned by reportCallThroughError after reporting the error), not to a null pointer.
tiering¶
What does ORC's ReOptimizeLayer do?
Instruments each function with a call counter; at CallCountThreshold (10) it recompiles the unit with a user transformation and redirects the symbol through a RedirectableSymbolManager, so callers see the new code on their next call (Algorithm 24.3.6).
Why can ReOptimizeLayer without deoptimization only apply sound optimizations at the higher tier?
Redirection swaps the callee for future calls; there is no way to transfer a running activation or to undo an assumption, so tier-1 code must be correct on every input (Theorem 24.2.10 is what a speculative tier needs).
HotSpot C1/C2 vs the ORC layer: what is the same, what differs?
Same shape: cheap tier, counters, recompile hot code, redirect; HotSpot adds profile-guided speculation with deoptimization and on-stack replacement, and its thresholds are thousands of calls, not 10.
dwarf¶
What are the three parts of DWARF a debugger needs to show a variable?
The DIE tree (DW_TAG_subprogram, DW_TAG_variable with type and location), the line table (address ↔ line, is_stmt, prologue_end) and location expressions or lists (where the value is, per address range).
Evaluate DW_OP_fbreg -24
Push frame_base − 24; with no DW_OP_stack_value the variable is in memory at that address (a stack slot), which is what pebble-debugify's #dbg_declare records become at -O0.
What does DW_OP_stack_value change?
The expression's result is the variable's value itself, not the address of its storage; used for values that were folded or recomputed (e.g. a constant, or reg + 1).
What is a location list?
A list of address ranges, each with a location expression, for a variable whose place changes across the function after optimization; ranges with no entry mean "optimized out" (Definition 24.4.4).
dibuilder¶
Which metadata does pebble-debugify attach to a module (Algorithm 24.4.6)?
One DICompileUnit (llvm.dbg.cu) and the module flags Debug Info Version 3 and Dwarf Version 5; one DISubprogram per function (!dbg); a DILocation on every instruction; DILocalVariables with #dbg_declare (allocas) and #dbg_value (named SSA defs).
Why must a pass call DIBuilder::finalize()?
It replaces the temporary nodes (each subprogram's retainedNodes, the compile unit's lists) with the real ones; without it the module holds temporary metadata that the verifier rejects.
Where does pebblec's debug line information come from, and why is it synthetic?
Chapter 11's code generator does not carry PIR's @line:col into LLVM IR, so pebble-debugify assigns a fresh line per instruction, as LLVM's own debugify does; the variable names are real (from the alloca and SSA names).
debug-records¶
#dbg_declare vs #dbg_value
declare: the variable lives at this address for the whole function (an alloca, -O0); value: from this point on the variable's value is this SSA value (after mem2reg, at every store and phi); a deleted value becomes #dbg_value(poison), "optimized out".
Why did LLVM 19 replace llvm.dbg.value calls by records?
Calls were instructions, so instruction counts, iteration and heuristics differed between -g and non-g builds; records hang off instructions via DbgMarker and are invisible to such code (Proposition 9.6.11).
What does LiveDebugValues compute from debug records?
Per variable, the machine location (register, spill slot) at every instruction after register allocation, joined across control flow, and emitted as location lists; a call clobbers caller-saved registers, a spill keeps the slot as a fallback (Algorithm 24.4.7).
refcount¶
Naive reference counting rule (Algorithm 24.5.3)
Every new reference to an object retains (+1), every overwritten or scope-ending reference releases (−1), free at 0; the allocation's +1 is owned by the variable that receives it.
What are owned and guaranteed conventions in Swift?
Owned: the caller passes +1 and the callee is responsible for releasing; guaranteed: the caller keeps the object alive for the call, no retain/release at all; the choice moves the count traffic to where it is cheapest.
The weakness of reference counting, and the three responses
Cycles are never freed; responses: weak references (Swift, Objective-C), a cycle collector (CPython's gcmodule), or accepting the leak.
tracing-gc¶
What is a safepoint and what must the compiler emit for a precise moving collector?
A point where the collector may run (calls, loop back-edges); a stack map listing every live pointer's location, with (base, derived) pairs for interior pointers, so the collector can find roots and relocate them (Definition 24.5.5, Algorithm 24.5.6).
Which pointers are roots at a call?
The pointer values live across the call: defined before it and used after it; a dead pointer must not be reported (it would retain garbage or, worse, be updated to a moved address the code never reads).
Why (base, derived) pairs in gc.statepoint?
A moving collector adjusts an interior pointer by the same delta as its base; only the base identifies the object, and RewriteStatepointsForGC::findBasePointers computes it for every live value, phis included.
ownership¶
Ownership in one line
Every value has one owner; a move transfers ownership and invalidates the source; a borrow (&, &mut) lends it for a lifetime; drops are inserted where the owner's scope ends: no run-time bookkeeping.
E0382 vs E0502
E0382: use of a moved value (the initialization check); E0502/E0499: a borrow that conflicts with a live borrow (the borrow-conflict check); both are errors of Algorithm 24.5.8 on MIR.
What do non-lexical lifetimes change?
A borrow is live only until the last use of the reference, computed on MIR's control-flow graph, so let r = &v; use(r); v.push(1) compiles; the conflict rules themselves are unchanged.
What is drop elaboration?
Turning MIR's drop(x) into nothing (never initialized), an unconditional drop (always initialized) or a drop guarded by a run-time drop flag (maybe initialized), decided by the MaybeInitializedPlaces / MaybeUninitializedPlaces dataflow (Algorithm 24.5.8).
regions¶
What is a region (arena) and what does it cost per object?
A block of memory into which objects are allocated by bumping a pointer and which is freed as a whole when it ends; per object: one pointer bump, no header, no count, no scan.
Tofte–Talpin region inference, in one sentence
Infer, from the types, the smallest lexically scoped region that contains every use of each value; allocate the value there; free the region at its letregion end.
The space-leak problem of regions and its fix
A loop allocating per iteration fills one region until it ends; storage-mode analysis (the ML Kit) lets an allocation reset the region first when nothing in it is live.
funclets¶
What is a funclet?
A handler (catch or cleanup) outlined as its own small function that the runtime calls while the throwing frame is still live, sharing the parent's frame through a frame pointer; LLVM represents it with catchswitch/catchpad/cleanuppad and parent tokens (Definition 24.6.1).
What does WinEHPrepare::colorFunclets compute, and what follows it?
The set of funclets each block belongs to (its colors); blocks with two colors are cloned by cloneCommonBlocks until every block has one, then state numbers are assigned (Algorithm 24.6.3, Theorem 24.6.10).
Why is catchswitch not a funclet?
It is the dispatch point after a try: it selects among its catchpads and forwards to its unwind label on no match; it keeps the parent's color and produces a token that its catchpads consume.
wasm-eh¶
How does WebAssembly EH differ from Itanium tables?
No unwinder library and no tables: try/catch/delegate/rethrow are structured instructions and the engine unwinds; every frame with a handler stops the engine, and the C++ personality is called from the landing code (Definition 24.6.4).
What does WasmEHPrepare insert after a catchpad?
wasm.catch for the exception pointer, the landing-pad index and LSDA into __wasm_lpad_context, a call to _Unwind_CallPersonality, and a load of the selector; nothing for a lone catch (...) or a cleanuppad (Algorithm 24.6.5).
What is delegate for?
A throw inside a handler's own nested try (e.g. around __cxa_end_catch) must bypass the enclosing handlers: delegate forwards it to the try at the given label depth without running any code in between.
eh-optimization¶
How does FunctionAttrs infer nounwind (Algorithm 24.6.7)?
Bottom-up over call-graph SCCs: an SCC is nounwind if no instruction in it may throw except direct calls inside the SCC (InstrBreaksNonThrowing with IncludePhaseOneUnwind); then every function of the SCC is marked.
When may invoke become call?
When the callee is nounwind: no execution unwinds, so both forms agree and the landing pad loses its predecessor; simplifycfg's removeUnwindEdge does it and the unreachable pad is deleted (Proposition 24.6.9).
Is a function with a catch-all landing pad that never resumes nounwind?
Yes: the attribute is about exceptions leaving the function; an invoke whose pad catches everything and returns lets nothing escape (the box's other).
What must the inliner do when inlining through an invoke?
Turn every may-throw call of the copied body into an invoke to the caller's landing pad, replace the callee's resumes by branches to that pad, and merge the pads' clauses (HandleInlinedLandingPad, Algorithm 24.6.8).
mlir¶
What is a dialect, and what is a conversion target?
A dialect is a namespace of operations with a verifier in MLIR's single IR; a conversion target assigns Legal / Dynamic(φ) / Illegal (and recursive legality) to operations and dialects (Definition 24.7.1).
Partial vs full conversion
Partial: legalize what patterns reach and keep pre-existing operations that are not marked Illegal (mixed-dialect IR is fine); full: fail unless every operation is legal at the end.
What does OperationLegalizer::legalize do, in order?
Skip if ignored; succeed if the target says legal (marking nested ops ignored when recursively legal); try folding; try patterns by benefit, recursively legalizing what each creates, rolling back on failure (Algorithm 24.7.2).
compcert¶
What does CompCert's main theorem say?
If transf_c_program p = OK tp, then Asm.semantics tp backward-simulates Csem.semantics p: every behavior of the compiled program is a behavior of the source (or the source goes wrong first), checked in Coq (Theorem 24.7.8).
What is a forward simulation with a measure (Definition 24.7.4)?
A relation between source and target states, indexed by a well-founded order, such that each source step is matched by one or more target steps, or by zero steps with the index decreasing: no infinite stuttering.
Why does CompCert prove forward simulations and conclude backward ones?
Forward proofs are by cases on source steps, which pass authors understand; determinism of the target (Asm.semantics_determinate) turns a forward simulation into a backward one (forward_to_backward_simulation).
alive2¶
What does alive-tv check?
That the target function refines the source: for every input, every target behavior is a source behavior or the source has UB there, encoded in SMT with Alive2's memory model, loops unrolled to a bound (Proposition 24.7.6).
Why does Alive2 report a false alarm after inlining?
A call to a function it does not inline is an unknown call that may not return; when the target has the value inlined, the target is "more defined": validate per function before interprocedural stages (Algorithm 24.7.5 step 4).
Fuzzing, translation validation, verified compilation: what does each guarantee?
Fuzzing: no difference on the programs tried; translation validation: this run refines its input, under the tool's assumptions; verification: every run of the compiler preserves semantics, by a machine-checked proof.