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.
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.
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.
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.
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.
x := *ySuppose the current points-to graph is:
y --> a a --> b x --> cWe 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?
*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.x to that node: at most one edge needs to be created, so this is a constant-time operation.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.O(1): it just involves adding an edge.O(α(n)) amortized time, where α is the inverse Ackermann function, which grows extremely slowly (slower than log n).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.