Abstract
Program flow analysis is a technique which determines properties about the run-time behavior of a program by analyzing its source code. Flow information has a wide variety of uses in optimizing compilers and software tools for software understanding, testing and maintenance. There are two important requirements for a flow analysis to be successfully applied in optimizing compilers and software tools: (i) first the analysis needs to be relatively precise and (ii) the analysis needs to be practical. However, typically there is a tradeoff between analysis precision and analysis practicality. Many existing practical flow analyses are based on inclusion constraints. However, these analyses do not model dimensions of analysis precision that are of crucial importance for the analysis of object-oriented languages and its usability in software tools and compilers. The first contribution of this thesis is the development of annotated inclusion constraints— a general framework that allows relatively precise and at the same time practical analysis of large programs. The annotated constraint system is parameterized by an annotation language and operations on the annotations. The key idea is to take a relatively imprecise flow analysis that can be expressed using non-annotated inclusion constraints, and add a dimension of precision by choosing appropriate annotations and operations on the annotations. Using this approach results in analyses that are substantially more precise while remaining efficient and practical. The second contribution is the formulation and implementation of a field-sensitive points-to analysis for Java in the context of this framework. Points-to analysis for Java is a fundamental flow analysis with a wide variety of uses in optimizing compilers and software tools. Extensive experiments show that our analysis has practical cost and achieves substantial impact on various client applications. Another contribution is the development of object sensitivity, a new form of context sensitivity for object-oriented languages. We have formulated and implemented several object-sensitive points-to analyses for Java as instances of the framework for annotated constraints. The empirical results show that object sensitivity substantially improves the precision of points-to and side-effect analyses over context-insensitive analyses. At the same time, the annotations model context sensitivity efficiently, achieving practical cost, comparable to the cost of context-insensitive analysis. The last contribution is the application of relatively precise flow analysis for the construction of interclass dependence diagrams (to be used in integration and regression testing, impact analysis, reverse engineering, etc.). We have developed a general algorithm for diagram construction, and have shown empirically that using field-sensitive points-to analysis improves diagram precision substantially compared to earlier work. The enhanced precision improves the usability of the diagrams in software tools.