Data Structure Analysis:
An Efficient Context-Sensitive Heap Analysis
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:
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}
}