Escape analysis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Escape analysis: correctness proof, implementation and experimental results

Full text

Pdf (1.68 MB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

San Diego, California, United States

Pages: 25 - 37

Year of Publication: 1998

ISBN:0-89791-979-3

Author

Bruno Blanchet

ENS and INRIA Rocquencourt, 45, rue d'Ulm. F-75005, Paris

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 32, Citation Count: 20

Additional Information:

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/268946.268949 What is a DOI?

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	Samson Abramsky, Strictness analysis and polymorphic invariance, on Programs as data objects, p.1-23, April 1986, Copenhagen, Denmark
	2	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
	3	Andrew W. Appel, Garbage collection can be faster than stack allocation, Information Processing Letters, v.25 n.4, p.275-279, June 17, 1987 [doi>10.1016/0020-0190(87)90175-X]
	4	APPE{,, A. W., AND SHAO, Z. An Empirical and Analytic Study of Stack vs. Heap Cost for Languages with Closures. Journal of Functional Programming I, 1 (Jan. 1993), I - 27.
	5	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]
	6	BI,^tlCtlET, B. Garbage collection statique. DEA report, INRIA, Rocquencourt, Sept. 1996.
	7	Geoffrey Burn, A relationship between abstract interpretation and projection analysis, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.151-156, December 1989, San Francisco, California, United States [doi>10.1145/96709.96724]
	8	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
	9	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
	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	DOLIG{~, D. Conception, r4alisation eL certification d'un glaneur de cellules ~oncu~renL PhD thesis, Universit6 Paris VII, May 1995.
	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	HARPER, tL, MILNS~, R., AND TO~'rR, M. The definition of Standard ML. LFCS Report Series ECS-LFCS-89-81, Laboratory for Foundations of Computer Science, Dept. of Computer Science, University of Edinburgh, May 1989.
	18	HARPJSON, W. The interprocedural analysis and automatic parallelisation of Scheme programs. Lisp and Symbolic Computation ~ (1989}, 176- 396.
	19	HEVEItMAN, L. Compile Time Garbage Collection Using Reference Count Analysis. Tech. Rap. Rice COMP TR88-75, Rice University, Houston, Texas, Aug. 1988.
	20	James Hicks, Experiences with compiler-directed storage reclamation, Proceedings of the conference on Functional programming languages and computer architecture, p.95-105, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165194]
	21	C. A. R. Hoare, Some Properties of Predicate Transformers, Journal of the ACM (JACM), v.25 n.3, p.461-480, July 1978 [doi>10.1145/322077.322088]
	22	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]
	23	HUGHES, J. Backward Analysis of Functional Programs. In Par- ~ial Evaluation and Mired Computation (1988), D. Bj0rner, A. P. Ershov, and N. D. Jones, Eds., Elsevier Science Publishors B.V. (North Holland).
	24	HUGIt~, S. Compile-Time Garbage Collection for Higher-Order Functional Languages. J. Logic Gomputat. 2, 4 (1992), 483 - 509.
	25	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]
	26	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]
	27	Proceedings of the 3rd European Symposium on Programming, May 1990
	28	KNUTH, D. E. A Generalization of Dijkstra's Algorithm. Information Processing Letters 6, 1 (Feb. 1977), 1 -5.
	29	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
	30	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
	31	A. Neirynck , A. J. Demers, Computation of aliases and support sets, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.274-283, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41650]
	32	Young Gil Park , Benjamin Goldberg, Escape analysis on lists, ACM SIGPLAN Notices, v.27 n.7, p.116-127, July 1992
	33	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]
	34	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
	35	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
	36	TAP~AN, R. Finding dominators in Directed Graphs. SIAM Journal of Oomputing 3, 1 (Mar. 1974), 62- 89.
	37	Robert Endre Tarjan, Applications of Path Compression on Balanced Trees, Journal of the ACM (JACM), v.26 n.4, p.690-715, Oct. 1979 [doi>10.1145/322154.322161]
	38	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 21

	Niels Hallenberg , Martin Elsman , Mads Tofte, Combining region inference and garbage collection, ACM SIGPLAN Notices, v.37 n.5, May 2002
	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
	Jeff Bogda , Urs Hölzle, Removing unnecessary synchronization in Java, ACM SIGPLAN Notices, v.34 n.10, p.35-46, Oct. 1999
	Atsushi Igarashi , Naoki Kobayashi, Resource usage analysis, ACM SIGPLAN Notices, v.37 n.1, p.331-342, Jan. 2002
	Michael G. Burke , Jong-Deok Choi , Stephen Fink , David Grove , Michael Hind , Vivek Sarkar , Mauricio J. Serrano , V. C. Sreedhar , Harini Srinivasan , John Whaley, The Jalapeño dynamic optimizing compiler for Java, Proceedings of the ACM 1999 conference on Java Grande, p.129-141, June 12-14, 1999, San Francisco, California, United States
	Julian Dolby , Andrew Chien, An automatic object inlining optimization and its evaluation, ACM SIGPLAN Notices, v.35 n.5, p.345-357, May 2000
	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
	Yanhong A. Liu , Scott D. Stoller, Eliminating dead code on recursive data, Science of Computer Programming, v.47 n.2-3, p.221-242, May 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
	Bruno Blanchet, Escape analysis for object-oriented languages: application to Java, ACM SIGPLAN Notices, v.34 n.10, p.20-34, Oct. 1999
	John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, ACM SIGPLAN Notices, v.34 n.10, p.187-206, Oct. 1999
	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
	Oukseh Lee , Kwangkeun Yi, Experiments on the effectiveness of an automatic insertion of memory reuses into ML-like programs, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	Mads Tofte , Lars Birkedal , Martin Elsman , Niels Hallenberg, A Retrospective on Region-Based Memory Management, Higher-Order and Symbolic Computation, v.17 n.3, p.245-265, September 2004
	Atsushi Igarashi , Naoki Kobayashi, Resource usage analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.2, p.264-313, March 2005
	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
	Oukseh Lee , Hongseok Yang , Kwangkeun Yi, Static insertion of safe and effective memory reuse commands into ML-like programs, Science of Computer Programming, v.58 n.1-2, p.141-178, October 2005
	Richard Carlsson , Konstantinos Sagonas , Jesper Wilhelmsson, Message analysis for concurrent programs using message passing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.4, p.715-746, July 2006
	Patricia M. Hill , Fausto Spoto, Deriving escape analysis by abstract interpretation, Higher-Order and Symbolic Computation, v.19 n.4, p.415-463, December 2006
	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
	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