Parameterized object sensitivity for points-to analysis for Java
- 1 January 2005
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Software Engineering and Methodology
- Vol. 14 (1), 1-41
- https://doi.org/10.1145/1044834.1044835
Abstract
The goal of points-to analysis for Java is to determine the set of objects pointed to by a reference variable or a reference object field. We present object sensitivity , a new form of context sensitivity for flow-insensitive points-to analysis for Java. The key idea of our approach is to analyze a method separately for each of the object names that represent run-time objects on which this method may be invoked. To ensure flexibility and practicality, we propose a parameterization framework that allows analysis designers to control the tradeoffs between cost and precision in the object-sensitive analysis. Side-effect analysis determines the memory locations that may be modified by the execution of a program statement. Def-use analysis identifies pairs of statements that set the value of a memory location and subsequently use that value. The information computed by such analyses has a wide variety of uses in compilers and software tools. This work proposes new versions of these analyses that are based on object-sensitive points-to analysis.We have implemented two instantiations of our parameterized object-sensitive points-to analysis. On a set of 23 Java programs, our experiments show that these analyses have comparable cost to a context-insensitive points-to analysis for Java which is based on Andersen's analysis for C. Our results also show that object sensitivity significantly improves the precision of side-effect analysis and call graph construction, compared to (1) context-insensitive analysis, and (2) context-sensitive points-to analysis that models context using the invoking call site. These experiments demonstrate that object-sensitive analyses can achieve substantial precision improvement, while at the same time remaining efficient and practical.Keywords
This publication has 14 references indexed in Scilit:
- The construction of contextual def-use associations for object-oriented systemsIEEE Transactions on Software Engineering, 2003
- 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
- Practical virtual method call resolution for JavaACM SIGPLAN Notices, 2000
- Optimizing Java Bytecode Using the Soot Framework: Is It Feasible?Lecture Notes in Computer Science, 2000
- Call graph construction in object-oriented languagesACM SIGPLAN Notices, 1997
- The effects of the precision of pointer analysisLecture Notes in Computer Science, 1997
- Precise concrete type inference for object-oriented languagesACM SIGPLAN Notices, 1994
- Interprocedural def-use associations for C systems with single level pointersIEEE Transactions on Software Engineering, 1994
- Efficient computation of interprocedural definition-use chainsACM Transactions on Programming Languages and Systems, 1994