Variables d'induction généralisées pour l'analyse par instances de programmes récursifs
Résumé
La sophistication croissante des microprocesseurs et des architectures ouvre la voie de nouvelles techniques d'optimisation dont il est souhaitable de décharger le programmeur. La parallélisation automatique consiste en une phase préalable d'analyse des dépendances, suivie de l'extraction du parallélisme puis de la génération du code parallèle. Nous nous attachons à des programmes, éventuellement récursifs, qui manipulent des structures de données combinant arbres et tableaux. Ce rapport a pour objet le calcul statique, c.-à-d. lors de la compilation, des adresses dans les structures de données. Ces adresses sont les informations de base pour l'analyse de dépendances. Nous introduisons le concept de \textitvariable d'induction généralisée, qui étend la notion classique attachée aux nids de boucles. Ce concept formalise le suivi des adresses au travers d'un balisage original de l'exécution. Ainsi, nous dégageons la notion d'instance pour nommer avec exactitude une instruction au cours de l'exécution. L'analyse par instances conjugue la finesse des traces d'exécution et la richesse du formalisme des langages réguliers. Nous présentons ici un modèle de programme qui permet le calcul exact de l'adressage pour chaque instance. Deux technique- s sont exposées, en étroite référence à la théorie des automates finis. La première est développée sous forme matricielle, tandis que la seconde fait appel à la théorie des transducteurs.