Pick your contexts well
Authors:
Open Access
- 26 January 2011
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 46 (1) , 17-30
Abstract
Object-sensitivity has emerged as an excellent context abstraction for points-to analysis in object-oriented languages. Despite its practical success, however, object-sensitivity is poorly understood. For instance, for a context depth of 2 or higher, past scalable implementations deviate significantly from the original definition of an object-sensitive analysis. The reason is that the analysis has many degrees of freedom, relating to which context elements are picked at every method call and object creation. We offer a clean model for the analysis design space, and discuss a formal and informal understanding of object-sensitivity and of how to create good object-sensitive analyses. The results are surprising in their extent. We find that past implementations have made a sub-optimal choice of contexts, to the severe detriment of precision and performance. We define a "full-object-sensitive" analysis that results in significantly higher precision, and often performance, for the exact same context depth. We also introduce "type-sensitivity" as an explicit approximation of object-sensitivity that preserves high context quality at substantially reduced cost. A type-sensitive points-to analysis makes an unconventional use of types as context: the context types are not dynamic types of objects involved in the analysis, but instead upper bounds on the dynamic types of their allocator objects. Our results expose the influence of context choice on the quality of points-to analysis and demonstrate type-sensitivity to be an idea with major impact: It decisively advances the state-of-the-art with a spectrum of analyses that simultaneously enjoy speed (several times faster than an analogous object-sensitive analysis), scalability (comparable to analyses with much less context-sensitivity), and precision (comparable to the best object-sensitive analysis with the same context depth).Keywords
This publication has 19 references indexed in Scilit:
- Evaluating the benefits of context-sensitive points-to analysis using a BDD-based implementationACM Transactions on Software Engineering and Methodology, 2008
- Relations as an abstraction for BDD-based program analysisACM Transactions on Programming Languages and Systems, 2008
- Effective typestate verification in the presence of aliasing2006
- Evaluating the impact of context-sensitivity on Andersen's algorithm for Java programs2005
- Using Datalog with Binary Decision Diagrams for Program Analysis2005
- Reflection Analysis for Java2005
- Parameterized object sensitivity for points-to analysis for JavaACM Transactions on Software Engineering and Methodology, 2005
- Cloning-based context-sensitive pointer alias analysis using binary decision diagrams2004
- Dimensions of Precision in Reference Analysis of Object-Oriented Programming Languages2003
- Featherweight JavaACM Transactions on Programming Languages and Systems, 2001