Lab for High Performance Computing SERC, Indian Institute of Science
Home | People | Research | Awards/Honours | Publications | Lab Resources | Gallery | Contact Info | Sponsored Research
Tech. Reports | Conferences / Journals | Theses / Project Reports

Points-to Analysis as a System of Linear Equations

The 17th International Static Analysis Symposium
Perpignan, France, September 14--16, 2010


  1. Rupesh Nasre, Department of Computer Science and Automation
  2. R. Govindarajan, Department of Computer Science and Automation; Supercomputer Education and Research Center


The efficiency of a points-to analysis is critical for several compiler optimizations and transformations, and has attracted considerable research attention. Despite several advances, the trade-off between precision and scalability still remains a key issue. In this work, we propose a novel formulation of the points-to analysis as a system of linear equations. With this, the efficiency of the points-to analysis can be significantly improved by leveraging the advances in solution procedures for solving the systems of linear equations. We demonstrate that the proposed transformation is non-trivial and becomes challenging due to the following facts, namely, multiple pointer indirections, address-of operators and multiple assignments to the same variable. The problem is exacerbated by the need to keep the transformed equations linear. Despite this, we successfully model all the pointer operations. The main technical contribution of our work is a novel inclusion based context-sensitive points-to analysis algorithm based on prime factorization. Experimental evaluation on SPEC 2000 benchmarks and two large open source programs reveals that our approach is competitive to the state-of-the-art algorithms. With an average memory requirement of mere 21MB, our context-sensitive points-to analysis algorithm analyzes each benchmark in 55 seconds on an average.


Full Text