Lifetime analysis of dynamically allocated objects

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Lifetime analysis of dynamically allocated objects

Full text

Pdf (1.08 MB)

Source

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

San Diego, California, United States

Pages: 285 - 293

Year of Publication: 1988

ISBN:0-89791-252-7

Authors

C. Ruggieri	Department of Computer Sciences, Purdue University, West Lafayette, IN
T. P. Murtagh	Department of Computer Science, Williams College, Williamstown, MA

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 26, Citation Count: 45

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

ABSTRACT

The choice of binding time disciplines has major consequences for both the run-time efficiency of programs and the convenience of the language expressing algorithms. Late storage binding time, dynamic allocation, provides the flexibility necessary to implement the complex data structures common in today's object oriented style of programming. In this paper we show that compile-time lifetime analysis can be applied to programs written in languages with static type systems and dynamically allocated objects, to provide earlier storage binding time for objects, while maintaining all the advantages of dynamic allocation.

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.

	All74	F. Allen. Interprocedural data flow analysis. In J.L.Rosenfield, editor, Informatiou Processing 74, pages 398-408, August 1974.
	Ban79	John P. Banning, An efficient way to find the side effects of procedure calls and the aliases of variables, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.29-41, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567756]
	Bar78	Jeffrey M. Barth, A practical interprocedural data flow analysis algorithm, Communications of the ACM, v.21 n.9, p.724-736, Sept. 1978 [doi>10.1145/359588.359596]
	CC77	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]
	Coo83	Keith Daniel Cooper, Interprocedural data flow analysis in a programming environment, 1983
	Cou86	Deborah S. Coutant, Retargetable high-level alias analysis, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-118, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512654]
	Hud86	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]
	JM76	Neil D. Jones , Steven S. Muchnick, Binding time optimization in programming languages: Some thoughts toward the design of an ideal language, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.77-94, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811542]
	Kil73	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]
	KU77	J.B. Kam and J.D. Ullman. Monotone data flow analysis frameworks. A cta Informatica, 305- 317, 1977.
	LH83	Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
	LSAS77	Barbara Liskov , Alan Snyder , Russell Atkinson , Craig Schaffert, Abstraction mechanisms in CLU, Communications of the ACM, v.20 n.8, p.564-576, Aug. 1977 [doi>10.1145/359763.359789]
	Mye81	Eugene M. Myers, A precise inter-procedural data flow algorithm, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.219-230, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567556]
	Ros79	Barry K. Rosen, Data Flow Analysis for Procedural Languages, Journal of the ACM (JACM), v.26 n.2, p.322-344, April 1979 [doi>10.1145/322123.322135]
	Rug87	Cristina Ruggieri , Thomas Murtagh, Dynamic memory allocation techniques based on the lifetime of objects, 1987
	Tar74	R. Tarjan. Finding dominators in directed graphs. SIAM 7ournal on Computing, 3(1):62- 89, March 1974.
	Wei80	William E. Weihl, Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.83-94, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567455]

CITED BY 45

	J. R. Larus , P. N. Hilfinger, Detecting conflicts between structure accesses, ACM SIGPLAN Notices, v.23 n.7, p.24-31, July 1988
	S. Horwitz , P. Pfeiffer , T. Reps, Dependence analysis for pointer variables, ACM SIGPLAN Notices, v.24 n.7, p.28-40, July 1989
	Jeff Bogda , Urs Hölzle, Removing unnecessary synchronization in Java, ACM SIGPLAN Notices, v.34 n.10, p.35-46, Oct. 1999
	Joseph Hummel , Laurie J. Hendren , Alexandru Nicolau, Abstract description of pointer data structures: an approach for improving the analysis and optimization of imperative programs, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.243-260, Sept. 1992
	Joseph Hummel , Laurie J. Hendren , Alexandru Nicolau, A general data dependence test for dynamic, pointer-based data structures, ACM SIGPLAN Notices, v.29 n.6, p.218-229, June 1994
	D. R. Chase, Safety consideration for storage allocation optimizations, ACM SIGPLAN Notices, v.23 n.7, p.1-10, July 1988
	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
	Dante J. Cannarozzi , Michael P. Plezbert , Ron K. Cytron, Contaminated garbage collection, ACM SIGPLAN Notices, v.35 n.5, p.264-273, May 2000
	Young Gil Park , Benjamin Goldberg, Escape analysis on lists, ACM SIGPLAN Notices, v.27 n.7, p.116-127, July 1992
	Michael Hind, Pointer analysis: haven't we solved this problem yet?, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.54-61, June 2001, Snowbird, Utah, United States
	Barton P. Miller , Jong-Deok Choi, A mechanism for efficient debugging of parallel programs, ACM SIGPLAN Notices, v.24 n.1, p.141-150, Jan. 1989
	Michael Hind , Michael Burke , Paul Carini , Jong-Deok Choi, Interprocedural pointer alias analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.848-894, July 1999
	Ravi Sharma , Mary Lou Soffa, Parallel generational garbage collection, ACM SIGPLAN Notices, v.26 n.11, p.16-32, Nov. 1991
	Henry G. Baker, Unify and conquer, Proceedings of the 1990 ACM conference on LISP and functional programming, p.218-226, June 27-29, 1990, Nice, France
	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
	Jong-Deok Choi , Michael Burke , Paul Carini, Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.232-245, March 1993, Charleston, South Carolina, United States
	Barbara G. Ryder , William A. Landi , Philip A. Stocks , Sean Zhang , Rita Altucher, A schema for interprocedural modification side-effect analysis with pointer aliasing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.2, p.105-186, March 2001
	Alexander Aiken , Manuel Fähndrich , Raph Levien, Better static memory management: improving region-based analysis of higher-order languages, ACM SIGPLAN Notices, v.30 n.6, p.174-185, June 1995
	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
	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
	Laurie J. Hendren , Alexandru Nicolau, Intererence analysis tools for parallelizing programs with recursive data structures, Proceedings of the 3rd international conference on Supercomputing, p.205-214, June 05-09, 1989, Crete, Greece
	Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991
	Rita Z. Altucher , William Landi, An extended form of must alias analysis for dynamic allocation, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.74-84, January 23-25, 1995, San Francisco, California, United States
	William Landi , Barbara G. Ryder , Sean Zhang, Interprocedural modification side effect analysis with pointer aliasing, ACM SIGPLAN Notices, v.28 n.6, p.56-67, June 1993
	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
	Alain Deutsch, Interprocedural may-alias analysis for pointers: beyond k-limiting, ACM SIGPLAN Notices, v.29 n.6, p.230-241, June 1994
	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
	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
	H. D. Pande , W. A. Landi , B. G. Ryder, Interprocedural Def-Use Associations for C Systems with Single Level Pointers, IEEE Transactions on Software Engineering, v.20 n.5, p.385-403, May 1994
	L. J. Hendren , A. Nicolau, Parallelizing Programs with Recursive Data Structures, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.35-47, January 1990
	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
	S. J. Eggers , R. H. Katz, The effect of sharing on the cache and bus performance of parallel programs, ACM SIGARCH Computer Architecture News, v.17 n.2, p.257-270, April 1989
	B. P. Miller , Jong-Deok Choi, A mechanism for efficient debugging of parallel programs, ACM SIGPLAN Notices, v.23 n.7, p.135-144, July 1988
	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
	Manuel Serrano , Marc Feeley, Storage use analysis and its applications, ACM SIGPLAN Notices, v.31 n.6, p.50-61, June 15, 1996
	Bruno Blanchet, Escape analysis for object-oriented languages: application to Java, ACM SIGPLAN Notices, v.34 n.10, p.20-34, Oct. 1999
	Suresh Jagannathan , Peter Thiemann , Stephen Weeks , Andrew Wright, Single and loving it: must-alias analysis for higher-order languages, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.329-341, January 19-21, 1998, San Diego, California, United States
	David Chase , Mark Wegman , F. Ken Zadeck, Analysis of pointers and structures, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Ramkrishna Chatterjee , Barbara G. Ryder , William A. Landi, Complexity of Points-To Analysis of Java in the Presence of Exceptions, IEEE Transactions on Software Engineering, v.27 n.6, p.481-512, June 2001
	Henry G. Baker, CONS should not CONS its arguments, or, a lazy alloc is a smart alloc, ACM SIGPLAN Notices, v.27 n.3, p.24-34, March 1992
	Erik Ruf, Context-insensitive alias analysis reconsidered, ACM SIGPLAN Notices, v.30 n.6, p.13-22, June 1995
	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
	Henry G. Baker, Lively linear Lisp: “look ma, no garbage!”, ACM SIGPLAN Notices, v.27 n.8, p.89-98, Aug. 1992
	Nandakumar Sankaran, A bibliography on garbage collection and related topics, ACM SIGPLAN Notices, v.29 n.9, p.149-158, Sept. 1994
	Michal Wegiel , Chandra Krintz, Dynamic prediction of collection yield for managed runtimes, ACM SIGPLAN Notices, v.44 n.3, March 2009