Entfernung von totem Code

In der Compilertheorie bezeichnet die Entfernung toten Codes ( auch Dead-Code - Eliminierung , Dead-Code-Stripping oder Dead-Code-Strip genannt ) eine Compileroptimierung , die toten Code (Code, der keinen Einfluss auf das Programmergebnis hat) entfernt . Das Entfernen solchen Codes bietet mehrere Vorteile: Es reduziert die Programmgröße (in manchen Kontexten ein wichtiger Faktor), verringert den Ressourcenverbrauch, beispielsweise die Anzahl der zu übertragenden Bytes ^{[ 1 ]} , und ermöglicht es dem laufenden Programm, irrelevante Operationen zu vermeiden , was die Laufzeit verkürzt . Zudem kann es durch die Vereinfachung der Programmstruktur weitere Optimierungen ermöglichen. Toter Code umfasst Code, der niemals ausgeführt werden kann ( unerreichbarer Code ), und Code, der lediglich tote Variablen beeinflusst (in die geschrieben, aber nie wieder gelesen wird), also für das Programm irrelevant ist.

Betrachten Sie das folgende in C geschriebene Beispiel .

int foo ( void ) { int a = 24 ; int b = 25 ; // Zuweisung an tote Variable int c ; c = a * 4 ; return c ; b = 24 ; // Nicht erreichbarer Code return 0 ; }

Eine einfache Analyse der Verwendung der Werte zeigt, dass der Wert bnach der ersten Zuweisung innerhalb von nicht verwendet wird foo. Da bdie Variable innerhalb von als lokale Variable deklariert ist foo, kann ihr Wert außerhalb von nicht verwendet werden foo. Somit bist die Variable überflüssig , und ein Optimierer kann ihren Speicherplatz freigeben und ihre Initialisierung eliminieren.

Da die erste return-Anweisung bedingungslos ausgeführt wird und keine nachfolgende Marke existiert, die mit einem "goto" erreicht werden könnte, ist kein möglicher Ausführungspfad zur zweiten Zuweisung an vorhanden b. Daher ist die Zuweisung unerreichbar und kann entfernt werden. Hätte die Prozedur einen komplexeren Kontrollfluss , beispielsweise eine Marke nach der return-Anweisung und ein "goto" gotoan anderer Stelle in der Prozedur, so könnte ein möglicher Ausführungspfad zur Zuweisung an existieren b.

Obwohl innerhalb der Funktion Berechnungen durchgeführt werden, werden deren Ergebnisse nicht an Stellen gespeichert, auf die außerhalb des Funktionsbereichs zugegriffen werden kann. Da die Funktion zudem einen statischen Wert (96) zurückgibt, kann dieser auf den zurückgegebenen Wert vereinfacht werden (diese Vereinfachung wird als Konstantenfaltung bezeichnet ).

Die meisten modernen Compiler bieten Optionen zur Aktivierung der Dead-Code-Eliminierung, teilweise auf verschiedenen Ebenen. Eine niedrigere Ebene entfernt beispielsweise nur nicht ausführbare Anweisungen. Eine höhere Ebene reserviert möglicherweise auch keinen Speicherplatz für ungenutzte Variablen. Eine noch höhere Ebene identifiziert und entfernt Anweisungen oder Funktionen, die keinen Zweck erfüllen.

Die Eliminierung von totem Code wird häufig als Alternative zur optionalen Codeeinbindung mittels eines Präprozessors eingesetzt . Betrachten Sie den folgenden Code.

// DEBUG_MODE auf false setzen constexpr bool DEBUG_MODE = false ;int main ( void ) { int a = 5 ; int b = 6 ; int c ; c = a * ( b / 2 ); if ( DEBUG_MODE ) { printf ( "%d \n " , c ); } return c ; }

Da die Konstante aufgrund ihrer Definition immer den Wert „ falschDEBUG_MODE “ ergibt , kann der Code innerhalb der if-Anweisung niemals ausgeführt werden, und die Entfernung von totem Code würde ihn vollständig aus dem optimierten Programm entfernen. Diese Technik ist beim Debuggen üblich , um optional Codeblöcke zu aktivieren; die Verwendung eines Optimierers mit Totcode-Eliminierung macht den Einsatz eines Präprozessors für dieselbe Aufgabe überflüssig.

In der Praxis entsteht ein Großteil des vom Optimierer gefundenen toten Codes durch andere Transformationen innerhalb des Optimierers. Beispielsweise fügen die klassischen Verfahren zur Reduzierung der Operatorstärke neue Berechnungen in den Code ein und machen die älteren, aufwändigeren Berechnungen überflüssig. ^{[ 2 ]} Die anschließende Eliminierung des toten Codes entfernt diese Berechnungen und vervollständigt den Effekt (ohne den Algorithmus zur Stärkereduzierung zu verkomplizieren).

Historisch gesehen erfolgte die Eliminierung von totem Code mithilfe von Informationen aus der Datenflussanalyse . ^{[ 3 ]} Ein auf der statischen Einzelzuweisungsform (SSA) basierender Algorithmus findet sich im Original-Zeitschriftenartikel zur SSA -Form von Ron Cytron et al. ^{[ 4 ]} Robert Shillingsburg (auch bekannt als Shillner) verbesserte den Algorithmus und entwickelte einen Begleitalgorithmus zur Entfernung überflüssiger Kontrollflussoperationen. ^{[ 5 ]}

Toter Code wird im Allgemeinen als bedingungslos tot betrachtet. Daher ist es sinnvoll, toten Code durch Dead-Code-Eliminierung zur Kompilierzeit zu entfernen .

In der Praxis ist es jedoch üblich, dass Codeabschnitte nur unter bestimmten Bedingungen toten oder unerreichbaren Code darstellen , die zum Zeitpunkt der Kompilierung oder Assemblierung möglicherweise nicht bekannt sind. Solche Bedingungen können durch unterschiedliche Laufzeitumgebungen bedingt sein (z. B. verschiedene Versionen eines Betriebssystems oder unterschiedliche Mengen und Kombinationen von Treibern oder Diensten, die in einer bestimmten Zielumgebung geladen werden). Dies kann unterschiedliche Sonderfälle im Code erfordern, während der Code in anderen Fällen bedingt tot sein kann. ^{[ 6 ] [ 7 ]} Darüber hinaus kann die Software (z. B. ein Treiber oder ein residenter Dienst) so konfiguriert werden, dass bestimmte Funktionen je nach Benutzerpräferenzen ein- oder ausgeschlossen werden, wodurch ungenutzte Codeabschnitte in einem bestimmten Szenario nutzlos werden. ^{[ 6 ] [ 7 ]} Obwohl modulare Software so entwickelt werden kann, dass Bibliotheken dynamisch nur bei Bedarf geladen werden, ist es in den meisten Fällen nicht möglich, nur die relevanten Routinen aus einer bestimmten Bibliothek zu laden. Selbst wenn dies unterstützt würde, kann eine Routine immer noch Codeabschnitte enthalten, die in einem bestimmten Szenario als toter Code gelten, aber bereits zur Kompilierzeit nicht ausgeschlossen werden konnten.

Die Techniken, die verwendet werden, um den Bedarf dynamisch zu erkennen, Abhängigkeiten zu identifizieren und aufzulösen, solchen bedingt toten Code zu entfernen und den verbleibenden Code beim Laden oder zur Laufzeit neu zu kombinieren, werden als dynamische Totcode-Eliminierung ^{[ 8 ] [ 9 ] [ 10 ]} oder dynamische Totbefehls-Eliminierung ^{[ 11 ]} bezeichnet .

Most programming languages, compilers and operating systems offer no or little more support than dynamic loading of libraries and late linking, therefore software utilizing dynamic dead-code elimination is very rare in conjunction with languages compiled ahead-of-time or written in assembly language.^[12][13][14] However, language implementations doing just-in-time compilation may dynamically optimize for dead-code elimination.^[10][15][16]

Although with a rather different focus, similar approaches are sometimes also utilized for dynamic software updating and hot patching.

• Redundant code
• Simplification (symbolic computation)
• Partial-redundancy elimination
• Conjunction elimination
• Dynamic software updating
• Dynamic coupling (computing)
• Self-relocation
• Software cruft
• Tree shaking
• Post-pass optimization
• Profile-guided optimization
• Superoptimizer
• Function multi-versioning

• Bodík, Rastislav; Gupta, Rajiv (Juni 1997). „Partielle Eliminierung von totem Code mittels Slicing-Transformationen“. Proceedings der ACM SIGPLAN 1997 Konferenz über Programmiersprachenentwurf und -implementierung (PLDI '97) : 682–694 .
• Aho, Alfred Vaino ; Sethi, Ravi ; Ullman, Jeffrey David (1986). Compiler – Prinzipien, Techniken und Werkzeuge . Addison Wesley Publishing Company . ISBN 0-201-10194-7Die
• Muchnick, Steven Stanley (1997). Fortgeschrittener Compilerbau und -implementierung . Morgan Kaufmann Publishers . ISBN 1-55860-320-4Die
• Grüne, Dick ; Bal, Henri Elle ; Jacobs, Ceriel JH; Langendoen, Koen G. (2000). Modernes Compiler-Design . John Wiley & Sons, Inc. ISBN 0-471-97697-0Die
• Kennedy, Ken ; Allen, Randy (2002). „Kapitel 4.4. Datenflussanalyse – Kapitel 4.4.2. Eliminierung von totem Code“. Optimierung von Compilern für moderne Architekturen: Ein abhängigkeitsbasierter Ansatz (Digitaldruck der 1. Auflage, 2011). Academic Press / Morgan Kaufmann Publishers / Elsevier . S.  137 , 145–147 , 167. ISBN 978-1-55860-286-1. LCCN  2001092381 .
• Muth, Robert; Debray, Saumya K.; Watterson, Scott; De Bosschere, Koen (Januar 2001) [1999-11-02]. „alto: ein Link-Time-Optimierer für den Compaq Alpha“. Software: Practice and Experience . 31 (1): 67–101 . CiteSeerX  10.1.1.33.4933 . doi : 10.1002/1097-024X(200101)31:1<67::AID-SPE357>3.0.CO;2-A . S2CID  442062 .[5]

• Wie kann man C/C++-Compiler dazu bringen, schrecklichen Code zu generieren?