School Homepage

Set-Sharing is Redundant for Pair-Sharing

Roberto Bagnara
Dipartimento di Matematica
Università di Parma
Via D'Azeglio, 85/A
I-43100 Parma
Italy

Patricia M. Hill
School of Computing
The University of Leeds
Leeds LS2 9JT
England

Enea Zaffanella
Dipartimento di Matematica
Università di Parma
Via D'Azeglio, 85/A
I-43100 Parma
Italy

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.