Andersen's algorithm

Computing the Points-To Graph

In the examples so far, we informally showed how the points-to graph is constructed using a given object abstraction. We now describe an algorithm that constructs the points-to graph automatically, given an abstraction for memory objects.

Points-To Analysis as a Dataflow Analysis

We use a forward dataflow analysis:

Values: the value of the analysis is a points-to graph. Using an adjacency-list representation, the graph is a map from an abstract object to a set of abstract objects, i.e., a value in V → 2^V, where V is the set of abstract objects (and pointer variables). e.g., if x may point to y or z, then the map contains x → {y, z}.
Meet operator: union of edges. e.g., if x may point to y on one path and to z on another path, then after the meet, x may point to either y or z.
Flow-insensitive analysis on the SSA representation: this is a relatively expensive dataflow analysis, so we use a flow-insensitive analysis on the SSA representation, which is usually as precise as a flow-sensitive analysis on the non-SSA representation, but typically much faster. i.e., there is a single global value (a single points-to graph), we may pick the statements in any order, and we meet eagerly: transferring across a statement adds edges to the single global points-to graph, and this addition of edges is the meet with the existing value.
Transfer functions: the general shape of a transfer function for an assignment e1 := e2 is that all the objects that e2 may point to must belong to the points-to set of e1. If e2 points to some object y when the statement executes, then e1 may now also point to y. The transfer function adds all objects that e2 may point to into the points-to set of e1.

This algorithm, which computes the points-to graph represented as a map from each object to a set of objects, is called Andersen's algorithm, after the person who first proposed it.

The Language

We describe the algorithm for a C-like language that supports the following operations:

p := &x         (address of a variable)
p := e          (assign an expression, e.g., a + b, to a variable)
*p := e         (assign through a pointer)
p := *e         (dereference the value computed by an arbitrary expression)
p := new ...    (dynamic allocation)
var x           (local variable declaration; types are omitted)

*p := e subsumes field assignments of the form p->f := q, and p := *e subsumes field reads of the form p := e->f: a dereference of a field is treated as though the entire object has been dereferenced.

Canonicalization

To simplify the analysis, we canonicalize these different syntaxes into a common syntax.

Variable declarations become allocations: we are not concerned about scope and lifetime issues in this analysis, so a local variable declaration can be treated just like any other dynamic allocation. For a declaration var x, we pretend that there is a pointer px initialized to the pointer returned by an allocation of the type of x:
```
var x      becomes      px := new ...
```
Every occurrence of &x is replaced with px (the address of x), and every use of x is replaced with *px. i.e., for each C-like variable, we pretend that we know its address, and every access to the variable dereferences that address.
Complex assignments are broken down: an assignment *e1 := e2, where e1 and e2 are expressions, is broken down into smaller statements that first compute the LHS, then compute the RHS, and then perform the assignment:
```
v1 := e1
v2 := e2
*v1 := v2
```
These three statements represent the original operation. It is easier to define transfer functions for the smaller statements.

Object Abstraction

An unbounded number of objects may be created at runtime by new, so we need an abstraction that gives us a finite set of abstract objects at compile time. We use the allocation-site abstraction: each new statement in the program (identified by its PC) gives rise to one abstract object. In general, Andersen's algorithm is independent of the exact object abstraction, but we use this concrete abstraction because the transfer functions can be slightly different depending on the object abstraction.

Running Example

Consider the following program. Recall that we are doing a flow-insensitive analysis, so the program is just an unordered bag of statements:

var p;
var q;
p := new ...;
q := new ...;
r := &p;
s := new ...;
*r := s;
t := &q;
u := *t;
p := q;

The program contains variable declarations, allocations using new, the & operator, assignments of the form *r := s, dereferences of the form u := *t, and copies of the form p := q.

After canonicalization, var p becomes ap := new ... (where ap represents the address of p), and var q becomes aq := new .... p := new ... becomes *ap := new ..., which is further broken down into v1 := new ... and *ap := v1. r := &p becomes r := ap. p := q becomes *ap := *aq, which is further broken down into v3 := *aq and *ap := v3. Labeling each statement with its PC:

 1: ap := new ...
 2: aq := new ...
 3: v1 := new ...
 4: *ap := v1
 5: v2 := new ...
 6: *aq := v2
 7: r := ap
 8: s := new ...
 9: *r := s
10: t := aq
11: u := *t
12: v3 := *aq
13: *ap := v3

Transfer Functions

We write x → a to represent the fact that a belongs to the points-to set of x, and pt(x) for the points-to set of x. There are four rules.

Allocation (p := new ... at PC l): l ∈ pt(p). e.g., if x → a before the statement x := new ... at PC l, then after transferring across it, x may point to either a or l: we add the edge x → l to the points-to graph.

Adding an edge (rather than replacing the existing edges) is called a weak update: we add a new value to an existing set. In contrast, a strong update would overwrite the existing set with the new value, e.g., change x → a to x → l. Because we are doing a flow-insensitive analysis, which consumes the statements in an arbitrary order and meets eagerly, strong updates would be unsound. Weak updates are sound: we conservatively say that x may point to whatever it was pointing to earlier, plus whatever it may point to by virtue of this statement.

Assign (*p := q): pt(*p) ⊇ pt(q), i.e., for each a ∈ pt(p), pt(a) ⊇ pt(q). e.g., for *x := y, if x → a, x → b, a → d, and y → c, then after the transfer, both a and b may additionally point to c: a → c, d and b → c.

Copy (p := q): pt(p) ⊇ pt(q). e.g., for x := y, if x → a and y → b, then after the transfer, x may point to either a or b, and y still points only to b.

Dereference (p := *q): pt(p) ⊇ pt(*q), i.e., for each a ∈ pt(q), pt(p) ⊇ pt(a). e.g., for x := *y, if x → a, y → b, c, b → d, and c → e, then after the transfer, x may point to whatever b and c may point to, in addition to what it pointed to earlier: x → a, d, e.

Running Andersen's Algorithm on the Example

Statements 1, 2, 3 (allocation): ap → 1, aq → 2, v1 → 3.
Statement 4 (*ap := v1, assign): whatever ap points to (1) may now point to whatever v1 points to (3): 1 → 3.
Statement 5 (allocation): v2 → 5.
Statement 6 (*aq := v2, assign): 2 → 5.
Statement 7 (r := ap, copy): r → 1.
Statement 8 (allocation): s → 8.
Statement 9 (*r := s, assign): r points to 1, so 1 → 8.
Statement 10 (t := aq, copy): t → 2.
Statement 11 (u := *t, dereference): t points to 2, and 2 points to 5, so u → 5.
Statement 12 (v3 := *aq, dereference): aq points to 2, and 2 points to 5, so v3 → 5.
Statement 13 (*ap := v3, assign): ap points to 1, so 1 → 5.

The resulting points-to graph:

ap --> 1         1 --> 3, 5, 8
aq --> 2         2 --> 5
v1 --> 3
v2 --> 5
r  --> 1
s  --> 8
t  --> 2
u  --> 5
v3 --> 5

We keep repeating this procedure for all the statements, in an arbitrary order, until we reach a fixed point, i.e., until no more edges are added. You can check that the graph above is a fixed point. Thus, Andersen's algorithm is a forward dataflow analysis that uses the four rules above as transfer functions and union of edges as the meet operator.

Generalizing Andersen's Algorithm to More Constructs

Andersen's algorithm, as discussed so far, considers four kinds of statements: allocation p := new ..., copy p := q, assign *p := q, and dereference p := *q (after canonicalization, p := &x becomes a copy). Real programming languages have more constructs that manipulate pointers. We now generalize the algorithm to handle some of these constructs.

Pointer Arithmetic, Address-Taken Fields, and Address-Taken Array Elements

Languages like C allow pointer arithmetic, and taking the address of a field or of an array element:

p = q + i;
p = &q->f;
p = &a[i];

What happens to the points-to information in the presence of such statements?

Suppose q points to (the beginning of) some object. After p = q + i, p may point anywhere within the object that q points to: the distance between q and p is i. Similarly, after p = &q->f, p points to the field f within the larger object that q points to. And if a is an array, after p = &a[i], p points to the ith element within the array, i.e., at a distance of i times the element size (e.g., i*4) from the beginning of the array.

In all these cases, p points to the same object as the one that q (or a) points to; the only difference is that p may point to the middle of that object. We treat this as p pointing to the same abstract object as q. i.e., when we say that p points to an abstract object, we really mean that p points to either the beginning or the middle of that abstract object.

What if the pointer goes out of bounds? e.g., due to an overflow, q + i may point outside the object that q points to. In C (and in higher-level languages), pointing beyond the boundary of an object in this way is undefined behavior (UB), and such a program is illegal. Illegal does not necessarily mean that the compiler throws an error; rather, it is the programmer's responsibility to ensure that this situation never arises, i.e., that pointer arithmetic, an address-taken field, or an address-taken array element never yields a pointer beyond the boundary of the object that the original pointer (q or a) pointed to.

Thus, assuming the absence of UB, we can safely say that, after each of these statements, p points within an object that q (or a) pointed to before the execution of the statement. Using this fact, we treat all three constructs as simple copies:

Statement Treated as

p = q + i p = q

p = &q->f p = q

p = &a[i] p = a

These transfer functions assume that pointers cannot go out of bounds (otherwise, the behavior is undefined).

Statement	Treated as
`p = q + i`	`p = q`
`p = &q->f`	`p = q`
`p = &a[i]`	`p = a`

Field-Insensitive Analysis

Higher-level languages like Java and C# do not allow pointer arithmetic, but we can still have field accesses. Consider the following program, where new allocates a new memory object, and we use the allocation-site abstraction (each statement is labeled with its allocation site):

1: x = new;
2: x->f = new;
3: x->g = new;

Statement 1 makes x point to abstract object 1, which represents all objects allocated at allocation site 1.

Statement 2 (x->f = new) updates the field f of the object that x points to, so that it points to the newly allocated object; i.e., field f of object 1 may point to abstract object 2. In other words, the contents of the object pointed to by x may point to 2, which is as good as saying *x = new. The only difference between *x = new and x->f = new is that the former overwrites the entire object, whereas the latter updates only one field of the object. But in either case, the object contains a pointer that may point to abstract object 2. So we simply treat such statements as *x = new. Similarly, x->g = new also becomes *x = new.

The resulting points-to graph using Andersen's algorithm is:

x --> 1
1 --> 2, 3

i.e., x points to 1, and the object allocated at site 1 may point to objects allocated at site 2 or at site 3.

This is called a field-insensitive analysis: we ignore the fact that the pointer to 2 can only live in field f, and the pointer to 3 can only live in field g. Instead, we approximate the whole object as a single abstract object whose contents may point to either 2 or 3. The analysis is not sensitive to the fact that different pointers may be stored in different fields.

Implication: Now consider the statement:

y = x->g;

This reads the contents of the object pointed to by x and stores them in y. In a field-insensitive analysis, this is treated as y = *x. Since x points to 1, and 1 may contain pointers to 2 or 3, we get:

y --> 2, 3

This is imprecise: y only reads the field g, and g can only point to 3. A more precise analysis should have told us that y can only point to 3, and not to 2.

Field-Sensitive Analysis

We can do better, provided the language does not allow pointer arithmetic or address-taken fields. In the presence of pointer arithmetic or address-taken fields, it becomes very hard to determine whether a pointer may point anywhere in the middle of an object, or to field f, or to field g. e.g., for p = q + i, if i is not a compile-time constant, it is hard to say whether p points to field f or to field g.

Languages like Java and C# do not allow pointer arithmetic or address-taken fields. For such languages, we can track the contents of each field of each abstract object separately. For the same program:

1: x = new;
2: x->f = new;
3: x->g = new;

we can say that the field f of abstract object 1 may point to 2, and the field g of abstract object 1 may point to 3. To represent this in the points-to graph, we label each edge with the field through which the pointer may be stored:

x --> 1
1 --f--> 2
1 --g--> 3

Through f, 1 may point to 2; through g, 1 may point to 3. But through g, 1 may not point to 2: if g is dereferenced, only 3 will be obtained. This points-to graph is more precise than the one computed by the field-insensitive analysis.

Implication: For y = x->g, y reads the contents of field g of the object pointed to by x. The object pointed to by x is 1, and the field being dereferenced is g, which may only point to 3. So:

y --> 3

The field-sensitive constraints differentiate based on field names: we know that field g is being dereferenced, so y may only point to 3, and not to 2.

Field-sensitive analysis is easiest in the absence of pointer arithmetic and address-taken fields. In general, it is possible even in their presence, but the analysis becomes more complex. Field-sensitive analyses are thus typically easier and more practical to implement for languages that do not allow pointer arithmetic and address-taken fields, such as Java and C#.

Running Time of Andersen's Algorithm

We now discuss the running time of Andersen's algorithm. We will make some approximations: we will do a worst-case analysis of how much time the algorithm can take, and also discuss the typical time that the analysis may take.

Problem Size

Let n be the size of the program, e.g., the number of statements in the program. We assume:

The number of abstract objects is O(n). Roughly, the number of allocation statements grows with the size of the program. If we are doing a field-sensitive analysis, the number of fields gets multiplied with the number of allocation sites, but we still assume that the total is O(n). The abstract objects form the nodes of the points-to graph, so the points-to graph has O(n) nodes.

Each statement generates a constraint. Writing p as shorthand for the points-to set of p, the constraints are of the following forms:

Statement	Constraint	Meaning
`p = q` (copy)	`p ⊇ q`	whatever `q` may point to, `p` may point to
`*p = q` (assignment through a pointer)	`*p ⊇ q`	whatever `q` may point to, `*p` may point to
`p = *q` (dereference)	`p ⊇ *q`	whatever `*q` may point to, `p` may point to

Most of the program is made up of statements that resemble either assignments, copies, or dereferences, so there are O(n) such constraints.

Fixed-Point Computation by Relaxation

Andersen's algorithm identifies a fixed-point solution for these O(n) constraints. Whenever a constraint is not satisfied, we relax the current solution. e.g., for the copy constraint p ⊇ q, we check whether the constraint is already satisfied; if not, we add elements from the points-to set of q to the points-to set of p, so that the constraint becomes satisfied. This addition of elements to the points-to set of p is called relaxing the solution.

Recall that adding abstract objects to the points-to set of p is equivalent to adding edges to the points-to graph. Since the points-to graph has O(n) nodes, it can have at most O(n²) edges. Relaxing involves growing the points-to sets of some pointers (e.g., growing the points-to set of *p using the constraint *p ⊇ q), i.e., adding edges to the points-to graph.

Also, the points-to set of any single pointer (e.g., the points-to set of q or of *p) contains at most O(n) abstract objects, because that is the total number of abstract objects. i.e., a node in the points-to graph has at most O(n) outgoing edges.

Cost of Relaxing One Constraint

We now consider the worst-case time to relax each kind of constraint individually.

Copy, p ⊇ q: may require the addition of O(n) edges. q may have up to O(n) outgoing edges, and we must ensure that p also has outgoing edges to each of those abstract objects. Checking or inserting all of them takes O(n) time in the worst case.
Assignment through a pointer, *p ⊇ q: may require the addition of O(n²) edges. Both q and p may have O(n) outgoing edges, and for each outgoing edge of p, we must add all the outgoing edges of q to the abstract object that p points to:
```
for all l ∈ q:
  for all m ∈ p:
    add l to m
```
There are two quantifiers, each ranging over O(n) elements: we may need to add O(n) elements to each of O(n) sets, making a total of O(n²) edges. e.g., if q points to {1, 2, 3, ...} and p points to {a, b, c, ...}, then each of 1, 2, 3, ... must be added to the points-to set of a, of b, of c, and so on.
Dereference, p ⊇ *q: may require O(n²) work, by a similar argument. q may point to O(n) abstract objects, each of which may point to O(n) abstract objects, making a total of O(n²) two-hop outgoing edges. The number of distinct abstract objects that p can point to is still at most O(n) (that is the total number of nodes in the graph), but each of the O(n²) two-hop edges must be checked to ensure that the constraint is satisfied, which is an O(n²) operation.

To summarize, the last two constraints are the culprits: the worst-case time to relax the solution so that it satisfies one constraint is O(n²).

Total Running Time

There are O(n) constraints, and each needs to be checked for relaxation at least once, so the worst-case time is O(n³). This is a rough analysis; a more precise analysis is available in David McAllester's paper On the Complexity Analysis of Static Analyses, which includes a theorem that the fixed-point solution for Andersen's algorithm can be obtained in O(n³) time.

Implications: O(n³) is a very disappointing running time. Programs can be very large (thousands to millions of lines of code), and if compilation takes hours or days due to an O(n³) time complexity, it is a non-starter. For this reason, Andersen's algorithm is not very practical for the purposes of compilation, but it is often used for other purposes like verification and program analysis. We will see a faster alternative to Andersen's algorithm next.

Moreover, even the average or typical case is roughly quadratic to cubic. We need to relax O(n) constraints regardless, and even if each relaxation takes O(n) time on average, the total is already O(n²). Even quadratic time is very bad: for a million-line program, quadratic time can take hours or more. It would be acceptable if the worst case were cubic but the typical case were linear; but here, even the typical case is at least quadratic. For this reason, Andersen's algorithm is considered a heavyweight (expensive) algorithm for pointer analysis.