Data Structure Analysis A Fast and Scalable Context-Sensitive Heap Analysis.pdf

Data Structure Analysis: A Fast and Scalable Context-Sensitive Heap Analysis Chris Lattner Vikram Adve University of Illinois at Urbana-Champaign {lattner,vadve}@cs.uiuc.edu ABSTRACT This paper describes a scalable heap analysis algorithm, Data Structure Analysis, designed to enable analyses and transformations of programs at the level of entire logical data structures. Data Structure Analysis attempts to identify dis- joint instances of logical program data structures and their internal and external connectivity properties (without trying to categorize their “shape”). To achieve this, Data Struc- ture Analysis is fully context-sensitive (in the sense that it names memory objects by entire acyclic call paths), is field- sensitive, builds an explicit model of the heap, and is robust enough to handle the full generality of C. Despite these aggressive features, the algorithm is both extremely fast (requiring 2-7 seconds for C programs in the range of 100K lines of code) and is scalable in practice. It has three features we believe are novel: (a) it incrementally builds a precise program call graph during the analysis; (b) it distinguishes complete and incomplete information in a man- ner that simplifies analysis of libraries or other portions of programs; and (c) it uses speculative field-senstivity in type- unsafe programs in order to preserve efficiency and scalabil- ity. Finally, it shows that the key to achieving scalability in a fully context-sensitive algorithm is the use of a unification- based approach, a combination that has been used before but whose importance has not been clearly articulated. 1. INTRODUCTION Alias analysis for programs with complex pointer-based data structures has been most successful at guiding tradi- tional low-level memory optimizations. These transforma- tions rely on disambiguating pairs of memory references and on identifying local and interprocedural side-effects of state- ments. In contrast, there has been much less success with tr