Efficient bottom-up heap analysis for symbolic path-based data access summaries

Abstract

We propose a heap analysis for extracting data access summaries based on symbolic access paths (SAPs) of methods in object-oriented languages. The analysis takes advantage of the insight that typical programs access dynamic data structures in regular manners. We combine this insight with a bottom-up approach that computes a local summary for each basic block, loop, and method in the program, which is then encapsulated into an abstract block in order to efficiently handle the higher levels of the analysis. We solve the problem of the dependence of local analysis results on the global heap aliasing by inferring the sets of aliases on which the correctness of the local results is predicated. Experimental evaluation for Java shows that for typical programs that use dynamic data structures, our analysis runs in a fast single pass and produces useful results.