Determination of variable dependence information at compile-time through abstract interpretation

Abstract

Traditional schemes for abstract interpretation-based global analysis of logic
programs generally focus on obtaining procedure argument mode and type
information. Variable sharing information is often given only the attention
needed to preserve the correctness of the analysis. However, such sharing
information can be very useful. In particular, it can be used for predicting
run-time goal independence, which can eliminate costly run-time checks in
and-parallel execution. In this paper, a new algorithm for doing abstract
interpretation in logic programs is described which infers the dependencies
of the terms bound to program variables with increased precision and at all
points in the execution of the program, rather than just at a procedure level.
Algorithms are presented for computing abstract entry and success substitutions which extensively keep track of variable aliasing and term dependence
information. The algorithms are illustrated with examples.