Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Recherche de sous-expressions communes
Résumé
En informatique, la recherche de sous-expressions communes est une technique d'optimisation de code qui cherche des instances d'expressions communes (c'est-à-dire renvoyant toutes la même valeur) et qui détermine si cela vaut la peine de les remplacer par une variable unique contenant la valeur calculée.
Dans le code suivant :
a = b * c + g;
d = b * c * d;
il peut être intéressant de transformer le code compilé comme si on avait écrit :
tmp = b * c;
a = tmp + g;
d = tmp * d;
« intéressant » signifie que le programme transformé s'exécutera plus vite que l'original.
La possibilité d'effectuer une telle optimisation s'appuie sur une analyse des expressions disponibles (une analyse de flux de données). Une expression bc est disponible à un point p d'un programme si :
chaque chemin depuis un nœud initial vers p évalue bc avant d'atteindre p ;
il n'y a pas d'affectation de nouvelle valeur dans b ou c après leur évaluation, mais avant p.
L'optimiseur comparera le coût au gain pour savoir si le coût du stockage en mémoire de la valeur tmp est inférieur au coût d'une multiplication ; en pratique, d'autres facteurs, comme le fait de disposer des valeurs dans tel ou tel registre intervient aussi.
Ceux qui écrivent des compilateurs distinguent deux sortes de recherche de sous-expressions communes :
la recherche locale de sous-expressions communes qui fonctionne au sein d'un même bloc de base et qui est donc une optimisation simple à implanter.
la recherche globale de sous-expressions communes qui agit sur l'ensemble d'une procédure.
Les deux sortes s'appuient sur l'analyser le flux de données pour savoir quelles expressions sont disponibles à tel ou tel endroit d'une procédure.
Les avantages de la recherche de sous-expressions communes sont en général suffisants et c'est donc un type courant d'optimisation.
Dans des cas simples comme celui de l'exemple qui précède, les programmeurs peuvent éliminer manuellement les expressions en double lorsqu'ils écrivent leur code.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.