John Whaley
ABSTRACT
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 points-to escape graph also contains escape information, which characterizes how objects allocated in one region of the program can escape to be accessed by another region. The algorithm is designed to analyze arbitrary regions of complete or incomplete programs, obtaining complete information for objects that do not escape the analyzed regions.
We have developed an implementation that uses the escape information to eliminate synchronization for objects that are accessed by only one thread and to allocate objects on the stack instead of in the heap. Our experimental results are encouraging. We were able to analyze programs tens of thousands of lines long. For our benchmark programs, our algorithms enable the elimination of between 24% and 67% of the synchronization operations. They also enable the stack allocation of between 22% and 95% of the objects.
- 1.J. Aldrich, C. Chambers, E. Sirer, and S. Eggers. Static analyses for eliminating unnecessary synchronization from java programs. In Proceedings of the 6th International Static Analysis Symposium, September 1999.Google Scholar
Cross Ref
- 2.Lars Ole Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, May 1994.Google Scholar
- 3.B. Goldberg and Y. Park. Escape analysis on lists. In Proceedings of the SIGPLAN '92 Conference on Program Language Design and Implementation, pages 116- 127, July 1992. Google ScholarDigital Library
- 4.H. Baker. Unifying and conquer (garbage, updating, aliasing ..) in functional languages. In Proceedings of the ACM Conference on Lisp and Functional Programming, pages 218-226, 1990. Google ScholarDigital Library
- 5.B. Blanchet. Escape analysis: Correctness proof, implementation and experimental results. In Proceedings of the 25th Annual A CM Symposium on the Principles of Programming Languages, Paris, France, January 1998. ACM, ACM, New York. Google ScholarDigital Library
- 6.B. Blanchet. Escape analysis for object oriented languages, application to java. In Proceedings of the 14th Annual Conference on Object-Oriented Programming Systems, Languages and Applications, Denver, CO, November 1999. Google ScholarDigital Library
- 7.J. Bodga and U. Hoelzle. Removing unnecessary synchronization in java. In Proceedings of the 14th Annual Conference on Object-Oriented Programming Systems, Languages and Applications, Denver, CO, November 1999. Google ScholarDigital Library
- 8.M. Burke, J. Choi, S. Fink, D. Grove, M. Hind, V. Sarkar, M. Serrano, V. Sreedhar, H. Srinivasan, and 3. Whaley. The jalapefio dynamic optimizing compiler for java. In Proceedings of the A CM SIGPLAN 1999 Java Grande Conference, June 1999. Google ScholarDigital Library
- 9.R. Chatterjee, B. Ryder, and W. Landi. Relevant context inference. In Proceedings of the 26th Annual A CM Symposium on the Principles of Programming Languages, San Antonio, TX, January 1999. Google ScholarDigital Library
- 10.J. Choi, M. Burke, and P. Carini. Efficient flow-sensitive interprocedural computation of pointerinduced aliases and side effects. In Conference Record of the Twentieth Annual Symposium on Principles of Programming Languages, Charleston, SC, January 1993. ACM. Google ScholarDigital Library
- 11.J. Choi, M. Gupta, M. Serrano, V. Sreedhar, and S. Midkiff. Escape analysis for java. In Proceedings of the l~th Annual Conference on Object-Oriented Programming Systems, Languages and Applications, Denver, CO, November 1999. Google ScholarDigital Library
- 12.J. Corbett. Using shape analysis to reduce finite-state models of concurrent java programs. In Proceedings of the International Symposium on Software Testing and Analysis, March 1998. Google ScholarDigital Library
- 13.J. Dean, D. Grove, and C. Chambers. Optimization of object-oriented programs using static class hierarchy analysis. In Proceedings of the gth European Conference on Object-Oriented Programming, Aarhus, Denmark, August 1995. Google ScholarDigital Library
- 14.A. Deutsch. On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications. In Proceedings of the 17th Annual A CM Symposium on the Principles of Programming Languages, pages 157-168, San Francisco, CA, January 1990. ACM, ACM, New York. Google ScholarDigital Library
- 15.A. Deutsch. On the complexity of escape analysis, in Proceedings of the 24th Annual A CM Symposium on the Principles of Programming Languages, Paris, France, January 1997. ACM, ACM, New York. Google ScholarDigital Library
- 16.P. Diniz and M. Rinard. Lock coarsening: Eliminating lock overhead in automatically parallelized objectbased programs. In Proceedings of the Ninth Workshop on Languages and Compilers for Parallel Computing, pages 285-299, San Jose, CA, August 1996. Springer- Verlag. Google ScholarDigital Library
- 17.P. Diniz and M. Rinard. Synchronization transformations for parallel computing. In Proceedings of the 2~th Annual A CM Symposium on the Principles of Programming Languages, pages 187-200, Paris, France, January 1997. ACM, New York. Google ScholarDigital Library
- 18.M. Emami, R. Ghiya, and L. Hendren. Contextsensitive interprocedural points-to analysis in the presence of function pointers. In Proceedings of the SIG- PLAN '94 Conference on Program Language Design and Implementation, pages 242-256, Orlando, FL, June 1994. ACM, New York. Google ScholarDigital Library
- 19.J. Hannan. A type-based analysis for block allocation in functional languages. In Proceedings of the Second International Static Analysis Symposium. ACM, ACM, New York, September 1995. Google ScholarDigital Library
- 20.W. Landi and B. Ryder. A safe approximation algorithm for interprocedural pointer aliasing. In Proceedings of the SIGPLAN '92 Conference on Program Language Design and Implementation, San Francisco, CA, June 1992. Google ScholarDigital Library
- 21.J. Plevyak, X. Zhang, and A. Chien. Obtaining sequential efficiency for concurrent object-oriented languages. In Proceedings of the 2Pad Annual A CM Symposium on the Principles of Programming Languages, San Francisco, CA, January 1995. ACM, New York. Google ScholarDigital Library
- 22.E. Ruf. Context-insensitive alias analysis reconsidered. In Proceedings of the SIGPLAN '95 Conference on Program Language Design and Implementation, La Jolla, CA, June 1995. Google ScholarDigital Library
- 23.R. Rugina and M. Rinard. Pointer analysis for multithreaded programs. In Proceedings of the SIGPLAN '99 Conference on Program Language Design and Implementation, Atlanta, GA, May 1999. Google ScholarDigital Library
- 24.M. Sagiv, T. Raps, and R. Wilhelm. Solving shapeanalysis problems in languages with destructive updating. A CM Transactions on Programming Languages and Systems, 20(1):1-50, January 1998. Google ScholarDigital Library
- 25.P. Sathyanathan and M. Lain. Context-sensitive interprocedural pointer analysis in the presence of dynamic aliasing. In Proceedings of the Ninth Workshop on Languages and Compilers for Parallel Computing, San Jose, CA, August 1996. Springer-Verlag. Google ScholarDigital Library
- 26.M. Shapiro and S. Horwitz. Fast and accurate flowinsensitive points-to analysis. In Proceedings of the 24th Annual A CM Symposium on the Principles of Programming Languages, Paris, France, January 1997. Google ScholarDigital Library
- 27.Bjarne Steensgaard. Points-to analysis in almost linear time. In Proceedings of the 23rd Annual A CM Symposium on the Principles of Programming Languages, St. Petersburg Beach, FL, January 1996. Google ScholarDigital Library
- 28.R. Wilson attd M. Lain. Efficient context-sensitive pointer analysis for C programs. In Proceedings of the SIGPLAN '95 Conference on Program Language Design and Implementation, La Jolla, CA, June 1995. ACM, New York. Google ScholarDigital Library
- 29.Y. Tang and P. Jouvelot. Control-flow effects for escape analysis. In Workshop on Static Analysis, pages 313- 321, September 1992.Google Scholar
Index Terms
- Compositional pointer and escape analysis for Java programs
Recommendations
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 ...
Interprocedural pointer alias analysis
We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework ...
Comments