May-Alias Analysis and the Shape of a Points-To Set

A rule that hoists a field read out of a loop is valid only if no store in the loop can modify that field. In a language with references, the store may go through a different variable that happens to point at the same object. Deciding whether two expressions can denote the same storage is alias analysis, and every optimization and every interprocedural check that reasons about mutation depends on it.

Aliasing is a relation between expressions, points-to is a relation to objects

Two pointer expressions alias if they denote overlapping storage. Must-alias means they always do; may-alias means they can on some execution. Points-to analysis computes, for each pointer expression, the set of abstract objects it may refer to. Two expressions may-alias if their points-to sets intersect, possibly restricted to the same field.

The abstraction of objects is the first design decision. A heap allocation site is the usual choice: every object created by a particular new or malloc is represented by one abstract object, regardless of how many times the site executes. This is finite and cheap, and it merges all iterations of a loop into one object, which loses the distinction between the first and last element of a list. Allocation-site abstraction is the reason a points-to analysis can say “this list node may point to any node allocated there”, including itself.

Field sensitivity refines an abstract object into one node per field. Without it, a write to p.x and a read of p.y are treated as aliasing, which is a common source of imprecision in analyses of struct-heavy code. With it, the analysis tracks (object, field) pairs, at a cost proportional to the number of fields in the program’s types.

Array sensitivity is the same idea for elements, and it is usually approximated. A single abstract element per array is common; a bounded number of elements distinguishes the first few indices. Full index sensitivity is undecidable in general and expensive in practice.

Inclusion constraints propagate sets forward

Andersen’s analysis is the reference formulation. It generates constraints from the program syntax:

• p = &x gives the constraint {x} ⊆ pts(p).
• p = q gives pts(q) ⊆ pts(p).
• p = *q gives, for each o in pts(q), pts(o) ⊆ pts(p).
• *p = q gives, for each o in pts(p), pts(q) ⊆ pts(o).

The constraints are solved to the least fixpoint: every points-to set starts empty and grows until no constraint adds an element. The result is a may analysis, because a set contains every object that can flow to the pointer on some path.

The solving strategy determines the cost. A naive worklist that reprocesses every constraint whose input changed is polynomial, with a worst case commonly stated as cubic in the number of variables for the basic formulation. Sparse representations and cycle detection reduce the practical cost substantially, and the analysis is considered usable on programs of millions of lines when field sensitivity is limited.

# Inclusion constraints for a tiny language.
# pts[v] is the set of allocation sites v may point to.
constraints = []  # (source, target) meaning pts[source] <= pts[target]

def solve(pts):
    changed = True
    while changed:
        changed = False
        for src, dst in constraints:
            new = pts[src] - pts[dst]
            if new:
                pts[dst] |= new
                changed = True
    return pts

The loop is the entire solver in its simplest form. Real implementations add a worklist keyed by changed variables and propagate only along constraints that mention them, which is the same optimisation as the dataflow worklist in Monotone Dataflow and Fixpoint Convergence. The lattice here is the powerset of allocation sites, and the transfer functions are the constraint propagations.

Unification is cheaper and coarser

Steensgaard’s analysis replaces inclusion with unification. When two pointers are related by an assignment, their points-to sets are merged into one equivalence class, and the merge is symmetric: if p = q, then p and q point to the same set, even though the assignment only flows one way. The result is solved with a union-find structure in near-linear time.

The price is precision. Unification cannot distinguish “p may point to A or B” from “q points to A and p points to B”; it collapses them. For a linter asking whether two pointers may alias, the coarser answer is still sound for may-alias (it may report more aliases than exist), so it is acceptable when the question is “can this be aliased” and unacceptable when the question is “which object is this”.

The two analyses sit at opposite ends of a curve that also includes one-level flow, which unifies within a function but propagates between functions, and various hybrid forms. The right point depends on the client. A compiler’s alias analysis for optimization wants precision on hot loops; a linter’s taint analysis wants to know whether a value can reach a sink, and a coarser relation that is fast enough to run on every commit may be worth more than a precise one that runs nightly.

Flow sensitivity and strong updates

A flow-insensitive analysis computes one points-to set per variable for the whole function; a flow-sensitive one computes a set per program point. Flow sensitivity buys the ability to do strong updates: after p = &x, p points only to x, and a previous binding is killed. A flow-insensitive analysis must weakly update, adding x to the set and keeping the old targets, because it cannot order the assignments.

Strong updates are what make a local pointer analysis precise enough to prove that a null check dominates a dereference, which is the kind of proof a path-sensitive analysis needs at each branch. Without them, every assignment is an accumulation, and a variable that is reassigned in a loop accumulates every object it ever held. The cost is another dimension in the analysis: a points-to set per program point rather than per variable, which multiplies memory by the number of points.

Most production analyses are flow-insensitive at the heap and flow-sensitive for locals, or flow-sensitive within a function and summary-based across calls. The split reflects where the precision pays: local variables are few and their flow is simple, while heap objects are many and their flow is the whole point of the analysis.

Where alias analysis fails loudly

C and C++ expose the cases that break the abstraction. Pointer arithmetic produces a pointer into the middle of an object, and a cast can reinterpret the same bytes as a different type. A union makes two fields overlap by definition. memcpy copies bytes between objects without any assignment the constraint generator can see, so a model is required or the copy is invisible.

Unsafe Rust has the same character: raw pointers, transmutes, and interior mutability can create aliases the type system does not track. Even safe Rust strains a naive analysis, because a shared reference and a mutable reference cannot coexist, but the borrow checker’s guarantee is not automatically available to an external tool that only sees the syntax.

Interprocedural aliasing adds the summary problem. A function that returns one of its parameters creates an alias between the return value and the argument, and a caller that ignores this will treat the result as fresh. A function that stores its argument into a global creates an alias that outlives the call. Summaries must record these flows, and the context sensitivity discussion in Interprocedural Summaries and Context Sensitivity applies directly: the same function called with two different objects produces two different alias relations.

The practical consequence for a linter is that alias precision is not a luxury. A rule that reports a use-after-free, a double lock, or a write to immutable data is only as good as its alias relation, and the false positives it produces are usually traceable to a specific abstraction choice: allocation-site merging, field insensitivity, or a weak update where a strong one was needed. Those choices belong to the taxonomy in The Structure of False Positives, and naming them in a report does more for triage than any change to the message text.