Patricia M. Hill
Abstract:We study the problem of an efficient and precise sharing analysis of (constraint) logic programs. After recognizing that neither plain Sharing nor its non-redundant (but equivalent) abstraction scale well to real programs, we consider the domain proposed by C. Fecht [1, 2]. This domain consists of a combination of Pos with a quite weak abstraction of Sharing. While verifying that this domain is truly remarkable, in terms of both precision and efficiency, we have revealed significant precision losses for several real programs. This loss concerns groundness, pair-sharing and linearity. We define a simple domain for sharing analysis that supports the implementation of several widening techniques. In particular, with this domain it is straightforward to turn Fecht's idea into a proper widening. More precise widenings are also considered. However, in spite of thorough experimentation we found that, provided Pos is included in the domain, the first widening we propose is hard to improve on.
Keywords: Abstract Interpretation, Mode Analysis, Sharing Analysis, Widening.
Available: PDF, 300 DPI, 600 DPI, and 1200 DPI PostScript, DVI, BibTeX entry.
[Page last updated on January 22, 2000, 20:38:36.]
Home | Personal | Papers | Teaching | Links