Recherche de sous-expressions communes

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.

Exemple

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*c 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.

Intérêt de la technique

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. En fait, la source principale d'optimisation par recherche de sous-expressions communes réside dans les séquences de code intermédiaire produites par le compilateur, comme lors d'opérations d'indexation de tableaux, où il n'est pas possible aux développeurs d'intervenir explicitement. Dans certains cas, des fonctionnalités du langage source peuvent créer de nombreuses expressions redondantes. Par exemple, en langage C, l'expansion des macros peut provoquer l'apparition de sous-expressions communes qui n'étaient pas évidentes dans le code source d'origine.

Les compilateurs doivent faire des choix judicieux concernant le nombre de valeurs temporaires créées pour stocker des valeurs. Un nombre excessif provoque une pénurie de registres qui conduit à vider les registres en mémoire vive, ce qui peut être plus long que de simplement recalculer un résultat arithmétique lorsque c'est nécessaire.

Références

• Steven S. Muchnick, Advanced Compiler Design and Implementation (Morgan Kaufmann, 1997) pp. 378-396
• John Cocke, "Global Common Subexpression Elimination." Proceedings of a Symposium on Compiler Construction, ACM SIGPLAN Notices 5(7), July 1970, pages 850-856.
• Briggs, Preston, Cooper, Keith D., and Simpson, L. Taylor. "Value Numbering." Software-Practice and Experience, 27(6), June 1997, pages 701-724.

Voir aussi

• Static single assignment form, une représentation intermédiaire du code source rendant plus facile l'identification de sous-expressions communes.