Lesson 19.1 — Memory and alias queries: may, must, partial and no alias; mod/ref; AA pipelines¶

Techniques: alias queries over memory locations (NoAlias / MayAlias / PartialAlias / MustAlias); mod/ref queries between instructions and locations; chaining alias analyses into one pipeline (LLVM AAResults, GCC's alias oracle) · Pebble implements: nothing new in this lesson; exercises E1–E2 call AAResults through MemorySSA, and the lab's alias() answers queries from points-to sets · Prerequisites: Ch 9 (the memory model, load/store/getelementptr, noalias, TBAA metadata), Lesson 16.8 (Memory SSA) · Time: 3–4 hours

1. Problem and motivation¶

After mem2reg (Ch 16) the scalars a program keeps in registers are in SSA form, and every scalar optimization of Ch 17 can follow def-use chains. What is left in memory is everything whose address is taken: arrays, structs, heap objects, globals, locals passed by pointer. For those, a pass that wants to move, delete or reuse a memory access must first answer one question:

void f(int *a, int *b) {
  *a = 1;
  *b = 2;
  use(*a);     /* is this 1?  only if a and b never point to the same int */
}

Forwarding 1 to the load is legal exactly when the store through b cannot write the bytes the load reads. That is an alias query. Two related questions follow: whether an instruction (a call, above all) may read or write a location — a mod/ref query — and how several analyses of different strength combine into one answer — an alias-analysis pipeline. This lesson makes the three precise. Lessons 19.2–19.9 are about the analyses that answer them; Lessons 19.10–19.11 about the optimizations that ask them.

The difficulty is fundamental. Theorem 19.1.8 shows that exact aliasing is undecidable, so every analysis approximates, and the only acceptable direction of error is towards "may alias". The shape of the answers comes from LLVM's interface [LLVM-AADoc, LLVM-AA], which follows the vocabulary of the pointer-analysis literature [Hin01].

Alias queries¶

An alias query takes two memory locations — a pointer and a size — and returns one of four answers: the accesses never overlap (NoAlias), they overlap exactly (MustAlias), they overlap partly at a known offset (PartialAlias), or the analysis cannot tell (MayAlias). pebblec never asks directly; its passes ask through MemorySSA and LLVM's AAResults.

Mod/ref queries¶

Many clients ask about an instruction rather than a pair of locations: can this call write *p? Can this store make a later load stale? The answer is an element of the four-point lattice NoModRef ⊑ Ref, Mod ⊑ ModRef. Calls are where most precision is lost: an opaque call may read and write all memory it can reach, which is why escape information (Lesson 19.2) and function summaries (Lesson 19.7) matter.

AA pipelines¶

No single analysis is best everywhere. BasicAA reasons locally about allocations and offsets, TBAA uses language types, scoped-noalias uses restrict promises, GlobalsAA uses whole-module facts about globals. A compiler runs them as a chain: each is asked in turn, and the first definite answer wins. The chain is the object that optimization passes see.

2. Definitions and algorithms¶

We use a small concrete semantics. A store \(\sigma\) maps byte addresses to byte values; each execution of an instruction happens at a program point with an environment that gives every SSA pointer value an address (a natural number) or poison.

Definition 19.1.1 (Memory location)

A memory location is a pair \(L = (p, s)\) of a pointer-typed value \(p\) and a size \(s \in \mathbb{N} \cup \{\top\}\) in bytes (\(\top\): unknown size, "anything reachable from \(p\) in either direction"). In an execution where \(p\) evaluates to the address \(a\), \(L\) denotes the byte interval \(\llbracket L \rrbracket = [a, a + s)\) (all bytes of the object if \(s = \top\)). LLVM's MemoryLocation is this pair plus metadata (TBAA and scope tags).

Definition 19.1.2 (Alias relation)

Let \(L_1 = (p_1, s_1)\) and \(L_2 = (p_2, s_2)\) be locations used at program points \(\ell_1, \ell_2\), and consider every execution and every pair of dynamic instances of \(\ell_1, \ell_2\) that the client relates (for example, the same iteration). Then

\(L_1, L_2\) must alias if in every such pair \(\llbracket L_1 \rrbracket\) and \(\llbracket L_2 \rrbracket\) start at the same address;
they partially alias at offset \(d \neq 0\) if in every such pair the intervals overlap and the start of \(L_2\) minus the start of \(L_1\) is \(d\);
they do not alias if in no such pair do the intervals intersect;
otherwise they may alias.

An alias analysis is a function \(\mathit{AA}(L_1, L_2) \in \{\mathsf{No}, \mathsf{May}, \mathsf{Partial}, \mathsf{Must}\}\). It is sound if it answers \(\mathsf{No}\) only for pairs that do not alias, and \(\mathsf{Must}\) or \(\mathsf{Partial}\) only for pairs that must or partially alias. \(\mathsf{May}\) is always sound.

The four answers on one base pointer

With %p4 = getelementptr i8, ptr %p, i64 4: \((p, 8)\) and \((p, 4)\) must alias (same start); \((p, 8)\) and \((p4, 4)\) partially alias at offset 4; \((p, 4)\) and \((p4, 4)\) do not alias; \((p, 8)\) and \((q, 4)\) for an unrelated argument %q may alias.

Definition 19.1.3 (Precision order)

Order the answers by information: \(\mathsf{May} \sqsubset \mathsf{No}\) and \(\mathsf{May} \sqsubset \mathsf{Partial} \sqsubset \mathsf{Must}\) (a MustAlias for equal sizes is a PartialAlias at offset 0 with more information). An analysis \(A\) is at least as precise as \(B\) if \(A(L_1, L_2) \sqsupseteq B(L_1, L_2)\) for every query. For points-to based analyses precision is also measured by the number of pairs answered MayAlias (Lesson 19.4 §8).

Definition 19.1.4 (Mod/ref information)

\(\mathit{MR} = \{\mathsf{NoModRef}, \mathsf{Ref}, \mathsf{Mod}, \mathsf{ModRef}\}\) is the powerset lattice of \(\{\mathsf{ref}, \mathsf{mod}\}\) ordered by \(\subseteq\), with \(\sqcap = \cap\) and \(\sqcup = \cup\). For an instruction \(I\) and a location \(L\), \(\mathit{MR}(I, L)\) contains \(\mathsf{ref}\) if some execution of \(I\) may read a byte of \(\llbracket L \rrbracket\) and \(\mathsf{mod}\) if it may write one. A mod/ref analysis is sound if its answer is a superset of that set.

Definition 19.1.5 (Memory effects of a function)

The memory effects of a function \(f\) map each kind of memory — its pointer arguments' targets (argmem), memory inaccessible to the module (inaccessiblemem), and all other memory — to an element of \(\mathit{MR}\). LLVM writes them as the attribute memory(...), for example memory(argmem: read); memory(none) is a pure function.

Algorithm 19.1.6 (An alias-analysis chain)

Input: alias analyses \(A_1, \dots, A_k\) (in pipeline order), locations \(L_1, L_2\); an instruction \(I\) and a location \(L\) for mod/ref.
Output: \(\mathit{alias}(L_1, L_2)\) and \(\mathit{modref}(I, L)\).
Precondition: every \(A_i\) is sound (Definitions 19.1.2 and 19.1.4).
Postcondition: both answers are sound and at least as precise as every single \(A_i\)'s answer (Proposition 19.1.9).
Invariant: after asking \(A_1, \dots, A_j\), the running mod/ref answer \(R_j = \bigcap_{i \le j} A_i(I, L)\) is sound.

function Alias(L1, L2):
    for i ← 1 to k:
        r ← A_i.alias(L1, L2)
        if r ≠ May: return r            # the first definite answer wins
    return May

function ModRef(I, L):
    R ← {ref, mod}
    for i ← 1 to k:
        R ← R ∩ A_i.modref(I, L)          # every analysis may only remove possibilities
        if R = ∅: return NoModRef
    return R

function CallModRef_i(call c of f, L):      # what one A_i does for a call
    E ← memory effects of f (Definition 19.1.5)
    R ← E(other) ∪ E(inaccessiblemem)       # memory not reached through arguments
    for each pointer argument a of c:
        if E(argmem) ≠ ∅ and A_i.alias((a, ⊤), L) ≠ No:
            R ← R ∪ E(argmem)
    if L's object is a local that has not escaped before c:   # Lesson 19.2
        R ← R ∩ (the argmem part only)
    return R

The chain asks the analyses in order: LLVM's default -O2 pipeline is BasicAA, then scoped-noalias, then TBAA (plus GlobalsAA when available). A definite answer ends the alias query, which is why cheap analyses go first. The mod/ref query intersects because different analyses exclude different possibilities.

MustAlias is not \"the same pointer\"

Two different SSA values can must-alias (%p and getelementptr i8, ptr %p, i64 0), and the same SSA value in a loop may denote a different address in every iteration: MustAlias is about the related dynamic instances of Definition 19.1.2. A transformation that moves an access across iterations (LICM, Lesson 19.11) must ask about the right instances.

3. Worked example¶

Alias queries¶

Take the IR of the first real-world box (§7): arguments %p, %q, a local %buf = alloca [16 x i8], and five accesses. The table computes each answer from Definition 19.1.2 (sizes from the access types; \(b\) is %buf's address).

query	intervals	reasoning	answer
`%p` (8) vs `%p0` (4)	\([p, p+8)\), \([p, p+4)\)	same start in every execution	MustAlias
`%p` (8) vs `%p4` (4)	\([p, p+8)\), \([p+4, p+8)\)	overlap, start difference 4	PartialAlias (off 4)
`%p0` (4) vs `%p4` (4)	\([p, p+4)\), \([p+4, p+8)\)	adjacent, never intersect	NoAlias
`%p` (8) vs `%q` (4)	unknown relation	two arguments may be equal	MayAlias
`%b8` (8) vs `%q` (4)	\([b+8, b+16)\), unknown	`%buf` is a fresh local; its address cannot be in `%q` (Lesson 19.2)	NoAlias

Mod/ref queries¶

In the second box, %p and %q are noalias arguments and the four calls have memory effects none, read, argmem: write and unknown. Algorithm 19.1.6's CallModRef:

call	effects \(E\)	query `%p`	query `%q`
`@pure(%x)`	none	NoModRef	NoModRef
`@reader(%q)`	read (all memory)	NoModRef: `%p` is `noalias` and not captured, so `@reader` cannot reach it	Ref
`@argwriter(%q)`	argmem: write	NoModRef: the only argument is `%q`, NoAlias with `%p`	Mod
`@unknown()`	read and write all	NoModRef: still not captured	ModRef: `%q` escaped into `@reader`/`@argwriter`, so `@unknown` may reach it

AA pipelines¶

The third box compiles f(int *restrict a, float *b, int *c) with stores *a = 1; *b = 2.0f; *c = 3. BasicAA knows a is noalias, so it answers NoAlias for (a, b) and (a, c) and MayAlias for (b, c); TBAA knows int and float accesses cannot overlap, so it answers NoAlias for (a, b) and (b, c) and MayAlias for (a, c). The chain basic-aa,tbaa asks BasicAA first and falls back to TBAA only on MayAlias:

pair	BasicAA	TBAA	chain
(a, b)	No	No	No (BasicAA)
(a, c)	No	May	No (BasicAA)
(b, c)	May	No	No (TBAA)

Try it yourself: ./course drill tbaa-query --seed 3 --solution runs the TBAA half of the chain on generated C accesses.

4. Invariants and correctness¶

Alias queries¶

Theorem 19.1.7 (Soundness of client transformations)

Let \(T\) be a transformation that swaps two adjacent memory accesses at \(\ell_1\) (location \(L_1\)) and \(\ell_2\) (location \(L_2\)), at least one of them a write, when \(\mathit{AA}(L_1, L_2) = \mathsf{No}\). If \(\mathit{AA}\) is sound, every execution of the transformed program produces the same store as the original at every point after \(\ell_2\).

Proof

Consider one execution and the dynamic instances of \(\ell_1, \ell_2\) that the swap reorders (they are related in the sense of Definition 19.1.2, because they are adjacent). By soundness, \(\llbracket L_1 \rrbracket \cap \llbracket L_2 \rrbracket = \emptyset\) in this execution. A write changes only the bytes of its interval, and a read depends only on the bytes of its interval. If both are writes, they change disjoint byte sets, and the final store is the same in either order. If one reads and one writes, the read sees the same bytes in either order, because the write does not touch them, and the write stores the same value in either order, because that value is an SSA operand computed before both accesses. Hence the store after \(\ell_2\) and every value read are equal in both orders; the rest of the execution starts from the same state and, by induction on the number of later steps, proceeds identically.

Theorem 19.1.8 (Exact alias analysis is undecidable)

There is no algorithm that, given a program in a language with pointers, loops and conditionals and two accesses in it, decides whether they may alias (Definition 19.1.2).

Proof

By reduction from the halting problem. Given a program \(M\) (with no pointer operations) and input \(w\), build int a, b; int *p = &a; run M on w; p = &b; *p = 1; return b; and ask whether the store *p = 1 may alias b. If \(M\) halts on \(w\), p = &b executes and the store writes b; if \(M\) does not halt, the store never executes and no pair of instances overlaps, so the accesses do not alias. A decider for aliasing would decide halting. (Stronger results — Landi 1992, Ramalingam 1994 — show undecidability in much more restricted settings; Hind's survey [Hin01] discusses what they mean for practical analyses.)

Mod/ref queries¶

Proposition 19.1.9 (The chain is sound and at least as precise as each member)

Let every \(A_i\) be sound. Then both answers of Algorithm 19.1.6 are sound, \(\mathit{ModRef}(I, L) \subseteq A_i(I, L)\) for every \(i\), and for every pair of locations with at least one related pair of dynamic instances, \(\mathit{Alias}(L_1, L_2) \sqsupseteq A_i(L_1, L_2)\) for every \(i\).

Proof

Alias. The chain returns \(\mathsf{May}\) (always sound) or the answer \(r\) of some sound \(A_j\), so it is sound. For precision, take a pair with at least one related instance pair. Members \(A_i\) with \(i < j\) answered \(\mathsf{May} \sqsubseteq r\). A member \(A_i\) with \(i > j\) answers either \(\mathsf{May} \sqsubseteq r\) or a definite answer; two different definite answers cannot both be sound here: \(\mathsf{No}\) says no instance pair overlaps while \(\mathsf{Must}\) and \(\mathsf{Partial}\) say every instance pair overlaps, and \(\mathsf{Must}\) (start difference 0) contradicts \(\mathsf{Partial}\) (difference \(d \neq 0\)); one witnessed instance pair suffices for each contradiction. So a later definite answer equals \(r\), and \(r \sqsupseteq A_i\) for all \(i\). (For accesses that never execute every answer is vacuously sound, and the chain keeps the first.)

Mod/ref. Loop invariant: \(R_j\) contains the true effect set \(S\) of Definition 19.1.4. Initially \(R_0 = \{\mathsf{ref}, \mathsf{mod}\} \supseteq S\). If \(R_{j-1} \supseteq S\) and, by soundness, \(A_j(I, L) \supseteq S\), then \(R_j = R_{j-1} \cap A_j(I, L) \supseteq S\). Returning early at \(\emptyset\) returns \(R_j\) itself. Finally \(R_k = \bigcap_i A_i(I, L) \subseteq A_i(I, L)\) for each \(i\).

Lemma 19.1.10 (Call mod/ref from memory effects)

CallModRef of Algorithm 19.1.6 is sound if the memory effects \(E\) of \(f\) are sound and the alias queries it makes are sound.

Proof

An access by the callee to a byte of \(\llbracket L \rrbracket\) goes through a pointer derived either from an argument (covered by \(E(\mathit{argmem})\), added only if some argument may alias \(L\) — if all arguments are NoAlias with \((\cdot, \top)\)-locations of \(L\), no argument-derived pointer reaches \(L\)'s bytes), or from somewhere else (covered by \(E(\mathit{other}) \cup E(\mathit{inaccessiblemem})\)). The last step removes the non-argument part for a local object that has not escaped: no pointer to it exists outside the caller's own SSA values and memory it has not published (Definition 19.2.6), so the callee can reach it only through its arguments. Each step keeps every effect that can happen.

AA pipelines¶

The chain's correctness is Proposition 19.1.9. What can break it is an unsound member: TBAA on a program that type-puns (Lesson 19.3 §4), or a noalias promise the source code does not keep. The chain does not detect such conflicts; the first member to answer decides.

5. Complexity¶

Technique	Cost of one query	Cost for a function	Variables
Alias query (one AA)	BasicAA: \(O(d \cdot g)\) with recursion depth \(d\) (underlying-object walks are capped at `MaxLookupSearchDepth` = 10 steps, recursive queries at depth 512) and GEP length \(g\); TBAA: \(O(h)\) for tag paths of height \(h\)	all pairs: \(O(a^2)\) queries	\(a\) accesses in a function
Mod/ref query	\(O(r \cdot q)\): \(r\) pointer arguments, each an alias query of cost \(q\)	\(O(a \cdot c)\) call/location pairs	\(c\) calls
Chain of \(k\) AAs	\(\le k\) member queries (early exit on a definite answer)	\(O(k a^2 q)\) worst case	\(k\) analyses

Justification. Each alias query of Algorithm 19.1.6 calls at most \(k\) members once each; each call-mod/ref loops over the call's arguments. A client that asks all pairs pays the quadratic factor, which is why MemorySSA (Lesson 19.10) exists: it asks only the pairs along def-use chains and caches them. Pathological input: a function with \(a\) stores to \(a\) distinct arguments; every pair is MayAlias for BasicAA, so every chain query walks all \(k\) members: \(k \cdot a(a-1)/2\) member queries. aa-eval on a real kernel shows the scale: the second box of Lesson 19.2 performs 21 alias queries and 16 mod/ref queries for a 10-line function. LLVM bounds the recursive BasicAA walk with AAQueryInfo's cache and depth counter, and batch clients use BatchAAResults to cache results for a whole pass [LLVM-AA].

Alias queries¶

Offset-carrying answers. LLVM's AliasResult stores the offset of a PartialAlias (23 bits) so clients like DSE can compute which bytes overlap; trade-off: a slightly larger result, used only by overwrite reasoning [LLVM-AA].
Alias sets. Instead of pairwise queries, partition all accesses of a loop into sets that may alias (AliasSetTracker, used by LICM's promotion, Lesson 19.11); trade-off: one pass over the loop instead of \(O(a^2)\) queries, but a set merges transitively ("a may alias b, b may alias c" puts a and c together) and loses pairwise precision.
Points-to based queries. Answer from points-to sets (Lessons 19.4–19.5, the lab's alias()): NoAlias iff the sets are disjoint; trade-off: whole-program cost once, then constant-time queries, but no offsets and no MustAlias.

Mod/ref queries¶

Location kinds in memory effects. LLVM's MemoryEffects distinguish argument memory, inaccessible memory, error-number memory and target-specific memory; trade-off: more attribute bits, much sharper answers for library calls (memory(argmem: read)).
Capture-aware call queries. callCapturesBefore asks whether the object escaped before the call, not anywhere in the function (Lesson 19.2); trade-off: a dominance-ordered walk of uses per query.

AA pipelines¶

Batching and caching. BatchAAResults caches every answer for the duration of one pass, assuming the IR does not change; trade-off: fast repeated queries, but the client must not mutate the IR it asked about.
External AAs. A plugin can add its own analysis to the chain (AAManager::registerFunctionAnalysis), for example a points-to based one (the lab's ★ extension); trade-off: every query pays for one more member, so it must be cheap or placed last.

7. In real compilers¶

Alias queries¶

LLVM

llvm/include/llvm/Analysis/AliasAnalysis.h — AliasResult (the four answers plus an offset), MemoryLocation (pointer, LocationSize, AAMDNodes); llvm/lib/Analysis/AliasAnalysis.cpp — AAResults::alias asks each AA and stops at the first answer that is not MayAlias [LLVM-AA] (LLVM 23.1.2). aa-eval (AliasAnalysisEvaluator.cpp) asks every pair in a function and prints the answers. GCC gcc/tree-ssa-alias.cc — refs_may_alias_p_1 is the reference-reference query and ptr_derefs_may_alias_p the pointer query over points-to sets [GCC-TreeAlias] (GCC 14.2).

aa-eval: the four alias answers on one base pointer

Reproduce (opt 23.1.2; any OS):

cat > kinds.ll <<'LL'
declare void @reads(ptr) memory(argmem: read)

define void @kinds(ptr %p, ptr %q) {
  %buf = alloca [16 x i8]
  %p0 = getelementptr i8, ptr %p, i64 0
  %p4 = getelementptr i8, ptr %p, i64 4
  %b8 = getelementptr i8, ptr %buf, i64 8
  store i64 0, ptr %p
  store i32 1, ptr %p0
  store i32 2, ptr %p4
  store i32 3, ptr %q
  store i64 4, ptr %b8
  call void @reads(ptr %buf)
  ret void
}
LL
opt -aa-pipeline=basic-aa -passes=aa-eval -print-all-alias-modref-info -disable-output kinds.ll

Output (complete):

Function: kinds: 5 pointers, 1 call sites
  MustAlias:    i64* %p, i32* %p0
  PartialAlias (off 4): i64* %p, i32* %p4
  NoAlias:  i32* %p0, i32* %p4
  MayAlias: i64* %p, i32* %q
  MayAlias: i32* %p0, i32* %q
  MayAlias: i32* %p4, i32* %q
  NoAlias:  i64* %b8, i64* %p
  NoAlias:  i64* %b8, i32* %p0
  NoAlias:  i64* %b8, i32* %p4
  NoAlias:  i64* %b8, i32* %q
  NoModRef:  Ptr: i64* %p   <->  call void @reads(ptr %buf)
  NoModRef:  Ptr: i32* %p0  <->  call void @reads(ptr %buf)
  NoModRef:  Ptr: i32* %p4  <->  call void @reads(ptr %buf)
  NoModRef:  Ptr: i32* %q   <->  call void @reads(ptr %buf)
  Just Ref:  Ptr: i64* %b8  <->  call void @reads(ptr %buf)
===== Alias Analysis Evaluator Report =====
  10 Total Alias Queries Performed
  5 no alias responses (50.0%)
  3 may alias responses (30.0%)
  1 partial alias responses (10.0%)
  1 must alias responses (10.0%)
  Alias Analysis Evaluator Pointer Alias Summary: 50%/30%/10%/10%
  5 Total ModRef Queries Performed
  4 no mod/ref responses (80.0%)
  0 mod responses (0.0%)
  1 ref responses (20.0%)
  0 mod & ref responses (0.0%)
  Alias Analysis Evaluator Mod/Ref Summary: 80%/0%/20%/0%

What to notice: MustAlias for the same start and PartialAlias (off 4) for an 8-byte access overlapping a 4-byte one at offset 4, exactly the §3 table; NoAlias between two adjacent 4-byte halves; MayAlias between two unrelated arguments; NoAlias between the local %buf and any argument. The last line of mod/ref output (Just Ref for %b8 and the memory(argmem: read) call) is the §2 lattice's Ref element.

Find where LLVM does it. Open llvm/lib/Analysis/AliasAnalysis.cpp at llvmorg-23.1.2 and find AAResults::alias(const MemoryLocation &LocA, ...). Which answer makes the loop over AAs stop? (Quiz llvm-where-aa-chain.)

Mod/ref queries¶

LLVM

AAResults::getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &) intersects the members' answers (Result &= AA->getModRefInfo(...)) and exits at NoModRef; BasicAA's version combines the callee's MemoryEffects with capture information (Lesson 19.2) [LLVM-AA, LLVM-BasicAA]. GCC's call_may_clobber_ref_p and ref_maybe_used_by_call_p answer the same questions from call-clobber sets [GCC-TreeAlias].

aa-eval: mod/ref of four calls with different memory effects

Reproduce (opt 23.1.2; any OS):

cat > mr.ll <<'LL'
declare i32 @pure(i32) memory(none)
declare i32 @reader(ptr) memory(read)
declare void @argwriter(ptr) memory(argmem: write)
declare void @unknown()

define void @f(ptr noalias %p, ptr noalias %q, i32 %x) {
  store i32 0, ptr %p
  store i32 0, ptr %q
  call i32 @pure(i32 %x)
  call i32 @reader(ptr %q)
  call void @argwriter(ptr %q)
  call void @unknown()
  ret void
}
LL
opt -aa-pipeline=basic-aa -passes=aa-eval -print-all-alias-modref-info -disable-output mr.ll 2>&1 \
  | grep -E 'Ptr: i32\* %[pq]' | sed 's/i32\* //'

Output (complete):

  NoModRef:  Ptr: %p    <->  %1 = call i32 @pure(i32 %x)
  NoModRef:  Ptr: %q    <->  %1 = call i32 @pure(i32 %x)
  NoModRef:  Ptr: %p    <->  %2 = call i32 @reader(ptr %q)
  Just Ref:  Ptr: %q    <->  %2 = call i32 @reader(ptr %q)
  NoModRef:  Ptr: %p    <->  call void @argwriter(ptr %q)
  Just Mod:  Ptr: %q    <->  call void @argwriter(ptr %q)
  NoModRef:  Ptr: %p    <->  call void @unknown()
  Both ModRef:  Ptr: %q <->  call void @unknown()

What to notice: the pure call is NoModRef for both locations; @reader(%q) is Just Ref for %q and NoModRef for the noalias, never-captured %p; @argwriter(%q) is Just Mod for %q; the unknown call is ModRef for %q (it escaped into the earlier calls) but still NoModRef for %p — Lemma 19.1.10's last step.

AA pipelines¶

LLVM

llvm/lib/Passes/PassBuilderPipelines.cpp builds the default AA pipeline (buildDefaultAAPipeline: BasicAA, scoped-noalias, TBAA, and GlobalsAA as a module-level result when available); opt's -aa-pipeline= replaces it. GCC does not chain separate analyses: refs_may_alias_p_1 calls points-to disambiguation, access-path rules and TBAA alias sets in one function [GCC-TreeAlias].

Three AA pipelines on one C function with restrict and two types

Reproduce (clang 23.1.2, opt 23.1.2; any OS):

cat > p.c <<'C'
int f(int *restrict a, float *b, int *c) {
  *a = 1;
  *b = 2.0f;
  *c = 3;
  return *a;
}
C
clang-23 -O1 -Xclang -disable-llvm-optzns -fno-discard-value-names -S -emit-llvm p.c -o p.ll
opt -passes='sroa' -S p.ll -o p1.ll
for aa in basic-aa tbaa 'basic-aa,tbaa'; do
  echo "== -aa-pipeline=$aa"
  opt -aa-pipeline="$aa" -passes=aa-eval -evaluate-aa-metadata -print-all-alias-modref-info \
      -disable-output p1.ll 2>&1 | grep -E '^  [A-Za-z]+Alias:.*store.*<->' | sed 's/, align 4//g'
done

Output (complete):

== -aa-pipeline=basic-aa
  NoAlias:   store float 2.000000e+00, ptr %b, !tbaa !10 <->   store i32 1, ptr %a, !tbaa !9
  NoAlias:   store i32 3, ptr %c, !tbaa !9 <->   store i32 1, ptr %a, !tbaa !9
  MayAlias:   store i32 3, ptr %c, !tbaa !9 <->   store float 2.000000e+00, ptr %b, !tbaa !10
== -aa-pipeline=tbaa
  NoAlias:   store float 2.000000e+00, ptr %b, !tbaa !10 <->   store i32 1, ptr %a, !tbaa !9
  MayAlias:   store i32 3, ptr %c, !tbaa !9 <->   store i32 1, ptr %a, !tbaa !9
  NoAlias:   store i32 3, ptr %c, !tbaa !9 <->   store float 2.000000e+00, ptr %b, !tbaa !10
== -aa-pipeline=basic-aa,tbaa
  NoAlias:   store float 2.000000e+00, ptr %b, !tbaa !10 <->   store i32 1, ptr %a, !tbaa !9
  NoAlias:   store i32 3, ptr %c, !tbaa !9 <->   store i32 1, ptr %a, !tbaa !9
  NoAlias:   store i32 3, ptr %c, !tbaa !9 <->   store float 2.000000e+00, ptr %b, !tbaa !10

What to notice: each member alone leaves one MayAlias, and a different one: BasicAA knows a is noalias (from restrict) but cannot separate b from c; TBAA separates float from int but not a from c. The chain basic-aa,tbaa answers NoAlias for all three pairs — the §3 table and Proposition 19.1.9.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Alias queries	Four answers; PartialAlias/MustAlias need offsets and sizes; soundness only in the "may" direction	per query \(O(d \cdot g)\) for local AAs · microseconds, cached per pass	`aa-eval` prints every pair; answers explain nothing about why	Low for the interface, high for good members	every memory transform (DSE, GVN, LICM, vectorizer)
Mod/ref queries	Four-point lattice per instruction; calls limited by memory effects and escape facts	\(O(r \cdot q)\) per call query	`aa-eval -print-all-alias-modref-info`	Medium (memory-effect attributes, capture tracking)	MemorySSA construction, DSE, LICM around calls
AA pipelines	At least as precise as each member (Proposition 19.1.9); inherits any member's unsoundness	\(\le k\) member queries, early exit	the answer, not the member that gave it	Low (a list); ordering matters for speed	LLVM `AAManager`, `-aa-pipeline`; GCC's single oracle

Choose alias queries as the interface between analyses and transformations: they are small, cacheable, and let analyses of very different kinds cooperate. Choose mod/ref queries whenever the question is about an instruction, above all a call, rather than two addresses. Choose a pipeline of cheap local analyses first and expensive or specialised ones later; put an analysis whose soundness depends on source-language rules (TBAA) where the front end guarantees those rules hold.

9. Assessment¶

Quiz: alias-answers-table, alias-partial-offset (tag alias-queries); modref-calls, modref-lattice-meet (tag modref); aa-chain-answers, llvm-where-aa-chain (tag aa-pipeline).
Drill: ./course drill tbaa-query exercises one member of the chain end to end; the alias and mod/ref answers themselves are small enough that the quiz asks for them on concrete IR, and the lab's alias() is a points-to-based member (labs/ch19-points-to/SPEC.md).
Flashcards: tags alias-queries, modref, aa-pipeline.
Exercises: E1 and E2 (exercises) consume AAResults; no exercise implements this lesson's interface itself.

References¶

See the chapter references.

Lesson 19.1 — Memory and alias queries: may, must, partial and no alias; mod/ref; AA pipelines¶

1. Problem and motivation¶

Alias queries¶

Mod/ref queries¶

AA pipelines¶

2. Definitions and algorithms¶

3. Worked example¶

Alias queries¶

Mod/ref queries¶

AA pipelines¶

4. Invariants and correctness¶

Alias queries¶

Mod/ref queries¶

AA pipelines¶

5. Complexity¶

6. Variants and refinements¶

Alias queries¶

Mod/ref queries¶

AA pipelines¶

7. In real compilers¶

Alias queries¶

Mod/ref queries¶

AA pipelines¶

8. Comparison¶

9. Assessment¶

References¶