Name
Abstract | ||
|---|---|---|
Tracking subset relations between the contents containers on the heap is fundamental to modeling the semantics of many common programing idioms such as applying a function to a subset of objects and maintaining multiple views of the same set of objects. We introduce a relation, must reference sets, which subsumes the concept of must-aliasing and enables existing shape analysis techniques to efficiently and accurately model many types of containment properties without the use of explicit quantification or specialized logics for containers/sets. We extend an existing shape analysis to model the concept of reference sets. Reference sets allow the analysis to efficiently track a number of important relations (must-=, and must-⊆) between objects that are the targets of sets of references (variables or pointers). We show that shape analysis augmented with reference set information is able to precisely model sharing for a range of data structures in real programs that cannot be expressed using simple must-alias information. In contrast to more expressive proposals based on logic languages (e.g., extensions of first-order predicate logic with transitive closure or the use of a decision procedure for sets), reference sets can be efficiently tracked in a shape analyzer. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-11319-2_19 | VMCAI |
Keywords | Field | DocType |
existing shape analysis,reference set relation,model sharing,shape analyzer,shape analysis technique,logic language,shape analysis,reference set,simple must-alias information,reference set information,first-order predicate logic,data structure,first order,transitive closure | Pointer (computer programming),Data structure,Computer science,Theoretical computer science,Heap (data structure),Transitive closure,Predicate logic,Model sharing,Semantics,Shape analysis (digital geometry) | Conference |
Volume | ISSN | ISBN |
5944 | 0302-9743 | 3-642-11318-4 |
Citations | PageRank | References |
1 | 0.36 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark Marron | 1 | 124 | 9.74 |
| Rupak Majumdar | 2 | 3401 | 220.08 |
| Darko Stefanović | 3 | 194 | 17.52 |
| Deepak Kapur | 4 | 2282 | 235.00 |