Theory and Practice of Logic Programming



Regular Papers

Enhanced sharing analysis techniques: a comprehensive evaluation


ROBERTO BAGNARA a1, ENEA ZAFFANELLA a1 1 and PATRICIA M. HILL a2 2
a1 Department of Mathematics, University of Parma, Parma, Italy (e-mail: bagnara@cs.unipr.it, zaffanella@cs.unipr.it)
a2 School of Computing, University of Leeds, Leeds, UK (e-mail: hill@comp.leeds.ac.uk)

Article author query
bagnara r   [Google Scholar] 
zaffanella e   [Google Scholar] 
hill pm   [Google Scholar] 
 

Abstract

$\textup{\textsf{Sharing}}$, an abstract domain developed by D. Jacobs and A. Langen for the analysis of logic programs, derives useful aliasing information. It is well-known that a commonly used core of techniques, such as the integration of $\textup{\textsf{Sharing}}$ with freeness and linearity information, can significantly improve the precision of the analysis. However, a number of other proposals for refined domain combinations have been circulating for years. One feature that is common to these proposals is that they do not seem to have undergone a thorough experimental evaluation even with respect to the expected precision gains. In this paper we experimentally evaluate: helping $\textup{\textsf{Sharing}}$ with the definitely ground variables found using $\textit{Pos}$, the domain of positive Boolean formulas; the incorporation of explicit structural information; a full implementation of the reduced product of $\textup{\textsf{Sharing}}$ and $\textit{Pos}$; the issue of reordering the bindings in the computation of the abstract $\mgu$; an original proposal for the addition of a new mode recording the set of variables that are deemed to be ground or free; a refined way of using linearity to improve the analysis; the recovery of hidden information in the combination of $\textup{\textsf{Sharing}}$ with freeness information. Finally, we discuss the issue of whether tracking compoundness allows the computation of more sharing information.


Key Words: abstract interpretation; logic programming; sharing analysis; experimental evaluation.


Footnotes

1 The work of the first and second authors has been partly supported by MURST projects “Certificazione automatica di programmi mediante interpretazione astratta” and “Interpretazione astratta, sistemi di tipo e analisi control-flow.”

2 This work was partly supported by EPSRC under grant GR/M05645.