Stack allocation and synchronization optimizations for Java using escape analysis

ABSTRACT

This article presents an escape analysis framework for Java to determine (1) if an object is not reachable after its method of creation returns, allowing the object to be allocated on the stack, and (2) if an object is reachable only from a single thread during its lifetime, allowing unnecessary synchronization operations on that object to be removed. We introduce a new program abstraction for escape analysis, the connection graph, that is used to establish reachability relationships between objects and object references. We show that the connection graph can be succinctly summarized for each method such that the same summary information may be used in different calling contexts without introducing imprecision into the analysis. We present an interprocedural algorithm that uses the above property to efficiently compute the connection graph and identify the nonescaping objects for methods and threads. The experimental results, from a prototype implementation of our framework in the IBM High Performance Compiler for Java, are very promising. The percentage of objects that may be allocated on the stack exceeds 70% of all dynamically created objects in the user code in three out of the ten benchmarks (with a median of 19%); 11% to 92% of all mutex lock operations are eliminated in those 10 programs (with a median of 51%), and the overall execution time reduction ranges from 2% to 23% (with a median of 7%) on a 333-MHz PowerPC workstation with 512 MB memory.

REFERENCES

• 1: Jonathan Aldrich , Craig Chambers , Emin Gün Sirer , Susan J. Eggers, Static Analyses for Eliminating Unnecessary Synchronization from Java Programs, Proceedings of the 6th International Symposium on Static Analysis, p.19-38, September 22-24, 1999
• 2: David F. Bacon , Ravi Konuru , Chet Murthy , Mauricio Serrano, Thin locks: featherweight synchronization for Java, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.258-268, June 17-19, 1998, Montreal, Quebec, Canada
• 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: 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 [doi>10.1145/268946.268949]
• 5: Bruno Blanchet, Escape analysis for object-oriented languages: application to Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.20-34, November 01-05, 1999, Denver, Colorado, United States
• 6: 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
• 7: Michael G. Burke , Paul R. Carini , Jong-Deok Choi , Michael Hind, Flow-Insensitive Interprocedural Alias Analysis in the Presence of Pointers, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.234-250, August 08-10, 1994
• 8: Craig Chambers , Igor Pechtchanski , Vivek Sarkar , Mauricio J. Serrano , Harini Srinivasan, Dependence Analysis for Java, Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing, p.35-52, August 04-06, 1999
• 9: David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.296-310, June 1990, White Plains, New York, United States
• 10: Ramkrishna Chatterjee , Barbara G. Ryder , William A. Landi, Relevant context inference, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-146, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292554]
• 11: Ben-Chung Cheng , Wen-Mei W. Hwu, Modular interprocedural pointer analysis using access paths: design, implementation, and evaluation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.57-69, June 18-21, 2000, Vancouver, British Columbia, Canada
• 12: 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 [doi>10.1145/158511.158639]
• 13: Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-19, November 01-05, 1999, Denver, Colorado, United States
• 14: Choi, J.-D., Gupta, M., Serrano, M. J., Sreedhar, V. C., and Midkiff, S. 2002. Stack allocation and synchronization optimizations for Java using escape analysis. Res. rep. RC22340. IBM T. J. Watson Research Center, Yorktown Heights, NY.
• 15: James C. Corbett, Constructing compact models of concurrent Java programs, Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis, p.1-10, March 02-04, 1998, Clearwater Beach, Florida, United States
• 16: Alain Deutsch, On the complexity of escape analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.358-371, January 15-17, 1997, Paris, France [doi>10.1145/263699.263750]
• 17: Pedro Diniz , Martin Rinard, Synchronization transformations for parallel computing, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.187-200, January 15-17, 1997, Paris, France [doi>10.1145/263699.263718]
• 18: Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
• 19: Manuel Fähndrich , Jakob Rehof , Manuvir Das, Scalable context-sensitive flow analysis using instantiation constraints, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.253-263, June 18-21, 2000, Vancouver, British Columbia, Canada
• 20: David Gay , Alex Aiken, Memory management with explicit regions, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.313-323, June 17-19, 1998, Montreal, Quebec, Canada
• 21: 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
• 22: Rakesh Ghiya , Laurie J. Hendren, Connection analysis: a practical interprocedural heap analysis for C, International Journal of Parallel Programming, v.24 n.6, p.547-578, Dec. 1996
• 23: Rakesh Ghiya , Laurie J. Hendren, Putting pointer analysis to work, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.121-133, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268957]
• 24: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 25: Deepak Goyal , Robert Paige, A language-theoretic approach to algorithms, 2000
• 26: Manish Gupta , Jong-Deok Choi , Michael Hind, Optimizing Java Programs in the Presence of Exceptions, Proceedings of the 14th European Conference on Object-Oriented Programming, p.422-446, June 12-16, 2000
• 27: 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
• 28: IBM Corporation 1997. IBM High Performance Compiler for Java. Available online for download at http://www.alphaWorks.ibm.com/formula.
• 29: JavaMemoryModel 2002. Java memory model mailing list. Archived at http://www.cs.umd.edu/pugh/java/memoryModel/archive/.
• 30: William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.235-248, June 15-19, 1992, San Francisco, California, United States
• 31: J. R. Larus , P. N. Hilfinger, Detecting conflicts between structure accesses, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.24-31, June 20-24, 1988, Atlanta, Georgia, United States
• 32: Jaejin Lee , David A. Padua , Samuel P. Midkiff, Basic compiler algorithms for parallel programs, Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 04-06, 1999, Atlanta, Georgia, United States
• 33: Li, Z. and Abu-Sufah, W. 1987. On reducing data synchronization in multiprocessed loops. IEEE Trans. Comput. C-36, 1 (Jan.), 105--109.
• 34: Donglin Liang , Mary Jean Harrold, Efficient points-to analysis for whole-program analysis, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.199-215, September 06-10, 1999, Toulouse, France
• 35: Jeremy Manson , William Pugh, Core semantics of multithreaded Java, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.29-38, June 2001, Palo Alto, California, United States [doi>10.1145/376656.376806]
• 36: Thomas J. Marlowe , Barbara G. Ryder, Data-flow analysis and incremental iteration, 1989
• 37: S. P. Midkiff , D. A. Padua, Compiler algorithms for synchronization, IEEE Transactions on Computers, v.36 n.12, p.1485-1495, Dec. 1987 [doi>10.1109/TC.1987.5009499]
• 38: Oliver, M., Deciulescu, E., and Clark, C. 2000. Java positioning paper. Available online at http://www-1.ibm.com/servers/eserver/zseries/software/java/position.html.
• 39: Young Gil Park , Benjamin Goldberg, Escape analysis on lists, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.116-127, June 15-19, 1992, San Francisco, California, United States
• 40: William Pugh, Fixing the Java memory model, Proceedings of the ACM 1999 conference on Java Grande, p.89-98, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304106]
• 41: Reid, A., McCorquodale, J., Baker, J., Hsieh, W., and Zachary, J. 1999. The need for predictable garbage collection. In Proceedings of the WCSSS'99 Workshop on Compiler Support for System Software.
• 42: 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
• 43: C. Ruggieri , T. P. Murtagh, Lifetime analysis of dynamically allocated objects, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-293, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73585]
• 44: Radu Rugina , Martin Rinard, Pointer analysis for multithreaded programs, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.77-90, May 01-04, 1999, Atlanta, Georgia, United States
• 45: Mooly Sagiv , Thomas Reps , Reinhard Wilhelm, Solving shape-analysis problems in languages with destructive updating, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.1, p.1-50, Jan. 1998 [doi>10.1145/271510.271517]
• 46: 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 [doi>10.1145/174675.177855]
• 47: 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
• 48: John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.187-206, November 01-05, 1999, Denver, Colorado, United States
• 49: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees; Graphs and networks

General Terms:
Algorithms, Languages

Keywords:
Connection graphs, escape analysis, points-to graph