Optimisation des compilateurs/Version imprimable

Optimisation des compilateurs

Une version à jour et éditable de ce livre est disponible sur Wikilivres,
une bibliothèque de livres pédagogiques, à l'URL :
https://fr.wikibooks.org/wiki/Optimisation_des_compilateurs

Vous avez la permission de copier, distribuer et/ou modifier ce document selon les termes de la Licence de documentation libre GNU, version 1.2 ou plus récente publiée par la Free Software Foundation ; sans sections inaltérables, sans texte de première page de couverture et sans Texte de dernière page de couverture. Une copie de cette licence est incluse dans l'annexe nommée « Licence de documentation libre GNU ».

Généralités sur les optimisations des compilateurs

Au début des histoires des compilateurs, leurs optimisations n'ont pas été plus efficaces que l'optimisation manuelle faite par les programmeurs. Il faut dire que les programmeurs, autrefois très doués en assembleur, avaient à leur disposition un grand nombre de techniques d'optimisation dans leur boite à outils, alors que les compilateurs n'implémentaient qu'un faible nombre d'algorithmes d'optimisation. De plus, l'architecture des processeur rendait l'optimisation à la main plus facile. Les processeurs étaient alors de type CISC, ce qui veut dire qu'ils implémentaient une large gamme d'instructions. Les compilateurs étaient à l'époque incapables d'utiliser certaines instructions très complexes, là où les programmeurs assembleur pouvaient le faire aisément.

Mais avec l'avancement de la technologie des compilateurs, les compilateurs sont devenus plus efficaces que l'optimisation manuelle, effectuée par le programmeur. Du moins, c'est encore le cas sur les architectures modernes usuelles, comme les architectures des PC actuels (x86). Le résultat est encore plus probant sur les architectures RISC et les processeurs VLIW (Very Long Instruction Word), qui sont "compiler friendly". Il reste cependant quelques niches où les programmeurs peuvent encore battre un compilateur, comme la programmation sur des DSP, des processeurs de traitement de signal aux architectures aussi intéressantes que complexes.

Pour l'anecdote, un compilateur qui peut garantir à sa sortie le plus rapide (ou petit) programme compilé est fondamentalement impossible à implémenter. Ceci 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 démontre 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.

L'influence de l'architecture sur l'optimisation

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.

L’architecture du processeur cible

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.

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 celle 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).

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é. Ces conflits causent un blocage du pipeline « Pipeline Stall » et une perte de temps dans lequel le processeur attend la résolution du conflit.

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

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 plateforme utilisée. Cela requiert bien sur une connaissance approfondie d’une part des instructions et d’autre part du processeur utilisé.

L’architecture de la machine

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é.

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.

Les optimisations liées aux constantes

Beaucoup des optimisations des compilateurs sont liées à des expressions qui manipulent des constantes. Par exemple, certains calculs dont une opérande est constante peuvent être simplifiés. Nous allons les détailler ci-dessous.

La propagation des constantes

La première optimisation de ce type, la plus connue, est la propagation des constantes. Ce n'est pas un optimisation à proprement parler, vu qu'elle n'est pas directement à l'origine de gains de performance. Mais elle permet aux autres optimisations liés aux constants de donner le meilleur d'elles-mêmes. Sans propagation des constantes, l'élimination des calculs constants ou des conditions inutiles ne pourrait pas se faire. C’est pourquoi nous en parlons dès le début de ce chapitre.

Elle consiste à remplacer les 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;

L'élimination des calculs/conditions constants

Quand une expression a tous ses opérandes constants, on sait qu'elle va systématiquement renvoyer le même résultat (sauf dans quelques cas particuliers, que nous aborderons plus bas). Le compilateur peut alors calculer ce résultat et remplacer l'expression par celui-ci. Cette optimisation porte un nom : on parle de constant folding. Il en existe plusieurs cas particuliers, le plus simple étant celui des expressions arithmétiques. Nous n'allons pas l'aborder, mais allons cependant parler de quelques cas particuliers, assez intéressants à connaitre.

L'élimination des expressions arithmétiques

Le cas le plus simple est clairement celui où toutes les opérandes sont constantes : le compilateur peut alors faire le calcul lui-même et simplement mettre le résultat directement dans le code du programme. Par exemple, prenons le code suivant. Vous remarquerez qu'il s'agit de l'exemple obtenu dans la section précédente, le résultat de la propagation des constantes dans l'exemple cité.

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

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

Après application du constant folding, ce code devient tout simplement :

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

int delta = - 28;

Dans l'exemple précédent, l'expression voit l'intégralité de ses opérandes devenir constantes. Mais ce n'est pas systématique et il arrive que l'expression ne soit que partiellement simplifiée. Typiquement, certaines opérandes vont devenir constantes, alors que d'autres vont rester des variables. L'économie en calcul est quand même substantielle.

Il arrive que la propagation de constante ne permette pas d'économiser des calculs, mais transforme une opération entre deux variables en une opération agissant sur une variable et une constante. Le calcul n'est alors pas éliminé, mais transformé. Par exemple, prenons le code suivant :

const int a = 2;
int b = ... ; // la valeur de b est non-constante

int delta = a * b ;

La propagation de constantes va le simplifier en :

int b = ... ; // la valeur de b est non-constante

int delta = 2 * b ;

Le calcul n'a pas disparu, on n'a pas fait d'économie, le nombre d'opérations effectuées par le processeur est inchangé. Malgré tout, cela permet quelques simplifications. La première est que les opérandes constantes utilisent les modes d'adressages plus efficients, qui n'utilisent pas de registres. Dans l'exemple plus haut, on a fait disparaitre une variable, la valeur 2 est intégrée dans l'instruction d'addition via le mode d'adressage immédiat, ce qui a permis d'économiser un registre. Optimisation très importante !

Une autre source d'optimisation est qu'on peut remplacer le calcul par un autre, plus rapide. Pour en donner un 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. Comme autre exemple, multiplier une expression par 0 ou par 1 est inutile, le résultat étant connu à l'avance. Même chose pour une addition ou soustraction avec 0, ou une division par 1. Le compilateur peut reconnaitre de tels cas et supprimer l'instruction inutile. Mais nous verrons cela plus tard dans la suite du cours. Disons juste que pour le moment, c'est un optimisation qui permet d'en appliquer d'autres.

La propagation de constantes est fiable quand la déclaration de la constante et son utilisation se trouve dans le même fichier ou module. Dans le cas où ce n'est pas le cas, après compilation des deux modules (celui qui déclare la constante, et celui qui l'utilise), la modification ultérieure de la valeur de la constante requiert la recompilation du module l'utilisant ; sinon le module continue d'utiliser une version obsolète de la valeur de la constante.

L'élimination des conditions constantes

Le second cas particulier élimine les branchements de type if...else dont la condition est constante. 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;

Évidemment, les conditions constantes (toujours vraies ou fausses) ne sont jamais écrites telles qu'elles dans un programme. Elles apparaissent généralement une fois que la propagation de constante a fait son travail. Et de manière générale, les conditions constantes sont presque toujours liées à l'application d'autres optimisations liées aux constantes, que nous verrons plus loin.

Les appels de fonctions avec des arguments constants

Un autre cas particulier est celui de l'appel du fonction avec des arguments constants. On précise que tous les arguments de la fonction doivent être constants pour que la technique fonctionne. Dans ce cas , le compilateur peut simplement calculer le résultat renvoyé par la fonction. Par exemple prenons ce code :

int abs (int n)
{
  if (n > 0)
    return n ;
  else
    return -n ;
}

int main(int n)
{
  int a = -4 ;
  return abs(a) ;
}

On voit que la fonction est appelée avec tous ses arguments constants. Le compilateur peut alors calculer son résultat et remplacer l'appel par une simple affectation du résultat. Le code se simplifie alors en :

int abs (int n)
{
  if (n > 0)
    return n ;
  else
    return -n ;
}

int main(int n)
{
  return 4 ;
}

Mais attention, cette optimisation 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, c'est-à-dire les expressions et fonctions sans effet de bord. Il existe des calculs qui ne respectent pas cette règle, notamment certaines fonctions : ce sont des expressions ou fonctions dites impures.

Un compilateur n'a pas vraiment de moyens pour savoir si une fonction est pure ou impure : il devrait regarder et analyser le code de la fonction, 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 optimisations des expressions et calculs

De nos jours, les compilateurs cherchent par tous les moyens à réduire la vitesse d'exécution des programmes qu'ils compilent. Cela peut se faire de plusieurs manières, mais toutes se rapportent à deux techniques assez générales : soit on diminue le nombre d'instructions pour faire la même chose, soit on utilise des instructions équivalentes mais qui sont plus rapides. Les deux méthodes sont complémentaires, ce qui fait qu'elles sont utilisées de concert. Elles permettent de transformer une suite d'instructions en une autre suite, qui fait exactement la même chose, mais plus rapidement

Nul besoin de magie pour ce faire, surtout pour les langages de haut-niveau. Du fait de leur abstraction, un code source peut être traduit en langage machine de plusieurs manières différentes, qui donnent chacune une suite d'instruction différente. Le compilateur a juste besoin de trouver celle qui donne la suite d'instruction la plus rapide. Généralement, les compilateurs font une traduction directe du code source en langage machine, et améliorent ensuite le code obtenu. Pour l'améliorer, ils appliquent diverses transformations et simplifications sur le code machine obtenu.

Ces simplifications sont souvent effectuées, par souci de simplicité, sur des suites de quelques instructions, qui correspondent généralement à une fonction ou à une entité précise du programme. Mais d'autres peuvent être appliquées au-delà des barrières des fonctions et peuvent s'appliquer sur des suites plus grandes, voire sur tout un programme. En clair, on peut classer ces techniques en trois catégories :

• Les premières techniques remplacent une instruction assez complexe par une instruction plus simple, mais équivalente.
• Les secondes s'appliquent localement, à savoir qu'elles simplifient une suite de quelques instructions adjacentes (une fonction, par exemple).
• Les dernières s'appliquent globalement sur tout le programme et permettent d'obtenir des gains plus importants mais avec une implémentation plus complexe.

Dans ce qui va suivre, nous allons voir chaque type d’optimisation dans l'ordre indiqué ci-dessus.

Les optimisations des instructions

Le premier type d'optimisation des calculs consiste à remplacer une instruction par une autre, plus rapide. Évidemment, cette technique ne s'applique pas systématiquement : les concepteurs de processeur ne sont pas stupides et ne créent pas d'instructions complexes inutilement. Le remplacement ne peut se faire que dans quelques cas particuliers, quand les opérandes ont des valeurs particulières. Par exemple, on peut citer le cas d'une multiplication par une puissance n de 2 (2ⁿ) revient à effectuer un décalage de n bits vers la gauche (vers les bits de poids fort). On pourrait aussi citer le cas du modulo par une puissance de deux, équivalent à un ET logique avec le masque adéquat. Beaucoup de ces simplifications sont expliquées dans le livre « Les opérations bit à bit », disponible sur Wikilivres.

Les optimisations locales

Les optimisations locales s'appliquent sur une suite d'instruction, qui est limitée par les règles de portée du langage de programmation source. Pour simplifier, on peut dire que ces suites correspondent le plus souvent à une fonction, un sous-programme, une méthode (selon le langage utilisé). Ces techniques sont assez diverses : certaines changent l'ordre des calculs, de manière à mieux utiliser les registres ou le pipeline du processeur, d'autres vont simplifier des suites de calculs.

Les simplifications algébriques

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).

La suppression des calculs inutiles

Il arrive que certaines instructions 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 existe de nombreux algorithmes pour détecter de tels résultats, mais la plupart examinent des fonctions, et pas plus. Ils examinent si la variable est exploitée dans le corps de la fonction et/ou retournée : si elle ne l'est pas, alors elle est inutile. Le compilateur peut alors supprimer les instructions qui calculent ce résultat, qui ne servent à rien. Ces calculs inutiles apparaissent souvent après que la propagation de constantes a fait son travail.

La suppression des calculs redondants

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.

Prenons l'exemple classique, à savoir une simple boucle qui parcourt une chaine de caractère.

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

Cette boucle recalcule la longueur de la chaine à chaque itération de la boucle, ce qui donne des calculs redondants. Or, un bon compilateur C peut peut stocker cette valeur dans une variable, variable qui est alors réutilisée en lieu et place du résultat des expressions redondantes. Dans notre exemple, il va 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)
{
   ...
}

Il faut préciser que cette technique n'est pas toujours possible. Notamment, 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 :

L'optimisation sur des fenêtres « peephole »

Cette technique, appliquée après génération du code machine, examine quelques instructions adjacentes et détecte s'il est possible de les remplacer par une instruction ou une séquence d’instructions plus courte.

Le cas classique est celui de l'instruction MAD, disponible sur de nombreux processeurs, 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 on doit utiliser une addition et une multiplication à la place. C'est au compilateur de fusionner l'addition avec une multiplication en une seule instruction MAD.

Un exemple d’optimisation de ce type est l’élimination des lectures redondantes.

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

On peut en donner un autre exemple avec 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.

La vectorisation

Un autre exemple, plus intéressant, est celui des instructions vectorielles. Le compilateur possède de nombreuses techniques qui permettent au compilateur de découvrir des suites d'instructions qui peuvent profiter des instructions SIMD des processeurs modernes. L'ensemble des techniques sont ce qu'on appelle la vectorisation. De nos jours, les compilateurs font du bon travail et donnent des résultats nettement meilleurs que la majorité des programmeurs quand il s'agit de vectoriser un code source. Mais un bon programmeur peut cependant faire mieux qu'un bon compilateur, si on lui laisse la possibilité d'utiliser l'assembleur. Évidemment, cela demande des programmeurs extrêmement compétents en assembleur, qui maitrisent l'architecture des ordinateurs sur les doigts de la main, mais cela peut donner des gains assez importants pour certaines fonctions particulières. Le cas classique est celui de l'utilisation des instructions SIMD dans la programmation de routines de traitement de signal ou de vidéo, qui peut donner des fonctions de trois à quatre fois plus rapides !

L'ordonnancement des instructions

Les compilateurs modernes sont capables de changer l'ordre des opérations pour profiter au mieux du pipeline des processeurs modernes. Ils vont pour cela échanger des instructions de place, ce qui permettra au processeur de les exécuter en même temps. Mais cela n'est pas toujours possible, en raison de contraintes appelées dépendances. Celles-ci sont nombreuses et il en existe plusieurs types : dépendances de données, de contrôle, structurelles, etc. Le cas classique est celui où une instruction exploite le résultat d'un calcul précédent : on ne peut alors pas échanger ces instructions de place, pour des raisons évidentes. De même, on ne peut pas faire passer un calcul avant un branchement, si celui-ci dépend de son résultat. Ces optimisations donnent souvent de bons résultats, mais leur utilisation pratique dépend fortement du pipeline du processeur. On n'optimise pas un code source de la même manière pour un pipeline a 5 étages que pour un pipeline à 20 étages... Tout cela limite les possibilités de réorganisation des instructions, même si les compilateurs disposent de quelques techniques pour limiter les dégâts.

Les optimisations des branchements

Les branchements sont une véritable plaie pour les processeurs modernes dotés d'un pipeline. Certes, les processeurs modernes disposent de techniques pour réduire leur impact sur les performances, la plus connue étant de loin la prédiction de branchements. Cependant, éliminer des branchements a quand même des effets sur les performances. Elle libère de la place dans les tampons de l'unité de prédiction de branchement (les Brnch Target Buffer), elle améliore l'utilisation du pipeline, etc. Mais surtout, supprimer des branchements permet aux autres optimisations du compilateur de mieux faire leur travail. En effet, les branchements entrainent l'apparition de dépendances de contrôles, qui empêchent certains déplacements de calculs : il est impossible de déplacer certains calculs avant un branchement, de les faire sortir d'une fonction, etc. Pour comprendre cela, rappelons que la majorité des optimisations travaillent sur des suites d'instructions linéaires, libres de tout branchements, ces suites portant le nom de blocs de base (basic blocs, en anglais). Les ré-ordonnancements d'instructions, ainsi que certaines optimisations, ne peuvent se faire qu'à l'intérieur d'un de ces bloc de base. Éliminer des branchements permet d'obtenir des blocs de base plus gros, donnant plus de possibilités de ré-ordonnancement ou de simplifications au compilateur. Bref, éliminer des branchements est toujours une bonne chose, et nous allons voir comment le compilateur s'y prend pour ce faire.

L'inlining

Une autre 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. Les gains liés à cette optimisation ont plusieurs origines :

• En premier lieu, cela permet d'éliminer l'appel de la fonction, ainsi que tout le code qui prépare l'appel, qui sauvegarde les registres, etc. Celui-ci étant assez couteux (sauvegarder des registres et empiler les arguments n'est pas gratuit), le gain en performance peut être substantiel.
• Dans certains cas, cela permet aussi d'améliorer l'usage de la mémoire cache. En effet, l'inlining donne un code plus linéaire. Après inlining, le processeur balaye la mémoire octet par octet, au lieu de sauter d'une fonction à une autre à chaque appel. La suite d'instruction obtenue repsecte donc mieux le principe de localité spatiale, ce qui est apprécié autant par le cache que par les circuits de prefetching.
• 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.

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. Le programme final prend donc plus de place. Il faut signaler que cette augmentation de la taille du code peut avoir un effet négatif sur les performances, en perturbant l'usage de la mémoire cache. En effet, qui dit code plus gros dit plus de mémoire cache utilisée. On comprend pourquoi cette optimisation n'est effectuée que pour des fonctions relativement petites, pour éviter de trop faire augmenter la taille du code et de nuire aux performances.

Le Bound Cheking

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];
}

La fusion de branchements

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.

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 ) ;
}

Les optimisations liées à la hiérarchie mémoire

À l'heure actuelle, la majorité des instructions d'un programme sont des accès mémoire, et non des instructions de calculs ou des branchements. Et cela a une conséquence assez fâcheuse : obtenir de bonnes performances demande de faire bon usage de la hiérarchie mémoire, que ce soit au niveau du compilateur ou du programmeur. C'est pour cela que les compilateurs disposent d'optimisations assez intéressantes, qui permettent d'exploiter correctement les structures de données choisies par le programmeur. Ce chapitre va aborder ces optimisations, et vous expliquer en quoi elles consistent.

La re-matérialisation

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 MMX ou SSE. 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.

Les optimisations des parcours de tableaux

Dans la plupart des cas, les compilateurs ne peuvent pas changer les structures de données en d'autres, plus adaptées aux hiérarchies mémoires actuelles. À la place, les compilateurs optimisent les parcours de tableaux : ils changent l'ordre de parcours des tableaux, ou le sens de traversée. Pour cela, ils modifient les boucles qui permettent de faire ces parcours. C'est pour cela que les optimisations que nous allons voir vont toutes impliquer des boucles, au point qu'elles auraient parfaitement eu leur place dans le chapitre précédent. Cette optimisation permet de gagner assez facilement en performances, parfois d'un facteur 10, parfois plus.

Le changement de l’ordre des boucles

L'optimisation consiste à changer l’ordre des boucles entrelacées, histoire de parcourir les tableaux ligne par ligne, au lieu de les traverser colonne par colonne. Pour comprendre ce que fait cette optimisation, il faut savoir que les langages de programmation usuels stockent les tableaux de tableaux ligne par ligne : des données d'une ligne sont consécutives en mémoire, et les lignes sont placées les unes à la suite des autres 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 préchargement (prefetching). D'autres langages fonctionnent colonne par colonne.

L'optimisation d'échange de boucle demande juste d'échanger une boucle externe avec une interne, afin de respecter le principe de localité : cela 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 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

Un défaut de cette optimisation est qu'elle dépend de la technique du cache utilisée et de la disposition du tableau dans la mémoire utilisée par le compilateur. Elle ne s'applique pas de la même manière selon que le langage stocke les tableaux de tableaux ligne par ligne ou colonne par colonne, par exemple. De plus, elle 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);
    }
}

La 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 équivalent 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é.

La division de boucles (« Loop splitting » ou « loop peeling »)

C’est la division d’une boucle en plusieurs autres boucles ou bien la suppression de dépendance. 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.

Un cas simple et spécial de cette technique consiste à supprimer une première itération complexe de la boucle et de 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] issu 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.

Les optimisations de la taille du code

Si la vitesse des programmes peut être optimisée, les compilateurs peuvent aussi jouer sur la taille du programme. La taille d'un programme en elle-même n'est pas importante pour des programmes PC puisque la majorité d'entre eux possèdent plusieurs gibioctets de RAM, ce qui laisse une grande marge. Par contre, diminuer la taille du code a des effets indirects sur les performances de ces machines en économisant de la mémoire cache. L'optimisation de la taille du code a cependant une plus grande importance sur certaines applications embarquées ou destinées à l'informatique industrielle, qui doivent faire avec des machines peu puissantes.

Il faut signaler que, parmi les optimisations précédentes, certaines ont un effet sur la taille du code. C'est le cas des simplifications de calculs, des optimisations qui permettent de supprimer des calculs inutiles, la propagation des constantes, le constant folding, la fusion de boucle, l’élimination des branchements inutiles, etc. Mais l'inverse est aussi vrai : certaines optimisations qui rendent les programmes plus rapides augmentent la taille du code. C'est notamment le cas de l'inlining, du déroulage de boucles, etc. Aussi, ne vous étonnez pas si les optimisations que nous allons voir sont, pour certaines, l'exact inverse de certaines optimisations vues précédemment.

Le choix des instructions

La première optimisation consiste à choisir les instructions les plus courtes quand on peut utiliser plusieurs instructions pour une même opération. L'exemple classique sur les processeurs x86 est la mise à zéro d'un registre : il vaut mieux effectuer un XOR qu'un MOV. Par exemple, XOR EAX EAX est plus court que MOV EAX 0. Le seul problème, c'est que les instructions courtes ne sont pas forcément les plus rapides, or le compilateur a tendance à choisir des instructions plus longues, mais plus rapides.

La jonction de branchements

Il est possible que dans un if…else, certaines lignes de code soient recopiées à la fois dans le if et dans le else. Il arrive de plus que le résultat de ces lignes de code soit totalement indépendant du contenu du else ou du if.

Prenez cet exemple :

if (a > 0)
{
    --a;
    ++b;
}
else 
{
    ++a;
    ++b;
}

On voit bien que la ligne ++b peut être factorisée vu qu'elle est totalement indépendante du contenu du if et du else. Un compilateur peut effectuer automatiquement cette transformation, ce qui donne :

++b;

if (a > 0)
{
    --a;
}
else 
{
    ++a;
}

L'abstraction de procédure

Une autre technique très utile est l'abstraction de procédure, aussi appelé factorisation de code. Ce nom traduit bien ce que fait cette technique : elle factorise des morceaux de code identique en un seul. Plus précisémment, elle détecte des morceaux de code présents en plusieurs exemplaires et les transforme en fonction : les exemplaires sont alors retirés du programme, et sont remplacés par un appel à la fonction créée. On peut voir cette technique comme l'exact inverse de l'inlining.

Autant vous dire que décider quand inliner ou utiliser l'abstraction de procédure est généralement un véritable casse-tête. Généralement, les compilateurs disposent de paramètres de compilation pour spécifier s'il faut optimiser pour la taille du code ou pour la vitesse : l'abstraction de procédure est utilisée quand on choisit l'option taille du code, alors que l'inlining est utilisé quand on choisit l'option vitesse.

La suppression de code mort

Un compilateur peut aussi détecter les morceaux de code qui ne seront jamais exécutés. Par exemple, il est capable de remarquer que le code d'un else ou d'un if dont la condition est constante ne sera jamais exécuté et peut alors supprimer ce code. Cela permet de gagner de la place assez facilement, surtout quand la propagation de constante fait son petit effet. De même, le code situé après une boucle infinie (en C ou Java : while(true){...} ou for(;;){...}) ne contenant aucune instruction d'interruption (break;) ne sera jamais exécuté et peut donc être supprimé.

GFDL

Vous avez la permission de copier, distribuer et/ou modifier ce document selon les termes de la licence de documentation libre GNU, version 1.2 ou plus récente publiée par la Free Software Foundation ; sans sections inaltérables, sans texte de première page de couverture et sans texte de dernière page de couverture.