Skip to content

Lesson 19.2 — Local alias rules: BasicAA, capture tracking, GlobalsAA

Techniques: BasicAA-style reasoning (underlying objects, distinct allocations, GEP decomposition and offset arithmetic, object sizes, phi/select recursion); capture (escape) tracking; GlobalsAA (mod/ref of non-address-taken globals, bottom-up over the call graph) · Pebble implements: nothing directly; exercises E1–E2 get these answers through AAResults, and E1's "local that never escapes" rule is capture tracking · Prerequisites: Lesson 19.1; Ch 9, GEP in full (the gep-offset drill); call graphs and SCCs (Ch 20 is later; Lesson 15.2's SCCs suffice) · Time: 4–5 hours

1. Problem and motivation

Most alias questions a compiler asks are local and easy for a human: two different arrays never overlap, a[i] and a[i+1] are four bytes apart, a local whose address was never passed anywhere cannot be touched by a call. Whole-program points-to analysis (Lessons 19.4–19.8) can answer them too, but it is expensive and needs the whole program. The local rules answer most queries in microseconds from the function alone, which is why every production compiler runs them first. LLVM puts them in BasicAA [LLVM-BasicAA]; GCC in its alias oracle [GCC-TreeAlias]. Diwan, McKinley and Moss measured that simple, local rules already give most of the optimization benefit for their clients [DMM98].

BasicAA

BasicAA answers a query by looking at where each pointer comes from: strip casts and GEPs to find the underlying object (an alloca, a global, an argument, a call result); if the objects are different and both are "identified", the pointers do not alias. If they share a base, compare the byte offsets computed by the GEPs. If a pointer is a phi or select, answer for each incoming value and combine. The rules come from the definition of the memory model: separate allocations never overlap, and an in-bounds GEP stays inside its object (Ch 9).

Capture tracking

A local variable whose address is never stored, returned or passed to an unknown function is private: no other pointer in the program can reach it. Capture tracking decides this by walking the uses of the pointer. It is what lets BasicAA say that an opaque call cannot touch a local, and what lets DSE delete the last stores to a local before return (Lesson 19.11).

GlobalsAA

Globals are the opposite case: every function in the module may access them. But an internal (static) global whose address is never taken can only be accessed by name, by the functions of this module. GlobalsAA computes, for every function, which such globals it (and everything it calls) may read or write, bottom-up over the call graph. Then a call to a function that never touches counter is NoModRef for counter.

2. Definitions and algorithms

BasicAA

Definition 19.2.1 (Underlying object)

The underlying object \(\mathrm{obj}(p)\) of a pointer value \(p\) is obtained by repeatedly replacing \(p\) by its base operand while \(p\) is a getelementptr, a pointer cast or an addrspacecast (at most MaxLookupSearchDepth steps); the value reached is an alloca, a global, an argument, a call result, a load, a phi, a select or a constant. Every address \(p\) can denote lies within the object allocated by \(\mathrm{obj}(p)\) when all the GEPs on the way are inbounds (Ch 9).

Definition 19.2.2 (Identified object)

An identified object is a value that denotes a fresh allocation distinct from every other identified object: an alloca, a global variable (not a global alias), the result of a call whose return value is noalias (such as malloc), or a noalias argument. The first three are function-local identified objects when they are allocas or noalias calls of the function being analysed.

Definition 19.2.3 (Decomposed GEP)

A pointer \(p\) decomposes to \((b, c, \{(s_1, v_1), \dots, (s_k, v_k)\})\) if \(p = b + c + \sum_{i} s_i \cdot v_i\) as byte addresses, where \(b\) is a non-GEP base, \(c\) a constant, \(s_i\) constant scales and \(v_i\) SSA integer values (extensions looked through). For %x = getelementptr inbounds [4 x i8], ptr %a, i64 %idx, the decomposition is \((\%a, 0, \{(4, \%idx)\})\); for getelementptr i8, ptr %x, i64 4 it is \((\%a, 4, \{(4, \%idx)\})\).

Algorithm 19.2.4 (BasicAA alias check)

  • Input: locations \((p_1, s_1)\), \((p_2, s_2)\) in one function \(F\).
  • Output: an answer of Definition 19.1.2.
  • Precondition: the IR is valid; inbounds and noalias promises hold (otherwise the program has undefined behavior and any answer is allowed).
  • Postcondition: the answer is sound (Theorem 19.2.11).
  • Invariant: each recursive call is on a strictly smaller pair (a phi/select operand replaces a phi/select), bounded by the query cache and the depth limit; a cycle through phis returns the cached provisional answer MayAlias.
function Alias(p1, s1, p2, s2):
    p1, p2 ← strip casts
    if p1 = p2 (and not a value from a different loop iteration): return Must
    o1, o2 ← obj(p1), obj(p2)                                    # Definition 19.2.1
    if o1 ≠ o2:
        if o1, o2 are both identified objects: return No           # distinct allocations
        if one is an argument and the other a function-local identified object: return No
        if one is a call/load result r and the other a local ℓ not captured before r: return No   # Definition 19.2.6
    if s2 > size(o1) or s1 > size(o2): return No                 # an access larger than the object
    if p1 or p2 is a GEP: r ← AliasGEP(p1, s1, p2, s2); if r ≠ May: return r
    if p1 or p2 is a phi: return AliasPhi(p1, s1, p2, s2)
    if p1 or p2 is a select: return AliasSelect(p1, s1, p2, s2)
    return May

function AliasGEP(p1, s1, p2, s2):
    (b1, c1, V1) ← Decompose(p1);  (b2, c2, V2) ← Decompose(p2)
    if Alias(b1, ⊤, b2, ⊤) = No: return No                        # different bases never meet
    if b1 = b2 (Must):
        V ← V1 − V2      # cancel equal (scale, value) terms
        if V = ∅:        # constant distance d = c2 − c1
            d ← c2 − c1
            if d ≥ s1 or −d ≥ s2: return No                       # [0, s1) and [d, d + s2) disjoint
            if d = 0 and s1 = s2: return Must
            return Partial (offset d)
        g ← gcd of the scales in V; if every value of Σ V lies in g·ℤ and the intervals
             [0, s1) and [c2 − c1 + g·k, … + s2) are disjoint for all k: return No       # modular reasoning
    return May

function AliasPhi(φ, s, q, t):    # φ = phi(x1, …, xn)
    r ← Alias(x1, s, q, t)
    for i ← 2 to n: if Alias(xi, s, q, t) ≠ r: return May
    return r

function AliasSelect(σ, s, q, t):  # σ = select(c, x, y): the same with two operands
    return Alias(x, s, q, t) if Alias(x, s, q, t) = Alias(y, s, q, t) else May

size(o) is the allocation size of an identified object when it is known (the alloca type, the global's type, malloc's constant argument), and \(\infty\) otherwise.

Capture tracking

Definition 19.2.5 (Derived pointer)

A value \(v\) is derived from a pointer \(p\) if \(v = p\), or \(v\) is a GEP, cast, phi or select one of whose pointer operands is derived from \(p\).

Definition 19.2.6 (Capture)

A pointer \(p\) is captured by an instruction \(I\) if \(I\) may make some bit of \(p\)'s value (the address) available beyond the values derived from \(p\): \(I\) stores a value derived from \(p\) to memory (as the value operand), passes it to a call argument that is not captures(none) (nocapture), converts it with ptrtoint, or returns it (when return counts as capture). A local object is captured before an instruction \(J\) if some capturing instruction can execute before \(J\) on some path. An object that is not captured anywhere is non-escaping.

Algorithm 19.2.7 (Capture tracking: may the pointer be captured?)

  • Input: a pointer \(p\); a flag \(\mathit{returnCaptures}\); a limit \(U\) on the number of uses explored.
  • Output: false only if no use of any value derived from \(p\) captures it.
  • Precondition: none.
  • Postcondition: a false answer means \(p\) is non-escaping (Lemma 19.2.12).
  • Invariant: the worklist holds uses of values derived from \(p\); every derived value's uses are enqueued once.
function MayBeCaptured(p, returnCaptures, U):
    W ← uses of p;  seen ← W;  n ← 0
    while W ≠ ∅:
        u ← pop(W);  I ← the user instruction;  n ← n + 1
        if n > U: return true                                   # give up: assume captured
        case I of
          load from u, store to address u:             continue # dereferencing is not capturing
          store whose stored value is u:                return true
          call, u passed as an argument:  if the parameter is captures(none) and the
                                          call does not return it: continue else return true
          ret u:                          if returnCaptures: return true else continue
          icmp u with null or with a local:   continue           # comparing leaks no address
          getelementptr, bitcast, phi, select: for each use x of I not in seen: push x; seen ∪= {x}
          otherwise (ptrtoint, …):        return true
    return false

GlobalsAA

Definition 19.2.8 (Non-address-taken global)

An internal (module-local) global variable \(g\) is non-address-taken if every use of \(g\) is the pointer operand of a load or store (or of a call to a function known not to capture it): its address is never stored, passed, compared or converted. Such a global can be accessed only by the loads and stores that name it.

Algorithm 19.2.9 (GlobalsAA)

  • Input: a module; its call graph with SCCs in bottom-up (callees first) order.
  • Output: for every function \(f\) a map \(\mathit{FI}(f)\) from non-address-taken globals to \(\mathit{MR}\), or "unknown".
  • Precondition: the call graph contains every direct call; indirect calls and calls to declarations are treated below.
  • Postcondition: for every call \(c\) of \(f\) and non-address-taken \(g\), \(\mathit{MR}(c, g) \subseteq \mathit{FI}(f)(g)\) (Theorem 19.2.13).
  • Invariant: when an SCC is processed, every callee outside it already has its final \(\mathit{FI}\) (or is unknown).
function GlobalsAA(M):
    G ← { g internal : g is non-address-taken (Definition 19.2.8) }
    for each SCC S of the call graph, callees before callers:
        FI ← ∅ (every g ↦ NoModRef);  unknown ← false
        for each f in S:
            if f is a declaration:
                if f may call back into M (not nocallback) or may synchronize (not nosync): unknown ← true
                # otherwise f cannot touch any global of G
            else:
                for each load/store of some g ∈ G in f: FI(g) ← FI(g) ∪ {ref or mod}
                for each call in f:
                    if indirect: unknown ← true
                    else if callee ∉ S: if FIof(callee) is unknown: unknown ← true
                                        else FI ← FI ∪ FIof(callee)      # pointwise ∪
        for each f in S: FIof(f) ← (unknown ? "unknown" : FI)      # one summary per SCC
    return FIof

query ModRef(call c of f, location of g):  if g ∈ G and FIof(f) is known: return FIof(f)(g) else ModRef

3. Worked example

BasicAA

The kernel of the first box (§7), compiled by clang-23 -O1:

struct pt { int x, y; };
int g;
void kern(int *a, struct pt *s, int i) {
  int local[4];
  a[i] = 1;  a[i + 1] = 2;  s->x = 3;  s->y = 4;  local[i] = 5;
  g = local[0] + *(char *)&s->y;
}

Its pointers are %arrayidx = a + 4i, %arrayidx2 = %arrayidx + 4, %s, %y = s + 4, %arrayidx4 = local + 4i, %local and @g; every access is 4 bytes. Algorithm 19.2.4 on each of the 21 pairs:

pair objects rule that decides answer
%arrayidx, %arrayidx2 %a, %a AliasGEP: \(V_1 - V_2 = \emptyset\), \(d = 4 \ge s_1 = 4\) No
%arrayidx, %s; %arrayidx2, %s; both with %y %a, %s two arguments: nothing applies May
%s, %y %s, %s AliasGEP: \(d = 4 \ge 4\) No
%arrayidx4 with %arrayidx, %arrayidx2, %s, %y %local vs argument argument vs function-local identified object No
%local with %arrayidx, %arrayidx2, %s, %y same same No
%arrayidx4, %local %local, %local AliasGEP: \(V = \{(4, i)\}\) does not cancel May
@g with %arrayidx, %arrayidx2, %s global vs argument an argument may point to @g May
@g, %y @g vs %s object size: %y = s + 4 inbounds, so %s's object has at least 8 bytes; @g has 4 No
@g with %arrayidx4, %local two identified objects distinct allocations No

That is 13 NoAlias and 8 MayAlias, exactly the box's summary line.

Capture tracking

In the second box f has two locals: private_ is only loaded and stored; &leaked is passed to keep. Algorithm 19.2.7 on %leaked: its uses are a store to its address (continue), the call keep(%leaked) with a parameter that is not captures(none) → captured. On %private_: a store to its address, a load from it: the worklist empties → not captured. So for the calls keep(...) and opaque(), BasicAA's mod/ref (Lemma 19.1.10) answers NoModRef for %private_ and ModRef for %leaked, and after -O1 the load of private_ is folded to the constant 1 while the load of leaked stays after the calls.

GlobalsAA

In the third box, counter is static and only loaded and stored by name: \(G = \{\mathit{counter}\}\) (shared is external, so not in \(G\)). Bottom-up over the SCCs {set_shared}, {bump}, {log_it}, {f}:

SCC body accesses to \(G\) calls \(\mathit{FI}\)
set_shared none (shared ∉ \(G\)) none counter ↦ NoModRef
bump load and store of counter none counter ↦ ModRef
log_it (declaration) — may call back into the module unknown
f store and load of counter set_shared, bump, log_it (unknown) unknown

So call set_shared is NoModRef for @counter; call bump stays ModRef (it really writes it); call log_it stays ModRef (it might call f, which writes it).

Try it yourself: this lesson has no drill of its own; the quiz asks for BasicAA answers on concrete GEPs, and ./course drill gep-offset (Ch 9) practises the offset arithmetic that AliasGEP relies on.

4. Invariants and correctness

BasicAA

Lemma 19.2.10 (The constant-offset GEP rule)

If \(p_1\) and \(p_2\) decompose to the same base \(b\) with the same variable terms and constant parts \(c_1, c_2\), and \(d = c_2 - c_1\), then the intervals \([p_1, p_1 + s_1)\) and \([p_2, p_2 + s_2)\) are disjoint in every execution iff \(d \ge s_1\) or \(-d \ge s_2\); they start at the same address iff \(d = 0\).

Proof

In any execution, \(p_2 - p_1 = (b + c_2 + \Sigma) - (b + c_1 + \Sigma) = d\), where \(\Sigma\) is the common variable part, evaluated to the same number because the terms are the same SSA values in the same execution (the relation of Definition 19.1.2 is "same dynamic instance of the values", which is why BasicAA refuses values from different loop iterations). The intervals are \([p_1, p_1 + s_1)\) and \([p_1 + d, p_1 + d + s_2)\). Two half-open intervals \([x, x + s)\) and \([y, y + t)\) are disjoint iff \(y \ge x + s\) or \(x \ge y + t\); with \(y - x = d\) this is \(d \ge s_1\) or \(-d \ge s_2\). They start together iff \(d = 0\).

Theorem 19.2.11 (BasicAA is sound)

Under its precondition, every answer of Algorithm 19.2.4 is sound.

Proof

By induction on the recursion (well-founded by the invariant). Must is returned only for equal values (same address) or by Lemma 19.2.10 with \(d = 0\) and equal sizes. No is returned in five places. (1) Two different identified objects are two distinct allocations (Definition 19.2.2), and by the memory model distinct live allocations occupy disjoint bytes; since both pointers point into their objects (Definition 19.2.1, inbounds), the accessed bytes are disjoint. For a noalias argument, the attribute's semantics make accesses through it disjoint from accesses not based on it. (2) An argument cannot point into a function-local identified object: the object is created after the argument's value was fixed. (3) A call or load result \(r\) cannot hold the address of a local not captured before \(r\): nothing outside the function's own derived values has seen that address (Lemma 19.2.12). (4) If an access of \(s_2\) bytes were to fit inside an object of fewer than \(s_2\) bytes it would be out of bounds, which is undefined behavior. (5) AliasGEP returns No by Lemma 19.2.10, or when the bases themselves never meet. AliasPhi/AliasSelect return a definite answer only if every operand yields it; the pointer equals one of the operands in each execution, so the answer holds for it (induction hypothesis). Otherwise May, which is always sound.

Capture tracking

Lemma 19.2.12 (Capture tracking is sound)

If Algorithm 19.2.7 returns false for a pointer \(p\) to an object \(o\) created in \(F\), then during the execution of \(F\) no value outside the values derived from \(p\) (and no memory location) ever holds an address inside \(o\).

Proof

Suppose some value \(w\) not derived from \(p\) holds an address in \(o\). Addresses of \(o\) come into existence only as \(p\) and values computed from it. Take the first moment an address of \(o\) leaves the set of derived values. It must flow through an instruction that uses a derived value and produces something that is not derived: a store of it as a value (the address enters memory), a call argument without captures(none) (the callee may store or return it), a ret (the caller receives it; the algorithm treats it as capture unless the client excludes returns), a ptrtoint (the address becomes an integer), or another non-listed instruction. Loads and stores to the address, and comparisons, produce no pointer value from it. The worklist explores exactly the uses of derived values (GEP, cast, phi, select results are pushed) and returns true at every one of those instructions. So a false answer means no such first moment exists — a contradiction.

The use limit \(U\) keeps the walk cheap; exceeding it returns true (captured), which is the safe direction. What breaks it: inline assembly or code that recovers an address from integers (a ptrtoint in another function of a pointer it received) — LLVM treats ptrtoint as capture precisely so that later inttoptr cannot recreate an uncaptured address.

GlobalsAA

Theorem 19.2.13 (GlobalsAA is sound)

For every call \(c\) of a function \(f\) with known \(\mathit{FI}(f)\) and every non-address-taken global \(g\), the accesses to \(g\) during \(c\) are within \(\mathit{FI}(f)(g)\).

Proof

By induction on the bottom-up order of SCCs. During a call of \(f \in S\), an access to \(g\) is a load or store that names \(g\) (Definition 19.2.8: no pointer to \(g\) exists), executed either in a function of \(S\) — recorded in \(\mathit{FI}\) by the body scan, which unions over all of \(S\) because functions in one SCC may call each other any number of times — or in a callee outside \(S\), whose summary is final by the invariant and was unioned in. Indirect calls and calls to declarations that may call back into the module could reach any function, so they make the SCC unknown; declarations that are both nocallback and nosync cannot execute module code and cannot name an internal global, so they add nothing. Hence the union is an upper bound.

5. Complexity

Technique Time per query / per run Space Variables
BasicAA \(O(D \cdot g)\) per query, \(D \le 512\) recursive levels, each decomposing GEP chains of length \(g \le 10\) (Lesson 19.1 §5); cached per AAQueryInfo \(O(\text{queries})\) cache \(g\) GEP depth, \(D\) recursion depth
Capture tracking \(O(\min(u, U))\) per pointer \(O(u)\) \(u\) uses of the pointer and derived values, \(U = 100\) (capture-tracking-max-uses-to-explore)
GlobalsAA \(O(I + C)\) once per module (one scan of every instruction, one pass over the call graph); \(O(1)\) per query \(O(\lvert F \rvert \cdot \lvert G \rvert)\) summaries \(I\) instructions, \(C\) call edges, \(F\) functions, \(G\) non-address-taken globals

Justification. BasicAA's phi recursion can branch: a pair of phis with \(k\) operands each leads to \(k^2\) sub-queries; the cache (each (pair, size) answered once per query) and the depth cap bound the total. Pathological family: a chain of \(n\) phis, each merging two GEPs of the previous one, doubles the number of paths per level; without the cache a query costs \(\Theta(2^n)\), with it \(O(n^2)\) distinct pairs. Capture tracking touches each use at most once (the seen set). GlobalsAA's body scan is linear, and each call edge merges summaries once per SCC. In practice BasicAA is the cheapest member of the chain: the aa-eval run in the first box answers 21 queries on a 10-line function essentially instantly.

6. Variants and refinements

BasicAA

  • Modular and range reasoning on variable indices. BasicAA also proves a[2*i] and a[2*i+1] disjoint (a GCD argument on the scales) and uses known bits and constant ranges of the index values; trade-off: more ValueTracking queries per alias query.
  • Cross-iteration awareness. A query can be marked "may be cross-iteration" (the MayBeCrossIteration flag used by LICM and the vectorizer), which disables Must answers for values that differ between iterations; trade-off: correctness for loop transforms at the cost of fewer Must answers.
  • Separate-storage assumptions. llvm.assume with a separate_storage bundle lets front ends assert that two objects never overlap; trade-off: trusts the front end, like noalias.

Capture tracking

  • Captured-before, not captured-anywhere. PointerMayBeCapturedBefore and LLVM's EarliestEscapeAnalysis ask whether the capture can happen before a given instruction (using dominance), so a local that escapes only at the end of a function is still private before that; trade-off: a dominator-tree query per use.
  • Capture components. LLVM 21+ distinguishes capturing only the address (for comparisons) from capturing the provenance (the right to access), captures(address) vs captures(provenance); trade-off: finer answers, more attribute states to infer and check.

GlobalsAA

  • Indirect globals. GlobalsAA also tracks globals that hold the only pointer to a heap allocation (AllocsForIndirectGlobals), so loads through them are known not to alias other memory; trade-off: another pattern to maintain.
  • Whole-program reachability. With LTO the module is the whole program, and more globals become internal; trade-off: needs LTO (Ch 20).

7. In real compilers

BasicAA

LLVM and GCC

LLVM llvm/lib/Analysis/BasicAliasAnalysis.cpp — BasicAAResult::aliasCheck (objects, identified objects, escape sources, object sizes), BasicAAResult::aliasGEP with DecomposeGEPExpression, aliasPHI, aliasSelect [LLVM-BasicAA] (LLVM 23.1.2). GCC gcc/tree-ssa-alias.cc — decl_refs_may_alias_p (two declarations), indirect_refs_may_alias_p and aliasing_component_refs_p (access paths and offsets) [GCC-TreeAlias] (GCC 14.2).

BasicAA on a kernel with arrays, struct fields, a local and a global

Reproduce (clang 23.1.2, opt 23.1.2; Linux x86-64 (the answers are target independent)):

cat > kern.c <<'C'
struct pt { int x, y; };
int g;
void kern(int *a, struct pt *s, int i) {
  int local[4];
  a[i] = 1;
  a[i + 1] = 2;
  s->x = 3;
  s->y = 4;
  local[i] = 5;
  g = local[0] + *(char *)&s->y;
}
C
clang-23 -O1 -fno-discard-value-names -S -emit-llvm kern.c -o kern.ll
opt -aa-pipeline=basic-aa -passes=aa-eval -print-all-alias-modref-info -disable-output kern.ll 2>&1 \
  | grep -E 'Alias:'

Output (complete):

  NoAlias:  i32* %arrayidx, i32* %arrayidx2
  MayAlias: i32* %arrayidx, i32* %s
  MayAlias: i32* %arrayidx2, i32* %s
  MayAlias: i32* %arrayidx, i32* %y
  MayAlias: i32* %arrayidx2, i32* %y
  NoAlias:  i32* %s, i32* %y
  NoAlias:  i32* %arrayidx, i32* %arrayidx4
  NoAlias:  i32* %arrayidx2, i32* %arrayidx4
  NoAlias:  i32* %arrayidx4, i32* %s
  NoAlias:  i32* %arrayidx4, i32* %y
  NoAlias:  i32* %arrayidx, i32* %local
  NoAlias:  i32* %arrayidx2, i32* %local
  NoAlias:  i32* %local, i32* %s
  NoAlias:  i32* %local, i32* %y
  MayAlias: i32* %arrayidx4, i32* %local
  MayAlias: i32* %arrayidx, i32* @g
  MayAlias: i32* %arrayidx2, i32* @g
  MayAlias: i32* %s, i32* @g
  NoAlias:  i32* %y, i32* @g
  NoAlias:  i32* %arrayidx4, i32* @g
  NoAlias:  i32* %local, i32* @g

What to notice: the 13 NoAlias and 8 MayAlias answers of the §3 table: a[i] vs a[i+1] and s->x vs s->y by constant offsets (Lemma 19.2.10), everything involving local by "argument vs function-local object", local[i] vs local MayAlias because i is unknown, and s->y vs @g NoAlias by the object-size rule.

Find where LLVM does it. In BasicAliasAnalysis.cpp, find the check in aliasCheck that returns NoAlias when "the size of one access is larger than the entire object on the other side". Which helper function implements it? (Quiz llvm-where-object-size.)

Capture tracking

LLVM

llvm/lib/Analysis/CaptureTracking.cpp — PointerMayBeCaptured (Algorithm 19.2.7 with the 100-use cap), PointerMayBeCapturedBefore, DetermineUseCaptureKind (the per-use case analysis) [LLVM-CaptureTracking]; BasicAA's EarliestEscapeAnalysis caches the earliest capture per object. Go uses the same idea at a larger scale: escape analysis decides heap vs stack (Lesson 19.9).

A private local and a leaked local around two opaque calls

Reproduce (clang 23.1.2, opt 23.1.2; Linux x86-64):

cat > cap.c <<'C'
void opaque(void);
void keep(int *);
int f(void) {
  int private_ = 1, leaked = 2;
  keep(&leaked);          /* leaked escapes: keep() may store &leaked somewhere */
  opaque();               /* ...so opaque() may read or write it */
  return private_ + leaked;
}
C
clang-23 -O1 -Xclang -disable-llvm-optzns -fno-discard-value-names -S -emit-llvm cap.c -o cap.ll
opt -aa-pipeline=basic-aa -passes=aa-eval -print-all-alias-modref-info -disable-output cap.ll 2>&1 \
  | grep -E 'ModRef.*Ptr: .*(private_|leaked).*call void @(opaque|keep)'
echo "== after -O1 (the load of private_ is gone, the load of leaked stays):"
clang-23 -O1 -fno-discard-value-names -S -emit-llvm cap.c -o - | sed -n '/^define/,/^}/p'

Output (complete):

  NoModRef:  Ptr: i32* %private_    <->  call void @keep(ptr noundef %leaked)
  Both ModRef:  Ptr: i32* %leaked   <->  call void @keep(ptr noundef %leaked)
  NoModRef:  Ptr: i32* %private_    <->  call void @opaque()
  Both ModRef:  Ptr: i32* %leaked   <->  call void @opaque()
== after -O1 (the load of private_ is gone, the load of leaked stays):
define dso_local range(i32 -2147483647, -2147483648) i32 @f() local_unnamed_addr #0 {
entry:
  %leaked = alloca i32, align 4
  call void @llvm.lifetime.start.p0(ptr nonnull %leaked) #3
  store i32 2, ptr %leaked, align 4, !tbaa !9
  call void @keep(ptr noundef nonnull %leaked) #3
  call void @opaque() #3
  %0 = load i32, ptr %leaked, align 4, !tbaa !9
  %add = add nsw i32 %0, 1
  call void @llvm.lifetime.end.p0(ptr nonnull %leaked) #3
  ret i32 %add
}

What to notice: both calls are NoModRef for %private_ and ModRef for %leaked; after -O1 the reload of private_ is gone (its value 1 is folded into add ... 1) while leaked is reloaded after opaque() — capture decides which loads survive a call.

GlobalsAA

LLVM

llvm/lib/Analysis/GlobalsModRef.cpp — GlobalsAAResult::AnalyzeGlobals (Definition 19.2.8), AnalyzeCallGraph (Algorithm 19.2.9, including the nosync/nocallback test for declarations), GlobalsAAResult::getModRefInfo (the query) [LLVM-GlobalsAA]. It runs once per module in the -O2 pipeline and is queried through the AA chain. GCC's IPA reference analysis (ipa-reference.cc) computes the same per-function read/write sets of static globals.

GlobalsAA proves that a call does not touch a static global

Reproduce (clang 23.1.2, opt 23.1.2; Linux x86-64):

cat > gl.c <<'C'
static int counter;                              /* internal, address never taken */
int shared;
__attribute__((noinline)) void set_shared(int x) { shared = x; }
__attribute__((noinline)) static void bump(void) { counter++; }
void log_it(int);                                /* external: might call back into f */
int f(int x) {
  counter = x;
  set_shared(x);
  bump();
  log_it(x);
  return counter;
}
C
clang-23 -O1 -Xclang -disable-llvm-optzns -fno-discard-value-names -S -emit-llvm gl.c -o gl.ll
for aa in basic-aa 'globals-aa,basic-aa'; do
  echo "== -aa-pipeline=$aa"
  opt -aa-pipeline="$aa" -passes='require<globals-aa>,function(aa-eval)' -print-all-alias-modref-info \
      -disable-output gl.ll 2>&1 | grep -E 'Ptr: i32\* @counter.*call void @(set|bump|log)'
done

Output (complete):

== -aa-pipeline=basic-aa
  Both ModRef:  Ptr: i32* @counter  <->  call void @set_shared(i32 noundef %1)
  Both ModRef:  Ptr: i32* @counter  <->  call void @bump()
  Both ModRef:  Ptr: i32* @counter  <->  call void @log_it(i32 noundef %2)
== -aa-pipeline=globals-aa,basic-aa
  NoModRef:  Ptr: i32* @counter <->  call void @set_shared(i32 noundef %1)
  Both ModRef:  Ptr: i32* @counter  <->  call void @bump()
  Both ModRef:  Ptr: i32* @counter  <->  call void @log_it(i32 noundef %2)

What to notice: with BasicAA alone every call is ModRef for @counter; adding GlobalsAA makes set_shared NoModRef (its summary does not mention counter), while bump stays ModRef (it writes it) and log_it stays ModRef (an external function may call back into f) — the §3 table.

8. Comparison

Technique Power / precision Speed (asymptotic · practical) Output / error quality Implementation effort Typical use
BasicAA Local facts only: distinct allocations, offsets, sizes, phi/select; nothing about what arguments or loaded pointers point to \(O(D \cdot g)\) per query, cached · the cheapest AA Four answers with offsets (PartialAlias) Medium (many rules, many corner cases) First member of every LLVM AA pipeline
Capture tracking Decides "private local" exactly for the use patterns it knows; conservative on any other use \(O(\min(u, 100))\) per pointer yes/no (plus capture components) Low–medium BasicAA escape sources, DSE at function exit, call mod/ref, captures(none) inference
GlobalsAA Mod/ref of calls for internal non-address-taken globals; gives up on indirect calls and callbacks \(O(I + C)\) once per module per-function mod/ref summaries Medium (call graph, SCC order) LLVM -O2 module pass; GCC ipa-reference

Choose BasicAA always: it is the baseline every other analysis refines. Choose capture tracking whenever a question involves a local and a call or a function exit. Choose GlobalsAA for programs with file-static state (C libraries, interpreters): it is cheap and the only AA that can clear a call for a global.

9. Assessment

  • Quiz: basicaa-kernel-answers, llvm-where-object-size (tag basicaa); capture-uses, capture-private-load (tag capture); globalsaa-summary, globalsaa-callback (tag globalsaa).
  • Drill: ./course drill gep-offset (Ch 9) for the offset arithmetic of AliasGEP. The rules themselves are small and are practised through the quiz on concrete IR; capture tracking reappears in exercise E1 (non-escaping locals).
  • Flashcards: tags basicaa, capture, globalsaa.
  • Exercises: E1 (pebble-dse) uses PointerMayBeCaptured for the "dead at function exit" rule.

References

See the chapter references.