DIFFERENTIAL METHODS IN LOGIC PROGRAM ANALYSIS

Program analysis based on abstract interpretation has proven very usef ul in compilation of constraint and logic programming languages. Unfor tunately, the traditional goal-dependent framework is inherently impre cise. This is because it handles call and return in such a way that da taflow information may be re-asserted unnecessarily, leading to a loss of precision for many description domains. For a few specific domains , the literature contains proposals to overcome the problem, and some implementations use various unpublished tricks that sometimes avoid th e precision loss. The purpose of this paper is to map the landscape of goal-dependent, goal-independent, and combined approaches to generic analysis of logic programs. This includes formalising existing methods and tricks in a way that is independent of specific description domai ns. Moreover, we suggest new methods for overcoming the loss of precis ion - altogether eight different semantics are considered and compared . We provide theoretical results determining the relative accuracy of the approaches. These show that two of our new semantics are uniformly more accurate than existing approaches. Experiments that we have perf ormed (for two description domains) with implementations of the eight different approaches enable a discussion of their relative runtime per formances. We discuss the expected effect on other domains as well and conclude that our new methods can be trusted to yield significantly m ore accurate analysis for a small extra implementation effort, without compromising the efficiency of analysis. (C) 1998 Elsevier Science In c. All rights reserved.