Set-Sharing is Redundant for Pair-Sharing

Title
Publication TypeJournal Article
Year of Publication2002
AuthorsBagnara R, Hill PM, Zaffanella E
JournalTheoretical Computer Science
Volume277
Pagination3–46
ISSN0304-3975
Keywordsabstract interpretation, domain decomposition, logic programming, sharing analysis, software verification, static analysis
Abstract

Although the usual goal of sharing analysis is to detect which pairs of variables share, the standard choice for sharing analysis is a domain that characterizes set-sharing. In this paper, we question, apparently for the first time, whether this domain is over-complex for pair-sharing analysis. We show that the answer is yes. By defining an equivalence relation over the set-sharing domain we obtain a simpler domain, reducing the complexity of the abstract unification procedure. We present experimental results showing that, in practice, our domain compares favorably with the set-sharing one over a wide range of benchmark and real programs.

DOI10.1016/S0304-3975(00)00312-1
File attachments: 
We are a passionate team of experts. Do not hesitate to let us have your feedback:
You may be surprised to discover just how much your suggestions matter to us.