Holt kód megszüntetése

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ákSzerkeszté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álozó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 holtkód megszüntetés A holtkódot feltétel nélkül halottnak tekintik. Ezért ésszerű megkísérelni a holt kód eltávolítását a holt kód 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.

Lásd mégSzerkesztés

ReferenciákSzerkesztés

  1. Reduction of Operator Strength, Program Flow Analysis: Theory & Application. Prentice-Hall (1981. június 1.). ISBN 0-13729681-9 
  2. A Survey of Data-flow Analysis Techniques, Program Flow Analysis: Theory & Application. Prentice-Hall (1981. június 1.). ISBN 0-13729681-9 
  3. Efficiently Computing Static Single Assignment Form and the Program Dependence Graph. ACM TOPLAS 13(4) (1991. november 16.) 
  4. Engineering a Compiler. Morgan Kaufmann, 498ff. o. (2003. november 16.). ISBN 978-1-55860698-2 
  5. 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 (will also save the memory for the corresponding code excerpts due to our Dynamic Dead Code Elimination), or it can be disabled or enabled at any later time via API functions in case someone wants to keep a user from being able to reboot the machine. […] we are considering to add more synchronous cache flush calls […] Due to our Dynamic Dead Code Elimination method this would not cause any kind of bloating when not needed in a particular target configuration as a particular cache flush call would be included in FreeKEYB's runtime image only if the corresponding disk cache is loaded as well or FreeKEYB was told by command line switches to load the corresponding support.”
  6. 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 depending on the type of machine it is being loaded on, the type of keyboard, layout, country and code page used, the type of mouse and video adapter(s) installed, the other drivers loaded on that system, the operating system and the load and relocation method(s) used, the individual features included, and the configuration options specified in the command line. Due to the large number of command line switches and options supported […] (around fifty switches […] with multiple possible settings) there is a high number of feature combinations with uncountable dependencies […] resulting in […] endless number of […] different target images. FreeKEYB's Dynamic Dead Code Elimination technique manages to resolve […] these […] dependencies and […] remove dead code and data […] is not restricted to […] include or exclude a somewhat limited number of modules or whole sub-routines and fix up some dispatch tables as in classical TSR programming, but […] works […] at […] byte level […] able to remove […] individual instructions in the middle of larger routines […] distributed all over the code to handle a particular case or support a specific feature […] special tools are used to analyze the code […] and create […] fixup tables […] automated […] using conditional defines […] to declare the various cases […] not only optional at assembly time but at initialization time […] without the […] overhead of having at least some amount of dead code left in the runtime image […] to keep track of all the dependencies between […] these conditionals, dynamically build and relocate the runtime image, fix up all the references between these small, changing, and moving binary parts […] still allowing to use the tiny .COM/.SYS style […] model […] is done at initialization time […] API to import and export object structures between FreeKEYB and the calling application […] to transparently resize and move them internally […] at runtime […]”
  7. a b FreeKEYB - Enhanced DOS keyboard and console driver (v6.5 ed.), 1997-10-13 [1] (NB. FreeKEYB is a Unicode-based dynamically configurable successor of K3PLUS supporting most keyboard layouts, code pages, and country codes. Utilizing an off-the-shelf macro assembler as well as a framework of automatic pre- and post-processing analysis tools to generate dependency and code morphing meta data to be embedded into the executable file alongside the binary code and a self-discarding, relaxing and relocating loader, the driver implements byte-level granular dynamic dead code elimination and relocation techniques at load-time as well as self-modifying code and reconfigurability at run-time to minimize its memory footprint downto close the canonical form depending on the underlying hardware, operating system, and driver configuration as well as the selected feature set and locale (about sixty configuration switches with hundreds of options for an almost unlimited number of possible combinations). This complexity and the dynamics are hidden from users, who deal with a single executable file just like they would do with a conventional driver. K3PLUS was an extended keyboard driver for DOS widely distributed in Germany at its time, with adaptations to a handful of other European languages available. It supported a sub-set of features already, but did not implement dynamic dead code elimination.)
  8. 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 die jeweils notwendigen Bestandteile des Treibers erst zum Installationszeitpunkt zusammenbastelt und reloziert, so daß keine ungenutzten Code- oder Datenbereiche mehr resident bleiben (z.B. wenn jemand ein bestimmtes FreeKEYB-Feature nicht benötigt). […]” (NB. This represents the first known implementation of byte-level granular dynamic dead code elimination for software assembled or compiled ahead-of-time.)
  9. [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 you can at installation time […] specify which components of the driver you want and which you don't. This goes to an extent of dynamic loadable modularization and late linkage I have not seen under DOS so far. If you do not like the screen saver, macros, the calculator, or mouse support, or <almost anything else>, you can specify this at the command line, and FreeKEYB, while taking all the dependencies between the routines into account, will completely remove all the code fragments, which deal with that feature and are not necessary to provide the requested functionality, before the driver relocates the image into the target location and makes itself resident. Removing some smaller features just saves a couple of bytes but excluding more complex components can save you half a Kb and more. You can also specify the size of the data areas […]”
  10. (2001. december 30.). „KEYBOARD.SYS internal structure”. comp.os.msdos.programmer. (Web link). „[…] the loader will dynamically optimize the resident data areas and code sections at byte level to remove any redundancy from the driver depending on the given hardware/software/driver configuration and locale. […]”
  11. a b FreeKEYB - Advanced international DOS keyboard and console driver (v7 preliminary ed.), 2006-01-16
  12. (2002. február 2.). „Treiber dynamisch nachladen (Intra-Segment-Offset-Relokation zum Laden von TSRs in die HMA)”. de.comp.os.msdos. (Web link).
  13. (2002. február 24.). „GEOS/NDO info for RBIL62?”. comp.os.geos.programmer. (Web link). „[…] Since FreeKEYB uses our dynamic dead-code-elimination to optimize its memory image for the target environment at load time, I would certainly like to add special support into FreeKEYB for GEOS which could be controlled by a command line option, so the extra code is only loaded when GEOS is used as well. […]”
  14. (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, would it prove to improve the usability under GEOS […] Due to our sophisticated new Dynamic Dead Code Elimination technology which removes at byte level any code snippets unused in a particular given driver, user, or system configuration and hardware environment when the driver's installer builds and relocates the load image of itself, this would have no memory impact for non-GEOS users at all, so there's not much to worry about (memory footprint etc.) as in traditionally coded DOS drivers. […]”
  15. 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
  16. Dynamic dead code elimination and hardware futures, 2011. március 2.[halott link] [4] [5]
  17. a b (1995. december 4.). „Cyclic data structures”. comp.lang.functional. (Web link). „[…] Lazy evaluation is basically dynamic dead code elimination. […]” (NB. Possibly the first public use of the term dynamic dead code elimination, though only conceptually and with a focus on lazy evaluation in functional languages.)
  18. 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.)
  19. 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]
  20. 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ókSzerkesztés

Létező linkekSzerkesztés

FordításSzerkeszté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 jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.