Razvijanje prevajalnika je zelo težka naloga. Toda na srečo je z razvojem projektov, kot je LLVM, rešitev tega problema zelo poenostavljena, kar omogoča, da celo en programer ustvari nov jezik, ki je po zmogljivosti blizu C. Delo z LLVM je zapleteno zaradi dejstva, da ta sistem predstavlja ogromna količina kode, opremljena z malo dokumentacije. Da bi poskusil popraviti to pomanjkljivost, bo avtor gradiva, katerega prevod objavljamo danes, prikazal primere kode, napisane v Go, in pokazal, kako se najprej prevedejo v , nato pa v LLVM IR z uporabo prevajalnika . Koda Go SSA in LLVM IR je bila nekoliko spremenjena, da se odstranijo stvari, ki niso pomembne za tukaj podane razlage, da bi bile razlage bolj razumljive.
Prvi primer
Prva funkcija, ki si jo bom tukaj ogledal, je preprost mehanizem za seštevanje števil:
func myAdd(a, b int) int{
return a + b
}Ta funkcija je zelo preprosta in morda nič ne bi moglo biti preprostejše. Prevede se v naslednjo kodo Go SSA:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0V tem pogledu so namigi o vrsti podatkov funkcije postavljeni na desno in jih je v večini primerov mogoče prezreti.
Ta majhen primer vam že omogoča, da vidite bistvo enega vidika SSA. Namreč, pri pretvorbi kode v SSA obliko se vsak izraz razdeli na najbolj elementarne dele, iz katerih je sestavljen. V našem primeru ukaz return a + b, pravzaprav predstavlja dve operaciji: seštevanje dveh števil in vrnitev rezultata.
Poleg tega si lahko tukaj ogledate osnovne bloke programa, v tej kodi je samo en blok - vstopni blok. Več o blokih bomo govorili spodaj.
Koda Go SSA se zlahka pretvori v LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Opazite lahko, da čeprav so tu uporabljene različne sintaktične strukture, je struktura funkcije v bistvu nespremenjena. Koda LLVM IR je nekoliko močnejša od kode Go SSA, podobna C. Tukaj je v deklaraciji funkcije najprej opis podatkovnega tipa, ki ga vrne, tip argumenta je naveden pred imenom argumenta. Poleg tega je za poenostavitev razčlenjevanja IR pred imeni globalnih entitet simbol @, pred krajevnimi imeni pa simbol % (funkcija se prav tako šteje za globalno entiteto).
Ena stvar, ki jo je treba omeniti pri tej kodi, je odločitev o predstavitvi tipa Go int, ki je lahko predstavljen kot 32-bitna ali 64-bitna vrednost, odvisno od prevajalnika in cilja prevajanja, je sprejet, ko LLVM ustvari kodo IR. To je eden od mnogih razlogov, da koda LLVM IR ni, kot mnogi mislijo, neodvisna od platforme. Takšne kode, ustvarjene za eno platformo, ni mogoče preprosto vzeti in prevesti za drugo platformo (razen če ste primerni za rešitev tega problema ).
Druga zanimiva točka, ki jo je treba omeniti, je, da vrsta i64 ni celo število s predznakom: je nevtralen v smislu predstavljanja predznaka števila. Odvisno od navodil lahko predstavlja predznačena in nepredznačena števila. V primeru predstavitve operacije seštevanja to ni pomembno, zato ni razlike pri delu s predznačenimi ali nepredznačenimi števili. Tukaj bi rad omenil, da v jeziku C prekoračitev celoštevilske spremenljivke s predznakom povzroči nedefinirano vedenje, zato vmesnik Clang operaciji doda zastavico nsw (no signed wrap), ki pove LLVM, da lahko domneva, da se dodajanje nikoli ne prelije.
To je lahko pomembno za nekatere optimizacije. Na primer seštevanje dveh vrednosti i16 na 32-bitni platformi (z 32-bitnimi registri) zahteva po dodajanju operacijo razširitve znaka, da ostane v območju i16. Zaradi tega je pogosto bolj učinkovito izvajati celoštevilske operacije na podlagi velikosti strojnih registrov.
Kaj bo potem s to IR kodo, nas zdaj ne zanima posebej. Koda je optimizirana (vendar v primeru preprostega primera, kot je naš, ni nič optimizirana) in nato pretvorjena v strojno kodo.
Drugi primer
Naslednji primer, ki si ga bomo ogledali, bo nekoliko bolj zapleten. Govorimo namreč o funkciji, ki sešteje rezino celih števil:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Ta koda se pretvori v naslednjo kodo 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 t0Tukaj že lahko vidite več konstrukcij, značilnih za predstavitev kode v obliki SSA. Morda najbolj očitna lastnost te kode je dejstvo, da ni strukturiranih ukazov za nadzor toka. Za krmiljenje poteka izračunov so na voljo le pogojni in brezpogojni skoki ter, če ta ukaz obravnavamo kot ukaz za nadzor poteka, povratni ukaz.
Pravzaprav ste tukaj lahko pozorni na dejstvo, da program ni razdeljen na bloke z zavitimi oklepaji (kot v družini jezikov C). Razdeljen je z oznakami, ki spominjajo na zbirne jezike, in predstavljen v obliki osnovnih blokov. V SSA so osnovni bloki definirani kot sosednja zaporedja kode, ki se začnejo z oznako in končajo z osnovnimi navodili za dokončanje bloka, kot je − return и jump.
Še eno zanimivo podrobnost te kode predstavlja navodilo phi. Navodila so precej nenavadna in lahko traja nekaj časa, da jih razumete. Zapomni si to je okrajšava za Static Single Assignment. To je vmesna predstavitev kode, ki jo uporabljajo prevajalniki, v kateri je vsaki spremenljivki dodeljena vrednost samo enkrat. To je super za izražanje preprostih funkcij, kot je naša funkcija myAddprikazan zgoraj, vendar ni primeren za bolj zapletene funkcije, kot je funkcija, obravnavana v tem razdelku sum. Zlasti spremenljivke se spreminjajo med izvajanjem zanke i и n.
SSA zaobide omejitev dodeljevanja vrednosti spremenljivk enkrat z uporabo tako imenovanega navodila phi (ime je vzeto iz grške abecede). Dejstvo je, da se morate za generiranje kode SSA za jezike, kot je C, zateči k nekaterim trikom. Rezultat klica tega ukaza je trenutna vrednost spremenljivke (i ali n), kot njeni parametri pa se uporablja seznam osnovnih blokov. Na primer, upoštevajte to navodilo:
t0 = phi [entry: 0:int, for.body: t6] #n
Njegov pomen je naslednji: če je bil prejšnji osnovni blok blok entry (vnos), potem t0 je stalnica 0, in če je bil prejšnji osnovni blok for.body, potem morate vzeti vrednost t6 iz tega bloka. Vse to se morda zdi precej skrivnostno, vendar je ta mehanizem tisto, zaradi česar SSA deluje. S človeškega vidika je zaradi vsega tega koda težko razumljiva, toda dejstvo, da je vsaka vrednost dodeljena samo enkrat, veliko olajša številne optimizacije.
Upoštevajte, da če pišete svoj prevajalnik, se vam običajno ne bo treba ukvarjati s tovrstnimi stvarmi. Tudi Clang ne ustvari vseh teh navodil phi, uporablja mehanizem alloca (podobno je delu z navadnimi lokalnimi spremenljivkami). Nato pri izvajanju klicanega prehoda za optimizacijo LLVM , navodila alloca pretvorjena v obliko SSA. TinyGo pa prejme vhodne podatke od Go SSA, ki je priročno že pretvorjen v obliko SSA.
Druga novost obravnavanega fragmenta vmesne kode je, da je dostop do elementov rezine po indeksu predstavljen v obliki operacije izračuna naslova in operacije dereferenciranja nastalega kazalca. Tukaj lahko vidite neposredno dodajanje konstant IR kodi (na primer - 1:int). V primeru s funkcijo myAdd to ni bilo uporabljeno. Zdaj, ko smo te funkcije odpravili, si poglejmo, kaj ta koda postane, ko jo pretvorimo v obliko 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
}
Tudi tukaj lahko vidimo enako strukturo, ki vključuje druge skladenjske strukture. Na primer v klicih phi vrednosti in oznake zamenjane. Vendar je tu nekaj, na kar je vredno biti še posebej pozoren.
Za začetek lahko vidite popolnoma drugačen podpis funkcije. LLVM ne podpira rezin, zato je prevajalnik TinyGo, ki je ustvaril to vmesno kodo, zaradi optimizacije razdelil opis te podatkovne strukture na dele. Lahko predstavlja elemente treh rezin (ptr, len и cap) kot strukturo (strukturo), vendar njihova predstavitev kot tri ločene entitete omogoča nekaj optimizacij. Drugi prevajalniki lahko predstavljajo rezino na druge načine, odvisno od klicnih konvencij funkcij ciljne platforme.
Druga zanimiva lastnost te kode je uporaba navodil getelementptr (pogosto okrajšano kot GEP).
To navodilo deluje s kazalci in se uporablja za pridobitev kazalca na element rezine. Na primer, primerjajmo ga z naslednjo kodo, napisano v C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Ali z naslednjim ekvivalentom tega:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
Najpomembnejše pri tem so navodila getelementptr ne izvaja operacij dereferenciranja. Samo izračuna nov kazalec na podlagi obstoječega. Lahko se vzame kot navodila mul и add na ravni strojne opreme. Več o navodilih GEP si lahko preberete .
Druga zanimiva lastnost te vmesne kode je uporaba navodil icmp. To je navodilo za splošni namen, ki se uporablja za izvajanje celoštevilskih primerjav. Rezultat tega ukaza je vedno vrednost tipa i1 — logična vrednost. V tem primeru se primerjava izvede s ključno besedo slt (s predznakom manj kot), saj primerjamo dve števili, ki ju je prej predstavljal tip int. Če bi primerjali dve celi števili brez predznaka, bi uporabili icmp, ključna beseda, uporabljena v primerjavi, pa bi bila ult. Za primerjavo števil s plavajočo vejico se uporablja drugo navodilo, fcmp, ki deluje na podoben način.
Rezultati
Menim, da sem v tem gradivu zajel najpomembnejše značilnosti LLVM IR. Seveda je tu še marsikaj. Zlasti lahko vmesna predstavitev kode vsebuje številne opombe, ki omogočajo prehodom optimizacije, da upoštevajo nekatere značilnosti kode, ki jih pozna prevajalnik in ki jih drugače ni mogoče izraziti v IR. Na primer, to je zastava inbounds GEP navodila ali zastavice nsw и nuw, ki jih lahko dodate k navodilom add. Enako velja za ključno besedo private, ki optimizatorju nakazuje, da se funkcija, ki jo označi, ne bo sklicevala zunaj trenutne prevajalske enote. To omogoča veliko zanimivih interproceduralnih optimizacij, kot je izločanje neuporabljenih argumentov.
Več o LLVM lahko preberete v , na katerega se boste pogosto sklicevali, ko boste razvijali lasten prevajalnik, ki temelji na LLVM. Tukaj , ki obravnava razvoj prevajalnika za zelo preprost jezik. Oba vira informacij vam bosta koristila pri ustvarjanju lastnega prevajalnika.
Drage bralke in bralci! Ali uporabljate LLVM?
Vir: www.habr.com