Vývoj kompilátoru je velmi náročný úkol. Naštěstí s rozvojem projektů jako je LLVM, se tento úkol výrazně zjednodušuje, což umožňuje i jednotlivému programátorovi vytvořit nový jazyk, který je výkonově blízký C. Práce s LLVM je komplikována tím, že tento systém je reprezentován obrovským objemem kódu, doplněným o malou dokumentaci. Aby se autor materiálu, jehož překlad dnes publikujeme, pokusil tento nedostatek napravit, chystá se demonstrovat příklady kódu napsaného v Go a ukázat, jak jsou nejprve překládat do , a poté do LLVM IR pomocí kompilátoru . Kód Go SSA a LLVM IR byl mírně upraven, odstranily se části, které se netýkají zde uvedených vysvětlení, aby byla tato vysvětlení srozumitelnější.
První příklad
První funkce, kterou zde hodlám podrobněji prozkoumat, představuje jednoduchý mechanismus pro sčítání čísel:
func myAdd(a, b int) int{
return a + b
}Tato funkce je velmi jednoduchá a asi už nic jednoduššího ani nevymyslíte. 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 t0Při tomto zobrazení funkce jsou typové nápovědy umístěny napravo, většinou na ně lze nevšímat.
Tento malý příklad již umožňuje vidět podstatu jednoho z aspektů SSA. A to, že při převodu kódu do formy SSA je každý výraz rozbit 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: součet dvou čísel a návrat výsledku.
Kromě toho zde můžeme vidět také základní bloky programu, v tomto kódu je pouze jeden blok — vstupní (entry block). O bloky se podrobněji zmíníme níže.
Kód Go SSA se snadno převádí do LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
} Je možné si všimnout, že ačkoli jsou zde použity jiné syntaktické struktury, struktura funkce se v zásadě nezměnila. Kód LLVM IR je o něco silnější než kód Go SSA a připomíná C. Zde, v deklaraci funkce, je nejprve popsán návratový typ dat, typ argumentu je uveden před názvem argumentu. Navíc, pro zjednodušení parsování IR, před názvy globálních entit stojí symbol @, zatímco před názvy lokálních — symbol % (funkce je také považována za globální entitu).
Jedním z rysů tohoto kódu, na který je třeba upozornit, je, že rozhodnutí o reprezentaci typu Go int, který může být reprezentován jako 32bitová nebo 64bitová hodnota v závislosti na kompilátoru a cíli kompilace, je učiněno při vytváření kódu LLVM IR. To je jeden z mnoha důvodů, proč kód LLVM IR není, jak si mnozí myslí, platformově nezávislý. Takový kód vytvořený pro jednu platformu nelze jednoduše vzít a zkompilovat pro jinou platformu (pokud se tomuto úkolu nepřistoupí ).
Dalším zajímavým bodem, který stojí za zmínku, je, že typ i64 není celé číslo se znaménkem: je neutrální z pohledu reprezentace znaménka čísla. V závislosti na instrukci může představovat jak čísla se znaménkem, tak čísla bez znaménka. V případě reprezentace operace sčítání to nedělá rozdíl, a proto zde není rozdíl v práci s čísly se znaménkem nebo bez znaménka. Zde by bylo vhodné poznamenat, že v jazyce C přetečení celočíselné proměnné se znaménkem vede k nedefinovanému chování, a proto frontend Clang přidává k operaci příznak nsw (no signed wrap), což naznačuje LLVM, že může vycházet z předpokladu, že při sčítání nikdy nedochází k přetečení.
To může být důležité pro některé optimalizace. Například sčítání dvou hodnot i16 na 32bitové platformě (s 32bitovými registry) vyžaduje po provedení sčítání operaci rozšíření znaménka, aby zůstala v rozsahu i16. Z tohoto důvodu je často efektivnější provádět celočíselné operace s ohledem na velikosti registrů strojového kódu.
To, co se dále děje s tímto IR kódem, nás teď příliš nezajímá. Kód se optimalizuje (ale v případě tak jednoduchého příkladu, jako je náš, se již nic neoptimalizuje), a poté se převádí na strojový kód.
Druhý příklad
Následující příklad, který probereme, bude o něco složitější. A to konkrétně o funkci, která sčítá slice 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řevádí na následující Go SSA kód:
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 už můžeme vidět více konstrukcí typických pro reprezentaci kódu ve formě SSA. Snad nejzřejmější vlastností tohoto kódu je to, že zde nejsou strukturované příkazy pro řízení toku výpočtů. Pro řízení toku výpočtů zde máme pouze podmíněné a bezpodmínečné skoky, a pokud tuto instrukci považujeme za příkaz pro řízení toku, je zde příkaz návratu.
Ve skutečnosti si zde můžeme všimnout, že program není rozdělen do bloků pomocí složených závorek (jak je to v jazycích rodiny C). Je rozdělen pomocí štítků, což připomíná assemblerové jazyky, a je prezentován ve formě základních bloků. V SSA jsou základními bloky nazývány nepřetržité sekvence kódu začínající štítkem a končící pokyny ukončení základního bloku, například — vrátit a jump.
Dalším zajímavým detailem tohoto kódu je instrukce phi. Tato instrukce je poměrně neobvyklá, její pochopení může zabrat nějaký čas. Pamatujte, že — je zkratka pro Static Single Assignment. Je to mezi-representation kódu používanému kompilátory, ve které je každé proměnné přiřazena hodnota pouze jednou. To je skvělé pro výrazy jednoduchých funkcí, jako je naše funkce myAdd, uvedená výše, ale nehodí se pro složitější funkce — jako je ta, kterou zkoumáme v této části sum. Konkrétně se během provádění cyklu mění proměnné i a n.
SSA obchází omezení na jednorázové přiřazení hodnot proměnným pomocí tzv. instrukce phi (jeho název pochází z řecké abecedy). K tomu, aby bylo možné vytvořit SSA-representation kódu pro jazyky jako je C, je nutné použít některé triky. Výsledkem zavolání této instrukce je aktuální hodnota proměnné (i nebo n), a jako její parametry se používá seznam základních bloků. Například zvažte tuto instrukci:
t0 = phi [entry: 0:int, for.body: t6] #n Její smysl spočívá v tom, že pokud byl předchozím základním blokem blok entry (vstupní), pak t0 je konstanta 0, a pokud byl předchozím základním blokem blok for.body, pak je třeba vzít hodnotu t6 z tohoto bloku. To vše může vypadat docela tajemně, ale díky tomuto mechanismu funguje SSA. Z lidského hlediska to všechno komplikuje 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 píšete vlastní kompilátor, obvykle se nemusíte s takovými věcmi potýkat. I Clang nevytváří všechny tyto instrukce phi, používá mechanismus alloca (ten připomíná práci s běžnými lokálními proměnnými). Poté, při provádění optimalizace LLVM zvané , se instrukce alloca přetvářejí na formu SSA. TinyGo však získává vstupní data od Go SSA, které, co je pohodlné, již byly převedeny do formy SSA.
Dalším novým prvkem zkoumaného fragmentu mezi-representation kódu je, že přístup k prvkům slice přes index je reprezentován jako operace výpočtu adresy a operace dereferencování získaného ukazatele. Zde můžeme vidět i přímé přidávání konstant v IR-kódu (např. — 1:int). V příkladu s funkcí myAdd Podobné nebylo použito. Nyní, po rozebrání těchto vlastností, se podívejme, jak se tento kód změní při transformaci do formy LLVM IR:
define i64 @sum(i64* %ptr, i64 %len, i64 p) {
entry:
br label %for.loop
for.loop: ; preds = %for.body, %entry
%0 = phi i64 [ 0, %entry ], [ %5, ref.next ]
%1 = phi i64 [ 0, %entry ], [ %6, ref.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á obsahuje další syntaktické konstrukce. Například při voláních phi se hodnoty a značky prohodily. Nicméně tady je i něco, na co stojí za to se zvlášť zaměřit.
Za prvé, tady můžeme vidět úplně jinou signaturu funkce. LLVM nepodporuje slice, a proto, jako optimalizaci, kompilátor TinyGo, který vytvořil tento mezikód, rozdělil popis této datové struktury na části. Mohl by představit tři prvky slice (ptr, len a cap) jako strukturu (struct), ale reprezentace jako tři oddělené entity umožňuje provádět některé optimalizace. Další kompilátory mohou reprezentovat slice jiným způsobem, to závisí na konvencích o volání funkcí cílové platformy.
Další zajímavou vlastností tohoto kódu je použití instrukce getelementptr (často se zkracuje na GEP).
Tato instrukce pracuje s ukazateli a používá se k získání ukazatele na prvek slice. Například, pojďme ji porovnat 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ší na tom je, že instrukce getelementptr neprovádí operaci dereference. Pouze počítá nový ukazatel na základě existujícího. Můžeme ji vnímat jako instrukci mul a add na hardwarové úrovni. Podrobnosti o instrukci GEP si můžete přečíst .
Další zajímavou vlastností tohoto mezikódu je použití instrukce icmp. Tento návod je obecně určen k provádění srovnání celých čísel. Výsledkem provedení tohoto pokynu je vždy hodnota typu i1 — logická hodnota. V tomto případě se provádí srovnání pomocí klíčového slova slt (signed less than), protože porovnáváme dvě čísla, jež jsou předložena typem int. Kdybychom porovnávali dvě celá čísla bez znaménka, použili bychom pokyn icmp, a klíčové slovo používané při porovnávání by bylo ult. K porovnání čísel s pohyblivou řádovou čárkou se používá jiný pokyn, fcmp, který funguje podobným způsobem.
Závěry
Domnívám se, že jsem v tomto materiálu pokryl nejdůležitější rysy LLVM IR. Určitě existuje ještě mnoho dalších věcí. Především může být v mezičinném zastoupení kódu přítomno mnoho anotací, které umožňují při optimalizačních průchodech zohlednit určité rysy kódu známé kompilátoru, které nelze jiným způsobem vyjádřit v IR. Například to je příznak inbounds pokynu GEP, nebo příznaky nsw a nuw, které mohou být přidány k pokynu add. To samé platí pro klíčové slovo private, které naznačuje optimalizátorovi, že na označenou funkci nebude odkazováno zvenčí aktuální jednotky kompilace. To umožňuje provádět mnoho zajímavých mezifunkčních optimalizací, jako je odstranění nepoužívaných argumentů.
Podrobnosti o LLVM si můžete přečíst v , kterou budete často potřebovat při vývoji vlastního kompilátoru založeného na LLVM. Zde je , ve kterém se zkoumá vývoj kompilátoru pro velmi jednoduchý jazyk. Oba tyto zdroje informací vám budou užitečné při vytváření vlastního kompilátoru.
Vážení čtenáři! Používáte LLVM?
Zdroj: habr.com
