Efficient Context-Sensitive Shape Analysis with Graph Based Heap Models

Marron, Mark and Hermenegildo, Manuel V. and Kapur, Deepak and Stefanovic, Darko (2008). Efficient Context-Sensitive Shape Analysis with Graph Based Heap Models. "Lecture Notes In Computer Science", v. 4959 ; pp. 245-259. ISSN 0302-9743. https://doi.org/10.1007/978-3-540-78791-4_17.

Description

Title: Efficient Context-Sensitive Shape Analysis with Graph Based Heap Models
Author/s:
  • Marron, Mark
  • Hermenegildo, Manuel V.
  • Kapur, Deepak
  • Stefanovic, Darko
Item Type: Article
Título de Revista/Publicación: Lecture Notes In Computer Science
Date: March 2008
ISSN: 0302-9743
Volume: 4959
Subjects:
Freetext Keywords: Heap analysis techniques, optimizing compiler, memoizing analysis.
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (879kB) | Preview

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.

More information

Item ID: 2905
DC Identifier: http://oa.upm.es/2905/
OAI Identifier: oai:oa.upm.es:2905
DOI: 10.1007/978-3-540-78791-4_17
Official URL: http://www.springer.com/computer/lncs?SGWID=0-164-0-0-0
Deposited by: Memoria Investigacion
Deposited on: 26 Apr 2010 08:45
Last Modified: 20 Apr 2016 12:31
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM