Allocation de registres |
Les sources sont dans l’archive td8-coloring.tar.gz, on construit l’exécutable avec la commande make.
L’allocation de registres est un des modules les plus importants du compilateur, parce que la qualité du code produit dépendra beaucoup de la qualité de l’allocation de registres. On cherche donc à minimiser le nombre de registres sauvegardés en pile (code plus efficace en temps), et à utiliser pour ceux-ci un nombre minimum d’emplacements de pile (code plus efficace en espace).
Cela conduit à plusieurs types de coloriages différents, pour lesquels vous allez implémenter successivement des algorithmes de plus en plus efficaces (et de plus en plus complexes).
Vous allez compléter les squelettes de code donnés dans coloring.ml et spill.ml afin de satisfaire les spécifications correspondantes coloring.mli et spill.mli, qui définissent :
(* dans coloring.mli *) type decision = Spill Color of MIPS.register (* dans spill.mli *) type decision = MIPSOps.offset (* dans les deux cas *) type coloring = decision Interference.Vertex.Map.t
Une decision associée à une variable (ou pseudo-registre) v correspond à un choix :
Un coloring est une table d’association qui associe les variables du programme à des decision.
Dans la suite, le degré d’une variable est le nombre d’arêtes d’interférences liées à cette variable.
Le but du TD est de construire des coloring appropriés.
On s’intéresse d’abord à l’allocation de registres physiques, puis à l’allocation d’emplacements de pile.
Vous aurez besoin des fonctions définies dans interference.mli.
Vous allez compléter le code de coloring.ml. Lors de l’allocation de registres, on est limité par le nombre de registres disponibles, ici MIPS.allocatable. On applique donc un coloriage glouton sur un ensemble de couleurs fini.
colorier (graph) =
choisir une variable v avec le degré minimum
allouer (graph, v)
allouer (graph, v)
colorier (graph \ v)
déterminer les couleurs possibles pour v
si aucune couleur possible
alors
allouer v sur la pile
sinon
choisir une couleur c pour v
Vous aurez besoin des fonctions iph, ipp, remove, lowest et choose du module Interference. On vous demande d’implémenter les fonctions suivantes, où la fonction simplification correspond à colorier dans l’algorithme, et la fonction selection correspond à allouer.
let forbidden_colors (graph : Interference.graph) (coloring : coloring) (v : Register.t) : ColorSet.t = ... let simplification (graph : Interference.graph) : coloring = ... let selection (graph : Interference.graph) (v : Vertex.t) : coloring = ...
Vous allez compléter le code de spill.ml. Lors de l’allocation d’emplacements de pile, on peut considérer que le nombre d’emplacements possibles est infini. Les variables avec de nombreuses interférences ne posent pas de problème ici. Cela nous amène à optimiser l’allocation d’emplacements de pile pour tenir compte des préférences entre variables. On applique donc un coloriage avec fusion sur un ensemble de couleurs infini.
fusionner (graph) =
s'il existe une arête de préférence (u,v) du graphe
alors
fusionner (graph | u et v ont fusionné)
sinon
colorier (graph)
colorier (graph) =
choisir une variable v avec le degré minimum
colorier (graph \ v)
déterminer les couleurs impossibles pour v
choisir une couleur c pour v
Vous aurez besoin des fonctions ipp, remove, lowest, pppick et coalesce du module Interference. Attention à la fonction coalesce qui rend un graphe où ne reste qu’un seul des 2 noeuds qui lui sont passés en argument (le deuxième). Cela impose de colorier également le premier après coup. On vous demande d’implémenter les fonctions suivantes, où la fonction simplify correspond à colorier dans l’algorithme, et la fonction coalesce correspond à fusionner.
let forbidden_slots (graph : Interference.graph) (coloring : coloring) (v : Register.t) : Int32Set.t = ... let simplify (graph : Interference.graph) : coloring = ... let coalesce (graph : Interference.graph) : coloring = ...
Vous avez implémenté complètement l’allocation de registres !
Vous pouvez désormais tester votre programme avec make ltl.
De nombreuses optimisations existent pour l’allocation de registres, on va en implémenter quelques-unes. On ne s’intéresse ici qu’à l’allocation de registres physiques du module Coloring.
On voudrait pouvoir allouer les variables reliées par une arête de préférence au même registre physique. Comme on n’a pas ici un nombre de couleurs infini, il faut procéder plus finement que lors de l’allocation d’emplacements de pile. On applique donc un coloriage avec fusion conservative sur un ensemble de couleurs fini.
colorier (graph) =
s'il existe une variable v de degré inférieur à k
alors
allouer (graph, v)
sinon
fusionner (graph)
allouer (graph, v)
colorier (graph \ v)
déterminer les couleurs possibles pour v
si aucune couleur possible
alors
allouer v sur la pile
sinon
choisir une couleur c pour v
fusionner (graph) =
s'il existe une arête de préférence (u,v) du graphe
qui passe le test de George
alors
colorier (graph | u et v ont fusionné)
sinon
empiler (graph)
empiler (graph) =
choisir une variable v de degré maximum
allouer (graph, v)
Vous aurez besoin des fonctions pppick, coalesce, coalesceh et highest du module Interference. Les fonctions qui implémentent le test de George sont georgepp et georgeph. On vous demande d’implémenter ou de modifier les fonctions suivantes, où la fonction spilling correspond à empiler dans l’algorithme, et la fonction coalescing correspond à fusionner.
let simplification (graph : Interference.graph) : coloring = ... let coalescing (graph : Interference.graph) : coloring = ... let spilling (graph : Interference.graph) : coloring = ...
Dans la version de la fusion conservative que vous avez implémentée, seules les variables de fort degré sont fusionnées. On aimerait pouvoir fusionner également des variables de faible degré reliées par une arête de préférence. On applique donc un coloriage avec fusion conservative et congélation sur un ensemble de couleurs fini.
colorier (graph) =
s'il existe une variable v de degré inférieur à k
et sans arête de préférence
alors
allouer (graph, v)
sinon
fusionner (graph)
fusionner (graph) =
s'il existe une arête de préférence (u,v) du graphe
qui passe le test de George
alors
colorier (graph | u et v ont fusionné)
sinon
congeler (graph)
congeler (graph) =
s'il existe une variable v de degré inférieur à k
alors
enlever du graphe les arêtes de préférence liées à v
colorier (graph)
sinon
empiler (graph)
Note : allouer et empiler sont conservés à l’identique.
Vous aurez besoin des fonctions lowest_non_move_related et lowest du module Interference. On vous demande d’implémenter ou de modifier les fonctions suivantes, où la fonction freezing correspond à congeler dans l’algorithme.
let simplification (graph : Interference.graph) : coloring = ... let coalescing (graph : Interference.graph) : coloring = ... let freezing (graph : Interference.graph) : coloring = ...
Jusqu’à maintenant, on a uniquement optimisé le nombre de variables qui doivent être allouées en pile. Comme un accès à la pile est plus coûteux qu’un accès à un registre, on aimerait aussi que les variables les plus utilisées soient allouées à des registres, même si cela entraîne un peu plus d’allocations en pile.
Pour cela on utilise une heuristique : on définit le coût d’une variable comme le rapport du nombre d’utilisations de cette variable sur son degré.
empiler (graph) = choisir une variable v avec le coût minimum allouer (graph, v)
Vous aurez besoin de la fonction minimum du module Interference. Le coût est donné par la fonction cost. Modifiez spilling pour utiliser ce coût.
La solution complète se trouve dans les fichiers coloring.ml et spill.ml.
Ce document a été traduit de LATEX par HEVEA