Lab 19 · Andersen vs Steensgaard points-to analysis over LLVM IR¶

Chapter: 19 · Memory: Alias Analysis & Memory Optimizations · Lessons: 19.4, 19.5 · Time: 10–14 hours · Tests: ./course test 19 (label ch19; the lab tests are ch19.lab and ch19.PointsTo.*)

Goal¶

You implement two whole-program, flow- and context-insensitive points-to analyses over a documented subset of LLVM IR: Andersen's inclusion-based analysis with a worklist solver (Lesson 19.4, Algorithm 19.4.4) and Steensgaard's unification-based analysis with union-find (Lesson 19.5, Algorithm 19.5.3). As a ★ extension you add online cycle elimination to Andersen (Hardekopf–Lin lazy cycle detection or Pearce et al.'s dynamic topological order). The tests check each analysis three ways: exact agreement with a Python oracle on random programs, soundness at run time (every pointer the program actually computes must point into an object of its points-to set), and the precision ordering Andersen ⊆ Steensgaard. Then you measure how many alias pairs each algorithm proves NoAlias, and how long each takes.

The contract¶

One function you write, in pebble/lib/Analysis/Alias/src/ (any files you like; the provided Stub.cpp stops with TODO(ch19) until you replace it). The header is pebble/include/pebble/Analysis/PointsTo.h:

namespace pebble::alias {
using AbstractObject = const llvm::Value *;       // nullptr = the unknown object
enum class PointsToAlgorithm { Andersen, AndersenCycles, Steensgaard };
struct PointsToResult {
  std::map<const llvm::Value *, std::vector<AbstractObject>> Pointers; // every pointer value
  std::map<AbstractObject, std::vector<AbstractObject>> Memory;        // contents of each object
  unsigned Collapsed = 0;                                              // AndersenCycles only
};
PointsToResult computePointsTo(const llvm::Module &M, PointsToAlgorithm A);   // YOU
}

The same header declares the provided helpers (implemented in pebble/lib/Analysis/Alias/provided/Provided.cpp), which fix the definitions the printer, the instrumentation and the tests share: isAbstractObject, isHeapAllocation, objectsOf (the object universe in canonical order), constantPointsTo (the objects a constant operand denotes), pointsTo, alias, objectName, valueName.

Requirements¶

R1 (keys). Pointers has an entry for every pointer-typed argument and instruction of every function with a body (an empty vector if it points nowhere). No duplicates in any vector. computePointsTo does not modify M.
R2 (the IR subset and its constraints). Objects are allocas, global variables, functions, and calls to malloc/calloc (one object per allocation site). The analysis is field-insensitive: one content set per object. Each construct generates these inclusion constraints (Andersen reads them as ⊇, Steensgaard as "unify the pointees"):

Construct	Constraint
`%p = alloca`, `%p = call @malloc/@calloc`	\(p \ni\) that object
`getelementptr`, `bitcast`, `addrspacecast`, `freeze`, `phi`, `select` of pointers	\(\mathrm{pts}(\text{result}) \supseteq \mathrm{pts}(\text{operand})\) for each pointer operand
`%v = load ptr, ptr %p`	\(\mathrm{pts}(v) \supseteq \mathrm{contents}(o)\) for every \(o \in \mathrm{pts}(p)\)
`store ptr %v, ptr %p`	\(\mathrm{contents}(o) \supseteq \mathrm{pts}(v)\) for every \(o \in \mathrm{pts}(p)\)
`llvm.memcpy`/`llvm.memmove(%d, %s)`	\(\mathrm{contents}(o_d) \supseteq \mathrm{contents}(o_s)\) for \(o_d \in \mathrm{pts}(d)\), \(o_s \in \mathrm{pts}(s)\)
direct call of a defined function	each pointer formal \(\supseteq\) its actual; the call's result \(\supseteq\) every returned pointer
indirect call through `%f`	the same, for every function object in \(\mathrm{pts}(f)\) (Andersen: discovered on the fly)
call of a declared function (other than the allocators and intrinsics), `inttoptr`, any other pointer-producing instruction	result \(\ni\) unknown
global variable with initializer	contents \(\ni\) every object its initializer's pointer constants denote
external global (no initializer)	contents \(\ni\) unknown
`main`, and functions with no uses	each pointer parameter \(\ni\) unknown
the unknown object	contents(unknown) \(\ni\) unknown

Constant operands denote constantPointsTo(C); a constant that denotes nothing (null, undef, poison) contributes nothing (in particular, a store ptr null adds no constraint — otherwise Steensgaard would unify every pointer that is ever null). Pointer arguments of external calls are ignored and ptrtoint is outside the subset (both are documented unsound corners: Lesson 19.4 §4). - R3 (Andersen). Andersen returns the least solution of the inclusion constraints (Theorem 19.4.11): exactly the sets the Python oracle computes. - R4 (Steensgaard). Steensgaard returns the unification solution of Algorithm 19.5.3: \(\mathrm{pts}(v)\) is the set of objects in the class \(v\)'s cell points to. Handle indirect calls with a signature per class (Steensgaard's λ types): a class containing function objects carries cells for the return value and each parameter, and an indirect call unifies the actual arguments and result with them. - R5 (soundness). For every execution, every pointer value points into an object of its set (or is null, or points to memory the module does not own). The instrumentation checks this at run time. - R6 ★ (cycle elimination). AndersenCycles returns exactly Andersen's sets and collapses the strongly connected components of the constraint graph online, while solving; Collapsed counts the nodes merged into another node (> 0 on the running example). - R7 (performance). ch19-pointsto --stress 1000 finishes each algorithm in under 5 s on the CI runner (the reference: Andersen 0.6 s, with cycle elimination 0.1 s, Steensgaard 0.01 s). Steensgaard must be \(O(N \alpha(N))\) union-find work plus output (Lesson 19.5 §5).

Output formats¶

The provided printer print<pebble-points-to;ALG> (ALG = andersen, andersen-cycles, steensgaard; module pass, stderr) prints:

pebble-points-to: andersen
ptr <value> -> {<object>, ...}     every pointer argument and instruction, functions in module order
mem <object> -> {<object>, ...}    every object with non-empty contents, objectsOf order, then ?
alias <function>: <n> pointers, <m> may, <k> no
collapsed: <c>                     andersen-cycles only

Values are named f:%x (argument or instruction of function f), objects @g (globals, functions), f:%x (allocas and heap sites of f) and ? (unknown). Sets are sorted in objectsOf order with ? last. The alias line takes the distinct pointer operands of the function's loads, stores and memory intrinsics and counts unordered pairs by alias(): NoAlias iff neither set contains ? and the sets are disjoint (an empty set is disjoint from everything). Example (the running example, corpus/running.c):

mem @p -> {@a, @b, @c}
mem @r -> {@p}
mem @u -> {@c}
alias run: 9 pointers, 3 may, 33 no

Provided infrastructure¶

File	What it gives you
`pebble/lib/Analysis/Alias/provided/Provided.cpp`	the object universe, constant operands, `alias()`, names
`pebble/lib/Passes/Memory/Ch19Passes.cpp`	`print<pebble-points-to;ALG>` and `pebble-points-to-instrument<ALG[;drop]>`
`runtime/ptcheck.c`	the run-time checker the instrumentation calls (register objects, check pointers)
`tools/PointsToMain.cpp`	`ch19-pointsto`: `--table` (precision and time), `--check-order`, `--stress N`
`tools/oracle.py`	random pointer programs as IR (`gen`) and the expected `mem` lines (`dump --alg A`) from `tools/course/lib/pointsto.py`
`corpus/.c`, `corpus/.ll`	five C programs (running example, linked lists, function pointers, swap, structs + memcpy) and their `clang-23 -O0` + `mem2reg` IR

What the tests check¶

Test	Checks
`ch19.PointsTo.EveryPointerIsAKeyAndModuleUnchanged`	R1 on every corpus file, all three algorithms
`ch19.PointsTo.PrecisionOrderingOnCorpus`	Andersen ⊆ Steensgaard per value and object; AndersenCycles = Andersen
`ch19.PointsTo.RunningExample`	the sets of Lessons 19.4–19.5; ★ `Collapsed > 0`
`ch19.PointsTo.UnificationLosesNoAlias`, `UnknownIsConservative`	`alias()` on your sets; unknown handling
`tests/ch19/lab/pointsto-cases.ll`	the exact output for one function per construct of R2 (all three algorithms)
`tests/ch19/lab/pointsto-running.test`	the running example's `mem` lines and alias counts
`tests/ch19/lab/pointsto-oracle.test`	`mem` lines = `oracle.py dump` on 2 × 40 random programs, per algorithm
`tests/ch19/lab/pointsto-sound.test`	R5: instrumented random module and corpus programs run under `lli` without a violation, for both algorithms; the `;drop` negative control must fail
`tests/ch19/lab/pointsto-compare.test`	`--check-order` on corpus + random module; the measurement table's totals; `--stress 300` runs; ★ `collapsed:` > 0

Milestones¶

Constraints. Walk the module and build your constraint representation for R2; print it in a debug mode of your own. Run opt -load-pass-plugin=build/<preset>/lib/PebblePasses.so -passes='print<pebble-points-to;andersen>' -disable-output labs/ch19-points-to/corpus/running.ll.
Andersen (R1, R3): ./course test 19 → ch19.PointsTo.* and pointsto-oracle.test (andersen lines) pass.
Soundness (R5): pointsto-sound.test.
Steensgaard (R4): the remaining oracle lines, pointsto-cases.ll, pointsto-compare.test.
★ Cycle elimination (R6): collapsed: > 0 and identical sets.
Measure: build/<preset>/bin/ch19-pointsto --table labs/ch19-points-to/corpus/*.ll and --stress 1000, --stress 4000; fill in:

Input	may pairs (A)	may pairs (S)
corpus (224 pairs)
stress 1000	—	—
stress 4000	—	—

The reference solution gives 45 vs 51 may-alias pairs on the corpus; on --stress 4000 Andersen takes about 75 s, Andersen with lazy cycle detection 1.8 s and Steensgaard 0.3 s (Lesson 19.4 §8).

Hints¶

Hint 1 — where to start

Separate constraint generation from solving: both algorithms consume the same four constraint kinds (address-of, copy, load, store) plus indirect calls. Give every pointer value a node, and every object a content node that stands for "what this object's memory holds".

Hint 2 — the key idea for Andersen

Loads and stores are "complex" constraints: they add copy edges when a new object appears in the dereferenced set. Remember, per node, which objects you have already expanded, so each (node, object) pair is expanded once. Indirect calls work the same way: a new function object in the callee's set adds copy edges from actuals to formals and from the return node to the result.

Hint 3 — Steensgaard in one sentence

If the content node of object o is also o's location cell, then "o ∈ pts(v)" means "find(content(o)) = pointee(find(v))", and every constraint becomes one or two joins of pointee classes (Algorithm 19.5.3). Make join iterative (an explicit worklist of pairs) so deep unifications do not overflow the stack.

Hint 4 — design sketch

Andersen: vectors indexed by node — SparseBitVector<> points-to sets, successor lists with a DenseSet of edges, per-node lists of load destinations and store sources, a FIFO worklist with an in-list flag. ★ Lazy cycle detection: when propagating along n → m leaves pts(m) = pts(n), run Tarjan's SCC search from m once per edge and merge each component into one representative (union-find over nodes); keep the merged node's constraint lists. Steensgaard: Parent, Rank, Pointee and Signature vectors over cells; fresh cells for pointees created on demand.

Stretch goals¶

★ Field sensitivity (Lesson 19.6): split each object by constant GEP offset (Pearce's field-sensitive model) and compare the table.
★ Difference propagation: propagate only the new part of a set along edges (Pearce et al.) and measure the stress runs again.
★ Das's one-level flow (Algorithm 19.5.5) as a fourth algorithm; check Andersen ⊆ Das ⊆ Steensgaard with --check-order-style code of your own.
★ Register your result as an LLVM alias analysis (AAManager::registerFunctionAnalysis) and see whether pebble-loadfwd finds more.