On the complexity of escape analysis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity of escape analysis

Full text

Pdf (1.23 MB)

Source

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

Paris, France

Pages: 358 - 371

Year of Publication: 1997

ISBN:0-89791-853-3

Author

Alain Deutsch

INRIA Recquencourt, F-78153 Le Chesnay Cedex, France

Sponsors

L'Ecole des Mines de Paris : L'Ecole des Mines de Paris
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Ctr Natl de la Recherche Sci :
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 35, Citation Count: 14

Additional Information:

references cited by index terms

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/263699.263750 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	A. BANERJEE AND D. SCHMIDT, Stackability in the simply-typed call-by-value lambda calculus, in Static Analysis, First Intl. Static Analysis Symposium, SAS'94, vol. 864 of Lecture Notes on Computer Science, Springer Verlag, Sept. 1994, pp. 131-146.
	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	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
	5	David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, ACM SIGPLAN Notices, v.25 n.6, p.296-310, Jun. 1990
	6	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]
	7	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]
	8	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]
	9	Alain Deutsch, Semantic models and abstract interpretation techniques for inductive data structures and pointers, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.226-229, June 21-23, 1995, La Jolla, California, United States [doi>10.1145/215465.215594]
	10	R. FARROW, E#icient on.line evaluation of functions defined on paths in trees, Tech. Rep. 476-093-17, Rice Univ., Houston,TX, Feb. 1977.
	11	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
	12	W. HARRISON, The interprocedura\| analitsis and automatic parallelisation of Scheme programs, Lisp and Symbolic Computation, 2 (1989), pp. 176-396.
	13	Fritz Henglein, Efficient type inference for higher-order binding-time analysis, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.448-472, June 1991, Cambridge, Massachusetts, United States
	14	Paul Hudak , Jonathan Young, Higher-order strictness analysis in untyped lambda calculus, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-109, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512653]
	15	R. HUGHI#S, Backwards analysis of functional programs, in Proe. Workshop on Partial Evaluation and Mixed Computation, D. Bjorner, A. Ershov, and N. Jones, eds., North-Holland, Oct. 1987, pp. 155-169.
	16	S. HUGHES, Compile-time garbage collection for higher-order functional languages, J. of Logic and Computation, 2 (1992), pp. 483-509.
	17	Thomas Johnsson, Lambda lifting: transforming programs to recursive equations, Proc. of a conference on Functional programming languages and computer architecture, p.190-203, January 1985, Nancy, France
	18	Neil D. Jones, Flow Analysis of Lambda Expressions (Preliminary Version), Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.114-128, July 13-17, 1981
	19	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]
	20	Simon B. Jones , Daniel Le Métayer, Compile-time garbage collection by sharing analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.54-74, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99375]
	21	John B. Kam , Jeffrey D. Ullman, Global Data Flow Analysis and Iterative Algorithms, Journal of the ACM (JACM), v.23 n.1, p.158-171, Jan. 1976 [doi>10.1145/321921.321938]
	22	Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
	23	D. KNUTH, A generalization of Dijkstra's algorithm, Information Processing Letters, 6 (1977), pp. 1-5.
	24	William Landi, Undecidability of static analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.4, p.323-337, Dec. 1992 [doi>10.1145/161494.161501]
	25	R. MILNER, A theory of type po\|ymorphism in programming, J. Comput. System Sci., 17 (1978), pp. 348-375.
	26	M. MOHNeN, Efficient compile-time garbage collection for arbitrarit data structures, Tech. Rep. 95-08, RWTH Aachen, Department of Computer Science, 1995.
	27	S. MUCHNICK AND N. JONES, Complezity of flow analysis, inductive assertion sitnthesis and a language due to Dijkstra, in Program Flow Analysis: Theory and Applications, New Jersey, 1981, Prentice-Hall, pp. 380-393.
	28	Alan Mycroft, The Theory and Practice of Transforming Call-by-need into Call-by-value, Proceedings of the Fourth 'Colloque International sur la Programmation' on International Symposium on Programming, p.269-281, April 22-24, 1980
	29	Hanne Riis Nielson , Flemming Nielson, Bounded fixed point iteration, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.71-82, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143182]
	30	Young Gil Park , Benjamin Goldberg, Escape analysis on lists, ACM SIGPLAN Notices, v.27 n.7, p.116-127, July 1992
	31	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
	32	Peter Sestoft, Replacing function parameters by global variables, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.39-53, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99374]
	33	Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
	34	Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
	35	M. Takeichi, Lambda-hoisting: a transformation technique for fully lazy evaluation of functional programs, New Generation Computing, v.5 n.4, p.377-391, 1988 [doi>10.1007/BF03037416]
	36	J. TALPIN AND P. JOUVELOT, The type and effect discipline, in Seventh Annual IEEE Symp. on Logic in Computer Science, 1992.
	37	Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
	38	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]

CITED BY 14

	Peng Wu , Sam Midkiff , José Moreira , Manish Gupta, Efficient support for complex numbers in Java, Proceedings of the ACM 1999 conference on Java Grande, p.109-118, June 12-14, 1999, San Francisco, California, United States
	John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, ACM SIGPLAN Notices, v.34 n.10, p.187-206, Oct. 1999
	Roberto Giacobazzi , Francesco Ranzato , Francesca Scozzari, Making abstract interpretations complete, Journal of the ACM (JACM), v.47 n.2, p.361-416, March 2000
	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
	Bruno Blanchet, Escape analysis for object-oriented languages: application to Java, ACM SIGPLAN Notices, v.34 n.10, p.20-34, Oct. 1999
	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
	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
	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
	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
	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
	Wei-Ngan Chin , Florin Craciun , Shengchao Qin , Martin Rinard, Region inference for an object-oriented language, ACM SIGPLAN Notices, v.39 n.6, May 2004
	Misha Zitser , Richard Lippmann , Tim Leek, Testing static analysis tools using exploitable buffer overflows from open source code, ACM SIGSOFT Software Engineering Notes, v.29 n.6, November 2004
	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