CR-08 : Compilation avancée

Programme de l’UE

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 (CFG, psi-SSA, dominance, loop-forest, etc.)
  • Analyse (dependances, durée de vie, alias, flot de données, interprétation abstraite — treillis, points fixes, étiquetage de graphe)
  • Transformations (fusion de boucles, pavage, data-layout, source-à-source, unimodulaire — ILP, graphes, polyèdres, réseaux)
  • Allocation de registres (assignation vs allocation, vidage en mémoire, coalescing — graphes, optimisation combinatoire, LP)
  • Ordonnancement (ordonnancement, pipeline logiciel — ILP, approximabilité, retiming)

Calendrier prévisionnel

12/09, 17/09, 19/09 [de 16h à 18h]

Intervenants

  • Alain Darte, DR CNRS
  • NN