Razvijanje prevoditelja vrlo je težak zadatak. Ali, na sreću, s razvojem projekata kao što je LLVM, rješenje ovog problema je uvelike pojednostavljeno, što čak i jednom programeru omogućuje stvaranje novog jezika koji je po performansama blizak C-u. Rad s LLVM-om kompliciran je činjenicom da ovaj sustav je predstavljen ogromnom količinom koda, opremljen s malo dokumentacije. Kako bi pokušao ispraviti ovaj nedostatak, autor materijala, čiji prijevod danas objavljujemo, demonstrirat će primjere koda napisanih u Go-u i pokazati kako se oni prvo prevode u , a zatim u LLVM IR pomoću kompajlera . Kod Go SSA i LLVM IR malo je uređen kako bi se uklonile stvari koje nisu relevantne za ovdje navedena objašnjenja, kako bi objašnjenja bila razumljivija.
Prvi primjer
Prva funkcija koju ću ovdje pogledati je jednostavan mehanizam za zbrajanje brojeva:
func myAdd(a, b int) int{
return a + b
}Ova je funkcija vrlo jednostavna i možda ništa ne može biti jednostavnije. Prevodi se u sljedeći Go SSA kod:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0U ovom prikazu, savjeti za vrstu podataka smješteni su s desne strane i u većini slučajeva mogu se zanemariti.
Ovaj mali primjer već vam omogućuje da vidite bit jednog aspekta SSA. Naime, kod pretvaranja koda u SSA oblik svaki izraz se rastavlja na najelementarnije dijelove od kojih se sastoji. U našem slučaju, naredba return a + b, zapravo, predstavlja dvije operacije: zbrajanje dvaju brojeva i vraćanje rezultata.
Osim toga, ovdje možete vidjeti osnovne blokove programa; u ovom kodu postoji samo jedan blok - ulazni blok. U nastavku ćemo govoriti više o blokovima.
Go SSA kod se lako pretvara u LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Ono što možete primijetiti je da iako se ovdje koriste različite sintaktičke strukture, struktura funkcije je u osnovi nepromijenjena. LLVM IR kod je malo jači od Go SSA koda, sličan C. Ovdje, u deklaraciji funkcije, prvo postoji opis tipa podataka koji vraća, tip argumenta je naznačen prije naziva argumenta. Nadalje, radi pojednostavljenja IR parsiranja, imenima globalnih entiteta prethodi simbol @, a ispred mjesnih imena stoji simbol % (funkcija se također smatra globalnim entitetom).
Jedna stvar koju treba primijetiti u vezi s ovim kodom je da Go-ova odluka o reprezentaciji tipa int, koji se može predstaviti kao 32-bitna ili 64-bitna vrijednost, ovisno o kompajleru i cilju kompilacije, prihvaća se kada se generira LLVM IR kod. Ovo je jedan od mnogih razloga zašto LLVM IR kod nije, kao što mnogi misle, neovisan o platformi. Takav kod, kreiran za jednu platformu, ne može se jednostavno uzeti i kompajlirati za drugu platformu (osim ako niste prikladni za rješavanje ovog problema ).
Još jedna zanimljiva točka vrijedna pažnje je da vrsta i64 nije cijeli broj s predznakom: neutralan je u smislu predstavljanja predznaka broja. Ovisno o uputama, može predstavljati brojeve s predznakom i bez predznaka. U slučaju prikaza operacije zbrajanja to nije bitno, pa nema razlike u radu s brojevima s predznakom i bez predznaka. Ovdje bih želio napomenuti da u jeziku C, prekoračenje varijable cijelog broja s predznakom dovodi do nedefiniranog ponašanja, tako da Clang sučelje dodaje oznaku operaciji nsw (no signed wrap), što govori LLVM-u da može pretpostaviti da se dodavanje nikada ne prelijeva.
Ovo može biti važno za neke optimizacije. Na primjer, zbrajanje dviju vrijednosti i16 na 32-bitnoj platformi (s 32-bitnim registrima) zahtijeva, nakon dodavanja, operaciju proširenja predznaka kako bi ostao u rasponu i16. Zbog toga je često učinkovitije izvoditi cjelobrojne operacije na temelju veličina registara stroja.
Što će se dalje dogoditi s ovim IR kodom, sada nas ne zanima posebno. Kod je optimiziran (ali u slučaju jednostavnog primjera kao što je naš, ništa nije optimizirano) i zatim pretvoren u strojni kod.
Drugi primjer
Sljedeći primjer koji ćemo pogledati bit će malo kompliciraniji. Naime, govorimo o funkciji koja zbraja odsječak cijelih brojeva:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Ovaj se kod pretvara u sljedeći 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 t0Ovdje već možete vidjeti više konstrukcija tipičnih za predstavljanje koda u SSA obliku. Možda je najočitija značajka ovog koda činjenica da ne postoje strukturirane naredbe za kontrolu toka. Za kontrolu tijeka izračuna postoje samo uvjetni i bezuvjetni skokovi, te, ako ovu naredbu smatramo naredbom za kontrolu tijeka, povratna naredba.
Zapravo, ovdje možete obratiti pozornost na činjenicu da program nije podijeljen u blokove pomoću vitičastih zagrada (kao u C obitelji jezika). Podijeljen je oznakama koje podsjećaju na asemblerske jezike i prikazan je u obliku osnovnih blokova. U SSA, osnovni blokovi su definirani kao kontinuirani nizovi koda koji počinju oznakom i završavaju osnovnim uputama za dovršetak bloka, kao što su − return и jump.
Još jedan zanimljiv detalj ovog koda predstavlja instrukcija phi. Upute su prilično neobične i može potrajati neko vrijeme za razumijevanje. Zapamti to je skraćenica za Static Single Assignment. Ovo je posredni prikaz koda koji koriste prevoditelji, u kojem se svakoj varijabli dodjeljuje vrijednost samo jednom. Ovo je izvrsno za izražavanje jednostavnih funkcija poput naše funkcije myAddprikazan gore, ali nije prikladan za složenije funkcije kao što je funkcija o kojoj se govori u ovom odjeljku sum. Konkretno, varijable se mijenjaju tijekom izvođenja petlje i и n.
SSA zaobilazi ograničenje dodjele vrijednosti varijable jednom pomoću takozvane instrukcije phi (ime mu je preuzeto iz grčkog alfabeta). Činjenica je da kako bi se SSA reprezentacija koda generirala za jezike kao što je C, morate pribjeći nekim trikovima. Rezultat poziva ove instrukcije je trenutna vrijednost varijable (i ili n), a kao njegovi parametri koristi se popis osnovnih blokova. Na primjer, razmotrite ovu uputu:
t0 = phi [entry: 0:int, for.body: t6] #n
Njegovo značenje je sljedeće: ako je prethodni osnovni blok bio blok entry (unos), zatim t0 je konstanta 0, a ako je prethodni osnovni blok bio for.body, tada trebate uzeti vrijednost t6 iz ovog bloka. Sve ovo može izgledati prilično tajanstveno, ali ovaj mehanizam čini SSA funkcioniranjem. Iz ljudske perspektive, sve to čini kôd teškim za razumijevanje, ali činjenica da se svaka vrijednost dodjeljuje samo jednom čini mnoge optimizacije mnogo lakšim.
Imajte na umu da ako napišete vlastiti kompilator, obično se nećete morati baviti ovakvim stvarima. Čak ni Clang ne generira sve te upute phi, koristi mehanizam alloca (nalikuje radu s običnim lokalnim varijablama). Zatim, prilikom pokretanja LLVM optimizacijskog prolaza pozvanog , upute alloca pretvoren u SSA oblik. TinyGo, međutim, prima unos od Go SSA, koji je, prikladno, već pretvoren u SSA oblik.
Još jedna inovacija fragmenta međukoda koji se razmatra je da je pristup elementima odsječka indeksom predstavljen u obliku operacije izračunavanja adrese i operacije dereferenciranja rezultirajućeg pokazivača. Ovdje možete vidjeti izravno dodavanje konstanti IR kodu (na primjer - 1:int). U primjeru s funkcijom myAdd ovo nije korišteno. Sada kada smo riješili te značajke, pogledajmo što ovaj kod postaje kada se pretvori u LLVM IR obrazac:
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
}
Ovdje, kao i prije, možemo vidjeti istu strukturu, koja uključuje i druge sintaktičke strukture. Na primjer, u pozivima phi vrijednosti i oznake zamijenjene. Ipak, ima tu nešto na što vrijedi obratiti posebnu pozornost.
Za početak, ovdje možete vidjeti potpuno drugačiji potpis funkcije. LLVM ne podržava odsječke, i kao rezultat toga, kao optimizacija, TinyGo kompajler koji je generirao ovaj međukod podijelio je opis ove strukture podataka u dijelove. Može predstavljati tri elementa odsječka (ptr, len и cap) kao strukturu (struct), ali njihovo predstavljanje kao tri odvojena entiteta dopušta neke optimizacije. Drugi prevoditelji mogu predstavljati odsječak na druge načine, ovisno o konvencijama pozivanja funkcija ciljne platforme.
Još jedna zanimljiva značajka ovog koda je korištenje instrukcija getelementptr (često skraćeno GEP).
Ova instrukcija radi s pokazivačima i koristi se za dobivanje pokazivača na element presjeka. Na primjer, usporedimo ga sa sljedećim kodom napisanim u C-u:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Ili sa sljedećim ekvivalentom ovome:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
Ovdje je najvažnije da su upute getelementptr ne izvodi operacije dereferenciranja. Samo izračunava novi pokazivač na temelju postojećeg. Može se uzeti kao instrukcija mul и add na hardverskoj razini. Možete pročitati više o GEP uputama .
Još jedna zanimljiva značajka ovog međukoda je korištenje instrukcija icmp. Ovo je instrukcija opće namjene koja se koristi za implementaciju cjelobrojnih usporedbi. Rezultat ove instrukcije uvijek je vrijednost tipa i1 — logična vrijednost. U ovom slučaju, usporedba se vrši pomoću ključne riječi slt (sa znakom manje od), budući da uspoređujemo dva broja prethodno predstavljena tipom int. Ako bismo uspoređivali dva cijela broja bez predznaka, koristili bismo icmp, a ključna riječ korištena u usporedbi bila bi ult. Za usporedbu brojeva s pomičnim zarezom koristi se druga instrukcija, fcmp, koji radi na sličan način.
Rezultati
Vjerujem da sam u ovom materijalu pokrio najvažnije značajke LLVM IR. Naravno, ovdje ima još puno toga. Konkretno, intermedijarni prikaz koda može sadržavati mnoge napomene koje omogućuju optimizacijske prolaze da uzmu u obzir određene značajke koda poznate kompajleru koje se inače ne mogu izraziti u IR. Na primjer, ovo je zastava inbounds GEP upute ili zastavice nsw и nuw, koji se mogu dodati uputama add. Isto vrijedi i za ključnu riječ private, naznačujući optimizatoru da funkcija koju označava neće biti referencirana izvan trenutne jedinice kompilacije. To omogućuje mnogo zanimljivih interproceduralnih optimizacija poput eliminacije neiskorištenih argumenata.
Više o LLVM možete pročitati u , na koji ćete se često pozivati kada razvijate vlastiti kompilator temeljen na LLVM-u. Ovdje , koji se bavi razvojem prevoditelja za vrlo jednostavan jezik. Oba ova izvora informacija bit će vam korisna pri izradi vlastitog prevoditelja.
Dragi čitatelji! Koristite li LLVM?
Izvor: www.habr.com