Lesson 19.4 — Inclusion-based points-to analysis: Andersen, cycle detection, wave and deep propagation¶

Techniques: Andersen's analysis (inclusion constraints, the constraint graph, the worklist solver, the cubic bound); cycle detection — online (Pearce, Kelly and Hankin 2003), lazy and hybrid (Hardekopf and Lin 2007), offline variable substitution; wave and deep propagation (Pereira and Berlin 2009) · Pebble implements: Andersen, and ★ Andersen with online cycle elimination, in the comparison lab (labs/ch19-points-to, contract pebble/include/pebble/Analysis/PointsTo.h) · Prerequisites: Lesson 19.1; Ch 14 (lattices, least fixed points, worklists; the Datalog view of Lesson 14.8); strongly connected components (Lesson 15.2) · Time: 6–8 hours

1. Problem and motivation¶

The local rules of Lessons 19.2–19.3 know nothing about what a pointer loaded from memory, or passed in as an argument, can point to. Points-to analysis answers that question for every pointer in the program at once: it computes, for each pointer variable \(p\), a set \(\mathrm{pts}(p)\) of abstract objects (allocation sites) that \(p\) may hold the address of. Two pointers whose sets are disjoint cannot alias. The analyses of this lesson are flow-insensitive (one set per variable for the whole program, ignoring statement order) and context-insensitive (one copy of each function); Lessons 19.6–19.7 relax both.

The running example of the chapter (every variable is also a memory location, as in C at -O0; labs/ch19-points-to/corpus/running.c is the same program in C):

1: p = &a      2: q = &b      3: r = &p      4: s = q       5: *r = s
6: t = *r      7: u = &c      8: q = u       9: b = t      10: q = b

What may p point to? Statement 1 says a. Statement 5 writes s into whatever r points to — p — so p also gets what s holds, b (via 4) and c (via 8 and 4). And via 9 and 10 a flows around a cycle back into q. Andersen's answer is \(\mathrm{pts}(p) = \{a, b, c\}\) but \(\mathrm{pts}(u) = \{c\}\).

Andersen's analysis¶

Andersen's PhD thesis [And94] reduced points-to analysis for C to inclusion constraints — "the set of p includes the set of q" — and solved them. Each statement form gives one kind of constraint; the least solution of all constraints is the answer. It is the most precise flow- and context-insensitive analysis for this model, and the baseline every other analysis in this chapter is compared with. GCC's points-to analysis is Andersen-style [GCC-StructAlias]; the course lab implements it over LLVM IR.

Cycle detection¶

The constraint graph of a real program has many cycles of copy edges (the running example has one of five nodes). Every node on a cycle ends with the same set, so propagating sets around the cycle is wasted work. Collapsing each cycle into one node saves most of the solving time. The question is when to look for cycles: before solving (offline; misses cycles that appear only through loads and stores), after every edge insertion (online; Pearce, Kelly and Hankin [PKH03]), only when propagation looks suspicious (lazy; Hardekopf and Lin [HL07]), or with an offline pre-analysis that predicts which cycles will form (hybrid; [HL07]).

Wave and deep propagation¶

Instead of a worklist, wave propagation [PB09] repeats rounds of: collapse all cycles, propagate sets once through the now acyclic graph in topological order, then add the edges that loads and stores require. Deep propagation pushes a change depth-first from the node where it happened. Both avoid revisiting nodes in an unlucky worklist order.

2. Definitions and algorithms¶

Andersen's analysis¶

Definition 19.4.1 (Pointer program and inclusion constraints)

A pointer program is a finite set of statements over a finite set \(V\) of variables, each also a memory location, of four forms. Each generates a constraint on a function \(\mathrm{pts} : V \to \mathcal{P}(\mathit{Obj})\), where \(\mathit{Obj} \subseteq V\) is the set of variables whose address is taken:

\[ \begin{aligned} p = \&a &\quad\leadsto\quad a \in \mathrm{pts}(p) \\ p = q &\quad\leadsto\quad \mathrm{pts}(p) \supseteq \mathrm{pts}(q) \\ p = {*}q &\quad\leadsto\quad \forall o \in \mathrm{pts}(q).\ \mathrm{pts}(p) \supseteq \mathrm{pts}(o) \\ {*}p = q &\quad\leadsto\quad \forall o \in \mathrm{pts}(p).\ \mathrm{pts}(o) \supseteq \mathrm{pts}(q) \end{aligned} \]

The first two are base and simple constraints, the last two complex constraints. On LLVM IR (the lab), variables are SSA pointer values plus one content node per object; load, store, GEP, phi and calls map to these forms (labs/ch19-points-to/SPEC.md, R2).

Definition 19.4.2 (Points-to solution)

A solution is a function \(\mathrm{pts}\) satisfying every constraint of the program. Solutions are ordered pointwise by \(\subseteq\). The least solution \(\mathrm{pts}^*\) is the solution below every other solution (Theorem 19.4.11 shows it exists).

Definition 19.4.3 (Constraint graph)

The constraint graph has a node per variable, labelled with its current set, and an edge \(q \to p\) for each simple constraint \(\mathrm{pts}(p) \supseteq \mathrm{pts}(q)\). Complex constraints are attached to the dereferenced node: a load \(p = {*}q\) is stored at \(q\), a store \({*}p = q\) at \(p\). When an object \(o\) enters \(\mathrm{pts}(q)\), the load adds the edge \(o \to p\); when \(o\) enters \(\mathrm{pts}(p)\), the store adds \(q \to o\). At any time the graph's edges are simple constraints implied by the program and the current sets.

Algorithm 19.4.4 (Andersen's analysis: the worklist solver)

Input: a pointer program (Definition 19.4.1).
Output: \(\mathrm{pts}(v)\) for every variable.
Precondition: none; the program need not execute.
Postcondition: \(\mathrm{pts} = \mathrm{pts}^*\), the least solution (Theorem 19.4.11).
Invariant: (I1) \(\mathrm{pts} \subseteq \mathrm{pts}^*\) pointwise; (I2) every edge of the graph is a simple constraint that \(\mathrm{pts}^*\) satisfies; (I3) every node \(n\) with an unsatisfied outgoing edge or an unexpanded complex constraint is in the worklist \(W\).

function Andersen(program):
    pts[v] ← ∅ for every v;  succ[v] ← ∅;  loads[v] ← [];  stores[v] ← []
    for p = &a:  pts[p] ← pts[p] ∪ {a}
    for p = q:   succ[q] ← succ[q] ∪ {p}
    for p = *q:  loads[q].append(p)
    for *p = q:  stores[p].append(q)
    W ← FIFO of the variables with pts ≠ ∅, without duplicates
    while W ≠ ∅:
        n ← pop(W)
        for o in pts[n]:
            for p in loads[n]:  if AddEdge(o, p): push(W, o)       # p ⊇ *n becomes p ⊇ o
            for q in stores[n]: if AddEdge(q, o): push(W, q)       # *n ⊇ q becomes o ⊇ q
        for m in succ[n]:
            if pts[n] ⊄ pts[m]:
                pts[m] ← pts[m] ∪ pts[n];  push(W, m)
    return pts

function AddEdge(x, y):   # returns true if x → y is new
    if x = y or y ∈ succ[x]: return false
    succ[x] ← succ[x] ∪ {y};  return true

Cycle detection¶

Definition 19.4.5 (Cycle, collapse)

A cycle of the constraint graph is a strongly connected component with at least two nodes. Collapsing a set \(C\) of nodes replaces them by one representative \(r \in C\) (a union-find class): \(\mathrm{pts}(r) \leftarrow \bigcup_{c \in C} \mathrm{pts}(c)\), \(r\) inherits all edges and complex constraints of \(C\) (edges inside \(C\) disappear), and every later reference to a member goes to \(\mathrm{find}(\cdot) = r\).

Algorithm 19.4.6 (Online cycle detection)

Input, output, precondition: as Algorithm 19.4.4.
Postcondition: the least solution; after every insertion the graph (over representatives) has no cycle through the new edge.
Invariant: (I1)–(I3) of Algorithm 19.4.4 for representatives; every collapsed class is contained in a cycle of the graph (Theorem 19.4.14).

# Algorithm 19.4.4 with AddEdge replaced by:
function AddEdgeOnline(x, y):
    x, y ← find(x), find(y)
    if not AddEdge(x, y): return false
    if Reaches(y, x):                          # the new edge closes a cycle
        Collapse(the SCC of the graph that contains x and y)   # Tarjan from y, restricted
    return true

function Reaches(y, x):  depth-first search over succ from y; true if x is visited

Pearce, Kelly and Hankin make Reaches cheap by maintaining a topological order of the graph: an inserted edge \(x \to y\) with \(\mathrm{ord}(x) < \mathrm{ord}(y)\) cannot close a cycle, and otherwise only the nodes between the two positions are searched and reordered [PKH03].

Algorithm 19.4.7 (Lazy cycle detection, LCD)

Input, output, precondition: as Algorithm 19.4.4.
Postcondition: the least solution.
Invariant: as Algorithm 19.4.6; additionally each edge triggers at most one search.

# in Algorithm 19.4.4, replace the propagation loop by:
        for m in succ[n]:
            m ← find(m)
            if pts[n] ⊄ pts[m]:
                pts[m] ← pts[m] ∪ pts[n];  push(W, m)
            else if pts[n] = pts[m] ≠ ∅ and (n, m) not triggered before:
                mark (n, m) triggered
                for each SCC C found by Tarjan's algorithm from m: Collapse(C)
                n ← find(n)

The heuristic: when a propagation along \(n \to m\) changes nothing and the two sets are already equal, \(n\) and \(m\) are probably on a cycle [HL07, §3].

Algorithm 19.4.8 (Hybrid cycle detection, HCD: the offline part)

Input: the program's constraints before solving.
Output: static cycles to collapse at once, and pairs \((\,{*}a, b\,)\) meaning "every object that enters \(\mathrm{pts}(a)\) lies on a cycle with \(b\)".
Precondition: none.
Postcondition: each collapsed set and each pair is implied by the constraints: the cycle exists in the constraint graph of \(\mathrm{pts}^*\) (Theorem 19.4.14).
Invariant: the offline graph has a node \(v\) per variable and a ref node \({*}v\) per dereferenced variable; ref nodes stand for "whatever \(v\) points to".

function HCDOffline(program):
    G ← graph with nodes v and *v;  edges: q → p for p = q;  *q → p for p = *q;  q → *p for *p = q
    for each SCC C of G (Tarjan):
        if C has no ref node and |C| ≥ 2: collapse C now                   # a static cycle
        else if C has exactly one ref node *a and an ordinary node b:
            record (*a, b)                         # every o ∈ pts(a) will close the cycle through *a
    return the recorded pairs

# online, in Algorithm 19.4.4, when n is popped:
#     for each recorded (*n, b): for o in pts[n]: Collapse({o, b})

This presentation records pairs only for SCCs with a single ref node, where the argument of Theorem 19.4.14 is direct; Hardekopf and Lin also handle SCCs with several ref nodes [HL07]. Implementations differ in what they do offline: GCC's scc_visit (called by find_indirect_cycles) also unites the ordinary members of such an SCC at once and maps each ref node to the SCC's representative [GCC-StructAlias] — a merge that is exact whenever the dereferenced sets are non-empty, which is when the cycle actually forms.

Wave and deep propagation¶

Algorithm 19.4.9 (Wave propagation)

Input, output: as Algorithm 19.4.4.
Precondition: none.
Postcondition: the least solution (Theorem 19.4.15).
Invariant: at the start of each round, (I1) and (I2) hold; after step 2 of a round every edge present at the start of the round is satisfied.

function Wave(program):
    initialise pts, succ and the complex constraints as in Algorithm 19.4.4
    repeat:
        for each SCC C of the current graph: Collapse(C)          # 1. now acyclic
        for n in a topological order of the representatives:      # 2. one wave
            for m in succ[n]: pts[m] ← pts[m] ∪ pts[n]
        new ← false                                                # 3. complex constraints
        for each load p = *q:  for o in pts[find(q)]: if AddEdge(find(o), find(p)): new ← true
        for each store *p = q: for o in pts[find(p)]: if AddEdge(find(q), find(o)): new ← true
    until not new
    return pts

Deep propagation [PB09] replaces step 2 by a depth-first push from each node whose set changed, carrying only the new part of the set (the difference), and collapsing cycles when the depth-first search meets a node already on its stack.

3. Worked example¶

Andersen's analysis¶

The running example's initial graph has the copy edges \(q \to s\) (4), \(u \to q\) (8), \(t \to b\) (9), \(b \to q\) (10); sets \(\mathrm{pts}(p) = \{a\}\), \(\mathrm{pts}(q) = \{b\}\), \(\mathrm{pts}(r) = \{p\}\), \(\mathrm{pts}(u) = \{c\}\); the load \(t = {*}r\) and the store \({*}r = s\) hang on \(r\). Algorithm 19.4.4, with a FIFO worklist started in variable order (the table is produced by ./course drill points-to-andersen's oracle, tools/course/lib/pointsto.py):

step	pop	new edges	changes	worklist after
1	p	—	—	q r u
2	q	—	pts(s): {} → {b}	r u s
3	r	p→t, s→p	—	u s p
4	u	—	pts(q): {b} → {b, c}	s p q
5	s	—	pts(p): {a} → {a, b}	p q
6	p	—	pts(t): {} → {a, b}	q t
7	q	—	pts(s): {b} → {b, c}	t s
8	t	—	pts(b): {} → {a, b}	s b
9	s	—	pts(p): {a, b} → {a, b, c}	b p
10	b	—	pts(q): {b, c} → {a, b, c}	p q
11	p	—	pts(t): {a, b} → {a, b, c}	q t
12	q	—	pts(s): {b, c} → {a, b, c}	t s
13	t	—	pts(b): {a, b} → {a, b, c}	s b
14	s	—	—	b
15	b	—	—	—

Step 3: r points to p, so the load t = *r becomes the edge \(p \to t\) and the store *r = s becomes \(s \to p\).
Steps 5–13: the sets travel around the cycle \(p \to t \to b \to q \to s \to p\) twice: once carrying \(\{a, b\}\), once carrying \(c\).
Steps 14–15: the final pops find nothing new.

The final graph and the least solution:

flowchart LR
  r["r {p}"]
  u["u {c}"] --> q
  q["q {a,b,c}"] --> s["s {a,b,c}"]
  s -->|store via r| p["p {a,b,c}"]
  p -->|load via r| t["t {a,b,c}"]
  t --> b["b {a,b,c}"]
  b --> q
  classDef hl fill:#fde68a,stroke:#b45309;
  class p,q,s,t,b hl;

\(\mathrm{pts}(a) = \mathrm{pts}(c) = \emptyset\) (nothing is stored into them), \(\mathrm{pts}(r) = \{p\}\), \(\mathrm{pts}(u) = \{c\}\), and the five highlighted nodes hold \(\{a, b, c\}\). 15 of the 36 pairs of distinct variables have intersecting sets (the drill's pairs count).

Try it yourself: ./course drill points-to-andersen --seed 4 --difficulty hard --solution.

Cycle detection¶

Online (Algorithm 19.4.6). Steps 1–2 as above. In step 3 the new edge \(s \to p\) closes the cycle: \(p \to t \to b \to q \to s \to p\) — \(p\) reaches \(s\) over the edges just added and the copies. The SCC \(\{p, q, b, s, t\}\) collapses into \(p\) with \(\mathrm{pts} = \{a\} \cup \{b\} \cup \emptyset \cup \{b\} \cup \emptyset = \{a, b\}\):

step	pop	new edges	collapse	changes	worklist after
1	p	—	—	—	q r u
2	q	—	—	pts(s): {} →	r u s
3	r	p→t, s→p	{p, q, b, s, t} → p	—	u p
4	u	—	—	pts(p): {a, b} → {a, b, c}	p
5	p	—	—	—	—

Five pops and two propagations instead of fifteen and eleven.

Lazy (Algorithm 19.4.7). No propagation leaves two equal non-empty sets until step 14: popping s finds \(\mathrm{pts}(s) = \mathrm{pts}(p) = \{a, b, c\}\) on the edge \(s \to p\), runs Tarjan from p and collapses the same five nodes; step 15 pops the representative. Here LCD finds the cycle late: its benefit shows on graphs where sets keep growing after the cycle forms (the --stress runs in §8).

Hybrid (Algorithm 19.4.8). The offline graph has the copy edges \(q \to s\), \(u \to q\), \(t \to b\), \(b \to q\), the load edge \({*}r \to t\) and the store edge \(s \to {*}r\). Tarjan finds the SCC \(\{q, s, {*}r, t, b\}\) (the path \(s \to {*}r \to t \to b \to q \to s\)), with one ref node, so HCD records \(({*}r, q)\); every other SCC is a single node. Online, step 3 pops r with \(\mathrm{pts}(r) = \{p\}\) and collapses p with q at once (\(\{a\} \cup \{b\} = \{a, b\}\)): the cycle \(q \to s \to p \to t \to b \to q\) was predicted before a single set had been propagated. Algorithm 19.4.8 alone does not merge s, t and b (they are on the cycle only through \({*}r\); GCC's variant merges them offline), and it finds only cycles visible in the offline graph, which is why HCD is combined with lazy detection.

Wave and deep propagation¶

Algorithm 19.4.9 on the running example (the oracle's andersen_wave trace):

round	SCCs collapsed	topological order	sets after the wave	new edges
1	none	p a r t b u q s c	q {b, c}, s {b, c}; p {a}, r {p}, u {c}	p→t (load), s→p (store)
2	{p, q, b, s, t}	a r u p c	p (the class)	none: stop

Two rounds replace fifteen worklist pops. Deep propagation would push \(c\) from u through q, s, p, t, b in one depth-first sweep once the edges exist.

4. Invariants and correctness¶

Andersen's analysis¶

Definition 19.4.10 (Executions of a pointer program)

An execution runs the statements of a pointer program in any finite order, with repetition, on a store \(\mu : V \to V \cup \{\mathsf{null}\}\) that starts with every variable \(\mathsf{null}\). p = &a sets \(\mu(p) = a\); p = q sets \(\mu(p) = \mu(q)\); p = *q sets \(\mu(p) = \mu(\mu(q))\) and *p = q sets \(\mu(\mu(p)) = \mu(q)\), both doing nothing when the dereferenced pointer is null. A solution is sound if \(\mu(v) \in \mathrm{pts}(v)\) whenever \(\mu(v) \neq \mathsf{null}\), for every store \(\mu\) of every execution. (Flow-insensitivity: any order is allowed, so the analysis covers every real control flow.)

Theorem 19.4.11 (The least solution exists, and Algorithm 19.4.4 computes it)

The set of solutions has a least element \(\mathrm{pts}^*\). Algorithm 19.4.4 terminates and returns \(\mathrm{pts}^*\).

Proof

Existence. The lattice \((V \to \mathcal{P}(\mathit{Obj}), \subseteq)\) is complete and finite. Define \(F(\mathrm{pts})\) as \(\mathrm{pts}\) joined with everything the four rules add in one step (for each constraint, the right-hand side's objects are added to the left-hand side's sets). \(F\) is monotone: every rule adds more when its inputs are larger. The solutions are exactly the fixed points (\(F(\mathrm{pts}) = \mathrm{pts}\) iff no rule adds anything), and by Knaster–Tarski (Ch 14) the least fixed point \(\mathrm{lfp}\,F = \bigsqcup_i F^i(\bot)\) exists and is the least solution.

Invariants. (I1): each assignment in the algorithm adds to \(\mathrm{pts}(m)\) elements of \(\mathrm{pts}(n)\) along an edge \(n \to m\) that, by (I2), is a constraint \(\mathrm{pts}^*\) satisfies; with (I1) for \(n\), the added elements are in \(\mathrm{pts}^*(n) \subseteq \mathrm{pts}^*(m)\). Base elements are in \(\mathrm{pts}^*\) by definition. (I2): initial edges are simple constraints. A load \(p = {*}n\) adds \(o \to p\) only for \(o \in \mathrm{pts}(n) \subseteq \mathrm{pts}^*(n)\) (I1), and the load constraint on \(\mathrm{pts}^*\) then gives \(\mathrm{pts}^*(p) \supseteq \mathrm{pts}^*(o)\); stores are symmetric. (I3): a node's set changes only after a push; edges are added with a push of their source.

Termination. Each iteration pops a node. Pushes happen only when a set grows (at most \(\lvert V \rvert \cdot \lvert \mathit{Obj} \rvert\) times in total) or an edge is added (at most \(\lvert V \rvert^2\) times), so the number of pops is finite.

Result is a solution. At the end \(W = \emptyset\). By (I3) every edge is satisfied and every complex constraint has been expanded for every object in the dereferenced set, so all base, simple and complex constraints hold. With (I1), \(\mathrm{pts} \subseteq \mathrm{pts}^*\) and \(\mathrm{pts}\) is a solution, hence \(\mathrm{pts} = \mathrm{pts}^*\) by minimality.

Theorem 19.4.12 (Andersen's analysis is sound)

Every solution — in particular \(\mathrm{pts}^*\) — is sound for every execution (Definition 19.4.10).

Proof

By induction on the number of executed statements, show that the store satisfies \(\mu(v) \in \mathrm{pts}(v) \cup \{\mathsf{null}\}\) for all \(v\). Initially every value is null. Step p = &a: \(\mu(p) = a \in \mathrm{pts}(p)\) by the base constraint. Step p = q: \(\mu(p) = \mu(q) \in \mathrm{pts}(q) \cup \{\mathsf{null}\} \subseteq \mathrm{pts}(p) \cup \{\mathsf{null}\}\). Step p = *q with \(\mu(q) = o \neq \mathsf{null}\): \(o \in \mathrm{pts}(q)\) by hypothesis, the load constraint gives \(\mathrm{pts}(p) \supseteq \mathrm{pts}(o)\), and \(\mu(p) = \mu(o) \in \mathrm{pts}(o) \cup \{\mathsf{null}\}\). Step *p = q with \(\mu(p) = o \neq \mathsf{null}\): \(o \in \mathrm{pts}(p)\), the store constraint gives \(\mathrm{pts}(o) \supseteq \mathrm{pts}(q)\), and the new \(\mu(o) = \mu(q) \in \mathrm{pts}(q) \cup \{\mathsf{null}\}\). No other variable changes.

Soundness is relative to the model

Theorem 19.4.12 is about the four statement forms. Real C adds pointer arithmetic (handled by field-insensitivity: a GEP result points to the same objects), casts through integers (ptrtoint then inttoptr: the lab maps inttoptr to the unknown object, but an address hidden in an integer stored to memory is lost), external code that stores pointers it receives, and memcpy of pointer-carrying bytes. The lab's SPEC.md lists which of these it models; its run-time instrumentation (pebble-points-to-instrument) checks soundness on real executions.

Cycle detection¶

Lemma 19.4.13 (Nodes on a cycle have equal sets in every solution)

If \(x \to^{+} y\) and \(y \to^{+} x\) in the constraint graph of a solution \(\mathrm{pts}\) (edges being simple constraints that \(\mathrm{pts}\) satisfies), then \(\mathrm{pts}(x) = \mathrm{pts}(y)\).

Proof

Each edge \(u \to w\) gives \(\mathrm{pts}(w) \supseteq \mathrm{pts}(u)\); by transitivity along the path \(x \to^{+} y\), \(\mathrm{pts}(y) \supseteq \mathrm{pts}(x)\), and along \(y \to^{+} x\) the reverse.

Theorem 19.4.14 (Cycle collapse preserves the least solution)

Algorithms 19.4.6, 19.4.7 and 19.4.8 (with 19.4.4) return \(\mathrm{pts}^*\); for a collapsed class \(C\) they report \(\mathrm{pts}^*(c) = \mathrm{pts}(\mathrm{find}(c))\) for every \(c \in C\).

Proof

Consider the constraint system in which the members of a class \(C\) are the same variable. Its least solution \(\mathrm{pts}_C\) satisfies all original constraints (identifying variables adds constraints \(x \supseteq y\) and \(y \supseteq x\) between members), so \(\mathrm{pts}^* \subseteq \mathrm{pts}_C\). Conversely, \(C\) lies on a cycle of edges that \(\mathrm{pts}^*\) satisfies — for Algorithms 19.4.6 and 19.4.7 because every edge added satisfies (I2) of Theorem 19.4.11 and \(C\) is an SCC of those edges; for Algorithm 19.4.8 because a static cycle consists of copy edges, and a recorded pair \(({*}a, b)\) comes from an offline cycle \(b \to \dots \to x \to {*}a \to y \to \dots \to b\) whose only ref node is \({*}a\) (an edge \(x \to {*}a\) is a store \({*}a = x\), an edge \({*}a \to y\) a load \(y = {*}a\)); for each \(o \in \mathrm{pts}^*(a)\) the store and load constraints give the edges \(x \to o \to y\), so \(b \to \dots \to x \to o \to y \to \dots \to b\) is a cycle of edges satisfied by \(\mathrm{pts}^*\). By Lemma 19.4.13 all members have equal sets in \(\mathrm{pts}^*\), so \(\mathrm{pts}^*\) also satisfies the identified system: \(\mathrm{pts}_C \subseteq \mathrm{pts}^*\). So the least solutions coincide, and the proof of Theorem 19.4.11 goes through for the identified system (the collapsed node's set is the union of its members' sets, which are all below \(\mathrm{pts}^*\)). The course oracle checks this on 600 random programs (tools/course/tests/test_ch19.py), and the lab checks AndersenCycles = Andersen.

Wave and deep propagation¶

Theorem 19.4.15 (Wave propagation computes the least solution)

Algorithm 19.4.9 terminates and returns \(\mathrm{pts}^*\).

Proof

Invariant (I1) holds as in Theorem 19.4.11: every union follows an edge satisfied by \(\mathrm{pts}^*\), and collapsing preserves \(\mathrm{pts}^*\) (Theorem 19.4.14). After step 2 of a round, every edge of the round's acyclic graph is satisfied: processing \(n\) in topological order, all of \(n\)'s predecessors have already been processed and \(\mathrm{pts}(n)\) no longer changes in this round, so the union into each successor is final for this round. Step 3 adds the edges required by every complex constraint for the current sets. If no edge is added, all simple, base and complex constraints hold, so \(\mathrm{pts}\) is a solution below \(\mathrm{pts}^*\), i.e. equal to it. Termination: each round that continues adds at least one edge between representatives, and there are at most \(\lvert V \rvert^2\) of them.

5. Complexity¶

Let \(n = \lvert V \rvert\) variables (graph nodes), \(k = \lvert \mathit{Obj} \rvert \le n\) objects, \(m\) statements.

Technique	Time (worst)	Time (typical)	Space
Andersen, worklist, whole-set propagation	\(O(n^2 k^2)\) set-union work (each of \(n\) nodes grows \(\le k\) times and sends \(\le k\) objects along \(\le n\) edges); \(O(n^3)\) with difference propagation	near-linear to quadratic on real code; dominated by large sets on cycles	\(O(n^2 + nk)\): edges plus sets
+ online cycle detection	\(O(n^3)\) plus \(O(n)\) per edge insertion for `Reaches` (less with a topological order)	40× faster than plain on the lab's 4000-variable stress input (§5)	same
+ lazy / hybrid (LCD, HCD)	\(O(n^3)\); each edge triggers at most one Tarjan search (\(O(n + e)\))	LCD + HCD was the fastest combination in [HL07]'s experiments	same, plus the triggered-edge set
Wave	\(O(n^2)\) rounds × \(O(n^2 k)\) per round in the worst case	few rounds: most edges exist after the first	same

Proposition 19.4.16 (The cubic bound)

With difference propagation — each node propagates only the objects that arrived since it was last processed — Andersen's worklist solver does \(O(n^3)\) work, and there is a family of programs on which it does \(\Theta(n^3)\).

Proof

Upper bound. There are at most \(n^2\) edges (between \(n\) nodes). With difference propagation each object crosses each edge at most once, because it is propagated only when it is new at the source, and it is new at a node at most once. So set work is at most \(n^2 \cdot k \le n^3\). Complex constraints: each (node, object) pair is expanded once, adding at most \(n\) edges, so \(O(n \cdot k \cdot n) = O(n^3)\). Lower bound. Take objects \(o_1, \dots, o_n\), sources \(x_1, \dots, x_n\) with \(x_i = \&o_j\) for all \(i, j\) (\(n^2\) statements), and targets \(y_1, \dots, y_n\) with \(y_j = x_i\) for all \(i, j\) (\(n^2\) statements): \(3n\) variables and \(n^2\) edges \(x_i \to y_j\). Every \(x_i\) starts with all \(n\) objects, so when \(x_i\) is popped for the first time its difference is all of \(\{o_1, \dots, o_n\}\), and it sends these \(n\) objects along each of its \(n\) edges: \(n^2\) object transfers per source, \(\Theta(n^3)\) in total (with whole-set propagation the subset tests alone cost the same).

The cubic bound is a property of the problem, not just of this algorithm: Heintze and McAllester relate inclusion-based flow analyses to a problem for which no subcubic algorithm is known, the "cubic bottleneck" [HM97]. At scale the measured behavior of the lab's reference solution on random programs with \(N\) variables and \(3N\) statements (ch19-pointsto --stress N): for \(N = 1000\), 0.6 s plain, 0.1 s with lazy cycle detection; for \(N = 4000\), 75 s plain and 1.8 s with lazy cycle detection (2574 and 10 269 nodes collapsed). Cycles, not the cubic worst case, dominate real inputs.

Andersen's analysis¶

Difference propagation [PKH03]: propagate only \(\Delta = \mathrm{pts}(n) \setminus \mathrm{sent}(n)\); trade-off: one more set per node, much less set work (Proposition 19.4.16's bound depends on it).
Offline variable substitution (Rountev and Chandra [RC00]; HVN/HRU by Hardekopf and Lin [HL07b]): before solving, merge variables that provably get equal sets (pointer equivalence) and objects that are always pointed to together (location equivalence); trade-off: a linear-time pre-pass that often halves the graph. GCC runs it ("Detecting pointer and location equivalences", §7 box).
Sparse bitmaps and BDDs for sets: LLVM's SparseBitVector in the lab; BDDs in bddbddb (Lesson 19.8); trade-off: memory vs. per-operation cost.
Field-sensitive Andersen (Lesson 19.6) and context-sensitive Andersen (Lesson 19.7) refine the model; the solver is unchanged.

Cycle detection¶

Online with dynamic topological order (Pearce et al. [PKH03]): fewer searches than naive DFS-on-insert; trade-off: order maintenance on every insertion.
Lazy (LCD, [HL07]): a search only when a propagation finds equal sets; trade-off: may detect cycles late (the running example), and false triggers cost a search.
Hybrid (HCD, [HL07]): offline prediction of cycles through dereference nodes, plus a lookup table used online; trade-off: finds only cycles visible in the offline graph, so it is combined with LCD. GCC's "Finding indirect cycles" phase is HCD (§7).
Heintze–Tardieu's approach [HT01]: pre-transitive graphs, cycles found by reachability during queries; trade-off: fast for demand-driven clients (Lesson 19.8).

Wave and deep propagation¶

Wave (Algorithm 19.4.9): trade-off: every round recomputes SCCs and a topological order of the whole graph, cheap when few rounds are needed.
Deep propagation [PB09]: pushes each difference depth-first and detects cycles on the DFS stack; trade-off: good locality, but recursion depth grows with graph depth.
SVF's AndersenWaveDiff combines wave with difference propagation and positive-weight-cycle collapse for fields (§7).

7. In real compilers¶

Andersen's analysis¶

GCC, SVF and the lab

GCC gcc/tree-ssa-structalias.cc — constraint generation (get_constraint_for_component_ref for field accesses), then solve_constraints: perform_var_substitution (offline variable substitution), find_indirect_cycles (HCD), solve_graph (the worklist with lazy cycle detection) [GCC-StructAlias] (GCC 14.2; GCC 15 has the same phases). The points-to sets feed the alias oracle of Lesson 19.1 [GCC-TreeAlias]. SVF svf/lib/WPA/Andersen.cpp is a research-grade Andersen over LLVM IR [SX16]. LLVM has no Andersen analysis in its default pipeline: whole-program cost is too high for its compile-time budget, and BasicAA plus TBAA answer most local queries. Pebble pebble/lib/Analysis/Alias/src/ — your lab solution.

GCC's inclusion constraints and points-to sets

Reproduce (gcc-14 14.2.0 (Ubuntu 14.2.0-4ubuntu2~24.04.1); Linux x86-64):

cat > pt.c <<'C'
int f(int k) {
  int x = 1, y = 2, z = 3;
  int *p = &x, *q = &y;
  int **pp = k ? &p : &q;
  *pp = &z;                  /* store through a pointer: p or q may now point to z */
  return *p + *q;
}
C
gcc-14 -O2 -fdump-tree-ealias-details -c pt.c
d=$(ls pt.c.*t.ealias)
echo "== constraints (GCC's four forms: a = &b, a = b, a = *b, *a = b)"
sed -n '/^Constraints:/,/^Collapsing/p' "$d" | grep -E '^\*?(p|q|pp|iftmp)[._0-9]* |= \*?(p|q|pp)|^derefaddrtmp'
echo "== solver phases"
grep -E '^(Collapsing|Detecting|Rewriting|Finding|Solving)' "$d"
echo "== points-to sets"
sed -n '/^Points-to sets/,/^Alias information/p' "$d" | grep -E '^(p|q|pp|iftmp)[._0-9]* = '

Output (complete):

== constraints (GCC's four forms: a = &b, a = b, a = *b, *a = b)
p = &x
q = &y
iftmp.0_5 = &p
iftmp.0_5 = &q
derefaddrtmp(16) = &z
*iftmp.0_5 = derefaddrtmp(16)
p.1_1 = p
_2 = *p.1_1
q.2_3 = q
_4 = *q.2_3
== solver phases
Collapsing static cycles and doing variable substitution
Detecting pointer and location equivalences
Rewriting constraints and unifying variables
Finding indirect cycles
Solving graph
== points-to sets
p = { x z } same as p.1_1
q = { y z } same as q.2_3
iftmp.0_5 = { p q }
p.1_1 = { x z }
q.2_3 = { y z }

What to notice: GCC's constraints are exactly Definition 19.4.1's forms: p = &x, iftmp.0_5 = &p, and the store *iftmp.0_5 = derefaddrtmp(16) with derefaddrtmp(16) = &z (a temporary for the address of z). The solution has p = { x z } and q = { y z }: the store through pp adds z to both, flow-insensitively, even though only one of them is written in any run.

Cycle detection¶

GCC

gcc/tree-ssa-structalias.cc — "Collapsing static cycles and doing variable substitution" (offline SCCs with Nuutila's algorithm and HVN), "Finding indirect cycles" (find_indirect_cycles, hybrid cycle detection), and lazy cycle detection inside solve_graph; the file's comments cite Pearce, Kelly and Hankin and Hardekopf and Lin [GCC-StructAlias]. The ★ part of the lab is LCD.

GCC collapses a copy cycle before solving

Reproduce (gcc-14 14.2.0; Linux x86-64):

cat > cyc.c <<'C'
int f(int k) {
  int x = 1, y = 2, z = 3;
  int *a = &x, *b = &y, *c = &z;
  for (int i = 0; i < k; i++) {   /* rotate: a <- b <- c <- a, a copy cycle */
    int *t = a;
    a = b;
    b = c;
    c = t;
  }
  return *a + *b + *c;
}
C
gcc-14 -O2 -fno-tree-loop-optimize -fdump-tree-ealias-details -c cyc.c
d=$(ls cyc.c.*t.ealias)
echo "== constraints"
sed -n '/^Constraints:/,/^Collapsing/p' "$d" | grep -E '^(a|b|c|t)_[0-9]+ '
echo "== what the solver did"
sed -n '/^Collapsing/,/^Solving/p' "$d" | grep -vE '^Equivalence classes'
echo "== points-to sets"
sed -n '/^Points-to sets/,/^Alias information/p' "$d" | grep -E '^(a|b|c)_[0-9]+ = '

Output (complete):

== constraints
a_5 = &x
a_5 = b_6
b_6 = &y
b_6 = c_7
c_7 = &z
c_7 = a_5
== what the solver did
Collapsing static cycles and doing variable substitution
Building predecessor graph
Detecting pointer and location equivalences
Found location equivalence for node y
Found location equivalence for node z
Direct node id 16 "b_6" mapped to SCC leader node id 15 "a_5"
Direct node id 17 "c_7" mapped to SCC leader node id 15 "a_5"
STOREDANYTHING is a non-pointer variable, eliminating edges.
Rewriting constraints and unifying variables
Unifying b_6 to a_5
Unifying c_7 to a_5
Unifying _2 to _1
Unifying _4 to _1
Uniting pointer but not location equivalent variables
Finding indirect cycles
Solving graph
== points-to sets
a_5 = { x y z }
b_6 = { x y z } same as a_5
c_7 = { x y z } same as a_5

What to notice: the loop rotates three pointers, so the SSA phis form the copy cycle a_5 = b_6, b_6 = c_7, c_7 = a_5. GCC's offline SCC pass maps b_6 and c_7 to the "SCC leader" a_5 and unifies them before the solver runs; all three end with { x y z }, as Lemma 19.4.13 predicts.

Find where GCC does it. In gcc/tree-ssa-structalias.cc (GCC 14.2), which function implements the hybrid cycle detection phase printed as "Finding indirect cycles"? (Quiz gcc-where-hcd.)

Wave and deep propagation¶

SVF

svf/lib/WPA/AndersenWaveDiff.cpp — AndersenWaveDiff::solveWorklist: an SCC detection that yields nodes in topological order (the wave), then a worklist for the loads and stores that the wave made new (postProcessNode) [SVF-Wave, SX16] (SVF 3.3). GCC and LLVM do not use wave propagation.

SVF's wave propagation solver

Reproduce (curl 8.5.0; source at tag SVF-3.3):

curl -sL https://raw.githubusercontent.com/SVF-tools/SVF/SVF-3.3/svf/lib/WPA/AndersenWaveDiff.cpp \
  | sed -n '/^void AndersenWaveDiff::initialize/,/^}/p;/^void AndersenWaveDiff::solveWorklist/,/^}/p'

Output (complete):

void AndersenWaveDiff::initialize()
{
    Andersen::initialize();
    setDetectPWC(true);   // Standard wave propagation always collapses PWCs
}
void AndersenWaveDiff::solveWorklist()
{
    // Initialize the nodeStack via a whole SCC detection
    // Nodes in nodeStack are in topological order by default.
    NodeStack& nodeStack = SCCDetect();

    // Process nodeStack and put the changed nodes into workList.
    while (!nodeStack.empty())
    {
        NodeID nodeId = nodeStack.top();
        nodeStack.pop();
        collapsePWCNode(nodeId);
        // process nodes in nodeStack
        processNode(nodeId);
        collapseFields();
    }

    // New nodes will be inserted into workList during processing.
    while (!isWorklistEmpty())
    {
        NodeID nodeId = popFromWorklist();
        // process nodes in worklist
        postProcessNode(nodeId);
    }
}

What to notice: initialize switches on positive-weight-cycle collapsing; solveWorklist first takes a topologically ordered node stack from SCCDetect() and processes every node once in that order (collapsing cycles as it goes) — step 2 of Algorithm 19.4.9 — and only then handles loads and stores in postProcessNode — step 3.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Andersen's analysis	The most precise flow- and context-insensitive analysis for the model (least solution); on the lab corpus 45 of 224 alias pairs MayAlias, vs 51 for Steensgaard	\(O(n^3)\) with difference propagation · 75 s on the lab's 4000-variable stress input without cycle detection	One set per pointer; exact least solution, easy to inspect	Low for the basic solver (~200 lines), medium with all optimizations	GCC's points-to; SVF; static analyzers; the lab
Cycle detection (online, lazy, hybrid)	Same sets (Theorem 19.4.14)	same bound · 40× faster than plain on the lab's stress run (1.8 s vs 75 s)	Same sets; collapsed-node counts	Medium (union-find, Tarjan, triggered edges)	GCC (HCD + LCD), SVF, research solvers
Wave / deep propagation	Same sets (Theorem 19.4.15)	few rounds of linear work on typical graphs; worst case as above	Same sets	Medium (SCCs and topological order per round)	SVF (`AndersenWaveDiff`), research

Choose Andersen's analysis when you need the best precision a flow- and context-insensitive analysis can give and can afford whole-program solving; it is the reference point for everything else. Choose cycle detection always with it: without it, real programs are one to two orders of magnitude slower. Prefer lazy + hybrid detection in a worklist solver; choose wave propagation when a round-based structure fits (parallel propagation, differential solving) or the graph stabilises in few rounds.

Measure it yourself: build/<preset>/bin/ch19-pointsto --table labs/ch19-points-to/corpus/*.ll and --stress 4000 (the lab's measurement section).

9. Assessment¶

Quiz: andersen-running-pts, andersen-edges-step3 (tag andersen); cycle-collapse-online, cycle-lazy-trigger, gcc-where-hcd (tag cycle-detection); wave-rounds, wave-topo (tag wave-propagation).
Drill: ./course drill points-to-andersen (easy: sets; medium: + alias pairs; hard: + the cycles a detector collapses).
Flashcards: tags andersen, cycle-detection, wave-propagation.
Exercises: the comparison lab labs/ch19-points-to/SPEC.md, milestones 1–3 and ★ 5.

References¶

See the chapter references.

Lesson 19.4 — Inclusion-based points-to analysis: Andersen, cycle detection, wave and deep propagation¶

1. Problem and motivation¶

Andersen's analysis¶

Cycle detection¶

Wave and deep propagation¶

2. Definitions and algorithms¶

Andersen's analysis¶

Cycle detection¶

Wave and deep propagation¶

3. Worked example¶

Andersen's analysis¶

Cycle detection¶

Wave and deep propagation¶

4. Invariants and correctness¶

Andersen's analysis¶

Cycle detection¶

Wave and deep propagation¶

5. Complexity¶

6. Variants and refinements¶

Andersen's analysis¶

Cycle detection¶

Wave and deep propagation¶

7. In real compilers¶

Andersen's analysis¶

Cycle detection¶

Wave and deep propagation¶

8. Comparison¶

9. Assessment¶

References¶