Monash University

We report on a detailed study of the application and eectiveness of program analysis based on abstract interpretation to automatic program parallelization. We study the case of parallelizing logic programs using the notion of strict independence. We rst propose and prove correct a interpretation, using a parametric domain. The methodology is generic in the sense of allowing the use of dierent analysis domains. A number of well-known approximation domains are then studied and the transformation into the parametric domain dened. The transformation directly illustrates the relevance and applicability of each abstract domain for the application. Both local and global analyzers are then built using these domains and embedded in a complete parallelizing compiler. Then, the performance of the domains in this context is assessed through a number of experiments. A comparatively wide range of aspects is studied, from the resources needed by the analyzers in terms of time and memory to the actual benets obtained from the information inferred. Such benets are evaluated both in terms of the characteristics of the parallelized code and of the actual speedups obtained from it. The results show that data ow analysis plays an important role in achieving ecient parallelizations, and that the cost of such analysis ca