Andersen's Pointsto analysis
Andersen’s PointstoAnalysis
Level 0: Recall
Andersen’s PointstoAnalysis is one of the two seminal types of pointstoanalyses (the other one being Steensgaard’s PointstoAnalysis.) The goal of pointstoanalyses is to find out the pointsto relationship between variables and allocation sites. The analysis is implemented as a constraint satisfaction problem.
Level 1: Understanding
The difference between Andersen’s PointstoAnalysis and Steensgaard’s PointstoAnalysis comes from the way the constraints are generated to formulate the constraint satisfaction problem. Andersen’s PointstoAnalysis formulates subset constraints while Steensgaard’s PointstoAnalysis formulates unificationbased 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 PointstoAnalysis? Same reason why we use any pointstoanalysis: some optimization problems require finding out the pointstorelationship 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 PointstoAnalysis over Steensgard PointstoAnalysis: Both analyses can be formulated as context and field insensitive analyses, however, Andersen’s PointstoAnalysis differs from Steensgaard’s in that it is flowsensitive. This means that if there is a need for flowsensitivity one would choose Andersen’s PointstoAnalysis over Steensgaard’s PointstoAnalysis.
Level 3: Analysis
How would one implement an Andersen’s PointstoAnalysis? 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 PointstoAnalysis 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 demanddriven pointsto 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 PointstoAnalysis. In GCC there exists an implementation of Andersen’s PointstoAnalysis which is fieldsensitive (for stack allocated structvariables). 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.
No webmentions were found.

{% for webmention in webmentions %}

{{ webmention.content }}
{% endfor %}
No bookmarks were found.
{% endif %}
{% for webmention in webmentions %}
 {% endfor %}
No likes were found.
{% endif %}
{% for webmention in webmentions %}

{{ webmention.content }}
{% endfor %}
No links were found.
{% endif %}
{% for webmention in webmentions %}
 {{ webmention.title }} {% endfor %}
No posts were found.
{% endif %}
{% for webmention in webmentions %}

{{ webmention.content }}
{% endfor %}
No replies were found.
{% endif %}
{% for webmention in webmentions %}
 {% endfor %}
No reposts were found.
{% endif %}
{% for webmention in webmentions %}
 {% endfor %}
No RSVPs were found.
{% endif %}
{% for webmention in webmentions %}

{% if webmention.author %} {% endif %}{% if webmention.content %} {{ webmention.content }} {% else %} {{ webmention.title }} {% endif %}
{% endfor %}
No webmentions were found.
{% endif %}