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
  1. Cette optimisation met en évidence du code mort (ici, les deux premières affectations sont inutiles).
  2. 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)

<= Gestion de tables de symboles


 
m1ilc/compil_9.txt · Dernière modification: 2009/11/16 19:36 par suitable