Browse Theses

Static analysis of heap references is an important problem because almost all modern programming languages use the heap for dynamic memory structures. Despite significant progress in the theory and practice of static analysis, analyzing properties of heap data has not reached the same level of maturity as the analysis of static and stack data. In particular, the liveness of heap objects is conservatively approximated by its reachability from program variables. Even state of the art garbage collectors are unable to distinguish between reachable objects that are live(i.e., objects used by the program in the future) and the reachable objects that are dead (i.e., objects not used by the program in the future). As a consequence, many dead objects remain uncollected, resulting in memory leaks and poor performance.In this thesis, we propose a method to release dead objects automatically so that they can be collected by the garbage collector. This is done by detecting unused references to objects and setting them to null. If all references to the object are nullified, then the dead objects may become unreachable and may be claimed by garbage collector. The interesting aspects of our method are in both the identification of the analyses required to solve the problem, and the way they are carried out. We identify the following analyses to describe interesting properties of heap data—liveness, aliasing, availability, and anticipability. Together, they cover various combinations of directions of analysis (i.e., forward and backward) and confluence of information (i.e., union and intersection). We describe how these analyses are used to find, at each program point, the references to objects that are guaranteed to be unused in the future. Such references are made null by a transformation pass. If this makes some objects unreachable, they can be collected by the garbage collector. This causes more garbage to be collected, resulting in fewer collections. Additionally, for those garbage collectors that scavenge live objects, it makes each collection faster.In the first part of the thesis, we describe our method for Java like imperative languages, while in the second part of the thesis, we present our method for first order functional languages without imperative features. In each case, a prototype implementation of the analyses is carried out and applied to a set of interesting programs to demonstrate the usefulness of our technique.