La représentation intermédiaire est un lieu privilégié où analyser finement le comportement d'un programme et modifier le code pour améliorer son efficacité. L'objectif de cette séance est de mettre en place une analyse simple (analyse de vivacité) et une optimisation associée (élimination de code mort), sur la représentation intermédiaire IrAst.
Analyse de vivacité
L'analyse de vivacité consiste à déterminer, en chaque point du programme, quelles sont les variables dont la valeur courante est susceptible d'être utilisée par une instruction subséquente.
L'élimination de code mort est une utilisation simple de cette information : une instruction qui affecte une valeur à une variable peut être supprimée si cette valeur n'est utilisée nulle part (et si ladite instruction n'a pas d'autre effet de bord).
Équations de flot de données
Une variable x est vivante en un point de programme p donné s'il existe au moins un chemin d'exécution de p à une utilisation de x qui ne passe pas par une redéfinition de x.
La vivacité d'une variable en un point donné dépend des points de programme suivants : le flot de données va être inversé. De plus, la quantification sur les chemins est existentielle. Les équations de flot de données prennent donc la forme suivante :
In[p] = (Out[p] \ Kill[p]) ∪ Gen[p]
Out[p] = ⋃ᵣ In[r] r ∈ Succ[p]
où In, Out, Kill et Gen associent
un ensemble de variables à chaque point p du programme.
Une instruction produit une variable vivante x si elle utilise la valeur courante de x, c'est-à-dire si elle accède à x en lecture. À l'inverse, une instruction tue une variable x si elle redéfinit sa valeur, c'est-à-dire si elle accède à x en écriture. Donc si p est un point de programme exécutant une instruction i, on a les définitions suivantes :
Gen[p] = { x | i lit la valeur de x }
Kill[p] = { x } pour i ≡ x := ...
Kill[p] = ∅ pour i ≡ print, goto
Graphe de flot de contrôle
Les règles du flot de contrôle sont les suivantes :
- Une instruction goto l a pour seul successeur le point de programme identifié par l'étiquette l.
- Une instruction goto l when ... a un ou deux successeurs : l'instruction suivante si elle existe, et le point de programme identifié par l'étiquette l.
- Toutes les autres instructions ont zéro ou un successeur : l'instruction suivante si elle existe.
Exercice préparatoire
Considérons le programme suivant :
1: goto 15
2: label 2
3: z := y
4: x := 1
5: goto 9 when y
6: z := x
7: x := x + z
8: goto 12
9: label 9
10: y := w + 2
11: z := x + 1
12: label 12
13: y := x + z
14: w := w + 1
15: label 15
16: goto 2 when y
17: print y
Donnez son graphe de flot de contrôle, puis résolvez les équations de vivacité. Indiquez quelles instructions peuvent être éliminées.
Travail à effectuer
1. Analyse de vivacité
Vous devez télécharger et compléter le fichier suivant : IrLiveness.ml.
Les principales fonctions à compléter sont
- mk_succ : crée une table associant à chaque point de programme l'ensemble de ses successeurs.
- lv_gen, lv_kill : associe à une instruction l'ensemble des variables vivantes qu'elle produit, détruit.
- mk_lv : calcule le plus petit point fixe des équations de flot de données sur un programme donné.
2. Élimination de code mort
Vous devez télécharger et compléter le fichier suivant : IrDeadCodeElim.ml.
Les principales fonctions à compléter sont
- dce_step : calcule les vivacités et élimine les instructions mortes (une étape).
- dce : itère la fonction précédente tant qu'il reste des instructions à éliminer.
Extensions
1. Améliorer l'efficacité de l'analyse
1.1. Calcul de point fixe avec liste de tâches
Améliorez le code de mk_lv en utilisant une liste de tâches à la place de l'exploration exhaustive répétée des instructions.
1.2. Chaînes définition/utilisation et analyse incrémentale
Raffinez l'analyse de vivacité pour que l'information mémorisée ne soit plus simplement l'ensemble des variables vivantes, mais les étiquettes des instructions responsables de cette vivacité.
Déduisez-en une version améliorée de dce, qui n'a pas besoin de recalculer complètement les vivacités après chaque élimination.
Indication : il faudra à nouveau calculer un point fixe.
2. Propagation des constantes
2.1. Simplification des constantes
Si une instruction est une opération binaire s'appliquant à deux constantes, calculer directement le résultat et remplacer l'instruction par une simple affectation.
2.2. Définitions accessibles
Une définition accessible d'une variable x en un point de programme p est un point de programme p' contenant une instruction x := ... et tel qu'il existe un chemin de p' à p qui ne traverse pas d'autre définition de x. Par convention, on supposera qu'une instruction fantôme définit toutes les variables au début du programme main (mais que cette "définition" ne leur donne pas de valeur).
D'après cette définition, la propagation des informations se fait dans l'ordre du programme. De plus, la quantification sur les chemins est existentielle. Les équations de flot de données sont donc :
In[p] = ⋃ᵣ Out[r] r ∈ Pred[p]
Out[p] = (In[p] \ Kill[p]) ∪ Gen[p]
où, si p est un point de programme contenant une instruction
de la forme x := ..., alors Gen[p] est l'instruction
elle-même et Kill[p] est l'ensemble des autres définitions
de x. Pour toute autre forme d'instruction ces deux ensembles
sont vides.
Implémentez un module IrAccessibility qui calcule les définitions accessibles en chaque point du programme.
2.3. Propagation des constantes
Si une instruction i utilise une variable x en un point du programme où il y a une seule définition accessible pour x, et que cette définition donne à x une valeur constante (il ne peut donc pas s'agir de la définition fantôme du début du programme), alors la variable x peut directement être remplacée par sa valeur.
Implémentez un module IrConstantPropagation qui remplace ainsi les variables définies pas des constantes, et itère ce processus autant que possible.
Indication : là aussi, une forme de point fixe va être utile.
2.4. Combinaison d'optimisations
Remarquez que nos deux optimisations peuvent avoir une influence l'une sur l'autre. Faites en sorte que leur combinaison soit la plus efficace possible.
3. Propagation des copies
De même que pour la propagation des constantes, si une instruction i utilise une variable x en un point de programme p où il y a une seule définition accessible pour x (en un point de programme pₒ), et que cette définition affecte à x la valeur d'une autre variable y, alors on peut potentiellement remplacer l'utilisation de x par une utilisation directe de y.
Attention toutefois, ceci ne peut se faire que s'il n'existe aucune redéfinition de y en un point de programme intermédiaire pᵢ tel qu'il existe des chemins d'exécution de pₒ à pᵢ et de pᵢ à p.
De même encore que pour la propagation des constantes, cette optimisation peut avoir une influence sur l'optimisation d'élimination du code mort.
Pour ceux qui en veulent, notez que cette optimisation un peu plus complexe à mettre en œuvre que les précédentes est particulièrement utile. En combinaison avec l'élimination de code mort, elle pourra s'articuler de manière intéressante avec d'autres extensions qui vous seront proposées dans le TP 4 (allocation de registres) et le TP 5 (fonctions).
4. Expression libre
Les autres optimisations possibles ne manquent pas, et leurs interactions peuvent être riches. Pour d'autres classiques, voir par exemple les mots-clés "expressions disponibles" et "élimination des sous-expressions communes".