Thèse

Résumé de ma thèse

Le but de l’allocation de registres est d’assigner les variables d’un programme aux registres ou de les « spiller » en mémoire s’il n’y a plus de registre disponible. La mémoire est bien plus lente, il est donc préférable de minimiser le spilling. Ce problème est difficile car il est étroitement lié à la colorabilité du programme. Chaitin et al. [1981] ont modélisé l’allocation de registres en le coloriage du graphe d’interférence, qu’ils ont prouvé NP-complet, il n’y a donc pas dans ce modèle de test exact qui indique s’il est nécessaire ou non de faire du spill, et si oui quoi spiller et où. Dans l’algorithme de Chaitin et al., une variable spillée est supprimée dans tout le programme, ce qui est inefficace aux endroits où suffisamment de registres sont encore disponibles.

Pour palier ce problème, de nombreux auteurs ont remarqué que l’on peut couper les intervalles de vie des variables grâce à l’insertion d’instructions de copies, ce qui crée des plus petits intervalles et permet de spiller les variables sur des domaines plus réduits. La difficulté est alors de choisir les bons endroits où couper les intervalles. En pratique, on obtient de meilleurs résultats si les intervalles sont coupés en de très nombreux points [Briggs, 1992; Appel and George, 2001], on attend alors du coalescing qu’il enlève la plupart de ces copies, mais s’il échoue, le bénéfice d’avoir un meilleur spill peut être annulé. C’est pour cette raison que Appel and George [2001] ont créé le « Coalescing Challenge ».

Récemment (2004), trois équipes ont découvert que le graphe d’interférence d’un programme sous la forme Static Single Assignment (SSA) sont cordaux. Colorier le graphe devient alors facile avec un schéma d’élimination simpliciel et la communauté se demande si SSA simplifie l’allocation de registres. Nos espoirs étaient que, comme l’était le coloriage, le spilling et le coalescing deviennent plus facilement résolubles puisque nous avons à présent un test de coloriage exact.

Notre premier but a alors été de mieux comprendre d’où venait la complexité de l’allocation de registres, et pourquoi le SSA semble simplifier le problème. Nous sommes revenus à la preuve originelle de Chaitin et al. [1981] pour mettre en évidence que la difficulté vient de la présence d’arcs critiques et de la possibilité d’effectuer des permutations de couleurs ou non. Nous avons étudié le problème du spill sous SSA et différentes versions du problème de coalescing : les cas généraux sont NP-complets mais nous avons trouvé un résultat polynomial pour le coalescing incrémental sous SSA. Nous nous en sommes servis pour élaborer de nouvelles heuristiques plus efficaces pour le problème du coalescing, ce qui permet l’utilisation d’un découpage agressif des intervalles de vie.

Ceci nous a conduit à recommander un meilleur schéma pour l’allocation de registres. Alors que les tentatives précédentes donnaient des résultats mitigés, notre coalescing amélioré permet de séparer proprement l’allocation de registres en deux phases indépendantes : premièrement, spiller pour réduire la pression registre, en coupant potentiellement de nombreuses fois ; deuxièmement, colorier les variables et appliquer le coalescing pour supprimer le plus de copies possible.

Ce schéma devrait être très efficace dans un compilateur de type agressif, cependant, le grand nombre de coupes et l’augmentation du temps de compilation nécessaire pour l’exécution du coalescing sont prohibitifs à l’utilisation dans un cadre de compilation just-in-time (JIT). Nous avons donc créé une nouvelle heuristique appelée « déplacement de permutation », faite pour être utilisée avec un découpage selon SSA, qui puisse remplacer notre coalescing dans ce contexte.

Mots-clés

Compilation, allocation de registres, SSA, spilling, coalescing, complexité.

Résumé de la soutenance

Durant la compilation d'un programme, l'allocation de registres a pour but d'assigner les variables du programme aux registres (rapides), où à des emplacements mémoire (lents). Traditionnellement, les algorithmes à base de graphes utilisent le graphe d'interférence des variables pour déterminer si deux variables peuvent partager le même registre. Dans ce modèle, l'allocation de registres est un problème NP-complet car il s'apparente à de la coloration de graphe. La récente découverte que, sous SSA (représentation intermédiaire du programme), le graphe d'interférence est chordal, donc facilement colorable, nous a amenés à reconsidérer l'allocation de registres. Durant cette soutenance, nous exposerons une partie des travaux effectués durant la thèse. Nous nous proposons d'expliquer en premier lieu en quoi cette découverte nous a poussés à repenser l'allocation de registres en deux phases. Alors que traditionnellement une seule phase est utilisée, nous recommandons de séparer le spilling (allocation de variables en mémoire) du coloring (assignation des variables restantes aux registres). Ensuite, nous exposerons le problème du coalescing, dont le but et d'assigner des variables différentes aux même registres pour éviter des instructions de copies inutiles. Nous détaillerons pour ce problème le cas où le graphe d'interférence est chordal et où l'on cherche à coalescer deux variables. La question est alors de savoir, étant donné un graphe chordal, si deux noeuds donnés peuvent être coloriés de la même couleur sans augmenter le nombre de couleurs nécessaires. Ce problème est polynomial et nous vous présenterons un algorithme pour le résoudre.