Practical escape analyses

Abstract

A key analysis developed for the compilation of parallel programs is thread escape analysis (hereafter referred to as escape analysis), which determines what objects are accessed in more than one thread, and which references within a program are references to such objects. Escape analysis has several important client optimizations: identifying objects on which races may exist, identifying locks that can be removed, identifying heap allocated objects referenced within a single thread, and compiling for strict memory models. While the effectiveness of individual escape analyses has been measured for different client optimizations, there has been no effort to compare the effectiveness of the different escape analyses over all the different clients. Nor has therebeen any attempt to develop a perfect escape analysis and measure how far from it the different escape analyses are. This paper presents a perfect escape analysis for specific runs of Java programs, which tracks all possibly escaping objects at runtime, and determines precisely which ones escape. It uses a caching technique to reduce the time and space needed for collecting access information by 8 times and 48 times, respectively, relative to not using the caching technique. We compare the perfect escape analysis results with the results from the practical escape analyses, using the four clients above or metrics that are significant for those clients. From this comparison we conclude that the relative precision of different escape analyses changes with different clients and that the most precise analysis for each client is "close enough" to the perfect analysis for three out of the four clients.