Flashcards — Chapter 19¶
99 cards. Review them with spaced repetition in the terminal (./course flash 19) or export them to Anki (./course flash export 19). Here, click a card to reveal its back.
alias-queries¶
The four alias answers and what each promises
NoAlias: the byte intervals never intersect. MustAlias: they start at the same address in every related pair of executions. PartialAlias: they overlap at a known offset d ≠ 0. MayAlias: no information (always sound).
Which direction may an alias analysis err in?
Only towards MayAlias. Answering NoAlias (or Must/Partial) for a pair that behaves otherwise in some execution is unsound and leads to miscompiles.
Why is exact alias analysis impossible?
It is undecidable: a program can make a store alias a variable exactly when an arbitrary computation halts (Theorem 19.1.8).
aa-eval on store i64 %p vs store i32 (p+4)
PartialAlias (off 4): the 8-byte and 4-byte intervals overlap and start 4 bytes apart.
modref¶
Mod/ref lattice
Subsets of {ref, mod}: NoModRef ⊑ Ref, Mod ⊑ ModRef. Chains intersect the members' answers.
Why can an opaque call be NoModRef for a local?
If the local has not been captured before the call, no pointer to it exists outside the caller's own values, so the callee can reach it only through its arguments (Lemma 19.1.10).
memory(argmem: write) call vs a noalias pointer it does not receive
NoModRef: the callee writes only through its pointer arguments, none of which may alias the location.
aa-pipeline¶
How does LLVM combine alias analyses for an alias query?
AAResults asks each AA in order and returns the first answer that is not MayAlias (AAResults::alias).
How does LLVM combine analyses for a mod/ref query?
It intersects the members' ModRefInfo (Result &= …) and stops early at NoModRef.
LLVM 23's default AA pipeline
BasicAA, then scoped-noalias AA, then TBAA; GlobalsAA as a cached module result when available (PassBuilder::buildDefaultAAPipeline).
Can a chain be less precise than one of its members?
No: it returns May only if every member did, and sound definite answers cannot conflict on executed accesses (Proposition 19.1.9).
basicaa¶
BasicAA: two different identified objects
NoAlias: distinct allocations (allocas, globals, noalias calls, noalias arguments) never overlap.
BasicAA's constant-offset GEP rule
Same base and variable part, constant distance d: NoAlias iff d ≥ s1 or −d ≥ s2; MustAlias iff d = 0 and equal sizes; otherwise PartialAlias (Lemma 19.2.10).
BasicAA: the object-size rule
If an access of s bytes would not fit in the other pointer's underlying object, they cannot alias (it would be out of bounds, i.e. UB).
BasicAA on phi and select
Answer for each operand; if all agree return that answer, else MayAlias.
Why does a[i] vs local[j] give NoAlias for an argument a?
An argument cannot point into a function-local identified object, which is created after the argument's value is fixed.
capture¶
What captures a pointer?
Storing it as a value, passing it to a call parameter that is not captures(none), returning it (when counted), or ptrtoint; loads/stores through it and comparisons do not.
Capture tracking: cost and limit
One walk over the uses of the pointer and derived values; LLVM gives up (assumes captured) after 100 uses.
Captured-before vs captured-anywhere
PointerMayBeCapturedBefore / EarliestEscapeAnalysis ask whether a capture can execute before a given instruction; a local that escapes late is still private before that.
globalsaa¶
Which globals does GlobalsAA track?
Internal globals whose address is never taken: every use is a load or store that names them.
How does GlobalsAA compute per-function mod/ref?
Bottom-up over call-graph SCCs: union of the SCC's own loads/stores of tracked globals and the callees' summaries; indirect calls or callbacks make it unknown.
Why can a call to an external function stay ModRef for a static global?
The external function may call back into the module (no nocallback/nosync), and a module function may access the global.
tbaa¶
C's effective-type rule in one sentence
An object may be accessed only through its own type (up to qualifiers/signedness), an aggregate or union containing it, or a character type (C11 §6.5 ¶7); C++ adds std::byte.
A TBAA access tag
(base type, access type, offset): e.g. b->a.i in struct B {int k; struct A a;} with struct A {short s; int i;} is (B, int, 8).
Why does a char access never get NoAlias from TBAA?
omnipotent char is an ancestor of every scalar type, so the least common type is char and the char tag accesses the whole common type.
TBAA and type punning
Punning ((float)&int_var) is UB; TBAA-based optimization may then return stale values. -fno-strict-aliasing drops the tags.
TBAA: b->k (B,int,0) vs a->i (A,int,4)
NoAlias: both are int, but walking from B at 0 never meets A and walking from A at 4 never meets B.
scoped-noalias¶
What does restrict promise?
During the block, an object accessed through the restrict pointer and modified is accessed only through pointers based on it (C11 §6.7.3.1).
ScopedNoAliasAA's rule
NoAlias if for some domain the access's alias.scope list (non-empty) is a subset of the other access's noalias list, in either direction.
Why does the inliner create alias.scope/noalias metadata?
After inlining, noalias parameters disappear; per-call scopes in a fresh domain keep the promise for the inlined body (AddAliasScopeMetadata).
andersen¶
Andersen's four constraint forms
p = &a: a ∈ pts(p); p = q: pts(p) ⊇ pts(q); p = *q: pts(p) ⊇ pts(o) for o ∈ pts(q); *p = q: pts(o) ⊇ pts(q) for o ∈ pts(p).
What does Andersen's worklist do when it pops n?
For each o ∈ pts(n): add o → p for loads p = *n and q → o for stores *n = q; then propagate pts(n) along every edge n → m.
Andersen's worst-case bound and why
O(n³) with difference propagation: ≤ n² edges, each object crosses each edge once; Θ(n³) on the complete bipartite family (Proposition 19.4.16).
Andersen on the running example: pts(u), pts(r), pts(a)?
{c}, {p}, {} — the five cycle nodes p, q, s, t, b get {a, b, c}.
Why is Andersen sound?
Every solution of the inclusion constraints over-approximates every store reached by executing the statements in any order (Theorem 19.4.12).
cycle-detection¶
Why can cycles of the constraint graph be collapsed?
All nodes on a cycle of satisfied edges have equal sets in every solution (Lemma 19.4.13), so merging them preserves the least solution.
Lazy cycle detection trigger
When propagation along n → m finds pts(n) = pts(m) ≠ ∅ and that edge has not triggered before: run Tarjan from m and collapse.
Hybrid cycle detection (HCD)
Offline SCCs over variables and ref nodes *v; a cycle through one ref node *a with ordinary b means: collapse every object of pts(a) with b as it appears.
Online cycle detection (Pearce et al.)
On each new edge x → y, check whether y reaches x (cheaply, with a dynamic topological order) and collapse the SCC.
wave-propagation¶
Wave propagation round
Collapse all SCCs, propagate sets once in topological order, add the edges loads and stores now require; repeat until no edge is added.
Why is one wave enough for the current edges?
In topological order every predecessor is final before a node propagates, so all current edges are satisfied after the wave.
Deep propagation
Push each difference depth-first from the node that changed, detecting cycles on the DFS stack (Pereira & Berlin 2009).
steensgaard¶
Steensgaard's rule for p = q
Join the class p points to with the class q points to (and recursively their pointees): equality, not inclusion.
Steensgaard's complexity
O((n + m) α(n + m, n)) with union by rank and path compression (Tarjan 1975).
Precision ordering theorem
Andersen ⊆ Steensgaard: a unification solution satisfies all inclusion constraints, and Andersen's is the least (Corollary 19.5.7).
Does Steensgaard's result depend on statement order?
No: it computes the finest unification solution, which is unique (Theorem 19.5.8).
das¶
Das's one-level flow in one sentence
Inclusion (a directed flow edge) at the top level of each assignment, unification of everything one level below.
Precision of Das's analysis
Andersen ⊆ Das ⊆ Steensgaard (Theorem 19.5.9); on the running example pts(u) = {c} like Andersen, pts(a) = {a,b,c} like Steensgaard.
Das's invariant on flow edges
Every flow edge a → b has D(a) = D(b): the dereference nodes of its ends are unified.
flow-sensitive¶
Strong update condition
A store *p = q replaces o's contents if pts(p) = {o} and o is a singleton (not a summary object like a heap site in a loop).
SFS's two stages
(1) an auxiliary flow-insensitive analysis defines which stores/loads touch which objects, giving memory SSA def-use chains; (2) sparse flow-sensitive propagation along them.
Why does SSA give flow sensitivity for free?
Each SSA value has one definition, so a per-value set is per-definition; only memory needs extra machinery.
field-sensitivity¶
Field-insensitive vs field-based vs field-sensitive
One location per object / one per field name shared by all objects / one per (object, field).
Positive-weight cycle (PWC)
A cycle of offset constraints with positive total offset: it would derive o.0, o.1, … forever; Pearce et al. collapse such objects to field-insensitive.
How GCC names fields in points-to dumps
By bit offset and size: s.0+64 is bits 0–63 of s; field sensitivity is enabled at -O2 (max-fields-for-field-sensitive = 100).
call-strings¶
k-call-string context
The last k call sites on the stack; a call at s from context c enters the callee in the last k elements of c·s.
Why can 1-CFA fail on a wrapper?
id called only from wrapper w at one site d gets the single context ⟨d⟩, merging all of w's callers; 2-CFA keeps ⟨c1,d⟩ and ⟨c2,d⟩.
Contexts in k-CFA, worst case
S^k for S call sites; Andersen over (context, variable) nodes then costs O((n S^k)³).
cloning-summaries¶
Cloning (Whaley–Lam)
A context per acyclic call path after collapsing recursive SCCs; 10^14 contexts made feasible with BDDs.
Summary-based (functional) approach
Analyse each function once parametrically in its inputs and instantiate the summary at every call site (Sharir & Pnueli).
LLVM's pointer summaries
function-attrs infers memory(...) and captures(none) bottom-up over call-graph SCCs; alias queries use them at every call.
object-sensitivity¶
Object sensitivity
A method is analysed per receiver object (allocation site, plus the receiver's heap context up to depth k) (Milanova, Rountev & Ryder 2005).
Type sensitivity
Object sensitivity with each allocation site in a context replaced by the class containing it: coarser, much cheaper (Smaragdakis et al. 2011).
Box.set/get on two Box objects: object-sensitive vs insensitive
Object-sensitive: x → hA, y → hB; insensitive: both get {hA, hB}.
datalog-pta¶
The load rule of points-to Datalog
pts(p, o) :- load(p, q), pts(q, r), pts(r, o).
The store rule of points-to Datalog
pts(r, o) :- store(p, q), pts(p, r), pts(q, o).
Why does the Datalog minimal model equal Andersen's least solution?
Sets of facts closed under the rules are exactly solutions of the inclusion constraints (Theorem 19.8.5).
bddbddb
Datalog evaluated with binary decision diagrams; variable ordering decides performance (Whaley, Avots, Carbin & Lam 2005).
demand-driven¶
Demand-driven points-to
Answer one query by solving only the constraints relevant to it (grown on demand), with caching (Heintze & Tardieu 2001).
Refinement-based analysis (Sridharan & Bodík)
CFL reachability with matched field/call parentheses, refined only where the client needs it, within a budget.
What does SVF's ContextDDA do when a query runs out of budget?
It downgrades the query to the flow-sensitive answer instead of failing.
escape¶
Escape states (Choi et al.)
NoEscape ⊏ ArgEscape ⊏ GlobalEscape: not reachable after return / reachable from parameters or return value / reachable from globals or other threads.
What does NoEscape allow?
Stack allocation or scalar replacement of the object, and elision of locks on it (Theorem 19.9.6).
Go: "moved to heap: q"
q's address is returned (or otherwise outlives the frame), so the variable is heap-allocated.
HotSpot flag to disable escape analysis
-XX:-DoEscapeAnalysis; -XX:+PrintEscapeAnalysis exists only in debug JVMs (notproduct).
shape¶
Why can points-to not prove a list acyclic?
All nodes from one allocation site are one abstract object pointing to itself; shape analysis keeps definite nodes and summary nodes apart.
Three-valued logic in TVLA
Predicate values 0, 1, 1/2 (unknown); summary individuals; canonical abstraction merges nodes with equal abstraction predicates.
lseg(x, y)
Separation logic's acyclic list segment from x to y; x ↦ y ∗ lseg(y, z) with y not a program variable abstracts to lseg(x, z).
memoryssa¶
MemoryDef / MemoryUse / MemoryPhi
A write (new memory version) / a read / a merge of versions at a join; liveOnEntry is version 0.
Where does LLVM place MemoryPhis?
At the iterated dominance frontier of the blocks containing MemoryDefs (placePHINodes): minimal SSA for one memory variable.
Clobbering access of a load
The nearest access above it that may write its location, skipping non-aliasing defs; at a phi whose paths disagree, the phi.
memssa-check-limit
The walker's step budget (default 100); when exhausted it returns a conservative but correct access.
Optimized use
A MemoryUse whose defining access was replaced by its clobber; print<memoryssa> shows uses after optimization.
sroa¶
SROA in three steps
Build slices of an alloca, form partitions of overlapping unsplittable slices, rewrite each partition into its own alloca and promote.
What stops SROA?
A use it cannot analyse: the alloca's address escapes, or an access has an unknown offset or size.
SROA and memcpy
A splittable slice: a memcpy into an aggregate is cut at partition borders into per-partition loads/stores.
dse¶
When is a store dead?
Every path from it — including an unwinding exit — reaches a complete overwrite of the same bytes (MustAlias, ≥ size; in a loop only through loop-invariant pointers) before any may-read, or the memory dies (non-escaping local at exit).
Partial overwrite in LLVM's DSE
A memset/memcpy overwritten at the start or end is shortened by tryToShorten, keeping the intrinsic's alignment.
No-op store
store (load p), p with no write to p in between: deleted.
Why is a volatile store never deleted or used as a kill?
Its execution is observable behavior.
load-forwarding¶
Store-to-load forwarding condition
The load's clobber is a simple store that dominates it, MustAliases it, and has the same type.
Redundant load condition (with MemorySSA)
An earlier dominating load of the same type and MustAlias location whose MemoryUse is dominated by the later load's clobber.
Load PRE (GVN)
If the value is available in all predecessors but one, insert the load there and merge with a phi.
memcpyopt¶
memcpy forwarding
memcpy(b, a); memcpy(c, b) → memcpy(c, a) when nothing wrote a or b in between and the second copies no more than the first.
memset formation
Adjacent stores of the same byte value become one memset (tryMergingIntoMemset).
Call-slot optimization
A call that writes a temporary later copied to d writes d directly, if d is not accessed in between and the call cannot see d.
licm-promotion¶
LICM promotion: what is needed?
A must-alias set of loop-invariant loads/stores with no other access in the loop that may write it.
Load-only promotion
If other loop accesses may read the location, only loads are promoted and the stores stay in the loop.
When may promotion sink the store to the exits?
If a store executes on every iteration (guaranteed) or the location is an uncaptured local, so the extra store is unobservable.