Dezvoltarea unui compilator este o sarcină foarte dificilă. Dar, din fericire, odată cu dezvoltarea unor proiecte precum LLVM, soluția la această problemă este mult simplificată, ceea ce permite chiar și unui singur programator să creeze un nou limbaj care este aproape ca performanță de C. Lucrul cu LLVM este complicat de faptul că acest sistemul este reprezentat de o cantitate imensă de cod, echipat cu puțină documentație. Pentru a încerca să corecteze această deficiență, autorul materialului, a cărui traducere o publicăm astăzi, va demonstra exemple de cod scris în Go și va arăta cum sunt traduse pentru prima dată în , și apoi în LLVM IR folosind compilatorul . Codul Go SSA și LLVM IR a fost ușor editat pentru a elimina lucrurile care nu sunt relevante pentru explicațiile date aici, pentru a face explicațiile mai ușor de înțeles.
Primul exemplu
Prima funcție pe care o voi privi aici este un mecanism simplu pentru adăugarea numerelor:
func myAdd(a, b int) int{
return a + b
}Această funcție este foarte simplă și, poate, nimic nu ar putea fi mai simplu. Se traduce în următorul cod Go SSA:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Cu această vizualizare, indicațiile de tip de date sunt plasate în dreapta și pot fi ignorate în majoritatea cazurilor.
Acest mic exemplu vă permite deja să vedeți esența unui aspect al SSA. Și anume, la conversia codului în formă SSA, fiecare expresie este împărțită în părțile cele mai elementare din care este compusă. În cazul nostru, comanda return a + b, de fapt, reprezintă două operații: adăugarea a două numere și returnarea rezultatului.
În plus, aici puteți vedea blocurile de bază ale programului; în acest cod există un singur bloc - blocul de intrare. Vom vorbi mai multe despre blocuri mai jos.
Codul Go SSA se convertește cu ușurință în LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Ceea ce puteți observa este că, deși aici sunt folosite structuri sintactice diferite, structura funcției este practic neschimbată. Codul LLVM IR este puțin mai puternic decât codul Go SSA, similar cu C. Aici, în declarația funcției, mai întâi există o descriere a tipului de date pe care îl returnează, tipul argumentului este indicat înaintea numelui argumentului. În plus, pentru a simplifica analiza IR, numele entităților globale sunt precedate de simbol @, iar înaintea numelor locale există un simbol % (o funcție este considerată și o entitate globală).
Un lucru de remarcat despre acest cod este că decizia de reprezentare a tipului lui Go int, care poate fi reprezentat ca o valoare de 32 sau 64 de biți, în funcție de compilator și ținta compilației, este acceptată atunci când LLVM generează codul IR. Acesta este unul dintre numeroasele motive pentru care codul LLVM IR nu este, așa cum cred mulți oameni, independent de platformă. Un astfel de cod, creat pentru o platformă, nu poate fi preluat și compilat pur și simplu pentru o altă platformă (cu excepția cazului în care sunteți potrivit pentru a rezolva această problemă ).
Un alt punct interesant de remarcat este că tipul i64 nu este un întreg cu semn: 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 nesemnate. În cazul reprezentării operației de adunare, acest lucru nu contează, deci nu există nicio diferență în lucrul cu numere semnate sau nesemnate. Aici aș dori să observ că în limbajul C, debordarea unei variabile întregi cu semne duce la un comportament nedefinit, astfel încât interfața Clang adaugă un steag la operație nsw (fără wrap semnat), care îi spune LLVM că poate presupune că adăugarea nu se revarsă niciodată.
Acest lucru poate fi important pentru unele optimizări. De exemplu, adăugarea a două valori i16 pe o platformă de 32 de biți (cu registre de 32 de biți) necesită, după adăugare, o operație de extindere a semnelor pentru a rămâne în raza de acțiune i16. Din această cauză, este adesea mai eficient să se efectueze operații cu numere întregi bazate pe dimensiunile registrului mașinii.
Ce se întâmplă în continuare cu acest cod IR nu ne interesează în mod deosebit acum. Codul este optimizat (dar în cazul unui exemplu simplu ca al nostru, nimic nu este optimizat) și apoi convertit în cod de mașină.
Al doilea exemplu
Următorul exemplu pe care îl vom analiza va fi puțin mai complicat. Și anume, vorbim despre o funcție care însumează o felie de numere întregi:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Acest cod se convertește î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 puteți vedea deja mai multe construcții tipice pentru reprezentarea codului în formularul SSA. Poate cea mai evidentă caracteristică a acestui cod este faptul că nu există comenzi structurate de control al fluxului. Pentru a controla fluxul de calcule, există doar salturi condiționate și necondiționate și, dacă considerăm această comandă ca o comandă de control al fluxului, o comandă de retur.
De fapt, aici puteți acorda atenție faptului că programul nu este împărțit în blocuri folosind acolade (ca în familia de limbaje C). Este împărțit pe etichete, care amintește de limbajele de asamblare și este prezentat sub formă de blocuri de bază. În SSA, blocurile de bază sunt definite ca secvențe adiacente de cod care încep cu o etichetă și se termină cu instrucțiuni de completare a blocurilor de bază, cum ar fi - return и jump.
Un alt detaliu interesant al acestui cod este reprezentat de instrucțiune phi. Instrucțiunile sunt destul de neobișnuite și poate dura ceva timp pentru a înțelege. sa nu uiti asta este prescurtarea pentru Static Single Assignment. Aceasta este o reprezentare intermediară a codului folosit de compilatori, în care fiecărei variabile i se atribuie o valoare o singură dată. Acest lucru este excelent pentru a exprima funcții simple precum funcția noastră myAddprezentat mai sus, dar nu este potrivit pentru funcții mai complexe, cum ar fi funcția discutată în această secțiune sum. În special, variabilele se modifică în timpul execuției buclei i и n.
SSA ocolește restricția privind atribuirea de valori variabile o dată, folosind așa-numita instrucțiune phi (numele lui este preluat din alfabetul grecesc). Cert este că, pentru ca reprezentarea SSA a codului să fie generată pentru limbaje precum C, trebuie să apelezi la câteva trucuri. Rezultatul apelării acestei instrucțiuni este valoarea curentă a variabilei (i sau n), și o listă de blocuri de bază este utilizată ca parametri. De exemplu, luați în considerare această instrucțiune:
t0 = phi [entry: 0:int, for.body: t6] #n
Sensul său este următorul: dacă blocul de bază anterior a fost un bloc entry (intrare), atunci t0 este o constantă 0, iar dacă blocul de bază anterior a fost for.body, atunci trebuie să luați valoarea t6 din acest bloc. Toate acestea pot părea destul de misterioase, dar acest mecanism este ceea ce face ca SSA să funcționeze. Dintr-o perspectivă umană, toate acestea fac codul dificil de înțeles, dar faptul că fiecare valoare este atribuită o singură dată face multe optimizări mult mai ușoare.
Rețineți că, dacă vă scrieți propriul compilator, de obicei nu va trebui să vă ocupați de acest tip de lucruri. Nici măcar Clang nu generează toate aceste instrucțiuni phi, folosește un mecanism alloca (seamănă cu lucrul cu variabile locale obișnuite). Apoi, atunci când rulați o trecere de optimizare LLVM numită , instrucțiuni alloca convertit la forma SSA. TinyGo, totuși, primește informații de la Go SSA, care, în mod convenabil, este deja convertită în forma SSA.
O altă inovație a fragmentului de cod intermediar luat în considerare este aceea că accesul la elementele slice prin index este reprezentat sub forma unei operații de calcul a adresei și a unei operații de dereferențiere a pointerului rezultat. Aici puteți vedea adăugarea directă a constantelor la codul IR (de exemplu - 1:int). În exemplul cu funcția myAdd acesta nu a fost folosit. Acum că am îndepărtat aceste funcții, să aruncăm o privire la ce devine acest cod atunci când este convertit în forma LLVM IR:
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
}
Aici, ca și înainte, putem vedea aceeași structură, care include și alte structuri sintactice. De exemplu, în apeluri phi valorile și etichetele schimbate. Cu toate acestea, există ceva aici căruia merită să-i acordăm o atenție deosebită.
Pentru început, aici puteți vedea o semnătură complet diferită a funcției. LLVM nu acceptă slice-uri și, ca urmare, ca o optimizare, compilatorul TinyGo care a generat acest cod intermediar a împărțit descrierea acestei structuri de date în părți. Ar putea reprezenta trei elemente de felie (ptr, len и cap) ca structură (struct), dar reprezentarea lor ca trei entități separate permite unele optimizări. Alți compilatori pot reprezenta felia în alte moduri, în funcție de convențiile de apelare ale funcțiilor platformei țintă.
O altă caracteristică interesantă a acestui cod este utilizarea instrucțiunii getelementptr (deseori prescurtat ca GEP).
Această instrucțiune funcționează cu pointeri și este folosită pentru a obține un pointer către un element slice. De exemplu, să-l comparăm cu următorul cod scris în C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Sau cu următorul echivalent cu acesta:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
Cel mai important lucru aici este că instrucțiunile getelementptr nu efectueaza operatii de dereferentiere. Doar calculează un nou indicator pe baza celui existent. Poate fi luat ca instrucțiuni mul и add la nivel hardware. Puteți citi mai multe despre instrucțiunile GEP .
O altă caracteristică interesantă a acestui cod intermediar este utilizarea instrucțiunii icmp. Aceasta este o instrucțiune de uz general folosită pentru a implementa comparații întregi. Rezultatul acestei instrucțiuni este întotdeauna o valoare de tip i1 - valoare logică. În acest caz, se face o comparație folosind cuvântul cheie slt (semnat mai puțin decât), deoarece comparăm două numere reprezentate anterior prin tip int. Dacă am compara două numere întregi fără semn, atunci am folosi icmp, iar cuvântul cheie folosit în comparație ar fi ult. Pentru a compara numerele în virgulă mobilă, se folosește o altă instrucțiune, fcmp, care funcționează într-un mod similar.
Rezultatele
Cred că în acest material am acoperit cele mai importante caracteristici ale LLVM IR. Desigur, aici sunt mult mai multe. În special, reprezentarea intermediară a codului poate conține multe adnotări care permit trecerilor de optimizare să ia în considerare anumite caracteristici ale codului cunoscute de compilator care nu pot fi exprimate altfel în IR. De exemplu, acesta este un steag inbounds Instrucțiuni GEP sau steaguri nsw и nuw, care poate fi adăugat la instrucțiuni add. Același lucru este valabil și pentru cuvântul cheie private, indicând optimizatorului că funcția pe care o marchează nu va fi referită din afara unității de compilare curente. Acest lucru permite o mulțime de optimizări interprocedurale interesante, cum ar fi eliminarea argumentelor neutilizate.
Puteți citi mai multe despre LLVM în , la care vă veți referi des când vă dezvoltați propriul compilator bazat pe LLVM. Aici , care urmărește dezvoltarea unui compilator pentru un limbaj foarte simplu. Ambele surse de informații vă vor fi utile atunci când vă creați propriul compilator.
Dragi cititori! Folosești LLVM?
Sursa: www.habr.com