I kompilatorteorin är eliminering av död kod ( DCE ) en optimering som tar bort död kod . Död kod (även värdelös kod ) är en kod vars exekvering inte påverkar programmets utdata , alla resultat av beräkningen av en sådan kod är döda variabler , det vill säga variabler vars värden inte används senare i program [1] [2] .
I samband med den befintliga oklarheten i termen död kod [3] [4] är det viktigt att notera att optimering av borttagning av död kod inte handlar om borttagning av oåtkomlig kod . Lokalisering och borttagning av oåtkomlig kod kan hanteras av sopsamlaren [5] eller andra optimeringar, såsom borttagning av oåtkomlig kod [2] .
Att ta bort värdelös kod kan påskynda programmet genom att minska antalet operationer som utförs i det och minska storleken på programmet eller mellanliggande representation .
Tänk på följande C -kod :
int foo ( void ) { int a = 24 ; int b ; b = a + 3 ; /* onödig kod */ returnera en << 2 ; }I det här exemplet är additionsoperationen b = a + 3död kod, eftersom variabeln binte används i ytterligare beräkningar och är död från denna punkt till slutet av proceduren. Efter att ha tagit bort den här instruktionen får vi:
int foo ( void ) { int a = 24 ; int b ; /* Död variabel */ returnera en << 2 ; }Efter att ha tagit bort additionsoperationen blir variabeln bdöd under hela proceduren. Eftersom det deklareras lokalt kan det tas bort helt från programmet:
int foo ( void ) { int a = 24 ; returnera en << 2 ; }Även om utvärderingen sker inuti en funktion, skrivs dess resultat till en variabel som endast ligger inom den funktionen; och med tanke på att funktionen ovillkorligen returnerar talet 96, kan den förenklas genom att optimera konstant utbredning så att dess kropp endast består av operationen return 96. Och sedan kan kompilatorn ersätta alla anrop till den funktionen med returvärdet.
Den klassiska DCE ( "Dead" )-algoritmen fungerar på SSA-representationen och består av två förbikopplingar: den första förbikopplingen ( "Mark" ) markerar (markerar) alla uppenbarligen aktiva operationer (exitoperationer för procedurer, input-outputoperationer som ändrar globala variabler) ; det andra svepet ( "Sweep" ) börjar med liveoperationer och går upp argumentdefinitionerna, markerar alla operationer i dess väg som live, slutar med de operationer som inte har några föregångare i SSA-form [6] . Den maximala beräkningskomplexiteten för en sådan algoritm beror på storleken på programmet som O(n 2 ) [7] .
DCE kanske inte utför någon oberoende analys, utan använder helt enkelt resultaten av analysen av aktiva variabler [8] , men beräkningskomplexiteten för en sådan analys är O(n 3 ) i värsta fall [7] . Det finns specifika algoritmer som handlar om att ta bort tomma noder i en CFG-graf , kombinera flera grundläggande block till ett, etc. För en sådan analys behövs en inbyggd kontrollflödesgraf [9] .
Algoritmen "Döda" publicerades först i artikeln "Static Single Assignment Form and the Program Dependence Graph" i ACM TOPLAS 1991 [10] . Algoritmen "Clean " som fungerar med en CFG-graf utvecklades och implementerades av Rob Schiller 1992 [11] .
Borttagning av död kod kan tillämpas flera gånger under kompileringsprocessen, eftersom död kod finns i programmet inte bara för att den finns i källkoden - vissa andra transformationer kan göra koden död. Till exempel förvandlar kopieringsförökningsoptimeringar och konstantförökningsoptimeringar ofta instruktioner till värdelös kod [1] [12] . Du måste också ta bort död kod skapad av andra transformationer i kompilatorn [12] . Till exempel ersätter den klassiska algoritmen för att minska styrkan på en operation arbetsintensiva operationer med mindre arbetsintensiva, varefter borttagningen av den döda koden eliminerar de gamla operationerna och fullbordar transformationen (utan att komplicera algoritmen för att minska styrkan ) [13] .