Purpose

This module calculates the data dependences occurring in the source program. The analysis is based on the method by U. Banerjee [Ban93], but extends it in several aspects. The most important extensions are:

• The dimension of the non-empty polytope describing all integer solutions for the vector t is no longer restricted to 0 or 1. It is now possible to handle polytopes of any dimensionality.
• The loops need not be nested perfectly; imperfectly nested loops can be handled.
• All methods can deal with structure parameters.

The tool computes the set of all memory conflicts representing them by the so called h-transformation which was introduced by P. Feautrier [Fea91]. Banerjee's methods do not calculate the precise flow of data but compute all pairs of operations with conflicting accesses to the same memory cell. Therefore, it might become necessary to introduce new parameters (pseudo parameters) in order to represent sets of h-transformations. A detailed description of the analysis can be found in [Kei96] (text in German).