Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper presents an analysis and transformation for individual object reclamation in 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 programs 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.

REFERENCES

• 1: Jonathan Aldrich , Valentin Kostadinov , Craig Chambers, Alias annotations for program understanding, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 2: Bowen Alpern , C. R. Attanasio , Anthony Cocchi , Derek Lieber , Stephen Smith , Ton Ngo , John J. Barton , Susan Flynn Hummel , Janice C. Sheperd , Mark Mergen, Implementing jalapeño in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.314-324, November 01-05, 1999, Denver, Colorado, United States
• 3: John Boyland, Alias burying: unique variables without destructive reads, Software—Practice & Experience, v.31 n.6, p.533-553, May 2001 [doi>10.1002/spe.370]
• 4: Sigmund Cherem , Radu Rugina, Region analysis and transformation for Java programs, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029884]
• 5: Sigmund Cherem , Radu Rugina, Compile-time deallocation of individual objects, Proceedings of the 5th international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada [doi>10.1145/1133956.1133975]
• 6: S. Cherem and R. Rugina. A practical escape and effect analysis for building lightweight method summaries. In Proceedings of the International Conference on Compiler Construction, Braga, Portugal, March 2007.
• 7: Wei-Ngan Chin , Florin Craciun , Shengchao Qin , Martin Rinard, Region inference for an object-oriented language, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 8: GNU Classpath. http://www.gnu.org/software/classpath/.
• 9: David Gay , Bjarne Steensgaard, Fast Escape Analysis and Stack Allocation for Object-Based Programs, Proceedings of the 9th International Conference on Compiler Construction, p.82-93, March 25-April 02, 2000
• 10: Samuel Z. Guyer , Kathryn S. McKinley , Daniel Frampton, Free-Me: a static analysis for automatic individual object reclamation, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 11: Brian Hackett , Radu Rugina, Region-based shape analysis with tracked locations, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.310-323, January 12-14, 2005, Long Beach, California, USA
• 12: Michael Hicks , Greg Morrisett , Dan Grossman , Trevor Jim, Experience with safe manual memory-management in cyclone, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029883]
• 13: Kin-Keung Ma , Jeffrey S. Foster, Inferring aliasing and encapsulation properties for java, Proceedings of the 22nd annual ACM SIGPLAN conference on Object oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 14: Naftaly H. Minsky, Towards Alias-Free Pointers, Proceedings of the 10th European Conference on Object-Oriented Programming, p.189-209, July 08-12, 1996
• 15: Mooly Sagiv , Thomas Reps , Reinhard Wilhelm, Solving shape-analysis problems in languages with destructive updating, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.1, p.1-50, Jan. 1998 [doi>10.1145/271510.271517]
• 16: Mooly Sagiv , Thomas Reps , Reinhard Wilhelm, Parametric shape analysis via 3-valued logic, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.3, p.217-298, May 2002 [doi>10.1145/514188.514190]
• 17: R. Shaham, E. Yahav, E. K. Kolodner, and M. Sagiv. Establishing local temporal heap safety properties with applications to compiletime memory management. In Proceedings of the International Static Analysis Symposium, San Diego, CA, June 2003.
• 18: Mads Tofte , Jean-Pierre Talpin, Implementation of the typed call-by-value λ-calculus using a stack of regions, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.188-201, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177855]
• 19: Raja Vallée-Rai , Phong Co , Etienne Gagnon , Laurie Hendren , Patrick Lam , Vijay Sundaresan, Soot - a Java bytecode optimization framework, Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research, p.13, November 08-11, 1999, Mississauga, Ontario, Canada
• 20: P. Wadler. Linear types can change the world! In M. Broy and C. Jones, editors, Working Conference on Programming Concepts and Methods, pages 347--359. North Holland, 1990.
• 21: John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.187-206, November 01-05, 1999, Denver, Colorado, United States
• 22: Reinhard Wilhelm , Shmuel Sagiv , Thomas W. Reps, Shape Analysis, Proceedings of the 9th International Conference on Compiler Construction, p.1-17, March 25-April 02, 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

General Terms:
Languages, Performance

Keywords:
compile-time memory management, individual object deallocation, object destructors, program transformations, uniqueness inference