Razvoj kompajlera je vrlo težak zadatak. No, srećom, s razvojem projekata poput LLVM, rješenje ovog problema postaje znatno jednostavnije, što omogućava čak i programeru samotnjaku da kreira novi jezik koji je po performansama blizak C-u. Rad s LLVM otežava to što je ovaj sustav predstavljen ogromnom količinom koda, uz malo dokumentacije. Kako bi pokušao ispraviti ovaj nedostatak, autor materijala čiji prijevod danas objavljujemo, namjerava demonstrirati primjere koda napisanog na Go-u i pokazati kako se oni prvo prevode u , a zatim — u LLVM IR koristeći kompajler . Kod Go SSA i LLVM IR je malo uredan, iz njega su uklonjeni dijelovi koji nisu povezani s objašnjenjima koja se ovdje daju, kako bi ta objašnjenja bila jasnija.
Prvi primjer
Prva funkcija koju planiram ovdje analizirati predstavlja jednostavan mehanizam za zbrajanje brojeva:
func myAdd(a, b int) int{
return a + b
}Ova funkcija je vrlo jednostavna, i vjerojatno ne postoji jednostavnija. Prevodi se u sljedeći kod Go SSA:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0U ovom predstavljanju funkcije, naznake tipova podataka se nalaze s desne strane, u većini slučajeva se na njih može ne obraćati pažnja.
Ovaj mali primjer već omogućava da vidimo suštinu jednog od aspekata SSA. Naime, prilikom prebacivanja koda u oblik SSA, svaki izraz se razbija na najsitnije dijelove od kojih se sastoji. U našem slučaju, naredba return a + b, zapravo predstavlja dvije operacije: zbrajanje dva broja i vraćanje rezultata.
Osim toga, ovdje se mogu vidjeti i osnovni blokovi programa, u ovom kodu postoji samo jedan blok — ulazni (entry block). O blokovima ćemo govoriti više u nastavku.
Kod Go SSA se lako pretvara u LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
} Može se primijetiti da, iako se ovdje koriste druge sintaktičke konstrukcije, struktura funkcije uglavnom nije promijenjena. LLVM IR kod je malo složeniji od Go SSA koda i sličan je C-u. Ovdje, u deklaraciji funkcije, prvo ide opis povratnog tipa podataka, dok se tip argumenta navodi prije imena argumenta. Osim toga, kako bi se olakšala IR parsiranje, ispred imena globalnih entiteta stoji simbol @, a ispred imena lokalnih — simbol % (funkcija se također smatra globalnim entitetom).
Jedna od značajki ovog koda, kojoj treba obratiti pažnju, jest da se odluka o predstavljanju tipa Go int, koji može biti predstavljen 32-bitnom ili 64-bitnom vrijednošću, ovisno o kompajleru i svrsi kompajliranja, donosi prilikom stvaranja LLVM IR koda. To je jedan od mnogih razloga zašto LLVM IR kod nije, kao što mnogi misle, platformno neovisan. Takav kod, stvoren za jednu platformu, ne može se jednostavno uzeti i kompajlirati za drugu platformu (osim ako se ne pristupi rješavanju ovog problema ).
Još jedna zanimljiva stvar koju treba primijetiti jest da tip i64 nije cijeli broj sa znakom: on je neutralan u pogledu predstavljanja znaka broja. Ovisno o instrukciji, može predstavljati i pozitivne i negativne brojeve. U slučaju predstavljanja operacije zbrajanja to ne igra ulogu, pa ovdje nema razlike u radu s brojevima sa znakom ili bez znaka. Ovdje treba napomenuti da u jeziku C prelivanje cijele brojne varijable sa znakom dovodi do neodređenog ponašanja, zbog čega frontend Clang dodaje oznaku nsw (no signed wrap), što signalizira LLVM-u da može pretpostaviti da se tijekom zbrajanja nikada ne događa prelivanje.
To može biti važno za neke optimizacije. Na primjer, zbrajanje dva vrijednosti i16 na 32-bitnoj platformi (s 32-bitnim registrima) zahtijeva, nakon izvršenja zbrajanja, operaciju proširenja znaka kako bi ostalo unutar raspona i16. Zbog toga je često učinkovitije izvesti cijele brojčane operacije uzimajući u obzir veličine registara u mašini.
Ono što se dalje događa s ovim IR-kodom trenutno nas ne zanima previše. Kod se optimizira (ali u slučaju tako jednostavnog primjera kao naš, ništa se više ne optimizira), a zatim se pretvara u strojni kod.
Drugi primjer
Sljedeći primjer koji ćemo razmotriti bit će malo složeniji. Naime, radi se o funkciji koja zbraja niz 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 se već može vidjeti više konstrukcija karakterističnih za predstavljanje koda u SSA formi. Najvjerojatnija očigledna karakteristika ovog koda je činjenica da ovdje nema strukturiranih naredbi za upravljanje tokom izvođenja. Za upravljanje tokom izvođenja ovdje postoje samo uvjetne i bezuvjetne skokove, a ako se ta naredba smatra naredbom za upravljanje tokom, tada je to naredba povratka.
Zapravo, ovdje se može primijetiti da program nije podijeljen na blokove korištenjem vitičastih zagrada (kao u jezicima obitelji C). Podijeljen je oznakama, što podsjeća na asemberske jezike, i predstavljen u obliku osnovnih blokova. U SSA osnovni blokovi su neprekidne sekvencije koda koje se započinju oznakom i završavaju instrukcijama koje završavaju osnovni blok, na primjer — return i jump.
Još jedan zanimljiv detalj ovog koda predstavljan je instrukcijom phi. Ova instrukcija je prilično neobična, može potrajati neko vrijeme da se s njom razjasni. Zapamtite da — je skraćenica za Static Single Assignment. To je intermedijarno predstavljanje koda koji koriste prevoditelji, u kojem se svakoj varijabli dodjeljuje vrijednost samo jednom. Ovo je odlično za izražavanje jednostavnih funkcija, poput naše funkcije myAdd, prikazane iznad, ali nije prikladno za složenije funkcije — poput one koja se razmatra u ovom odjeljku sum. Konkretno, tokom izvođenja petlje, varijable se mijenjaju. i i n.
SSA zaobilazi ograničenje jednog dodjeljivanja vrijednosti varijablama koristeći takozvanu instrukciju phi (njezino ime uzeto je iz grčkog alfabeta). Naime, da bi se SSA predstavljanje koda moglo oblikovati za jezike poput C, potrebno je koristiti neke trikove. Rezultat poziva ove instrukcije je trenutna vrijednost varijable (i ili n), a kao njezini parametri koristi se lista osnovnih blokova. Na primjer, razmotrite takvu instrukciju:
t0 = phi [entry: 0:int, for.body: t6] #n Njezin smisao je sljedeći: ako je prethodni osnovni blok bio blok entry (ulazni), tada je t0 — konstanta 0, a ako je prethodni osnovni blok bio for.body, tada treba uzeti vrijednost t6 iz ovog bloka. Sve to može izgledati prilično misteriozno, ali zahvaljujući ovom mehanizmu osigurava se rad SSA. Sa ljudske tačke gledišta, sve ovo otežava razumijevanje koda, ali činjenica da se svaka vrijednost dodjeljuje samo jednom znatno pojednostavljuje mnoge optimizacije.
Obratite pažnju na to da, ako pišete vlastiti prevoditelj, obično nećete imati posla s ovakvim stvarima. Čak ni Clang ne generira sve te instrukcije phi, koristi mehanizam alloca (podsjeća na rad s običnim lokalnim varijablama). Zatim, tokom izvođenja optimizacijskog prolaza LLVM, nazvanog , instrukcije alloca pretvaraju se u SSA formu. TinyGo, međutim, dobiva ulazne podatke od Go SSA, koji su, što je zgodno, već pretvoreni u SSA formu.
Još jedna novina razmatranog fragmenta intermedijarnog koda je to što je pristup elementima slice-a po indeksu predstavljen kao operacija izračunavanja adrese i operacija dereferenciranja dobijenog pokazivača. Ovdje se može vidjeti i neposredno dodavanje konstanti u IR-kod (na primjer — 1:int). U primjeru s funkcijom myAdd slična nije korištena. Sada, nakon što smo razjasnili te osobine, pogledajmo u što će se ovaj kod pretvoriti kada ga transformiramo u oblik LLVM IR:
definir i64 @sum(i64* %ptr, i64 %len, i64 p) {
entry:
br label %for.loop
for.loop: ; preds = %for.body, %entry
%0 = phi i64 [ 0, %entry ], [ %5, ref.next ]
%1 = phi i64 [ 0, %entry ], [ %6, ref.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 prethodno, možemo vidjeti istu strukturu, koja uključuje druge sintaktičke konstrukcije. Na primjer, u pozivima phi su se zamijenile vrijednosti i oznake. Međutim, ovdje postoji i nešto na što se posebno treba obratiti pažnja.
Prvo, ovdje možemo vidjeti potpuno drugačiji potpis funkcije. LLVM ne podržava slajseve, kao rezultat toga, kao optimizaciju, kompajler TinyGo, koji je stvorio ovaj međukôd, razdvojio je opis te strukture podataka na dijelove. Mogao bi predstaviti tri elementa slajsa (ptr, len i cap) u obliku strukture (struct), ali predstavljanje njih u obliku tri odvojene entiteta omogućava izvođenje nekih optimizacija. Drugi kompajleri mogu predstaviti slajs još nekako, to ovisi o konvencijama o pozivu funkcija ciljne platforme.
Još jedna zanimljiva osobina ovog koda je korištenje instrukcije getelementptr (često skraćeno nazvana GEP).
Ova instrukcija radi s pokazivačima i koristi se za dobivanje pokazivača na element slajsa. Na primjer, usporedimo je s sljedećim kodom napisanom u C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Ili s sljedećim, ekvivalentnim ovome:
int* sliceptr(int *ptr, int index) {
return ptr + index;
} Najvažnije ovdje je to što instrukcija getelementptr ne izvršava operacije dereferenciranja. Ona samo izračunava novi pokazivač, oslanjajući se na postojeći. Može se smatrati kao instrukcija mul i add na hardverskoj razini. Detalje o instrukciji GEP možete pročitati .
Još jedna zanimljiva osobina ovog međukôda je korištenje instrukcije icmp. To je opća uputa koja se koristi za usporedbu cijelih brojeva. Rezultat izvršavanja ove upute uvijek je vrijednost tipa i1 — logička vrijednost. U ovom slučaju se provodi usporedba koristeći ključnu riječ slt (signed less than), budući da uspoređujemo dva broja ranije predstavljena tipom int. Da smo uspoređivali dva cijela broja bez znaka, onda bismo koristili icmp, a ključna riječ koja se koristi za usporedbu bila bi ult. Za usporedbu brojeva s pomičnom decimalnom točkom koristi se druga uputa, fcmp, koja djeluje na sličan način.
Zaključci
Vjerujem da sam u ovom materijalu pokrio najvažnije značajke LLVM IR-a. Naravno, ovdje ima još mnogo toga. Konkretno, u međustepenom predstavljanju koda može postojati mnogo oznaka koje omogućuju uzimanje u obzir određenih značajki koda poznatih prevoditelju pri prolasku optimizacije, a koje se na drugi način ne mogu izraziti u IR-u. Na primjer, to je oznaka inbounds upute GEP, ili oznake nsw i nuw, koje se mogu dodati uputi add. Isto vrijedi i za ključnu riječ private, koja optimizatoru ukazuje da se na označenu funkciju ne može referencirati izvan trenutne jedinice kompilacije. To omogućava mnoge zanimljive optimizacije između procedura, poput uklanjanja neiskorištenih argumenata.
Detalje o LLVM-u možete pročitati u , koja će vam često biti od koristi pri razvoju vlastitog prevoditelja temeljenog na LLVM-u. Ovo je , koja se bavi razvojem prevoditelja za vrlo jednostavan jezik. Oba ova izvora informacija bit će vam korisna prilikom izrade vlastitog prevoditelja.
Dragi čitatelji! Koristite li LLVM?
Izvor: habr.com
