Alias and Pointer Analysis

Two names alias when they can refer to the same memory location. The instant a language admits pointers, references, or arrays, aliasing appears — and with it, the single greatest obstacle to optimisation. Consider this fragment:

*p = 1; // store through p *q = 2; // store through q use(*p); // can we reuse the value 1 we just wrote?

Can the compiler forward the constant 1 into use(*p)? Only if it can prove that p and q do not alias. If q might point at the same cell as p, then *q = 2 may have overwritten it, and the value is 2, not 1. Almost every memory optimisation — redundant-load elimination, store forwarding, register promotion, code motion of loads out of loops, reordering for parallelism — rests on the same question: do these two accesses touch disjoint memory? To move code safely you usually need to prove must-not-alias, and that is precisely what pointer analysis exists to establish.

May-alias vs must-alias

Because the exact answer is generally unknowable, alias analysis gives one of two approximate answers, and it is vital to know which:

May-alias — "is it possible that p and q refer to the same location on some execution?" A may-analysis is a conservative over-approximation: if it says "no may-alias", the two truly never alias.
Must-alias — "do p and q definitely refer to the same location on every execution that reaches here?" A must-analysis is an under-approximation used to justify propagating a value from one name to another.

The optimiser's typical need is the negation of may-alias: to reorder or reuse a load it wants "no-alias" = "not may-alias". So a good may-alias analysis is one that says "may-alias" as rarely as it soundly can — every spurious "maybe" is a missed optimisation. Note the asymmetry with soundness: a may-analysis errs by saying "maybe" too often; a must-analysis errs by saying "definitely" too rarely. Both stay safe; both leave performance on the table.

Points-to analysis: the underlying machinery

You rarely compute aliasing directly. Instead you compute a points-to relation — \mathit{pt}(p), the set of abstract memory objects (typically named by their allocation site) that pointer p may hold — and then read aliasing off it: p and q may-alias exactly when their points-to sets intersect.

p \text{ may-alias } q \iff \mathit{pt}(p) \cap \mathit{pt}(q) \neq \varnothing.

The two foundational algorithms are flow-insensitive — they ignore statement order and control flow, treating the program as an unordered bag of pointer assignments, and computing one points-to set per variable valid for the whole program. That sounds crude, but it scales to millions of lines, and it is the backbone of what production compilers actually run.

Above, nodes are pointer variables and heap objects; an edge p \to o means "p may point at object o". Because p and r both point at o_1, their points-to sets intersect, so p and r may-alias.

Andersen vs Steensgaard: inclusion vs unification

The two classic flow-insensitive analyses differ in exactly one design choice — how they treat an assignment p = q — and that choice sets their entire precision/scalability character.

Andersen's analysis (1994) is inclusion-based. It reads p = q as a subset constraint \mathit{pt}(q) \subseteq \mathit{pt}(p): everything q can point to, p can point to. It collects such constraints across the whole program and computes their least solution by iterating to a fixed point — which amounts to a dynamic transitive closure and costs O(n^3) in the worst case. Precise, but heavy.

Steensgaard's analysis (1996) is unification-based. It reads p = q as an equality: p and q must henceforth have the same points-to set, so it merges their nodes with a union-find structure. Because merges never split, each variable ends up in one equivalence class, and the whole analysis runs in near-linear time — O(n\,\alpha(n)). The price is precision: forcing equality where inclusion would suffice conflates objects that Andersen keeps apart.

	Andersen	Steensgaard
Treats `p = q` as	inclusion \mathit{pt}(q)\subseteq\mathit{pt}(p)	unification \mathit{pt}(p)=\mathit{pt}(q)
Direction	directed (one-way) constraints	undirected (symmetric) merge
Data structure	constraint graph + worklist	union-find (disjoint sets)
Worst-case cost	O(n^3)	O(n\,\alpha(n)) near-linear
Precision	higher	lower (over-merges)
Typical use	when precision matters most	whole-program at massive scale

A Steensgaard-style analysis in code

Here is the unification idea in miniature: a union-find over pointer variables, with each class carrying the heap object it points to. Assignment merges classes; address-of records a points-to target. Two variables may-alias exactly when they end up pointing to the same object.

// Union-find (disjoint-set) over pointer variables. class UnionFind { private parent = new Map<string, string>(); private target = new Map<string, string | null>(); // the object a class points to make(x: string): void { if (!this.parent.has(x)) { this.parent.set(x, x); this.target.set(x, null); } } find(x: string): string { this.make(x); let root = x; while (this.parent.get(root) !== root) root = this.parent.get(root)!; let cur = x; // path compression while (cur !== root) { const nx = this.parent.get(cur)!; this.parent.set(cur, root); cur = nx; } return root; } // Steensgaard: p = q ==> unify p and q (equality of points-to). unify(a: string, b: string): void { const ra = this.find(a), rb = this.find(b); if (ra === rb) return; const ta = this.target.get(ra)!, tb = this.target.get(rb)!; this.parent.set(rb, ra); const merged = ta ?? tb; this.target.set(ra, merged); if (ta && tb && ta !== tb) this.unify(ta, tb); // pointed-to objects merge too } pointAt(p: string, obj: string): void { this.make(obj); this.target.set(this.find(p), obj); } pointsTo(p: string): string | null { return this.target.get(this.find(p)) ?? null; } mayAlias(a: string, b: string): boolean { const ta = this.pointsTo(a), tb = this.pointsTo(b); return ta !== null && ta === tb; } } // Program: a = &o1; b = &o2; p = &a; r = &a; p = r; const uf = new UnionFind(); uf.pointAt("a", "o1"); uf.pointAt("b", "o2"); uf.pointAt("p", "a"); // p -> a uf.pointAt("r", "a"); // r -> a uf.unify("p", "r"); // p = r : same points-to class console.log("p may-alias r? " + uf.mayAlias("p", "r")); // true: both -> a console.log("a may-alias b? " + uf.mayAlias("a", "b")); // false: o1 vs o2

Because unification is symmetric and never undone, the class structure only ever grows coarser — which is exactly why it is fast, and exactly why it sometimes says "may-alias" where Andersen's directed constraints would prove disjointness.

The precision knobs

Beyond the inclusion/unification split, a pointer analysis is tuned along several orthogonal sensitivity dimensions, each trading precision for cost:

Flow sensitivity — respect statement order (a per-program-point points-to set) instead of one global set. More precise; far more expensive.
Field sensitivity — distinguish o.f from o.g rather than collapsing every field of an object into one cell. Cheap and usually well worth it.
Context sensitivity — keep points-to facts separate per calling context (call-site or object sensitivity), exactly as in interprocedural analysis.
Heap modelling — how finely abstract objects are named: one node per allocation site is the standard; coarser models merge more, finer models (e.g. per-context heap) split more.

Every knob you turn up shrinks spurious may-alias pairs and enables more optimisation — until the analysis stops finishing in reasonable time. Choosing where to sit on this curve is the engineering of a pointer analysis.

Because sound whole-program pointer analysis is expensive and often imprecise, languages let the programmer assert non-aliasing that the compiler may then assume. C's restrict keyword promises that a pointer is the only access path to the object it points to for its lifetime, licensing aggressive load/store reordering. C99's strict-aliasing rule lets the compiler assume pointers of incompatible types don't alias. Rust goes furthest: its ownership and borrowing rules guarantee at compile time that a &mut reference is unique — a language-level must-not-alias proof — which is precisely why Rust can hand LLVM noalias annotations that C code usually can't, and sometimes optimise better than equivalent C.

Deciding whether two pointers may alias in a general program is undecidable — it reduces to the halting problem (you can make aliasing depend on whether an arbitrary computation terminates). So there is no "exact" alias analysis, only sound approximations that err on the safe side. The safe side for a may-analysis is to say "may-alias" when unsure: a spurious yes only forgoes an optimisation, whereas a spurious no would let the compiler miscompile. Never read "may-alias" as "does alias" — it means "the analysis could not prove they don't". The whole game is building analyses precise enough to say "no" often, while never unsoundly saying "no" when the answer might be "yes".