Tech Report CS-91-67

Generic Abstract Interpretation Algorithms for Prolog: Two Optimization Techniques and Their Experimental Evaluation

Vincent Englebert, Baudouin Le Charlier, Didier Roland and Pascal Van Hentenryck

December 1991

Abstract:

The efficient implementation of generic abstract interpretation algorithms for Prolog is reconsidered. Two new optimization techniques are proposed and applied to the original algorithm of [15]: dependency on clause prefixes and caching of operations. The first improvement avoids reevaluating a clause prefix when no abstract value which it depends on has been updated. The second improvement consists of caching all operations on substitutions and reusing the results whenever possible. The algorithm together with the two optimization techniques have been implemented in $C$ (about 8000 lines of code each), tested on a large number of Prolog programs, and compared with the original implementation on an abstract domain containing modes, types, and sharing. In conjuction with refinements of the domain algorithms, they produce an average reduction of more than 58% in computation time. Extensive experimental results on the programs are given, including computation times, memory consumption, hit ratios for the caches, the number of operations performed, and the time distribution. As a main result, the improved algorithms exhibit the same efficiency as the specific tools of [29, 10], despite the fact that our abstract domain is more sophisticated and accurate. The abstract operations also take 90% of the computation time, indicating that the room left for improvement is very limited. Results on a simpler domain are also given and show that even extremely basic domains can benefit from the optimizations. The general-purpose character of the optimizations is also discussed.

(complete text in pdf)