More Web Proxy on the site http://driver.im/

Article

Run-Time Support for Optimizations Based on Escape Analysis

Authors:

Thomas Kotzmann,

Hanspeter MossenbockAuthors Info & Claims

CGO '07: Proceedings of the International Symposium on Code Generation and Optimization

Pages 49 - 60

https://doi.org/10.1109/CGO.2007.34

Published: 11 March 2007 Publication History

Abstract

The JavaTM programming language does not allow the programmer to influence memory management. An object is usually allocated on the heap and deallocated by the garbage collector when it is not referenced any longer. Under certain conditions, the virtual machine can allocate objects on the stack or eliminate their allocation via scalar replacement. However, even if the dynamic compiler guarantees that the conditions are fulfilled, the optimizations require support by the run-time environment. We implemented a new escape analysis algorithm for Sun Microsystems' Java HotSpotTM VM. The results are used to replace objects with scalar variables, to allocate objects on the stack, and to remove synchronization. This paper deals with the representation of optimized objects in the debugging information and with reallocation and garbage collection support for a safe execution of optimized methods. Assignments to fields of parameters that can refer to both stack and heap objects are associated with an extended write barrier which skips card marking for stack objects. The traversal of objects during garbage collection uses a wrapper that abstracts from stack objects and presents their pointer fields as root pointers to the garbage collector. When a previously compiled and currently executing method must be continued in the interpreter because dynamic class loading invalidates the machine code, execution is suspended and compiler optimizations are undone. Scalar-replaced objects are reallocated on the heap lazily when control returns to the invalidated method, whereas stack-allocated objects must be reallocated immediately before program execution resumes. After reallocation, objects for which synchronization was removed are relocked.

References

[1]

{1} O. Agesen and D. Detlefs. Mixed-mode bytecode execution. Technical Report TR-2000-87, Sun Microsystems Laboratories, June 2000.

Digital Library

[2]

{2} O. Agesen, D. Detlefs, A. Garthwaite, R. Knippel, Y. S. Ramakrishna, and D. White. An efficient meta-lock for implementing ubiquitous synchronization. In Proceedings of the ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 207- 222, Denver, Nov. 1999.

Digital Library

[3]

{3} D. F. Bacon, R. Konuru, C. Murthy, and M. Serrano. Thin locks: Featherweight synchronization for Java. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 258- 268, Montreal, June 1998.

Digital Library

[4]

{4} B. Blanchet. Escape analysis for Java¿: Theory and practice. ACM Transactions on Programming Languages and Systems, 25(6):713-775, Nov. 2003.

Digital Library

[5]

{5} J. Bogda and U. Hölzle. Removing unnecessary synchronization in Java. In Proceedings of the ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 35-46, Denver, Nov. 1999.

Digital Library

[6]

{6} J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P. Midkiff. Stack allocation and synchronization optimizations for Java using escape analysis. ACM Transactions on Programming Languages and Systems, 25(6):876-910, Nov. 2003.

Digital Library

[7]

{7} J. Dean, D. Grove, and C. Chambers. Optimization of object-oriented programs using static class hierarchy analysis. In Proceedings of the European Conference on Object-Oriented Programming, pages 77-101, Århus, Aug. 1995.

Digital Library

[8]

{8} D. Detlefs and O. Agesen. Inlining of virtual methods. In Proceedings of the European Conference on Object-Oriented Programming, pages 258-278, Lisbon, June 1999.

Digital Library

[9]

{9} D. Gay and B. Steensgaard. Fast escape analysis and stack allocation for object-based programs. In Proceedings of the International Conference on Compiler Construction, pages 82-93, Berlin, Mar. 2000.

Digital Library

[10]

{10} U. Hölzle, C. Chambers, and D. Ungar. Debugging optimized code with dynamic deoptimization. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 32-43, San Francisco, June 1992.

Digital Library

[11]

{11} A. L. Hosking and R. L. Hudson. Remembered sets can also play cards. In Proceedings of the ACM OOPSLA Workshop on Memory Management and Garbage Collection, Washington, D. C., Oct. 1993.

[12]

{12} Intel Corporation. IA-32 Intel Architecture Software Developer's Manual, Volume 2A & 2B: Instruction Set Reference, 2006. Order numbers 253666-018 and 253667-018.

[13]

{13} K. Ishizaki, M. Kawahito, T. Yasue, H. Komatsu, and T. Nakatani. A study of devirtualization techniques for a Java¿ just-in-time compiler. In Proceedings of the ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 294- 310, Minneapolis, Oct. 2000.

Digital Library

[14]

{14} T. Kotzmann. Escape Analysis in the Context of Dynamic Compilation and Deoptimization. PhD thesis, Institute for System Software, Johannes Kepler University Linz, Oct. 2005.

[15]

{15} T. Kotzmann and H. Mössenböck. Escape analysis in the context of dynamic compilation and deoptimization. In Proceedings of the International Conference on Virtual Execution Environments, pages 111-120, Chicago, June 2005.

Digital Library

[16]

{16} E. Ruf. Effective synchronization removal for Java. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 208- 218, Vancouver, June 2000.

Digital Library

[17]

{17} K. Russell and D. Detlefs. Eliminating synchronization-related atomic operations with biased locking and bulk rebiasing. In Proceedings of the ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 263-272, Portland, Oct. 2006.

Digital Library

[18]

{18} Standard Performance Evaluation Corporation. The SPEC JBB2005 Benchmark. http://www.spec.org/jbb2005/.

[19]

{19} Standard Performance Evaluation Corporation. The SPEC JVM98 Benchmarks. http://www.spec.org/jvm98/.

[20]

{20} T. Suganuma, T. Yasue, and T. Nakatani. A region-based compilation technique for a Java just-in-time compiler. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 312- 323, San Diego, June 2003.

Digital Library

[21]

{21} Sun Microsystems, Inc. Java Platform, Standard Edition 6 Source Snapshot Releases. http://download.java.net/jdk6/.

[22]

{22} R. Veldema, C. J. H. Jacobs, R. F. H. Hofman, and H. E. Bal. Object combining: A new aggressive optimization for object intensive programs. In Proceedings of the Joint ACM-ISCOPE Conference on Java Grande, pages 165-174, Seattle, Nov. 2002.

Digital Library

[23]

{23} J. Whaley and M. Rinard. Compositional pointer and escape analysis for Java programs. In Proceedings of the ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 187-206, Denver, Nov. 1999.

Digital Library

Cited By

Ding BLi QZhang YTang FChen J(2024)MEA2: A Lightweight Field-Sensitive Escape Analysis with Points-to Calculation for GolangProceedings of the ACM on Programming Languages10.1145/36897598:OOPSLA2(1362-1389)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689759
Zhang YDhawal ONandivada VChiba SUgawa TLaemmel RPereira JMosses P(2024)Reducing Write Barrier Overheads for Orthogonal PersistenceProceedings of the 17th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3687997.3695646(210-223)Online publication date: 17-Oct-2024
https://dl.acm.org/doi/10.1145/3687997.3695646
Anand AAdithya SRustagi SSeth PSundaresan VMaier DNandivada VThakur M(2024)Optimistic Stack Allocation and Dynamic Heapification for Managed RuntimesProceedings of the ACM on Programming Languages10.1145/36563898:PLDI(296-319)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656389
Show More Cited By

Index Terms

Run-Time Support for Optimizations Based on Escape Analysis
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Runtime environments
    2. General programming languages
      1. Language types
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

Escape analysis for Java^TM: Theory and practice

Escape analysis is a static analysis that determines whether the lifetime of data may exceed its static scope.This paper first presents the design and correctness proof of an escape analysis for Java^TM. This analysis is interprocedural, context ...
Escape analysis on lists
PLDI '92: Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation

Higher order functional programs constantly allocate objects dynamically. These objects are typically cons cells, closures, and records and are generally allocated in the heap and reclaimed later by some garbage collection process. This paper describes ...
Escape analysis on lists

Higher order functional programs constantly allocate objects dynamically. These objects are typically cons cells, closures, and records and are generally allocated in the heap and reclaimed later by some garbage collection process. This paper describes ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CGO '07: Proceedings of the International Symposium on Code Generation and Optimization

March 2007

346 pages

ISBN:0769527647

Sponsors

Publisher

IEEE Computer Society

United States

Publication History

Published: 11 March 2007

Check for updates

Qualifiers

Article

Conference

CGO07

Sponsor:

CGO07: 5th Annual IEEE / ACM International Symposium on Code Generation and Optimization

March 11 - 14, 2007

Acceptance Rates

CGO '07 Paper Acceptance Rate 27 of 84 submissions, 32%;

Overall Acceptance Rate 312 of 1,061 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
307
Total Downloads

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

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ding BLi QZhang YTang FChen J(2024)MEA2: A Lightweight Field-Sensitive Escape Analysis with Points-to Calculation for GolangProceedings of the ACM on Programming Languages10.1145/36897598:OOPSLA2(1362-1389)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689759
Zhang YDhawal ONandivada VChiba SUgawa TLaemmel RPereira JMosses P(2024)Reducing Write Barrier Overheads for Orthogonal PersistenceProceedings of the 17th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3687997.3695646(210-223)Online publication date: 17-Oct-2024
https://dl.acm.org/doi/10.1145/3687997.3695646
Anand AAdithya SRustagi SSeth PSundaresan VMaier DNandivada VThakur M(2024)Optimistic Stack Allocation and Dynamic Heapification for Managed RuntimesProceedings of the ACM on Programming Languages10.1145/36563898:PLDI(296-319)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656389
Vukasovic MProkopec A(2023)Exploiting Partially Context-sensitive Profiles to Improve Performance of Hot CodeACM Transactions on Programming Languages and Systems10.1145/361293745:4(1-64)Online publication date: 13-Sep-2023
https://dl.acm.org/doi/10.1145/3612937
Weingarten MTheodoridis TProkopec AKotselidis CProkopec A(2022)Inlining-Benefit Prediction with Interprocedural Partial Escape AnalysisProceedings of the 14th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages10.1145/3563838.3567677(13-24)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3563838.3567677
Würthinger TWimmer CHumer CWöß AStadler LSeaton CDuboscq GSimon DGrimmer M(2017)Practical partial evaluation for high-performance dynamic language runtimesACM SIGPLAN Notices10.1145/3140587.306238152:6(662-676)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3140587.3062381
Würthinger TWimmer CHumer CWöß AStadler LSeaton CDuboscq GSimon DGrimmer MCohen AVechev M(2017)Practical partial evaluation for high-performance dynamic language runtimesProceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3062341.3062381(662-676)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3062341.3062381
Wimmer CJovanovic VEckstein EWürthinger TWu PHack S(2017)One compiler: deoptimization to optimized codeProceedings of the 26th International Conference on Compiler Construction10.1145/3033019.3033025(55-64)Online publication date: 5-Feb-2017
https://dl.acm.org/doi/10.1145/3033019.3033025
Zheng YBulej LBinder W(2015)Accurate profiling in the presence of dynamic compilationACM SIGPLAN Notices10.1145/2858965.281428150:10(433-450)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2858965.2814281
Zheng YBulej LBinder WAldrich JEugster P(2015)Accurate profiling in the presence of dynamic compilationProceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2814270.2814281(433-450)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2814270.2814281
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents