Home |
People |
Research |
Awards/Honours |
Publications |
Lab Resources |
Gallery |
Contact Info |
Sponsored Research
The 17th International Static Analysis Symposium
Perpignan, France, September 14--16, 2010
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.