Optimisation des compilateurs

Cette optimisation consiste à changer l'ordre des boucles entrelacées. En effet, on pourrait échanger une boucle externe avec une interne. Cette transformation nous permet de vérifier le principe de localité. D'ailleurs, ça 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 le fait 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

Mais cette transformation dépend de la technique du cache utilisée et de la disposition du tableau dans la mémoire utilisée par le compilateur.

C'est la division d'une boucle en plusieurs autres boucles ou bien la suppression de dépendance.

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

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 équivalente 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 transformation est la mise en place de prochaines affectations dans la même itération et cela pour augmenter le taux de « cache hit ».

Par exemple, une procédure dans un programme a besoin d'effacer cent éléments. Pour l'accomplir, il faut appeler cent 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 vingt boucles au lieu de cent. Donc on diminue le nombre d'instructions composées par un test et un « jump » par un facteur cinq. Cependant, quatre nouvelles opérations d'additions sont ajoutées, mais cela peut rester négligeable face aux quatre 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é.

C'est le fait d'enlever une structure conditionnelle de l'intérieur de la boucle et de la mettre à l'extérieur. Ensuite, on duplique la boucle, et on met 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 termes de quantité du code initial. Cette technique est introduite dans le gcc version 3.4.

C'est le remplacement d'une boucle while par un bloc contenant une boucle do…while.

Ce code en C :

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

Est équivalent à :

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

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

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

if i >= 100
goto L2

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

 goto L1
 if i >= 100
 a[i] := 0
 i := i + 1
 goto L1
 if i >= 100
 goto L2
 <<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

 if i >= 100
 goto L2

Pour i=99

 if i < 100
 goto L1
 a[i] := 0
 i := i + 1
 if i < 100
 <<at L2>>

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

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.

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

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

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

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

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

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.