Analyse de durée de vie

Voici le cours correspondant. La solution est ici.

Présentation

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.

Analyse de durée de vie

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.

Ecriture et lecture de registres

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.

Voir la solution.

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.

Voir la solution.

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>

Optimisation du code mort

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.

Voir la solution.

Relancez le calcul des registres vivants sur test/dead.p, le pseudo-registre correspondant à x a disparu !

Calcul des interférences

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.

Une première version

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.

Voir la solution.

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

Le cas des move

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.

Voir la solution.

Vous pouvez vérifier sur test/trivial.p que certaines interférences ont disparu.

Des arêtes de préférence

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.

Voir la solution.

Vous pouvez visualiser sur test/trivial.p que des arêtes de préférence sont apparues.

Pour finir...

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.

Voir la solution.

La solution complète se trouve dans les fichiers liveness.ml et build.ml.


Ce document a été traduit de LATEX par HEVEA