Kääntäjäteoriassa kuolleen koodin eliminointi ( DCE ) on optimointi , joka poistaa kuolleen koodin . Kuollut koodi (myös hyödytön koodi ) on koodi, jonka suoritus ei vaikuta ohjelman ulostuloon , kaikki tällaisen koodin laskennan tulokset ovat kuolleita muuttujia eli muuttujia, joiden arvoja ei käytetä myöhemmin ohjelma [1] [2] .
Käsitteen kuollut koodi [3] [4] olemassa olevan epäselvyyden yhteydessä on tärkeää huomata, että kuolleen koodin poiston optimointi ei käsittele tavoittamattoman koodin poistamista . Tavoittelemattoman koodin lokalisointi ja poistaminen voidaan hoitaa roskakeräimellä [5] tai muilla optimoinnilla, kuten tavoittamattoman koodin poistaminen [2] .
Turhan koodin poistaminen voi nopeuttaa ohjelmaa vähentämällä siinä suoritettavien toimintojen määrää ja pienentämällä ohjelman tai väliesityksen kokoa .
Harkitse seuraavaa C -koodia :
int foo ( tyhjä ) { int a = 24 ; int b ; b = a + 3 ; /* Käyttämätön koodi */ palauta << 2 ; _ }Tässä esimerkissä summausoperaatio b = a + 3on kuollut koodi, koska muuttujaa bei käytetä myöhemmissä laskelmissa ja se on kuollut tästä pisteestä toimenpiteen loppuun asti. Tämän ohjeen poistamisen jälkeen saamme:
int foo ( tyhjä ) { int a = 24 ; int b ; /* Kuollut muuttuja */ palauta << 2 ; _ }Kun summausoperaatio on poistettu, muuttuja bkuolee koko toimenpiteen aikana. Koska se on ilmoitettu paikallisesti , se voidaan poistaa kokonaan ohjelmasta:
int foo ( tyhjä ) { int a = 24 ; palauta << 2 ; _ }Vaikka arviointi tapahtuu funktion sisällä, sen tulos kirjoitetaan muuttujaan, joka on vain kyseisen funktion piirissä ; ja koska funktio palauttaa ehdoitta luvun 96, sitä voidaan yksinkertaistaa optimoimalla jatkuva eteneminen siten, että sen runko koostuu vain operaatiosta return 96. Ja sitten kääntäjä voi korvata kaikki kyseisen funktion kutsut palautusarvolla.
Klassinen DCE ( "Dead" ) -algoritmi toimii SSA-esityksen kanssa ja koostuu kahdesta ohituksesta: ensimmäinen ohitus ( "Mark" ) merkitsee (merkitsee) kaikki ilmeisesti elävät toiminnot (menettelyn lopetustoiminnot, globaaleja muuttujia muuttavat syöttö-lähtöoperaatiot) ; toinen pyyhkäisy ( "Sweep" ) alkaa live-operaatioilla ja nostaa argumenttimäärityksiä ja merkitsee kaikki polullaan olevat toiminnot suoriksi, päättyen operaatioihin, joilla ei ole edeltäjiä SSA-muodossa [6] . Tällaisen algoritmin suurin laskennallinen monimutkaisuus riippuu ohjelman koosta O(n 2 ) [7] .
DCE ei välttämättä suorita mitään itsenäistä analyysiä, vaan käyttää vain aktiivisten muuttujien analyysin tuloksia [8] , mutta tällaisen analyysin laskennallinen monimutkaisuus on O(n 3 ) pahimmassa tapauksessa [7] . On olemassa erityisiä algoritmeja, jotka käsittelevät tyhjien solmujen poistamista CFG-graafista , useiden peruslohkojen yhdistämistä yhdeksi jne. Tällaista analyysiä varten tarvitaan rakennettu ohjausvuokaavio [9] .
"Dead" -algoritmi julkaistiin ensimmäisen kerran artikkelissa "Static Single Assignment Form and the Program Dependence Graph" ACM TOPLAS :ssa vuonna 1991 [10] . CFG-graafin kanssa toimivan " Clean " -algoritmin kehitti ja toteutti Rob Schiller vuonna 1992 [11] .
Kuolleen koodin poistoa voidaan käyttää useita kertoja käännösprosessin aikana, koska kuollut koodi on ohjelmassa paitsi siksi, että se sisältyy lähdekoodiin - jotkut muut muunnokset voivat tehdä koodin kuolleeksi. Esimerkiksi kopioinnin etenemisen optimointi ja jatkuvan etenemisen optimointi muuttavat ohjeet usein hyödyttömäksi koodiksi [1] [12] . Sinun on myös poistettava muiden muunnosten luoma kuollut koodi kääntäjästä [12] . Esimerkiksi klassinen algoritmi operaation voimakkuuden vähentämiseksi korvaa työvoimavaltaiset toiminnot vähemmän työvoimavaltaisilla, minkä jälkeen kuolleen koodin poistaminen poistaa vanhat toiminnot ja suorittaa muunnoksen (mutkaisematta lujuuden vähentämisalgoritmia ) [13] .