Abstract:

This paper presents an efficient context-sensitive heap analysis algorithm called Data Structure Analysis designed to enable analyses and transformations on entire disjoint recursive data structures. The analysis has several challenging properties needed to enable such transformations: context-sensitivity with cloning (essential for proving disjointness), field-sensitivity, and the use of an explicit heap model rather than just alias information. It is also applicable to arbitrary C programs. To our knowledge no prior work provides all these properties and is efficient and scalable enough for large programs. Measurements for 29 programs show that the algorithm is extremely fast, space-efficient, and scales almost linearly across 3 orders-of-magnitude of code size.

Published:

"Data Structure Analysis: An Efficient Context-Sensitive Heap Analysis", Chris Lattner & Vikram Adve
Technical Report #UIUCDCS-R-2003-2340, Computer Science Dept., Univ. of Illinois, Apr. 2003.

Update:

This document was updated on 15 November 2003 to reflect improvements to the algorithm, and to be more clear and precise.

Download:

• Data Structure Analysis: An Efficient Context-Sensitive Heap Analysis (PS)
• Data Structure Analysis: An Efficient Context-Sensitive Heap Analysis (PDF)

BibTeX Entry:

  @TechReport{LattnerAdve:DSA,
    Author      = {Chris Lattner and Vikram Adve},
    Title       = "{Data Structure Analysis: An Efficient Context-Sensitive Heap Analysis}",
    Institution = "{Computer Science Dept., Univ. of Illinois at Urbana-Champaign}",
    Number      = {UIUCDCS-R-2003-2340},
    Type        = {Tech. Report},
    Month       = {Apr},
    Year        = {2003}
  }