Steensgaard's algorithm

We saw that Andersen's algorithm can take quadratic to cubic time in the size of the program. We now discuss another very popular algorithm, called Steensgaard's algorithm, after the person who proposed it.

Space: From Linear Per Node to Constant Per Node

Recall that Andersen's algorithm requires O(n2) space just to represent the may-points-to relationships: if there are O(n) nodes in the points-to graph, then there can be up to O(n2) edges. (We also saw that computing this graph can take O(n3) time in the worst case.) i.e., Andersen's algorithm requires up to O(n) space for each object, register, or address, because each of them can have up to O(n) outgoing edges, one for each thing that it may point to.

Steensgaard's algorithm requires only constant space for each object, register, or address.

The Key Idea: Unification

Whenever a node has more than one outgoing edge, e.g., p points to both q and r, we merge (or unify) the abstract objects q and r into a single abstract object, which we call {q,r}:
p --> q              p --> {q,r}
p --> r      becomes

Insight: if an object p may point to two different abstract objects q and r, then q and r are likely to behave similarly. So we do not need to track their points-to sets separately; instead, we merge them into a single compound object, and pretend that they are a single abstract object.

Cost: this comes at the cost of precision. After unification, anything that r may point to, q may also point to, and vice versa.

Unification is Transitive

When two nodes are unified, their outgoing edges are also merged, and so the targets of those outgoing edges must also be unified, and so on. e.g., suppose the original points-to graph is:
p --> q, r
q --> s, t
r --> u
s, t, u --> v, w     (each of s, t, u may point to v or w)
Because q and r are unified, the unified node {q,r} may point to s, t, or u; so these are unified into a single abstract object {s,t,u}. Transitively, whatever {s,t,u} may point to is unified into {v,w}. The resulting graph is:
p --> {q,r} --> {s,t,u} --> {v,w}
The big graph with many edges is reduced to a much smaller graph with only three edges. This is the key change from Andersen's algorithm: the points-to information becomes much smaller, potentially at a loss of precision. The hope is that this loss of precision is small for typical programming patterns; this was shown empirically, and that is why this is a popular algorithm.

To summarize, Steensgaard's algorithm relies on the heuristic that all the pointees of a single object are likely to have similar points-to sets (similar behaviour). So we avoid tracking them separately: we unify them into a single node, track them as a single abstract object, and unify their outgoing edges as well, transitively.

A Precision Improvement: Do Not Unify Non-Pointers

A commonly used variant of Steensgaard's algorithm improves precision slightly. Among all the pointees (outgoing edges) of a node, we unify only those pointees that are themselves pointers; we do not unify pointees that are not pointers.

e.g., in the example above, suppose u is not a pointer (e.g., u is an integer, a scalar); then u cannot have any outgoing edges of its own. When q and r are unified, the outgoing edges of {q,r} go to s, t, and u. s and t are unified, because they are pointers that may further point to other things; but u is left alone:

p --> {q,r} --> {s,t} --> {v,w}
        |
        +-----> u
General rule: if a pointee is not a pointer (i.e., it has no outgoing edges of its own), then do not unify it.

This helps because it avoids unnecessary outgoing edges from non-pointers. In the earlier graph, the points-to graph said that u may also point to v or w, even though u is not even a pointer. This simple improvement avoids this precision loss, and it seems to work well when evaluated empirically on real-world programs.

Space and Time Complexity

We analyze the simple Steensgaard's algorithm, i.e., without the precision improvement discussed above.

Space

A node can have at most one outgoing edge: if it had multiple outgoing edges, we would have unified their targets into a single node (and we do this across all edges, transitively). So only a constant amount of space is required for every node in the graph, and the number of edges in the points-to graph is O(n) in the worst case.

This is a significant improvement over the O(n2) worst-case space complexity of Andersen's algorithm. For a program with millions of lines of code, O(n) is of the order of a million, but O(n2) is of the order of a million squared, which may overflow our hardware resources.

Time

The time complexity is determined by the cost of the transfer function for each statement. e.g., consider:
x := *y
Suppose the current points-to graph is:
y --> a
a --> b
x --> c
We look at what y points to (a), and then at what a points to (b). So x may now also point to b. But x was already pointing to c, so x now has two outgoing edges, and we unify b and c into a single node. The new points-to graph is:
y --> a --> {b,c}
x --> {b,c}
What work was required for this transfer?
  1. Identify the node associated with the RHS (here *y). Because every node has at most one outgoing edge, y has at most one outgoing edge (to a), and a has at most one outgoing edge (to b). So there is exactly one such node (b), unlike Andersen's algorithm where there could be up to O(n) such nodes.
  2. Create an edge from x to that node: at most one edge needs to be created, so this is a constant-time operation.
  3. Unify, if required: x may already have had (at most) one outgoing edge; after adding the new edge, we unify the two targets. At most one unification needs to be done.
The exact cost of identification and unification depends on the data structure used to represent the unified nodes. A natural choice is the union-find data structure (from your data structures class): With n statements, there are at most O(n) transfers, so the total time is O(n α(n)). This is almost linear time (slightly higher than linear, but less than O(n log n)), which is a significant improvement over the quadratic-to-cubic time of Andersen's algorithm. That is why Steensgaard's algorithm is typically used in compilers.

Historical Notes