Evaluating the benefits of context-sensitive points-to analysis using a BDD-based implementation
Authors:
Open Access
- 1 September 2008
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Software Engineering and Methodology
- Vol. 18 (1) , 1-53
Abstract
We present Paddle, a framework of BDD-based context-sensitive points-to and call graph analyses for Java, as well as client analyses that use their results. Paddle supports several variations of context-sensitive analyses, including call site strings and object sensitivity, and context-sensitively specializes both pointer variables and the heap abstraction. We empirically evaluate the precision of these context-sensitive analyses on significant Java programs. We find that that object-sensitive analyses are more precise than comparable variations of the other approaches, and that specializing the heap abstraction improves precision more than extending the length of context strings.Keywords
This publication has 42 references indexed in Scilit:
- Context-Sensitive Points-to Analysis: Is It Worth It?2006
- Parameterized object sensitivity for points-to analysis for JavaACM Transactions on Software Engineering and Methodology, 2005
- Parametric shape analysis via 3-valued logicACM Transactions on Programming Languages and Systems, 2002
- A framework for call graph construction algorithmsACM Transactions on Programming Languages and Systems, 2001
- A schema for interprocedural modification side-effect analysis with pointer aliasingACM Transactions on Programming Languages and Systems, 2001
- Interprocedural pointer alias analysisACM Transactions on Programming Languages and Systems, 1999
- Context-sensitive interprocedural points-to analysis in the presence of function pointers1994
- Interprocedural modification side effect analysis with pointer aliasing1993
- Symbolic Boolean manipulation with ordered binary-decision diagramsACM Computing Surveys, 1992
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975