Data Structure Analysis: A Fast and Scalable Context-Sensitive Heap Analysis
Chris Lattner, Vikram Adve · 2003
In our recent work, we have developed compiler analyses and transformations that operate at the level of entire logical data structures, rather than individual load and store operations or individual data elements. This paper describes a fast, scalable heap analysis algorithm that has been the foundation for supporting such transformations, which we call Data Structure Analysis. Data Structure Analysis is fully context-sensitive (in the sense that it resolves memory objects by entire acyclic call paths), it is field-sensitive, and builds an explicit model of the heap. Nevertheless, the algorithm is both extremely fast (requiring 2-7 seconds for C programs in the range of 100K lines of code) and scalable in practice. The algorithm is robust enough to handle the full generality of C. It has three features we believe are novel: (a) it incrementally builds a program call graph during the analysis despite using a special handling of strongly connected components of the call graph for e#ciency; (b) it distinguishes complete and incomplete information in a manner that simplifies handling of incomplete programs; and (c) it uses partial field-senstivity in type-unsafe programs in order to preserve e#ciency and scalability. Finally, the key to achieving scalability is that the algorithm combines full context-sensitivity (as noted above) with a unification-based analysis, a combination that has been used before but its importance has not been clearly articulated.