Az optimalizáló fordító egy olyan fordító , amely különféle módszereket használ, hogy optimálisabb programkódot kapjon, miközben megőrzi funkcionalitását. A leggyakoribb optimalizálási célok a következők: a programvégrehajtási idő csökkentése, a teljesítmény növelése, a programkód tömörítése, a memória megtakarítása, az energiaköltségek minimalizálása, az I/O műveletek számának csökkentése .
Az optimalizálás implicit módon megtörténhet a program fordítása során, de általában a fordítói munka külön lépésének tekintik. A linkerek az optimalizálás egy részét is végrehajthatják, például eltávolíthatják a nem használt szubrutinokat vagy átrendezhetik őket .
Az optimalizálás általában optimalizáló transzformációk sorozatán keresztül valósul meg, olyan algoritmusokon keresztül , amelyek egy programot használnak, és módosítják azt, hogy egy szemantikailag egyenértékű változatot hozzanak létre, amely hatékonyabb az optimalizálási célok bizonyos csoportjai számára. Egyes kódoptimalizálási problémákról bebizonyosodott, hogy NP-teljesek [1] , vagy akár eldönthetetlenek [2] . Ennek ellenére gyakorlatilag sok közülük heurisztikus módszerekkel van megoldva, amelyek meglehetősen kielégítő eredményeket adnak.
Tegyen különbséget az alacsony és a magas szintű optimalizálás között. Az alacsony szintű optimalizálás elemi utasítások szintjén alakítja át a programot, például egy adott architektúra processzorának utasításait . A magas szintű optimalizálás a program szerkezeti elemeinek, például modulok, függvények, ágak, ciklusok szintjén történik.
Az optimalizálás során alkalmazott módszerek hatókör szerint osztályozhatók: érinthetnek egyetlen utasítást és egy egész programot is. A lokális (a program egy kis részét érintő) módszerek könnyebben megvalósíthatók, mint a globális módszerek (a teljes programra vonatkoztatva), de a globális módszerek gyakran előnyösebbek.
A lokális kukucskáló optimalizálások több szomszédos ( a programábrázolás egyik grafikonja szempontjából) utasítást figyelembe vesznek (mintha „a kukucskálón keresztül néznénk ” a kódon), hogy megnézzék, lehet-e velük bármilyen transzformációt végrehajtani az optimalizálás szempontjából. cél. Különösen helyettesíthetők egyetlen utasítással vagy egy rövidebb utasítássorozattal.
Például egy szám megkettőzését hatékonyabban lehet elvégezni balra tolással, vagy a szám hozzáadásával.
A lokális optimalizálás során lépésenként csak egy alapblokk információit veszik figyelembe [3] . Mivel az alapblokkban nincsenek vezérlési folyamatátmenetek , ezek az optimalizálások kevés elemzést igényelnek (időt takarítanak meg és csökkentik a memóriaigényt), de ez azt is jelenti, hogy a következő lépéshez nem kerül tárolásra információ.
Az eljáráson belüli optimalizálás ( angolul intraprocedural ) olyan globális optimalizálás, amelyet teljes egészében egy fordítási egység (például függvények vagy eljárások) keretein belül hajtanak végre [4] . Az ilyen optimalizálásnál sokkal több információ jár, mint a lokálisnál, amivel jelentősebb hatások érhetők el, ez azonban sokszor erőforrás-igényes számításokat igényel. Ha az optimalizált programegységben vannak globális változók , az ilyen típusú optimalizálás nehézkes lehet.
Számos optimalizálást alkalmaznak a hurkokra. A ciklus nagy számú iterációjával az ilyen optimalizálás rendkívül hatékony, mivel a program végrehajtásának jelentős részét egy kis átalakítás befolyásolja. Mivel a ciklusok sok program végrehajtási idejének jelentős részét teszik ki, szinte minden fordítóprogramban létezik ciklusoptimalizálás, és ezek a legfontosabbak.
Például a ciklusinvariánsok azonosításával néha lehetséges néhány műveletet eltávolítani a hurokból, hogy ne hajtsanak végre redundáns ismételt számításokat.
Az ilyen típusú optimalizálás a program teljes forráskódját egyszerre elemzi. Az ezekkel a módszerekkel nyert információ nagyobb mennyisége azt jelenti, hogy az optimalizálás hatékonyabb lehet, mint más módszerek. Az ilyen optimalizálás meglehetősen összetett módszereket alkalmazhat, például egy függvényhívást a függvénytörzs másolatával (inline vagy inline) helyettesítünk.
Példa Legyen néhány függvény:
int pred ( int x ) { ha ( x == 0 ) return 0 ; más visszatérés x - 1 ; }A beágyazás előtt a kód így nézett ki:
int f ( int y ) { return pred ( y ) + pred ( 0 ) + pred ( y + 1 ); }Optimalizálás után:
int f ( int y ) { belső hőmérséklet = 0 ; ha ( y == 0 ) hőmérséklet += 0 ; else temp += y - 1 ; /* (egy) */ if ( 0 == 0 ) hőmérséklet += 0 ; különben hőmérséklet += 0 - 1 ; * (2) */ if ( y + 1 == 0 ) hőmérséklet += 0 ; else temp += ( y + 1 ) - 1 ; * (3) */ visszatérő hőmérséklet ; }A függvénybeillesztés kiküszöböli a függvényhívásokhoz kapcsolódó többletköltséget. Ezenkívül a beillesztés után lehetőség van olyan eljáráson belüli optimalizációk alkalmazására, amelyeket korábban lehetetlen vagy túl nehéz volt megvalósítani. A beépítésnek azonban megvannak a maga hátrányai, mint szinte minden optimalizálásnak – növeli a kód statikus méretét, ami negatív hatásokhoz vezethet a berendezés e tényezőre érzékeny részein.
Az optimalizálást befolyásoló tényezők közül a célgép számítási jellemzői (például a processzormagok száma és órajele, a processzor gyorsítótárának mérete, a rendszerbusz sávszélessége , a RAM mennyisége) és a cél architektúrája egyaránt. processzor (különösen, a különböző architektúrákban eltérő számú általános célú regiszter áll rendelkezésre, a számítási folyamat másként valósul meg ). Az optimalizálást befolyásoló tényezők másik csoportja a célkódhasználati forgatókönyv, például az optimalizálási célok jelentősen eltérhetnek a hibakeresési és tesztkód, az alkalmi futtatás, a folyamatos használat, a beágyazott vagy önálló alkalmazások esetében.
A fordítóprogramok különféle optimalizálási módszereiben használt optimalizálási elvek közül (egyesek ellentmondhatnak egymásnak, vagy nem alkalmazhatók különböző optimalizálási célokra):
Az adatfolyam-optimalizálások adatfolyam - elemzésen alapulnak, és általában bemenő adatnak tekintik az egymáshoz kapcsolódó vezérlőfolyam-gráfot és adatfolyam-gráfot, valamint gyakran a vezérlőfolyamat-gráf hurokfáját és hurokcímkéit. Ezeken a grafikonokon különösen az információ terjedését elemezve feltárul az optimalizálás lehetősége a kívánt célok szempontjából, majd az optimalizációkat alkalmazzák.
Gyakori részkifejezések eltávolítása A közös részkifejezések eltávolítása egy olyan fordítóoptimalizálás, amely azonos kifejezések példányait keresi, és elemzi annak lehetőségét, hogy lecseréljék őket egyetlen változóra, amely tartalmazza a számított értéket. Állandók konvolúciója Optimalizálások, amelyek csökkentik a redundáns számításokat azáltal, hogy az állandó kifejezéseket és változókat az értékükre cserélik. Induktív változók elemzése ( eng. Indukciós változók elemzése ) Lásd a leírást a Ciklusoptimalizálás részben . Zsákutca rekordok törlése Törölje a hozzárendeléseket a később nem olvasott változókhoz. A hozzárendelés eltávolítása vagy azért történik, mert a változót nem olvasták be a változó élettartamának vége előtt, vagy azért, mert egy későbbi hozzárendelés felülírja azt.Az SSA (Single Static Assignment, Single Static Assignment) az adatfolyam-grafikon (DFG) megjelenítésének egyik formája, amelyben minden változóhoz csak egyszer van hozzárendelve érték. Ezzel elkerülhető az ívek megszorzása a grafikonon egy változó többszöri írása és olvasása során, és megkönnyíti a gráfelemzést. Ennek érdekében az SSA nézet speciális Phi függvényeket (adatfolyam gráf csomópontokat) vezet be a vezérlőfolyamat gráf egyes konvergenciapontjain. Ezek az új csomópontok az úgynevezett pszeudo-hozzárendelések.
A többszörös definíciók nem csak a vezérlési folyamatok konvergenciái ("vagy") miatt lehetségesek, hanem azért is, mert lehetőség van néhány összetett érték egészének olvasására, amelyet egynél több művelettel írtak le részekre ("és"). Ebben az esetben az SSA űrlap fenntartása érdekében további pszeudo-hozzárendeléseket vezetnek be az alapblokkon belül, amelyek egy értéket gyűjtenek több közül.
Néhány optimalizálás az SSA-n alapul. Bár néhány közülük SSA nélkül is működhet, akkor a leghatékonyabbak, ha SSA van jelen.