Flashcards — Chapter 9¶
106 cards. Review them with spaced repetition in the terminal (./course flash 9) or export them to Anki (./course flash export 9). Here, click a card to reveal its back.
module¶
What does an LLVM module contain?
Data layout string, target triple, identified struct types, global variables, functions, aliases/ifuncs, comdats and named metadata (Definition 9.1.1). It is self-contained: every @name it uses is defined or declared in its own symbol table.
Why is the module (not the function) LLVM's unit of compilation?
LLVM IR was designed as a persistent representation that survives link time and can be serialized and optimized again (LTO). The module carries everything needed to interpret it: layout, triple, types, globals, metadata.
What happens when a .ll file uses @f but never declares or defines it?
The parser reports "use of undefined value '@f'" when it finishes the module: forward references must resolve within the module (Proposition 9.1.8).
Cost of parsing and of linking modules?
Parsing/printing: linear in the text. Linking: O(g + r) expected (g = global values via hashed symbol tables, r = references redirected by RAUW).
linkage¶
Which linkages are discardable if unused?
private, internal, linkonce, linkonce_odr and available_externally (GlobalValue::isDiscardableIfUnused).
Why can an optimizer inline a linkonce_odr function but not a weak one?
Both may be replaced at link time, but ODR linkages promise every definition is equivalent (only de-refinable), while weak/linkonce are interposable: the body that runs may be entirely different.
Linking: which wins among weak @x = 1 and external @x = 2?
The external definition (strength 5 beats weak's 3). Two external definitions of the same name give "symbol multiply defined!" (Algorithm 9.1.4).
What does dso_local promise?
That the symbol resolves within the same linked object (executable or shared library), so the back end may use direct PC-relative access instead of the GOT. Local linkage and hidden/protected visibility imply it.
How does llvm-link treat two internal @k from different modules?
It keeps both and renames one (@k.3): local names are renamed, never resolved.
ssa-values¶
What is a value in LLVM IR, and does it have storage?
Parameters, non-void instructions, basic blocks, globals and constants. A value is the result itself, not a variable: %add is how the text refers to the sum, and uses point directly at the defining instruction.
How are unnamed values numbered (%0, %1, …)?
In textual order: unnamed parameters, then for each block the block (if unnamed) and its unnamed non-void instructions, gap-free (Algorithm 9.1.7). The LLVM 23 parser accepts increasing numbers with gaps; the printer renumbers densely.
Why does %i = add i64 %i, 1 not work as a loop counter?
SSA: each name has one definition, and a non-phi instruction may not use its own result ("Only PHI nodes may reference their own value!"). Loop-carried values are phis in the header.
types-scalar¶
Do LLVM integer types have a sign?
No. iN is just N bits; signedness is in the instructions (sdiv/udiv, icmp slt/ult, sext/zext, ashr/lshr) and flags. add/sub/mul/shl/and/or/xor give the same bits either way (Proposition 9.2.9).
What did opaque pointers remove and what stayed?
The pointee type (i32* is gone; every pointer is ptr, LLVM 17). The address space stays: ptr addrspace(1). Loads, stores, GEPs and calls name the types themselves.
What is the byte type bN (LLVM 23)?
A first-class type for raw memory: each bit is an integer bit, part of a pointer, or poison. It lets memcpy-like code move data without claiming it is an integer; converted by bitcast.
types-aggregate¶
Literal vs identified struct types?
Literal structs ({ i32, ptr }) are uniqued structurally: equal bodies = same type. Identified structs (%struct.Point) are nominal: distinct even with equal bodies; clashing names get renamed (%A.0).
Can an LLVM struct type contain itself?
No. The parser rejects recursive identified structs ("identified structure type 'T' is recursive"), and with opaque ptr there is no pointee type through which a type could refer to itself: the type graph is well founded (Proposition 9.2.10).
Packed struct <{ i8, i32 }>: offsets and size?
Fields at alignment 1: i8 at 0, i32 at 1; size 5, alignment 1.
Cost of type equality in LLVM?
O(1): types are hash-consed per LLVMContext, so structural equality of literal types is pointer equality (Corollary 9.2.11).
types-vector¶
What is <vscale x 4 x i32>?
A scalable vector: vscale × 4 lanes of i32, vscale a hardware constant unknown at compile time (Arm SVE, RISC-V V). Its size is not a compile-time constant: it cannot be (or be inside) a global; it may be alloca'd, loaded, stored and used as a GEP source type (the offset scales with vscale).
What is known about sizes of scalable vectors?
Each is vscale times a known minimum; ratios between scalable sizes are compile-time constants, comparisons with fixed sizes are not (TypeSize = min + scalable flag).
Alignment of <3 x i32> under the x86-64 layout?
No v96 entry, so natural alignment: store size 12 rounded up to a power of two = 16; alloc size 16.
types-special¶
What does the token type forbid?
Merging: no phi or select of tokens, no token-typed globals, only intrinsics may return tokens. Every use names one statically known producer (Proposition 9.2.13).
What are target extension types?
target("name", types…, ints…): opaque, target-defined types (GPU image handles, SPIR-V, RISC-V vector tuples) that may be passed around, used in phis/selects, but not bitcast, compared or converted.
Can a function take a label parameter?
No: "invalid type for function argument". label is the type of basic blocks; metadata is only for intrinsic arguments.
datalayout¶
Default alignment of i64 when the data layout says nothing?
4 bytes: the LangRef default is i64:32:64 (ABI 32 bits, preferred 64). x86-64's layout overrides it with i64:64.
Integer alignment rule for a width with no entry (e.g. i24)?
Use the next larger listed integer width (i32 → 4), or the largest listed width if none is larger (Algorithm 9.2.6).
Offset of the double in { i8, double } on i686 vs x86-64?
4 on i686 (f64:32:64 in its layout) vs 8 on x86-64.
Why must the module's data layout match the back end's?
The optimizer folds sizes and offsets from the string; if the back end lays out memory differently, the code is wrong. Back ends check it (TargetMachine::isCompatibleDataLayout).
What is a target triple?
arch[sub]-vendor-os[-env], e.g. x86_64-unknown-linux-gnu; it selects the back end, object format and ABI. It is normalized (aarch64-apple-macosx14 → arm64-apple-macosx14.0.0).
terminators¶
List LLVM 23's terminators.
ret, br, switch, indirectbr, invoke, callbr, resume, catchswitch, catchret, cleanupret, unreachable.
How many successors does switch i32 %x, label %d [i32 1, label %j i32 2, label %j] have?
Three edges, counted with multiplicity: d, j, j. A phi in %j needs two entries for this block, with equal values.
Why is a call that may throw a terminator (invoke)?
It has two successors (normal and unwind). A value it defines is available only on the normal edge; if it were a plain call in the middle of a block, the rest of the block would be skipped on unwinding.
What may the optimizer do with code that must reach unreachable?
Delete it or assume it is not executed: reaching unreachable is UB. That is how a switch with an unreachable default becomes a table lookup with poison holes.
phi-select¶
When exactly are phis evaluated?
On an edge p → b, all phis of b are assigned simultaneously from their entries for p, read at the end of p (parallel copy).
select c, x, y: when is it poison?
If c is poison, or if the chosen operand is poison. The unchosen operand's poison does not propagate.
Why is branch → select a refinement but select → branch not?
A branch on poison is UB; a select on poison is only poison. Converting the branch removes UB (allowed); converting the select adds UB unless the condition is frozen (Proposition 9.3.10, Theorem 9.7.13).
Must a phi's incoming value dominate the phi?
No: it must dominate the end of the corresponding predecessor. A value from the loop body can feed the header phi on the back edge.
verifier¶
State the SSA dominance property.
Every use is dominated by its definition: same block and earlier, or the definition's block strictly dominates the use's block; for a phi, the definition dominates the end of the incoming block (Definition 9.3.3, Theorem 9.3.5).
Name the verifier rules W2–W4.
W2: the entry block has no predecessors. W3: phis first in a block. W4: one phi entry per incoming edge (with multiplicity), equal values for the same predecessor, no non-predecessors.
Which LLVM message corresponds to a use not dominated by its definition?
"Instruction does not dominate all uses!" (Verifier::verifyDominatesUse).
Which checks does the parser do, and which the verifier?
Parser: one terminator per block (it starts a new block after each), names defined once and used defined, operand and return types. Verifier: entry predecessors, phi grouping and entries, self-reference, dominance, EH rules.
Cost of verifying a function?
O(i + u + T_dom): linear in instructions and uses plus dominator-tree construction; each dominance query is O(1) with DFS numbers and cached instruction order.
memory¶
When is an alloca promotable to SSA (mem2reg)?
When it is used only by non-volatile loads and stores of one type (plus lifetime markers), never stored as a value, passed to a call or indexed by a GEP (isAllocaPromotable, Proposition 9.4.12).
What does loading from uninitialized alloca memory give?
undef ("an undefined value"), per the LangRef's alloca section.
Why does mem2reg not promote an array accessed through constant GEPs? What does?
mem2reg requires whole-object loads/stores. SROA first splits the aggregate into scalars (constant indices), then promotes them.
atomics¶
List the atomic orderings from weakest to strongest.
unordered < monotonic < acquire, release < acq_rel < seq_cst. monotonic = C++ relaxed.
What does a non-atomic load that races with a write return in LLVM's model?
undef (for the racing bytes). Hence the optimizer may hoist a plain load out of a spin loop (Proposition 9.4.13).
volatile vs atomic?
volatile: the number and order of volatile accesses are preserved (I/O, sig_atomic_t); no cross-thread ordering. Atomics: ordering and synchronization between threads.
x86-64 code for a release store vs a seq_cst store?
release: a plain mov. seq_cst: xchg (a full barrier).
gep¶
GEP byte offset formula.
Δ = i0·alloc(T0) + Σ_{j≥1} (field offset if T_j is a struct, else i_j·alloc(element)), computed modulo 2^w in the index width (Definition 9.4.3, Theorem 9.4.5).
Why does gep %struct.S, ptr %p, i64 0, i32 1 start with 0?
The first index steps over whole S objects (p is an array of S); 0 selects the object %p points to, then i32 1 selects field 1.
Can a GEP follow a pointer stored in a struct field?
No. GEP never touches memory; to go through a pointer you must load it and start a new GEP.
&s[1].Z.B[5][13] for the LangRef's RT/ST structs on x86-64?
824 + 16 + 4 + 5·80 + 13·4 = 1296 bytes (clang -O2 emits getelementptr inbounds nuw i8, ptr %s, i64 1296).
Why must struct GEP indices be i32 constants?
The field's offset depends on which field, and fields have different types: the result type must be known statically.
inbounds, nusw, nuw on GEP: what does violating them give?
Poison (not UB). nusw/nuw: no signed/unsigned wrap in the scaling, partial sums and address additions; inbounds: nusw plus every intermediate address in bounds of one allocated object.
When does inbounds imply nuw?
When all offsets are non-negative: in-bounds addresses cannot wrap because no object crosses the end of the address space (Proposition 9.4.7).
What is LLVM 23's canonical form of a GEP?
The byte-offset form: constant offsets as getelementptr i8, ptr %p, i64 C; a single variable index over T as getelementptr [alloc(T) x i8]; multi-index GEPs split (Algorithm 9.4.9).
icmp eq (gep inbounds i8, ptr %p, i64 4), null: why does it fold to false?
Only null is in bounds of null, so an inbounds GEP with a non-zero offset of null is poison; in defined executions the result is not null.
casts¶
Which cast creates poison for out-of-range values?
fptosi/fptoui (value does not fit). Flags add more: trunc nuw/nsw, zext nneg, uitofp nneg.
Is trunc(zext x) = x? Is sext(trunc y) = y?
trunc(zext x) = x always (and trunc nuw is never poison there). sext(trunc y) = y only if y fits the narrow signed range.
ptrtoint vs ptrtoaddr (LLVM 22+)?
ptrtoint gives all the pointer's bits and captures address and provenance; ptrtoaddr gives the index-width address bits and captures only the address.
calls¶
How does a call to printf spell the callee's type?
call i32 (ptr, ...) @printf(ptr @fmt, …): the full function type, since pointers carry no type.
Who applies C's default argument promotions for a variadic call in LLVM IR?
The front end (you, in lab E5): float → double with fpext, char/short → i32 with sext/zext.
What happens if a call's calling convention differs from the callee's?
Undefined behavior; InstCombine replaces the call with its unreachable marker (store i1 true, ptr poison).
tail vs musttail?
tail: the call does not access the caller's stack objects (a tail-call candidate). musttail: a tail call is required, with signature constraints that make it always possible.
attributes¶
What does memory(argmem: read) mean on a function?
It only reads memory reachable from its pointer arguments; writing it is UB (Definition 9.5.4).
How is memory(...) inferred for a call-graph SCC?
Join the effects of all instructions of all members, skipping calls inside the SCC; all members get the same effect (Algorithm 9.5.5, Proposition 9.5.9). Linear in instructions.
Why does FunctionAttrs require an exact definition?
For linkonce/weak functions another, less optimized body may run, which could access more memory.
noundef violated vs nonnull violated?
noundef: undefined behavior. nonnull (and align, range, nofpclass): the value becomes poison.
What does zeroext on a return value do?
It is ABI: the callee zero-extends the (e.g. i1/i8) result to the full register, as the C caller of a _Bool function expects.
intrinsics¶
How is an overloaded intrinsic named?
Base name + '.' + the mangled overloaded types: llvm.ctpop.i32, llvm.memcpy.p0.p0.i64, llvm.sadd.with.overflow.i64.
What does llvm.smul.with.overflow.i64 return?
{ i64, i1 }: the wrapped product and the signed-overflow bit; take it apart with extractvalue.
What does LLVM 23 do with declare i64 @llvm.ctpop.i32(i64)?
It remangles the name to @llvm.ctpop.i64 (the suffix is recomputed from the type); a wrongly shaped signature is rejected instead.
metadata¶
Is dropping metadata always correct?
Yes (Theorem 9.6.8): value metadata only adds poison/UB, TBAA only licenses alias assumptions, loop metadata are hints/properties, debug records have no semantics.
TBAA: when are two scalar accesses NoAlias?
When neither access type is an ancestor-or-self of the other in the type tree (Algorithm 9.6.3). 'omnipotent char' is an ancestor of all C types, so char may alias anything.
What does !range !{i8 0, i8 5} on a load mean?
The loaded value is in [0, 5) or the load returns poison.
Why is !llvm.loop a distinct self-referential node?
So two loops with identical properties still have different nodes; LoopInfo::getLoopID also checks the self-reference.
debug-records¶
What is a debug record?
An annotation like #dbg_value(i64 %s, !var, !DIExpression(), !loc) attached before an instruction; not an instruction, not in the instruction list (LLVM 19+).
Why did LLVM replace llvm.dbg.value calls with records?
Calls were instructions: passes that counted or scanned instructions behaved differently with -g, and they cost compile time. Records cannot change instruction-sequence-based decisions (Proposition 9.6.11).
How do you visit the debug records of an instruction?
Instruction::getDbgRecordRange(); iterating instructions(F) never yields them.
bitcode¶
LLVM's IR compatibility policy?
Bitcode from 3.0 onward can be read; the textual format has no compatibility promise; non-debug metadata may be dropped when upgrading; debug metadata is dropped.
Encode 30 as vbr4.
Chunks of 3 payload bits + continuation bit, low first: 110 with continuation (1110), then 011 (0011): bits 0011 1110 = 62.
Why are bitcode operands relative?
An operand is written as (current value number − operand's id), usually a small number, so it fits in one VBR chunk regardless of function size.
ub¶
Name four kinds of immediate UB in LLVM IR.
Division by zero (or by poison, or INT_MIN/-1); load/store through a poison, null or dangling pointer; branch or switch on poison; reaching unreachable; poison passed to noundef.
Why does clang fold x + 1 > x to true for int but not unsigned?
Signed overflow is UB in C, so clang emits add nsw; an overflowing nsw add is poison, which may be refined to true (Theorem 9.7.15). unsigned wraps: no flag, real comparison.
How does llubi report a branch on poison?
Immediate UB detected: Branch on poison condition.
poison¶
Is and i8 %p, 0 zero when %p is poison?
No: it is poison. Almost every instruction propagates poison from any operand (exceptions: select's unchosen operand, freeze).
What does freeze do?
freeze x = x if x is not poison; otherwise some arbitrary but fixed value, the same for all uses of that freeze (LLVM 10+).
%f = freeze %p; %d = sub %f, %f — value?
0: both uses see the same frozen value. sub %p, %p with %p poison is poison.
Cost of evaluating straight-line code with poison?
O(i) without nondeterminism; enumerating freeze choices multiplies by 2^N per frozen poison (Algorithm 9.7.5).
undef¶
How does undef differ from poison?
undef is any value, chosen independently at each use; poison is a single 'no value' that propagates. Poison is stronger (poison refines to undef or any value).
Why is mul %x, 2 → add %x, %x wrong if %x is undef?
mul undef, 2 is always even; add undef, undef picks two independent values and can be odd: the rewrite adds behaviors (Proposition 9.7.14).
What does the LangRef say to use instead of undef?
poison, "whenever possible"; freeze where a well-defined arbitrary value is needed.
flags¶
List LLVM's poison-generating flags.
nuw, nsw (add/sub/mul/shl/trunc), exact (udiv/sdiv/lshr/ashr), disjoint (or), samesign (icmp), nneg (zext, uitofp), inbounds/nusw/nuw (GEP), nnan/ninf (FP).
add nsw x, x → shl x, 1: which flags may shl keep?
nsw only (nuw fails: x = -1 is fine for add nsw but shl nuw shifts out a 1).
Folding add nsw (add nsw x, 100), 100 on i8: keep nsw?
No: x = -100 gives a well-defined source (100) but -100 + (-56) overflows; instcombine emits plain add i8 %x, -56.
When may instcombine turn add into or disjoint?
When known bits prove the operands share no set bit (e.g. and x, 15 and shl y, 4); then add = or and disjoint holds.
refinement¶
Define refinement.
T refines S if every behavior of T on every input is a behavior of S (UB in S allows anything; poison in S allows any value). A transformation is correct iff output refines input.
Why are allowed flag sets closed under union?
Flags only add poison conditions; if each flag alone never fires where the source is defined, none fires, so all together refine too (Proposition 9.7.9).
How does Alive2 check refinement, and how does the flags drill?
Alive2: SMT encoding for all inputs (bounded loops). The drill: exhaustive enumeration at i8 (one variable) or i4 (two), Algorithm 9.7.10.
ir-compare¶
Phis vs block arguments?
Same information (Theorem 9.8.6): phi entries per edge ↔ branch arguments. Block arguments can pass different values on two edges from the same block; phis need an edge split for that.
Which IRs in Lesson 9.8 use block arguments?
Swift SIL, Cranelift IR (block parameters) and MLIR; LLVM IR and GIMPLE use phis; MIR, PIR and Wasm use mutable locals.
Why is every Wasm CFG reducible?
Structured control: backward branches only target an enclosing loop's start, which dominates everything inside it (Proposition 9.8.11).
How do MIR and PIR express array bounds checks?
As explicit assert terminators before the access (MIR: assert(Lt(i, len), "index out of bounds…"); PIR: assert _5, bounds).
Why does Cranelift IR need no freeze?
Its integer ops wrap or trap; there is no poison (Proposition 9.8.10).