Roberto, Margherita and Beatrice


Personal Info




Widening Sharing

Enea Zaffanella
Servizio IX Automazione
Università di Modena

Roberto Bagnara
Dipartimento di Matematica e Informatica
Università di Parma
Parco Area delle Scienze 53/A
I-43124 Parma

Patricia M. Hill
School of Computer Studies
University of Leeds
Leeds, LS2 9JT
United Kingdom


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, linearity, but not freeness. (Indeed, we have proved that a wide family of abstractions of Sharing do not incur precision loss on freeness.) 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 the first widening we propose is hard to improve on, provided Pos is included in the domain. We show that when Pos is not included, a widening based on cliques of sharing pairs is preferred.

Keywords: Mode Analysis, Sharing Analysis, Widening.


C. Fecht.
An efficient and precise sharing domain for logic programs.
In H. Kuchen and S. D. Swierstra, editors, Programming Languages: Implementations, Logics and Programs, Proceedings of the Eighth International Symposium, volume 1140 of Lecture Notes in Computer Science, pages 469--470, Aachen, Germany, 1996. Springer-Verlag, Berlin.

C. Fecht.
Efficient and precise sharing domains for logic programs.
Technical Report A/04/96, Universität des Saarlandes, Fachbereich 14 Informatik, Saarbrücken, Germany, 1996.

Available: PDF, 300 DPI, 600 DPI, and 1200 DPI PostScript, DVI, BibTeX entry.

[Page last updated on January 22, 2000, 20:38:36.]

© Roberto Bagnara

Home | Personal | Papers | Teaching | Links