Les optimisations des compilateurs

Tout d'abord, le compilateur est capable de changer l'ordre des opérations pour profiter au mieux du fonctionnement en pipeline(1) des processeurs modernes. Et à ce petit jeu, aucun programmeur ne peut rivaliser.

La seconde méthode consiste à utiliser les instructions machine les plus adaptées, histoire d'obtenir quelques simplifications. Par exemple, il est possible de remplacer certaines instructions par d'autres, plus rapides. L'exemple le plus connu est celui des multiplications/divisions par une puissance de deux constante qui se transforme facilement en décalage.

Une autre méthode consiste à fusionner des suites d'instructions élémentaires en une seule instruction. Par exemple, prenons le cas d'un processeur qui possède l'instruction MAD qui permet d'effectuer le calcul A + B * C en une seule instruction. Dans un code source écrit dans un langage de haut niveau, on ne peut pas utiliser celle-ci directement, et c'est au compilateur de fusionner une addition avec une multiplication en une seule instruction MAD.

Il est strictement inutile de faire ce genre de chose à la main, à une exception près : les processeurs de traitement de signal. Sur ces processeurs, coder en assembleur permet d'utiliser les modes d'adressage modulo et bit-reverse que le compilateur ne peut pas utiliser facilement.

Le compilateur peut aussi tenter d'utiliser des instructions vectorielles quand c'est possible. Les techniques qui permettent au compilateur de découvrir des suites d'instructions qui peuvent profiter des instructions SIMD(2) des processeurs modernes sont ce qu'on appelle de la vectorisation.

Et à ce petit jeu, un bon programmeur donne un résultat nettement meilleur qu'un compilateur : ces derniers ont beaucoup de mal à optimiser les codes vectoriels. Bien sûr, de telles optimisations ne sont pas évidentes, mais elles peuvent permettre d'obtenir des codes de trois à quatre fois plus rapides !

Un compilateur peut, sous certaines conditions, effectuer des simplifications algébriques. De nombreuses optimisations de ce genre sont possibles pour les entiers : a * b + a * c qui se transforme en a * ( b + c ). Cependant, ces optimisations ne sont pas toujours possibles : par exemple, calculer -( a - b ) avec des entiers ne peut pas être simplifié en -a + b à cause d'une possibilité d'overflow assez bien cachée. Quelque chose de similaire a lieu pour les flottants : les opérations flottantes ne sont pas associatives ni distributives. Mais certains compilateurs ne se gênent pas pour faire les simplifications, à partir d'un certain niveau d'optimisation.

On trouve aussi la même chose pour les booléens, sous certaines conditions. Par exemple, l'expression if(!a && !b) peut être simplifiée en if (! (a || b) ). Mais ces optimisations ne sont pas toujours possibles, modifier l'ordre des comparaisons ou en supprimer peut ne pas donner le même résultat. Dans un tel cas, sachez que simplifier ces expressions à la main permet d'améliorer la lisibilité de votre programme (même si c'est souvent une amélioration marginale).

Certains calculs dans un programme sont totalement constants. Par exemple, des calculs du style : int a = 2 * 3.1415926535 sont simplifiables. De même, un compilateur peut réduire de nombreux calculs du type a + 0, a * 0, a * 1, etc. Dès qu'une expression a tous ses opérandes constants, un compilateur peut parfois calculer le résultat lui-même et remplacer l'expression par son résultat : on parle de constant folding.

Mais attention, cela n'est valable que dans un cas bien précis : celui des expressions et fonctions qui donnent le même résultat pour des opérandes identiques. Il existe des calculs qui ne respectent pas cette règle, notamment certaines fonctions : ce sont des expressions ou fonctions dites impures. Et un compilateur n'a pas vraiment de moyens pour savoir si une fonction est pure ou impure : il devrait regarder et analyser son code, ce qui demanderait trop de ressources pour un résultat qui n'en vaut pas le coup. Dans ces conditions, le compilateur considère toutes les fonctions comme étant impures. La conséquence, c'est que de très nombreuses optimisations seront rendues impossibles si jamais on trouve une fonction au mauvais endroit dans le code source.

Les compilateurs sont aussi capables de propager ces constantes. Cela veut dire remplacer les noms de variables dont la valeur est constante par la constante elle-même.

Par exemple, le code suivant :

const int a = 2;
const int b = 6;
const int c = 8;

int delta = b*b - 4*a*c;

peut être remplacé par :

const int a = 2;
const int b = 6;
const int c = 8;

int delta = 6 * 6 - 4 * 2 * 8;

On peut remarquer que cette optimisation se marie particulièrement bien avec le constant folding. Dans l'exemple du dessus, combiner les deux optimisations permet de calculer le résultat directement :

const int a = 2;
const int b = 6;
const int c = 8;

int delta = - 28;

Certains calculs sont inutiles ou redondants : il arrive souvent que des expressions calculent la même valeur que ce soit dans le code source ou dans la représentation intermédiaire d'un programme. Dans ce cas, une valeur est calculée plusieurs fois à des endroits relativement proches, par des suites d'instructions séparées.

Par exemple, prenons ce cas de figure :

#include <limits>

float solve_secondDegre_equation(float a, float b, float c)
{
    if (b*b - 4*a*c > 0)
    {
        return ( -b + sqrt (b*b - 4*a*c) ) / (2 * a) ;
    }
    else if (b*b - 4*a*c == 0)
    {
        return -b / (2 * a) ;
    }
    else
    {
        return std::quiet_NaN();
    }
}

Comme vous le voyez, le delta (b*b - 4*a*c) est recalculé plusieurs fois. Un compilateur pourrait remplacer automatiquement ce code redondant par ceci :

#include <limits>

float solve_second_Degre_equation(float a, float b, float c)
{
    float temp = 2 * a ;
    float temp2 = b*b - 4*a*c ;

    if (temp2 > 0)
    {
        return ( -b + sqrt (temp2) ) / temp ;
    }
    else if (temp2 == 0)
    {
        return -b / temp ;
    }
    else
    {
        return std::quiet_NaN();
    }
}

Le compilateur peut stocker cette valeur dans une variable, variable qui est alors réutilisée en lieu et place du résultat des expressions redondantes. Expressions redondantes qui sont alors supprimées.

Cependant, le compilateur ne peut rien faire si la valeur est calculée par une fonction impure. Quand le compilateur voit que deux fonctions impures sont appelées avec des arguments identiques, il ne peut pas savoir si le résultat renvoyé sera le même et ne peut pas remplacer la seconde exécution de la fonction par une simple lecture de variable.

Il faut toutefois signaler qu'il y a des exceptions à cette exception. Par exemple, prenez le code suivant :

for (unsigned i = 0; i < strlen(string); ++i)
{
   ...
}

Un bon compilateur C peut parfaitement optimiser de lui-même l'usage de la fonction strlen, et donner un code assembleur équivalent au code suivant :

unsigned length = strlen(string);

for (unsigned i = 0; i < length; ++i)
{
   ...
}

Quoi qu'il en soit, éviter des expressions longues comme le bras est un plus clairement appréciable en termes de lisibilité, et factoriser des expressions dans des variables correctement nommées est alors d'une grande aide.

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.

Les boucles sont définitivement une source d'optimisation assez importante. Il faut dire qu'un calcul dans une boucle sera exécuté de nombreuses fois (une fois par itération), ce qui fait que supprimer un seul calcul peut faire gagner quelques milliers de cycles d'horloge. Dans ces conditions, il faut sortir un maximum de choses des boucles.

Or, il arrive que certains calculs fournissent le même résultat à chaque tour de boucle : on parle d'invariant de boucles. Dans ces conditions, il vaut mieux sortir ces invariants 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.

Il arrive aussi que certains calculs soient inutiles. Par inutiles, on veut dire que leur résultat n'est pas utilisé dans le programme. Plus précisément, ces résultats sont écrits dans une variable qui n'est jamais lue. Il suffit que la variable soit dans une fonction pour que le compilateur puisse détecter qu'une variable ne sera jamais utilisée. Le compilateur peut alors supprimer les instructions qui ne servent qu'à calculer ce résultat, et ne servent à aucun autre calcul. Ces calculs inutiles apparaissent souvent après que la propagation de constantes a fait son travail.

Une optimisation bien connue est l'inlining. Cette technique consiste à éliminer les appels de fonction d'un programme : le corps de la fonction est intégralement recopié à chaque endroit où celle-ci est appelée. Il faut remarquer que cette technique a tendance à fortement augmenter la taille du code : au lieu d'un seul exemplaire de la fonction, celle-ci est recopiée en autant d'exemplaires qu'il y a de sites d'appel. Aussi, elle n'est effectuée que pour des fonctions relativement petites.

Cela permet d'éliminer l'appel de la fonction, ainsi que tout le code qui prépare l'appel. Dans certains cas, cela permet aussi d'améliorer l'usage de la mémoire cache (pas de saut dans la mémoire). L'inlining permet aussi à d'autres optimisations de fonctionner plus efficacement, comme la propagation de constantes. Il permet aussi d'obtenir des blocs de code linéaires de « grande taille », permettant au réordonnancement d'instructions de fonctionner au mieux.

Dans certains langages de programmation, les accès à un tableau avec un indice invalide vont lever une exception ou faire planter le programme. Pour cela, le compilateur insère des comparaisons qui vérifient la validité de l'indice. Ces comparaisons prennent évidemment du temps de calcul, et le compilateur dispose d'optimisations pour en éviter qui seraient inutiles. Il peut notamment prouver que certains morceaux de code ne peuvent pas donner lieu à des accès en dehors du tableau, pour éviter d'ajouter les tests de validité de l'indice. C'est notamment le cas avec ce code :

int sum = 0;

for (int i = 0; i < Array.size(); ++i)
{
    sum += Array[i];
}

Une autre source d'optimisations provient des branchements de type if..else dont la condition est constante. Les conditions toujours vraies ou fausses apparaissent souvent suite à la propagation de constantes. Si jamais une condition se retrouve être toujours vraie ou fausse, alors le bloc if..else qui correspond est supprimé et seule la portion qui sera toujours exécutée sera alors intégrée dans le programme.

Par exemple, le code suivant :

int a;

if (true)
{
    a += 6;
}
else
{
    a += 9;
}

sera transformé en :

int a;

a += 6;

Maintenant, prenons le cas d'un branchement A, dont l'instruction/adresse de destination est un autre branchement B, qui lui-même pointe sur une instruction C. Au cours de l'exécution, le branchement va envoyer le processeur sur B, qui va aussitôt brancher vers C : autant brancher directement vers C. Dans ce cas, le compilateur va modifier l'adresse de destination du branchement A pour qu'il pointe directement sur l'instruction C.

Le compilateur peut aussi effectuer des transformations sur les boucles. La transformation la plus basique est ce qu'on appelle le déroulage de boucles. Dérouler des boucles consiste à effectuer plusieurs tours de boucle d'un seul coup, en recopiant le corps de la boucle en plusieurs exemplaires. Cette technique est clairement utile pour diminuer le nombre de branchements exécutés : 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.

Exemple, prenons cette boucle :

int indice;

for (indice = 0; indice < taille_tableau; indice = indice + 1)
{
    a[indice] = b[indice] * 7;
}

Celle-ci peut être déroulée comme suit :

int indice;

for (indice = 0; indice < taille_tableau ; 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;
}

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. 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; ++i)
{
     a[indice] = b[indice] * 7;
}

Mais certaines boucles gagnent à être écrites de cette manière à la main, avec quelques optimisations. En effet, 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 superscalaire(3) ou à exécution dans le désordre 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).

Cette technique consiste à fusionner deux boucles qui itèrent avec les mêmes indices en une seule.

Par exemple, le code suivant :

for (int j = 0; j < 100; ++j)
{
    array1[j] = 25;
}
for (int i = 0; i < 100; ++i)
{
    array2[i] = i;
}

donnera ceci :

for (int i = 0; i < 100; ++i)
{
    array1[i] = 25;
    array2[i] = i;
}

On a vu plus haut que les compilateurs sont capables de sortir certains calculs des boucles. Les calculs en question sont des calculs qui ne dépendent pas de l'indice de la boucle, que ce soit directement ou indirectement : on parle d'invariants de boucle. Il est possible d'utiliser l'extraction des invariants de boucle pour des conditions.

Par exemple, le code suivant :

for (i = 0; i < 1000; i++) 
{
    if (w) 
    {
        y[i] = 0;
    }
    else
    {
        x[i] += y[i];
    }
}

Deviendra :

if (w) 
{
    for (i = 0; i < 1000; i++) 
    {
        y[i] = 0;
    }
} 
else 
{
    for (i = 0; i < 1000; i++) 
    {
        x[i] += y[i];
    }
}

Enfin, dernière optimisation : transformer les boucles while (ou for, ne soyons pas raciste), en boucle do..while entourées par un if. L'astuce consiste à vérifier avec le if si la boucle doit être exécutée au moins une fois, et à exécuter la boucle do..while si c'est le cas. Si jamais le compilateur peut prouver que la boucle est exécutée au moins une fois, alors le if devient inutile. Cette optimisation permet de supprimer une exécution d'un branchement, sans compter qu'elle permet aussi à certaines optimisations de fonctionner au mieux, notamment la suppression des variables d'induction.

Il arrive souvent que l'on n'ait pas assez de registres pour stocker des variables temporaires. Dans ce cas, le contenu de certains registres est alors sauvegardé sur la pile pour une utilisation ultérieure : on parle de spilling. À ce petit jeu, les programmeurs assembleurs disposent d'une optimisation dont aucun compilateur actuel n'est capable : ils peuvent sauvegarder les registres, non pas sur la pile, mais dans les registres MMXMultiMedia eXtensions ou SSEStreaming SIMD Extensions. Mais si cette optimisation n'est pas possible automatiquement, il vaut mieux recalculer certaines variables temporaires que de les mémoriser temporairement dans un registre : on parle de rematérialisation. Cette optimisation est en quelque sorte l'inverse de celle qui supprime les expressions redondantes.

Cette technique consiste à faire l'inverse de la fusion de boucle : des boucles qui itèrent sur des tableaux différents sont scindées en deux. Ainsi, chaque boucle travaillera indépendamment sur chaque tableau d'un bloc (on parcourt un tableau puis l'autre). Cette technique améliore la localité et la gestion du cache comparé à une seule boucle qui piocherait les données dans un tableau puis dans l'autre. Suivant la situation, cette optimisation sera plus ou moins efficace par rapport à la fusion de boucle : le compilateur dispose d'heuristiques pour déterminer quand utiliser telle ou telle optimisation suivant la situation.

Certains langages stockent les tableaux de tableaux ligne par ligne : des données d'une ligne sont consécutives en mémoire. Dans ces conditions, il vaut mieux parcourir les tableaux ligne par ligne, histoire de profiter de la mémoire cache du processeur et de diverses techniques de prefetching. D'autres langages fonctionnent colonne par colonne.

Dans ce cas, le compilateur peut parfois échanger l'ordre des boucles pour parcourir les tableaux ligne par ligne, ou colonne par colonne (selon le langage). Mais cela ne fonctionne que quand le compilateur peut prouver que la modification n'a pas d'effet de bord, ce qui n'est pas toujours possible. Par exemple, le compilateur n'a pas le droit de le faire dans un cas pareil :

for (int i = 0; i < nbLignes; ++i)
{
    for (int j = 0; j < nbColonnes; ++j)
    {
         tab[i][j] = fonction(i,j);
    }
}

Quand on sait que cette optimisation permet de gagner assez facilement en performances, parfois d'un facteur 10, mieux vaut être prudent et la faire à la main.