Enhanced Sharing Analysis Techniques: A Comprehensive Evaluation
Roberto Bagnara, Enea Zaffanella and Patricia M. Hill
To appear at the 2nd International Conference on Principles and Practice of
Declarative Programming (PPDP 2000), Montreal, Canada, September 20-22, 2000
Abstract
Sharing, a domain due to Jacobs and 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 standard integration
of Sharing with freeness and linearity information, can significantly
improve the precision of Sharing. 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 experimental evaluation even with respect
to the expected precision gains. In this paper, we discuss and/or
experimentally evaluate: helping Sharing with definitely ground
variables computed with Pos; the incorporation of explicit structural
information into the domain of analysis; more sophisticated ways of
integrating Sharing and Pos; the issue of reordering the bindings in
the computation of the abstract mgu; an original proposal concerning
the addition of a domain recording the set of variables that are
deemed to be ground or free; a more refined way of using linearity to
improve the analysis; the issue of whether tracking compoundness
allows to compute more precise sharing information; and, finally, the
recovery of hidden information in the combination of Sharing with the
usual domain for freeness.