Élimination des sous-expressions courantes

Dans la théorie du compilateur , l'élimination des sous-expressions communes ( CSE ) est une optimisation du compilateur qui recherche des instances d' expressions identiques (c'est-à-dire qu'elles sont toutes évaluées à la même valeur) et analyse s'il vaut la peine de les remplacer par une seule variable contenant la valeur calculée.

Dans le code suivant :

a = b * c + g; d = b * c * e; 

il peut être utile de transformer le code en :

tmp = b * c; a = temps + g; d = tmp * e; 

si le coût de stockage et de récupération tmpest inférieur au coût de calcul b * cd'un temps supplémentaire.

La possibilité d'effectuer une CSE repose sur l'analyse des expressions disponibles (une analyse de flux de données ). Une expression b*cest disponible en un point p d'un programme si :

• chaque chemin du nœud initial à p est évalué b*cavant d'atteindre p ,
• et il n'y a pas de devoirs à faire avant bou caprès l'évaluation mais avant p .

L'analyse coûts/bénéfices effectuée par un optimiseur calculera si le coût du stockage tmpest inférieur au coût de la multiplication ; en pratique, d'autres facteurs tels que les valeurs conservées dans les registres sont également importants.

Les auteurs de compilateurs distinguent deux types de CSE :

• l'élimination des sous-expressions communes locales fonctionne dans un seul bloc de base
• l'élimination des sous-expressions communes globales fonctionne sur une procédure entière,

Les deux types s'appuient sur une analyse du flux de données pour déterminer quelles expressions sont disponibles à quels moments d'un programme.

Les avantages de l’exécution de l’optimisation CSE sont suffisamment importants pour qu’il s’agisse d’une optimisation couramment utilisée.

Dans des cas simples comme dans l'exemple ci-dessus, les programmeurs peuvent éliminer manuellement les expressions en double lors de l'écriture du code. La principale source d'expressions en double est constituée par les séquences de code intermédiaires générées par le compilateur, comme pour les calculs d'indexation de tableau , où il n'est pas possible pour le développeur d'intervenir manuellement. Dans certains cas, les fonctionnalités du langage peuvent créer de nombreuses expressions en double. Par exemple, les macros C , où les extensions de macros peuvent entraîner des sous-expressions communes non apparentes dans le code source d'origine.

Les compilateurs doivent être judicieux quant au nombre de valeurs temporaires créées pour contenir des valeurs. Un nombre excessif de valeurs temporaires crée une pression sur les registres, ce qui peut entraîner un débordement des registres vers la mémoire, ce qui peut prendre plus de temps que le simple recalcul d'un résultat arithmétique lorsque cela est nécessaire.