Chinese Journal of Computers   Full Text
Title	The Study of Stack Allocation in Loop Based on Escape Analysis
Authors	WANG Lei XU Xing
Address	(School of Computer, Beihang University, Beijing 100083)
Year	2008
Issue	No.7(1101—1108)
Abstract &   Background	Abstract The technique of stack allocation improves the efficiency of Java program, but the trade-off between the ratio of allocated objects and the size of stack is difficult. In this paper, a flow-insensitive, inter-procedural, and context-sensitive escape analysis is implemented. The allocation policy based on loop as a basic unit is presented, and the concepts of object stack and stack region are proposed. The authors implement the stack allocation based on escape analysis through the loop analysis. The result of SPECjvm98 shows that 8.3% to 25% (with an average of 15.18%) of all objects could be stack allocated in the new algorithm with the controlled size of stack. Keywords JVM; program analysis; escape analysis; stack allocation; loop analysis Background This work is partially supported by Beijing Natural Science Foundation, Intel China Research Center and Scientific Research Foundation for Returned Scholars. The main concerned problem in this paper is the stack allocation of object in loop. In JVM, the memory needed for a Java program is allocated in the heap or stack. Compared with heap allocation, stack allocation has three important advantages which include: (1) it reduces some synchronization operations; (2) it lightens some burden of the garbage collector; (3) since the stack space is a hot spot of Cache, stack operations are much faster than ones in heap. However, when objects are allocated in loop, the conflict between the ratio of stack allocation of objects and size of the stack space is irreconcilable. Blanchet and Gray realize the allocation of fixed-length objects that can be reused in loop, but these methods do not solve the problem of stack allocation of variable objects. In this paper, the allocation policy based on loop as a basic unit is presented, and the concepts of object stack and stack region are proposed. The authors implement the stack allocation base on escape analysis through the loop analysis. The result of SPECjvm98 shows that 8.3% to 25% (with an average of 15.18%) of all objects could be stack allocated in the new algorithm with the controlled size of stack. Before this paper’s work, the group implemented a flow-insensitive, inter-procedural, and context-sensitive escape analysis, which has been applied to remove unnecessary synchronization in Java. For the authors’ benchmarks, 7.3% to 99.9% of synchronization operations are eliminated.