V teorii kompilátoru je eliminace mrtvého kódu ( DCE ) optimalizací , která odstraňuje mrtvý kód . Mrtvý kód (také zbytečný kód ) je kód, jehož provádění neovlivňuje výstup programu, všechny výsledky výpočtu takového kódu jsou mrtvé proměnné , tedy proměnné, jejichž hodnoty se později v program [1] [2] .
V souvislosti se stávající nejednoznačností pojmu mrtvý kód [3] [4] je důležité poznamenat, že optimalizace odstraňování mrtvého kódu se nezabývá odstraňováním nedostupného kódu . Lokalizaci a odstranění nedostupného kódu může řešit garbage collector [5] nebo jiné optimalizace, jako je odstranění nedostupného kódu [2] .
Odstranění zbytečného kódu může urychlit program snížením počtu operací v něm prováděných a zmenšením velikosti programu nebo přechodné reprezentace .
Zvažte následující kód C :
int foo ( void ) { int a = 24 ; int b ; b = a + 3 ; /* Zbytečný kód */ vrátit << 2 ; _ }V tomto příkladu je operace sčítání b = a + 3mrtvý kód, protože proměnná bse nepoužívá v dalších výpočtech a je mrtvá od tohoto bodu až do konce procedury. Po odstranění této instrukce dostaneme:
int foo ( void ) { int a = 24 ; int b ; /* Mrtvá proměnná */ vrátit << 2 ; _ }Po odstranění operace sčítání se proměnná bv celém postupu stane mrtvou. Protože je deklarován lokálně , lze jej z programu zcela odstranit:
int foo ( void ) { int a = 24 ; vrátit << 2 ; _ }I když vyhodnocení probíhá uvnitř funkce, její výsledek je zapsán do proměnné, která je pouze v rozsahu této funkce; a vzhledem k tomu, že funkce bezpodmínečně vrací číslo 96, lze ji zjednodušit optimalizací konstantního šíření tak, aby její tělo sestávalo pouze z operace return 96. A pak kompilátor může nahradit všechna volání této funkce návratovou hodnotou.
Klasický algoritmus DCE ( "Dead" ) pracuje na reprezentaci SSA a skládá se ze dvou obchvatů: první bypass ( "Mark" ) označuje (označuje) všechny zjevně živé operace (operace ukončení procedury, vstupně-výstupní operace, které mění globální proměnné) ; druhé rozmítání ( "Sweep" ) začíná živými operacemi a pokračuje v definicích argumentů, přičemž všechny operace na své cestě označuje jako živé a končí těmi operacemi, které nemají žádné předchůdce ve formě SSA [6] . Maximální výpočetní složitost takového algoritmu závisí na velikosti programu jako O(n 2 ) [7] .
DCE nemusí provádět žádnou nezávislou analýzu, ale jednoduše použít výsledky analýzy aktivních proměnných [8] , ale výpočetní náročnost takové analýzy je v nejhorším případě O(n 3 ) [7] . Existují specifické algoritmy, které se zabývají odstraňováním prázdných uzlů v CFG grafu , kombinováním několika základních bloků do jednoho atd. Pro takovou analýzu je potřeba sestavit graf řídicích toků [9] .
Algoritmus "Dead" byl poprvé publikován v článku "Static Single Assignment Form and the Program Dependence Graph" v ACM TOPLAS v roce 1991 [10] . Algoritmus „ Clean “, který pracuje s CFG grafem, vyvinul a implementoval Rob Schiller v roce 1992 [11] .
Odstranění mrtvého kódu lze během procesu kompilace použít vícekrát, protože mrtvý kód je v programu nejen proto, že je obsažen ve zdrojovém kódu – některé další transformace mohou způsobit, že je kód mrtvý. Například optimalizace šíření kopírování a optimalizace konstantního šíření často mění instrukce v zbytečný kód [1] [12] . Musíte také odstranit mrtvý kód vytvořený jinými transformacemi v kompilátoru [12] . Například klasický algoritmus pro snížení síly operace nahradí pracné operace méně pracnými, po kterých odstranění mrtvého kódu odstraní staré operace a dokončí transformaci (aniž by se komplikoval algoritmus pro snížení síly ) [13] .