Razvoj kompajlera je veoma težak zadatak. Ali, srećom, razvojem projekata poput LLVM-a, rješenje ovog problema je uvelike pojednostavljeno, što omogućava čak i jednom programeru da kreira novi jezik koji je po performansama blizak C. Rad sa LLVM-om je komplikovan činjenicom da je ovo sistem je predstavljen ogromnom količinom koda, opremljen sa malo dokumentacije. Kako bismo pokušali ispraviti ovaj nedostatak, autor materijala, čiji prijevod danas objavljujemo, će demonstrirati primjere koda napisanog u Go-u i pokazati kako se prvo prevode u , a zatim u LLVM IR koristeći kompajler . Go SSA i LLVM IR kod je malo izmijenjen kako bi se uklonile stvari koje nisu relevantne za ovdje data objašnjenja, kako bi objašnjenja bila razumljivija.
Prvi primer
Prva funkcija koju ću ovdje pogledati je jednostavan mehanizam za dodavanje brojeva:
func myAdd(a, b int) int{
return a + b
}Ova funkcija je 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 t0Sa ovim prikazom, nagoveštaji za tip podataka se postavljaju sa desne strane i mogu se zanemariti u većini slučajeva.
Ovaj mali primjer vam već omogućava da vidite suštinu jednog aspekta SSA. Naime, prilikom pretvaranja koda u SSA oblik, svaki izraz se razlaže na najelementarnije dijelove od kojih se sastoji. U našem slučaju, komanda return a + b, u stvari, predstavlja dvije operacije: zbrajanje dva broja i vraćanje rezultata.
Osim toga, ovdje možete vidjeti osnovne blokove programa; u ovom kodu postoji samo jedan blok - blok za unos. 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 imena argumenta. Osim toga, da bi se pojednostavilo IR raščlanjivanje, nazivima globalnih entiteta prethodi simbol @, a ispred lokalnih imena nalazi se simbol % (funkcija se takođe smatra globalnim entitetom).
Jedna stvar koju treba zapaziti u vezi sa ovim kodom je odluka o Go-ovoj odluci o predstavljanju tipa int, koji se može predstaviti kao 32-bitna ili 64-bitna vrijednost, ovisno o kompajleru i cilju kompilacije, prihvaća se kada LLVM generiše IR kod. Ovo je jedan od mnogih razloga zašto LLVM IR kod nije, kako mnogi misle, nezavisan od platforme. Takav kod, kreiran za jednu platformu, ne može se jednostavno uzeti i kompajlirati za drugu platformu (osim ako niste pogodni za rješavanje ovog problema ).
Još jedna zanimljiva stvar koju vrijedi napomenuti je da je tip i64 nije cijeli broj s predznakom: neutralan je u smislu predstavljanja predznaka broja. U zavisnosti od instrukcije, može predstavljati i potpisane i nepotpisane brojeve. U slučaju predstavljanja operacije sabiranja, to nije bitno, tako da nema razlike u radu sa brojevima s predznakom ili bez predznaka. Ovdje bih želio napomenuti da u jeziku C, prekoračenje varijable s predznakom cijelog broja dovodi do nedefiniranog ponašanja, tako da Clang frontend dodaje zastavicu operaciji nsw (bez potpisanog omota), što govori LLVM-u da može pretpostaviti da se sabiranje nikada ne prelije.
Ovo može biti važno za neke optimizacije. Na primjer, dodavanjem dvije vrijednosti i16 na 32-bitnoj platformi (sa 32-bitnim registrima) zahtijeva, nakon dodavanja, operaciju proširenja znaka kako bi ostao u dometu i16. Zbog toga je često efikasnije izvoditi cjelobrojne operacije na osnovu veličina registra mašine.
Ono što se dalje dešava sa ovim IR kodom nas sada ne zanima. Kod se optimizira (ali u slučaju jednostavnog primjera kao što je naš, ništa nije optimizirano) i zatim se konvertuje u mašinski kod.
Drugi primjer
Sljedeći primjer koji ćemo pogledati bit će malo složeniji. Naime, govorimo o funkciji koja sabira isječak cijelih brojeva:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Ovaj kod se 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 formi. Možda najočitija karakteristika ovog koda je činjenica da ne postoje strukturirane komande za kontrolu toka. Za kontrolu toka proračuna postoje samo uvjetni i bezuvjetni skokovi, a ako ovu naredbu smatramo naredbom za kontrolu toka, naredba za povratak.
Zapravo, ovdje možete obratiti pažnju na činjenicu da program nije podijeljen na blokove pomoću vitičastih zagrada (kao u C porodici jezika). Podijeljen je oznakama, koji podsjećaju na asemblerske jezike, i predstavljen u obliku osnovnih blokova. U SSA, osnovni blokovi su definirani kao neprekidni nizovi koda koji počinju oznakom i završavaju osnovnim uputama za završetak bloka, kao što je − return и jump.
Još jedan zanimljiv detalj ovog koda predstavlja instrukcija phi. Uputstva su prilično neobična i može potrajati neko vrijeme za razumijevanje. zapamtite da je skraćenica od Static Single Assignment. Ovo je srednji prikaz koda koji koriste kompajleri, u kojem se svakoj varijabli dodjeljuje vrijednost samo jednom. Ovo je sjajno za izražavanje jednostavnih funkcija poput naše funkcije myAddprikazano iznad, ali nije pogodno za složenije funkcije kao što je funkcija o kojoj se govori u ovom odjeljku sum. Konkretno, varijable se mijenjaju tokom izvršavanja petlje i и n.
SSA zaobilazi ograničenje dodjeljivanja vrijednosti varijabli jednom koristeći takozvanu instrukciju phi (ime je preuzeto iz grčkog alfabeta). Činjenica je da kako bi se SSA reprezentacija koda generirala za jezike poput C, morate pribjeći nekim trikovima. Rezultat pozivanja ove instrukcije je trenutna vrijednost varijable (i ili n), a kao njegovi parametri se koristi lista osnovnih blokova. Na primjer, razmotrite ovu instrukciju:
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, i ako je prethodni osnovni blok bio for.body, tada trebate uzeti vrijednost t6 iz ovog bloka. Sve ovo može izgledati prilično misteriozno, ali ovaj mehanizam je ono što čini da SSA funkcionira. Iz ljudske perspektive, sve ovo čini kod teško razumljivim, ali činjenica da se svaka vrijednost dodjeljuje samo jednom čini mnoge optimizacije mnogo lakšima.
Imajte na umu da ako pišete svoj kompajler, obično se nećete morati baviti ovakvim stvarima. Čak ni Clang ne generiše sva ova uputstva phi, koristi mehanizam alloca (liči na rad sa običnim lokalnim varijablama). Zatim, kada se izvodi LLVM optimizacija pass pozvan , instrukcije alloca pretvoren u SSA oblik. TinyGo, međutim, prima podatke od Go SSA, koji je, zgodno, već konvertovan u SSA oblik.
Još jedna inovacija fragmenta međukoda koji se razmatra je da je pristup elementima preseka po indeksu predstavljen u obliku operacije izračunavanja adrese i operacije dereferenciranja rezultujućeg pokazivača. Ovdje možete vidjeti direktno dodavanje konstanti IR kodu (na primjer - 1:int). U primjeru sa funkcijom myAdd ovo nije korišteno. Sada kada smo izbacili te karakteristike sa puta, pogledajmo šta ovaj kod postaje kada se konvertuje u LLVM IR oblik:
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. Međutim, ovdje postoji nešto na što vrijedi obratiti posebnu pažnju.
Za početak, ovdje možete vidjeti potpuno drugačiji potpis funkcije. LLVM ne podržava rezove, i kao rezultat toga, kao optimizacija, TinyGo kompajler koji je generisao ovaj međukod je podelio opis ove strukture podataka na delove. Može predstavljati tri elementa kriške (ptr, len и cap) kao struktura (struktura), ali njihovo predstavljanje kao tri odvojena entiteta omogućava neke optimizacije. Drugi prevodioci mogu predstavljati isečak na druge načine, u zavisnosti od konvencija pozivanja funkcija ciljne platforme.
Još jedna zanimljiva karakteristika ovog koda je korištenje instrukcije getelementptr (često skraćeno kao GEP).
Ova instrukcija radi sa pokazivačima i koristi se za dobijanje pokazivača na element slice. Na primjer, uporedimo ga sa sljedećim kodom napisanim u C:
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 osnovu postojećeg. Može se uzeti kao uputstvo mul и add na nivou hardvera. Možete pročitati više o GEP uputama .
Još jedna zanimljiva karakteristika ovog međukoda je korištenje instrukcije icmp. Ovo je instrukcija opće namjene koja se koristi za implementaciju poređenja cijelih brojeva. Rezultat izvršavanja ove instrukcije je uvijek vrijednost tipa i1 — logička vrijednost. U ovom slučaju, poređenje se vrši pomoću ključne riječi slt (potpisano manje od), pošto poredimo dva broja koja su prethodno bila predstavljena tipom int. Kada bismo uspoređivali dva neoznačena cijela broja, koristili bismo icmp, a ključna riječ korištena u poređenju bi bila ult. Za poređenje brojeva s pomičnim zarezom koristi se druga instrukcija, fcmp, koji radi na sličan način.
Ishodi
Vjerujem da sam u ovom materijalu pokrio najvažnije karakteristike LLVM IR. Naravno, ovdje ima još mnogo toga. Konkretno, posredni prikaz koda može sadržavati mnoge napomene koje omogućavaju optimizacijske prolaze kako bi se uzele u obzir određene karakteristike koda poznate kompajleru koje se drugačije ne mogu izraziti u IR. Na primjer, ovo je zastava inbounds GEP upute ili zastavice nsw и nuw, koji se može dodati uputstvima add. Isto važi i za ključnu reč private, što ukazuje optimizatoru da funkcija koju on označava neće biti referencirana izvan trenutne kompilacijske jedinice. Ovo omogućava mnogo zanimljivih međuproceduralnih optimizacija kao što je eliminisanje neiskorištenih argumenata.
Više o LLVM-u možete pročitati u , na koji ćete se često pozivati kada razvijate svoj vlastiti kompajler baziran na LLVM-u. Evo , koji se bavi razvojem kompajlera za vrlo jednostavan jezik. Oba ova izvora informacija bit će vam korisna kada kreirate vlastiti kompajler.
Dragi čitaoci! Koristite li LLVM?
izvor: www.habr.com