Analyse de durée de vie |
Les sources sont dans l’archive td7-liveness.tar.gz, on construit l’exécutable avec la commande make.
L’analyse de durée de vie sert à optimiser l’allocation de registres. Elle est donc suivie d’un calcul des interférences entre registres (registres ne pouvant pas être affectés au même registre physique ou emplacement de pile). Cela conduit à s’intéresser à deux modules :
Vous allez implémenter les .ml correspondant.
C’est un problème de propagation arrière, pour lequel on
a besoin de calculer le point-fixe d’un ensemble
d’équations données en cours sous la forme :
| outvalue = used ⋃ (invalue \ defined) (1) |
Le calcul d’un point-fixe est donné dans le module kildall.mli. On se servira du foncteur Simplified qui prend un problème sous forme de SimplifiedProblem et rend comme solution les valeurs invalue et outvalue recherchées.
Un squelette de code vous est donné dans liveness.ml.
Comme la formule 1 le montre, il faut commencer par donner la définition des fonctions defined et used.
Réfléchissez bien à l’effet de chaque instruction sur les registres. En particulier, les registres physiques impactés n’apparaissent pas nécessairement dans les paramètres du constructeur de l’instruction.
Déduisez-en la définition de instruction_semantics, qui traduit l’effet d’une instruction sur l’ensemble des registres vivants.
Comme l’analyse de durée de vie est une analyse de propagation arrière, le paramètre input correspond aux registres vivants après l’instruction, et instruction_semantics doit retourner les registres vivants avant l’instruction.
Vous pouvez tester votre programme en affichant les registres vivants à chaque point du programme ERTL, avec la commande :
# ./compilo -dertl -dlive <programme>
Ou, pour réduire le nombre de registres physiques :
# ./compilo -dertl -dlive -few <programme>
Regardez en particulier ce qui se passe pour le pseudo-registre contenant la valeur de la variable x de la fonction dead dans l’exemple test/dead.p.
Il fait bien partie des registres vivants alors que comme le nom de l’exemple l’indique, il devrait être mort puisque la valeur de x n’est pas utilisée.
Que faire pour ne pas considérer ces registres comme vivants ?
Une optimisation immédiate consiste à ne pas effectuer une écriture dans un pseudo-registre si celui-ci n’est pas vivant après l’instruction, et si l’élimination de l’instruction ne modifie pas l’exécution du programme.
Complétez la fonction eliminable pour qu’elle renvoie Some l avec l le label de l’instruction suivante, quand on peut éliminer l’instruction pour la raison évoquée ci-dessus, et None sinon.
Note : Elle pourrait renvoyer un booléen pour l’application qui nous intéresse, on choisit ce type pour une utilisation ultérieure.
Utilisez-la pour améliorer la détection des variables vivantes dans instruction_semantics.
Relancez le calcul des registres vivants sur test/dead.p, le pseudo-registre correspondant à x a disparu !
Un graphe d’interférence a pour sommets les registres (pseudo- ou physiques) de la fonction, et relie par ses arêtes les registres pouvant être vivants en même temps à un point du programme. Vous allez le construire, en utilisant la spécification donnée dans interference.mli.
Il s’agit de compléter le code de build.ml.
On utilise ici liveafter soit l’ensemble des registres vivants après chaque instruction, c’est-à-dire au moment d’écrire un registre. Le graphe d’interférence graph n’a initialement aucune arête.
Complétez le graphe d’interférence en y ajoutant une arête pour tout couple de registres dont un est écrit par une instruction, et l’autre est vivant à ce point du programme.
Vous pouvez utiliser la fonction mki :
let mki (g : graph) (defregs : Register.Set.t * MIPS.RegisterSet.t) (liveregs : Register.Set.t * MIPS.RegisterSet.t) : graph = ...
qui ajoute au graphe g les arêtes entre les paires de registres prises dans defregs et liveregs, en prenant soin d’éviter de faire interférer un registre avec lui-même, ou deux registres physiques ensemble.
Vous pouvez visualiser le graphe d’interférence produit en utilisant les commandes :
# ./compilo -dgraph <nom de fonction> <programme> | circo -Tps > <fichier>.eps # kghostview <fichier>.eps
Regardez ce qui se passe dans un cas simple, avec l’exemple test/trivial.p. Est-ce que toutes les interférences affichées sont indispensables ?
En fait, l’algorithme simple utilisé jusqu’ici considère un move comme une instruction d’écriture quelconque, donc la source du move et sa destination peuvent interférer. En réalité on souhaite que la source et la destination d’un move partagent le même registre physique si possible, car ils ont la même valeur.
Implémentez cette optimisation dans l’algorithme précédent.
Vous pouvez vérifier sur test/trivial.p que certaines interférences ont disparu.
On souhaite aller plus loin et transformer les arêtes qu’on vient d’enlever, qui correspondent à des move, en des arêtes de préférence. L’allocateur de registre pourra utiliser cette information pour partager si possible le même registre physique entre les sommets reliés par une arête de préférence, ce qui rendra l’instruction move inutile.
Redéfinissez le graphe d’interférence pour ajouter de telles arêtes, en utilisant les fonctions mkppp et mkpph :
let mkppp (g : graph) (reg1 : Register.t) (reg2 : Register.t) : graph = ... let mkpph (g : graph) (reg1 : Register.t) (reg2 : MIPS.register) : graph = ...
qui ajoutent au graphe g des arêtes de préférences entre leurs paramètres reg1 et reg2.
Vous pouvez visualiser sur test/trivial.p que des arêtes de préférence sont apparues.
Il reste un problème à régler, le cas du registre physique
$zero, qui contient en permanence la valeur zero. Plutôt que
d’ajouter des interférences entre celui-ci et tous les
pseudo-registres, utilisez Zero.nonzeroable pour déterminer les
pseudo-registres possiblement non-nuls.
La solution complète se trouve dans les fichiers liveness.ml et build.ml.
Ce document a été traduit de LATEX par HEVEA