AbstractAn 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.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).