Compilation des arbres : Représentation mémoire et modèle polyédrique

Le modèle polyédrique est un framework algébrique qui permet une optimisation efficace des programmes de calculs intensifs. Ce domaine de recherche a été un domaine de recherche prolifique depuis sa création. Cependant, ses hypothèses fortes sur la forme du flot de contrôle et des accès mémoires rendent son application assez limitée en pratique, même si de nombreux efforts ont été faits pour l'étendre, principalement en autorisant des programmes avec des flots de contrôle plus complexes. Dans cette thèse, nous proposons d'explorer deux directions de recherche afin de traiter un flot de contrôle et des accès mémoires de forme arbitraire, et de cibler d'autres structures de données que les tableaux. Notre première contribution est une reformulation sémantique du modèle polyédrique qui répond partiellement à la première question et qui pourrait servir de base mathématique pour des résultats plus fins sur les extensions possibles de la portée du modèle. Cette contribution met en évidence les propriétés statiques des programmes utilisées par les algorithmes polyédriques.Notre deuxième contribution traite des types de données algébriques, tels que les arbres, qui, s'ils ne sont pas aussi courants que les tableaux dans les programmes scientifiques, sont omniprésents dans de nombreux algorithmes. Nous proposons un schéma de compilation pour ces types de donnée, en les représentant en mémoire selon une disposition fixe. Les mouvements en mémoire sont caractérisés dans le style du modèle polyédrique, ce qui permet une génération de code C optimisée. En résumé, cette thèse contribue à la recherche en cours sur le modèle polyédrique sur deux points : en donnant un autre point de vue sur les programmes polyédriques et en explorant comment les types de données algébriques pourraient réutiliser les idées du cadre.The polyhedral model is a algebraic-based framework which enables efficient code optimization for computer-intensive programs which has been a prolific area of research since its inception. However, its strong assumptions about the shape of the control flow and memory accesses makes its application quite narrow in practice, even if many efforts have been done to extend it, mostly in the direction of more complex control-flow.In this thesis, we propose to explore two research directions in order to deal with arbitrary control flow and memory pattern accesses, and target other data structures than arrays. Our first contribution is a semantic-based rephrasing of the framework that partially answers the first question and could sustain more in-depth research on the extension of the scope of the model to encompass "almost polyhedral programs". This contribution highlights the static program properties used by the polyhedral algorithms.Our second contribution deals with algebraic data types, such as trees, which are, if not as common as arrays in scientific programs, ubiquitous in many algorithms. We propose a compilation scheme for algebraic data types laid out in memory according to a fixed layout. Memory movements are characterized "in the polyhedral model style" which enables optimized C code generation. All in all, this thesis contributes to the on-going research of the polyhedral model on two points: by giving another point of view of polyhedral programs and by exploring how algebraic data types could reuse ideas from the framework