===== VI. Optimisation du Code Intermédiaire ===== ==== Introduction ==== La phase d'optimisation de code prend en entrée du code intermédiaire et retourne en sortie du code intermédiaire "optimisé." Elle a lieu avant la phase de génération de code. Donc, les optimisations qui sont réalisées sont indépendantes de la machine cible. La plupart de ces optimisations concernent les boucles car généralement ceux sont ces parties du code qui sont les plus consommatrices de temps CPU. Ces optimisations nécessitent des analyses préalables : par exemple, pour optimiser les boucles il faut d'abord les détecter en procédant à une __analyse de flot de contrôle__ . Et pour optimiser l'utilisation des variables à l'intérieur d'une boucle, on doit procéder à une __analyse de flot de données__. ==== Organisation des optimisations de code ==== | analyse de flot de contrôle ^ -> -> | analyse de flot de données ^ -> -> | transformation | Pour réaliser une analyse de flot de contrôle on représente le code par un graphe de flot : * le noeuds (de ce graphe) sont des blocs de base * les arêtes représentent le flot de contrôle Un bloc de base est un bloc d'instructions tel que le flot de contrôle entre en début de bloc et sort à la fin du bloc sans possibilité de s'arrêter ou brancher (sauf à la fin du bloc). Un bloc de base est typiquement une séquence d'instructions pour calculer une expression arithmétique. === Exemple === Etudions le graphe de flot de contrôle pour le produit scalaire de deux vecteurs: do I= 1, N prod = A(I) * B(I) sum = sum + prod En code intermédiaire, ce code source deviendrait 1 prod := 0 2 I := 1 3 T1 := 4*I 4 T2 := adr(A) - 4 5 T3 := T2[T1] 6 T4 := 4 * I 7 T5 := adr(B) - 4 8 T6 := T5[T4] 9 T7 := T3 * T6 10 T8 := prod + T7 11 prod := T8 12 I := I + 1 13 if I <= N goto(3) 14 ... Ici nous identifions un bloc de lignes 3 à 13, un bloc de lignes 1 à 2, puis un nouveau bloc à partir de ligne 14. === Analyse de flot de données === On utilise un DAG --Directed Acyclic Graphe-- qui représente l'expression arithmétique correspondante à un bloc de base. Comme pour un AST, un noeud d'un DAG identifie une sous-expression. La différence entre un AST et un DAG est qu'un noeud d'un DAG peut avoir plusieurs pères. Une sous-expression commune à plusieurs expression peut n'être représentée qu'une seule fois tandis que dans un arbre de syntaxe une telle sous-expression doit être représentée plusieurs fois. Exemple : arbre de syntaxe et DAG pour ''b*c+c*b'' + + / \ ( ) / \ \ / * * * / \ / \ / \ b c c b b c (a+b*c)-(b*c-d) + + / \ / \ + - + - / \ / \ / \ / \ a * * d a * d / \ / \ / \ b c b c c b === DAG du bloc B2 === FIXME Dessin à rajouter ==== Principales Sources d'Optimisation ==== On peut distinguer deux grandes classes d'optimisations : * les optimisations __locales__ à un bloc de base * les optimisations __de boucle__ === Optimisations Locales === == Elimination des sous-expressions communes == ^ Code source ^ Code interméd. ^ Code interméd. optimisé ^ | X = A[I] | ''T1 := 4*I''\\ ''X := A[T1]'' | ''T1 := 4*I''\\ ''X := A[T1]'' | | A[I] = A[J] | ''T2 := 4*J''\\ ''T3 := A[T2]''\\ ''T4 := 4*I''\\ ''A[T4] := T3'' | ''T2 := 4*J''\\ ''T3 := A[T2]''\\ ''A[T1] := T3'' | | A[J] = X | ''T5 := 4*J''\\ ''A[T5] := X'' | ''A[T2] := X'' | == Propagation de copie == x = y ... x ... où x et y sont des variables. On remplace la copie (x) par l'original (y). ^ Initialement ^ Après ^ | ''X := T1''\\ ''A[T2] := T3''\\ ''A[T4] := X'' | ''A[T2] := T3''\\ ''A[T4] := T1'' | == Elimination de code mort ((dead code elimination)) == Une variable est vivante ("alive") à un certain point du programme si sa valeur est utilisée plus loin dans le code. Dans le cas contraire, on peut supprimer son affectation. == Propagation de constante == Elle consiste à remplacer une expression qui peut être évaluée à une constante par sa valeur. ^ Initialement ^ Propagation de constante ^ Elimination du code mort ^ | ''T1 := 3''\\ ''T2 := 2*T1''\\ ''A[T2] := 1'' | ''T1 := 3''\\ ''T2 := 6''\\ ''A[6] := 1'' | ''A[6] := 1 '' | == Remarques == - Cette optimisation met en évidence du code mort (ici, les deux premières affectations sont inutiles). - Cets optimisation suit le "constant folding" réalisé avant la traduction en code intermédiaire (cf. ''# define'' en C). ==== Optimisations de Boucles ==== * Déplacement de code : on sort de la boucle les invariantes de boucle, c'est à dire les expressions qui sont constantes dans la boucle. * Elimination des variables induites : on supprime une variable dont la valeur progresse de façon corrélée avec la valeur des indices de boucle (ou bien on l'utilise comme indice de boucle et supprime celle-là). * Réduction du coût : on sort les opérations couteuse de la boucle === Exemple Compréhensif === Retour sur le produit scalaire, pour N=5 (''# define N 5'') == Optimisations Locales == ^ Ligne ^ Code Intermédiaire ^ Elimination de\\ sous-expressions\\ redondantes ^ Propagation\\ de copie ^ | 1 | prod := 0 | prod := 0 | prod := 0 | | 2 | I := 1 | I := 1 | I := 1 | | 3 | T1 := 4*I | T1 := 4*I | T1 := 4*I | | 4 | T2 := adr(A) - 4 | T2 := adr(A) - 4 | T2 := adr(A) - 4 | | 5 | T3 := T2[T1] | T3 := T2[T1] | T3 := T2[T1] | | 6 | T4 := 4*I | | | | 7 | T5 := adr(B) - 4 | T5 := adr(B) - 4 | T5 := adr(B) - 4 | | 8 | T6 := T5[T4] | T6 := T5[T1] | T6 := T5[T1] | | 9 | T7 := T3 * T6 | T7 := T3 * T6 | T7 := T3 * T6 | | 10 | T8 := prod + T7 | T8 := prod + T7 | | | 11 | prod := T8 | prod := T8 | prod := prod + T7 | | 12 | I := I+1 | I := I+1 | I := I+1 | | 13 | if I <= 5 goto(3) | if I <= 5 goto(3) | if I <= 5 goto(3) | == Optimisations de Boucle == Les optimisations de boucle s'appuient sur le graphe de flot de contrôle. ^ Ligne ^ Code après\\ Optimisations\\ Locales ^ Déplacement de code ^ Eliminations de\\ Variable Induite ^ | 1 | prod := 0 | prod := 0 | prod := 0 | | 2 | I := 1 | I := 1 | T1 := 0 | | ^ entrée de boucle | || | 3 | T1 := 4*I | T2 := adr(A) - 4 | T2 := adr(A) - 4 | | 4 | T2 := adr(A) - 4 | T5 := adr(B) - 4 | T5 := adr(B) - 4 | | | ^ entrée de boucle ^ entrée de boucle ^ | 5 | T3 := T2[T1] | T1 := 4*I | T1 := T1 + 4 | | 6 | T5 := adr(B) - 4 | T3 := T2[T1] | T3 := T2[T1] | | 7 | T6 := T5[T1] | T6 := T5[T1] | T6 := T5[T1] | | 8 | T7 := T3 * T6 | T7 := T3 * T6 | T7 := T3 * T6 | | 9 | prod := prod + T7 | prod := prod + T7 | prod := prod + T7 | | 10 | I := I+1 | I := I+1 | | | 11 | if I <= 5 goto(3) | if I <= 5 goto(5) | if T1 <= 16 goto(5) | ---- [[compil_8| <= Gestion de tables de symboles]]