Vývoj kompilátoru je velmi obtížný úkol. Ale naštěstí s rozvojem projektů jako LLVM se řešení tohoto problému značně zjednodušuje, což umožňuje i jedinému programátorovi vytvořit nový jazyk, který se výkonově blíží C. Práce s LLVM je komplikovaná tím, že tento systém je reprezentován velkým množstvím kódu, který je vybaven malou dokumentací. Abychom se pokusili tento nedostatek napravit, autor materiálu, jehož překlad dnes zveřejňujeme, předvede příklady kódu napsaného v Go a ukáže, jak jsou poprvé přeloženy do a poté v LLVM IR pomocí kompilátoru . IR kód Go SSA a LLVM byl mírně upraven, aby byly odstraněny věci, které nejsou relevantní pro zde uvedená vysvětlení, aby byla vysvětlení srozumitelnější.
První příklad
První funkcí, na kterou se zde podívám, je jednoduchý mechanismus pro sčítání čísel:
func myAdd(a, b int) int{
return a + b
}Tato funkce je velmi jednoduchá a snad už nic jednoduššího být nemůže. Překládá se do následujícího kódu Go SSA:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0V tomto zobrazení jsou rady datových typů umístěny vpravo a lze je ve většině případů ignorovat.
Tento malý příklad vám již umožňuje vidět podstatu jednoho aspektu SSA. Totiž při převodu kódu do formy SSA je každý výraz rozložen na nejzákladnější části, ze kterých se skládá. V našem případě příkaz return a + b, ve skutečnosti představuje dvě operace: sečtení dvou čísel a vrácení výsledku.
Navíc zde vidíte základní bloky programu, v tomto kódu je pouze jeden blok - vstupní blok. O blocích si povíme více níže.
Kód Go SSA se snadno převede na LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Čeho si můžete všimnout je, že ačkoli jsou zde použity různé syntaktické struktury, struktura funkce se v podstatě nemění. IR kód LLVM je o něco silnější než kód Go SSA, podobně jako C. Zde je v deklaraci funkce nejprve popis datového typu, který vrací, typ argumentu je uveden před názvem argumentu. Navíc pro zjednodušení IR analýzy je před názvy globálních entit uveden symbol @, a před místními názvy je symbol % (funkce je také považována za globální entitu).
Jedna věc, kterou je třeba o tomto kódu poznamenat, je rozhodnutí reprezentace typu Go int, která může být reprezentována jako 32bitová nebo 64bitová hodnota, v závislosti na kompilátoru a cíli kompilace, je přijata, když LLVM generuje IR kód. To je jeden z mnoha důvodů, proč IR kód LLVM není, jak si mnoho lidí myslí, nezávislý na platformě. Takový kód vytvořený pro jednu platformu nelze jednoduše vzít a zkompilovat pro jinou platformu (pokud nejste vhodní pro řešení tohoto problému ).
Dalším zajímavým bodem, který stojí za zmínku, je typ i64 není celé číslo se znaménkem: je neutrální, pokud jde o reprezentaci znaménka čísla. V závislosti na instrukci může představovat čísla se znaménkem i bez znaménka. V případě znázornění operace sčítání to nevadí, takže není rozdíl v práci s čísly se znaménkem nebo bez znaménka. Zde bych rád poznamenal, že v jazyce C vede přetečení podepsané celočíselné proměnné k nedefinovanému chování, takže frontend Clang přidá k operaci příznak nsw (bez podepsaného zalomení), což říká LLVM, že může předpokládat, že sčítání nikdy nepřeteče.
To může být důležité pro některé optimalizace. Například přidání dvou hodnot i16 na 32bitové platformě (s 32bitovými registry) vyžaduje po přidání operaci rozšíření znaménka, aby zůstal v dosahu i16. Z tohoto důvodu je často efektivnější provádět celočíselné operace založené na velikostech registrů stroje.
Co se stane dál s tímto IR kódem, nás teď zvlášť nezajímá. Kód je optimalizován (ale v případě jednoduchého příkladu, jako je ten náš, není optimalizováno nic) a následně převeden do strojového kódu.
Druhý příklad
Další příklad, na který se podíváme, bude trochu složitější. Konkrétně mluvíme o funkci, která sečte část celých čísel:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Tento kód se převede na následující kód Go SSA:
func sum(numbers []int) int:
entry:
jump for.loop
for.loop:
t0 = phi [entry: 0:int, for.body: t6] #n int
t1 = phi [entry: 0:int, for.body: t7] #i int
t2 = len(numbers) int
t3 = t1 < t2 bool
if t3 goto for.body else for.done
for.body:
t4 = &numbers[t1] *int
t5 = *t4 int
t6 = t0 + t5 int
t7 = t1 + 1:int int
jump for.loop
for.done:
return t0Zde již můžete vidět více konstrukcí typických pro reprezentaci kódu ve formě SSA. Snad nejviditelnějším rysem tohoto kódu je skutečnost, že neexistují žádné strukturované příkazy řízení toku. Pro řízení toku výpočtů existují pouze podmíněné a nepodmíněné skoky, a pokud tento příkaz považujeme za příkaz k řízení toku, příkaz návratu.
Ve skutečnosti zde můžete věnovat pozornost skutečnosti, že program není rozdělen do bloků pomocí složených závorek (jako v rodině jazyků C). Je rozdělena popisky, připomínajícími jazyky symbolických instrukcí, a prezentována ve formě základních bloků. V SSA jsou základní bloky definovány jako souvislé sekvence kódu začínající štítkem a končící pokyny pro dokončení základního bloku, jako je − return и jump.
Další zajímavý detail tohoto kódu představuje instrukce phi. Pokyny jsou poměrně neobvyklé a jejich pochopení může chvíli trvat. Pamatuj si to je zkratka pro Static Single Assignment. Jedná se o přechodnou reprezentaci kódu používaného kompilátory, ve kterém je každé proměnné přiřazena hodnota pouze jednou. To je skvělé pro vyjádření jednoduchých funkcí, jako je naše funkce myAddzobrazena výše, ale není vhodná pro složitější funkce, jako je funkce popsaná v této části sum. Proměnné se mění zejména během provádění cyklu i и n.
SSA obchází omezení jednorázového přiřazení hodnot proměnných pomocí takzvané instrukce phi (jeho název je převzat z řecké abecedy). Faktem je, že aby byla reprezentace kódu SSA generována pro jazyky jako C, musíte se uchýlit k některým trikům. Výsledkem volání této instrukce je aktuální hodnota proměnné (i nebo n), a jako jeho parametry se používá seznam základních bloků. Zvažte například tento pokyn:
t0 = phi [entry: 0:int, for.body: t6] #n
Jeho význam je následující: pokud předchozí základní blok byl blok entry (vstup), tedy t0 je konstanta 0, a pokud předchozí základní blok byl for.body, pak musíte vzít hodnotu t6 z tohoto bloku. To vše se může zdát docela záhadné, ale tento mechanismus je to, co dělá SSA práci. Z lidského hlediska je toto vše obtížné pro pochopení kódu, ale skutečnost, že každá hodnota je přiřazena pouze jednou, značně usnadňuje mnoho optimalizací.
Všimněte si, že pokud si napíšete svůj vlastní kompilátor, obvykle se s tímto druhem věcí nebudete muset zabývat. Dokonce ani Clang negeneruje všechny tyto instrukce phi, používá mechanismus alloca (připomíná to práci s běžnými lokálními proměnnými). Poté, když běží LLVM optimalizace pass volán , návod alloca převeden do podoby SSA. TinyGo však přijímá vstup od Go SSA, který je již pohodlně převeden do podoby SSA.
Další inovací uvažovaného fragmentu mezilehlého kódu je, že přístup k prvkům slepky pomocí indexu je reprezentován ve formě operace výpočtu adresy a operace dereferencování výsledného ukazatele. Zde můžete vidět přímé přidání konstant do IR kódu (například - 1:int). V příkladu s funkcí myAdd toto nebylo použito. Nyní, když máme tyto funkce z cesty, pojďme se podívat na to, čím se tento kód stane, když se převede do formy LLVM IR:
define i64 @sum(i64* %ptr, i64 %len, i64 %cap) {
entry:
br label %for.loop
for.loop: ; preds = %for.body, %entry
%0 = phi i64 [ 0, %entry ], [ %5, %deref.next ]
%1 = phi i64 [ 0, %entry ], [ %6, %deref.next ]
%2 = icmp slt i64 %1, %len
br i1 %2, label %for.body, label %for.done
for.body: ; preds = %for.loop
%3 = getelementptr i64, i64* %ptr, i64 %1
%4 = load i64, i64* %3
%5 = add i64 %0, %4
%6 = add i64 %1, 1
br label %for.loop
for.done: ; preds = %for.loop
ret i64 %0
}
Zde, stejně jako dříve, můžeme vidět stejnou strukturu, která zahrnuje další syntaktické struktury. Například v hovorech phi hodnoty a štítky vyměněny. Je zde však něco, co stojí za to věnovat zvláštní pozornost.
Pro začátek zde můžete vidět úplně jiný podpis funkce. LLVM nepodporuje řezy a v důsledku toho v rámci optimalizace kompilátor TinyGo, který vygeneroval tento mezikód, rozdělil popis této datové struktury na části. Může představovat tři prvky řezu (ptr, len и cap) jako strukturu (struct), ale jejich reprezentace jako tři samostatné entity umožňuje určité optimalizace. Jiné kompilátory mohou řez reprezentovat jinými způsoby, v závislosti na konvencích volání funkcí cílové platformy.
Další zajímavou vlastností tohoto kódu je použití instrukce getelementptr (často zkráceně GEP).
Tato instrukce pracuje s ukazateli a používá se k získání ukazatele na prvek řezu. Porovnejme to například s následujícím kódem napsaným v C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Nebo s následujícím ekvivalentem:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
Nejdůležitější je zde návod getelementptr neprovádí operace dereferencování. Pouze vypočítá nový ukazatel na základě stávajícího. Dá se to brát jako návod mul и add na hardwarové úrovni. Můžete si přečíst více o pokynech GEP .
Další zajímavou vlastností tohoto přechodného kódu je použití instrukce icmp. Toto je obecná instrukce používaná k implementaci celočíselných porovnávání. Výsledkem této instrukce je vždy hodnota typu i1 — logická hodnota. V tomto případě je provedeno srovnání pomocí klíčového slova slt (se znaménkem menší než), protože porovnáváme dvě čísla dříve reprezentovaná typem int. Pokud bychom porovnávali dvě celá čísla bez znaménka, pak bychom použili icmpa klíčové slovo použité v porovnání by bylo ult. Pro porovnání čísel s pohyblivou řádovou čárkou se používá další instrukce, fcmp, který funguje podobným způsobem.
Výsledky
Věřím, že v tomto materiálu jsem pokryl nejdůležitější vlastnosti LLVM IR. Samozřejmě je toho tady mnohem víc. Zejména mezilehlá reprezentace kódu může obsahovat mnoho anotací, které umožňují optimalizační průchody, aby vzaly v úvahu určité vlastnosti kódu známé kompilátoru, které nelze jinak vyjádřit v IR. Například toto je vlajka inbounds GEP instrukce nebo příznaky nsw и nuw, které lze přidat do návodu add. Totéž platí pro klíčové slovo private, což optimalizátoru signalizuje, že na funkci, kterou označí, nebude odkazovat mimo aktuální kompilační jednotku. To umožňuje mnoho zajímavých interprocedurálních optimalizací, jako je eliminace nepoužívaných argumentů.
Více o LLVM si můžete přečíst v , na který budete často odkazovat při vývoji vlastního kompilátoru založeného na LLVM. Tady , která se zabývá vývojem kompilátoru pro velmi jednoduchý jazyk. Oba tyto zdroje informací se vám budou hodit při vytváření vlastního kompilátoru.
Vážení čtenáři! Používáte LLVM?
Zdroj: www.habr.com