Holt kód megszüntetése
Ezt a szócikket némileg át kellene dolgozni a wiki jelölőnyelv szabályainak figyelembevételével, hogy megfeleljen a Wikipédia alapvető stilisztikai és formai követelményeinek. |
A fordítóprogram-elméletben a holt kód megszüntetése (más néven DCE – dead code elimination, holt kód eltávolítása, holt kód csupaszítása, vagy holt kód tisztítása) egy fordítóprogram optimalizációja, hogy eltávolítsa azokat a kódokat, amik nincsenek hatással a program eredményeire. Eltávolítani ilyen kódot számos előnnyel jár: csökkenti a program méretét, fontos szempont néhány összefüggésben, és megengedi a futó programnak, hogy elkerüljön lényegtelen műveleteket, amik csökkentik a futási időt. Ezáltal elérhetővé válik további optimalizáció a program szerkezetének egyszerűsítésével. Holt kód alatt értünk olyan kódokat, amiket sosem lehet végrehajtani (elérhetetlen kód), és olyan kódokat, amik csak holt változókra hatnak (megírva, de sosem olvasva újra), amik lényegtelenek a programnak.
Példák
[szerkesztés]Tekintsük a következő C-ben írt példát.
int foo(void)
{
int a = 24;
int b = 25; /* Hozzárendelés holt változóhoz */
int c;
c = a * 4;
return c;
b = 24; /* Elérhetetlen kód */
return 0;
}
A változók egyszerű elemzése megmutatja, hogy b
változót az első értékadást követően nem használják foo
függvény belsejében. Továbbiakban b
helyi változóként van deklarálva a foo
függvényben, szóval ezt a változót nem lehet a foo
függvényen kívül használni. Így a b
változó halott, és az optimalizáló visszakövetelheti ennek a változónak a tárhelyét és megszünteti az inicializálását.
Továbbá, mivel az első return utasítást feltétel nélkül hajtják végre, egyetlen megvalósítható út sem éri el a b
-hez tartozó második hozzárendelést. Így a hozzárendelés elérhetetlen és eltávolítható. Ha az eljárásnak bonyolultabb vezérlési folyamata van, például egy címke a return utasítás után és egy goto
az eljárás más részén, akkor megvalósítható végrehajtási útvonal állhat fenn a b
hozzárendeléshez.
Annak ellenére, hogy egyes számításokat a függvényben hajtanak végre, értékeik nem kerülnek tárolásra a függvényen kívül elérhető helyeken. Továbbá, mivel a függvény statikus (96) értéket ad vissza, egyszerűsíthető a visszaadott értékre (ezt az egyszerűsítést állandó hajtogatásnak nevezzük).
A legtöbb fejlett fordítónak lehetősége van aktiválni a holtkód-eltávolítást, néha változó szinten. Alacsonyabb szint csak azokat az utasításokat távolíthatja el, amelyek nem hajthatók végre. Előfordulhat, hogy egy magasabb szint nem foglal helyet a nem használt változók számára. Egy még magasabb szint meghatározhat olyan utasításokat vagy funkciókat, amelyek semmilyen célt nem szolgálnak, és kiküszöböli azokat.
A holt kód megszüntetésének általános használata alternatívája az opcionális kód felvételnek egy előfeldolgozón keresztül. Vegye figyelembe a következő kódot.
int main(void) {
int a = 5;
int b = 6;
int c;
c = a * (b / 2);
if (0) { /* DEBUG */
printf("%d\n", c);
}
return c;
}
Mivel a 0 kifejezés mindig hamisra fog értékelni, az if utasítás belsejében lévő kódot soha nem lehet végrehajtani, és a holt kód megszüntetése teljesen eltávolítja az optimalizált programból. Ez a technika gyakori a hibakeresés során, ha opcionálisan aktiválják a kódblokkokat; Az optimalizáló használata holt kód megszüntetésével feleslegessé teszi az előfeldolgozó használatát ugyanazon feladat végrehajtásához.
A gyakorlatban az optimalizáló által talált holt kód nagy részét az optimalizáló más átalakításai hozzák létre. Például az operátor erősségének csökkentésére szolgáló klasszikus technikák új számításokat illesztenek be a kódba, és a régebbi, drágább számításokat holtakká teszik.[1] későbbi holtkód-eltávolítás eltávolítja ezeket a számításokat, és befejezi a hatást (anélkül, hogy megnehezítené az erő-csökkentő algoritmust).
Történelmileg az elhalt kód eltávolítását az adatfolyam-elemzésből[2] származó információk felhasználásával hajtották végre. A statikus egyszeri hozzárendelési formanyomtatványon (SSA) alapuló algoritmus megjelenik Ron Cytron és munkatársai eredeti SSA formátumú folyóiratcikkében.[3] Robert Shillingsburg (más néven Shillner) továbbfejlesztette az algoritmust, és kifejlesztett egy társalgoritmust a haszontalan vezérlés-áramlás műveletek eltávolítására.[4]
Dinamikus holt kód megszüntetése
[szerkesztés]A holt kódot feltétel nélkül halottnak tekintik. Ezért észszerű megkísérelni eltávolítását annak megszüntetésével a fordítás idején.
A gyakorlatban azonban az is gyakori, hogy a kódrészek csak bizonyos körülmények között képviselik az elhalt vagy elérhetetlen kódokat, amelyek a fordítás vagy összeállítás idején nem ismertek. Ilyen feltételeket különböző futtatókörnyezetek (például egy operációs rendszer különböző verziói, vagy egy adott célkörnyezetbe betöltött illesztőprogramok vagy szolgáltatások különböző készletei és kombinációi) szabhatnak meg, amelyek eltérő kódokat igényelhetnek a kódban, de ugyanakkor a többi esethez feltételesen holt kód lesz.[5][6] Ezenkívül a szoftver (például egy illesztőprogram vagy helyi szolgáltatás) konfigurálható úgy, hogy bizonyos funkciókat tartalmazzon vagy kizárjon a felhasználói preferenciáktól függően, használhatatlanná téve a kódrészeket egy adott forgatókönyv esetén.[5][6] Noha moduláris szoftvereket lehet fejleszteni a könyvtárak dinamikus betöltésére csak igény szerint, a legtöbb esetben nem lehet csak a vonatkozó rutinokat betölteni egy adott könyvtárból, és még ha ez támogatott is lenne, a rutin továbbra is tartalmazhat kódrészleteket, amelyek képesek egy adott forgatókönyvben halott kódnak kell tekinteni, de már összeállításkor sem lehetett kizárni.
A kereslet dinamikus detektálására, a függőségek azonosítására és feloldására, az ilyen feltételesen elhalt kód eltávolítására, valamint a fennmaradó kód újrakombinálására használt technikákat töltéskor vagy futás közben dinamikus holtkód-eliminációnak[5][6][7][8][9][10][11][12][13][14][15][16][17] vagy dinamikus holt utasítás-eliminációnak nevezzük.[18]
A legtöbb programozási nyelv, fordító és operációs rendszer nem, vagy alig nyújt nagyobb támogatást, mint a könyvtárak dinamikus betöltése és a késői összekapcsolás, ezért a dinamikus holtkód-eltávolítást alkalmazó szoftver nagyon ritka az idő előtt összeállított vagy az assembly nyelvekkel[7][11][8] együtt. A futás idejű fordítást végző nyelvi implementációk azonban dinamikusan optimalizálódhatnak a holt kód megszüntetésére.[17][19][20]
Bár meglehetősen eltérő fókusszal, néha hasonló megközelítéseket is alkalmaznak a dinamikus szoftverfrissítéshez és a gyorsjavításhoz.
Jegyzetek
[szerkesztés]- ↑ Reduction of Operator Strength, Program Flow Analysis: Theory & Application. Prentice-Hall (1981. június 1.). ISBN 0-13729681-9
- ↑ A Survey of Data-flow Analysis Techniques, Program Flow Analysis: Theory & Application. Prentice-Hall (1981. június 1.). ISBN 0-13729681-9
- ↑ Efficiently Computing Static Single Assignment Form and the Program Dependence Graph. ACM TOPLAS 13(4) (1991. augusztus 12.)
- ↑ Engineering a Compiler. Morgan Kaufmann, 498ff. o. (2003. augusztus 12.). ISBN 978-1-55860698-2
- ↑ a b c [fd-dev Ctrl+Alt+Del]. freedos-dev, 2002. április 3. [2017. szeptember 9-i dátummal az eredetiből archiválva]. (Hozzáférés: 2017. szeptember 9.) „[…] any of the […] options can be "permanently" excluded at installation time […][…]”
- ↑ a b c [fd-dev Ctrl+Alt+Del]. freedos-dev, 2002. április 6. [2019. április 27-i dátummal az eredetiből archiválva]. (Hozzáférés: 2019. április 27.) „[…] FreeKEYB builds the driver's runtime image at initialization time […][…]”
- ↑ a b FreeKEYB - Enhanced DOS keyboard and console driver (v6.5 ed.), 1997-10-13, [1]
- ↑ a b (2001. április 10.). „[ANN] FreeDOS beta 6 released”. de.comp.os.msdos. (Web link). „[…] brandneue[s] Feature, der dynamischen Dead-Code-Elimination, die ... benötigt). […]”
- ↑ [fd-dev Changing codepages in FreeDOS]. freedos-dev, 2001. augusztus 21. [2019. április 19-i dátummal az eredetiből archiválva]. (Hozzáférés: 2019. április 20.) „[…] a […] unique feature […] we call dynamic dead code elimination, so […]”
- ↑ (2001. december 30.). „KEYBOARD.SYS internal structure”. comp.os.msdos.programmer. (Web link). „[…] the loader will dynamically optimize […]”
- ↑ a b FreeKEYB - Advanced international DOS keyboard and console driver (v7 preliminary ed.), 2006-01-16
- ↑ (2002. február 2.). „Treiber dynamisch nachladen (Intra-Segment-Offset-Relokation zum Laden von TSRs in die HMA)”. de.comp.os.msdos. (Web link).
- ↑ (2002. február 24.). „GEOS/NDO info for RBIL62?”. comp.os.geos.programmer. (Web link). „[…] Since FreeKEYB uses our […] : see there.”
- ↑ (2002. március 15.). „AltGr keyboard layer under GEOS?”. comp.os.geos.misc. (Web link). „[…] I would be willing to add special hooks into FreeKEYB, our much advanced DOS keyboard driver, […] Due to our sophisticated […]”
- ↑ A Just in Time Register Allocation and Code Optimization Framework for Embedded Systems. University of Cincinnati, Engineering: Computer Engineering. ucin982089462 (2001. január 31.), [2] Archiválva 2019. július 28-i dátummal a Wayback Machine-ben, [3] Archiválva 2019. július 28-i dátummal a Wayback Machine-ben
- ↑ Dynamic dead code elimination and hardware futures, 2011. március 2.[halott link] [4] [5]
- ↑ a b (1995. december 4.). „Cyclic data structures”. comp.lang.functional. (Web link). „[…] Lazy evaluation is basically dynamic dead code elimination. […]”
- ↑ Dynamic Dead-Instruction Detection and Elimination. Computer Science Department, University of Wisconsin-Madison, 2002. október 1. [2019. április 20-i dátummal az eredetiből archiválva]. (Hozzáférés: 2017. június 23.)
- ↑ Chapter 5. Java overview and iSeries implementation - 5.1.1. Miscellaneous components, Intentia Movex Java on the IBM iSeries Server - An Implementation Guide - Overview of Movex Java on the iSeries server - Movex Java on iSeries installation and configuration - Operational tips and techniques, Red Books. IBM Corp., 41. o.. SG24-6545-00 (2002. november 8.). ISBN 0-73842461-7, [6]
- ↑ Virtualization Support for Application Runtime Specialization and Extension - Programming Languages pp. 111–124. Universite des Sciences et Technologies de Lille, 2015 [2017. június 23-i dátummal az eredetiből archiválva]. (Hozzáférés: 2017. június 23.)
További információk
[szerkesztés]- (1997. június 1.) „Partial dead code elimination using slicing transformations”. Proceedings of the ACM SIGPLAN 1997 Conference on Programming Language Design and Implementation (PLDI '97), 682–694. o.
- Compilers - Principles, Techniques and Tools. Addison Wesley Publishing Company (1986. augusztus 12.). ISBN 0-201-10194-7
- Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers (1997. augusztus 12.). ISBN 1-55860-320-4
- Modern Compiler Design. John Wiley & Sons, Inc. (2000. augusztus 12.). ISBN 0-471-97697-0
- Chapter 4.4. Data Flow Analysis - Chapter 4.4.2. Dead Code Elimination, Optimizing Compilers for Modern Architectures: A Dependence-Based Approach, 2011 digital print of 1st, Academic Press / Morgan Kaufmann Publishers / Elsevier, 137, 145–147, 167. o. (2002. augusztus 12.). ISBN 978-1-55860-286-1
További információk
[szerkesztés]Fordítás
[szerkesztés]Ez a szócikk részben vagy egészben a Dead code elimination című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.