Escape analysis in the context of dynamic compilation and deoptimization

ABSTRACT

In object-oriented programming languages, an object is said to escape the method or thread in which it was created if it can also be accessed by other methods or threads. Knowing which objects do not escape allows a compiler to perform aggressive optimizations.This paper presents a new intraprocedural and interprocedural algorithm for escape analysis in the context of dynamic compilation where the compiler has to cope with dynamic class loading and deoptimization. It was implemented for Sun Microsystems' Java HotSpot™ client compiler and operates on an intermediate representation in SSA form. We introduce equi-escape sets for the efficient propagation of escape information between related objects. The analysis is used for scalar replacement of fields and synchronization removal, as well as for stack allocation of objects and fixed-sized arrays. The results of the interprocedural analysis support the compiler in inlining decisions and allow actual parameters to be allocated on the caller stack.Under certain circumstances, the Java HotSpot™ VM is forced to stop executing a method's machine code and transfer control to the interpreter. This is called deoptimization. Since the interpreter does not know about the scalar replacement and synchronization removal performed by the compiler, the deoptimization framework was extended to reallocate and relock objects on demand.

REFERENCES

• 1: 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 [doi>10.1145/945885.945886]
• 2: Jeff Bogda , Urs Hölzle, Removing unnecessary synchronization in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.35-46, November 01-05, 1999, Denver, Colorado, United States
• 3: J. Bogda and A. Singh. Can a shape analysis work at run-time? In Proceedings of the Java Virtual Machine Research and Technology Symposium, Monterey, 2001.
• 4: 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 [doi>10.1145/945885.945892]
• 5: 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 [doi>10.1145/115372.115320]
• 6: Jeffrey Dean , David Grove , Craig Chambers, Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis, Proceedings of the 9th European Conference on Object-Oriented Programming, p.77-101, August 07-11, 1995
• 7: David Gay , Bjarne Steensgaard, Fast Escape Analysis and Stack Allocation for Object-Based Programs, Proceedings of the 9th International Conference on Compiler Construction, p.82-93, March 25-April 02, 2000
• 8: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 9: Robert Griesemer , Srdjan Mitrovic, A Compiler for the Java HotSpotTM Virtual Machine, The School of Niklaus Wirth, "The Art of Simplicity", p.133-152, January 2000
• 10: M. Hirzel, A. Diwan, and M. Hind. Pointer analysis in the presence of dynamic class loading. In Proceedings of the European Conference on Object-Oriented Programming, pages 96--122, Oslo, June 2004.
• 11: Urs Hölzle , Craig Chambers , David Ungar, Debugging optimized code with dynamic deoptimization, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.32-43, June 15-19, 1992, San Francisco, California, United States
• 12: A. L. Hosking and R. L. Hudson. Remembered sets can also play cards. In Proceedings of the ACM OOPSLA Workshop on Garbage Collection and Memory Management, Washington, D.C., Oct. 1993.
• 13: Intel Corporation. IA-32 Intel Architecture Software Developer's Manual, Volume 2A & 2B: Instruction Set Reference, 2004. Order Numbers 253666 and 253667.
• 14: A. C. King. Removing GC synchronisation extended version. Technical Report 11-03, Computing Laboratory, University of Kent, Apr. 2003.
• 15: Jeremy Manson , William Pugh , Sarita V. Adve, The Java memory model, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.378-391, January 12-14, 2005, Long Beach, California, USA
• 16: H. Mössenböck. Adding static single assignment form and a graph coloring register allocator to the Java Hotspot™ client compiler. Technical Report 15, Johannes Kepler University Linz, Nov. 2000.
• 17: V. Krishna Nandivada , David Detlefs, Compile-Time Concurrent Marking Write Barrier Removal, Proceedings of the international symposium on Code generation and optimization, p.37-48, March 20-23, 2005 [doi>10.1109/CGO.2005.12]
• 18: R. Pozo and B. Miller. Java SciMark 2.0. http://math.nist.gov/scimark2/.
• 19: Erik Ruf, Effective synchronization removal for Java, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.208-218, June 18-21, 2000, Vancouver, British Columbia, Canada
• 20: R. Sedgewick. Algorithms, pages 441--449. Addison-Wesley, second edition, 1988.
• 21: Standard Performance Evaluation Corporation. The SPEC JVM98 Benchmarks. http://www.spec.org/jvm98/.
• 22: Sun Microsystems, Inc. The Java HotSpot Virtual Machine, v1.4.1, Sept. 2002. http://java.sun.com/products/hotspot/.
• 23: Frédéric Vivien , Martin Rinard, Incrementalized pointer and escape analysis, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.35-46, June 2001, Snowbird, Utah, United States
• 24: Christian Wimmer , Hanspeter Mössenböck, Optimized interval splitting in a linear scan register allocator, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA [doi>10.1145/1064979.1064998]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Incremental compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

General Terms:
Algorithms, Languages, Performance

Keywords:
Java, deoptimization, escape analysis, just-in-time compilation, optimization, scalar replacement, stack allocation, synchronization removal