Points-to Analysis as Constraint Solving

Patrick Nappa,  Bernhard Scholz, Jens Dietrich
University of Sydney

Points-to analysis is one of the major building blocks in programming language tools including compilers, program analysis tools, and integrated development editors. However, one of the major challenges in the research of points-to analysis is scalability. For large code bases, computing these points-to analyses is causing issues due to the near cubic worst-case complexity runtime of points-to analysis, hampering its scalability.

We introduce a new algorithmic approach for points-to analysis that translates the points-to problem to a constraint solving problem. The constraint solver uses a bottom-up approach minimizing work for points-to with various techniques including graph compression, i.e., dominance and strongly connected component analysis. The core of our new research is a new alias algorithm that finds pairs of alias relations in bulk by exploiting symmetry. We devise a new algorithm that minimizes work by employing the minimum set cover problem.  We provide real-world benchmarks to show the efficiency of our new approach.