Flashcards — Chapter 20¶
106 cards. Review them with spaced repetition in the terminal (./course flash 20) or export them to Anki (./course flash export 20). Here, click a card to reveal its back.
direct-cg¶
What does LLVM's external calling node stand for, and which functions does it call?
"Code outside the module." It has an edge to every function without local linkage and every function whose address is taken, in module order (CallGraph::addToCallGraph).
What is the calls-external node in LLVM's CallGraph?
A sink standing for "any function": an indirect call has an edge to it, and so does a declaration's body (unless the declaration is nocallback).
Why is a direct call graph sound but useless for virtual calls?
Every indirect or virtual call goes to the calls-external node ("may call anything"): nothing is resolved, so no interprocedural optimization can use those edges.
When is a call graph sound (Definition 20.1.2)?
Every edge some execution takes is in T(c), and every body some execution enters is in R. Precision: G1 ⊑ G2 iff R1 ⊆ R2 and T1(c) ⊆ T2(c) for all c.
cha¶
CHA's targets for r.m()
{ lookup(C, m) : C ⪯ decl(r) } — the dispatch result of every subclass of the receiver's declared type (Dean, Grove & Chambers 1995).
What assumption makes CHA-based devirtualization sound?
A closed hierarchy: no subclass of the declared type exists outside the analyzed code (whole program, hidden visibility, or deoptimization when a class is loaded).
Cost of CHA
One pass over reachable bodies; per call site O(|sub(decl(r))|) lookups after indexing the hierarchy — linear in practice.
rta¶
What does RTA add to CHA?
Only classes instantiated (a new) in reachable code count; reachable bodies and instantiated classes grow together to a least fixed point (Bacon & Sweeney 1996).
Why can RTA's fixed point need several rounds?
A newly reachable body can instantiate a class, which adds targets at call sites already processed, which can make more bodies reachable.
RTA's remaining imprecision
One global set of instantiated classes: a receiver is assumed to hold any instantiated subclass of its declared type, even if that class never flows to it.
xta-vta¶
XTA's sets
One class set per method/function and per field/global; new C adds C to the body's set, assignments move classes between bodies and globals (filtered by declared type), a call passes the receiver class into the target's set (Tip & Palsberg 2000).
VTA's sets
One type set per variable, propagated along a type propagation graph of assignments, parameters and returns (Sundaresan et al. 2000) — finer than XTA, still flow-insensitive.
Precision chain of the type-based call graphs
Dynamic ⊆ VTA ⊆ XTA ⊆ RTA ⊆ CHA (edges and reachable bodies), all sound (Theorem 20.1.14).
pta-cg¶
How does a points-to-based call graph resolve an indirect call?
Through the points-to set of the function pointer (or of the receiver's allocation sites, then lookup of their classes) — Definition 20.1.11.
On-the-fly call-graph construction
Add a call edge's parameter/return constraints only when the points-to sets discover the edge, so edges and points-to facts are one least fixed point (Soot's Spark, Doop, SVF).
Why is a CHA-seeded points-to analysis less precise than on-the-fly?
Every CHA edge contributes argument and return flows even if no object reaches the receiver, polluting other points-to sets.
scc-tarjan¶
What does Tarjan's algorithm output on a call graph, and in which order?
The SCCs, each exactly once, in bottom-up order: an SCC is emitted only after every SCC it calls (reverse topological order of the condensation).
What is lowlink(v) in Tarjan's algorithm?
The smallest DFS index reachable from v's subtree through at most one back or cross edge to a node still on the stack; v roots an SCC iff lowlink(v) = index(v).
Cost of Tarjan's SCC algorithm
O(n + e) time, O(n) space; LLVM's scc_iterator is the iterative version.
How does scc_iterator mark nodes of an emitted SCC?
It sets their visit number to ~0U, so they never win a later min (no separate on-stack flag).
traversal¶
Why do summary-based analyses traverse bottom-up?
A function's summary needs its callees' final summaries; bottom-up (Tarjan's order) makes them available, and recursive SCCs are solved by a local fixed point.
Which facts need a top-down traversal? Give three.
Facts that flow from callers: constant arguments passed by every caller, "every caller is norecurse", call-site hotness.
Top-down norecurse rule (rpo-function-attrs)
An internal, non-address-taken function in a non-recursive SCC whose callers are all norecurse is norecurse, even if it calls unknown external code.
Why start a recursive SCC's summaries at ⊥?
The least fixed point is the most precise sound solution; starting optimistic and iterating reaches it (Theorem 20.2.10). Starting at ⊤ would give a sound but weaker fixed point.
cgscc¶
Call edge vs ref edge in LazyCallGraph
Call edge: a direct call. Ref edge: a mere reference (address stored or passed). SCCs use call edges; RefSCCs use call ∪ ref edges.
Why does the CGSCC walk keep RefSCCs?
Devirtualization can turn a ref edge into a call edge; since it already was inside the RefSCC structure, no visited RefSCC can join a cycle with a later one.
What happens when a pass deletes a call inside a visited SCC?
updateCGAndAnalysisManagerFor…Pass splits the SCC, queues the parts not yet visited in postorder, and invalidates the analyses of changed SCCs.
What is devirt<N> in the CGSCC pipeline?
Rerun the SCC's pass pipeline (at most N times) when a pass turned an indirect call into a direct one, so the new callee edge is exploited in the same walk.
inline-classic¶
The inlining problem as an optimization problem
Choose call edges maximizing total benefit within a size budget: a knapsack problem (Scheifler 1977); NP-hard even for a star call graph (Theorem 20.3.4).
GCC's inliner in one sentence
A priority queue of call edges keyed by badness (estimated time saved per size growth), inlined greedily within unit-growth limits (inline_small_functions).
Size-threshold inlining: rule and weakness
Inline iff the callee has at most N instructions. It cannot see that constant arguments would fold most of a large callee, nor that a call is hot.
Why does inlining pay off beyond saving the call?
The copy is specialized to its call site: constant arguments fold, dead branches vanish, loads/stores become visible to the caller's alias analysis and loop optimizations.
inline-llvm¶
Course cost model: cost of a call site
5 × counted instructions of the callee reachable after folding with the constant arguments − (5 × args + 5 + 25), − 15000 if the callee is internal with this as its only use.
Course cost model: threshold
225; ≥ 325 for inlinehint; 3000 at a hot site, ≤ 45 at a cold site (no bonuses); +50% if one callee block is reachable; inline iff cost < max(1, T).
What is the last-call-to-static bonus?
−15000 on the cost when the callee is internal and this is its only call: after inlining it is deleted, so the copy adds no size (TTI::getInliningLastCallToStaticBonus).
Why does InlineCost "simulate" the callee at the call site?
To count only the instructions that survive: operands that become constants fold, and blocks behind folded branches are never reached.
mlgo¶
What does MLGO learn?
A policy π(features) → inline or not, trained offline to minimize final binary size (a delayed per-module reward), then compiled ahead of time into LLVM (MLInlineAdvisor).
Three MLGO features
Call-site height in the call graph, number of constant arguments, caller/callee block and instruction counts (FunctionPropertiesAnalysis), the InlineCost estimate.
What stays hand-written when MLGO decides?
The mechanics and legality: alwaysinline/noinline, recursion rules, InlineFunction. Only the choice among legal candidates is learned.
cloning¶
When may a call site be redirected to the clone g_φ?
Iff φ ⊆ φ_c: every parameter the clone assumes constant receives exactly that constant at the call site (Theorem 20.4.4(a)).
What limits the number of clones in LLVM's function specialization?
A score vs size check per candidate (bonus from InstCostVisitor), and funcspec-max-clones (3 per function by default).
Cloning vs inlining
Cloning specializes once for all call sites with the same constants and keeps one copy per context; inlining specializes per call site and duplicates at every site.
partial-inline¶
Partial inlining's shape
An early-return guard: inline the cheap entry and early exit at each call site, outline the rest (the region dominated by the slow path) into g.slow.
When is region extraction semantics-preserving?
Single-entry region with no escaping alloca, no return of the function, no EH pad entered from outside, no frame-identity intrinsics (Theorem 20.4.4(b)).
GCC's partial inlining pass
ipa-split (fnsplit): splits a function into a header and a .part function at a split point chosen by estimated size and time, then lets the inliner inline the header.
outlining¶
Outlining benefit b(w)
k·ℓ − (k·κ_c + ℓ + κ_f): k occurrences of length ℓ become k calls plus one body and its return.
How does the MachineOutliner find candidates?
Maps instructions to integers and builds a suffix tree; each internal node with ≥ 2 leaves is a repeated sequence (Fraser, Myers & Wendt 1984).
Hot/cold splitting's static coldness
A block is cold if every path from it reaches cold code: unreachable, a noreturn call, or a cold-marked call; maximal cold single-entry regions go to f.cold.N.
ipsccp¶
IPSCCP's lattice values across calls
An internal function's argument = join of the values passed at its executable call sites; a call's result = join of the callee's returned values.
Which functions can IPSCCP track?
Those whose every call site is known: local linkage and address not taken (otherwise arguments are ⊤).
Jump functions (Callahan, Cooper, Kennedy, Torczon 1986)
How each actual argument at a call site depends on the caller's parameters (literal, pass-through, polynomial); solved over the call graph for interprocedural constants.
summaries¶
Functional (summary) approach
Describe each procedure by its input→output effect and apply it at every call: for distributive problems it computes the meet over valid paths (Sharir & Pnueli 1981).
Call-string approach
Tag facts with the last k call sites; exact only with unbounded strings; finite k merges contexts that differ deeper.
Why does a context-insensitive analysis report spurious facts?
It lets a callee's return flow to every call site, including paths that return to a different caller than they came from (unrealizable paths).
ifds-ide¶
IFDS in one sentence
A distributive dataflow problem over a finite fact domain D, solved as realizable-path reachability in the exploded supergraph (Reps, Horwitz & Sagiv 1995).
IFDS complexity
O(E·D³) time for E supergraph edges and D facts (O(E·D) for locally separable, gen/kill problems); path and summary edges take O(N·D²) space.
What does IDE add to IFDS?
Values from a lattice per fact: exploded edges carry micro-functions (e.g. λv. 2v+1), composed into jump functions; phase II evaluates them top-down (Sagiv, Reps & Horwitz 1996).
What is a summary edge in IFDS?
⟨call, d⟩ → ⟨return site, d'⟩ derived when the callee has a path edge from its start fact to its exit fact; reused at every call site with the same input fact.
funcattrs¶
Memory-effect lattice of attribute inference
none < read < write (readnone / readonly / no attribute); a function's effect is the join of its own and its callees'.
SCC-based attribute inference
Bottom-up over SCCs; inside an SCC, ignore calls to members (optimistic), join everything else, give all members the result (Algorithm 20.6.5).
norecurse rule (bottom-up)
A single-function SCC without a self-call whose every call is to a known function that is already norecurse (or a nocallback declaration).
Which functions must never be annotated?
Declarations, optnone functions, and definitions that may be replaced at link time (weak, linkonce: !hasExactDefinition).
deadargelim¶
When is a parameter dead (DAE)?
It is unused, or only passed to dead parameters of internal functions or returned from a function whose return value is dead — a least fixed point over "live if X is live".
DAE's preconditions
Every call site known: local linkage, not address-taken, no musttail users, not varargs with va_start.
What does DAE do with a dead return value?
Changes the function to return void and replaces uses of call results (only in dead positions) with poison.
argpromotion¶
Argument promotion in one sentence
Replace a pointer parameter by the values loaded from it, loading them at each call site instead (by-reference to by-value).
Argument promotion's three conditions
Every use of p is a load at a constant offset; nothing writes those locations before the loads; each location is dereferenceable at every call site.
Why run argument promotion in the CGSCC walk?
It changes signatures of internal functions whose callers are all known; after promotion, SROA and mem2reg can promote the callers' aggregates too.
globalopt¶
GlobalOpt: when can a global become constant?
It is internal, its address does not escape, and it is never stored to: loads fold to its initializer.
GlobalOpt: shrink to bool
An internal global stored with a single value V besides its initializer becomes an i1 "has been stored" flag; loads become select(flag, V, init).
GlobalOpt: localize
An internal global used only in main, which is norecurse, becomes an alloca in main.
GlobalOpt: SRA of globals
An aggregate global accessed only through constant-index GEPs is split into one global per accessed field.
wpd¶
What is type metadata used for in WPD?
!type on vtables says which address points are compatible with which class; llvm.type.test at each virtual call identifies the slot's candidate vtables.
WPD's single-implementation rule
If a (type, offset) slot has one target in all compatible vtables, replace the indirect call by a direct call (DevirtModule::trySingleImplDevirt).
Virtual constant propagation
Targets readnone with constant arguments: evaluate them at compile time; uniform result → constant; i1 true in one vtable → compare vptr; else store results next to each vtable and load them.
Why does WPD need -fwhole-program-vtables?
The rewrite is only sound if no other vtable compatible with the class exists outside the LTO unit (closed hierarchy, Definition 20.7.2).
spec-devirt¶
Speculative call shape
if (fp == @g) call @g(args) else call fp(args); the direct arm can be inlined; the fallback keeps every other target correct.
LLVM's ICP thresholds
Promote in decreasing count while count ≥ 30% of the remaining count and ≥ 5% of the total, at most 3 targets (icp-remaining-percent-threshold, icp-total-percent-threshold, icp-max-prom).
Type feedback (Hölzle & Ungar 1994)
Record the receiver types seen at run time and guard + inline the common target: the origin of speculative devirtualization and ICP.
tce¶
When is a call in tail position?
It is followed only by a return of its result (or ret void), possibly via a shared return block holding just a phi of the result.
What does the tail marker promise?
The callee does not access the caller's stack frame (allocas); markTails sets it only when no alloca escapes. musttail requires the jump.
Sibling-call optimization
The code generator emits a jump instead of call+ret when the callee's arguments fit the caller's frame and calling conventions match; the callee returns to the caller's caller.
tre¶
TRE in one sentence
Replace a self-recursive tail call by assignments to argument phis and a branch back to a new loop header "tailrecurse".
When can TRE introduce an accumulator?
When one instruction a = call ⊕ x follows the call, ⊕ is associative and commutative with an identity, x does not depend on the call, and a is only returned.
TRE accumulator invariant
At the loop header, acc ⊕ f(current args) equals the original call's result; returns become acc ⊕ returned value.
Why may TRE not run with an escaping alloca?
The recursive call might read the caller's local through a pointer; turning the recursion into a loop would reuse (overwrite) that frame slot.
Why must TRE drop nsw/nuw flags on the accumulator?
The operations are performed in a different order, so intermediate results can overflow where the original ones did not.
lto¶
LTO symbol resolution flags
Per symbol per object: prevailing (p), visible to regular objects (x), ... The linker supplies them; LTO may internalize a prevailing symbol that is not visible outside the IR.
Why internalize in LTO?
Local linkage lets every IPO pass delete, clone, specialize or change the signature of a function, and GlobalOpt treat globals as fully known.
Monolithic LTO pipeline
IR move of all modules into one → internalize → lto<O2> (IPSCCP, WPD, GlobalOpt, inliner, ...) → codegen (optionally in parallel partitions).
thinlto¶
ThinLTO in one sentence
Per-module summaries, a thin link over the combined index (imports, exports, internalization, dead symbols, WPD), then parallel, cacheable per-module backends (Johnson, Amini & Li 2017).
ThinLTO import threshold rule
Start at import-instr-limit (100), multiply by 0.7 per level of an import chain (import-instr-evolution-factor); hot edges ×10, critical ×100, cold ×0.
What is promotion in ThinLTO?
Local symbols referenced by an exported or imported function are renamed to unique global names (.llvm.<hash>) so the imported copy can still refer to them.
How does an imported function appear in the importing module?
As an available_externally definition: it may be inlined and analyzed, but it is not emitted there.
ipgo¶
Edge profile and flow conservation
Counts per CFG edge; at every block incoming = outgoing (with a virtual exit→entry edge), so counters on the complement of a spanning tree determine all counts.
How many counters does spanning-tree instrumentation need?
|E⁺| − |V| + 1, where E⁺ includes the virtual exit→entry edge (Knuth & Stevenson 1973; LLVM's CFGMST, a maximum-weight tree).
Why does LLVM run a pre-inliner before PGO instrumentation?
Counts measured before inlining are per function (context-insensitive); inlining small callees first makes their counts per call site. CSPGO adds a second instrumentation after inlining.
Scaling a profile at inlining
The copy at site k gets c_g(e)·n_k/N_g; exact only if the callee behaves alike at every call site (Theorem 20.10.4).
autofdo¶
AutoFDO in one sentence
Sample the optimized production binary with perf (LBR), map addresses to source lines via debug info, and feed per-line counts to the next compile (Chen, Li & Moseley 2016).
Sample-profile block weight
The maximum sample count over the block's instructions (keyed by line offset and discriminator); missing weights are inferred by propagation or profi (min-cost flow).
Instrumentation vs sampling PGO
Instrumentation: exact counts, separate training build and run, slower. Sampling: statistical and lossy after optimization, but from production at negligible cost.
What is a discriminator?
An extra number in debug locations that separates different basic blocks on the same source line, so samples can be attributed to the right block.
bolt¶
Pettis–Hansen function ordering
Merge chains of functions along call-graph edges in decreasing weight, orienting each merge so the endpoints of the edge are closest ("closest is best").
Is greedy function ordering optimal?
No: minimizing Σ w·distance is weighted minimum linear arrangement, NP-hard; greedy merging can fix a hub between the wrong neighbours (Proposition 20.10.8).
BOLT vs Propeller
BOLT rewrites the linked binary from a disassembled CFG and a perf profile; Propeller emits basic-block sections at compile time and reorders them at a relink from the profile.
What do post-link optimizers change?
Code layout only: block order, hot/cold splitting, function order — for i-cache and TLB locality of the final binary.