Meziprocesová optimalizace - Interprocedural optimization
Interprocedural optimization ( IPO ) is a collection of compiler techniques used in computer programming to improve performance in programs containing many frequently used functions of small or medium length. IPO se liší od jiné optimalizace kompilátoru, protože analyzuje celý program; jiné optimalizace sledují pouze jednu funkci nebo dokonce jeden blok kódu.
IPO se snaží omezit nebo eliminovat duplicitní výpočty, neefektivní využití paměti a zjednodušit iterativní sekvence, jako jsou smyčky. Pokud dojde k volání jiné rutiny, která se vyskytne ve smyčce, může analýza IPO určit, že je nejlepší to vložit . Navíc IPO může re-nařídit rutiny pro lepší rozložení paměti a lokality .
IPO může také zahrnovat typické optimalizace kompilátoru na úrovni celého programu, například odstranění mrtvého kódu (DCE), které odstraní kód, který se nikdy nespustí. K dosažení tohoto cíle kompilátor testuje větve, které se nikdy nepřijmou, a odstraní kód v této větvi. IPO se také snaží zajistit lepší využití konstant. Moderní překladače nabízejí IPO jako možnost v době kompilace. Skutečný proces IPO může nastat v kterémkoli kroku mezi zdrojovým kódem čitelným člověkem a vytvořením hotového spustitelného binárního programu.
U jazyků, které se kompilují po jednotlivých souborech, vyžaduje efektivní IPO napříč překladovými jednotkami (soubory modulů) znalost „vstupních bodů“ programu, aby bylo možné spustit optimalizaci celého programu ( WPO ). V mnoha případech je to implementováno jako předání optimalizace propojení času ( LTO ), protože linker vidí celý program.
Analýza
Cílem jakékoli optimalizace rychlosti je mít program spuštěný co nejrychleji; problém je v tom, že není možné, aby kompilátor správně analyzoval program a určoval, co bude dělat, natož co pro něj programátor zamýšlel . Naproti tomu lidští programátoři začínají na druhém konci s určitým účelem a pokoušejí se vytvořit program, který ho dosáhne, nejlépe bez vynaložení velkého přemýšlení v procesu.
Z různých důvodů, včetně čitelnosti, jsou programy často rozděleny do několika postupů, které zpracovávají několik obecných případů. Obecnost každého postupu však může vyústit ve zbytečné úsilí při konkrétním použití. Meziprocesová optimalizace představuje pokus o snížení tohoto plýtvání.
Předpokládejme, že existuje postup, který vyhodnotí F (x) a kód požaduje výsledek F (6) a později F (6) znovu. Toto druhé vyhodnocení je téměř jistě zbytečné: výsledek mohl být místo toho uložen a odkazován později, za předpokladu, že F je čistá funkce . Tato jednoduchá optimalizace je zmařena v okamžiku, kdy se implementace F (x) stane nečistou; to znamená, že jeho provedení zahrnuje odkaz na jiné parametry než explicitní argument 6, které byly mezi vyvoláními změněny, nebo vedlejší účinky, jako je tisk nějaké zprávy do protokolu, počítání počtu vyhodnocení, akumulace času CPU , příprava interních tabulek takže bude usnadněno následné vyvolání souvisejících parametrů atd. Ztráta těchto nežádoucích účinků nehodnocením podruhé může být přijatelná, nebo nemusí.
Obecněji, kromě optimalizace, druhým důvodem pro použití postupů je vyhnout se duplikaci kódu, který by při každém provedení procedury přinesl stejné výsledky nebo téměř stejné výsledky. Obecným přístupem k optimalizaci by tedy bylo obrátit toto: některá nebo všechna vyvolání určitého postupu jsou nahrazena příslušným kódem, přičemž parametry jsou vhodně nahrazeny. Kompilátor se poté pokusí optimalizovat výsledek.
WPO a LTO
Whole program optimization ( WPO ) is the compiler optimization of a program using information about all the modules in the program. Normálně se optimalizace provádějí na základě jednotlivých modulů, „compiland“ ; ale tento přístup, i když je snadnější psát a testovat a je méně náročný na zdroje během samotné kompilace, neumožňuje jistotu ohledně bezpečnosti řady optimalizací, jako je agresivní vložení, a proto je nemůže provést, i když by se skutečně ukázaly jako zvýšení efektivity, které nemění sémantiku emitovaného objektového kódu.
Link-time optimization ( LTO ) is a type of program optimization performed by a compiler to a program at link time . Doba Link optimalizace je relevantní pro programovací jazyky, které kompilovat programy na soubor jednotlivých souborů základ, a pak spojit tyto soubory společně (jako je C a Fortran ), spíše než všichni najednou (jako je Javě to just-in-time kompilace (JIT)).
Jakmile jsou všechny soubory zkompilovány samostatně do souborů objektů , tradičně kompilátor propojí (sloučí) soubory objektů do jednoho souboru, spustitelného souboru . Avšak v LTO implementovaném GNU Compiler Collection (GCC) nebo LLVM je kompilátor schopen vypsat svou mezilehlou reprezentaci ( GIMPLE bytecode nebo LLVM bitcode) na disk tak, aby všechny různé kompilační jednotky, které budou tvořit jeden spustitelný soubor lze optimalizovat jako jeden modul, když se spojení nakonec stane. Tím se rozšiřuje rozsah meziprocedurálních optimalizací tak, aby zahrnoval celý program (nebo spíše vše, co je viditelné v době odkazu). S optimalizací link-time může kompilátor aplikovat různé formy interprocedurální optimalizace na celý program, což umožňuje hlubší analýzu, větší optimalizaci a nakonec lepší výkon programu.
V praxi LTO ne vždy optimalizuje celý program - funkce knihovny , zejména dynamicky propojené sdílené objekty, jsou záměrně uchovávány, aby se zabránilo nadměrné duplikaci a aby se umožnila aktualizace. Statické propojení přirozeně propůjčuje koncept LTO, ale funguje pouze s archivy knihoven, které obsahují objekty IR, na rozdíl od souborů objektů pouze se strojovým kódem. Kvůli problémům s výkonem není vždy přímo použita ani celá jednotka - program lze rozdělit na LTO ve stylu rozděl a panuj, jako je GOP WHOPR. A samozřejmě, když je vytvářený program sám o sobě knihovnou, optimalizace by zachovala každý externě dostupný (exportovaný) symbol, aniž by se příliš snažil o jejich odstranění jako součásti DCE.
Mnohem omezenější forma WPO je stále možná bez LTO, jak dokládá -fwhole-program přepínač GCC . Tento režim umožňuje GCC předpokládat, že kompilovaný modul obsahuje vstupní bod (obvykle main() ) celého programu, takže všechny ostatní funkce v něm nejsou používány externě a lze je bezpečně optimalizovat. Jelikož se vztahuje pouze na jeden modul, nemůže skutečně zahrnovat celý program. (Lze jej kombinovat s LTO ve smyslu jednoho velkého modulu, což je užitečné, když linker nekomunikuje zpět do GCC o tom, jaké vstupní body nebo symboly se používají externě.)
Příklad
Program example;
integer b; {A variable "global" to the procedure Silly.}
Procedure Silly(a,x)
if x < 0 then a:=x + b else a:=-6;
End Silly; {Reference to b, not a parameter, makes Silly "impure" in general.}
integer a,x; {These variables are visible to Silly only if parameters.}
x:=7; b:=5;
Silly(a,x); write(x);
Silly(x,a); write(x);
Silly(b,b); write(b);
End example;
V případě, že parametry pro Silly jsou předány hodnotou , akce řízení nemá žádný vliv na původní proměnné, a protože Silly nepřispívá k jeho prostředí (čtení ze souboru, zápis do souboru, upravit globální proměnné , jako je b , atd .) jeho kód a všechna vyvolání může být optimalizována pryč úplně, takže hodnotu nedefinované (což nevadí), takže právě tyto tiskové prohlášení zůstávají, a oni na konstantních hodnotách.
Pokud jsou parametry předány odkazem , pak akce na ně v rámci Silly skutečně ovlivní originály. To se obvykle provádí předáním adresy stroje parametru proceduře tak, aby úpravy procedury byly v původní úložné oblasti. V případě volání odkazem má tedy postup Silly účinek. Předpokládejme, že jeho vyvolání jsou rozšířena na místě s parametry identifikovanými podle adresy: kód činí
x:=7; b:=5;
if x < 0 then a:=x + b else a:=-6; write(x); {a is changed.}
if a < 0 then x:=a + b else x:=-6; write(x); {Because the parameters are swapped.}
if b < 0 then b:=b + b else b:=-6; write(b); {Two versions of variable b in Silly, plus the global usage.}
Kompilátor by pak v tomto poměrně malém příkladu mohl sledovat logické konstanty (jako je) a zjistit, že predikáty příkazů if jsou konstantní a tak ...
x:=7; b:=5;
a:=-6; write(7); {b is not referenced, so this usage remains "pure".}
x:=-1; write(-1); {b is referenced...}
b:=-6; write(-6); {b is modified via its parameter manifestation.}
A protože zařazení do , b a x dodat nic společného s vnějším světem - se neobjevují ve výstupních prohlášení, ani jako vstup do následných výpočtech (jehož výsledky zase dělat vedení na výstupu, jinak oni jsou také zbytečné) - existuje ani v tomto kódu nemá smysl, takže výsledek je
write(7);
write(-1);
write(-6);
Alternativní metodou pro předávání parametrů, které se zdají být „podle odkazu“, je kopírování, kopírování, při kterém procedura funguje na lokální kopii parametrů, jejichž hodnoty jsou při výstupu z procedury zkopírovány zpět do originálů. Pokud má procedura přístup ke stejnému parametru, ale různými způsoby jako při vyvolání, jako je Silly (a, a) nebo Silly (a, b) , mohou vzniknout nesrovnalosti. Pokud by tedy parametry byly předány kopírováním, kopírováním v pořadí zleva doprava, Silly (b, b) by expandovalo do
p1:=b; p2:=b; {Copy in. Local variables p1 and p2 are equal.}
if p2 < 0 then p1:=p2 + b else p1:=-6; {Thus p1 may no longer equal p2.}
b:=p1; b:=p2; {Copy out. In left-to-right order, the value from p1 is overwritten.}
A v tomto případě je kopírování hodnoty p1 (která byla změněna) na b zbytečné, protože je okamžitě přepsáno hodnotou p2 , jejíž hodnota nebyla v rámci procedury změněna z původní hodnoty b , a tak třetí výrok se stává
write(5); {Not -6}
Takové rozdíly v chování pravděpodobně způsobí zmatek, který se prohloubí otázkami ohledně pořadí, ve kterém jsou parametry kopírovány: bude to při výstupu i při vstupu zleva doprava? Tyto podrobnosti pravděpodobně nejsou v příručce kompilátoru pečlivě vysvětleny, a pokud ano, budou pravděpodobně předány, protože nejsou relevantní pro okamžitý úkol a dlouho zapomenuty v době, kdy nastane problém. Pokud jsou (jak je pravděpodobné) dočasné hodnoty poskytovány prostřednictvím schématu úložiště zásobníku, je pravděpodobné, že proces zpětného kopírování bude v opačném pořadí než kopírování, což by v tomto příkladu znamenalo, že p1 bude poslední hodnota se místo toho vrátila do b .
Proces rozšiřování procedury in-line by neměl být považován za variantu nahrazení textu (jako v případě makro expanzí), protože mohou nastat chyby syntaxe, jako když jsou změněny parametry a konkrétní vyvolání používá jako parametry konstanty. Protože je důležité mít jistotu, že u všech konstant poskytovaných jako parametry nebude změněna jejich hodnota (konstanty mohou být uchovávány v paměti stejně jako proměnné), aby se následné použití této konstanty (vytvořené pomocí odkazu na její paměťové místo) nepokazilo, běžnou technikou je, že kompilátor generuje kód kopírující hodnotu konstanty do dočasné proměnné, jejíž adresa je předána proceduře, a pokud je její hodnota změněna, bez ohledu na to; nikdy se nekopíruje zpět na místo konstanty.
Jinými slovy, pečlivě napsaný testovací program může hlásit, zda jsou parametry předávány hodnotou nebo odkazem, a pokud je použit, jaký typ schématu kopírování a kopírování. Variace je však nekonečná: jednoduché parametry mohou být předány kopií, zatímco velké agregáty, jako jsou pole, mohou být předány odkazem; jednoduché konstanty, jako je nula, mohou být generovány speciálními strojovými kódy (jako je Clear nebo LoadZ), zatímco složitější konstanty mohou být uloženy v paměti označené jako jen pro čtení s jakýmkoli pokusem o její úpravu, což má za následek okamžité ukončení programu atd.
Obecně
Tento příklad je extrémně jednoduchý, i když komplikace jsou již patrné. Pravděpodobnější je, že to bude případ mnoha procedur, které mají řadu odvoditelných nebo programem deklarovaných vlastností, které mohou umožnit optimalizaci kompilátoru najít nějakou výhodu. Jakýkoli parametr procedury může být pouze pro čtení, zapisován do, být čten i zapisován nebo může být zcela ignorován, což vede k příležitostem, jako jsou konstanty, které nevyžadují ochranu prostřednictvím dočasných proměnných, ale co se stane v daném vyvolání, může dobře záviset na komplexní síť úvah. Jiné procedury, zejména procedury podobné funkcím, budou mít určité chování, které v konkrétních vyvoláních může umožnit, aby se některé práce vyhnuly: například funkce Gamma , pokud je vyvolána celočíselným parametrem, může být převedena na výpočet zahrnující celočíselné faktoriály.
Některé počítačové jazyky umožňují (nebo dokonce vyžadují) tvrzení, pokud jde o použití parametrů, a mohou dále nabízet příležitost deklarovat, že proměnné mají své hodnoty omezené na nějakou sadu (například 6 <x ≤ 28), což poskytuje další význam pro optimalizační proces, který proběhne, a také poskytnutí hodnotných kontrol koherence zdrojového kódu pro detekci omylů. Ale to nikdy není dost - pouze některým proměnným mohou být dána jednoduchá omezení, zatímco jiným by bylo zapotřebí složitých specifikací: jak by bylo možné určit, že proměnná P má být prvočíslem, a pokud ano, je nebo není zahrnuta hodnota 1? Komplikace jsou okamžité: jaký je platný rozsah pro den v měsíci D vzhledem k tomu, že M je číslo měsíce? A jsou všechna porušení hodná okamžitého ukončení? Jaká výhoda by z toho mohla vyplývat, i kdyby bylo vše možné zvládnout? A za jakou cenu? Úplné specifikace by se rovnaly novému vyjádření funkce programu v jiné podobě a kromě doby, kterou by kompilátor spotřeboval při jejich zpracování, by tedy byly předmětem chyb. Místo toho jsou povoleny pouze jednoduché specifikace s poskytnutou kontrolou rozsahu běhu.
V případech, kdy program nečte žádný vstup (jako v příkladu), lze si představit, že se analýza kompilátoru přenáší dopředu, takže výsledkem nebude více než řada tiskových příkazů nebo případně nějaké smyčky, které účelně generují takové hodnoty. Rozpoznal by pak program, který generuje prvočísla, a konvertoval na nejznámější metodu, nebo by místo toho představil odkaz na knihovnu? Nepravděpodobné! Obecně platí, že to vylučuje libovolně složitá úvaha ( Entscheidungsproblem ), a neexistuje jiná možnost než spustit kód pouze s omezenými vylepšeními.
Dějiny
Zdá se, že pro procedurální jazyky nebo jazyky podobné ALGOLu se meziprocedurální analýza a optimalizace začaly komerčně používat na začátku 70. let. Kompilátor pro optimalizaci PL / I společnosti IBM provedl interprocedurální analýzu, aby pochopil vedlejší účinky volání procedur i výjimek (obsazení, v termínech PL / I jako „za podmínek“) a v dokumentech Fran Allen . Práce na kompilaci programovacího jazyka APL byly nutně interprocedurální.
Techniky interprocedurální analýzy a optimalizace byly předmětem akademického výzkumu v 80. a 90. letech. Na počátku 90. let se znovu objevili ve světě komerčních překladačů pomocí překladačů od společnosti Convex Computer Corporation (dále jen „Application Compiler“ pro Convex C4) a od firmy Ardent (překladač pro Ardent Titan ). Tito kompilátoři prokázali, že technologie lze vyrobit dostatečně rychle, aby byly přijatelné v komerčním kompilátoru; následně se interprocedurální techniky objevily v řadě komerčních i nekomerčních systémů.
Vlajky a implementace
Unixový
GNU Compiler Collection má funkci inlining na všech úrovních optimalizace. Na -O1 toto se vztahuje pouze na ty, které pouze tzv jednou ( -finline-functions-once ), na -O2 tato omezení se uvolnila ( -finline-functions ). Ve výchozím nastavení se jedná o chování pouze pro jeden soubor, ale s optimalizací času propojení -flto se stane celým programem. Rozhraní příkazového řádku Clang je podobné rozhraní GCC, s výjimkou, že neexistuje žádná -fwhole-program možnost.
Soubory objektů produkované LTO obsahují mezilehlou reprezentaci (IR) specifickou pro překladač, která je interpretována v době propojení. Aby se zajistilo, že to bude dobře fungovat se statickými knihovnami , novější linkery GNU mají rozhraní „linker plugin“, které umožňuje kompilátoru v případě potřeby převést soubory objektů do podoby strojového kódu. Tento plugin také pomáhá řídit proces LTO obecně. Alternativně lze vytvořit „tlustý LTO“ objekt, který obsahuje strojový kód i IR, ale to zabere více místa.
Vzhledem k tomu, že GCC i LLVM (clang) jsou schopny produkovat IR z různých programovacích jazyků, může dojít k IPO v čase spojení i přes hranice jazyků. To je nejčastěji demonstrováno na C a C ++, ale LLVM umožňuje také pro Rust a všechny ostatní kompilátory založené na LLVM.
Možnosti jiné než LTO
GCC a Clang provádějí IPO ve výchozím nastavení na úrovni optimalizace 2. Míra optimalizace je však omezena, když je LTO zakázáno, protože IPO může nastat pouze v souboru objektu a nestatické funkce nelze nikdy vyloučit. Druhý problém má řešení jiné než LTO: -fwhole-program přepínač lze použít k předpokladu, že pouze main() je nestatický, tj. Viditelný zvenčí.
Další technikou, která není metodou LTO, jsou „funkční sekce“ ( -ffunction-sections v GCC a Clang). Umístěním každé funkce do své vlastní sekce v souboru objektu může linker provést odstranění mrtvého kódu bez IR odstraněním neodkazovaných částí ( --gc-sections ). Podobná možnost je k dispozici pro proměnné, ale způsobí to produkci mnohem horšího kódu.
jiný
S Intel C / C ++ kompilátory povolit celého programu IPO. Příznak umožňující meziprocedurální optimalizaci pro jeden soubor je -ip , příznak umožňující meziprocedurální optimalizaci pro všechny soubory v programu je -ipo .
MSVC kompilátor , integrované do Visual Studia, také podporuje interprocedural optimalizaci na celý program.
Rozhraní nezávislé na kompilátoru pro povolení meziprocedurálních optimalizací celého programu je prostřednictvím INTERPROCEDURAL_OPTIMIZATION vlastnosti v CMake .
