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 :
  1. 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


  2. 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 *)
  3. 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.

  4. 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.

  5. Après une étape de coloriage, vous devrez distinguer succès et échec.
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...
Voir la solution, si besoin est.


Ce document a été traduit de LATEX par HEVEA.