Optimisation de programmes par reconnaissance de templates

Most compiler optimizations apply local transformations on the code, without knowing the computation expressed by the program. Despite the performance obtained, the best the solution remains to call hand-optimized libraries. Learning and using a performance is a fastidious and bug-prone task. In this thesis, we propose to deleguate this task to the compiler. Given a program, this thesis propose a compiler algorithm able to (i) recognize programs slices realizing an algorithm and to (ii) substitute a program slice by a call to a performance library whenever it is possible and profitable. Ouralgorithm is able to detect all the program slice equivalent to the seeked algorithm with respect to Herbrand equivalence, a subset of program equivalence which ignore semantic properties of arithmetic operators. In addition to functions, we are able to find template instances in a program. Such a feature makes possible to find call sites to a template library. Our approach has been implementd in the tool TeMa (Template Matcher) and applied to the detection of functions from the BLAS library (Basic Linear Algebra Subroutines) in the kernels from the benchmarks SpecFP 2000 et Perfect Club. In particular, experimental results show a substantial speedup on the kernels swim, mgrid and applu.La plupart des optimisations de compilateur appliquent des transformations locales bas-niveau, sans se soucier du calcul exprimé par le programme. Malgré les performances obtenues, la meilleure solution est encore de faire appel à une bibliothèque optimisée écrite par un spécialiste du domaine. Apprendre et utiliser une bibliothèque est une tâche fastidieuse. Dans cette thèse, nous proposons de déléguer cette tâche au compilateur. Etant donné un programme écrit de manière naïve, cette thèse propose une heuristique capable de (i) reconnaître les parties de programme réalisant un algorithme et de (ii) substituer, lorsque c'est possible et profitable chaque partie reconnue par un appel vers la bibliothèque optimisée. Notre méthode est capable de détecter toutes les tranches de programme équivalentes aux fonctions recherchées au sens de l'équivalence de Herbrand, un sous-ensemble de l'équivalence sémantique qui ne tient pas compte de la sémantique des opérations atomiques. En plus des fonctions, nous sommes capables de trouver des instances de templates dans un programme. Une telle caractéristique rend possible la reconnaissance de bibliothèques de templates, et la réécriture d'un programme pour utiliser des templates. Notre approche a été implémentée dans l'outil TeMa (Template Matcher) et appliquée à la détection des fonctions de la bibliothèque BLAS (Basic Linear Algebra Subroutines) dans les noyaux des benchmarks SpecFP 2000 et Perfect Club. Les résultatsexpérimentaux montrent un facteur d'accélération substantiel sur les noyaux swim, mgrid et mdg