A fordítóelméletben a holt kód elimináció ( DCE ) egy olyan optimalizálás , amely eltávolítja a holt kódot . Holt kód (egyben haszontalan kód ) olyan kód, amelynek végrehajtása nem befolyásolja a program kimenetét , az ilyen kód kiszámításának minden eredménye holt változó , azaz olyan változó, amelynek értékeit később nem használjuk fel a programban. program [1] [2] .
A holt kód [3] [4] kifejezés meglévő többértelműsége kapcsán fontos megjegyezni, hogy a holt kód eltávolításának optimalizálása nem foglalkozik az elérhetetlen kód eltávolításával . Az elérhetetlen kódok lokalizálása és eltávolítása megoldható a szemétgyűjtővel [5] vagy más optimalizálással, például az elérhetetlen kód eltávolításával [2] .
A haszontalan kód eltávolítása felgyorsíthatja a programot azáltal, hogy csökkenti a benne végrehajtott műveletek számát, és csökkenti a program vagy a köztes reprezentáció méretét .
Vegye figyelembe a következő C kódot :
int foo ( üres ) { int a = 24 ; int b ; b = a + 3 ; /* Haszontalan kód */ return a << 2 ; }Ebben a példában az összeadási művelet b = a + 3holt kód, mivel a változót bnem használjuk fel további számításokban, és ettől a ponttól az eljárás végéig halott. Az utasítás eltávolítása után a következőket kapjuk:
int foo ( üres ) { int a = 24 ; int b ; /* Halott változó */ return a << 2 ; }Az összeadási művelet eltávolítása után a változó ba teljes eljárásban halottá válik. Mivel helyileg van deklarálva , teljesen eltávolítható a programból:
int foo ( üres ) { int a = 24 ; return a << 2 ; }Annak ellenére, hogy a kiértékelés egy függvényen belül történik, az eredmény egy olyan változóba kerül, amely csak az adott függvény hatókörébe tartozik ; és mivel a függvény feltétel nélkül a 96-os számot adja vissza, leegyszerűsíthető az állandó terjedés optimalizálásával úgy, hogy törzse csak a műveletből álljon return 96. Ezután a fordító lecserélheti a függvény összes hívását a visszatérési értékre.
A klasszikus DCE ( "Dead" ) algoritmus az SSA-reprezentáción dolgozik, és két bypassból áll: az első bypass ( "Mark" ) minden nyilvánvalóan élő műveletet (eljáráskilépési műveletek, globális változókat megváltoztató bemeneti-kimeneti műveletek) megjelöl (megjelöl) ; a második sweep ( "Sweep" ) élő műveletekkel kezdődik, és feljebb lép az argumentumdefiníciók között, és az útvonalában lévő összes műveletet élőként jelöli meg, és azokkal a műveletekkel végződik, amelyeknek nincs elődje SSA formában [6] . Egy ilyen algoritmus maximális számítási bonyolultsága a program méretétől függ, mint O(n 2 ) [7] .
A DCE nem végezhet független elemzést, hanem egyszerűen felhasználja az aktív változók elemzésének eredményeit [8] , de egy ilyen elemzés számítási bonyolultsága a legrosszabb esetben O(n 3 ) [7] . Vannak speciális algoritmusok, amelyek az üres csomópontok eltávolításával foglalkoznak egy CFG gráfban , több alapvető blokk egyesítésével stb. Egy ilyen elemzéshez egy beépített vezérlőfolyamat gráfra van szükség [9] .
A "Dead" algoritmust először a "Static Single Assignment Form and the Program Dependence Graph" című cikkben publikálták az ACM TOPLAS -ban 1991-ben [10] . A CFG gráfokkal működő " Clean " algoritmust Rob Schiller fejlesztette ki és implementálta 1992 - ben [ 11 ] .
A holt kód eltávolítása többször is végrehajtható a fordítási folyamat során, mivel a holt kód nem csak azért van a programban, mert a forráskód tartalmazza – bizonyos más átalakítások a kódot holttá tehetik. Például a másolásterjedés optimalizálás és az állandó terjedés optimalizálás gyakran használhatatlan kóddá változtatja az utasításokat [1] [12] . Ezenkívül el kell távolítania a fordító egyéb átalakításai által létrehozott halott kódot [12] . Például egy művelet erősségének csökkentésére szolgáló klasszikus algoritmus a munkaigényes műveleteket kevésbé munkaigényesekre cseréli, ami után a halott kód eltávolítása megszünteti a régi műveleteket és befejezi az átalakítást (anélkül, hogy bonyolítaná az erősség csökkentésére szolgáló algoritmust ) [13] .