Efficient Context-Sensitive Shape Analysis with Graph Based Heap Models

Marron, Mark; Hermenegildo, Manuel V.; Kapur, Deepak y 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.

Descripción

Título: Efficient Context-Sensitive Shape Analysis with Graph Based Heap Models
Autor/es:
  • Marron, Mark
  • Hermenegildo, Manuel V.
  • Kapur, Deepak
  • Stefanovic, Darko
Tipo de Documento: Artículo
Título de Revista/Publicación: Lecture Notes In Computer Science
Fecha: Marzo 2008
Volumen: 4959
Materias:
Palabras Clave Informales: Heap analysis techniques, optimizing compiler, memoizing analysis.
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Inteligencia Artificial
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (879kB) | Vista Previa

Resumen

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.

Más información

ID de Registro: 2905
Identificador DC: http://oa.upm.es/2905/
Identificador OAI: oai:oa.upm.es:2905
Identificador DOI: 10.1007/978-3-540-78791-4_17
URL Oficial: http://www.springer.com/computer/lncs?SGWID=0-164-0-0-0
Depositado por: Memoria Investigacion
Depositado el: 26 Abr 2010 08:45
Ultima Modificación: 20 Abr 2016 12:31
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM