Élimination du code mort - Dead code elimination

En théorie du compilateur , l' élimination du code mort (également connu sous le nom DCE , suppression de code mort , code mort stripping ou bande de code mort ) est une optimisation du compilateur pour supprimer le code qui ne concerne pas les résultats du programme. La suppression de ce code présente plusieurs avantages : elle réduit la taille du programme, une considération importante dans certains contextes, et elle permet au programme en cours d'exécution d'éviter d'exécuter des opérations non pertinentes, ce qui réduit son temps d'exécution. Il peut également permettre d'autres optimisations en simplifiant la structure du programme. Le code mort comprend le code qui ne peut jamais être exécuté ( code inaccessible ) et le code qui n'affecte que les variables mortes (écrites, mais jamais relues), c'est-à-dire sans rapport avec le programme.

Exemples

Considérons l'exemple suivant écrit en C . 

 int foo(void)
 {
   int a = 24;
   int b = 25; /* Assignment to dead variable */
   int c;
   c = a * 4;
   return c;
   b = 24; /* Unreachable code */
   return 0;
 }

Une simple analyse des usages des valeurs montrerait que la valeur d' baprès la première affectation n'est pas utilisée à l'intérieur foo. De plus, best déclaré comme variable locale à l'intérieur de foo, donc sa valeur ne peut pas être utilisée à l'extérieur de foo. Ainsi, la variable best morte et un optimiseur peut récupérer son espace de stockage et supprimer son initialisation.

De plus, comme la première instruction return est exécutée sans condition, aucun chemin d'exécution réalisable n'atteint la deuxième affectation à b. Ainsi, l'affectation est inaccessible et peut être supprimée. Si la procédure avait un flux de contrôle plus complexe , tel qu'une étiquette après l'instruction return et un gotoautre endroit dans la procédure, alors un chemin d'exécution réalisable pourrait exister pour l'affectation à b.

De plus, même si certains calculs sont effectués dans la fonction, leurs valeurs ne sont pas stockées dans des emplacements accessibles en dehors de la portée de cette fonction. De plus, étant donné que la fonction renvoie une valeur statique (96), elle peut être simplifiée à la valeur qu'elle renvoie (cette simplification est appelée pliage constant ).

La plupart des compilateurs avancés ont des options pour activer l'élimination du code mort, parfois à des niveaux variables. Un niveau inférieur peut supprimer uniquement les instructions qui ne peuvent pas être exécutées. Un niveau supérieur peut également ne pas réserver d'espace pour les variables inutilisées. Un niveau encore plus élevé pourrait déterminer des instructions ou des fonctions qui ne servent à rien et les éliminer.

Une utilisation courante de l'élimination du code mort est une alternative à l'inclusion de code facultative via un préprocesseur . Considérez le code suivant. 

 int main(void) {
   int a = 5;
   int b = 6;
   int c;
   c = a * (b / 2);
   if (0) {   /* DEBUG */
     printf("%d\n", c);
   }
   return c;
 }

Étant donné que l'expression 0 sera toujours évaluée à false , le code à l'intérieur de l'instruction if ne pourra jamais être exécuté et l'élimination du code mort le supprimera entièrement du programme optimisé. Cette technique est courante dans le débogage pour activer éventuellement des blocs de code ; l'utilisation d'un optimiseur avec élimination du code mort élimine le besoin d'utiliser un préprocesseur pour effectuer la même tâche.

En pratique, une grande partie du code mort qu'un optimiseur trouve est créée par d'autres transformations dans l'optimiseur. Par exemple, les techniques classiques de réduction de la force des opérateurs insèrent de nouveaux calculs dans le code et rendent les calculs plus anciens et plus coûteux morts. L'élimination ultérieure du code mort supprime ces calculs et complète l'effet (sans compliquer l'algorithme de réduction de force).

Historiquement, l'élimination des codes morts était effectuée à l'aide d'informations dérivées de l'analyse des flux de données . Un algorithme basé sur le formulaire d'affectation unique statique (SSA) apparaît dans l'article de revue original sur le formulaire SSA par Ron Cytron et al. Robert Shillingsburg (alias Shillner) a amélioré l'algorithme et développé un algorithme compagnon pour supprimer les opérations de flux de contrôle inutiles.

Élimination dynamique du code mort

Le code mort est normalement considéré comme mort inconditionnellement . Par conséquent, il est raisonnable d'essayer de supprimer le code mort en éliminant le code mort au moment de la compilation .

Cependant, dans la pratique, il est également courant que les sections de code ne représentent du code mort ou inaccessible que sous certaines conditions , qui peuvent ne pas être connues au moment de la compilation ou de l'assemblage. De telles conditions peuvent être imposées par différents environnements d'exécution (par exemple différentes versions d'un système d'exploitation, ou différents ensembles et combinaisons de pilotes ou de services chargés dans un environnement cible particulier), ce qui peut nécessiter différents ensembles de cas spéciaux dans le code, mais à devient en même temps un code mort conditionnellement pour les autres cas. En outre, le logiciel (par exemple, un pilote ou un service résident) peut être configurable pour inclure ou exclure certaines fonctionnalités en fonction des préférences de l'utilisateur, rendant les portions de code inutilisées inutiles dans un scénario particulier. Bien qu'un logiciel modulaire puisse être développé pour charger dynamiquement des bibliothèques à la demande uniquement, dans la plupart des cas, il n'est pas possible de charger uniquement les routines pertinentes d'une bibliothèque particulière, et même si cela était pris en charge, une routine peut toujours inclure des sections de code qui peuvent être considéré comme du code mort dans un scénario donné, mais ne pouvait pas être exclu au moment de la compilation, déjà.

Les techniques utilisées pour détecter dynamiquement la demande, identifier et résoudre les dépendances, supprimer ce code mort conditionnellement et recombiner le code restant au chargement ou à l' exécution sont appelées élimination dynamique du code mort ou élimination dynamique des instructions mortes .

La plupart des langages de programmation, des compilateurs et des systèmes d'exploitation n'offrent pas ou peu plus de support que le chargement dynamique des bibliothèques et la liaison tardive , par conséquent, les logiciels utilisant l'élimination dynamique du code mort sont très rares en conjonction avec des langages compilés à l'avance ou écrits en langage assembleur . Cependant, les implémentations de langage effectuant une compilation juste à temps peuvent optimiser dynamiquement l'élimination du code mort.

Bien qu'avec un objectif assez différent, des approches similaires sont parfois également utilisées pour la mise à jour dynamique des logiciels et l' application de correctifs à chaud .

Voir également

Les références

Lectures complémentaires

Liens externes