Dezvoltarea unui compilator este o sarcină foarte dificilă. Dar, din fericire, cu dezvoltarea proiectelor precum LLVM, rezolvarea acestei probleme devine mult mai simplă, permițând chiar și unui programator izolat să creeze un nou limbaj, apropiat ca performanță de C. Lucrul cu LLVM este complicat de faptul că acest sistem este prezentat printr-un volum imens de cod, însoțit de o documentație limitată. Pentru a încerca să corecteze această deficiență, autorul materialului, al cărui traducere o publicăm astăzi, intenționează să demonstreze exemple de cod scris în Go și să arate cum acestea sunt traduse mai întâi în , iar apoi — în LLVM IR folosind compilatorul . Codul Go SSA și LLVM IR a fost ușor editat, fiind eliminate părțile care nu se referă la explicațiile prezentate aici, pentru a face aceste explicații mai clare.
Primul exemplu
Prima funcție pe care intenționez să o discut aici reprezintă un mecanism simplu pentru adunarea numerelor:
func myAdd(a, b int) int{
return a + b
}Această funcție este foarte simplă și, probabil, nu există nimic mai simplu. Ea se traduce în următorul cod Go SSA:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0În această reprezentare a funcției, sugestiile privind tipurile de date sunt plasate la dreapta, în majoritatea cazurilor, acestea pot fi ignorate.
Acest mic exemplu permite deja să vedem esența unuia dintre aspectele SSA. În anume, la transformarea codului în forma SSA, fiecare expresie este descompusă în cele mai elementare părți din care este compusă. În cazul nostru, comanda return a + b, de fapt, reprezintă două operații: adunarea a două numere și returnarea rezultatului.
În plus, aici se pot vedea și blocurile de bază ale programului, în acest cod există un singur bloc — blocul de intrare (entry block). Vom vorbi mai în detaliu despre blocuri mai jos.
Codul Go SSA se transformă ușor în LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
} Se poate observa că, deși se folosesc alte construcții sintactice, structura funcției nu s-a schimbat semnificativ. Codul LLVM IR este ușor mai puternic decât codul Go SSA și seamănă cu C. Aici, în declarația funcției, descrierea tipului de date returnat vine prima, iar tipul argumentului este specificat înainte de numele argumentului. În plus, pentru a simplifica parsarea IR, înaintea numelui entităților globale stă un simbol @, iar înaintea numelui entităților locale — un simbol % (funcția este, de asemenea, considerată o entitate globală).
Una dintre trăsăturile acestui cod, la care ar trebui să fiți atenți, este că decizia privind reprezentarea tipului Go int, care poate fi reprezentat printr-o valoare de 32 sau 64 de biți, în funcție de compilator și de scopul compilării, este luată în momentul creării codului LLVM IR. Aceasta este una din numeroasele motive pentru care codul LLVM IR nu este, așa cum cred mulți, independent de platformă. Un astfel de cod creat pentru o platformă nu poate fi pur și simplu preluat și compilat pentru o altă platformă (decât dacă nu ne ocupăm de rezolvarea acestei probleme ).
. Un alt aspect interesant de menționat este că tipul i64 nu este un număr întreg semnat: este neutru în ceea ce privește reprezentarea semnului numărului. În funcție de instrucțiune, acesta poate reprezenta atât numere semnate, cât și numere nesemnate. În ceea ce privește reprezentarea operației de adunare, acest lucru nu are relevanță, astfel încât nu există nicio diferență în manipularea numerelor semnate sau nesemnate. Aici merită menționat că, în limbajul C, depășirea capacității unei variabile întregi semnate duce la un comportament nedefinit, așa că frontend-ul Clang adaugă un semn la operație nsw (no signed wrap), care indică LLVM că poate presupune că, la adunare, nu va avea loc niciodată depășirea capacității.
Acest lucru poate fi important pentru unele optimizări. De exemplu, adunarea a două valori i16 pe o platformă de 32 de biți (cu registres de 32 de biți) necesită, după efectuarea adunării, o operație de extindere a semnului, pentru a rămâne în intervalul i16. Din acest motiv, adesea devine mai eficient să se efectueze operații întregi având în vedere dimensiunile registrului mașinii.
Ceea ce se întâmplă ulterior cu acest cod IR nu ne interesează prea mult în acest moment. Codul este optimizat (dar, în cazul unui exemplu atât de simplu cum este al nostru, nimic nu mai este optimizat), apoi este transformat în cod mașină.
Al doilea exemplu
Următorul exemplu pe care îl vom analiza va fi puțin mai complex. În special, este vorba despre o funcție care sumazează un slice de întregi:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Acest cod este transformat în următorul cod 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 t0Aici putem vedea deja mai multe construcții caracteristice pentru reprezentarea codului sub formă de SSA. Probabil cea mai evidentă trăsătură a acestui cod este faptul că nu există comenzi structurate de control al fluxului de execuție. Controlul fluxului de execuție este realizat doar prin salturi condiționate și necondiționate, iar, dacă considerăm că această comandă este o comandă de control al fluxului, comanda de întoarcere.
De fapt, se poate observa că programul nu este împărțit în blocuri folosind acolade (ca în limbajele din familia C). Este structurat prin etichete, ceea ce amintește de limbajele de asamblare, și este prezentat sub formă de blocuri de bază. În SSA, blocurile de bază sunt secvențe continue de cod care încep cu o etichetă și se termină cu instrucțiuni de terminare a blocului de bază, de exemplu — return și jump.
O altă detaliu interesant al acestui cod este instrucțiunea phi. Această instrucțiune este destul de neobișnuită, și poate dura ceva timp să te familiarizezi cu ea. Ține minte că — este un acronim pentru Static Single Assignment. Aceasta este o reprezentare intermediară a codului folosită de compilatoare, în care fiecărei variabile îi este atribuită o valoare o singură dată. Aceasta este ideală pentru a exprima funcții simple, precum funcția noastră myAdd, prezentată mai sus, dar nu este adecvată pentru funcții mai complexe — precum funcția discutată în această secțiune sum. În special, în timpul execuției unui ciclu, variabilele se schimbă i și n.
SSA ocolește restricția de a atribui valori variabilelor o singură dată folosind așa-numita instrucțiune phi (numele său provine din alfabetul grecesc). Problema este că pentru a putea forma o reprezentare SSA a codului pentru limbaje precum C, este necesar să se facă unele trucuri. Rezultatul apelului acestei instrucțiuni este valoarea curentă a variabilei (i sau n), iar ca parametru folosește o listă de blocuri de bază. De exemplu, să luăm o astfel de instrucțiune:
t0 = phi [entry: 0:int, for.body: t6] #n Sensul său este următorul: dacă blocul de bază anterior a fost blocul entry (de intrare), atunci t0 este o constantă 0, iar dacă blocul de bază anterior a fost for.body, atunci trebuie să se ia valoarea t6 din acest bloc. Totul poate părea destul de misterios, dar datorită acestui mecanism se garantează funcționarea SSA. Din punct de vedere uman, toate acestea complică înțelegerea codului, dar faptul că fiecare valoare este atribuită o singură dată simplifică semnificativ multe optimizări.
Observați că, dacă scrieți propriul compilator, de obicei nu trebuie să vă ocupați de astfel de lucruri. Chiar și Clang nu generează toate aceste instrucțiuni phi, folosește mecanismul alloca , (care seamănă cu lucrul cu variabile locale normale). Apoi, în timpul unei treceri de optimizare LLVM, numită , instrucțiunile alloca sunt transformate în forma SSA. TinyGo, însă, primește datele de intrare de la Go SSA, care, din câte se pare, sunt deja transformate în forma SSA.
O altă noutate a acestui fragment de cod intermediar este că accesul la elementele unui slice prin index este reprezentat sub forma unei operații de calcul al adresei și a unei operații de dereferire a pointerului obținut. Aici se pot vedea și adăugarea directă a constantelor în codul IR (de exemplu — 1:int). În exemplul cu funcția myAdd Deși nu s-au folosit astfel de lucruri. Acum, după ce am înțeles aceste particularități, să ne uităm la felul în care va arăta acest cod atunci când este transformat în forma LLVM IR:
define 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
} Aici, la fel ca înainte, putem vedea aceeași structură, care include alte construcții sintactice. De exemplu, în apelurile phi valorile și etichetele s-au schimbat între ele. Cu toate acestea, există și câteva lucruri asupra cărora merită să ne concentrăm.
Pentru început, aici se poate observa o semnătură a funcției complet diferită. LLVM nu suportă slice-uri; din această cauză, ca parte a optimizării, compilatorul TinyGo, care a generat acest cod intermediar, a împărțit descrierea acestei structuri de date în părți. Ar fi putut reprezenta cele trei elemente ale slice-ului (ptr, len și cap) sub forma unei structuri (struct), dar reprezentarea lor ca trei entități separate permite realizarea unor optimizări. Alte compilatoare ar putea prezenta slice-ul și în alte moduri, în funcție de convențiile de apelare ale platformei țintă.
O altă caracteristică interesantă a acestui cod este utilizarea instrucțiunii getelementptr (adesea prescurtată GEP).
Această instrucțiune operează cu pointere și este folosită pentru a obține un pointer către un element al slice-ului. De exemplu, să o comparăm cu următorul cod scris în C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Sau cu următoarea, echivalentă cu aceasta:
int* sliceptr(int *ptr, int index) {
return ptr + index;
} Cel mai important aici este că instrucțiunea getelementptr nu efectuează operații de dereferențiere. Ea doar calculează un nou pointer, bazându-se pe cel existent. Poate fi percepută ca instrucțiunea mul și add la nivel hardware. Detaliile despre instrucțiunea GEP pot fi citite .
O altă caracteristică interesantă a acestui cod intermediar constă în utilizarea instrucțiunii icmp. Aceasta este o instrucțiune de uz general utilizată pentru implementarea comparării numerelor întregi. Rezultatul executării acestei instrucțiuni este întotdeauna o valoare de tip i1 — valoare logică. În acest caz, compararea se realizează folosind cuvântul cheie slt (semnat mai puțin decât), deoarece comparăm două numere prezentate anterior de tip int. Dacă am fi comparat două numere întregi fără semn, atunci am fi folosit icmp, iar cuvântul cheie utilizat la comparare ar fi fost ult. Pentru compararea numerelor cu virgulă mobilă se folosește o altă instrucțiune, fcmp, care funcționează similar.
Concluzii
Consider că în acest material am abordat cele mai importante caracteristici ale LLVM IR. Sigur, există încă foarte multe aspecte. În special, în reprezentarea intermediară a codului pot exista numeroase anotări care permit optimizările să țină cont de anumite caracteristici ale codului, cunoscute de compilator, care nu pot fi exprimate în alt mod în IR. De exemplu, acesta este un flag inbounds al instrucțiunii GEP, sau flaguri nsw și nuw, care pot fi adăugate la instrucțiune add. Aceleași considerații se aplică și cuvântului cheie private, care semnalează optimizatorului că funcția marcată nu va fi referită din afara unității curente de compilare. Acest lucru permite realizarea multor optimizări interesante interprocedurale, cum ar fi eliminarea argumentelor neutilizate.
Detalii despre LLVM pot fi citite în , la care vei apela frecvent în dezvoltarea propriului tău compilator bazat pe LLVM. Iată , care abordează dezvoltarea unui compilator pentru un limbaj foarte simplu. Ambele aceste surse de informații îți vor fi utile în crearea propriului compilator.
Stimați cititori! Folosești LLVM?
Sursa: habr.com
