Optimisation des compilateurs

WIKIBOOKS

L'optimisation des compilateurs est la procédure qui minimise certains facteurs d'un programme exécutable pour maximiser son efficacité. Le facteur généralement minimisé est le temps d'exécution. Néanmoins, on pourrait éventuellement s'intéresser à minimiser la quantité de mémoire utilisée ou bien la consommation en énergie du programme.

Les commentaires et les suggestions d'amélioration sont les bienvenus, alors, après votre lecture, n'hésitez pas. Commentez

- Titre : Optimisation des compilateurs

- Auteur : WIKIBOOKS

- Parution : 16 juillet 2014

- Licence : Le contenu de cet article est rédigé par WIKIBOOKS et est mis à disposition selon les termes de la Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 3.0 non transposé. Les logos Developpez.com, en-tête, pied de page, css, et look & feel de l'article sont Copyright ® 2013 Developpez.com.

Sommaire

- I. Techniques

- I-A. Optimisation des expressions

- I-B. Optimisation sur des fenêtres « peephole »

- I-C. Optimisation des boucles

- I-C-1. Changement de l'ordre des boucles

- I-C-2. « Loop splitting » ou « loop peeling »

- I-C-3. Fusion de boucles

- I-C-4. « Loop Unwiding »

- I-C-5. « Loop unswitching »

- I-C-6. Inversion de boucle

- II. Facteurs

- II-A. La machine elle-même

- II-B. L'architecture du processeur cible

- II-B-1. Le nombre de registres

- II-B-2. RISC vs. CISC

- II-B-3. Pipeline

- II-B-4. Le nombre d'unités fonctionnelles

- II-C. L'architecture de la machine

- II-C-1. La taille et le type du cache

- II-C-2. Le temps moyen d'accès mémoire/cache

- III. Problèmes avec l'optimisation

I - Techniques

Les techniques d'optimisation peuvent être divisées en deux catégories :

- La première s'applique localement, sur une instruction.

- La deuxième s'applique globalement sur tout le programme et nous permet d'obtenir plus de gain mais avec une implémentation plus complexe.

I-A - Optimisation des expressions

Cette technique d'optimisation locale simplifie les expressions mathématiques utilisées quand certaines valeurs constantes sont utilisées dans des opérations.

Par exemple, pour la multiplication :

- multiplier une expression par 0 revient à ne pas la calculer ;

- une multiplication par 1 est inutile ;

- une multiplication par une puissance n de 2 (2n) revient à effectuer un décalage de n bits vers la gauche (vers les bits de poids fort).

I-B - Optimisation sur des fenêtres « peephole »

Cette technique, appliquée après génération du code machine, consiste à examiner quelques instructions adjacentes et voir si c'est possible de les remplacer par une instruction ou une séquence d'instructions plus courte. Par exemple, une multiplication par deux peut être efficacement exécutée par un décalage à gauche ou par une simple addition de la valeur à elle-même.

Considérant ce code en assembleur Java :

…
aload 1
aload 1
mul
…

Il peut être remplacé par :

…
aload 1
dup
mul
…

Ce type d'optimisation a besoin d'avoir des hypothèses sur l'efficacité des instructions. Dans ce cas précis, on a assumé que l'opération « dup », qui duplique et écrit dans la pile, est plus efficace que l'opération « aload X », qui lit une variable locale et l'écrit dans la pile. Un autre exemple d'optimisation est d'éliminer les opérations de lecture redondante.

Ce code :

A = B + C ;
D = A + E ;

devient :

MOV b, R0
ADD c, R0
MOV R0, a
MOV a, R0 # lecture redondante, elle peut être supprimée
ADD e, R0
MOV R0, d

I-C - Optimisation des boucles

Cette technique agit sur les instructions qui constituent la boucle. Cette procédure est très intéressante, car une bonne partie du temps d'exécution d'un programme est dédiée à l'exécution des boucles. Il existe plusieurs opérations possibles dans ce type d'optimisation.

I-C-1 - Changement de l'ordre des boucles

Cette optimisation consiste à changer l'ordre des boucles entrelacées. En effet, on pourrait échanger une boucle externe avec une interne. Cette transformation nous permet de vérifier le principe de localité. D'ailleurs, ça permet d'éviter à la mémoire cache de chercher des lignes de données d'une itération à une autre. Considérons l'exemple d'un tableau à deux dimensions et le fait qu'on dispose du code suivant pour le remplir :

For i from 0 to 10
For j from 0 to 20
A [i,j]= i + j

Ce code peut être optimisé de la sorte avec ce type d'optimisation :

For j from 0 to 20
For i from 0 to 10
A [i,j]= i + j

Mais cette transformation dépend de la technique du cache utilisée et de la disposition du tableau dans la mémoire utilisée par le compilateur.

I-C-2 - « Loop splitting » ou « loop peeling »

C'est la division d'une boucle en plusieurs autres boucles ou bien la suppression de dépendance.

Un cas simple et spécial de cette technique consiste à supprimer une première itération complexe de la boucle et la mettre à l'extérieur de cette dernière.

Voici un exemple de « loop peeling ». On suppose que le code original est :

For j from 1 to 20
A [j] = A [1] + B [j]

Comme cette affectation du tableau A dépend du tableau A lui-même, le compilateur ne peut pas utiliser le parallélisme en toute sécurité. Pour cela, il supprime l'affectation problématique de A[1] de l'intérieur de la boucle et la met à l'extérieur.

On obtient donc après ce type d'optimisation :

A [1] = A [1] + B [1]
For j from 2 to 20
A [j] = A [1] + B [j]

La valeur de A[1] issue du premier calcul peut ensuite être stockée en registre pour l'utiliser à chaque itération de la boucle.

Cette technique d'optimisation est introduite dans le compilateur gcc dans la version 3.4.

I-C-3 - Fusion de boucles

Elle fusionne plusieurs boucles en une seule. Exemple en C :

int i, a[100], b[100];
for (i = 0; i < 100; i++)
{
a[i] = 1;
}
for (i = 0; i < 100; i++)
{
b[i] = 2;
}

L'exécution de ces deux boucles séparées est équivalente au code suivant :

int i, a[100], b[100];
for (i = 0; i < 100; i++)
{
a[i] = 1;
b[i] = 2;
}

Cette technique optimise le temps d'exécution du programme. En outre, il y a une technique similaire appelée fission de boucle qui consiste à exécuter une seule boucle en deux boucles et qui optimise l'utilisation de mémoire et donc qui applique mieux le principe de localité.

I-C-4 - « Loop Unwiding »

La transformation est la mise en place de prochaines affectations dans la même itération et cela pour augmenter le taux de « cache hit ».

Par exemple, une procédure dans un programme a besoin d'effacer cent éléments. Pour l'accomplir, il faut appeler cent fois la fonction delete comme suit :

for (int x = 0; x < 100; x++)
{
delete(x);
}

Avec cette technique, on va diminuer le temps d'exécution et on obtient le code optimisé suivant :

for (int x = 0; x < 100; x += 5)
{
delete(x);
delete(x+1);
delete(x+2);
delete(x+3);
delete(x+4);
}

Avec cette modification, on exécute seulement vingt boucles au lieu de cent. Donc on diminue le nombre d'instructions composées par un test et un « jump » par un facteur cinq. Cependant, quatre nouvelles opérations d'additions sont ajoutées, mais cela peut rester négligeable face aux quatre instructions de bouclage économisées (incrément de x et test de la condition), et dépend du coût des instructions sur le processeur utilisé.

I-C-5 - « Loop unswitching »

C'est le fait d'enlever une structure conditionnelle de l'intérieur de la boucle et de la mettre à l'extérieur. Ensuite, on duplique la boucle, et on met chaque version dans une branche.

Pour illustrer ce cas de figure, on additionne deux tableaux X et Y, et on fait une affectation dépendant de W, une variable booléenne.

On a au début ce pseudo-code :

for i to 1000 do
x[i] = x[i] + y[i];
if (w) then y[i] = 0;
end_for;

La condition à l'intérieur de la boucle rend très difficile un parallélisme en toute sécurité. Et après l'utilisation de cette technique, on obtient :

if (w) then
for i to 1000 do
x[i] = x[i] + y[i];
y[i] = 0;
end_for;
else
for i to 1000 do
x[i] = x[i] + y[i];
end_for
end_if;

Chacune de ces boucles peut être optimisée séparément. On note aussi que le code généré est presque le double en termes de quantité du code initial. Cette technique est introduite dans le gcc version 3.4.

I-C-6 - Inversion de boucle

C'est le remplacement d'une boucle while par un bloc contenant une boucle do…while.

Ce code en C :

int i, a[100];
i = 0;
while (i < 100) {
a[i] = 0;
i++;
}

Est équivalent à :

int i, a[100];
i = 0;
if (i < 100) {
do {
a[i] = 0;
i++;
} while (i < 100);
}

Apparemment, cette technique n'est pas efficace ; la même boucle et un code plus long. Mais la plupart des CPU utilisent les « pipelines » pour exécuter leurs instructions. Donc par nature, un « jump » causera un « pipeline stall », c'est-à-dire une initialisation de la pipeline.

Considérant le code assembleur suivant :

i := 0
L1:  if i >= 100 goto L2
a[i] := 0
i := i + 1
goto L1
L2:

Si i est initialisé à 100, l'ordre de l'exécution des instructions serait :

if i >= 100
goto L2

Et de l'autre côté, si on voit l'ordre de l'exécution des instructions si on initialise i à 99 :

goto L1
if i >= 100
a[i] := 0
i := i + 1
goto L1
if i >= 100
goto L2
<<at L2>>

Et maintenant regardant le code optimisé :

i := 0
if i >= 100 goto L2
L1:  a[i] := 0
i := i + 1
if i < 100 goto L1
L2:

Et si on répète les mêmes exécutions faites dans l'ancien code, on obtient successivement : Pour i=100

if i >= 100
goto L2

Pour i=99

if i < 100
goto L1
a[i] := 0
i := i + 1
if i < 100
<<at L2>>

Et comme on peut le constater, on élimine deux « goto » et donc deux initialisations du pipeline.

II - Facteurs

II-A - La machine elle-même

Plusieurs choix de techniques d'optimisation sont basés sur les caractéristiques de la machine cible. C'est possible parfois de paramétrer ces différents facteurs qui dépendent de la machine, et de ce fait un compilateur peut optimiser plusieurs machines juste en changeant les paramètres. Le compilateur GCC est un parfait exemple de cette technique d'adaptation.

II-B - L'architecture du processeur cible

II-B-1 - Le nombre de registres

Généralement, plus on a de registres, plus facile sera l'opération d'optimisation. En effet, les variables locales peuvent être enregistrées dans les registres et non pas dans la pile. En outre, les résultats intermédiaires peuvent être sauvegardés dans les registres au lieu d'effectuer une opération d'écriture et ensuite une autre opération de lecture pour récupérer le résultat.

II-B-2 - RISC vs. CISC

Les instructions de CISC sont de longueurs variables. Et il y a une panoplie d'instructions possibles qui sont différentes en temps d'exécution. En revanche, les instructions RISC ont généralement la même longueur avec quelques exceptions. En plus, le nombre d'instructions par cycle est presque constant dans le cas où on ne considère pas la durée d'accès mémoire. Ceci dit, les instructions CISC nous offrent une marge par rapport à celles du RISC, pour optimiser certaines opérations. Ce qui reste à faire pour le compilateur est de savoir le coût des différentes instructions et de choisir la meilleure séquence (voire optimisation sur des fenêtres).

II-B-3 - Pipeline

Essentiellement, une pipeline utilise l'unité arithmétique et logique (ALU) pour exécuter plusieurs instructions en même temps et en différentes étapes : décodage d'instruction, décodage d'adresse, lecture mémoire, lecture registre, calcul, écriture mémoire… D'ailleurs, une instruction peut être dans l'écriture de mémoire pendant qu'une autre effectue une lecture registre. Les conflits dans la pipeline se produisent quand une instruction dans une étape de la pipeline dépend du résultat d'une autre instruction qui est devant elle dans la pipeline et qui n'est pas encore totalement exécutée. Ces conflits causent un blocage de la pipeline « Pipeline Stall » et une perte de temps dans laquel le processeur attend la résolution du conflit.

Les optimiseurs peuvent ordonnancer et réorganiser les instructions pour éviter au mieux les blocages du pipeline.

II-B-4 - Le nombre d'unités fonctionnelles

Un processeur peut posséder plusieurs ALU et FPU (unité de calcul en virgule flottante). Cela permettra d'exécuter des instructions en parallèle. Ou en d'autres termes, cela nous permettra de mettre les instructions par paires. Ici aussi un ordonnancement minutieux doit être effectué par le compilateur pour utiliser au mieux les ressources de la plate-forme utilisée. Cela requiert bien sur une connaissance approfondie d'une part des instructions et d'autre part du processeur utilisé.

II-C - L'architecture de la machine

II-C-1 - La taille et le type du cache

Quelques techniques d'optimisations, comme « loop unwiding », permettent d'augmenter la taille du code généré et en même temps vérifier de plus en plus le principe de localité.

II-C-2 - Le temps moyen d'accès mémoire/cache

En ayant connaissance de ce facteur, un compilateur a une connaissance des pénalités causées par les différents types d'opérations mémoire/cache. Ceci est pris en compte dans des applications très spécialisées.

III - Problèmes avec l'optimisation

Au début des histoires des compilateurs, leurs optimisations n'ont pas été plus efficaces que l'optimisation manuelle faite par les programmeurs. Avec l'avancement de la technologie des compilateurs, le résultat est devenu plus efficace qu'une optimisation effectuée par le programmeur. Cela est plus évident avec les architectures RISC et les processeurs VLIW (Very Long Instruction Word).

En revanche, un compilateur qui peut garantir à sa sortie le plus rapide (ou petit) programme compilé est fondamentalement impossible à implémenter. Cela est dû au problème d'arrêt. En effet, selon cette dernière théorie, le compilateur ne peut pas décider automatiquement et dans tous les cas si le programme compilé va se terminer. Cette théorie affirme donc qu'il n'existera jamais de compilateur capable de vous dire, dans tous les cas, que le programme que vous avez écrit bouclera indéfiniment.