Escape analysis for object-oriented languages

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Escape analysis for object-oriented languages: application to Java

Full text

Pdf (1.73 MB)

Source

Conference on Object Oriented Programming Systems Languages and Applications archive
Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications table of contents

Denver, Colorado, United States

Pages: 20 - 34

Year of Publication: 1999

ISBN:1-58113-238-7

Also published in ...

Author

Bruno Blanchet

INRIA Rocquencourt Domaine de Voluceau - BP 105, 78153 Le Chesnay Cedex, France

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 85, Citation Count: 68

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/320384.320387 What is a DOI?

ABSTRACT

Escape analysis [27, 14, 5] is a static analysis that determines whether the lifetime of data exceeds its static scope.The main originality of our escape analysis is that it determines precisely the effect of assignments, which is necessary to apply it to object oriented languages with promising results, whereas previous work [27, 14, 5] applied it to functional languages and were very imprecise on assignments. Our implementation analyses the full Java™ Language.We have applied our analysis to stack allocation and synchronization elimination. We manage to stack allocate 13% to 95% of data, eliminate more than 20% of synchronizations on most programs (94% and 99% on two examples) and get up to 44% speedup (21% on average). Our detailed experimental study on large programs shows that the improvement comes from the decrease of the garbage collection and allocation times than from improvements on data locality [7], contrary to what happened for ML [5].

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alexander Aiken , Manuel Fähndrich , Raph Levien, Better static memory management: improving region-based analysis of higher-order languages, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.174-185, June 18-21, 1995, La Jolla, California, United States
	2	Jonathan Aldrich , Craig Chambers , Emin Gün Sirer , Susan J. Eggers, Static Analyses for Eliminating Unnecessary Synchronization from Java Programs, Proceedings of the 6th International Symposium on Static Analysis, p.19-38, September 22-24, 1999
	3	Lars Birkedal , Mads Tofte , Magnus Vejlstrup, From region inference to von Neumann machines via region representation inference, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.171-183, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237771]
	4	BLANCHET, B. Garbage Collection statique. DEA report, INRIA, Rocquencourt, Sept. 1996.
	5	Bruno Blanchet, Escape analysis: correctness proof, implementation and experimental results, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-37, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268949]
	6	Jeff Bogda , Urs Hölzle, Removing unnecessary synchronization in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.35-46, November 01-05, 1999, Denver, Colorado, United States
	7	Steve Carr , Kathryn S. McKinley , Chau-Wen Tseng, Compiler optimizations for improving data locality, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.252-262, October 05-07, 1994, San Jose, California, United States
	8	D. R. Chase, Safety consideration for storage allocation optimizations, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.1-10, June 20-24, 1988, Atlanta, Georgia, United States
	9	Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-19, November 01-05, 1999, Denver, Colorado, United States
	10	Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
	11	Patrick Cousot , Radhia Cousot, Systematic design of program analysis frameworks, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.269-282, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567778]
	12	Alan Deutsch, On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.157-168, December 1989, San Francisco, California, United States [doi>10.1145/96709.96725]
	13	Alain Deutsch, Interprocedural may-alias analysis for pointers: beyond k-limiting, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.230-241, June 20-24, 1994, Orlando, Florida, United States
	14	Alain Deutsch, On the complexity of escape analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.358-371, January 15-17, 1997, Paris, France [doi>10.1145/263699.263750]
	15	GAy, D., AND STEENSGAARD, B. Stack Allocating Objects in Java. http://research.microsoft, com/apl.
	16	John Hannan, A Type-based Analysis for Stack Allocation in Functional Languages, Proceedings of the Second International Symposium on Static Analysis, p.172-188, September 25-27, 1995
	17	HARRISON, W. The interprocedural analysis and automatic paxallelisation of Scheme programs. Lisp and Symbolic Computation 2 (1989), 176 - 396.
	18	HEDERMAN, L. Compile Time Garbage Collection Using Reference Count Analysis. Tech. l~ep. Rice COMP TR88-75, Rice University, Houston, Texas, Aug. 1988
	19	Paul Hudak, A semantic model of reference counting and its abstraction (detailed summary), Proceedings of the 1986 ACM conference on LISP and functional programming, p.351-363, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319876]
	20	HUGHES, S. Compile-Time Garbage Collection for Higher-Order Functional Languages. J. Logic Computat. 2, 4 (1992), 483 - 509.
	21	Katsuro Inoue , Hiroyuki Seki , Hikaru Yagi, Analysis of functional programs to detect run-time garbage cells, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.555-578, Oct. 1988 [doi>10.1145/48022.48025]
	22	Neil D. Jones , Steven S. Muchnick, A flexible approach to interprocedural data flow analysis and programs with recursive data structures, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.66-74, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582161]
	23	Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
	24	C. E. McDowell, Reducing garbage in Java, ACM SIGPLAN Notices, v.33 n.9, p.84-86, Sept. 1, 1998 [doi>10.1145/290229.290239]
	25	Markus Mohnen, Efficient Closure Utilisation by Higher-Order Inheritance Analysis, Proceedings of the Second International Symposium on Static Analysis, p.261-278, September 25-27, 1995
	26	Markus Mohnen, Efficient Compile-Time Garbage Collection for Arbitrary Data Structures, Proceedings of the 7th International Symposium on Programming Languages: Implementations, Logics and Programs, p.241-258, September 20-22, 1995
	27	Young Gil Park , Benjamin Goldberg, Escape analysis on lists, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.116-127, June 15-19, 1992, San Francisco, California, United States
	28	C. Ruggieri , T. P. Murtagh, Lifetime analysis of dynamically allocated objects, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-293, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73585]
	29	Manuel Serrano , Marc Feeley, Storage use analysis and its applications, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.50-61, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	30	O. Shivers, Control flow analysis in scheme, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.164-174, June 20-24, 1988, Atlanta, Georgia, United States
	31	TOFTE, M., AND TALPIN, J.-P. A theory of Stack Allocation in Polymorphically Typed Languages. Tech. Rep. 93/15, Departement of Computer Science, Copenhagen University, 9 July 1993.

CITED BY 68

	James Noble , David Holmes , John Potter, Exclusion for composite objects, ACM SIGPLAN Notices, v.35 n.10, p.13-28, Oct. 2000
	Tamar Domani , Gal Goldshtein , Elliot K. Kolodner , Ethan Lewis , Erez Petrank , Dafna Sheinwald, Thread-local heaps for Java, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	Y. Aridor , M. Factor , A. Teperman , T. Eilam , A. Schuster, A high performance cluster JVM presenting a pure single system image, Proceedings of the ACM 2000 conference on Java Grande, p.168-177, June 03-04, 2000, San Francisco, California, United States
	Cormac Flanagan , Stephen N. Freund, Detecting race conditions in large programs, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.90-96, June 2001, Snowbird, Utah, United States
	Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, ACM SIGPLAN Notices, v.34 n.10, p.1-19, Oct. 1999
	Feng Qian , Laurie Hendren, An adaptive, region-based allocator for java, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	Morgan Deters , Ron K. Cytron, Automated discovery of scoped memory regions for real-time Java, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	Craig Chambers, Staged compilation, ACM SIGPLAN Notices, v.37 n.3, March 2002
	Christian Grothoff , Jens Palsberg , Jan Vitek, Encapsulating objects with confined types, ACM SIGPLAN Notices, v.36 n.11, p.241-255, 11/01/2001
	Cormac Flanagan , Stephen N. Freund, Type-based race detection for Java, ACM SIGPLAN Notices, v.35 n.5, p.219-232, May 2000
	Ayal Zaks , Vitaly Feldman , Nava Aizikowitz, Sealed calls in Java packages, ACM SIGPLAN Notices, v.35 n.10, p.83-92, Oct. 2000
	Sara Porat , Marina Biberstein , Larry Koved , Bilha Mendelson, Automatic detection of immutable fields in Java, Proceedings of the 2000 conference of the Centre for Advanced Studies on Collaborative research, p.10, November 13-16, 2000, Mississauga, Ontario, Canada
	Dave Clarke , Sophia Drossopoulou, Ownership, encapsulation and the disjointness of type and effect, ACM SIGPLAN Notices, v.37 n.11, November 2002
	Alexandru Salcianu , Martin Rinard, Pointer and escape analysis for multithreaded programs, ACM SIGPLAN Notices, v.36 n.7, p.12-23, July 2001
	Sanjay Ghemawat , Keith H. Randall , Daniel J. Scales, Field analysis: getting useful and low-cost interprocedural information, ACM SIGPLAN Notices, v.35 n.5, p.334-344, May 2000
	Erik Ruf, Effective synchronization removal for Java, ACM SIGPLAN Notices, v.35 n.5, p.208-218, May 2000
	Ulrik Pagh Schultz , Kim Burgaard , Flemming Gram Christensen , Jørgen Lindskov Knudsen, Compiling java for low-end embedded systems, ACM SIGPLAN Notices, v.38 n.7, July 2003
	Darko Marinov , Robert O'Callahan, Object equality profiling, ACM SIGPLAN Notices, v.38 n.11, November 2003
	Radu Rugina , Martin C. Rinard, Pointer analysis for structured parallel programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.1, p.70-116, January 2003
	Donglin Liang , Maikel Pennings , Mary Jean Harrold, Extending and evaluating flow-insenstitive and context-insensitive points-to analyses for Java, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.73-79, June 2001, Snowbird, Utah, United States
	Kiyokuni Kawachiya , Akira Koseki , Tamiya Onodera, Lock reservation: Java locks can mostly do without atomic operations, ACM SIGPLAN Notices, v.37 n.11, November 2002
	Karen Zee , Martin Rinard, Write barrier removal by static analysis, ACM SIGPLAN Notices, v.37 n.11, November 2002
	Jong-Deok Choi , Manish Gupta , Mauricio J. Serrano , Vugranam C. Sreedhar , Samuel P. Midkiff, Stack allocation and synchronization optimizations for Java using escape analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.6, p.876-910, November 2003
	Fausto Spoto , Thomas Jensen, Class analyses as abstract interpretations of trace semantics, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.5, p.578-630, September 2003
	Mikel Luján , Mikel Luján , John R. Gurd , T. L. Freeman , José Miguel, Elimination of Java array bounds checks in the presence of indirection, Proceedings of the 2002 joint ACM-ISCOPE conference on Java Grande, p.76-85, November 03-05, 2002, Seattle, Washington, USA
	Martin Abadi , Cormac Flanagan , Stephen N. Freund, Types for safe locking: Static race detection for Java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.2, p.207-255, March 2006
	Jonathan Aldrich , Emin Gün Sirer , Craig Chambers , Susan J. Eggers, Comprehensive synchronization elimination for Java, Science of Computer Programming, v.47 n.2-3, p.91-120, May 2003
	Dave Clarke , Michael Richmond , James Noble, Saving the world from bad beans: deployment-time confinement checking, ACM SIGPLAN Notices, v.38 n.11, November 2003
	Ovidiu Gheorghioiu , Alexandru Salcianu , Martin Rinard, Interprocedural compatibility analysis for static object preallocation, ACM SIGPLAN Notices, v.38 n.1, p.273-284, January 2003
	Bruno Blanchet, Escape analysis for Java^TM: Theory and practice, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.6, p.713-775, November 2003
	Chandrasekhar Boyapati , Martin Rinard, A parameterized type system for race-free Java programs, ACM SIGPLAN Notices, v.36 n.11, p.56-69, 11/01/2001
	Atanas Rountev , Ana Milanova , Barbara G. Ryder, Points-to analysis for Java using annotated constraints, ACM SIGPLAN Notices, v.36 n.11, p.43-55, 11/01/2001
	Christoph von Praun , Thomas R. Gross, Static conflict analysis for multi-threaded object-oriented programs, ACM SIGPLAN Notices, v.38 n.5, May 2003
	Christoph von Praun , Thomas R. Gross, Object race detection, ACM SIGPLAN Notices, v.36 n.11, p.70-82, 11/01/2001
	Dan Grossman, Type-safe multithreading in cyclone, ACM SIGPLAN Notices, v.38 n.3, March 2003
	John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, ACM SIGPLAN Notices, v.34 n.10, p.187-206, Oct. 1999
	Frédéric Vivien , Martin Rinard, Incrementalized pointer and escape analysis, ACM SIGPLAN Notices, v.36 n.5, p.35-46, May 2001
	Amie L. Souter , Lori L. Pollock, OMEN: A strategy for testing object-oriented software, ACM SIGSOFT Software Engineering Notes, v.25 n.5, p.49-59, Sept. 2000
	Andrés Ferrari , Diego Garbervetsky , Victor Braberman , Pablo Listingart , Sergio Yovine, JScoper: Eclipse support for research on scoping and instrumentation for real time Java applications, Proceedings of the 2005 OOPSLA workshop on Eclipse technology eXchange, p.50-54, October 16-17, 2005, San Diego, California
	Erik Johansson , Konstantinos Sagonas , Jesper Wilhelmsson, Heap architectures for concurrent languages using message passing, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	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
	A. Georges , M. Christiaens , M. Ronsse , K. De Bosschere, JaRec: a portable record/replay environment for multi-threaded Java applications, Software—Practice & Experience, v.34 n.6, p.523-547, May 2004
	Martin Rinard , Alexandru Salcianu , Suhabe Bugrara, A classification system and analysis for aspect-oriented programs, ACM SIGSOFT Software Engineering Notes, v.29 n.6, November 2004
	Jong-Deok Choi , Keunwoo Lee , Alexey Loginov , Robert O'Callahan , Vivek Sarkar , Manu Sridharan, Efficient and precise datarace detection for multithreaded object-oriented programs, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Phung Hua Nguyen , Jingling Xue, Interprocedural side-effect analysis and optimisation in the presence of dynamic class loading, Proceedings of the Twenty-eighth Australasian conference on Computer Science, p.9-18, January 01, 2005, Newcastle, Australia
	Cormac Flanagan , Stephen N. Freund , Shaz Qadeer, Exploiting Purity for Atomicity, IEEE Transactions on Software Engineering, v.31 n.4, p.275-291, April 2005
	Adam Welc , Suresh Jagannathan , Antony Hosking, Safe futures for Java, ACM SIGPLAN Notices, v.40 n.10, October 2005
	Ran Shaham , Eran Yahav , Elliot K. Kolodner , Mooly Sagiv, Establishing local temporal heap safety properties with applications to compile-time memory management, Science of Computer Programming, v.58 n.1-2, p.264-289, October 2005
	Aaron Greenhouse , T. J. Halloran , William L. Scherlis, Observations on the assured evolution of concurrent Java programs, Science of Computer Programming, v.58 n.3, p.384-411, December 2005
	Vugranam C. Sreedhar, Data-centric security: role analysis and role typestates, Proceedings of the eleventh ACM symposium on Access control models and technologies, June 07-09, 2006, Lake Tahoe, California, USA
	Erik Corry, Optimistic stack allocation for java-like languages, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Tatiana Shpeisman , Vijay Menon , Ali-Reza Adl-Tabatabai , Steven Balensiefer , Dan Grossman , Richard L. Hudson , Katherine F. Moore , Bratin Saha, Enforcing isolation and ordering in STM, ACM SIGPLAN Notices, v.42 n.6, June 2007
	Bruno Dufour , Barbara G. Ryder , Gary Sevitsky, Blended analysis for performance understanding of framework-based applications, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom
	Angel Dominguez , Sumesh Udayakumaran , Rajeev Barua, Heap data allocation to scratch-pad memory in embedded systems, Journal of Embedded Computing, v.1 n.4, p.521-540, December 2005
	Michiel Ronsse , Koen De Bosschere, Non-Intrusive Detection of Synchronization Errors Using Execution Replay, Automated Software Engineering, v.9 n.1, p.95-121, January 2002
	Mark Stoodley , Vijay Sundaresan, Automatically Reducing Repetitive Synchronization with a Just-in-Time Compiler for Java, Proceedings of the international symposium on Code generation and optimization, p.27-36, March 20-23, 2005
	Huu Hai Nguyen , Martin Rinard, Detecting and eliminating memory leaks using cyclic memory allocation, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada
	Isil Dillig , Thomas Dillig , Eran Yahav , Satish Chandra, The CLOSER: automating resource management in java, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA
	Mario Méndez , Jorge Navas , Manuel V. Hermenegildo, An Efficient, Parametric Fixpoint Algorithm for Analysis of Java Bytecode, Electronic Notes in Theoretical Computer Science (ENTCS), v.190 n.1, p.51-66, July, 2007
	Christian Grothoff , Jens Palsberg , Jan Vitek, Encapsulating objects with confined types, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.6, p.32-es, October 2007
	Uday P. Khedker , Amitabha Sanyal , Amey Karkare, Heap reference analysis using access graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.1, p.1-es, November 2007
	John Bergin , Liam Murphy, Reducing runtime complexity of long-running application services via dynamic profiling and dynamic bytecode adaptation for improved quality of service, Proceedings of the 2007 workshop on Automating service quality: Held at the International Conference on Automated Software Engineering (ASE), p.22-27, November 06-06, 2007, Atlanta, Georgia
	Ajeet Shankar , Matthew Arnold , Rastislav Bodik, Jolt: lightweight dynamic analysis and removal of object churn, ACM SIGPLAN Notices, v.43 n.10, September 2008
	Francesco Logozzo, Class invariants as abstract interpretation of trace semantics, Computer Languages, Systems and Structures, v.35 n.2, p.100-142, July, 2009
	Jingling Xue , Phung Hua Nguyen , John Potter, Interprocedural side-effect analysis for incomplete object-oriented software modules, Journal of Systems and Software, v.80 n.1, p.92-105, January, 2007
	Jonas Lundberg , Tobias Gutzmann , Marcus Edvinsson , Welf Löwe, Fast and precise points-to analysis, Information and Software Technology, v.51 n.10, p.1428-1439, October, 2009
	Elvira Albert , Samir Genaim , Miguel Gómez-Zamalloa Gil, Live heap space analysis for languages with garbage collection, Proceedings of the 2009 international symposium on Memory management, June 19-20, 2009, Dublin, Ireland
	Mark Hills, Memory Representations in Rewriting Logic Semantics Definitions, Electronic Notes in Theoretical Computer Science (ENTCS), v.238 n.3, p.155-172, June, 2009