Vývoj kompilátora je veľmi náročná úloha. Ale, našťastie, s vývojom projektov ako LLVM sa riešenie tohto problému výrazne zjednodušuje, čo umožňuje aj jedinému programátorovi vytvoriť nový jazyk, ktorý je výkonovo blízky jazyku C. Práca s LLVM je komplikovaná tým, že tento systém je reprezentovaný obrovským množstvom kódu, ktorý je vybavený malou dokumentáciou. V snahe napraviť tento nedostatok autor materiálu, ktorého preklad dnes uverejňujeme, predvedie príklady kódu napísaného v Go a ukáže, ako sa prvýkrát prekladajú do a potom v LLVM IR pomocou kompilátora . IR kód Go SSA a LLVM bol mierne upravený, aby sa odstránili veci, ktoré nie sú relevantné pre tu uvedené vysvetlenia, aby boli vysvetlenia zrozumiteľnejšie.
Prvý príklad
Prvá funkcia, na ktorú sa tu pozriem, je jednoduchý mechanizmus na sčítanie čísel:
func myAdd(a, b int) int{
return a + b
}Táto funkcia je veľmi jednoduchá a možno už nič jednoduchšie nemôže byť. Prekladá sa do nasledujúceho kódu Go SSA:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0V tomto zobrazení sú rady typu údajov umiestnené vpravo a vo väčšine prípadov ich možno ignorovať.
Tento malý príklad vám už umožňuje vidieť podstatu jedného aspektu SSA. Totiž pri prevode kódu do formy SSA sa každý výraz rozloží na najzákladnejšie časti, z ktorých sa skladá. V našom prípade príkaz return a + b, v skutočnosti predstavuje dve operácie: sčítanie dvoch čísel a vrátenie výsledku.
Okrem toho tu vidíte základné bloky programu, v tomto kóde je len jeden blok - vstupný blok. O blokoch si povieme viac nižšie.
Kód Go SSA sa ľahko konvertuje na LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Čo si môžete všimnúť je, že hoci sú tu použité rôzne syntaktické štruktúry, štruktúra funkcie je v podstate nezmenená. IR kód LLVM je o niečo silnejší ako kód Go SSA, podobne ako C. Tu je v deklarácii funkcie najprv popis dátového typu, ktorý vracia, typ argumentu je uvedený pred názvom argumentu. Okrem toho, aby sa zjednodušila analýza IR, pred názvom globálnych entít je uvedený symbol @, a pred miestnymi názvami je uvedený symbol % (za globálnu entitu sa považuje aj funkcia).
Jedna vec, ktorú treba o tomto kóde poznamenať, je rozhodnutie o reprezentácii typu Go int, ktorá môže byť reprezentovaná ako 32-bitová alebo 64-bitová hodnota, v závislosti od kompilátora a cieľa kompilácie, je akceptovaná pri generovaní IR kódu LLVM. Toto je jeden z mnohých dôvodov, prečo IR kód LLVM nie je, ako si mnohí myslia, nezávislý od platformy. Takýto kód vytvorený pre jednu platformu nie je možné jednoducho vziať a skompilovať pre inú platformu (pokiaľ nie ste vhodný na riešenie tohto problému ).
Ďalším zaujímavým bodom, ktorý stojí za zmienku, je typ i64 nie je celé číslo so znamienkom: je neutrálne, pokiaľ ide o vyjadrenie znamienka čísla. V závislosti od inštrukcie môže predstavovať čísla so znamienkom aj bez znamienka. V prípade znázornenia operácie sčítania to nevadí, takže nie je rozdiel v práci s číslami so znamienkom alebo bez znamienka. Tu by som rád poznamenal, že v jazyku C vedie pretečenie celočíselnej premennej so znamienkom k nedefinovanému správaniu, takže rozhranie Clang pridáva k operácii príznak nsw (bez podpísaného obalu), čo LLVM hovorí, že môže predpokladať, že sčítanie nikdy nepretečie.
To môže byť dôležité pre niektoré optimalizácie. Napríklad pridanie dvoch hodnôt i16 na 32-bitovej platforme (s 32-bitovými registrami) vyžaduje po pridaní operáciu rozšírenia znamienka, aby zostal v dosahu i16. Z tohto dôvodu je často efektívnejšie vykonávať celočíselné operácie založené na veľkostiach registrov strojov.
Čo sa stane ďalej s týmto IR kódom, nás teraz zvlášť nezaujíma. Kód sa optimalizuje (ale v prípade jednoduchého príkladu, ako je ten náš, sa neoptimalizuje nič) a následne sa prevedie na strojový kód.
Druhý príklad
Ďalší príklad, na ktorý sa pozrieme, bude trochu komplikovanejší. Konkrétne hovoríme o funkcii, ktorá sčítava časť 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 sa skonvertuje na nasledujúci 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 t0Tu už môžete vidieť viac konštrukcií typických pre reprezentáciu kódu vo forme SSA. Snáď najzrejmejšou vlastnosťou tohto kódu je skutočnosť, že neexistujú žiadne štruktúrované príkazy na riadenie toku. Na riadenie toku výpočtov existujú iba podmienené a nepodmienené skoky, a ak tento príkaz považujeme za príkaz na riadenie toku, príkaz návratu.
V skutočnosti tu môžete venovať pozornosť skutočnosti, že program nie je rozdelený do blokov pomocou zložených zátvoriek (ako v rodine jazykov C). Je rozdelený štítkami, pripomínajúcimi jazyky symbolických inštrukcií, a prezentovaný vo forme základných blokov. V SSA sú základné bloky definované ako súvislé sekvencie kódu začínajúce štítkom a končiace pokynmi na dokončenie základného bloku, ako napríklad − return и jump.
Ďalší zaujímavý detail tohto kódu predstavuje inštrukcia phi. Pokyny sú dosť nezvyčajné a ich pochopenie môže chvíľu trvať. zapamätaj si to je skratka pre Static Single Assignment. Toto je prechodná reprezentácia kódu používaného kompilátormi, v ktorom je každej premennej priradená hodnota iba raz. Je to skvelé na vyjadrenie jednoduchých funkcií, ako je naša funkcia myAddzobrazený vyššie, ale nie je vhodný pre zložitejšie funkcie, ako je funkcia diskutovaná v tejto časti sum. Najmä premenné sa menia počas vykonávania cyklu i и n.
SSA obchádza obmedzenie na jednorazové priradenie hodnôt premenných pomocou takzvanej inštrukcie phi (jej názov je prevzatý z gréckej abecedy). Faktom je, že na to, aby sa reprezentácia kódu SSA vygenerovala pre jazyky ako C, musíte sa uchýliť k niektorým trikom. Výsledkom volania tejto inštrukcie je aktuálna hodnota premennej (i alebo n) a ako jeho parametre sa používa zoznam základných blokov. Zvážte napríklad tento pokyn:
t0 = phi [entry: 0:int, for.body: t6] #n
Jeho význam je nasledovný: ak predchádzajúcim základným blokom bol blok entry (vstup), potom t0 je konštanta 0, a ak predchádzajúci základný blok bol for.body, potom musíte vziať hodnotu t6 z tohto bloku. Toto všetko sa môže zdať dosť záhadné, ale tento mechanizmus robí SSA fungovaním. Z ľudského hľadiska to všetko sťažuje pochopenie kódu, ale skutočnosť, že každá hodnota je priradená iba raz, značne uľahčuje mnohé optimalizácie.
Všimnite si, že ak si napíšete vlastný kompilátor, zvyčajne sa nebudete musieť zaoberať takýmito vecami. Dokonca ani Clang negeneruje všetky tieto inštrukcie phi, používa mechanizmus alloca (pripomína to prácu s bežnými lokálnymi premennými). Potom, keď beží LLVM optimalizácia pass tzv , inštrukcie alloca prevedené do podoby SSA. TinyGo však prijíma vstup od Go SSA, ktorý je už pohodlne prevedený do formy SSA.
Ďalšou inováciou uvažovaného fragmentu medziľahlého kódu je, že prístup k prvkom segmentu podľa indexu je reprezentovaný vo forme operácie výpočtu adresy a operácie dereferencovania výsledného ukazovateľa. Tu môžete vidieť priame pridávanie konštánt do IR kódu (napríklad - 1:int). V príklade s funkciou myAdd toto nebolo použité. Teraz, keď máme tieto funkcie z cesty, poďme sa pozrieť na to, čím sa tento kód stane, keď sa prevedie na formu 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
}
Tu, ako predtým, môžeme vidieť rovnakú štruktúru, ktorá zahŕňa ďalšie syntaktické štruktúry. Napríklad pri hovoroch phi hodnoty a štítky sa vymenili. Je tu však niečo, čo stojí za to venovať osobitnú pozornosť.
Na začiatok tu môžete vidieť podpis úplne inej funkcie. LLVM nepodporuje rezy a výsledkom je optimalizácia, že kompilátor TinyGo, ktorý vygeneroval tento medzikód, rozdelil popis tejto dátovej štruktúry na časti. Mohlo by to predstavovať tri prvky rezu (ptr, len и cap) ako štruktúru (struct), ale ich reprezentácia ako tri samostatné entity umožňuje určité optimalizácie. Iné kompilátory môžu reprezentovať segment iným spôsobom, v závislosti od konvencií volania funkcií cieľovej platformy.
Ďalšou zaujímavou vlastnosťou tohto kódu je použitie inštrukcie getelementptr (často skracované ako GEP).
Táto inštrukcia pracuje s ukazovateľmi a používa sa na získanie ukazovateľa na prvok rezu. Porovnajme to napríklad s nasledujúcim kódom napísaným v C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Alebo s nasledujúcim ekvivalentom:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
Najdôležitejšia vec je, že pokyny getelementptr nevykonáva operácie dereferencovania. Len vypočíta nový ukazovateľ na základe existujúceho. Dá sa to brať ako návod mul и add na hardvérovej úrovni. Môžete si prečítať viac o pokynoch GEP .
Ďalšou zaujímavou vlastnosťou tohto prechodného kódu je použitie inštrukcie icmp. Toto je všeobecný pokyn používaný na implementáciu celočíselných porovnaní. Výsledkom tejto inštrukcie je vždy hodnota typu i1 — logická hodnota. V tomto prípade sa porovnanie vykoná pomocou kľúčového slova slt (so znamienkom menej ako), pretože porovnávame dve čísla predtým reprezentované typom int. Ak by sme porovnávali dve celé čísla bez znamienka, potom by sme použili icmpa kľúčové slovo použité v porovnaní by bolo ult. Na porovnanie čísel s pohyblivou rádovou čiarkou sa používa iná inštrukcia, fcmp, ktorý funguje podobným spôsobom.
Výsledky
Verím, že v tomto materiáli som pokryl najdôležitejšie vlastnosti LLVM IR. Samozrejme, je toho tu oveľa viac. Najmä prechodná reprezentácia kódu môže obsahovať veľa anotácií, ktoré umožňujú optimalizačné prechody, aby sa zohľadnili určité vlastnosti kódu známe kompilátoru, ktoré sa inak nedajú vyjadriť v IR. Toto je napríklad vlajka inbounds GEP inštrukcie alebo príznaky nsw и nuw, ktoré je možné pridať do návodu add. To isté platí pre kľúčové slovo private, čo naznačuje optimalizátorovi, že funkcia, ktorú označí, nebude odkazovaná z prostredia mimo aktuálnej kompilačnej jednotky. To umožňuje veľa zaujímavých interprocedurálnych optimalizácií, ako je eliminácia nepoužitých argumentov.
Viac o LLVM si môžete prečítať v , na ktorý sa budete často odvolávať pri vývoji vlastného kompilátora na báze LLVM. Tu , ktorá sa zaoberá vývojom kompilátora pre veľmi jednoduchý jazyk. Oba tieto zdroje informácií sa vám budú hodiť pri vytváraní vlastného kompilátora.
Vážení čitatelia! Používate LLVM?
Zdroj: hab.com