Sukurti kompiliatorių yra labai sudėtinga užduotis. Tačiau, laimei, kuriant tokius projektus kaip LLVM, šios problemos sprendimas labai supaprastėja, o tai leidžia net vienam programuotojui sukurti naują kalbą, kurios našumas yra artimas C. Darbą su LLVM apsunkina tai, kad Sistemą sudaro didžiulis kodo kiekis, aprūpintas mažai dokumentų. Siekdamas ištaisyti šį trūkumą, medžiagos, kurios vertimą šiandien skelbiame, autorius demonstruos Go parašyto kodo pavyzdžius ir parodys, kaip jie pirmą kartą išverčiami į
Pirmas pavyzdys
Pirmoji funkcija, kurią čia apžvelgsiu, yra paprastas skaičių pridėjimo mechanizmas:
func myAdd(a, b int) int{
return a + b
}
Ši funkcija yra labai paprasta ir, ko gero, niekas negali būti paprastesnis. Tai paverčiama tokiu „Go SSA“ kodu:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0
Šiame rodinyje duomenų tipo užuominos pateikiamos dešinėje ir daugeliu atvejų į jas galima nepaisyti.
Šis mažas pavyzdys jau leidžia pamatyti vieno SSA aspekto esmę. Būtent, konvertuojant kodą į SSA formą, kiekviena išraiška suskaidoma į elementariausias dalis, iš kurių ji susideda. Mūsų atveju komanda return a + b
, iš tikrųjų reiškia dvi operacijas: dviejų skaičių pridėjimą ir rezultato grąžinimą.
Be to, čia galite pamatyti pagrindinius programos blokus, šiame kode yra tik vienas blokas - įvesties blokas. Daugiau apie blokus kalbėsime toliau.
„Go SSA“ kodas lengvai konvertuojamas į LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Galima pastebėti, kad nors čia naudojamos skirtingos sintaksės struktūros, funkcijos struktūra iš esmės nesikeičia. LLVM IR kodas yra šiek tiek stipresnis nei Go SSA kodas, panašus į C. Čia funkcijos deklaracijoje pirmiausia pateikiamas jo grąžinamo duomenų tipo aprašymas, argumento tipas nurodomas prieš argumento pavadinimą. Be to, siekiant supaprastinti IR analizavimą, prieš pasaulinių objektų pavadinimus rašomas simbolis @
, o prieš vietinius pavadinimus yra simbolis %
(funkcija taip pat laikoma pasauliniu objektu).
Apie šį kodą reikia atkreipti dėmesį į tai, kad „Go“ tipo atstovavimo sprendimas int
, kuri gali būti vaizduojama kaip 32 bitų arba 64 bitų vertė, priklausomai nuo kompiliatoriaus ir kompiliavimo tikslo, priimama, kai LLVM generuoja IR kodą. Tai yra viena iš daugelio priežasčių, kodėl LLVM IR kodas nėra nepriklausomas nuo platformos, kaip daugelis galvoja. Tokio kodo, sukurto vienai platformai, negalima tiesiog paimti ir sukompiliuoti kitai platformai (nebent esate tinkamas šiai problemai išspręsti
Kitas įdomus dalykas, į kurį verta atkreipti dėmesį, yra tai, kad tipas i64
nėra sveikasis skaičius su ženklu: jis yra neutralus skaičiaus ženklo atstovavimo požiūriu. Priklausomai nuo instrukcijos, jis gali reikšti ir pasirašytus, ir be ženklų skaičius. Sudėjimo operacijos vaizdavimo atveju tai neturi reikšmės, todėl nėra jokio skirtumo dirbant su pasirašytais ar nepažymėtais skaičiais. Čia norėčiau atkreipti dėmesį į tai, kad C kalboje perpildžius sveikąjį kintamąjį su ženklu, atsiranda neapibrėžtas elgesys, todėl Clang priekinė programa prideda vėliavėlę prie operacijos nsw
(be pasirašyto įvyniojimo), kuris nurodo LLVM, kad gali daryti prielaidą, kad papildymas niekada neperpildytas.
Tai gali būti svarbu atliekant kai kuriuos optimizavimus. Pavyzdžiui, pridedant dvi reikšmes i16
32 bitų platformoje (su 32 bitų registrais) po pridėjimo reikalinga ženklo išplėtimo operacija, kad liktų diapazone i16
. Dėl šios priežasties dažnai efektyviau atlikti sveikųjų skaičių operacijas pagal mašinos registro dydžius.
Tai, kas nutiks toliau su šiuo IR kodu, dabar mūsų nelabai domina. Kodas optimizuojamas (tačiau tokio paprasto pavyzdžio kaip mūsų atveju niekas nėra optimizuojamas) ir tada konvertuojamas į mašininį kodą.
Antras pavyzdys
Kitas pavyzdys, kurį apžvelgsime, bus šiek tiek sudėtingesnis. Būtent, mes kalbame apie funkciją, kuri susumuoja sveikųjų skaičių dalį:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}
Šis kodas konvertuojamas į šį Go SSA kodą:
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 t0
Čia jau galite pamatyti daugiau konstrukcijų, būdingų kodo atvaizdavimui SSA formoje. Bene akivaizdžiausias šio kodo bruožas yra tai, kad nėra struktūrizuotų srauto valdymo komandų. Skaičiavimų srautui valdyti yra tik sąlyginiai ir besąlyginiai šuoliai, o jei šią komandą laikysime srauto valdymo komanda, grįžimo komanda.
Tiesą sakant, čia galite atkreipti dėmesį į tai, kad programa nėra suskirstyta į blokus naudojant lenktus skliaustus (kaip C kalbų šeimoje). Jis padalintas etiketėmis, primenančiomis asamblėjos kalbas ir pateikiamas pagrindinių blokų pavidalu. SSA pagrindiniai blokai apibrėžiami kaip gretimos kodo sekos, prasidedančios etikete ir baigiančios pagrindinėmis bloko užbaigimo instrukcijomis, pvz. return
и jump
.
Kita įdomi šio kodo detalė yra instrukcijoje phi
. Instrukcijos yra gana neįprastos ir gali užtrukti, kol ją suprasite. Prisiminti, kad myAdd
parodyta aukščiau, bet netinka sudėtingesnėms funkcijoms, tokioms kaip šiame skyriuje aptariama funkcija sum
. Visų pirma, kintamieji keičiasi ciklo vykdymo metu i
и n
.
SSA apeina kintamųjų reikšmių priskyrimo apribojimą vieną kartą naudojant vadinamąją instrukciją phi
(jo pavadinimas paimtas iš graikų abėcėlės). Faktas yra tas, kad norint, kad SSA kodas būtų sugeneruotas tokioms kalboms kaip C, turite imtis tam tikrų gudrybių. Šios instrukcijos iškvietimo rezultatas yra dabartinė kintamojo (i
arba n
), o kaip jo parametrai naudojamas pagrindinių blokų sąrašas. Pavyzdžiui, apsvarstykite šią instrukciją:
t0 = phi [entry: 0:int, for.body: t6] #n
Jo reikšmė tokia: jei ankstesnis pagrindinis blokas buvo blokas entry
(įvestis), tada t0
yra konstanta 0
, o jei ankstesnis pagrindinis blokas buvo for.body
, tada reikia paimti vertę t6
iš šio bloko. Visa tai gali atrodyti gana paslaptinga, tačiau dėl šio mechanizmo SSA veikia. Žmogaus požiūriu, visa tai apsunkina kodo supratimą, tačiau tai, kad kiekviena reikšmė priskiriama tik vieną kartą, daug lengviau optimizuoja.
Atminkite, kad jei rašote savo kompiliatorių, paprastai jums nereikės susidurti su tokiais dalykais. Net Clang nesukuria visų šių nurodymų phi
, jis naudoja mechanizmą alloca
(tai panašu į darbą su įprastais vietiniais kintamaisiais). Tada, kai vykdomas LLVM optimizavimo leidimas, vadinamas alloca
konvertuoti į SSA formą. Tačiau „TinyGo“ gauna įvestį iš „Go SSA“, kuri patogiai jau konvertuota į SSA formą.
Kita nagrinėjamo tarpinio kodo fragmento naujovė yra ta, kad prieiga prie pjūvio elementų pagal indeksą yra vaizduojama kaip adreso apskaičiavimo operacija ir gauto rodyklės nuorodos panaikinimo operacija. Čia galite pamatyti tiesioginį konstantų pridėjimą prie IR kodo (pavyzdžiui - 1:int
). Pavyzdyje su funkcija myAdd
tai nebuvo panaudota. Dabar, kai pašalinome šias funkcijas, pažiūrėkime, koks šis kodas tampa konvertavus į LLVM IR formą:
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
}
Čia, kaip ir anksčiau, matome tą pačią struktūrą, kuri apima ir kitas sintaksines struktūras. Pavyzdžiui, skambučiuose phi
vertės ir etiketės sukeistos. Tačiau čia yra kažkas, į ką verta atkreipti ypatingą dėmesį.
Pirmiausia čia galite pamatyti visiškai kitokį funkcijos parašą. LLVM nepalaiko skilčių, todėl optimizuojant TinyGo kompiliatorius, sugeneravęs šį tarpinį kodą, suskaidė šios duomenų struktūros aprašymą į dalis. Tai gali reikšti tris pjūvio elementus (ptr
, len
и cap
) kaip struktūrą (struktūrą), tačiau pateikiant jas kaip tris atskirus objektus, galima atlikti kai kuriuos optimizavimus. Kiti kompiliatoriai gali pavaizduoti skiltį kitais būdais, priklausomai nuo tikslinės platformos funkcijų iškvietimo susitarimų.
Kita įdomi šio kodo savybė yra instrukcijos naudojimas getelementptr
(dažnai sutrumpintas kaip GEP).
Ši instrukcija veikia su rodyklėmis ir naudojama norint gauti žymeklį į pjūvio elementą. Pavyzdžiui, palyginkime jį su šiuo kodu, parašytu C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}
Arba su šiuo ekvivalentu:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
Svarbiausia čia yra instrukcijos getelementptr
neatlieka nuorodų panaikinimo operacijų. Jis tiesiog apskaičiuoja naują žymeklį pagal esamą. Jis gali būti priimtas kaip instrukcija mul
и add
aparatūros lygiu. Daugiau apie GEP instrukcijas galite perskaityti
Kita įdomi šio tarpinio kodo savybė yra instrukcijos naudojimas icmp
. Tai bendros paskirties instrukcija, naudojama sveikųjų skaičių palyginimui įgyvendinti. Šios instrukcijos rezultatas visada yra tipo reikšmė i1
- loginė vertė. Šiuo atveju palyginimas atliekamas naudojant raktinį žodį slt
(pasirašyta mažiau nei), nes lyginame du skaičius, anksčiau pažymėtus tipu int
. Jei lygintume du beženklius sveikuosius skaičius, naudotume icmp
, o palyginime naudojamas raktinis žodis būtų ult
. Slankaus kablelio skaičiams palyginti naudojama kita instrukcija, fcmp
, kuris veikia panašiai.
rezultatai
Manau, kad šioje medžiagoje aprašiau svarbiausias LLVM IR savybes. Žinoma, čia yra daug daugiau. Visų pirma, tarpiniame kodo atvaizde gali būti daug anotacijų, leidžiančių optimizuoti, kad būtų atsižvelgta į tam tikras kompiliatoriui žinomas kodo ypatybes, kurių kitaip negalima išreikšti IR. Pavyzdžiui, tai vėliava inbounds
GEP instrukcijos arba vėliavėlės nsw
и nuw
, kurį galima pridėti prie instrukcijų add
. Tas pats pasakytina apie raktinį žodį private
, nurodant optimizuotojui, kad jo pažymėta funkcija nebus nuorodos iš dabartinio kompiliavimo vieneto ribų. Tai leidžia atlikti daug įdomių tarpprocedūrinių optimizacijų, pavyzdžiui, pašalinti nepanaudotus argumentus.
Daugiau apie LLVM galite perskaityti
Mieli skaitytojai! Ar naudojate LLVM?
Šaltinis: www.habr.com