Le code assembleur généré gagnera en efficacité si l'essentiel des variables et valeurs intermédiaires du programme sont stockées directement dans les registres plutôt que dans la mémoire. Cependant les registres sont en nombre fini et fixé, alors que les valeurs à stocker peuvent être en nombre arbitrairement grand.
L'objectif de cette séance est de modifier la phase d'allocation pour qu'elle affecte autant de valeurs que possible à des registres. Pour cela, on réutilisera l'analyse de vivacité de la séance précédente et on ira puiser dans la théorie des graphes.
Note : le contrat de base pour cette séance se passe de l'algorithme de graphes et tient en quelques lignes de code. Si vous n'êtes pas à jour dans les TP précédents, vous pouvez vous contenter ici de la section allocation sans frais. Si vous êtes à jour en revanche, vous pouvez écrire un programme intéressant et plus efficace : c'est par ici.
1. Allocation sans frais
L'allocation actuelle considère toutes les variables locales présentes dans la table des symboles, qu'elles aient été présentes dans le programme source ou introduites lors de la production de la représentation intermédiaire, et leur affecte à chacune dans l'ordre un emplacement de pile (Stack o).
Vous pouvez faire légèrement mieux en affectant les huit premières aux registres $t2 à $t9, en gardant comme avant les registres $t0 et $t1 pour effectuer des opérations sur des valeurs lues en mémoire.
Travail à effectuer
Dans le fichier IrtoAllocated.ml, modifier la fonction allocate_main, et plus précisément la branche then de la conditionnelle if reg_flag pour que cette nouvelle politique d'allocation soit mise en place lorsque le compilateur est utilisé avec l'option -r (comme register allocation) ou -O (comme opt).
Et ensuite...
Une fois ceci fait, on recommande les extensions réutiliser les registres virtuels et économiser les mouvements.
1'. Allocation de registres, pour de vrai
Pour faire mieux, il faut identifier les variables qui peuvent ou non être affectées au même emplacement : c'est le cas si et seulement si leurs intervalles de vie sont disjoints.
La stratégie est la suivante. À partir de l'analyse de vivacité de la séance précédente, construire un graphe d'interférence, dont les sommets sont les variables et dans lequel deux nœuds v₁ et v₂ sont reliés par une arête (non orientée) si ces deux variables ne peuvent pas être affectées au même emplacement. Ensuite, réaliser une coloration de graphe minimisant le nombre de couleurs utilisées. Pour une architecture à k registres, les k premières couleurs correspondront chacune à l'un des registres, et les suivantes correspondront à des affectations sur la pile.
Nous vous fournissons une implémentation pour une mini-bibliothèque de graphes dans le fichier Graph.ml, que vous devez télécharger et placer dans votre projet. Vous n'avez pas besoin de lire ce fichier, les fonctions utiles sont décrites dans cet énoncé.
1'.1. Construction du graphe d'interférence
Définition du graphe
Le graphe d'interférence contient un sommet pour chaque identifiant local présent dans la table des symboles de votre programme. Chaque sommet est simplement désigné par l'identifiant auquel il est associé.
Les arêtes peuvent être ajoutées au graphe au cours d'un parcours de l'ensemble des instructions. Essentiellement, on a interférence entre une variable (re)définie en un point de programme et une variable vivante en sortie de ce point de programme.
Le critère plus précis distingue les instructions de la forme Value(dest, Identifier id), qu'on appelle des copies.
- Pour tout point de programme comportant une instruction définissant une variable dest, hors copies, ajouter des arêtes entre dest et chaque variable vivante en sortie de ce point de programme.
- Pour tout point de programme comportant une instruction de copie Value(dest, Identifier id), ajouter des arêtes entre dest et chaque variable vivante en sortie de ce point de programme, exceptée id (une éventuelle arête déjà existante entre dest et id n'est pas modifiée).
Travail à effectuer
Vous devez télécharger et compléter le fichier InterferenceGraph.ml. Les principales fonctions à traiter sont :
add_interferences: Graph.t -> VarSet.t -> IrAst.instruction -> Graph.t
qui prend en paramètre un graphe d'interférence en cours de construction,
une instruction et l'ensemble des variables vivantes en sortie de cette
instruction, et ajoute autant d'arêtes au graphe que nécessaire, ainsi que
interference_graph: IrAst.main -> Graph.t
qui produit le graphe d'interférence d'un programme passé en argument.
Les éléments suivants de la bibliothèque Graph vous seront utiles :
- Graph.empty: Graph.T. Constante désignant le graphe vide.
- Graph.add_node: Graph.t -> string -> Graph.t. Fonction prenant en paramètres un graphe et un identifiant, et renvoyant un graphe avec un sommet supplémentaire pour cet identifiant. Lève l'exception InvalidNode si l'identifiant étiquette déjà un sommet du graphe.
- Graph.add_edge: Graph.t -> string -> string -> Graph.t. Fonction prenant en paramètres un graphe et deux identifiants, et renvoyant un graphe avec une arête supplémentaire entre les deux sommets désignés par ces identifiants. Renvoie le graphe sans modification si les deux identifiants sont égaux. Lève l'exception InvalidNode si l'un ou l'autre des identifiants n'étiquette pas un sommet du graphe.
1'.2. Algorithme de coloration
Une coloration d'un graphe est l'affectation d'une couleur à chaque sommet du graphe, de sorte que deux sommets adjacents ont des couleurs différentes. L'objectif d'un problème de coloration est de minimiser le nombre de couleurs utilisées, ou de se restreindre à un nombre de couleurs déterminé. Dans tous les cas, ces problèmes de coloration sont NP-complets.
On va implémenter ici un algorithme approché très simple de type glouton visant à minimiser le nombre de couleurs.
Définition de l'algorithme de coloration
On va prendre comme couleurs les entiers positifs ou nuls. On considère l'algorithme récursif suivant pour colorer un graphe g :
- choisir un sommet n de degré minimal dans g,
- construire le graphe g' obtenu en retirant n de g,
- colorer g',
- étant donnée les couleurs déjà affectées aux sommets de g', affecter à n la plus petite couleur possible (c'est-à-dire le plus petit entier non utilisé pour colorer les voisins de n).
Travail à effectuer
Vous devez télécharger et compléter le fichier GraphColoring.ml, pour y implémenter notre algorithme de coloration. Les principales fonctions à traiter sont :
pick_color: Graph.t -> coloring -> string
qui prend en paramètres un graphe, une coloration pour ce graphe et
l'identifiant d'un sommet n et renvoie la plus petite couleur
qui puisse être donnée à n (on pourra supposer que tous les
voisins de n sont déjà colorés), ainsi que
colorize: Graph.t -> coloring
qui prend en paramètre un graphe, et renvoie la coloration calculée avec
notre algorithme.
Les éléments suivants de la bibliothèque Graph vous seront utiles :
- Graph.min_degree: Graph.t -> string option. Renvoie un sommet de degré minimal du graphe passé en paramètre si le graphe contient au moins un sommet, et None sinon.
- Graph.neighbours: Graph.t -> string -> string list. Prend en paramètres un graphe g et un sommet s de ce graphe, et renvoie la liste des voisins de s dans g. Lève l'exception Not_found si le sommet s n'existe pas dans g.
- Graph.del_node: Graph.t -> string -> Graph.t. Prend en paramètres un graphe g et un sommet s de ce graphe, et renvoie le graphe g' formé en retirant de g le sommet s et toutes ses arêtes incidentes. Lève l'exception Not_found si le sommet s n'existe pas dans g.
1'.3. Allocation
Pour finir, il faut transfomer la coloration de chaque sommet en une allocation de l'identifiant correspondant. Pour cela, on peut allouer les couleurs 0 à 7 aux registres $t2 à $t9 (en gardant comme avant les registre $t0 et $t1 pour effecuter des opérations sur des valeurs lues en mémoireà), puis les couleurs suivantes à des emplacements de pile (Stack o).
Travail à effectuer
Dans le fichier IrtoAllocated.ml, modifier la fonction allocate_main, et plus précisément la branche then de la conditionnelle if reg_flag pour que l'algorithme d'allocation soit activé lorsque le compilateur est appelé avec l'option -r (comme register allocation) ou -O (comme opt).
Et ensuite...
Pour profiter au mieux du travail qui vient d'être fait, on recommande l'extension économiser les mouvements.
2. Extensions
2.1. Réutiliser les registres virtuels
L'amélioration décrite ici est strictement moins puissante que l'allocation à base de coloration de graphes. Elle peut en revanche améliorer considérablement l'allocation "sans frais".
Dans l'étape de traduction de expressions (GototoIr.ml), le chemin de moindre résistance consistait à créer un nouvel identifiant pour chaque valeur intermédiaire de chaque instruction arithmétique. Ceci peut être amélioré de deux manières complémentaires.
2.1.1. Réutilisation d'identifiants inter-instructions
Les identifiants créés ne concernent qu'une expression et ne sont utiles qu'au sein d'une instruction donnée. On peut donc déjà obtenir une première amélioration en faisant en sorte que la génération des nouveaux identifiants, faite pour l'instant par la fonction new_tmp, soit locale à chaque instruction et commence à chaque fois avec un compteur à zéro.
2.1.2. Réutilisation d'identifiants intra-expressions
Remarquez que dans le calcul d'une expression e₁ + e₂, et quel que soit le nombre d'identifiants temporaires utilisés dans le calcul de e₁, une fois que le résultat de e₁ est calculé, et placé par exemple dans tmp0, tous les identifiants à partir de tmp1 sont à nouveau disponibles pour le calcul de e₂.
Pour profiter de ceci, on peut par exemple ajouter un nouveau paramètre i à la fonction de traduction des expressions, dont l'effet sera "traduire une expression en utilisant comme identifiants temporaires les identifiants à partir de tmpi".
2.2. Économiser les mouvements
Grâce à l'allocation de registres, quelle que soit la version implémentée, une opération binaire pour laquelle le code généré était à l'origine de la forme
lw $t0, o₁($fp)
lw $t1, o₂($fp)
add $t0, $t0, $t1
sw $t0, o₃($fp)
est maintenant susceptible d'être implémentée par
move $t0, $r₁
move $t0, $r₂
add $t0, $t0, $t1
move $r₃, $t0
C'est appréciable, car de coûteuses opérations mémoire ont été remplacées
par de simples copies de registres. Mais avouez qu'on aurait préféré
obtenir tout simplement
add $r₃, $r₁, $r₂
Il y a (au moins) deux manières d'obtenir ce meilleur résultat, toutes deux
efficaces :
- La méthode ad hoc est simple et efficace
- La méthode générique utilise l'optimisation standard de propagation des copies. Un peu plus complexe à mettre en œuvre, mais optimise aussi un peu plus de choses au passage.
2.2.1. Méthode ad hoc
Dans le module de génération d'assembleur Mips, vous devez avoir actuellement une fonction load_value chargée de générer le code assembleur plaçant une valeur donnée dans un registre donné, typiquement $t0 ou $t1.
Vous pouvez créer une variante de cette fonction, qui produit deux choses : un code assembleur qui place la valeur dans le registre donné si elle n'est pas déjà stockée dans un registre (et ne fait rien si la valeur est déjà stockée dans un autre registre), et le nom du registre où va se trouver la valeur. Il ne reste alors qu'à adapter l'instruction en cours de traitement pour qu'elle récupère la valeur au bon endroit.
Dans le cas d'une instruction réalisant une affectation (Binop ou Value), n'oubliez pas de traiter de même le registre de destination.
2.2.2. Méthode générique
L'optimisation de propagation des copies, appliquée après l'allocation de registres, permet de court-circuiter les instructions move superfétatoires.
Ainsi, une fois que les instructions subséquentes modifiées pour aller chercher les valeurs directement à leur source, les instructions move associées deviennent des instructions mortes, qui peuvent être éliminées par l'optimisation d'élimination du code mort.
Si vous avez implémenté ces deux optimisations lors de la séance précédente, il vous suffit de les appliquer l'une après l'autre une fois l'allocation de registres achevées. Au besoin, l'optimisation de propagation des copies était décrite ici.
Attention toutefois, ceci ne concerne que pour les opérations move relatives aux opérandes. La destination du résultat doit toujours être traitée indépendamment.