Optimalizační kompilátor je kompilátor , který používá různé metody k získání optimálnějšího programového kódu při zachování jeho funkčnosti. Nejběžnější cíle optimalizace jsou: snížení doby provádění programu, zvýšení výkonu, zhutnění programového kódu, úspora paměti, minimalizace nákladů na energii, snížení počtu I/O operací .
K optimalizaci může dojít implicitně během překladu programu, ale obecně je považována za samostatný krok v práci kompilátoru. Linkery mohou také provádět část optimalizací, jako je odstranění nepoužívaných podprogramů nebo jejich přeskupení .
Optimalizace je obvykle implementována prostřednictvím řady optimalizačních transformací, algoritmů , které vezmou program a upraví jej, aby vytvořily sémanticky ekvivalentní variantu, která je účinnější pro určitý soubor optimalizačních cílů. Některé problémy s optimalizací kódu se ukázaly být NP-úplné [1] , nebo dokonce nerozhodnutelné [2] . Přesto je prakticky mnoho z nich řešeno heuristickými metodami, které dávají vcelku uspokojivé výsledky.
Rozlišujte mezi nízko a vysokoúrovňovou optimalizací. Nízkoúrovňová optimalizace transformuje program na úrovni elementárních instrukcí, například instrukcí procesoru určité architektury . Optimalizace na vysoké úrovni se provádí na úrovni konstrukčních prvků programu, jako jsou moduly, funkce, větve, cykly.
Metody používané při optimalizacích lze klasifikovat podle rozsahu: mohou ovlivnit jak jeden příkaz, tak celý program. Lokální metody (ovlivňující malou část programu) jsou snadněji implementovatelné než globální metody (aplikující se na celý program), ale globální metody jsou často přínosnější.
Lokální optimalizace kukátka berou v úvahu několik sousedních (ve smyslu jednoho z grafů reprezentace programu) instrukcí (jako by se „koukali skrz kukátko “ na kód), aby se zjistilo, zda je možné s nimi provést nějakou transformaci z hlediska optimalizace. fotbalová branka. Zejména mohou být nahrazeny jedinou instrukcí nebo kratší sekvencí instrukcí.
Například zdvojnásobení čísla lze efektivněji provést pomocí levého posunu nebo přidáním čísla ke stejnému číslu.
Při lokální optimalizaci se uvažuje pouze informace o jednom základním bloku na krok [3] . Protože v základních blocích nejsou žádné přechody řídicích toků , vyžadují tyto optimalizace malou analýzu (úspora času a snížení požadavků na paměť), ale také to znamená, že se neukládají žádné informace pro další krok.
Intraprocedurální optimalizace ( anglicky intraprocedural ) jsou globální optimalizace, které se provádějí zcela v rámci překladové jednotky (například funkcí nebo procedur) [4] . Při takové optimalizaci jde o mnohem více informací než u té lokální, což umožňuje dosáhnout výraznějších efektů, ale často to vyžaduje výpočty náročné na zdroje. Pokud jsou v optimalizované programové jednotce globální proměnné , může být optimalizace tohoto druhu obtížná.
Na smyčky je aplikováno velké množství optimalizací. Při velkém počtu iterací smyčky jsou takové optimalizace extrémně efektivní, protože podstatná část provádění programu je ovlivněna malou transformací. Protože smyčky jsou významnou součástí doby provádění mnoha programů, optimalizace smyček existují téměř ve všech kompilátorech a jsou nejdůležitější.
Například identifikací invariantů smyčky je někdy možné odstranit některé operace ze smyčky, aby se neprováděly nadbytečné opakované výpočty.
Takové typy optimalizací analyzují celý zdrojový kód programu najednou. Větší množství informací extrahovaných těmito metodami znamená, že optimalizace mohou být efektivnější než jiné metody. Takové optimalizace mohou používat poměrně složité metody, například volání funkce je nahrazeno kopií těla funkce (inline nebo inline).
Příklad Nechť existuje nějaká funkce:
int pred ( int x ) { if ( x == 0 ) návrat 0 ; jiný návrat x - 1 ; }Před vložením kód vypadal takto:
int f ( int y ) { return pred ( y ) + pred ( 0 ) + pred ( y + 1 ); }Po optimalizaci:
int f ( int y ) { int temp = 0 ; if ( y == 0 ) teplota += 0 ; jinak teplota += y - 1 ; /* (jeden) */ if ( 0 == 0 ) teplota += 0 ; jinak teplota += 0 - 1 ; /* (2) */ if ( y + 1 == 0 ) teplota += 0 ; else temp += ( y + 1 ) - 1 ; /* (3) */ návratová teplota ; }Vkládání funkcí eliminuje režii spojenou s voláním funkcí. Po inliningu je navíc možné aplikovat intraprocedurální optimalizace, které byly dříve nemožné nebo příliš obtížné na implementaci. Inlining má však své nevýhody, jako téměř každá optimalizace – zvyšuje statickou velikost kódu, což může vést k negativním efektům v částech zařízení, které jsou na tento faktor citlivé.
Mezi faktory ovlivňující optimalizaci patří jak výpočetní vlastnosti cílového stroje (například počet a takt procesorových jader, velikost mezipaměti procesoru , šířka pásma systémové sběrnice , množství paměti RAM), tak architektura cílového počítače. procesor (zejména v různých architekturách je k dispozici různý počet univerzálních registrů, výpočetní potrubí je implementováno odlišně ). Další třídou faktorů, které ovlivňují optimalizaci, jsou scénáře použití cílového kódu, například cíle optimalizace se mohou výrazně lišit pro ladicí a testovací kód, příležitostné spouštění, nepřetržité používání, vestavěné nebo samostatné aplikace.
Mezi optimalizační principy používané v různých optimalizačních metodách v kompilátorech (některé z nich si mohou odporovat nebo být nepoužitelné pro různé optimalizační cíle):
Optimalizace toku dat jsou založeny na analýze toku dat a obvykle považují graf řídicího toku a graf toku dat vzájemně propojené jako vstupní data, stejně jako často strom smyček a označení smyček grafu řídicího toku. Analýzou zejména šíření informací na těchto grafech je odhalena možnost optimalizace z hlediska požadovaných cílů a následně jsou optimalizace aplikovány.
Odstranění běžných podvýrazů Odstranění společného podvýrazu je optimalizace kompilátoru, která hledá instance identických výrazů a analyzuje možnost jejich nahrazení jedinou proměnnou obsahující vypočítanou hodnotu. Konvoluce konstant Optimalizace, které omezují nadbytečné výpočty tím, že nahradí konstantní výrazy a proměnné jejich hodnotami. Analýza indukčních proměnných ( anal . analýza indukčních proměnných ) Viz popis v části Optimalizace cyklu . Mazání záznamů ve slepé uličce Odstraňte přiřazení k proměnným, které se následně nečtou. Přiřazení je odstraněno buď proto, že proměnná nebyla načtena před koncem životnosti proměnné, nebo proto, že následné přiřazení ji přepíše.SSA (Single Static Assignment, Single Static Assignment) je forma reprezentace grafu toku dat (DFG), ve které je každé proměnné přiřazena hodnota pouze jednou. To zabraňuje násobení oblouků v grafu během více zápisů a čtení jedné proměnné a usnadňuje analýzu grafu. K tomu zavádí pohled SSA speciální funkce Phi (uzly grafu toku dat) v některých bodech konvergence v grafu toku řízení. Tyto nové uzly jsou tzv. pseudopřiřazení.
Vícenásobné definice jsou možné nejen kvůli konvergencím řídicích toků ("nebo"), ale také kvůli možnosti číst nějakou složenou hodnotu jako celek, která byla zapsána po částech více než jednou operací ("a"). V tomto případě, aby se zachovala forma SSA, jsou uvnitř základních bloků zavedena další pseudopřiřazení, která shromažďují jednu hodnotu z několika.
Některé optimalizace jsou založeny na SSA. Ačkoli některé z nich mohou fungovat bez SSA, jsou nejúčinnější, když je přítomen SSA.