MINIMAL DATA DEPENDENCE ABSTRACTIONS FOR LOOP TRANSFORMATIONS - EXTENDED VERSION

Many abstractions of program dependences have already been proposed, s uch as the Dependence Distance, the Dependence Direction Vector, the D ependence Level or the Dependence Cone. These different abstractions h ave different precisions. The minimal abstraction associated to a tran sformation is the abstraction that contains the minimal amount of info rmation necessary to decide when such a transformation is legal. Minim al abstractions for loop reordering and unimodular transformations are presented. As an example, the dependence cone, which approximates dep endences by a convex cone of the dependence distance vectors, is the m inimal abstraction for unimodular transformations. It also contains en ough information for legally applying all loop reordering transformati ons and finding the same set of valid mono- and multi-dimensional line ar schedules as the dependence distance set.