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.