Recherche de sous-expressions communes
From Wikipedia, the free encyclopedia
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.
Principe
La possibilité d'effectuer une telle optimisation s'appuie sur une analyse des expressions disponibles (une analyse de flux de données). Une expression b*c est disponible à un point p d'un programme si :
- chaque chemin depuis un nœud initial vers p évalue
b*cavant d'atteindre p ; - il n'y a pas d'affectation de nouvelle valeur dans
boucaprè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.
