Optimisation des compilateurs/Les optimisations des boucles

Les boucles sont une source d'optimisations inépuisables, ainsi qu'un vivier de performance assez important quand on optimise du code. En effet, chaque boucle est exécutée plusieurs fois : toute optimisation va donc rendre chaque itération plus rapide, décuplant ainsi les optimisations qui y sont faites. Parmi les optimisations liées aux boucles, on trouve des optimisations liées aux branchements, au code de la boucle elle-même (pas au code qu'elle itère), mais on trouve aussi des optimisations liées à la hiérarchie mémoire. Dans ce chapitre, nous allons nous concentrer sur les premières, les optimisations liées à la hiérarchie mémoire étant vues dans un chapitre à part.

Les invariants de boucle

Une optimisation, assez intuitive, consiste à sortir un maximum d'instructions du corps de la boucle. Pour cela, le compilateur doit détecter les instructions qui n'ont rien à y faire et peuvent être déplacées hors de la boucle sans effets secondaires. Ces instructions se reconnaissent assez facilement : elles fournissent le même résultat à chaque tour de boucle. Ces résultats sont appelées des invariants de boucles. Les instructions qui calculent ces invariants sont sortis de la boucle, histoire de ne les exécuter qu'une seule fois. Le compilateur sait détecter ces invariants : ils ne dépendent pas de l'indice de la boucle, ni de variables qui en dépendent indirectement. Inutile de faire cela à la main, donc. Sauf dans le cas des fonctions dont le compilateur ne peut dire si elles sont pures ou impures, encore une fois.

La technique de Loop unswitching

Il est possible d'utiliser l'extraction des invariants de boucle pour les conditions situées à l'intérieur de la boucle. Cela permet d’enlever une structure conditionnelle de l’intérieur de la boucle et de la mettre à l’extérieur. Mais pour obtenir un code correct, il faut aussi dupliquer la boucle en deux exemplaires et mettre 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 terme de quantité que le code initial. Cette technique est introduit dans le gcc version 3.4

La réduction en force

Les boucles, et notamment celles qui parcourent un tableau sont aussi une source d'optimisations.

Prenez ce code source :

for (int i = 0; i < ArraySize; ++i)
{
    Array[i] = i;
}

Cela ne se voit pas au premier abord, mais il y a une multiplication cachée dans cette boucle. Pour cela, il faut savoir que l'adresse de l'élément d'indice i est calculée en effectuant le calcul suivant : Adresse de base du tableau + (indice * taille d'un élément). Cette adresse se calcule donc à partir de l'indice de boucle avec une équation de la forme : Constante A + indice * Constante B. Dans une boucle, toute variable dont la valeur suit une équation du type A + (indice * B) s'appelle une variable d'induction.

Et bien ce genre de calcul peut se simplifier : il suffit de remarquer qu'à chaque tour de boucle, on ne fait qu'augmenter l'adresse de la quantité B. Le code se simplifie alors en :

char* base = A;

for (int i = 0; i < ArraySize; ++i)
{
    base += B;
    *pointer = i;
}

Autrefois, cette optimisation était effectuée à la main. D'ailleurs, nombreux sont les programmeurs C qui pensent qu'effectuer cette optimisation à la main est encore utile de nos jours. Toutefois, aujourd'hui, le compilateur sait automatiquement reconnaître les variables d'induction. Dans ce cas, il remplace cette équation par une addition, comme vu au-dessus, ce qui permet de supprimer une multiplication. Cette optimisation s'appelle la réduction en force.

L'inversion de boucle

Cette technique remplace une boucle While par une boucle Do…While dans un If. Cette technique n'est pas vraiment une optimisation en soit, quand on prend une boucle quelconque. Mais cela permet de simplifier certaines boucles : si le compilateur peut prouver que la boucle est exécutée au moins une fois, alors le if devient inutile. Cela arrive sur beaucoup de boucles et notamment pour celles qui parcourent des tableaux. En effet, on sait qu'un tableau possède toujours au moins un élément (sauf dans certains langages de programmation, mais passons). Dans ces conditions, la première itération ne demande de faire un test, comme ce serait le cas avec une boucle While. La boucle peut en réalité se simplifier directement en une simple boucle Do...While. Le If qui entoure la Do...While est alors supprimé.

Par exemple, ce code en C :

i = 0;
while (i < 100) 
{
    ...
}

L'optimisation transforme celui-ci en :

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

Puis, la propagation de constantes va rendre la condition (i < 100) constante, ce qui permet au compilateur de la retirer. Le code devient alors :

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

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

Considérant ce 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 :

1: if i >= 100
2: goto L2

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

1: goto L1
2: if i >= 100
3: a[i] := 0
4: i := i + 1
5: goto L1
6: if i >= 100
7: goto L2
8: <<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

1: if i >= 100
2: goto L2

Pour i=99

1: if i < 100
2: goto L1
3: a[i] := 0
4: i := i + 1
5: if i < 100
6: <<at L2>>

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

Le déroulage de boucles

Si le corps de la boucle a son importance, il ne faut pas oublier que la boucle elle-même utilise des branchements pour s’exécuter. Réduire le nombre de branchements dans une boucle peut donc donner des gains de performances, mais cela ne peut se faire que d'une seule manière : en supprimant des itérations. Cela est possible si le compilateur utilise la méthode du déroulage de boucles. Il s'agit d'une optimisation qui vise à réduire le nombre d'itérations d'une boucle en dupliquant son corps en plusieurs exemplaires. Elle est utilisée pour réduire le coût d’exécution des branchements et de comparaison de la boucle : vu qu'on exécute les branchements à chaque itération, diminuer le nombre d'itérations permet d'en diminuer le nombre également. Évidemment, le nombre d'itérations est modifié de manière à obtenir un résultat correct, afin de ne pas faire des itérations en trop.

Par exemple une procédure dans un programme a besoin d’effacer 100 éléments. Pour l’accomplir, il faut appeler 100 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 20 boucles au lieu de 100. Donc on divise le nombre de comparaisons et de branchements par 5. Cependant 4 nouvelles opérations d'additions sont ajoutées, mais cela peut rester négligeable face aux 4 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é.

Le Strip-mining

Pour obtenir un nombre d'itérations correct, les compilateurs utilisent généralement deux boucles : une qui est déroulée, et une autre qui traite les éléments restants. Cette technique porte le nom de Strip-mining. Par exemple, si je veux parcourir un tableau de taille fixe contenant 102 éléments, je devrais avoir une boucle comme celle-ci :

int indice;

for (indice = 0; indice < 100; indice = indice + 4)
{
    a[indice] = b[indice] * 7;
    a[indice + 1] = b[indice + 1] * 7;
    a[indice + 2] = b[indice + 2] * 7;
    a[indice + 3] = b[indice + 3] * 7;
}
for (indice = 100; indice < 102; ++indice)
{
    a[indice] = b[indice] * 7;
}

Déroulage de boucle et parallélisme

On peut noter que le déroulage de boucle se marie assez bien avec les diverses techniques qui permettent de paralléliser le code source. En effet, certaines boucles ont des itérations indépendantes, qui peuvent théoriquement s’exécuter en parallèle. Mais l'usage d'une boucle fait que les itérations ont une dépendance de contrôle entre elles : chaque itération doit attendre la fin de la précédente pour s’exécuter. Le déroulage de boucle permet au parallélisme de s'exprimer plus facilement, le compilateur pouvant détecter que les itérations sont indépendantes. On verra d'ailleurs dans la section suivante que cela facilite la vectorisation. Comme exemple, on peut reprendre l'exemple cité plus haut, :

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

On voit, une fois la boucle déroulée, que chaque itération de la boucle ne dépend pas des précédentes.

Certaines boucles gagnent à être déroulées à la main, de manière à rendre plus explicite le parallélisme latent. Par exemple, si je prends cette boucle :

unsigned somme = 0;

for (int i= 0; i < 10000; ++i)
{
    somme += tab[i];
}

le compilateur me donnera ceci :

unsigned somme = 0;

for (int i=0; i < 10000; i =  i + 4)
{
    somme += tab[i];
    somme += tab[i+1];
    somme += tab[i+2];
    somme += tab[i+3];
}

Or, le code le plus optimisé est celui-ci :

unsigned somme1 = 0;
unsigned somme2 = 0;
unsigned somme3 = 0;
unsigned somme4 = 0;

for (int i=0; i < 10000; i =  i + 4)
{
    somme1 += tab [i];
    somme2 += tab [i+1];
    somme3 += tab [i+2];
    somme4 += tab [i+3];
}

int somme = somme1 + somme2 + somme3 + somme4;

La raison est simple : les additions dans le corps de la boucle sont indépendantes les unes des autres, ce qui permet à un processeur moderne d'effectuer chaque addition en parallèle. Et le même principe peut s'appliquer pour toute opération qui utilise une variable accumulateur dans une boucle, sous réserve que le calcul le permette (cela demande un calcul associatif).

Déroulage de boucles et vectorisation

Il faut noter que le déroulage de boucle rend la vectorisation du code nettement plus facile. Une instruction dupliquée peut parfois être remplacé par une instruction SIMD unique, dans certains cas de figure

Par exemple, prenons le code suivant, qui multiplie les éléments d'un tableau par sept.

int i; 
for (i = 0; i < 100; ++i)
{
    a[i] = b[i] * 7 ;
}

Déroulons la boucle :

int i; 
for (i = 0; i < 100; i+=4)
{
    a[i] = b[i] * 7 ;
    a[i+1] = b[i+1] * 7 ;
    a[i+2] = b[i+2] * 7 ;
    a[i+3] = b[i+3] * 7 ;
}

On voit alors que les quatre opérations du corps de la boucle peuvent être remplacées par une instruction de multiplication SIMD. Si le processeur dispose d'une instruction de multiplication capable de traiter 4 éléments en une seule fois, la boucle déroulée peut être vectorisée en utilisant une multiplication vectorielle (que nous noterons vec_mul).

int i; 
for (i = 0; i < 100; i+=4)
{
    vec_a[i] = vec_mul ( vec_b[i] , 7 ) ;
}