Abstract FR:

Les methodes de resolution des systemes de contrainte aux collisions, elabores pour detecter les dependances entre instructions partageant une variable indicee, reposent sur l'hypothese de linearite de ces systemes. Nous proposons une methode pour lever en partie cette hypothese dans les etudes de dependances intra nid de boucles comme inter nids. L'examen des contextes de programmation les plus courants, conduisant a des systemes de contrainte aux collisions non lineaires, nous permet de constater que les expressions non lineaires sont en general des fonctions des compte-tours des boucles et des parametres de structure du programme. Il est possible de les lineariser en substituant les termes non lineaires par des symboles sur lesquels des contraintes peuvent etre introduites, d'une part a l'aide d'une base de regles de production de contraintes selon la forme du terme et d'un bloc-notes, d'autre part en etudiant leur difference entre deux iterations d'une boucle. Une fois ces expressions linearisees, le systeme de contrainte aux collisions peut-etre resolu par les algorithmes habituels. Cette methode est d'abord developpee pour etudier les dependances intra nids de boucles, puis etendue aux etudes inter nids de boucles que nous ramenons par la construction d'un nid de boucle virtuel commun a une etude intra nid. Son application demande dans tous les cas la mise sous forme canonique du programme qui est realisee dans une phase prealable plus generale de prenormalisation