On Sparse Intermediate Representations: Some Structural Properties and Applications to Just-In-Time Compilation

Habilitation à diriger des recherches, École normale supérieure de LyonLa compilation pour processeurs embarqués peut prendre diverses formes, depuis la très agressive compilation "ahead-of-time" sur serveur pour laquelle les ressources sont très importantes, à la compilation "just-in-time" sur l'architecture cible elle-même et pour laquelle les ressources en temps/espace/puissance sont souvent assez limitées. Une compilation tardive qui est au coeur même de la virtualisation a aussi pour ambition d'exploiter dynamiquement des informations disponibles uniquement à l'exécution et ainsi d'effectuer certaines optimisations impossibles statiquement. C'est dans ce cadre, celui de la compilation dynamique sur processeur embarqué, que se situent mes recherches. Le but de cette habilitation est d'illustrer l'importance du choix des structures de données utilisées pour, dans ce contexte, effectuer des optimisations fiables et efficaces. En particulier, je m'attarde sur la description de certaines propriétés clés de la forme dite SSA (Static Single Assignment) qui ont permis de revisiter totalement certains problèmes classiques de compilation que sont l'allocation de registres et l'analyse de vivacité (liveness). J'en profite pour parler d'un domaine de recherche pour l'instant, à tort, sous-exploité en compilation, qu'est l'étiquetage de graphes (graph labelling). Dans le détail, mes contributions comprennent: - l'étude de propriétés fondamentales structurelles et sémantiques de la forme SSA; - la généralisation de certaines de ces propriétés à la forme SSI (Static single Information); - le développement de (nouveaux) algorithmes de construction et destruction pour les formes SSA et SSI; - le développement de nouveaux algorithmes pour l'analyse de vivacité des variables; - une étude approfondie de la complexité du problème de vidage en mémoire sous SSA (spilling); le développement d'un nouveau schéma de vidage en mémoire; - une étude approfondie de la complexité du problème d'agrégation de variable (coalescing) sous SSA; le développement de nouvelles heuristiques de coloriage généralisé (avec aliasing et pre-allocation); le développement d'une heuristique efficace dans le cadre de compilation dynamique; - un nouveau formalisme basé sur le recoloriage permettant de réordonnancer et éliminer des opérations de copies dans un code alloué