Allocation de registres |
Le sujet est donné par l’archive td8.tar.gz.
La qualité du code produit par un compilateur dépend beaucoup de la qualité de l’allocation de registres. On cherche à minimiser d’une part le temps passé à accéder à la pile, d’autre part l’espace alloué sur la pile. Pour cela, nous allons résoudre deux problèmes de coloriage de graphe.
Le premier problème est traité dans le fichier coloring.ml. Consultez son interface coloring.mli. Le problème consiste à construire un coloriage du graphe. Un coloriage (coloring) est défini comme une table (map) qui à chaque sommet du graphe d’interférences associe une décision. Une décision est soit Spill, si le pseudo-registre concerné doit être représenté par un emplacement de pile, soit Color hwr, si ce pseudo-registre doit être représenté par le registre physique hwr.
Une fois ce premier problème résolu, reste à décider, pour chaque sommet qui a reçu la décision Spill, quel emplacement de pile utiliser; et combien d’emplacements de pile sont nécessaires en tout. Ce second problème est traité dans le fichier spill.ml. Consultez son interface spill.mli. Celle-ci est analogue, à ceci près que cette fois, une décision est simplement un «offset», qui représente un emplacement de pile dans la zone des données locales.
Les fichiers coloring.ml et spill.ml sont incomplets. À vous de les compléter pour obtenir un compilateur en état de marche.
Complétez le code de coloring.ml. Il faut écrire les fonctions forbidden_colors et simplification.
Ici, l’ensemble des couleurs permises est fini. On appliquera l’algorithme de coloriage optimiste de Briggs.
L’ensemble des couleurs permises est colors. Il s’agit d’une simple abréviation pour MIPS.allocatable. De même, ColorSet est ici une abréviation pour MIPS.RegisterSet.
Vous aurez besoin des fonctions iph, ipp, remove et lowest du module Interference. La fonction ColorSet.choose vous permettra de choisir arbitrairement une couleur parmi un ensemble non vide.
On notera que si on choisit toujours le sommet de plus faible degré, alors l’algorithme de Briggs se simplifie. Il n’est plus nécessaire de tester si ce sommet est trivialement colorable ou non, car dans les deux cas, on procède de la même manière: construire le graphe privé de ce sommet, colorier ce graphe, puis déterminer si on peut colorier ce sommet.
Complétez le code de spill.ml. Il faut écrire les fonctions forbidden_slots, coalescing et simplification.
Ici, l’ensemble des couleurs permises est infini, puisqu’on dispose d’autant d’emplacements de pile qu’on le souhaite. Les sommets de très haut degré ne posent donc pas de problème particulier. Ceci nous amène à effectuer une fusion («coalescing») agressive des sommets reliés par des arêtes de préférence.
S’il existe une arête de préférence, coalescing fusionnera cette arête puis s’appellera récursivement, pour continuer la fusion; sinon, coalescing appellera simplification.
La fonction simplification effectuera un coloriage en temps linéaire, à la Chaitin. Le graphe est toujours colorable, puisque le nombre de couleurs est non borné. La fonction allocate_slot, fournie, produit une couleur hors d’un ensemble fini donné.
Vous aurez besoin des fonctions ipp, remove, lowest, pppick et coalesce du module Interference. Attention: la fonction coalesce produit un graphe où ne reste qu’un seul des deux sommets passés en argument, à savoir le deuxième. L’appel récursif à coalescing produira donc un coloriage qui ne concerne que ce deuxième sommet, et il restera à colorier le premier.
Vous pouvez désormais tester votre compilateur avec make test ou make ltl.
Le compilateur fonctionne à présent, mais produit du code de mauvaise qualité. En effet, notre implémentation de Coloring ignore totalement les arêtes de préférence.
Après avoir fait make test, vous pouvez faire une copie de tout votre répertoire. Vous pourrez ensuite comparer le code produit par votre compilateur sans et avec les optimisations qui suivent.
# cp -r td8 td8-simple # (cd td8-simple/test && for i in *.spi ; do diff $i ../../td8/test/$i ; done)
On souhaite fusionner les deux extrémités d’une arête de préférence lorsque cela est permis par le critère de George. La phase de fusion commence après la simplification, car la simplification peut créer des opportunités de fusion.
La fonction simplification simplifiera un sommet de bas degré, s’il en existe un; sinon, elle passera la main à la fonction coalescing.
La fonction coalescing fusionnera une arête de préférence qui satisfait le critère de George, s’il en existe une, puis passera la main à simplification; sinon, elle passera à la fonction spilling, qui choisira un sommet et le considérera comme potentiellement «spillé».
Vous aurez donc trois fonctions mutuellement récursives: simplification, coalescing, spilling.
Vous aurez besoin des fonctions pppick, coalesce, phpick, et coalesceh du module Interference. Les fonctions qui implémentent le critère de George sont georgepp et georgeph.
Ci-dessus, on a effectué la simplification avant la fusion, au prétexte que la simplification peut créer des opportunités de fusion. C’est vrai; mais cela signifie que tant qu’il existe des sommets simplifiables, on n’effectue aucune fusion, donc on ignore les arêtes de préférence. Ce n’est pas très bon.
Pour remédier à cela, Appel et George restreignent la phase de simplification pour ne simplifier que des sommets qui ne portent aucune arête de préférence.
Par ailleurs, à la fin de la phase de fusion, donc dans la fonction coalescing, lorsqu’on constate que plus aucune fusion n’est possible, au lieu de passer directement au «spilling», on cherche d’abord s’il existe un sommet de bas degré portant une arête de préférence; si oui, on supprime cette arête et on passe la main à simplification; sinon, alors on passe au «spilling».
Vous aurez besoin de la fonction lowest_non_move_related du module Interference.
Lorsque ni simplification, ni fusion, ni dégel ne sont possible, il faut choisir un sommet pour un «spill» potentiel. Jusqu’ici, nous avons choisi ce sommet de façon arbitraire. En pratique, il est souhaitable de choisir un pseudo-registre qui sert peu dans le code, et dont le degré est élevé.
Définissez une fonction de coût qui reflète cela, et faites en sorte que le sommet choisi soit un sommet de moindre coût.
Vous utiliserez la fonction minimum du module Interference.
Ce document a été traduit de LATEX par HEVEA