L'ingénierie du logiciel doit concilier, d'une part, la modularité requise par les phases de développement et de maintenance et, d'autre part, l'efficacité indispensable dans la mise en oeuvre des applications. Ce dilemme nécessite des méthodes et des techniques de transformation permettant d'accroître l'efficacité des programmes modulaires. La déforestation, qui consiste à éliminer les structures intermédiaires apparaissant lors de la composition des différentes parties d'un programme, a suscité beaucoup d'intérêt, notamment en grammaires attribuées et en programmation fonctionnelle. En dépit de la diversité des formalismes utilisés, cette thèse compare les différentes techniques existantes et s'inspire de leurs atouts pour développer une nouvelle méthode de déforestation plus générale. Tout d'abord, une extension naturelle des grammaires attribuées est introduite pour permettre de représenter une plus large classe de programmes fonctionnels. Les grammaires attribuées dynamiques peuvent se passer de la présence physique d'un arbre pour guider les calculs et les transformations, mais bénéficient des méthodes classiques d'évaluation des grammaires attribuées. Ensuite, les principales méthodes fonctionnelles de déforestation (algorithme de Wadler, règle d'élimination foldr/build, normalisation des folds, fusion d'hylomorphismes) sont étudiées et comparées avec la composition descriptionnelle des grammaires attribuées. Les limitations de chaque méthode sont établies et permettent de déterminer les atouts nécessaires pour ces transformations de programmes. Finalement, une nouvelle méthode de déforestation est proposée. La composition symbolique utilise la puissance du formalisme des grammaires attribuées et incorpore un mécanisme d'évaluation partielle. Cette technique générale peut être appliquée sur des grammaires attribuées ou sur des programmes fonctionnels et permet de déforester des programmes pour lesquelles les méthodes existantes restaient impuissantes.

Une pression accrue s'exerce sur les compilateurs pour mettre en œuvre des transformations de programmes de plus en plus complexes délivrant le potentiel de performance des processeurs multicœurs et des accélérateurs hétérogènes. L'espace de recherche des optimisations de programmes possibles est gigantesque est manque de structure. La recherche de la meilleure transformation, qui inclut la prédiction des gains estimés de performance offerts par cette transformation, constitue le problème le plus difficiles pour les compilateurs optimisants modernes. Nous avons choisi de nous concentrer sur les transformations de boucles et sur leur automatisation, exprimées dans le modèle polyédrique. Les méthodes d'optimisation de programmes dans le modèle polyédrique se répartissent grossièrement en deux classes. La première repose sur l'optimisation linéaire d'une fonction de analytique de coût. La deuxième classe de méthodes met en œuvre une recherche itérative. La première approche est rapide, mais elle est facilement mise en défaut en ce qui concerne la découverte de la solution optimale. L'approche itérative est plus précise, mais le temps de compilation peut devenir prohibitif. Cette thèse contribue une approche nouvelle de la recherche itérative de transformations de programmes dans le modèle polyédrique. La nouvelle méthode proposée possède la précision et la capacité effective à extraire des transformations profitables des méthodes itératives, tout en en minimisant les faiblesses. Notre approche repose sur l'évaluation systématique d'une fonction de coût et de prédiction de performances non-linéaire. Par ailleurs, la parallélisation automatique dans le modèle polyédrique est actuellement dominée par des outils de compilation source-à-source. Nous avons choisi au contraire d'implémenter nos techniques dans la plateforme GCC, en opérant sur une représentation de code de bas niveau, à trois adresses. Nous montrons que le niveau d'abstraction de la représentation intermédiaire choisie engendre des difficultés de passage à l'échelle, et nous montrons comment les surmonter. À l'inverse, nous montrons qu'une représentation intermédiaire de bas niveau ouvre de nouveaux degrés de liberté, bénéficiant à notre stratégie itérative de recherche de transformations, et à la compilation polyédrique de manière générale. / In order to take the performance advantages of the current multicore and heterogeneous architectures the compilers are required to perform more and more complex program transformations. The search space of the possible program optimizations is huge and unstructured. Selecting the best transformation and predicting the potential performance benefits of that transformation is the major problem in today's optimizing compilers. The promising approach to handling the program optimizations is to focus on the automatic loop optimizations expressed in the polyhedral model. The current approaches for optimizing programs in the polyhedral model broadly fall into two classes. The first class of the methods is based on the linear optimization of the analytical cost function. The second class is based on the exhaustive iterative search. While the first approach is fast, it can easily miss the optimal solution. The iterative approach is more precise, but its running time might be prohibitively expensive. In this thesis we present a novel search-based approach to program transformations in the polyhedral model. The new method combines the benefits - effectiveness and precision - of the current approaches, while it tries to minimize their drawbacks. Our approach is based on enumerating the evaluations of the precise, nonlinear performance predicting cost-function. The current practice is to use the polyhedral model in the context of source-to-source compilers. We have implemented our techniques in a GCC framework that is based on the low level three address code representation. We show that the chosen level of abstraction for the intermediate representation poses scalability challenges, and we show the ways to overcome those problems. On the other hand, it is shown that the low level IR abstraction opens new degrees of freedom that are beneficial for the search-based transformation strategies and for the polyhedral compilation in general.