Déplacement des invariants de boucle

Deux optimisations peuvent être appliquées à l'extrait de code suivant :

for (int i = 0; i < n; i++) {
    x = y + z;
    a[i] = 6 * i + x * x;
}

L'affectation x = y + z et l'expression x * x peuvent être sortis de la boucle, car ce sont des invariants de boucle : ils ne changent pas d'une itération à la suivante. Le code optimisé ressemblera à :

x = y + z;
temp1 = x * x;
for (int i = 0; i < n; i++) {
    a[i] = 6 * i + temp1;
}

Pour déterminer les instructions et les expressions invariantes, on analyse la portion de code sur laquelle une valeur reste inchangée (Reaching definition en anglais).

Par exemple, si tous les opérandes d'une expression sont définis à l'extérieur de la boucle et inchangés depuis, on peut sortir cette expression de la boucle.

Le code qui a été sorti d'une boucle est exécuté moins souvent, ce qui apporte une accélération. Un autre effet de cette transformation est qu'elle permet de placer des constantes dans des registres et il ne faut donc pas calculer l'adresse d'une variable puis accéder à la mémoire à chaque itération.

Néanmoins, si l'on crée trop de variables, on augmente les besoins en allocation de registres, ce qui est encore plus gênant sur les processeurs qui disposent de peu de registres, comme les x86 32 bits. Si le compilateur a épuisé les registres, certaines variables devront être mises en mémoire. Pour pallier ce problème, il faut procéder à l'optimisation « inverse » du déplacement des invariants de boucle, la « rematérialisation ».

• (en) Aho, Alfred V.; Sethi, Ravi; & Ullman, Jeffrey D. (1986). Compilers: Principles, Techniques, and Tools. Addison Wesley. (ISBN 0-201-10088-6).

• Optimisation de boucle