Andersen’s Points-to-Analysis

Level 0: Recall

Andersen’s Points-to-Analysis is one of the two seminal types of points-to-analyses (the other one being Steensgaard’s Points-to-Analysis.) The goal of points-to-analyses is to find out the points-to relationship between variables and allocation sites. The analysis is implemented as a constraint satisfaction problem.

Level 1: Understanding

The difference between Andersen’s Points-to-Analysis and Steensgaard’s Points-to-Analysis comes from the way the constraints are generated to formulate the constraint satisfaction problem. Andersen’s Points-to-Analysis formulates subset constraints while Steensgaard’s Points-to-Analysis formulates unification-based analysis. This difference results in difference in complexity and precision of the analysis, Andersen’s being more precise than Steensgard but also having a higher algorithmic complexity.

Level 2: Application

So, why would we use Andersen’s Points-to-Analysis? Same reason why we use any points-to-analysis: some optimization problems require finding out the points-to-relationship in order to find out whether performing a transformation is safe on a given variable. For example: if it is known that two pointer variables are pointing exclusively to the same object at a point in the program, then a compiler optimization pass such as program folding could determine at compile time that a pointer equality operation would yield true and optimize the program accordingly. Why would we use Andersen’s Points-to-Analysis over Steensgard Points-to-Analysis: Both analyses can be formulated as context and field insensitive analyses, however, Andersen’s Points-to-Analysis differs from Steensgaard’s in that it is flow-sensitive. This means that if there is a need for flow-sensitivity one would choose Andersen’s Points-to-Analysis over Steensgaard’s Points-to-Analysis.

Level 3: Analysis

How would one implement an Andersen’s Points-to-Analysis? It is actually quite a simple interpretation of the program and a simple implementation. However, in order to trully simplify the implementation one must have access to a constraint satisfaction solver, otherwise one must write the constraint satisfaction solver themselves. An example of an implementation of an Andersen’s Points-to-Analysis in Prolog can be seen here:

pointsto(U,V) :-
   assign(plain(U),addr(V)).
pointsto(U,X) :
   assign(plain(U),plain(V)),
   pointsto(V,X).
pointsto(U,Y) :-
   assign(plain(U),star(V)),
   pointsto(V,X),
   pointsto(X,Y).
pointsto(X,Y) :-
   assign(star(U),plain(V)),
   pointsto(U,X),
   pointsto(V,Y).

This was taken from:

Saha, Diptikalyan, and C. R. Ramakrishnan. “Incremental and demand-driven points-to analysis using logic programming.” Proceedings of the 7th ACM SIGPLAN international conference on Principles and practice of declarative programming. 2005.

There are of course, extensions possible to Andersen’s Points-to-Analysis. In GCC there exists an implementation of Andersen’s Points-to-Analysis which is field-sensitive (for stack allocated struct-variables). Details on the implementation can be studied on the GCC source code and also here:

Berlin, Daniel. “Structure aliasing in GCC.” Proceedings of the GCC Developers Summit. 2005.