Flashcards — Chapter 11¶
75 cards. Review them with spaced repetition in the terminal (./course flash 11) or export them to Anki (./course flash export 11). Here, click a card to reveal its back.
sdt¶
What is syntax-directed translation of an expression?
A recursive walk that emits code for the operands, then one instruction whose result is a fresh temporary; the translation of a node is a function of its children's translations (Irons 1961; Algorithm 11.1.3).
Why are the temporaries of syntax-directed translation already in SSA form?
Each temporary is created and assigned exactly once, by the instruction for its node, and used only by its parent, which is emitted after it in the same block (Lemma 11.1.4). Only source variables need phis.
How much code does syntax-directed translation emit for an expression of e nodes?
O(e): one instruction (plus its checks) per operator node, in one walk; no phis, because temporaries never cross a join.
allocas-mem2reg¶
What is the allocas + mem2reg strategy?
The front end gives every local an alloca in the entry block and uses load/store for every read and write; LLVM's mem2reg promotes each promotable slot to SSA values, placing phis at the iterated dominance frontier of its stores (Clang, Kaleidoscope; Algorithm 11.1.6).
When is an alloca promotable by mem2reg?
It is a scalar alloca (in practice in the entry block) used only by loads and stores of its own type, whose address never escapes: no GEP, no call argument, no store of the pointer itself (Definition 11.1.5).
Which phis does mem2reg avoid by computing live-in blocks?
Phis at dominance-frontier blocks where the variable is dead: it places phis only in the IDF blocks where the slot is live-in, so the result is pruned SSA (ComputeLiveInBlocks; Theorem 11.1.7).
braun¶
What is a sealed block in on-the-fly SSA construction?
A block all of whose predecessors are known; no edge into it will be added. Reading a variable in an unsealed block creates an incomplete phi, filled when the block is sealed (Definition 11.1.8).
What is a trivial phi, and what replaces it?
A phi whose operands, ignoring itself, are all one value w (or none). It is replaced by w (poison if none), and phis that used it are re-checked, since they may become trivial too (Algorithm 11.1.9).
What does Braun et al.'s construction guarantee on reducible CFGs?
Minimal SSA: with trivial-phi removal, no more phis than Cytron et al.'s minimal SSA (Theorem 11.1.11). Pebble's lowering only creates reducible CFGs (Proposition 11.1.12).
jumping-code¶
What does JC(e, t, f) emit for e = e1 && e2?
A new block m; JC(e1, m, f); then in m, JC(e2, t, f). No value is computed and no join is created (Algorithm 11.2.2).
How does jumping code handle !e?
It swaps the targets, JC(e, f, t), and emits nothing.
How many blocks and edges does jumping code need for a condition with n atoms and no negation cost?
Each atom ends in one conditional branch (2n edges); each binary && or || adds one block, so n − 1 new blocks besides the entry and the targets (Proposition 11.2.4).
bool-values¶
What is the boolean-value strategy for a condition?
Evaluate every atom and combine the i1 results with and/or/xor (or select) in straight-line code, then one branch (Algorithm 11.2.6).
When is the boolean-value strategy equivalent to short-circuit evaluation?
When every operand that short-circuit evaluation might skip is speculatable: no side effects, no traps, no UB when evaluated anyway (Definition 11.2.5, Theorem 11.2.7).
Why can boolean values beat jumping code on random inputs?
They have no data-dependent branches to mispredict; jumping code pays a misprediction per unpredictable atom. In the lab, or-of-and costs 6.51 ns as jumping code vs 2.19 ns as values on random inputs, and about the same on repeated ones.
jump-table¶
What is a jump table lowering of a switch?
One unsigned range check x − min ≤ max − min, then an indirect jump through a table with one entry per value of [min, max]; holes point to the default (Algorithm 11.3.3).
Why does one unsigned comparison implement the range check of a jump table?
x − min computed with wraparound is below max − min + 1 as an unsigned number exactly when min ≤ x ≤ max (Lemma 11.3.2); values below min wrap to huge numbers.
What does a jump table cost in time and space?
O(1) dispatch (a compare, a load, an indirect jump) and O(R) table space for range R; LLVM requires density n/R ≥ 10% (40% when optimizing for size) and at least 4 entries.
binary-search¶
How does binary-search switch lowering work?
Sort the case values, compare x with the median, and recurse on each half; leaves test the remaining values (Algorithm 11.3.4; Hennessy–Mendelsohn, Bernstein).
How many comparisons does a balanced search over n cases need on any path?
At most ⌈log₂ n⌉ + 1 (Theorem 11.3.5), independent of the range of the values.
What must a binary search on switch values respect about signedness?
The comparisons must use the signedness of the case values' order: a switch on a signed integer is sorted and compared with signed predicates (slt), otherwise negative cases land in the wrong half.
bit-tests¶
What is the bit-test lowering of a switch?
When max − min < 64: compute 1 << (x − min) once and test it against one mask per destination (the bits of that destination's cases), after a range check (Algorithm 11.3.6).
How is the mask of a destination in bit-test lowering computed?
Bit (v − min) is set for every case value v that goes to that destination.
When does LLVM prefer bit tests over a jump table?
When the cluster fits in a machine word and has few destinations (at most 3) with enough cases (isSuitableForBitTests); then buildJumpTable declines the range in favor of bit tests.
llvm-switch¶
What does LLVM do with an IR switch during instruction selection?
SelectionDAGBuilder::visitSwitch sorts and merges the cases into range clusters, forms jump-table clusters (a dynamic program) and bit-test clusters, then emits a balanced binary tree over the clusters (Algorithm 11.3.7).
What does LLVM's jump-table partition minimize?
The number of clusters, a Kannan–Proebsting dynamic program over the sorted cases (Theorem 11.3.8); among equally small partitions it prefers the one with more table entries and fewer ranges (the score).
What does LLVM skip when lowering a switch at -O0?
The jump-table dynamic program and bit-test clustering; it only merges adjacent cases into ranges and builds the tree.
lvalue-rvalue¶
What is the difference between a place and a value in lowering?
A place expression (variable, p.f, p[e]) lowers to the location it denotes, P[[p]]; any expression lowers to a value V[[e]]. A place used as an operand is read when the instruction using it executes (Definition 11.4.1).
When must Pebble's lowering copy a place operand into a temporary?
When a later operand in the same list may write it, i.e. contains a call with a &mut argument (Definition 11.4.2, Lemma 11.4.3); otherwise the read would happen after the call.
In Pebble, which element does xs[i] = next(&mut i) write?
The one chosen before the call: the destination place (xs, i, the bounds check) is computed first and, since the right side may write i, the index is copied to a temporary (Algorithm 11.4.4, Lesson 11.4 §3).
loop-shapes¶
What is a top-tested loop?
A header block that tests the condition and branches to the body or the exit; the body ends with a jump back to the header (Definition 11.4.6). What front ends emit for while and for.
What does loop rotation produce?
A guarded do-while: a copy of the test before the loop (the guard) and the test at the end of the body (the latch branches back), so each iteration executes one branch instead of a branch and a jump (Algorithm 11.4.7).
What limits LLVM's loop rotation?
The header must be duplicable into the preheader; LoopRotate refuses when the header is larger than -rotation-max-header-size (default 16 instructions).
abi-direct¶
What does passing an aggregate by value (direct) mean in LLVM IR?
The aggregate travels as SSA values: scalarized into its fields or as a first-class aggregate type, assigned to registers by the back end (rustc's scalar pairs).
What is the risk of passing first-class aggregates directly to match a C ABI?
LLVM's back end assigns registers per IR value, not per C type, so a struct passed as an LLVM struct may not land where the C ABI puts it; front ends coerce instead.
When is passing directly cheapest?
For small aggregates both sides agree on: no memory traffic, the fields stay in registers across the call.
sret¶
What is an sret parameter?
A hidden first pointer parameter to caller-provided storage for an aggregate result; the function writes the result there and returns void.
Why is the sret pointer noalias in Pebble's convention?
The caller always passes a fresh temporary (call.result), which the callee cannot reach any other way (Theorem 11.5.3 (ii)); so LLVM may optimize the callee's stores to it. Passing an object the callee can also reach would break this.
How does Pebble return a struct from a function?
Through ptr sret(%T) noalias: the caller allocates, passes the pointer first, and reads the result after the call (Algorithm 11.5.2).
byval¶
What does the byval attribute mean?
The pointer argument designates a copy made by the call sequence: the callee gets its own copy of the pointee in the argument area (the stack).
How does byval differ from a caller copy + pointer?
With byval the copy is part of the call ABI (on the stack, made during the call); with a caller copy the caller makes an ordinary alloca + memcpy that the optimizer can see and often remove. Pebble uses caller copies.
Where does Clang use byval?
For x86-64 MEMORY-class arguments (structs over 16 bytes); AArch64 instead passes large aggregates indirectly as a pointer to a caller copy.
abi-coercion¶
What are the System V x86-64 eightbyte classes?
INTEGER, SSE, MEMORY, NO_CLASS (plus X87 variants). Each 8-byte chunk of an aggregate gets the merge of its fields' classes; any MEMORY, or size over 16 bytes, makes the whole argument MEMORY (Algorithm 11.5.4).
How does Clang choose the LLVM type for an INTEGER eightbyte?
GetINTEGERTypeAtOffset: if a pointer or i64 starts the eightbyte, use it; if a lone scalar fills the eightbyte's data, use its type (e.g. i32); otherwise an iN covering the bytes.
What does Clang coerce struct { int a; double b; } to on x86-64?
{ i32, double }: the first eightbyte is INTEGER (an i32 alone) and goes in edi, the second is SSE and goes in xmm0.
trap¶
What does the trap policy do on a failed check?
Calls a noreturn function that reports and exits immediately, without cleanups (Pebble: pebble_trap, exit 101; Swift cond_fail; -fsanitize-trap).
What may the optimizer assume after a trap check succeeds?
That the checked condition holds on the fall-through path, because the failure path never returns (Lemma 11.6.4).
What is the run-time cost of a passed trap check?
One compare and a predictable branch to a cold block; no unwind tables or landing pads.
unwind¶
What does the unwind policy do on a failed check?
Raises a panic or exception that runs the cleanups of every frame until a handler or the top (Rust's panic=unwind, Go panics, Java exceptions).
What does unwinding require of every call in LLVM IR?
Calls that may unwind through a frame with cleanups are invokes with a landing pad; the compiler must keep cleanup code and tables.
What does Rust's panic=abort change?
Panics abort instead of unwinding: no landing pads for cleanups, like a trap, and smaller code.
error-return¶
What is the error-return policy for a checked operation?
The operation returns a value that says whether it failed (Option, Result, a flag); the caller must test it (Rust checked_add, ?, Go's (v, err)).
What does an error return cost?
A compare and branch in the caller on every call, even when nothing fails; no tables.
How does Rust's ? operator lower?
To a match on the Try trait's result: on failure, convert the residual and return early; on success, continue with the value (lower_expr_try).
zero-cost-eh¶
What does zero-cost exception handling cost when nothing throws?
Nothing on the normal path: invoke compiles to a plain call; the landing pads and call-site tables are out of line (Theorem 11.7.3).
How does the unwinder find a frame's landing pad?
It looks up the return address in the function's call-site table (LSDA): each entry is a code range with a landing pad and an action; no entry means no pad (Algorithm 11.7.2).
What are the two phases of Itanium unwinding?
Search: walk the frames calling personalities to find a handler, without changing state. Cleanup: walk again, running landing pads (cleanups) up to the handler.
sjlj¶
How does setjmp/longjmp exception handling work?
Each function with handlers registers a context (setjmp buffer) on entry and stores the index of the active call site before each call; a throw longjmps to the context and dispatches on the index (Algorithm 11.7.4).
What does SjLj EH cost when nothing throws?
Registration and unregistration per function call plus one store per call site: a cost on the normal path, unlike table-driven EH.
Where does LLVM implement SjLj EH?
SjLjEHPrepare (llvm/lib/CodeGen/SjLjEHPrepare.cpp), selected with -exception-model=sjlj; the runtime is libgcc's Unwind_SjLj*.
explicit-errors¶
What is an explicit error-return convention?
Errors are returned as ordinary results or in a dedicated register, and the caller branches on them after each call (Definition 11.7.5).
How does Swift return errors?
In a register reserved by its calling convention (r12 on x86-64, x21 on AArch64), marked swifterror in LLVM IR; the caller tests it after the call.
How does the cost of explicit errors grow with call depth?
One test per frame on every return, thrown or not: O(depth) on the normal path, compared with 0 for table-driven EH.
closure-conversion¶
What is closure conversion?
Making every function closed by passing an environment parameter, and representing each function value as a record of a code pointer and the captured variables (Algorithm 11.8.2).
What invariant does a closure record satisfy?
It holds one field per free variable of the function, with the values those variables had when the closure was created (or references to them for by-reference capture).
What does closure conversion cost at run time?
One record of k + 1 words per closure creation (k captures) and an indirect call per application, unless escape analysis avoids them.
lambda-lifting¶
What is lambda lifting?
Moving a local function to the top level and passing its free variables as extra parameters at every call (Johnsson 1985; Algorithm 11.8.4).
When is lambda lifting correct?
When the local function does not escape: it is only called, never returned, stored or passed (Theorem 11.8.5).
How are the extra parameters of mutually calling local functions found?
A least fixed point: start with each function's direct free variables and add the extra parameters of every function it calls until nothing changes; at most m·|V| changes.
runtime-library¶
What is a runtime library?
Object code linked into every program of a language that provides functions the generated code calls but the source does not define: output, traps, start-up, helpers (Definition 11.9.1).
What is a libcall?
A call to a runtime helper that the code generator introduces for an operation the target cannot do inline, e.g. __divti3 for a 128-bit signed division.
Why is Pebble's C main in its own file of the runtime archive?
An archive member is linked only if it defines an undefined symbol; tools with their own main (pir-run) then never pull it in, and it cannot demand a pebble_main they lack.
object-linking¶
What does an object file record for a call to a function in another file?
An undefined symbol and a relocation (R_X86_64_PLT32 on x86-64 ELF) that the linker resolves to S + A − P.
Why must the runtime archive come after the objects on a GNU ld command line?
The linker searches an archive once, pulling only members that define symbols undefined at that point; symbols referenced later are not found (Theorem 11.9.6).
Why do pebblec, rustc and Clang link through cc instead of calling ld directly?
The C compiler driver knows the platform's start-up files, library paths, dynamic linker and PIE settings.