Research On Points-to Analysis For Java

Points-to analysis mainly aims at getting the runtime points-to sets of program variables. This thesis designs and implements a context-sensitive constraint-based points-to analysis algorithm for Java programs. In addition, this thesis proposes several opitimizations which can be used to accerlerate the algorithm.This thesis describes the design and implementation of an efficient Andersen-style, context-sensitive points-to analysis algorithm for Java code. Our algorithm supports language features like inheritance, polymorphism, and field objects. We track the fields of individual objects separately and make the algorithm in field-sensitive style for aggregate objects. This algorithm first summarizes methods of the program under analysis using directed graphs. The main analysis algorithm uses these graphs to construct the main points-to graph.To improve the efficiency and scalability of the algorithm, this thesis employs two kinds of optimizations, nodes topology construction with concomitance on-line cycle detection and elimination. We perform cycle elimination on points-to graphs to reduce their sizes. Topological sort is performed simultaneously on the nodes of graph to speed up the transitive closure computationon in the main points-to graph. Experiment result shows that the efficiency of the algorithm is notably raised by using these two optimizations.This thesis also introduces a method which uses points-to side-effect(PSE) analysis to accelerate context sensitive points-to analysis. A PSE-free method has no mutation on points-to relation of its calling context. So it can be skipped during points-to analysis. Our method first finds PSE-free methods in the program by performing PSE analysis on the local points-to graphes of the methods. Based on these PSE analysis results, the main points-to analysis algorithm efficiently computes the points-to graph by skipping PSE-free methods. Experiment result shows that the efficiency of the algorithm can be further improved by using PSE analysis.