Déplacement des invariants de boucle

Déplacement des invariants de boucle

En programmation informatique, les invariants de boucle sont des instructions ou des expressions d'un langage de programmation impératif qui peut être déplacé 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.

Sommaire

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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Déplacement des invariants de boucle de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Optimisation de boucle — En programmation informatique, les optimisations de boucle sont un ensemble de techniques visant à accélérer l exécution des boucles de programmation. Parmi les nombreuses techniques applicables, on peut citer : la parallélisation de… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Graphe de flot de contrôle — Graphes de flot de contrôle simplifiées[1] En informatique, un graphe de flot de contrôle (abrégé en GFC, control flow graph ou CFG en anglais) est une représentation sous forme de graphe de tous les chemins qui peuv …   Wikipédia en Français

  • SYSTÈMES DYNAMIQUES DIFFÉRENTIABLES — Sans doute née avec le mémoire que Poincaré écrivit en 1881 «sur les courbes définies par des équations différentielles», où l’étude quantitative (analytique) locale des équations différentielles dans le champ complexe est remplacée par leur… …   Encyclopédie Universelle

  • Courbe — En géométrie, le mot courbe, ou ligne courbe désigne certains sous ensembles du plan, de l espace usuels. Par exemple, les droites, les segments, les lignes polygonales et les cercles sont des courbes. La notion générale de courbe se décline en… …   Wikipédia en Français

  • Holonomie — En mathématiques, et plus précisément en géométrie différentielle, l holonomie d une connexion sur une variété différentielle est une mesure de la façon dont le transport parallèle le long de boucles fermées modifie les informations géométriques… …   Wikipédia en Français

  • Pseudovecteur — Une boucle de courant électrique (noir), crée un flux magnétique (bleu). Si on considère le système en miroir dans lequel le vecteur courant I est réfléchi, alors le pseudovecteur densité de flux magnétique B doit être réfléchi et inversé. En… …   Wikipédia en Français

  • MÉTALLOGRAPHIE - Essais physiques — Les principales caractéristiques physiques, en tout cas celles d’usage le plus courant, concernent respectivement la dilatation, la résistivité électrique, la capacité thermique massique, la conductivité thermique, les propriétés magnétiques, le… …   Encyclopédie Universelle

  • Cycle — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Le mot cycle provient du grec «κυκλοσ» (kuklos)qui signifie roue ou cercle. Dans une acception primitive il désigne «un intervalle de temps qui correspond …   Wikipédia en Français

  • CaRMetal — Développeurs Éric Hakenholz, Pierre Marc Mazat, Alain Busser Dernière version 3.7.2 (12 octobre 2011 …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”