Optimisation des compilateurs/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.