Previous Up Next

Compilation avancée et optimisation de programmes

Cours de recherche (30h de cours, travail sur des articles scientifiques)

Cours : Fabrice Rastello, Alain Darte (Fabrice.Rastello, Alain.Darte)



Présentation générale
Un compilateur n'est autre qu'un traducteur d'un langage (par exemple C ou Caml) vers un autre (par exemple un langage assembleur). Bien entendu, les langages de programmation sont dotés de propriétés sympathiques (par exemple grâce aux grammaires LALR) qui font que les traductions des compilateurs sont, heureusement, nettement plus convaincantes que celles d'un traducteur de langage naturel comme Babel Fish! On ne s'intéressera pas dans ce cours à ces problèmes de traduction, aujourd'hui bien maîtrisés.

Aujourd'hui, on demande bien plus à un compilateur, on veut qu'il génère du code non seulement correct (traduction) mais aussi efficace pour l'architecture cible (compilateur optimisant). Écrire "from scratch" un compilateur pour un processeur spécifique prend plusieurs années pour une équipe d'ingénieurs et, avec la pression du marché ("time-to-market") et l'évolution rapide des processeurs, cette approche n'est pas viable. On préfère produire des compilateurs dits reciblables, optimisants, pour une gamme de processeurs.

La difficulté et l'intérêt (du point de vue du chercheur) résident dans la mise au point d'optimisations. On souhaite que le code soit rapide, qu'il génère le moins de trafic mémoire possible, qu'il consomme peu, qu'il soit compact, etc. En pratique, une optimisation est une recette de cuisine pour transformer, améliorer le code, enrichir l'information que l'on a de celui-ci. Les recettes de cuisine sont bien entendu plus ou moins sophistiquées et coûteuses, et la difficulté pour l'ingénieur-cuisinier est de les faire cohabiter et de les utiliser à bon escient. Ainsi, la compilation est avant tout un problème d'ingénierie (certes d'experts) où la difficulté réside dans le choix des représentations intermédiaires du code et des informations qui lui sont associées: la représentation intermédiaire permet ou non d'exprimer trivialement certaines propriétés, ce qui influence considérablement l'implémentabilité de tel ou tel outil d'analyse.

On verra entre autres que les outils "mathématiques" nécessaires aux optimisations en compilation sont relativement divers (théorie des graphes, propriétés de treillis, programmation linéaire, ordonnancement) selon les représentations intermédiaires (graphe de flot de contrôle, forme SSA, forme psi-SSA, boucles imbriquées), les niveaux d'abstraction du code (code source ou code assembleur), et les fonctionnalités architecturales (instructions avec prédicats, registres). Le but de ce cours sera donc de décrire un certain nombre de phases d'analyses et de transformations relativement classiques et d'en profiter pour donner un aperçu des outils utilisés par le chercheur en optimisation de programmes.

Contenu du cours (indicatif)
Les thèmes suivants seront traités:
Représentations intermédiaires
CFG, psi-SSA, dominance, loop-forest, etc.

Analyses
dépendances, durée de vie, alias, flot de données: treillis, points fixes

Transformations
fusion de boucles, pavage, contraction de tableaux: ILP, graphes, polyèdres, "lattices"

Allocation de registres
affectation et allocation, vidage en mémoire, "coalescing": graphes, optimisation combinatoire, LP

Ordonnancement
DAG, pipeline logiciel: ILP, approximabilité, retiming

Domaines d'application
compilation parallèle, processeurs VLIW, compilation dynamique et bytecode Java, synthèse de circuits
Note: Benoît Dupont de Dinechin (STMicroelectronics) interviendra probablement lors d'un cours pour présenter les enjeux actuels de son équipe de compilation.

Acronymes:
Bibliographie
Architecture


Compilation et parallélisation automatique


Ordonnancement
Previous Up Next