Tech Report CS-91-55

Experimental Evaluation of a Generic Abstract Interpretation Algorithm for Prolog

Baudouin Le Charlier and Pascal Van Hentenryck

August 1991

Abstract:

Abstract interpretation of Prolog programs has attracted many researchers in recent years partly because of the potential for optimization in Prolog compilers and partly because of the declarative nature of logic programming languages which make them more amenable to optimization. Most of the work, however, has remained at the theoretical level, focusing on the developments of frameworks and the definition of abstract domains.

This paper reports our effort to verify experimentally the practical value of this area of research. It describes the design and implementation of the generic abstract interpretation algorithm that we originally proposed in [15], its instantiation to a sophisticated abstract domain (derived from [4]) containing modes, types, sharing, and aliasing, and its evaluation both in terms of performance and accuracy. The overall implementation (over 5000 lines of PASCAL) has been systematically analyzed on a variety of programs and has been compared with the complexity analysis of [15] and the specific analysis systems of [28]. The experimental results, given the abstract domain and the programs analyzed, indicate that (1) the number of iterations of the algorithm is bounded by $7.5 * N$ and is in most cases smaller than $3 * N$, where $N$ is the size of the program analyzed (e.g. the number of program points); (2) the CPU time in seconds is bounded by $N$ and is in most cases smaller than $0.6 * N$; (3) the algorithm explores few elements (less than 11% and often none) outside the subset of the fixpoint required to answer the query and hence is close to optimality; (4) the results are quite accurate and could be used in a Prolog compiler; (5) the performance and accuracy results compare well to the specific tools proposed in [28].