Déplacement des invariants de boucle

En programmation informatique, les invariants de boucle sont des instructions^{[réf. nécessaire]} ou des expressions d'un langage de programmation impératif qui peuvent être déplacées hors du corps de la boucle sans affecter le résultat du programme. Le déplacement des invariants de boucle est une optimisation assurée par le compilateur qui effectue automatiquement ce déplacement.

Exemple

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

Détection du code invariant

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.

Avantages et inconvénients de la méthode

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

Bibliographie

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

Voir également

• Optimisation de boucle