High Precision Sharing Analysis

Accurate variable sharing information is crucial both in the automatic

parallelisation and in the optimisation of sequential logic programs.

Analysis for variable sharing and term-dependence is thus an

importance topic and many analyses have been proposed for inferring

dependencies between the variables of a logic program. In this paper,

a new approach to sharing analysis is described which infers sharing

information to a much higher degree of accuracy than that of previous

proposals. The analysis is founded on abstract substitutions which

elegantly encode structural properties of substitutions. This enables

the synergistic relationship between sharing and type information to

be better exploited. The approach does not define a single analysis,

as such, by in fact defines a framework for combining and refining

existing analyses and deriving new analyses. Furthermore, in addition

to defining new analyses, it simplifies the task of justifying an

analysis. To illustrate, several new and powerful analyses are

derived and proven safe in a way which is neat and concise. The

usefulness of the analyses is demonstrated with examples.