Precise Set Sharing Analysis for Java-Style Programs

Méndez-Lojo, Mario and Hermenegildo, Manuel V. (2008). Precise Set Sharing Analysis for Java-Style Programs. "Lecture Notes in Computer Science", v. 4905 ; pp. 172-187. ISSN 0302-9743.


Title: Precise Set Sharing Analysis for Java-Style Programs
  • Méndez-Lojo, Mario
  • Hermenegildo, Manuel V.
Item Type: Article
Título de Revista/Publicación: Lecture Notes in Computer Science
Date: January 2008
ISSN: 0302-9743
Volume: 4905
Freetext Keywords: Java, set sharing analysis.
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

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


Finding useful sharing information between instances in object- oriented programs has recently been the focus of much research. The applications of such static analysis are multiple: by knowing which variables definitely do not share in memory we can apply conventional compiler optimizations, find coarse-grained parallelism opportunities, or, more importantly, verify certain correctness aspects of programs even in the absence of annotations. In this paper we introduce a framework for deriving precise sharing information based on abstract interpretation for a Java-like language. Our analysis achieves precision in various ways, including supporting multivariance, which allows separating different contexts. We propose a combined Set Sharing + Nullity + Classes domain which captures which instances do not share and which ones are definitively null, and which uses the classes to refine the static information when inheritance is present. The use of a set sharing abstraction allows a more precise representation of the existing sharings and is crucial in achieving precision during interprocedural analysis. Carrying the domains in a combined way facilitates the interaction among them in the presence of multivariance in the analysis. We show through examples and experimentally that both the set sharing part of the domain as well as the combined domain provide more accurate information than previous work based on pair sharing domains, at reasonable cost.

More information

Item ID: 2906
DC Identifier:
OAI Identifier:
DOI: 10.1007/978-3-540-78163-9_17
Official URL:
Deposited by: Memoria Investigacion
Deposited on: 26 Apr 2010 08:22
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