CR:ISMM07

Summary

Uniqueness Inference for Compile-Time Object Deallocation. Sigmund Cherem and Radu Rugina. In Proceedings of the 2007 International Symposium on Memory Management (ISMM 2007), Montreal, Quebec, Canada, October 2007.
(PDF) (Slides)

Abstract

This paper presents an analysis and transformation for individual object reclamation for Java programs. First, we propose a uniqueness inference algorithm that identifies variables and object fields that hold unique references. The algorithm performs an intra-procedural analysis of each method, and then builds and solves a set of inter-procedural uniqueness dependencies to find the global solution. Second, our system uses the uniqueness information to automatically instrument program with explicit deallocation of individual objects. A key feature of the transformation is its ability to deallocate entire heap structures, including recursive structures, when their root objects are freed. This is achieved by generating object destructors that recursively free all of the unique object fields. Our experiments show that the analysis is effective at reclaiming a large fraction of the objects at a low analysis cost.

Bibtex entry

@INPROCEEDINGS { CR:ISMM07,
    AUTHOR = { Sigmund Cherem and Radu Rugina },
    TITLE = { Uniqueness Inference for Compile-Time Object Deallocation },
    BOOKTITLE = { Proceedings of the 2007 International Symposium on Memory Management (ISMM 2007) },
    ADDRESS = { Montreal, Quebec, Canada },
    MONTH = { October },
    YEAR = { 2007 },
    URL = { http://www.cs.cornell.edu/w8/~siggi/getfile.php?ismm07.pdf },
    SLIDES = { http://www.cs.cornell.edu/w8/~siggi/getfile.php?ismm07.ppt },
    ABSTRACT = { This paper presents an analysis and transformation for individual object reclamation for Java programs. First, we propose a uniqueness inference algorithm that identifies variables and object fields that hold unique references. The algorithm performs an intra-procedural analysis of each method, and then builds and solves a set of inter-procedural uniqueness dependencies to find the global solution. Second, our system uses the uniqueness information to automatically instrument program with explicit deallocation of individual objects. A key feature of the transformation is its ability to deallocate entire heap structures, including recursive structures, when their root objects are freed. This is achieved by generating object destructors that recursively free all of the unique object fields. Our experiments show that the analysis is effective at reclaiming a large fraction of the objects at a low analysis cost. },
}