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. In this paper we define and evaluate a points-to analysis for Java which extends Andersen’s points-to analysis for C [4]. Andersen’s analysis for C can be implemented efficiently by using systems of set-inclusion constraints and by employing several techniques for constraint representation and resolution. We extend these techniques to efficiently represent and solve systems of annotated inclusion constraints. The annotations play two roles in our analysis. Method annotations are used to model precisely and efficiently the semantics of virtual calls. Field annotations allow us to distinguish the flow of values through different fields of an object. In addition, our analysis keeps track of all methods reachable from the entry point of the program, and avoids analyzing dead library code. We evaluate the performance of the analysis on a large set of realistic Java programs. Our results show that the analysis is practical and therefore will be useful as a relatively precise general-purpose points-to analysis for Java. The experiments also show that the points-to solution has significant impact on call graph construction, virtual call resolution, elimination of unnecessary synchronization, and stack-based object allocation.