ABSTRACT
This paper presents a simple and efficient data flow algorithm for escape analysis of objects in Java programs to determine (i) if an object can be allocated on the stack; (ii) if an object is accessed only by a single thread during its lifetime, so that synchronization operations on that object can 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 summarized for each method such that the same summary information may be used effectively in different calling contexts. We present an interprocedural algorithm that uses the above property to efficiently compute the connection graph and identify the non-escaping 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 three out of the ten benchmarks (with a median of 19%), 11% to 92% of all lock operations are eliminated in those ten 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 128 MB memory.
- 1.Jonathan Alridch, Craig Chambers, Emin Gun Sirer, and Susan Eggers. Static analysis for eliminating unnessary synchronization from java programs. In Proceedings of the Sixth International Static Analysis Symposium, Venezia, Italy, September 1999.]] Google ScholarDigital Library
- 2.D. E Bacon, R. Konuru, C. Murthy, and M. Sen'ano. Thin locks: Featherweight synchronization for Java. In Proc. A CM SIGPLAN Conference on Programming Lan. guage Design and Implementation, Montreal, Canada, June 1998.]] Google ScholarDigital Library
- 3.L. Birkedal, M. Tofte, and M. Vejlstrup. From region inference to yon Neumann machines via region representation inference. In Proc. 23rdAnnualACM Symposium on Principles of Programming Languages, January 1996.]] Google ScholarDigital Library
- 4.B. Blanchet. Escape analysis: Correctness, proof, implementation and experimental results. In Proc. 25th Annual ACM Symposium on Principles of Programming Languages, pages 25-37, San Diego, CA, January 1998.]] Google ScholarDigital Library
- 5.Bruno Blanchet. Escape analysis for object oriented languages: Application to Java. In Proceedings of ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, Denver, Colorado, November 1999.]] Google ScholarDigital Library
- 6.Jeff Bodga and Urs H61zle. Removing unnecessay synchronization in java. In Proceedings of ACM SIG- PLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, Denver, Colorado, November 1999.]] Google ScholarDigital Library
- 7.Michael Burke, Paul Carini, Jong-Deok Choi, and Michael Hind. Flow-insensitive interprocedural alias analysis in the presence of pointers. In K. Pingali, U. Banerjee, D. Gelernter, A. Nicolau, and D. Padua, editors, Lecture Notes in Computer Science, 892, pages 234-250. Springer-Verlag, I995. Proceedings from the 7th Workshop on Languages and Compilers for Parallel Computing. Extended version published as Research Report RC 19546, IBM T. J. Watson Research Center, September 1994.]] Google ScholarDigital Library
- 8.Michael G. Burke, Jong-Deok Choi, Stephen Fink, David Grove, Michael Hind, Vivek Sarkar, Mauricio J. Serrano, V. C. Sreedhar, Harini Srinivasan, and John Whaley. The Jalapefio dynamic optimizing compiler for java. In Proc. A CM SIGPLAN 1999 Java Grande Conference, June 1999.]] Google ScholarDigital Library
- 9.Jong-Deok Choi, David Grove, Michael Hind, and Vivek Sarkar. Efficient and Precise Modeling of Exceptions for the Analysis of Java Programs, 1999. To appear at PASTE '99.]] Google ScholarDigital Library
- 10.James C. Corbett. Constructing compact models of concurrent java programs. In Proceedings of the 1998 International Symposium of Software Testing and Analysis. ACM Press, March 1998.]] Google ScholarDigital Library
- 11.IBM Corporation. IBM High Performance Compiler for Java, 1997. Information available in Web page at http: //simontOl. torolab, ibm. com/hpj/hpj . available for download at http: //www. alphaWorks, ibm. com/formula.]]Google Scholar
- 12.A. Deutsch. On the complexity of escape analysis. In Proc. 24th Annual ACM Symposium on Principles of Programming Languages, pages 358-371, San Diego, CA, January 1997.]] Google ScholarDigital Library
- 13.P. Diniz and M. Rinard. Synchronization Transformations for Parallel Computing. In Proceedings of the 9'th Workshop on Languages and Compilers for Parallel Computers, January 1997.]] Google ScholarDigital Library
- 14.Julian Dolby. Automatic inline allocation of objects. In Proceedings of the 1997 ACM SIGPLAN Conference of Programming Language Design and Implementation, Las Vegas, Nevada, June 1997.]] Google ScholarDigital Library
- 15.David Gay and Bjame Steensgaard. Stack allocating objects in Java. Research Report, Microsoft Research, 1999.]]Google Scholar
- 16.R. Ghiya and L. J. Hendren. Putting pointer analysis to work. In Proc. 25th Annual ACM Symposium on Principles of Programming Languages, pages 121-133, San Diego, CA, January 1998.]] Google ScholarDigital Library
- 17.James Gosling, Bill Joy, and Guy Steele. The Java(TM) Language Specification. Addison-Wesley, 1996.]] Google ScholarDigital Library
- 18.J. Hannan. A type-based analysis for stack allocation in functional languages. In Proc. 2nd International Static Analysis Symposium, September 1995.]] Google ScholarDigital Library
- 19.Michael Hind, Michael Burke, Paul Carini, and Jong- Deok Choi. Interprocedural pointer alias analysis. A CM Transactions on Programming Languages and Systems, To appear.]] Google ScholarDigital Library
- 20.Z. Li and W. Abu-Sufah. On reducing data synchronization in multiprocessed loops. IEEE Transactions on Computers, C-36(1):105-109, January 1987.]]Google ScholarDigital Library
- 21.S.R Midkiff and D. Padua. Compiler algorithms for synchronization. IEEE Transactions on Computers, C- html, 36(12):1485-1495, December 1987.]] Google ScholarDigital Library
- 22.Y.G. Park and B. Goldberg. Escape analysis on lists, In Proc. ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 117-127, July 1992.]] Google ScholarDigital Library
- 23.A. Reid, J. McCorquodale, J. Baker, W. Hsieh, and J. Zachary. The need for predictable garbage collection. In WCSSS'99 Workshop on Compiler Support for System Software, March 1999.]]Google Scholar
- 24.C. Ruggieri and T.P. Murtagh. Lifetime analysis of dynamically allocated objects. In Proc. 15th Annual ACM Symposium on Principles of Programming Languages, pages 285-293, January 1988.]] Google ScholarDigital Library
- 25.John Whaley and Martin Rinard. Compositional pointer and escape analysis for java programs. In Proceedings of ACM SIGPLAN Conference on Object.Oriented Programming Systems, Languages, and Applications, Denver, Colorado, November 1999.]] Google ScholarDigital Library
Index Terms
- Escape analysis for Java
Recommendations
Partial Escape Analysis and Scalar Replacement for Java
CGO '14: Proceedings of Annual IEEE/ACM International Symposium on Code Generation and OptimizationEscape Analysis allows a compiler to determine whether an object is accessible outside the allocating method or thread. This information is used to perform optimizations such as Scalar Replacement, Stack Allocation and Lock Elision, allowing modern ...
Escape analysis for synchronization removal
SAC '06: Proceedings of the 2006 ACM symposium on Applied computingIn this paper we introduce our escape analysis framework for Java, which is a kind of flow-insensitive, inter-procedural, and context-sensitive data flow analysis. And we present an efficient static intra-procedural algorithm for inferring the set of ...
Escape analysis for JavaTM: 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 JavaTM. This analysis is interprocedural, context ...
Comments