Generic abstract interpretation algorithms for prolog: Two optimization techniques and their experimental evaluation

The efficient implementation of generic abstract interpretation algorithms for Prolog is reconsidered after [12, 14]. Two new optimization techniques are proposed and applied to the original algorithm of [12]: 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, patterns and sharing. In conjunction with refinments 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, 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 [26, 8], 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.