Allocation de registres
1 Environnement
Comme d'habitude, récupérer l'archive zyva.tar,
la décompacter, et écrire l'implémentation manquante
alloc.ml à partir de squelette.ml.
Soit la séquence de commande à effectuer tout de suite, après
récupération des fichiers.
# tar xf zyva.tar
# mv squelette.ml zyva/alloc.ml
# cd zyva
# make
Une fois le squelette complété, vous obtiendrez enfin du code exécutable, n'oubliez pas de le tester
à l'aide ``make ok''.
Vous pouvez aussi fabriquer un exemple
# ./zyva -4 test/fact.p > fact.spi
Puis le tester à l'aide de xspim.
# xspim -notrap -file fact.spi
2 Ce qu'il faut faire.
Il faut écrire un allocateur de registre par coloriage.
Le squelette contient tout l'environnement nécessaire.
C'est à dire :
-
La définition des registres utilisables et du nombre de
couleurs.
(* Deux trois trucs sur couleurs *)
let ncolors = List.length Mach.registers
let colors = of_list Mach.registers |
- La définition de la partition des sommets du graphe
d'interférence.
let sets = Partition.make 6
let precolored = sets.(0) (* precolored, remains here for ever *)
and low = sets.(1) (* candidates for simplify *)
and high = sets.(2) (* candidates for spill *)
and spilled = sets.(3) (* to be spilled *)
and colored = sets.(4) (* colored *)
and removed = sets.(5) (* on the stack waiting to be colored *) |
- Et surtout : l'étape build du coloriage, c'est à dire
la fabrication du graphe d'interférence et la répartition initiale des
sommets dans la partition.
- Il vous reste donc à écrire les autres étapes du coloriage
dénomées simplify, spill, et select dans la
figure du poly.
Il faut aussi
organiser le tout, c'est à dire en fait écrire
le corps de la fonction alloc en fin de fichier.
Notez que la fonction alloc
prend une fonction au sens de Spim en argument et renvoie
un code exécutable (voir la description de color_code plus
bas).
En fait, puisque le poly donne le code des colorieurs selon la
réalisation
récursive, je vous suggère la réalisation itérative avec pile
explicite (celle que décrit la figure du poly).
Vous pouvez choisir le coloriage le plus simple,
ou vous attaquer
d'entrée de jeu au coloriage optimiste.
Pour le choix des spills potentiels, vous pouvez très bien dans un
premier temps vous en remettre au hasard, puis seulement concevoir et
tester une heuristique de spill.
De même, le choix des couleurs peut très bien être arbitraire dans un
premier temps et biaisé dans un second temps.
- Après une étape de coloriage, vous devrez distinguer succès et échec.
-
En cas d'échec il faudra
fait appel à la
fonction
Spill.spill_fun pour effectivement spiller les
temporaires que vous aurez choisis pou rl'être.
(voir l'interface du module Spill)
- En cas de succès, il faudra faire appel à la fonction
color_code donneé dans
le squelette.
Cette fonction prend, dans l'ordre, le graphe d'interférence
et la fonction (au sens du module Spim) passée en argument à
alloc. Elle renvoie un code colorié et précédé de la
définition de taille du frame.
Je crois qu'il est possible d'écrire un colorieur simple en deux
heures en adoptant la démarche de ne pas chercher à comprendre ce que
font exactement tous les bouts de code appelés.
Ensuite, il conviendra sans doute d'aller voir de plus près ce que
font exactement, build, spill_fun et color_code
par exemple...
Ce document a été traduit de LATEX par
HEVEA.