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