Analyse de durée de vie |
Le sujet se trouve dans l’archive td7.tar.gz.
Nous nous intéressons aujourd’hui aux deux modules suivants:
On vous fournit des fichiers liveness.ml et build.ml incomplets.
Plaçons-nous dans liveness.ml.
Il vous faut d’abord définir les fonctions defined et used, qui indiquent quelles variables sont «tuées» et «engendrées» par chaque instruction.
Réfléchissez bien à l’effet de chaque instruction sur les pseudo-registres et registres physiques. Rappelez-vous en particulier qu’une instruction peut lire ou écrire certains registres physiques sans que ceux-ci soient explicitement mentionnés par l’instruction.
Définissez ensuite la fonction instruction_semantics, qui traduit l’effet d’une instruction sur l’ensemble des variables vivantes. L’analyse de durée de vie est une analyse arrière. Le paramètre liveafter est l’ensemble des variables supposées vivantes après l’instruction. La fonction instruction_semantics doit renvoyer l’ensemble des variables vivantes avant l’instruction.
Vous pouvez tester votre code en affichant les registres vivants à chaque point du programme ERTL:
# ./compilo -dertl -dlive test/fact.p
Ou bien, pour réduire le nombre de registres physiques et y voir un peu plus clair:
# ./compilo -dertl -dlive -few test/fact.p
Plaçons-nous dans build.ml.
L’analyse de durée de vie étant terminée, nous disposons de la valuation liveafter. Il s’agit d’une fonction qui à chaque label l associe l’ensemble des variantes vivantes à la sortie de l’instruction située au point l.
Un graphe d’interférence a pour sommets les variables, et les relie par des arêtes d’interférence et de préférence. À vous de construire ce graphe, en utilisant les fonctions de construction fournies par le module interference.mli.
Complétez le graphe d’interférence en y ajoutant une arête pour tout couple de variables distinctes dont l’une est définie par une instruction et l’autre est vivante à la sortie de cette instruction.
Vous pouvez utiliser la fonction mki (voir interference.mli).
Si vous avez installé la boîte à outils graphviz, vous pouvez visualiser le graphe d’interférence obtenu pour une fonction de votre choix (ici la factorielle) comme suit:
# ./compilo -few -dgraph f test/fact.p | circo -Tps > fact.eps # kghostview fact.eps
En principe, à ce point, make test doit réussir.
L’algorithme simple utilisé jusqu’ici considère une instruction move comme une opération unaire quelconque, donc considère que sa source et sa destination peuvent interférer. En réalité, parce que move est une fonction identité, cette interférence n’a pas lieu d’être. Au contraire, on souhaite que la source et la destination d’un move partagent le même registre physique si possible.
Étudiez le code obtenu pour la fonction factorielle. Est-il de bonne qualité? Il faut améliorer cela...
Ajoutez donc à l’algorithme précédent un cas particulier pour les instructions move. N’oubliez pas que le langage ERTL offre trois instructions de copie. Évaluez ensuite le résultat obtenu.
On souhaite aller plus loin et ajouter au graphe des arêtes de préférence pour favoriser la disparition des instructions move.
Vous utiliserez pour cela les fonctions mkppp et mkpph (voir interference.mli).
Évaluez ensuite le résultat obtenu, par exemple dans le cas de la fonction factorielle.
On revient ici dans liveness.ml.
Étudiez l’analyse de la variable x de la fonction dead dans test/dead.p.
# ./compilo -dertl -dlive -few test/dead.p
Le pseudo-registre correspondant à x est considéré comme vivant après les instructions x := 3 et x := x + x. De ce fait, ces instructions sont conservées, alors que l’on souhaiterait qu’elle soient éliminées, puisque la valeur de x n’est pas utilisée. On le constate en examinant le code assembleur produit:
./compilo -dasm -few test/dead.p
Que faire pour améliorer cela?
Une première amélioration consiste à éliminer une instruction si celle-ci est pure et si le pseudo-registre qu’elle définit est mort à la sortie de l’instruction. Pour effectuer cette amélioration, modifiez la définition de la fonction eliminable. La spécification de cette fonction est donnée en commentaire.
Modifiez le code qui construit le graphe d’interférences de façon à ignorer les instructions éliminables (qui n’ont pas encore été éliminées à ce point): elles ne donnent lieu à aucune arête.
Étudiez ce que cela donne dans le cas de test/dead.p. En principe, l’instruction x := x + x doit avoir disparu. Vérifiez-le:
./compilo -dasm -few test/dead.p
Cependant l’instruction x := 3 est toujours présente. Comment expliquez-vous cela?
Une seconde amélioration consiste à modifier la définition de la fonction instruction_semantics pour tenir compte (par avance) de l’élimination des instructions pures.
Étudiez ce que cela donne dans le cas de test/dead.p. Les instructions qui concernent x doivent avoir totalement disparu.
Si on le souhaite, il reste à traiter un cas particulier propre à MIPS, à
savoir le registre physique $zero, qui contient en permanence la valeur
zéro. En quelques rares occasions, ce registre physique peut servir à réaliser
un pseudo-registre. Il est nécessaire pour cela que l’on n’écrive jamais de
valeur autre que zéro dans ce pseudo-registre!
Jusqu’ici, par souci de simplicité, le registre physique $zero a été
considéré comme non allouable. Si on veut faire mieux, on peut modifier la
définition de MIPS.allocatable pour le rendre allouable. Faites-le.
La fonction nonzeroable (voir zero.mli), qui vous est
fournie, indique dans quels pseudo-registres une instruction risque d’écrire
une valeur non nulle. Ces pseudo-registres doivent alors être considérés comme
interférant avec le registre physique $zero. À vous de construire, dans
build.ml, des arêtes d’interférence qui reflètent cela.
Vérifiez via make test que vous n’avez pas introduit de bug. Vous pouvez
également comparer le code produit avec et sans cette optimisation. En
principe, elle permet d’éliminer quelques instructions de la forme
li $zero, 0. Le module ertl2ltlI.ml détecte ces instructions et
les élimine au vol.
Bien sûr, ce travail autour de $zero est plutôt anecdotique. Disons que
cela illustre le fait que la notion de coloriage de graphe permet souvent de
traiter assez facilement les bizarreries de certains processeurs.
Ce document a été traduit de LATEX par HEVEA