Lesson 19.3 — Language rules as alias facts: type-based alias analysis and scoped noalias

Techniques: type-based alias analysis (C/C++ strict aliasing, the character-type exemption, LLVM's struct-path TBAA metadata, Diwan–McKinley–Moss); scoped noalias (C restrict, LLVM noalias parameters, alias.scope/noalias metadata created by the inliner) · Pebble implements: nothing; Pebble has no unions or casts between pointer types, so a Pebble front end could emit TBAA tags safely (a ★ idea in the exercises) · Prerequisites: Lesson 19.1; Ch 9 (metadata, the noalias attribute) · Time: 4 hours

1. Problem and motivation

BasicAA (Lesson 19.2) cannot separate two pointer arguments: void f(int *i, float *f) might be called with the same address twice. Yet in C this call would be undefined behavior if both pointers are used to access the same object, because the language forbids reading an int object through a float lvalue. Source languages carry promises of this kind, and the front end can pass them to the optimizer as metadata. Two families of promises matter.

Type-based alias analysis (TBAA)

C's effective-type rule [C11, §6.5 ¶6–7] says an object may be accessed only through an lvalue of its own type (up to qualifiers and signedness), of an aggregate or union type that contains it, or of a character type. C++ has the same rule with std::byte added [CPP-basiclval]. So an int store and a float load can never touch the same object in a conforming program. Diwan, McKinley and Moss turned such rules into an alias analysis for Modula-3 [DMM98]; LLVM's TBAA encodes the C/C++ rules as a type tree in metadata, with struct paths so that b->a.i and b->k are distinguished even though both are int [LLVM-TBAA, LLVM-LangRef]. Programs that break the rule (type punning through casts) are miscompiled, which is why -fno-strict-aliasing exists.

Scoped noalias and restrict

restrict on a pointer parameter promises that, during the function, any object the pointer accesses and that is modified is accessed only through that pointer [C11, §6.7.3.1]. Clang turns it into the noalias parameter attribute. Once the function is inlined, parameters disappear, so the inliner re-expresses the promise as scoped noalias metadata: every access derived from the restrict pointer gets !alias.scope of a new scope, every other access in the inlined body gets !noalias of it [LLVM-Inliner-noalias]. ScopedNoAliasAA answers queries from these tags [LLVM-ScopedNoAlias].

2. Definitions and algorithms

Type-based alias analysis (TBAA)

Definition 19.3.1 (TBAA type DAG)

A TBAA type DAG has a root \(\rho\) and nodes of two kinds. A scalar node \(t\) has a parent \(\mathrm{par}(t)\) (another scalar node or \(\rho\)). A struct node \(S\) has fields \(\langle (T_1, o_1), \dots, (T_k, o_k) \rangle\) with offsets \(o_1 < \dots < o_k\), each \(T_i\) a scalar or struct node. For the least-common-ancestor computation a struct's parent is its first field's type. Clang builds it with root Simple C/C++ TBAA, a child omnipotent char, and every other scalar type (int, short, float, any pointer, …) as a child of omnipotent char.

Definition 19.3.2 (Access tag)

An access tag is a triple \((B, A, o)\): the base type \(B\) (the outermost aggregate the access path starts from, or the scalar itself), the access type \(A\) (a scalar node: the type of the loaded or stored value) and the byte offset \(o\) of the access within \(B\). b->a.i with struct B { int k; struct A a; } and struct A { short s; int i; } has tag \((B, \mathit{int}, 8)\); *p for int *p has tag \((\mathit{int}, \mathit{int}, 0)\).

Definition 19.3.3 (Field walk)

\(\mathrm{field}(T, o)\) follows one edge of the DAG: for a scalar \(T\) it is \((\mathrm{par}(T), o)\); for a struct \(T\) it is \((T_j, o - o_j)\) where \((T_j, o_j)\) is the last field with \(o_j \le o\). The walk from \((T, o)\) is the sequence \((T, o), \mathrm{field}(T, o), \mathrm{field}(\mathrm{field}(T, o)), \dots\) until the root.

Algorithm 19.3.4 (Struct-path TBAA query, LLVM's matchAccessTags)

• Input: access tags \(a = (B_a, A_a, o_a)\) and \(b = (B_b, A_b, o_b)\) over one type DAG.
• Output: \(\mathsf{May}\) or \(\mathsf{No}\).
• Precondition: both accesses come from a program that obeys the effective-type rule, and the tags describe the lvalues the front end compiled.
• Postcondition: \(\mathsf{No}\) only if no conforming execution makes the accesses overlap (Theorem 19.3.7).
• Invariant: during a walk, the current node \(T\) and offset \(o\) describe a subobject of \(B\) at offset \(o_{\text{start}} - o\) that contains the accessed bytes.

function TBAA(a, b):
    if a = b: return May
    C ← LCA(A_a, A_b)                          # least common ancestor via par()
    if C does not exist: return May             # different roots: unrelated type systems
    for (x, y) in [(a, b), (b, a)]:
        decided, may ← Subobject(x, y, C)
        if decided: return (May if may else No)
    return No                                   # neither base type contains the other there

function Subobject(x = (B_x, A_x, o_x), y = (B_y, A_y, o_y), C):
    if A_x = B_x = C: return (true, true)        # x accesses a whole object of the common type
    (T, o) ← (B_x, o_x)
    while T is not the root:
        if T = B_y:                              # x's path passes through y's base type
            return (true, o = o_y or T = A_x or B_y = A_y)
        (T, o) ← field(T, o)
    return (false, false)

LCA compares the two chains of ancestors from the root down; char is an ancestor of every scalar, so a char access is never separated from anything: the character-type exemption of the language rule.

Scoped noalias and restrict

Definition 19.3.5 (Scopes, domains and scoped accesses)

A scope domain is a metadata node; a scope is a node belonging to exactly one domain. An access \(I\) may carry two lists of scopes: \(\mathrm{AS}(I)\) (!alias.scope) and \(\mathrm{NA}(I)\) (!noalias). For a domain \(D\) write \(\mathrm{AS}_D(I)\) and \(\mathrm{NA}_D(I)\) for the scopes of \(D\) in each list. The LangRef semantics [LLVM-LangRef]: if every scope in \(\mathrm{AS}_D(I)\) is in \(\mathrm{NA}_D(J)\) and \(\mathrm{AS}_D(I) \neq \emptyset\), then \(I\) and \(J\) do not access overlapping memory.

Algorithm 19.3.6 (ScopedNoAliasAA and the inliner's translation)

• Input: two accesses \(I, J\) with scope lists; or, for the translation, a call \(c\) being inlined whose callee has noalias parameters \(q_1, \dots, q_m\).
• Output: \(\mathsf{No}\)/\(\mathsf{May}\); or scope lists on every memory access of the inlined body.
• Precondition: the scope lists satisfy Definition 19.3.5's semantics (the front end or the inliner created them from restrict promises that hold).
• Postcondition: No only for accesses that the semantics say do not overlap (Theorem 19.3.8); after the translation, any two accesses whose pointers are based on different noalias parameters get tags that make ScopedNoAliasAA answer No.
• Invariant: each new scope belongs to a fresh domain created for this one inlined call, so tags from different call sites never interact.

function MayAliasInScopes(Scopes, NoAlias):          # true = may alias
    for each domain D mentioned in NoAlias:
        S ← Scopes restricted to D
        if S ≠ ∅ and S ⊆ (NoAlias restricted to D): return false
    return true

function ScopedAlias(I, J):
    if not MayAliasInScopes(AS(I), NA(J)): return No
    if not MayAliasInScopes(AS(J), NA(I)): return No
    return May

function AddAliasScopeMetadata(c, callee):           # the inliner, simplified
    D ← new domain named after the callee
    for each noalias parameter q_k: s_k ← new scope in D
    for each memory access I in the inlined body:
        B ← the parameters q_k that I's pointer may be based on (underlying objects)
        if B = {q_k} (based on exactly one noalias parameter): AS(I) ∪= {s_k}
        NA(I) ∪= { s_j : q_j ∉ B }                   # I is not based on these parameters

3. Worked example

Type-based alias analysis (TBAA)

Take struct A { short s; int i; } and struct B { int k; struct A a; } (offsets: B.k 0, B.a 4, A.s 0, A.i 4, so b->a.i is at 8), the types of the second TBAA box (§7). The DAG: char under the root; short, int under char; \(A = \langle(\mathit{short}, 0), (\mathit{int}, 4)\rangle\); \(B = \langle(\mathit{int}, 0), (A, 4)\rangle\). Algorithm 19.3.4 on seven accesses (the walks were produced by the course oracle, tools/course/lib/tbaa.py, which agrees with opt on 600 random pairs):

pair	LCA of access types	walk	answer
b->a.i \((B,\mathit{int},8)\) vs b->k \((B,\mathit{int},0)\)	int	from \((B, 8)\): \(T = B = B_y\) at once, offsets 8 vs 0, \(B \neq A_x\)	No
b->a.i vs b->a.s \((B,\mathit{short},4)\)	char	\(T = B\) at once, offsets 8 vs 4	No
b->a.i vs *p \((\mathit{int},\mathit{int},0)\)	int	\((B,8) \to (A,4) \to (\mathit{int},0)\): \(T = B_y\), offsets 0 = 0	May
b->a.i vs a->i \((A,\mathit{int},4)\)	int	\((B,8) \to (A,4)\): offsets 4 = 4	May
b->a.i vs *q \((\mathit{short},\mathit{short},0)\)	char	\((B,8) \to (A,4) \to (\mathit{int},0) \to (\mathit{char},0) \to\) root; back from \((\mathit{short},0)\): short, char, root	No
b->k vs a->i	int	\((B,0) \to (\mathit{int},0) \to\) char, root; \((A,4) \to (\mathit{int},0) \to\) char, root: neither meets the other base	No
any access vs *c \((\mathit{char},\mathit{char},0)\)	char	the walk reaches char	May

Two int accesses are separated when their struct paths differ (b->k vs a->i), and an int and a short are separated even inside the same struct; only char, the whole-object access *p and matching paths keep MayAlias.

Try it yourself: ./course drill tbaa-query --seed 5 --difficulty hard --solution.

Scoped noalias and restrict

axpy(float *restrict y, const float *restrict x, …) inlined into caller (third box): the inliner creates domain "axpy" and scopes \(s_y\) (!10, "axpy: %y") and \(s_x\) (!13). The load of x[i] is based on x only: \(\mathrm{AS} = \{s_x\}\), \(\mathrm{NA} = \{s_y\}\); the load and store of y[i]: \(\mathrm{AS} = \{s_y\}\), \(\mathrm{NA} = \{s_x\}\). Query load x[i] (\(I\)) vs store y[i] (\(J\)): MayAliasInScopes\((\{s_x\}, \{s_x\})\): domain axpy, \(\{s_x\} \subseteq \{s_x\}\) → false → No. BasicAA alone sees two GEPs from the caller's arguments %p, %q and must answer May.

4. Invariants and correctness

Type-based alias analysis (TBAA)

Theorem 19.3.7 (Scalar TBAA is sound for conforming programs)

Consider tags of the scalar form \((t, t, 0)\) in clang's tree (every scalar type a child of char, signed and unsigned variants mapped to one node). If Algorithm 19.3.4 answers No for two accesses of a program that obeys C's effective-type rule, the accesses never overlap.

Proof

Suppose two accesses with access types \(t_1 \neq t_2\) overlap on some byte of an object \(X\) in a conforming execution. Let \(E\) be the effective type of the scalar object containing that byte. By [C11, §6.5 ¶7] each access type is either (a signedness or qualifier variant of) \(E\), or a character type, or an aggregate containing \(E\) — for scalar tags the last case does not arise. Clang maps variants of \(E\) to \(E\)'s node. So each \(t_k \in \{E, \mathit{char}\}\), and since \(t_1 \neq t_2\), one of them is char. Char is the parent of \(E\), so \(\mathrm{LCA}(t_1, t_2) = \mathit{char}\) and the tag whose access type is char has \(A_x = B_x = \mathit{char} = C\): Subobject returns \((\mathsf{true}, \mathsf{true})\) and the answer is May, a contradiction. (Equal tags answer May at once.)

Proof sketch for struct paths (full semantics: [LLVM-LangRef, tbaa Metadata]; the rule itself: [C11, §6.5 ¶7])

With struct paths a tag \((B, A, o)\) additionally records that the access is to the subobject of type \(A\) at offset \(o\) of an object of type \(B\). Subobject(x, y, C) walks from \(x\)'s base down the fields at \(x\)'s offset; if it meets \(y\)'s base type \(B_y\), both accesses name subobjects of a \(B_y\) object and they can overlap only at equal offsets (unless one of them accesses the whole \(B_y\) or an ancestor of a field type, the other disjuncts). If neither walk meets the other base, no object can be viewed both as a \(B_x\) with a subobject at \(o_x\) and as a \(B_y\) with a subobject at \(o_y\) in a conforming program, because the effective-type rule allows access through an aggregate type only to objects that actually are (or contain) that aggregate. The first line (A_x = B_x = C) keeps accesses to a whole object of the common type conservative.

Type punning breaks TBAA, not the compiler

*(float *)&x = 0.0f on an int x accesses an int object through a float lvalue: undefined behavior. The first TBAA box shows the consequence: at -O2 clang returns the constant 1 for a value the punned store changed; with -fno-strict-aliasing it reloads and returns 0. Use memcpy, a character buffer, or (in C, where the standard allows it) a union to reinterpret bytes; GCC documents that it honours union punning when the union type is visible [GCC-StrictAliasing].

Scoped noalias and restrict

Theorem 19.3.8 (ScopedNoAliasAA is sound)

If the scope lists satisfy Definition 19.3.5's semantics, ScopedAlias answers No only for accesses that do not overlap.

Proof

ScopedAlias(I, J) returns No only if MayAliasInScopes(AS(I), NA(J)) or the symmetric call returned false, which happens exactly when some domain \(D\) has \(\emptyset \neq \mathrm{AS}_D(I) \subseteq \mathrm{NA}_D(J)\) (or with \(I\) and \(J\) swapped). That is the premise of Definition 19.3.5's semantics, whose conclusion is that \(I\) and \(J\) do not access overlapping memory. The early return for missing lists (if !Scopes or !NoAlias: may alias) only adds May answers.

Proof sketch that the inliner's translation preserves restrict (full argument: [C11, §6.7.3.1] and the LangRef's noalias parameter semantics [LLVM-LangRef])

A noalias parameter \(q_k\) guarantees that, during the call, memory accessed through pointers based on \(q_k\) is not accessed through pointers not based on \(q_k\) (when either access writes). After inlining, an access \(I\) tagged \(\mathrm{AS}(I) = \{s_k\}\) is based on \(q_k\) only, and an access \(J\) with \(s_k \in \mathrm{NA}(J)\) is not based on \(q_k\) — exactly the pair the guarantee covers. The fresh domain per inlined call confines the promise to that call's execution: accesses from another inlined copy carry scopes of another domain, and Definition 19.3.5 compares scopes of one domain at a time. In loops, the llvm.experimental.noalias.scope.decl intrinsic marks where a scope starts so that duplicating the body (unrolling) does not merge two executions' scopes.

5. Complexity

Technique	Time per query	Space	Variables
TBAA	\(O(h_A + h_B + w)\): two ancestor chains for the LCA, then two walks of at most \(w\) field steps plus the chain to the root	the metadata DAG: \(O(\sum_S k_S)\)	\(h\) height of the scalar tree (3 in clang's), \(w\) nesting depth of structs, \(k_S\) fields of struct \(S\)
Scoped noalias	\(O(\lvert \mathrm{AS} \rvert + \lvert \mathrm{NA} \rvert)\) with hashing per domain	one scope per noalias parameter per inlined call	list sizes
Inliner translation	\(O(a \cdot m)\) per inlined call: underlying objects of each of \(a\) accesses against \(m\) parameters	\(O(a \cdot m)\) metadata	\(a\) accesses, \(m\) noalias parameters

Justification. Subobject advances one DAG edge per iteration and stops at the root, so each walk is bounded by struct nesting plus the scalar chain; clang's scalar tree has height 3 (root, char, type). Pathological family: deep inlining of functions with many restrict parameters: \(n\) nested inlined calls with \(m\) parameters each give accesses with \(\Theta(n \cdot m)\) scopes in their lists, and every query intersects lists of that size; LLVM caps the cost by creating scopes only for noalias arguments and by merging metadata conservatively when instructions are combined (AAMDNodes::merge, [LLVM-TBAA]).

6. Variants and refinements

Type-based alias analysis (TBAA)

• New-format (size-aware) TBAA. Type nodes that record sizes and access tags with sizes allow aggregate access types and precise overlap checks; trade-off: bigger metadata, and front ends must produce it (clang still emits the old format by default).
• !tbaa.struct. Describes the fields a memcpy copies, so SROA can give each split field a precise tag; trade-off: one more metadata kind to keep consistent.
• Pointer-type distinction. Clang 23 distinguishes pointer types in TBAA (p1 int, p1 _ZTS1B under any pointer, visible in the second box), so an int ** access does not alias a float ** access; trade-off: code that stores pointers of one type through another pointer type now needs -fno-pointer-tbaa or -fno-strict-aliasing.
• GCC alias sets. GCC assigns each type an alias set and records subset relations (get_alias_set, record_component_aliases in gcc/alias.cc); trade-off: no offsets, but also used for RTL-level disambiguation.
• Language-specific trees. Swift and Rust do not use C's rule but can encode their own guarantees; the LangRef lets any front end emit an unrelated type tree (different roots are never disambiguated).

Scoped noalias and restrict

• noalias on return values and arguments without inlining. noalias returns (from malloc-like functions) and parameters are used directly by BasicAA (Definition 19.2.2); scopes are only needed once the function boundary disappears.
• Rust references. rustc marks &mut T (and &T without interior mutability) arguments noalias, giving LLVM restrict-level facts for safe code; trade-off: a miscompile appears if unsafe code breaks the aliasing model.
• Explicit scope declarations. llvm.experimental.noalias.scope.decl (LLVM 13+) keeps scopes correct under loop unrolling and code duplication; trade-off: an intrinsic in the IR that passes must preserve or drop consistently.

7. In real compilers

Type-based alias analysis (TBAA)

LLVM, Clang and GCC

LLVM llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp — matchAccessTags, mayBeAccessToSubobjectOf, getLeastCommonType, TBAAStructTypeNode::getField [LLVM-TBAA] (LLVM 23.1.2); the file's header comment draws the DAG of Definition 19.3.1. Clang clang/lib/CodeGen/CodeGenTBAA.cpp — CodeGenTBAA::getRoot ("Simple C/C++ TBAA"), getChar ("omnipotent char"), getTypeInfo (which maps may_alias types to char). GCC gcc/alias.cc — get_alias_set, alias_sets_conflict_p; tree-ssa-alias.cc's same_type_for_tbaa [GCC-TreeAlias].

Strict aliasing changes the code, and type punning changes the result

Reproduce (clang 23.1.2; Linux x86-64):

cat > pun.c <<'C'
#include <stdio.h>
__attribute__((noinline)) int pun(int *i, float *f) {
  *i = 1;
  *f = 0.0f;
  return *i;          /* strict aliasing: an int and a float object cannot overlap */
}
int main(void) {
  int x;
  printf("%d\n", pun(&x, (float *)&x));   /* type punning: undefined behavior */
  return 0;
}
C
for flags in "-O2" "-O2 -fno-strict-aliasing"; do
  echo "== clang-23 $flags"
  clang-23 $flags -fno-discard-value-names -S -emit-llvm pun.c -o - | sed -n '/^define.*@pun/,/^}/p'
  clang-23 $flags pun.c -o pun && ./pun
done

Output (complete):

== clang-23 -O2
define dso_local noundef i32 @pun(ptr nofree noundef writeonly captures(none) initializes((0, 4)) %i, ptr nofree noundef writeonly captures(none) initializes((0, 4)) %f) local_unnamed_addr #0 {
entry:
  store i32 1, ptr %i, align 4, !tbaa !9
  store float 0.000000e+00, ptr %f, align 4, !tbaa !10
  ret i32 1
}
1
== clang-23 -O2 -fno-strict-aliasing
define dso_local i32 @pun(ptr nofree noundef captures(none) initializes((0, 4)) %i, ptr nofree noundef writeonly captures(none) initializes((0, 4)) %f) local_unnamed_addr #0 {
entry:
  store i32 1, ptr %i, align 4
  store float 0.000000e+00, ptr %f, align 4
  %0 = load i32, ptr %i, align 4
  ret i32 %0
}
0

What to notice: with TBAA the load after the float store is gone (ret i32 1, and the stores carry !tbaa tags); with -fno-strict-aliasing there are no tags and the load stays. The punning program prints 1 and 0: the optimized program is "wrong" only because it has undefined behavior (the pitfall in §4).

Struct-path tags and three TBAA queries

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

cat > s.c <<'C'
struct A { short s; int i; };
struct B { int k; struct A a; };
int get(struct B *b, int *p, short *q) {
  b->a.i = 1;          /* tag (B, int, 8)   */
  *q = 2;              /* tag (short, short, 0) */
  *p = 3;              /* tag (int, int, 0) */
  return b->a.i;
}
C
clang-23 -O1 -Xclang -disable-llvm-optzns -fno-discard-value-names -S -emit-llvm s.c -o - \
  | opt -passes=sroa -S -o s.ll
sed -n '/^define/,/^}/p' s.ll
grep -E '^!([6-9]|1[0-4]) = ' s.ll
opt -aa-pipeline=tbaa -passes=aa-eval -evaluate-aa-metadata -print-all-alias-modref-info -disable-output s.ll 2>&1 \
  | grep -E 'Alias:.*store.*<->.*store' | sed 's/, align [0-9]//g'

Output (complete):

define dso_local i32 @get(ptr noundef %b, ptr noundef %p, ptr noundef %q) #0 {
entry:
  %a = getelementptr inbounds nuw %struct.B, ptr %b, i32 0, i32 1
  %i = getelementptr inbounds nuw %struct.A, ptr %a, i32 0, i32 1
  store i32 1, ptr %i, align 4, !tbaa !9
  store i16 2, ptr %q, align 2, !tbaa !13
  store i32 3, ptr %p, align 4, !tbaa !14
  %a1 = getelementptr inbounds nuw %struct.B, ptr %b, i32 0, i32 1
  %i2 = getelementptr inbounds nuw %struct.A, ptr %a1, i32 0, i32 1
  %0 = load i32, ptr %i2, align 4, !tbaa !9
  ret i32 %0
}
!6 = !{!"int", !7, i64 0}
!7 = !{!"omnipotent char", !8, i64 0}
!8 = !{!"Simple C/C++ TBAA"}
!9 = !{!10, !6, i64 8}
!10 = !{!"B", !6, i64 0, !11, i64 4}
!11 = !{!"A", !12, i64 0, !6, i64 4}
!12 = !{!"short", !7, i64 0}
!13 = !{!12, !12, i64 0}
!14 = !{!6, !6, i64 0}
  NoAlias:   store i16 2, ptr %q, !tbaa !13 <->   store i32 1, ptr %i, !tbaa !9
  MayAlias:   store i32 3, ptr %p, !tbaa !14 <->   store i32 1, ptr %i, !tbaa !9
  NoAlias:   store i32 3, ptr %p, !tbaa !14 <->   store i16 2, ptr %q, !tbaa !13

What to notice: the tag !9 = !{!10, !6, i64 8} is \((B, \mathit{int}, 8)\) for b->a.i; !10 and !11 are the struct nodes of Definition 19.3.1 with their field offsets. TBAA separates the short store from both int stores but keeps *p (whole int) MayAlias with b->a.i — rows 3 and 5 of the §3 table.

Find where LLVM does it. In TypeBasedAliasAnalysis.cpp, which function returns the node found by comparing the two ancestor paths from the root, and what does matchAccessTags return when it is null? (Quiz llvm-where-tbaa-lca.)

Scoped noalias and restrict

LLVM

llvm/lib/Analysis/ScopedNoAliasAA.cpp — ScopedNoAliasAAResult::alias and mayAliasInScopes (the domain-by-domain subset test of Algorithm 19.3.6) [LLVM-ScopedNoAlias]; llvm/lib/Transforms/Utils/InlineFunction.cpp — AddAliasScopeMetadata (the translation) [LLVM-Inliner-noalias] (LLVM 23.1.2). GCC keeps restrict information as "restrict tags" in its points-to solution (tree-ssa-structalias.cc) rather than as metadata.

restrict becomes noalias, then scoped metadata after inlining

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

cat > r.c <<'C'
static void axpy(float *restrict y, const float *restrict x, float a, int n) {
  for (int i = 0; i < n; i++)
    y[i] += a * x[i];
}
void caller(float *p, float *q, int n) { axpy(p, q, 2.0f, n); }
C
echo "== the restrict parameters become noalias:"
clang-23 -O1 -Xclang -disable-llvm-optzns -S -emit-llvm r.c -o - | grep -E '^define.*@axpy'
echo "== after inlining into caller, the promise survives as scoped metadata:"
clang-23 -O2 -fno-vectorize -fno-unroll-loops -fno-discard-value-names -S -emit-llvm r.c -o r.ll
grep -E '(load|store) float' r.ll | sed 's/, align 4, !tbaa !14//'
grep -E '^!(9|1[0-3]) = ' r.ll
echo "== the query load x[i] <-> store y[i]:"
for aa in basic-aa scoped-noalias-aa; do
  printf '%-18s ' "$aa"
  opt -aa-pipeline=$aa -passes=aa-eval -evaluate-aa-metadata -print-all-alias-modref-info -disable-output r.ll 2>&1 \
    | grep -E 'Alias:.*%0 = load float.*<->.*store float' | awk '{print $1}'
done

Output (complete):

== the restrict parameters become noalias:
define internal void @axpy(ptr noalias noundef %0, ptr noalias noundef %1, float noundef %2, i32 noundef %3) #0 {
== after inlining into caller, the promise survives as scoped metadata:
  %0 = load float, ptr %arrayidx.i, !alias.scope !12, !noalias !9
  %1 = load float, ptr %arrayidx2.i, !alias.scope !9, !noalias !12
  store float %2, ptr %arrayidx2.i, !alias.scope !9, !noalias !12
!9 = !{!10}
!10 = distinct !{!10, !11, !"axpy: %y"}
!11 = distinct !{!11, !"axpy"}
!12 = !{!13}
!13 = distinct !{!13, !11, !"axpy: %x"}
== the query load x[i] <-> store y[i]:
basic-aa           MayAlias:
scoped-noalias-aa  NoAlias:

What to notice: @axpy's parameters are noalias; after inlining the load of x[i] has !alias.scope !12 !noalias !9 and the store to y[i] the reverse, with scopes !10 ("axpy: %y") and !13 ("axpy: %x") in domain !11 ("axpy"). BasicAA alone answers MayAlias for the two caller pointers; scoped-noalias-aa answers NoAlias — the §3 computation.

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
TBAA	Separates accesses of unrelated types and different struct paths; nothing for same-type accesses through different pointers; unsound for programs that type-pun	\(O(h + w)\) per query · very cheap	May/No per pair of tags; tags are readable in the IR	Front end: map the language's types to a DAG; back end: ~700 lines	C/C++ at -O1+; disabled by -fno-strict-aliasing (Linux kernel, many embedded code bases)
Scoped noalias	Separates accesses based on different restrict/noalias pointers, also after inlining; exactly as good as the programmer's promises	\(O(\lvert \mathrm{AS} \rvert + \lvert \mathrm{NA} \rvert)\) per query	No/May; scopes are named after the parameter	Inliner translation plus a ~200-line AA	Numerical kernels (restrict), Rust &mut, Fortran dummy arguments

Choose TBAA for languages whose type rules forbid cross-type access and whose code bases respect them; keep -fno-strict-aliasing for code that does not. Choose scoped noalias to carry per-pointer promises (restrict, Rust references, Fortran arguments) through inlining; it complements TBAA because it separates two pointers of the same type.

9. Assessment

• Quiz: tbaa-pairs, tbaa-char-exemption, llvm-where-tbaa-lca (tag tbaa); scoped-noalias-query, restrict-semantics (tag scoped-noalias).
• Drill: ./course drill tbaa-query (all difficulties; hard also asks for the tags). Scoped noalias has no drill: its rule is one subset test per domain, practised in the quiz on the axpy tags.
• Flashcards: tags tbaa, scoped-noalias.
• Exercises: tests/ch19/lit/loadfwd.ll's @tbaa function checks that your pebble-loadfwd benefits from TBAA through AAResults (E2).

References

See the chapter references.