Name
Abstract | ||
|---|---|---|
The performance of heap analysis techniques has a significant impact on their utility in an optimizing compiler.Most shape analysis techniques perform interprocedural dataflow analysis in a context-sensitive manner, which can result in analyzing each procedure body many times (causing significant increases in runtime even if the analysis results are memoized). To improve the effectiveness of memoization (and thus speed up the analysis) project/extend operations are used to remove portions of the heap model that cannot be affected by the called procedure (effectively reducing the number of different contexts that a procedure needs to be analyzed with). This paper introduces project/extend operations that are capable of accurately modeling properties that are important when analyzing non-trivial programs (sharing, nullity information, destructive recursive functions, and composite data structures). The techniques we introduce are able to handle these features while significantly improving the effectiveness of memoizing analysis results (and thus improving analysis performance). Using a range of well known benchmarks (many of which have not been successfully analyzed using other existing shape analysis methods) we demonstrate that our approach results in significant improvements in both accuracy and efficiency over a baseline analysis. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-78791-4_17 | CC |
Keywords | Field | DocType |
heap analysis technique,baseline analysis,analysis result,efficient context-sensitive shape analysis,interprocedural dataflow analysis,shape analysis technique,existing shape analysis method,memoizing analysis result,analysis performance,significant impact,heap model,procedure body,shape analysis,optimizing compiler | Data structure,Graph,Separation logic,Programming language,Computer science,Heap (data structure),Dataflow,Memoization,Shape analysis (digital geometry),Speedup | Conference |
Volume | ISSN | ISBN |
4959 | 0302-9743 | 3-540-78790-9 |
Citations | PageRank | References |
14 | 0.87 | 25 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark Marron | 1 | 124 | 9.74 |
| Manuel V. Hermenegildo | 2 | 2692 | 182.60 |
| Deepak Kapur | 3 | 2282 | 235.00 |
| Darko Stefanovic | 4 | 14 | 0.87 |