Desenvolupar un compilador és una tasca molt difícil. Però, afortunadament, amb el desenvolupament de projectes com LLVM, la solució a aquest problema es simplifica enormement, cosa que permet que fins i tot un sol programador creï un llenguatge nou que s'aproximi en rendiment al C. Treballar amb LLVM es complica pel fet que aquest El sistema està representat per una gran quantitat de codi, equipat amb poca documentació. Per intentar corregir aquesta mancança, l'autor del material, la traducció del qual publiquem avui, mostrarà exemples de codi escrits a Go i mostrarà com es tradueixen per primera vegada a , i després a LLVM IR mitjançant el compilador . El codi Go SSA i LLVM IR s'ha editat lleugerament per eliminar coses que no són rellevants per a les explicacions que es donen aquí, per tal de fer-les més entenedores.
Primer exemple
La primera funció que miraré aquí és un mecanisme senzill per afegir números:
func myAdd(a, b int) int{
return a + b
}Aquesta funció és molt senzilla i, potser, res més senzill. Es tradueix al següent codi Go SSA:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Amb aquesta vista, els suggeriments de tipus de dades es col·loquen a la dreta i es poden ignorar en la majoria dels casos.
Aquest petit exemple ja us permet veure l'essència d'un aspecte de SSA. És a dir, quan es converteix el codi en forma SSA, cada expressió es desglossa en les parts més elementals de les quals es compon. En el nostre cas, l'ordre return a + b, de fet, representa dues operacions: sumar dos nombres i retornar el resultat.
A més, aquí podeu veure els blocs bàsics del programa; en aquest codi només hi ha un bloc: el bloc d'entrada. A continuació parlarem més sobre els blocs.
El codi Go SSA es converteix fàcilment a LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
El que podeu observar és que, tot i que aquí s'utilitzen diferents estructures sintàctiques, l'estructura de la funció és bàsicament inalterada. El codi LLVM IR és una mica més fort que el codi Go SSA, similar al C. Aquí, a la declaració de la funció, primer hi ha una descripció del tipus de dades que retorna, el tipus d'argument s'indica abans del nom de l'argument. A més, per simplificar l'anàlisi IR, els noms de les entitats globals van precedits pel símbol @, i abans dels noms locals hi ha un símbol % (una funció també es considera una entitat global).
Una cosa a tenir en compte sobre aquest codi és que la decisió de representació del tipus de Go int, que es pot representar com un valor de 32 o 64 bits, segons el compilador i l'objectiu de la compilació, s'accepta quan LLVM genera el codi IR. Aquesta és una de les moltes raons per les quals el codi LLVM IR no és, com molta gent pensa, independent de la plataforma. Aquest codi, creat per a una plataforma, no es pot prendre i compilar simplement per a una altra plataforma (tret que sigui adequat per resoldre aquest problema ).
Un altre punt interessant a destacar és que el tipus i64 no és un nombre enter amb signe: és neutre pel que fa a representar el signe del nombre. Depenent de la instrucció, pot representar tant nombres signats com sense signe. En el cas de la representació de l'operació d'addició, això no importa, de manera que no hi ha cap diferència a l'hora de treballar amb nombres signats o sense signe. Aquí m'agradaria assenyalar que en el llenguatge C, el desbordament d'una variable entera amb signe condueix a un comportament no definit, de manera que la interfície Clang afegeix un indicador a l'operació. nsw (sense embolcall signat), que indica a LLVM que pot suposar que l'addició no es desborda mai.
Això pot ser important per a algunes optimitzacions. Per exemple, sumant dos valors i16 en una plataforma de 32 bits (amb registres de 32 bits) requereix, després d'afegir-ho, una operació d'expansió de signes per mantenir-se en el rang. i16. Per això, sovint és més eficient realitzar operacions senceres basades en les mides del registre de la màquina.
El que succeeixi després amb aquest codi IR ara no ens interessa especialment. El codi s'optimitza (però en el cas d'un exemple senzill com el nostre no s'optimitza res) i després es converteix en codi màquina.
Segon exemple
El següent exemple que veurem serà una mica més complicat. És a dir, estem parlant d'una funció que suma una porció de nombres enters:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Aquest codi es converteix en el següent codi 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 t0Aquí ja podeu veure més construccions típiques per representar codi en el formulari SSA. Potser la característica més òbvia d'aquest codi és el fet que no hi ha ordres de control de flux estructurat. Per controlar el flux de càlculs, només hi ha salts condicionals i incondicionals i, si considerem aquesta ordre com una ordre per controlar el flux, una ordre de retorn.
De fet, aquí podeu prestar atenció al fet que el programa no es divideix en blocs amb claus (com a la família de llenguatges C). Està dividit per etiquetes, que recorden els llenguatges assembladors, i es presenta en forma de blocs bàsics. A SSA, els blocs bàsics es defineixen com a seqüències de codi contigües que comencen amb una etiqueta i acaben amb instruccions bàsiques de finalització de blocs, com ara - return и jump.
Un altre detall interessant d'aquest codi està representat per la instrucció phi. Les instruccions són força inusuals i poden trigar un temps a comprendre-les. recorda que és l'abreviatura de Static Single Assignment. Aquesta és una representació intermèdia del codi utilitzat pels compiladors, en la qual a cada variable se li assigna un valor només una vegada. Això és ideal per expressar funcions simples com la nostra funció myAddmostrat més amunt, però no és adequat per a funcions més complexes com la funció que es parla en aquesta secció sum. En particular, les variables canvien durant l'execució del bucle i и n.
SSA passa per alt la restricció d'assignació de valors variables una vegada mitjançant l'anomenada instrucció phi (el seu nom prové de l'alfabet grec). El cas és que perquè la representació SSA del codi es generi per a llenguatges com C, cal recórrer a alguns trucs. El resultat de cridar aquesta instrucció és el valor actual de la variable (i o n), i s'utilitza una llista de blocs bàsics com a paràmetres. Per exemple, considereu aquesta instrucció:
t0 = phi [entry: 0:int, for.body: t6] #n
El seu significat és el següent: si el bloc bàsic anterior era un bloc entry (entrada), doncs t0 és una constant 0, i si el bloc bàsic anterior ho era for.body, llavors cal prendre el valor t6 d'aquest bloc. Tot això pot semblar força misteriós, però aquest mecanisme és el que fa que el SSA funcioni. Des d'una perspectiva humana, tot això fa que el codi sigui difícil d'entendre, però el fet que cada valor s'assigni només una vegada fa que moltes optimitzacions siguin molt més fàcils.
Tingueu en compte que si escriviu el vostre propi compilador, normalment no haureu de tractar amb aquest tipus de coses. Fins i tot Clang no genera totes aquestes instruccions phi, utilitza un mecanisme alloca (s'assembla a treballar amb variables locals ordinàries). Aleshores, quan s'executa una passada d'optimització LLVM cridada , instruccions alloca convertit al formulari SSA. TinyGo, però, rep aportacions de Go SSA, que, convenientment, ja està convertit al formulari SSA.
Una altra innovació del fragment de codi intermedi considerat és que l'accés als elements de tall per índex es representa en forma d'una operació de càlcul de l'adreça i una operació de desreferenciació del punter resultant. Aquí podeu veure l'addició directa de constants al codi IR (per exemple - 1:int). A l'exemple amb la funció myAdd això no s'ha utilitzat. Ara que tenim aquestes funcions fora del camí, mirem en què es converteix aquest codi quan es converteix al formulari 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
}
Aquí, com abans, podem veure la mateixa estructura, que inclou altres estructures sintàctiques. Per exemple, a les trucades phi valors i etiquetes intercanviades. Tanmateix, aquí hi ha alguna cosa a la qual val la pena prestar una atenció especial.
Per començar, aquí podeu veure una signatura de funció completament diferent. LLVM no admet slices i, com a resultat, com a optimització, el compilador TinyGo que va generar aquest codi intermedi va dividir la descripció d'aquesta estructura de dades en parts. Podria representar tres elements de tall (ptr, len и cap) com una estructura (estructura), però representar-les com a tres entitats separades permet algunes optimitzacions. Altres compiladors poden representar el segment d'altres maneres, depenent de les convencions de trucada de les funcions de la plataforma de destinació.
Una altra característica interessant d'aquest codi és l'ús de la instrucció getelementptr (sovint abreujat com a GEP).
Aquesta instrucció funciona amb punters i s'utilitza per obtenir un punter a un element de tall. Per exemple, comparem-lo amb el següent codi escrit en C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}O amb el següent equivalent a això:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
El més important aquí és que les instruccions getelementptr no realitza operacions de desreferenciació. Només calcula un punter nou basat en l'existent. Es pot prendre com a instruccions mul и add a nivell de maquinari. Podeu llegir més sobre les instruccions GEP .
Una altra característica interessant d'aquest codi intermedi és l'ús de la instrucció icmp. Aquesta és una instrucció de propòsit general que s'utilitza per implementar comparacions de nombres enters. El resultat d'aquesta instrucció és sempre un valor de tipus i1 - valor lògic. En aquest cas, es fa una comparació mitjançant la paraula clau slt (sign menys que), ja que estem comparant dos nombres representats anteriorment pel tipus int. Si comparéssim dos nombres enters sense signe, utilitzaríem icmp, i la paraula clau utilitzada a la comparació seria ult. Per comparar nombres de coma flotant, s'utilitza una altra instrucció, fcmp, que funciona de manera similar.
Resultats de
Crec que en aquest material he tractat les característiques més importants de LLVM IR. Per descomptat, aquí hi ha molt més. En particular, la representació intermèdia del codi pot contenir moltes anotacions que permeten que els passos d'optimització tinguin en compte determinades característiques del codi conegudes pel compilador que no es poden expressar d'una altra manera en IR. Per exemple, aquesta és una bandera inbounds Instruccions GEP o banderes nsw и nuw, que es pot afegir a les instruccions add. El mateix passa amb la paraula clau private, indicant a l'optimitzador que la funció que marca no es farà referència des de fora de la unitat de compilació actual. Això permet moltes optimitzacions interprocedimentals interessants com l'eliminació d'arguments no utilitzats.
Podeu llegir més sobre LLVM a , al qual us referireu sovint quan desenvolupeu el vostre propi compilador basat en LLVM. Aquí , que tracta de desenvolupar un compilador per a un llenguatge molt senzill. Ambdues fonts d'informació us seran útils a l'hora de crear el vostre propi compilador.
Benvolguts lectors! Esteu utilitzant LLVM?
Font: www.habr.com