Efficient and precise sharing domains for logic programs
Christian Fecht · 1996
Sharing information between logical variables is crucial for a lot of analyses of logic programs, e.g., freeness analysis, detection of And-parallelism, and occurcheck. Therefore, the development of accurate sharing domains has attracted a lot of research. The sharing domain JL of Jacobs/Langen, which represents substitutions by powersets of variables, is considered one of the most precise sharing domains. However, it is too inefficient in practice; lots of programs cannot be analyzed in reasonable time. Improvements of JL, by adding auxiliary information like linearity, suffer from the same inefficiency, too. To improve upon this situation, we systematically derived a new sharing domain #JL from JL which represents variables by downward closed powersets of variables. We combined #JL with the groundness domain POS. Both JL and the new domain #JL+POS have been implemented with the help of the Prolog analyzer generator GENA. In order to study the impact of linearity, we also implemented the abstract domains JL+LIN and #JL+POS+LIN. The new domains are much more efficient as their counterparts JL and JL+LIN, respectively. Even more important, they can analyze even largest real-world programs in reasonable time. Surprisingly, the new sharing domains seem to have the same precision than JL and JL+LIN in practice.