Flashcards — Chapter 10¶
130 cards. Review them with spaced repetition in the terminal (./course flash 10) or export them to Anki (./course flash export 10). Here, click a card to reveal its back.
uniquing¶
What does LLVMContext uniquing guarantee for types and constants?
Within one context, two uniqued objects are the same pointer iff their structural keys are equal (Theorem 10.1.11), so type/constant equality is a pointer compare.
How is ConstantInt::get implemented in LLVM 23?
A lookup in LLVMContextImpl's tables: IntZeroConstants / IntOneConstants for 0 and 1, IntConstants (DenseMap<APInt, unique_ptr<ConstantInt>>) otherwise; create on miss.
Are two identified (named) struct types with the same body the same object?
No. Named structs are deliberately not uniqued by structure; only literal (anonymous) struct types are.
Why does LLVM 23's ConstantInt have no use list?
ConstantData (integer/FP literals, undef, poison, null) is untracked: hasUseList() is false. Tracking millions of uses of i32 0 was a speed and thread-safety problem.
ownership¶
Who owns an Instruction, a BasicBlock, a Function?
Its BasicBlock, its Function, its Module respectively; the client holds the unique_ptr<Module>. Types and constants are owned by the LLVMContext.
removeFromParent vs eraseFromParent?
remove unlinks and returns the instruction (the caller now owns it, uses intact); erase unlinks AND deletes it (every saved pointer dangles).
Why does ~Module call dropAllReferences first?
Use edges can be cyclic (phi loops); nulling every operand first means no Use points into the tree, so deletion order no longer matters (Theorem 10.1.12).
Cost of deleting a module?
O(L): one pass over operand slots (dropAllReferences), one over objects.
ilist¶
What is an intrusive list?
A doubly linked list whose next/prev links live inside the elements; LLVM's ilist holds instructions, blocks, functions. O(1) insert/erase at a known node.
Which iterators does erasing node n invalidate in an ilist?
Only iterators to n itself (Lemma 10.1.13); neighbours keep valid iterators.
Why is for (Instruction &I : BB) I.eraseFromParent(); undefined behavior?
The loop's ++ reads the next pointer inside the freed instruction (ASan: heap-use-after-free in ilist_iterator::operator++).
How does make_early_inc_range make erasing the current element safe?
Its operator* returns *(I)++: the underlying iterator already points to the next element when the body runs. Erasing the NEXT element is still unsafe.
Cost of BasicBlock::size()?
O(n): simple_ilist::size is std::distance(begin(), end()).
arena¶
What is an index-based arena IR?
Entities in growable vectors addressed by small integer references; program order kept separately (Cranelift's DataFlowGraph + Layout, rustc IndexVec).
What failure mode replaces use-after-free in arenas?
Stale references: an index to a removed entity still reads (old) valid data; nothing detects it unless generations are added.
Space and access cost of arena references?
4-byte indices, O(1) access; append amortized O(1); data freed only with the whole arena.
use-lists¶
Fields of a Use?
Val (the value), Next, Prev (pointer to the incoming pointer: Use **), Parent (the user). 32 bytes on 64-bit hosts.
Where does a new use go in its value's list?
At the head (Use::addToList): uses() visits the most recently added use first.
State the def-use consistency invariant.
Every use of a tracked value is in that value's list exactly once and owned by its user's operand array; every listed use refers back to the value (Definition 10.2.4).
uses() vs users()?
uses() yields Use& (operand slots, with getOperandNo); users() yields the User* behind each use, once per use.
Cost of getNumUses vs hasOneUse?
getNumUses O(#uses) (walks the list); hasOneUse O(1) (checks at most two nodes).
operand-layout¶
Co-allocated operands?
Fixed operands allocated in the same block, immediately before the User object; operand i at this − (k−i)·sizeof(Use).
Hung-off operands?
A separate, growable operand array pointed to by the user (phi, switch); growHungoffUses reallocates and relinks the uses.
How is getOperandNo computed?
Pointer arithmetic: this Use minus the start of its user's operand list — nothing is stored.
rauw¶
What does RAUW(X, Y) do to use-list order?
Takes the head of X's list repeatedly and sets it to Y, so X's uses land at the front of Y's list in reversed order (Theorem 10.2.12).
When does RAUW(X, Y) preserve SSA dominance?
When Y is a constant, an argument, or an instruction whose definition dominates X's (Theorem 10.2.13).
Cost of RAUW?
Θ(m) for m uses of X (one O(1) Use::set each), plus handle notification and re-uniquing constant users.
What does RAUW assert?
New value non-null, same type, and not containing the old value (no this->RAUW(expr(this))).
value-handles¶
WeakVH vs WeakTrackingVH?
Both null on delete; WeakTrackingVH also follows RAUW to the new value, WeakVH keeps the old one.
What does AssertingVH cost in a Release build without ABI-breaking checks?
Nothing: it is a plain 8-byte pointer and checks nothing.
How do handles learn about deletion?
The value's HasValueHandle bit; ~Value / RAUW call ValueHandleBase::ValueIsDeleted / ValueIsRAUWd, which walk the handle list.
metadata-as-value¶
What is MetadataAsValue?
A uniqued Value of type metadata wrapping a metadata node, so metadata can be an operand (e.g. constrained FP rounding-mode strings).
What is ValueAsMetadata / LocalAsMetadata?
Metadata wrapping a Value; it follows RAUW via ValueAsMetadata::handleRAUW, without a use list.
Are MetadataAsValue wrappers uniqued?
Yes: MetadataAsValue::get returns the same object for the same metadata in a context.
direct-construction¶
How do you create an instruction without IRBuilder in LLVM 23?
XInst::Create(…, InsertPosition) with a BasicBlock::iterator (or block end, or nullptr); no folding.
Why is InsertPosition(Instruction *) deprecated?
An Instruction* cannot carry the debug-record head bit; iterators can.
Does direct construction fold constants?
No; only IRBuilder's folder does.
insertion-points¶
What is the head bit of a BasicBlock::iterator?
It decides whether an instruction inserted at a position with attached #dbg records goes before them (set) or after them (clear).
Which iterators have the head bit set?
begin(), getFirstNonPHIIt(), getFirstInsertionPt(); getIterator() does not.
Order of instructions created at a fixed insertion point?
Call order, each immediately before the point (Theorem 10.3.7).
folders¶
ConstantFolder's domain?
Only operations whose operands are all Constants.
What does InstSimplifyFolder add?
InstSimplify identities: x+0→x, x−x→0, x&x→x, x*0→0 … returning existing values without inserting.
Why can CreateAdd return a non-Instruction?
The folder may return a constant or an existing value; never cast<Instruction> the result blindly.
Which folder does Clang use?
TargetFolder (constant folding with the DataLayout).
inserters¶
What is an IRBuilder inserter?
The InsertHelper(I, Name, InsertPt) hook that links and names each created instruction; custom inserters add side effects.
Is the inserter called for folded operations?
No — only for created instructions (Theorem 10.3.9).
Which LLVM pass uses a worklist inserter?
InstCombine: IRBuilder<TargetFolder, IRBuilderInstCombineInserter> adds each new instruction to its worklist.
builder-state¶
What state does IRBuilderBase carry?
Insertion point, debug location, fast-math flags, fpmath tag, constrained-FP mode/rounding/exception behavior, default operand bundles.
What do InsertPointGuard / FastMathFlagGuard do?
RAII: save builder state on construction, restore it on every scope exit.
What does setIsFPConstrained(true) change?
CreateFAdd etc. emit llvm.experimental.constrained.* intrinsics with the builder's rounding and exception metadata, and they no longer consult the folder, so even constant operands produce a call.
llvm-rtti¶
isa<X>(nullptr)?
Asserts (UB in release). Use isa_and_present / dyn_cast_if_present for possibly-null values.
Why is classof a single range test?
Kinds are numbered in preorder, so each class's subclasses have contiguous kind numbers (Theorem 10.4.10).
cast vs dyn_cast?
cast asserts the type (UB if wrong in release); dyn_cast returns null for a wrong type.
What is CastInfo?
The Casting.h customization point that teaches isa/cast/dyn_cast new source types (value handles, optionals, PointerUnion, MLIR types).
Is PoisonValue an UndefValue?
Yes: PoisonValue derives from UndefValue, so isa<UndefValue>(poison) is true.
cxx-rtti¶
Can you dynamic_cast an llvm::Value?
No: Value has no virtual functions ('Value is not polymorphic').
What does dynamic_cast compile to?
A null check and a call to __dynamic_cast(sub, src type_info, dst type_info, hint).
Cost of a failed dynamic_cast under single inheritance?
≥ depth type_info comparisons (base-chain walk); measured ~6.7× slower than classof.
variant¶
How does std::visit dispatch?
A switch / table on the variant's index; the default case is unreachable.
What happens when you add an alternative to a variant?
Every visitor without an overload for it fails to compile (Theorem 10.4.13).
Cost of holds_alternative?
One index compare: O(1).
instvisitor¶
How does InstVisitor dispatch?
visit(I) switches on the opcode to visitXxx; unimplemented handlers DELEGATE to the parent class's handler, down to visitInstruction.
Which handler gets an icmp if you override only visitCmpInst?
visitCmpInst, via visitICmp → visitICmpInst → visitCmpInst.
Where do intrinsic calls go in InstVisitor?
delegateCallInst: specific class (e.g. visitMemCpyInst) → … → visitIntrinsicInst → visitCallInst.
handwritten-match¶
Most common bug in hand-written matchers?
Forgetting the commuted operand order (e.g. add X, (sub Y, X)).
When is hand-written matching preferable?
Tree manipulations and full searches (Reassociate), or when a switch on the opcode avoids re-testing.
Relative speed in Lab 10.3?
Raw casts 2.3 ms vs PatternMatch 11.5 ms per 2000 rounds: one opcode switch vs many sequential match() calls.
patternmatch¶
m_Value(X) twice vs m_Deferred(X)?
A second m_Value(X) just rebinds; m_Deferred(X) compares with the earlier binding. Use m_Deferred for 'same value'.
m_Specific vs m_Deferred?
m_Specific(V) captures V when the pattern is built; m_Deferred(X) reads X at match time.
Is PatternMatch complete when an m_Deferred refers to a variable bound under an inner m_c_ matcher?
No: it commits to the first successful inner order and never backtracks into it; e.g. m_Add(m_c_Mul(m_Value(X), m_Value(Y)), m_Deferred(X)) misses add (mul a, b), b (Theorem 10.5.7).
What does m_SMax match in LLVM 23?
Only the llvm.smax intrinsic (not select(icmp sgt …)); InstCombine canonicalizes to the intrinsic.
Worst-case matching cost?
O(2^k·|P|) for k nested commutative nodes per path; typically O(|P|).
rule-dsl¶
Name three rule DSLs for peepholes.
GCC match.pd (genmatch), GlobalISel TableGen combiner rules (GICombineRule), Cranelift ISLE.
When does a rewrite rule set terminate?
If every rule application strictly decreases a well-founded measure (Theorem 10.5.8); confluence is separate.
How does GlobalISel express commutativity?
A GICombinePatFrag listing both operand orders as alternative patterns.
smallvector¶
SmallVector growth rule?
new capacity = max(2·cap + 1, needed) (getNewCapacity).
Why do APIs take SmallVectorImpl<T>&?
It erases the inline size N from the type, so callers choose N.
Amortized cost of push_back?
O(1): n pushes move < 2n elements in total (Theorem 10.6.13).
What invalidates SmallVector iterators?
Any growth (all), insert/erase (at and after the position).
densemap¶
How does LLVM 23's DenseMap probe?
Linear probing with a used-bit per bucket; no empty/tombstone keys.
How does LLVM 23's DenseMap erase?
Knuth's Algorithm R: move later cluster keys whose probe path crosses the hole back into it.
How did DenseMap work up to LLVM 22?
Quadratic (triangular) probing with reserved empty and tombstone keys; erase leaves a tombstone.
DenseMap load factor limit?
Grows (doubles) before an insertion would make 4(n+1) ≥ 3B: α < 3/4; first allocation 64 buckets.
What does DenseMap erase invalidate in LLVM 23?
All iterators and references — other entries may move. Use remove_if for erase-while-scanning.
DenseMapInfo<unsigned>::getHashValue?
k * 37 (truncated to 32 bits).
setvector¶
What is a SetVector?
A vector + set: O(1) membership, iteration in insertion order.
Why prefer SetVector to DenseSet for worklists that affect output?
DenseSet<T*> iterates in pointer-hash order, which changes between runs; SetVector is deterministic (Theorem 10.6.17).
Cost of SetVector::remove?
O(n) (erase from the vector).
views¶
What is a StringRef?
A non-owning (pointer, length) view; valid only while the viewed chars live and are not reallocated.
When does a Twine dangle?
When stored past its full-expression: concat stores pointers to non-unary temporary Twines (and leaves point to std::string objects).
Safe ways to keep a Twine's value?
Twine::str() (std::string) or toStringRef(SmallString buffer); use Twine only as a parameter.
ArrayRef<Value*> Ops = {X, Y}; use(Ops); — safe?
No: the initializer_list array dies at the end of the declaration.
stringmap¶
Layout of a StringMap entry?
One allocation: StringMapEntry<V> header, then the key bytes and a NUL.
Does a StringRef to a StringMap key survive insertions?
Yes: only the pointer table is rehashed; entries never move (Proposition 10.6.19).
Cost of StringMap lookup?
Expected O(|key|) (hashing); stored full hashes avoid most string compares.
bitsets¶
BitVector storage for U bits?
⌈U/64⌉ 64-bit words; union/intersection are word-wise OR/AND.
When use SparseBitVector?
Sparse sets over huge universes: stores only non-zero 128-bit elements in a sorted list.
SparseBitVector<128> elements for {3, 64, 999}?
2 (chunks 0 and 7).
pointer-packing¶
Why can PointerIntPair store bits in a pointer?
A T with alignment 2^a has a zero low bits (Lemma 10.6.20).
sizeof(PointerUnion<A*, B*>)?
One pointer: the tag lives in a free low bit.
Clang's QualType?
A PointerIntPair packing the const/volatile/restrict qualifiers into the low bits of a (Type*|ExtQuals*) union.
apint¶
APInt i8: 200 as signed, 200 udiv 7, 200 sdiv 7?
−56, 28, −8.
Why can one adder serve signed and unsigned?
Both readings are congruent mod 2^w and +,−,× respect congruence; division and comparison do not (Theorem 10.6.21).
What does APFloat add over host floats?
Software IEEE formats with explicit rounding modes and status flags, so folding is host-independent.
llvm-error¶
Does if (E) check a failing llvm::Error?
No: operator bool marks it checked only if it is success; a failure must be handled or moved.
What happens to an unchecked Error in a checking build?
fatalUncheckedError aborts at its destruction or overwrite (Theorem 10.7.8).
handleAllErrors vs handleErrors?
handleErrors returns unhandled payloads as an Error; handleAllErrors requires all handled (leftovers → cantFail → llvm_unreachable).
cantFail and ExitOnError?
cantFail unwraps an Expected that cannot fail (unreachable otherwise); ExitOnError prints the error and exit(1)s.
exceptions¶
What is zero-cost exception handling?
The non-throwing path runs no extra instructions; invoke's unwind edge and LSDA tables are used only when throwing.
Which LLVM IR constructs implement try/catch?
invoke … unwind label %lpad, landingpad, a personality function, resume.
Why does LLVM forbid exceptions?
Table size, throw cost, and clients built with -fno-exceptions (llvm-config --cxxflags contains -fno-exceptions).
std-expected¶
Does std::expected detect ignored errors at run time?
No — only [[nodiscard]]; there is no checked bit.
What does and_then do on an error?
Skips the function and propagates the same error (Proposition 10.7.11).
Pebble's error convention?
std::expected<T, pebble::Error> (a message), converting llvm::Error with toString(E.takeError()) at the boundary.
interpreter¶
How does the ExecutionEngine interpreter run IR?
An InstVisitor walking instructions with a GenericValue map per frame; phis evaluated simultaneously on block entry.
What happens if interpreted IR calls llvm.abs?
report_fatal_error: 'Code generator does not support intrinsic function' — the process aborts.
Interpreter vs JIT crossover?
JIT wins when I > K/(t_i − t_c); measured K≈12 ms, t_i≈60 ns → I ≈ 2·10^5 instructions.
mcjit¶
How does MCJIT compile?
Whole modules to in-memory objects with the normal codegen, linked by RuntimeDyld, at the first address request.
MCJIT's status in LLVM 23?
Still present (lli -jit-kind=mcjit), superseded by ORC for new code.
When does MCJIT compile a module?
Whole, when getFunctionAddress first asks for one of its symbols (or when linking needs a symbol it defines); finalizeObject compiles every added module.
lljit¶
What does a ThreadSafeModule own?
The Module together with its LLVMContext (and a lock).
What does LLJIT compile on lookup("f")?
f's whole module, plus every module it references, via materialization units.
How are duplicate names resolved in ORC?
First definition in the JITDylib's link order (Proposition 10.8.9).
lazyjit¶
What does LLLazyJIT compile on lookup?
Nothing but stubs; each function compiles on its first call.
Which functions does LLLazyJIT compile?
Exactly those executed, each once, in order of first call (Theorem 10.8.10).
Downside of per-function lazy compilation?
Fixed per-function overhead (callback, partition, codegen call) when many small functions each run once.
cmake-llvm¶
How do you find LLVM from CMake?
find_package(LLVM 23.1 REQUIRED CONFIG) with LLVM_DIR=$(llvm-config --cmakedir); use LLVM_INCLUDE_DIRS, LLVM_DEFINITIONS.
Dylib vs components?
If LLVM_LINK_LLVM_DYLIB, link the single LLVM target; else llvm_map_components_to_libnames(… core orcjit native) expands a topologically ordered closure.
Why put -std=c++23 after $(llvm-config --cxxflags)?
--cxxflags contains -std=c++17; the last -std wins.
Which LLVM build settings must a client match?
LLVM_ENABLE_RTTI, LLVM_ENABLE_ABI_BREAKING_CHECKS (link-time checked), and no exceptions through LLVM frames.