Article

Fast Escape Analysis and Stack Allocation for Object-Based Programs

Authors:

Bjarne SteensgaardAuthors Info & Claims

CC '00: Proceedings of the 9th International Conference on Compiler Construction

Pages 82 - 93

Published: 25 March 2000 Publication History

Abstract

A fast and scalable interprocedural escape analysis algorithm is presented.T he analysis computes a description of a subset of created objects whose lifetime is bounded by the lifetime of a runtime stack frame.T he analysis results can be used for many purposes, including stack allocation of objects, thread synchronization elimination, dead-store removal, code motion, and iterator reduction. A method to use the analysis results for transforming a program to allocate some objects on the runtime stack is also presented.F or non-trivial programs, typically 10%-20% of all allocated objects are placed on the runtime stack after the transformation.

References

[1]

Jeffrey M. Barth. Shifting garbage collection overhead to compile time. Communications of the ACM, 20(7):513-518, July 1977.

[2]

Jeff Bogda and Urs Hölzle. Removing Unnecessary Synchronization in Java. In Proceedings of the 1999 ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages & Applications (OOPSLA' 99), pages 35-46. ACM Press, October 1999.

[3]

Bruno Blanchet. Escape Analysis for Object-Oriented Languages: Application to Java. In Proceedings of the 1999 ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages & Applications (OOPSLA' 99), pages 20-34. ACM Press, October 1999.

[4]

Bruno Blanchet. Escape analysis: Correctness proof, implementation and experimental results. In Conference Record of POPL '98: The 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 25-37, San Diego, California, January 98.

[5]

E. Barendsen and S. Smetsers. Conventional and uniqueness typing in graph rewrite systems. In Rudrapatna K. Shyamasundar, editor, Proceedings of Foundations of Software Technology and Theoretical Computer Science, volume 761 of LNCS, pages 41-51, Bombay, India, December 1993. Springer-Verlag.

[6]

David F. Bacon and Peter F. Sweeney. Fast static analysis of C++ virtual function calls.In Proceedings of the Conference on Object-Oriented Programming Systems, Languages, and Applications, volume 31, 10 of ACM SIGPLAN Notices, pages 324-341, New York, October6-10 1996. ACM Press.

[7]

Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4):451-490, October 1991.

[8]

Jong-Deok Choi, M. Gupta, Mauricio Serrano, Vugranam C Shreedhar, and Sam Midkiff. Escape Analysis for Java. In Proceedings of the 1999 ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages & Applications (OOPSLA'99), pages 1-19. ACM Press, October 1999.

[9]

David R. Chase, Mark Wegman, and F. Kenneth Zadeck. Analysis of pointers and structures. ACM SIGPLAN Notices, 25(6):296-310, June 1990.

[10]

Julian Dolby and Andrew A. Chien. An Evaluation of Automatic Object Inline Allocation Techniques. In Proceedings of the 1998 ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages & Applications (OOPSLA'98), pages 1-20. ACM Press, October 1998.

[11]

Alan Deutsch. On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications. In ACM-SIGPLAN ACM-SIGACT, editor, Conference Record of the 17th Annual ACM Symposium on Principles of Programming Languages (POPL '90), pages 157- 168, San Francisco, CA, USA, January 1990. ACM Press.

[12]

Alain Deutsch.O n the complexity of escape analysis. In Conference Record of POPL '97: The 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 358-371, Paris, France, January 97.

[13]

Robert Fitzgerald, Todd B. Knoblock, Erik Ruf, Bjarne Steensgaard, and David Tarditi. Marmot: An optimizing compiler for Java. Technical Report MSR-TR-99-33, Microsoft Research, June 1999. Accepted for publication in Software -- Practice & Experience.

[14]

James Hicks. Experiences with compiler-directed storage reclamation. In R. John M. Hughes, editor, Record of the 1993 Conference on Functional Programming and Computer Architecture, volume 523 of Lecture Notes in Computer Science, Copenhagen, June 1993. Springer-Verlag.

[15]

Simon Hughes. Compile-time garbage collection for higher-order functional languages. Journal of Logic and Computation, 2(4):483-509, August 1992.

[16]

Katsuro Inoue, Hiroyuki Seki, and Hikaru Yagi. Analysis of functional programs to detect run-time garbage cells. ACM Transactions on Programming Languages and Systems, 10(4):555-578, October 1988.

[17]

S.B . Jones and D. Le MÉtayer. Compile-time garbage collection by sharing analysis. In Proceedings of the Conference on Functional Programming Languages and Computer Architecture '89, Imperial College, London, pages 54-74, New York, NY, 1989. ACM.

[18]

Neil D. Jones and Steven S. Muchnick. Flow analysis and optimization of Lisp-like structures. In Steven S. Muchnick and Neil D. Jones, editors, Program Flow Analysis: Theory and Applications, pages 102-131. Englewood Cliffs, N.J.: Prentice-Hall, 1981.

[19]

Thomas P. Jensen and Torben Mogensen. A backwards analysis for compile-time garbage collection. In Neil D. Jones, editor, ESOP'90 3rd European Symposium on Programming, Copenhagen, Denmark, May 1990. (Lecture Notes in Computer Science, vol. 432), pages 227-239. Springer-Verlag, 1990.

[20]

Tim Lindholm and Frank Yellin. The Java Virtual Machine Specification. Addison-Wesley, second edition edition, 1999.

[21]

Markus Mohnen. Efficient compile-time garbage collection for arbitrary data structures. Technical Report 95-08, RWTH Aachen, Department of Computer Science, 1995.

[22]

Young Gil Park and Benjamin Goldberg. Escape analysis on lists. In Proceedings of the ACM SIGPLAN'92 Conference on Programming Language Design and Implementation (PLDI), pages 116-127, 1992.

[23]

Jakob Rehof and Torben Æ. Mogensen. Tractable constraints in finite semilattices. Science of Computer Programming, 35(2-3):191-221, 1998.

[24]

J.T.S chwartz. Optimization of very high level languages - I.V alue transmission and its corollaries. Computer Languages, 1(2):161-194, 1975.

[25]

Manuel Serrano and Marc Feeley. Storage use analysis and its applications. In Proceedings of the 1st International Conference on Functional Programming, June 1996.

[26]

Bjarne Steensgaard. Points-to analysis in almost linear time. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 32-41, St. Petersburg, Florida, January 1996.

[27]

Jan Vitek, R. Nigel Horspool, and James Uhl. Compile-time analysis of object-oriented programs. In Proceedings of the 4th Int. Conf. on Compiler Construction, CC'92, Paderborn, Germany, 1992. Springer-Verlag.

[28]

John Whaley and Martin Rinard. Compositional Pointer and Escape Analysis for Java Programs. In Proceedings of the 1999 ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages & Applications (OOPSLA'99), pages 187-206. ACM Press, October 1999.

Cited By

Helm DKübler FEichberg MReif MMezini MHuchard MKästner CFraser G(2018)A unified lattice model and framework for purity analysesProceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering10.1145/3238147.3238226(340-350)Online publication date: 3-Sep-2018
https://dl.acm.org/doi/10.1145/3238147.3238226
Bruno ROliveira LFerreira P(2017)NG2C: pretenuring garbage collection with dynamic generations for HotSpot big data applicationsACM SIGPLAN Notices10.1145/3156685.309227252:9(2-13)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3156685.3092272
Bruno RFerreira PJayaram KGandhi AKemme BPietzuch P(2017)POLM2Proceedings of the 18th ACM/IFIP/USENIX Middleware Conference10.1145/3135974.3135986(147-160)Online publication date: 11-Dec-2017
https://dl.acm.org/doi/10.1145/3135974.3135986
Show More Cited By

Recommendations

Side-effect analysis with fast escape filter
SOAP '12: Proceedings of the ACM SIGPLAN International Workshop on State of the Art in Java Program analysis

Side-effect analysis is a fundamental static analysis used to determine the memory locations modified or used by each program entity. For the programs with pointers, the analysis can be very imprecise. To improve the precision of side-effect analysis, ...
Compositional pointer and escape analysis for Java programs

This paper presents a combined pointer and escape analysis algorithm for Java programs. The algorithm is based on the abstraction of points-to escape graphs, which characterize how local variables and fields in objects refer to other objects. Each ...
Compositional pointer and escape analysis for Java programs
OOPSLA '99: Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

This paper presents a combined pointer and escape analysis algorithm for Java programs. The algorithm is based on the abstraction of points-to escape graphs, which characterize how local variables and fields in objects refer to other objects. Each ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CC '00: Proceedings of the 9th International Conference on Compiler Construction

March 2000

294 pages

ISBN:354067263X

Editor:
David A. Watt

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 25 March 2000

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Helm DKübler FEichberg MReif MMezini MHuchard MKästner CFraser G(2018)A unified lattice model and framework for purity analysesProceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering10.1145/3238147.3238226(340-350)Online publication date: 3-Sep-2018
https://dl.acm.org/doi/10.1145/3238147.3238226
Bruno ROliveira LFerreira P(2017)NG2C: pretenuring garbage collection with dynamic generations for HotSpot big data applicationsACM SIGPLAN Notices10.1145/3156685.309227252:9(2-13)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3156685.3092272
Bruno RFerreira PJayaram KGandhi AKemme BPietzuch P(2017)POLM2Proceedings of the 18th ACM/IFIP/USENIX Middleware Conference10.1145/3135974.3135986(147-160)Online publication date: 11-Dec-2017
https://dl.acm.org/doi/10.1145/3135974.3135986
Rhodes DFlanagan CFreund S(2017)Correctness of Partial Escape Analysis for Multithreading OptimizationProceedings of the 19th Workshop on Formal Techniques for Java-like Programs10.1145/3103111.3104039(1-6)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3103111.3104039
Bruno ROliveira LFerreira PKirsch CTitzer B(2017)NG2C: pretenuring garbage collection with dynamic generations for HotSpot big data applicationsProceedings of the 2017 ACM SIGPLAN International Symposium on Memory Management10.1145/3092255.3092272(2-13)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3092255.3092272
Yan DXu GYang SRountev A(2014)LeakCheckerProceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization10.1145/2581122.2544151(87-97)Online publication date: 15-Feb-2014
https://dl.acm.org/doi/10.1145/2581122.2544151
Yan DXu GYang SRountev A(2014)LeakCheckerProceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization10.1145/2544137.2544151(87-97)Online publication date: 15-Feb-2014
https://dl.acm.org/doi/10.1145/2544137.2544151
Xu G(2013)ResurrectorACM SIGPLAN Notices10.1145/2544173.250951248:10(111-130)Online publication date: 29-Oct-2013
https://dl.acm.org/doi/10.1145/2544173.2509512
Xu GHosking AEugster PLopes C(2013)ResurrectorProceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications10.1145/2509136.2509512(111-130)Online publication date: 29-Oct-2013
https://dl.acm.org/doi/10.1145/2509136.2509512
Xu G(2012)Finding reusable data structuresACM SIGPLAN Notices10.1145/2398857.238469047:10(1017-1034)Online publication date: 19-Oct-2012
https://dl.acm.org/doi/10.1145/2398857.2384690
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents