Compositional pointer and escape analysis for Java programs
John Whaley, Martin Rinard · ACM SIGPLAN Notices · 1999
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.
Cited by 63 works. doi:10.1145/320385.320400 Open-access PDF
Authors
References
- Points-to analysis in almost linear time
- Context-sensitive interprocedural points-to analysis in the presence of function pointers
- Efficient context-sensitive pointer analysis for C programs
- A safe approximate algorithm for interprocedural aliasing
- Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects
- The Jalapeño dynamic optimizing compiler for Java
- Escape analysis for Java
- Solving shape-analysis problems in languages with destructive updating
- Fast and accurate flow-insensitive points-to analysis
- Escape analysis for object-oriented languages