Dode code eliminatie - Dead code elimination

In compiler theorie , dode code eliminatie (ook bekend als DCE , dode code verwijderen , dode code strippen of dode codestrip ) een compileroptimalisatieruimte code die geen invloed op het programma resultaten te verwijderen. Het verwijderen van dergelijke code heeft verschillende voordelen: het verkleint de programmagrootte, een belangrijke overweging in sommige contexten, en het stelt het draaiende programma in staat om het uitvoeren van irrelevante bewerkingen te vermijden, wat de looptijd verkort. Het kan ook verdere optimalisaties mogelijk maken door de programmastructuur te vereenvoudigen. Dode code omvat code die nooit kan worden uitgevoerd ( onbereikbare code ), en code die alleen dode variabelen beïnvloedt (geschreven naar, maar nooit meer gelezen), dat wil zeggen niet relevant voor het programma.

Voorbeelden

Beschouw het volgende voorbeeld geschreven in 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;
 }

Een eenvoudige analyse van het gebruik van waarden zou aantonen dat de waarde van bna de eerste toewijzing niet binnen wordt gebruikt foo. Verder bwordt gedeclareerd als een lokale variabele inside foo, dus de waarde ervan kan niet outside worden gebruikt foo. De variabele bis dus dood en een optimizer kan zijn opslagruimte terugwinnen en zijn initialisatie elimineren.

Bovendien, omdat de eerste return-instructie onvoorwaardelijk wordt uitgevoerd, bereikt geen haalbaar uitvoeringspad de tweede toewijzing aan b. De opdracht is dus onbereikbaar en kan worden verwijderd. Als de procedure een complexere controlestroom had , zoals een label na de return-instructie en een gotoelders in de procedure, dan zou er een haalbaar uitvoeringspad kunnen bestaan ​​naar de toewijzing aan b.

Ook al worden sommige berekeningen in de functie uitgevoerd, hun waarden worden niet opgeslagen op locaties die toegankelijk zijn buiten het bereik van deze functie. Bovendien, gezien de functie een statische waarde retourneert (96), kan deze worden vereenvoudigd tot de waarde die wordt geretourneerd (deze vereenvoudiging wordt constant vouwen genoemd ).

De meeste geavanceerde compilers hebben opties om de verwijdering van dode code te activeren, soms op verschillende niveaus. Een lager niveau verwijdert mogelijk alleen instructies die niet kunnen worden uitgevoerd. Een hoger niveau reserveert mogelijk ook geen ruimte voor ongebruikte variabelen. Een nog hoger niveau kan instructies of functies bepalen die geen enkel doel dienen en deze elimineren.

Een algemeen gebruik van dode code-eliminatie is als alternatief voor optionele code-opname via een preprocessor . Beschouw de volgende code. 

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

Omdat de uitdrukking 0 altijd naar false evalueert , kan de code in de if-instructie nooit worden uitgevoerd, en het verwijderen van dode code zou deze volledig uit het geoptimaliseerde programma verwijderen. Deze techniek is gebruikelijk bij het debuggen om optioneel codeblokken te activeren; het gebruik van een optimalisatieprogramma met eliminatie van dode code elimineert de noodzaak om een preprocessor te gebruiken om dezelfde taak uit te voeren.

In de praktijk wordt veel van de dode code die een optimizer vindt, gemaakt door andere transformaties in de optimizer. De klassieke technieken voor het verminderen van de sterkte van de operator voegen bijvoorbeeld nieuwe berekeningen in de code in en maken de oudere, duurdere berekeningen dood. Daaropvolgende eliminatie van dode code verwijdert die berekeningen en voltooit het effect (zonder het algoritme voor sterktevermindering te compliceren).

Historisch gezien werd de eliminatie van dode code uitgevoerd met behulp van informatie die was afgeleid van gegevensstroomanalyse . Een algoritme op basis van een statisch enkelvoudig opdrachtformulier (SSA) verschijnt in het originele tijdschriftartikel over SSA- formulier door Ron Cytron et al. Robert Shillingsburg (ook bekend als Shillner) verbeterde het algoritme en ontwikkelde een begeleidend algoritme voor het verwijderen van nutteloze controlestroombewerkingen.

Dynamische eliminatie van dode code

Dode code wordt normaal gesproken als onvoorwaardelijk als dood beschouwd . Daarom is het redelijk om te proberen om dode code te verwijderen door dode code te verwijderen tijdens het compileren .

In de praktijk is het echter ook gebruikelijk dat codesecties alleen dode of onbereikbare code vertegenwoordigen onder bepaalde voorwaarden , die mogelijk niet bekend zijn op het moment van compilatie of assemblage. Dergelijke voorwaarden kunnen worden opgelegd door verschillende runtime-omgevingen (bijvoorbeeld verschillende versies van een besturingssysteem, of verschillende sets en combinaties van stuurprogramma's of services die in een bepaalde doelomgeving zijn geladen), waarvoor mogelijk verschillende sets speciale gevallen in de code nodig zijn, maar tegelijkertijd wordt voorwaardelijk dode code voor de andere gevallen. Ook kan de software (bijvoorbeeld een stuurprogramma of een residente service) configureerbaar zijn om bepaalde functies op te nemen of uit te sluiten, afhankelijk van gebruikersvoorkeuren, waardoor ongebruikte codegedeelten onbruikbaar worden in een bepaald scenario. Hoewel modulaire software kan worden ontwikkeld om bibliotheken alleen op verzoek dynamisch te laden, is het in de meeste gevallen niet mogelijk om alleen de relevante routines uit een bepaalde bibliotheek te laden, en zelfs als dit zou worden ondersteund, kan een routine nog steeds codesecties bevatten die kunnen kan in een bepaald scenario als dode code worden beschouwd, maar kon al tijdens het compileren niet worden uitgesloten.

De technieken gebruikt voor het dynamisch vraag detectie, identificatie en lossen afhankelijkheden, verwijderen dergelijke voorwaardelijk dode code en de resterende code recombineren bij belasting of runtime genoemd dynamische dode code verwijdering of dynamische dode instructie eliminatie .

De meeste programmeertalen, compilers en besturingssystemen bieden niet of weinig meer ondersteuning dan het dynamisch laden van bibliotheken en laat koppelen , daarom is software die dynamische eliminatie van dode code gebruikt, zeer zeldzaam in combinatie met talen die van tevoren zijn gecompileerd of in assembler zijn geschreven . Taalimplementaties die just-in-time-compilatie uitvoeren, kunnen echter dynamisch optimaliseren voor het elimineren van dode code.

Hoewel met een nogal andere focus, worden vergelijkbare benaderingen soms ook gebruikt voor dynamische software-updates en hot patching .

Zie ook

Referenties

Verder lezen

Externe links