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.
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 :
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.
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.
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
Dessin à rajouter
On peut distinguer deux grandes classes d'optimisations :
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 |
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 |
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.
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 |
# define
en C).
Retour sur le produit scalaire, pour N=5 (# define N 5
)
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) |
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) |