Abstract
An important problem in the analysis of programs written in object-oriented languages like C++/Java is to determine the values that a pointer variable ( a reference to an object in Java ) can have at run-time. This information can be used for applications such as virtual function resolution, side-e ect analysis, detecting memory errors etc. We address issues involved in designing a scalable, ow-sensitive solution for this and related compile-time analysis questions. First we present a ow-sensitive solution which uses conditional points-to analysis. Although we show that it is better than a solution using alias analysis, it has several limitations which a ect its scalability and precision. Next we identify properties necessary for any scalable, ow-sensitive algorithm solving these problems. Using this characterization, we propose two techniques: preprocessing using types and analysis-usingabstract-values, which remove many of these limitations. We show that these techniques can represent a part of the solution implicitly, and thus facilitate ecient demand-driven computation. We introduce analysis-using-abstract-values by presenting an algorithm for nding the precise solution for may points-to in the presence of only single-level pointers (pointers with a single level of indirection). We show that this algorithm improves the worst-case bound from O(n5 ) to O(n4 ). Finally, we present an extension of this technique for multi-level pointers (pointers with multiple levels of indirection), with examples to show improvements in eciency as well as precision. We also show that this technique can adaptively change ow-sensitivity when it is pro table to do so. We also show that analysis-using-abstract-values aids in modular analysis by allowing the analysis of part of a program and avoiding the need to keep the whole program in memory.