Å utvikle en kompilator er en veldig vanskelig oppgave. Men heldigvis, med utviklingen av prosjekter som LLVM, er løsningen på dette problemet betydelig forenklet, noe som gjør at selv en enkelt programmerer kan lage et nytt språk som er nær C i ytelse. Arbeid med LLVM er komplisert av det faktum at dette systemet er representert av en enorm mengde kode, utstyrt med lite dokumentasjon. For å prøve å rette opp denne mangelen, skal forfatteren av materialet, oversettelsen av som vi publiserer i dag, demonstrere eksempler på kode skrevet i Go og vise hvordan de først blir oversatt til , og deretter i LLVM IR ved å bruke kompilatoren . Go SSA og LLVM IR-koden er litt redigert for å fjerne ting som ikke er relevante for forklaringene gitt her, for å gjøre forklaringene mer forståelige.
Første eksempel
Den første funksjonen jeg skal se på her er en enkel mekanisme for å legge til tall:
func myAdd(a, b int) int{
return a + b
}Denne funksjonen er veldig enkel, og kanskje ingenting kan være enklere. Det oversettes til følgende Go SSA-kode:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Med denne visningen er datatypehintene plassert til høyre og kan ignoreres i de fleste tilfeller.
Dette lille eksemplet lar deg allerede se essensen av ett aspekt av SSA. Nemlig, når du konverterer kode til SSA-form, blir hvert uttrykk brutt ned i de mest elementære delene det er sammensatt av. I vårt tilfelle, kommandoen return a + b, faktisk representerer to operasjoner: å legge til to tall og returnere resultatet.
I tillegg kan du her se de grunnleggende blokkene til programmet; i denne koden er det bare en blokk - inngangsblokken. Vi snakker mer om blokker nedenfor.
Go SSA-koden konverteres enkelt til LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Det du kan legge merke til er at selv om det brukes forskjellige syntaktiske strukturer her, er strukturen til funksjonen i utgangspunktet uendret. LLVM IR-koden er litt sterkere enn Go SSA-koden, lik C. Her, i funksjonsdeklarasjonen, er det først en beskrivelse av datatypen den returnerer, argumenttypen er angitt før argumentnavnet. I tillegg, for å forenkle IR-parsing, er navnene på globale enheter innledet av symbolet @, og før lokale navn er det et symbol % (en funksjon regnes også som en global enhet).
En ting å merke seg om denne koden er at Gos type representasjonsbeslutning int, som kan representeres som en 32-biters eller 64-biters verdi, avhengig av kompilatoren og målet for kompileringen, aksepteres når LLVM genererer IR-koden. Dette er en av mange grunner til at LLVM IR-kode ikke er, som mange tror, plattformuavhengig. Slik kode, opprettet for én plattform, kan ikke bare tas og kompileres for en annen plattform (med mindre du er egnet til å løse dette problemet ).
Et annet interessant poeng verdt å merke seg er at typen i64 er ikke et fortegnet heltall: det er nøytralt når det gjelder å representere tegnet til tallet. Avhengig av instruksjonen kan den representere både signerte og usignerte tall. Når det gjelder representasjonen av addisjonsoperasjonen, spiller dette ingen rolle, så det er ingen forskjell på å jobbe med signerte eller usignerte tall. Her vil jeg merke at i C-språket fører overflyting av en signert heltallsvariabel til udefinert oppførsel, så Clang-grensesnittet legger til et flagg til operasjonen nsw (ingen signert omslag), som forteller LLVM at den kan anta at tillegg aldri renner over.
Dette kan være viktig for enkelte optimaliseringer. For eksempel å legge til to verdier i16 på en 32-bits plattform (med 32-bits registre) krever, etter tillegg, en tegnutvidelsesoperasjon for å forbli innenfor rekkevidde i16. På grunn av dette er det ofte mer effektivt å utføre heltallsoperasjoner basert på maskinregisterstørrelser.
Hva som skjer videre med denne IR-koden er ikke av spesiell interesse for oss nå. Koden er optimalisert (men i tilfellet med et enkelt eksempel som vårt, er ingenting optimalisert) og deretter konvertert til maskinkode.
Andre eksempel
Det neste eksemplet vi skal se på vil være litt mer komplisert. Vi snakker nemlig om en funksjon som summerer en del av heltall:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Denne koden konverteres til følgende Go SSA-kode:
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 t0Her kan du allerede se flere konstruksjoner som er typiske for å representere kode i SSA-skjemaet. Den kanskje mest åpenbare egenskapen til denne koden er det faktum at det ikke er noen strukturerte flytkontrollkommandoer. For å kontrollere flyten av beregninger er det bare betingede og ubetingede hopp, og hvis vi ser på denne kommandoen som en kommando for å kontrollere flyten, en returkommando.
Faktisk kan du her ta hensyn til det faktum at programmet ikke er delt inn i blokker ved å bruke krøllete bukseseler (som i C-familien av språk). Den er delt inn av etiketter, som minner om assembly-språk, og presenteres i form av grunnleggende blokker. I SSA er grunnleggende blokker definert som sammenhengende kodesekvenser som starter med en etikett og slutter med grunnleggende blokkfullføringsinstruksjoner, for eksempel − return и jump.
En annen interessant detalj i denne koden er representert av instruksjonen phi. Instruksjonene er ganske uvanlige og kan ta litt tid å forstå. Husk at er forkortelse for Static Single Assignment. Dette er en mellomrepresentasjon av koden som brukes av kompilatorer, der hver variabel kun tildeles en verdi én gang. Dette er flott for å uttrykke enkle funksjoner som funksjonen vår myAddvist ovenfor, men er ikke egnet for mer komplekse funksjoner som funksjonen diskutert i denne delen sum. Spesielt endres variabler under utførelsen av løkken i и n.
SSA omgår begrensningen med å tildele variabelverdier én gang ved hjelp av en såkalt instruksjon phi (navnet er hentet fra det greske alfabetet). Faktum er at for at SSA-representasjonen av kode skal genereres for språk som C, må du ty til noen triks. Resultatet av å kalle denne instruksjonen er gjeldende verdi av variabelen (i eller n), og en liste over grunnleggende blokker brukes som parametere. Tenk for eksempel på denne instruksjonen:
t0 = phi [entry: 0:int, for.body: t6] #n
Dens betydning er som følger: hvis den forrige grunnblokken var en blokk entry (inngang), da t0 er en konstant 0, og hvis den forrige grunnblokken var for.body, så må du ta verdien t6 fra denne blokken. Dette kan virke ganske mystisk, men denne mekanismen er det som får SSA til å fungere. Fra et menneskelig perspektiv gjør alt dette koden vanskelig å forstå, men det faktum at hver verdi kun tildeles én gang gjør mange optimaliseringer mye enklere.
Merk at hvis du skriver din egen kompilator, trenger du vanligvis ikke å forholde deg til denne typen ting. Selv Clang genererer ikke alle disse instruksjonene phi, den bruker en mekanisme alloca (det ligner å jobbe med vanlige lokale variabler). Deretter, når du kjører et LLVM-optimaliseringspass kalt , bruksanvisning alloca konvertert til SSA-form. TinyGo mottar imidlertid innspill fra Go SSA, som praktisk talt allerede er konvertert til SSA-form.
En annen nyvinning av fragmentet av mellomkode som vurderes, er at tilgang til skiveelementer ved indeks er representert i form av en operasjon for å beregne adressen og en operasjon for å avrefere den resulterende pekeren. Her kan du se direkte tillegg av konstanter til IR-koden (for eksempel - 1:int). I eksempelet med funksjonen myAdd denne er ikke brukt. Nå som vi har fått disse funksjonene ut av veien, la oss ta en titt på hva denne koden blir når den konverteres til LLVM IR-form:
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
}
Her kan vi som før se den samme strukturen, som inkluderer andre syntaktiske strukturer. For eksempel i samtaler phi verdier og etiketter byttet. Det er imidlertid noe her som er verdt å være spesielt oppmerksom på.
Til å begynne med kan du her se en helt annen funksjonssignatur. LLVM støtter ikke stykker, og som et resultat, som en optimalisering, delte TinyGo-kompilatoren som genererte denne mellomkoden beskrivelsen av denne datastrukturen i deler. Det kan representere tre skiveelementer (ptr, len и cap) som en struktur (struct), men å representere dem som tre separate enheter gir mulighet for noen optimaliseringer. Andre kompilatorer kan representere snittet på andre måter, avhengig av kallekonvensjonene til målplattformens funksjoner.
Et annet interessant trekk ved denne koden er bruken av instruksjonen getelementptr (ofte forkortet til GEP).
Denne instruksjonen fungerer med pekere og brukes til å få en peker til et skiveelement. La oss for eksempel sammenligne det med følgende kode skrevet i C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Eller med følgende tilsvarende til dette:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
Det viktigste her er at instruksjonene getelementptr utfører ikke derereferanseoperasjoner. Den beregner bare en ny peker basert på den eksisterende. Det kan tas som instruksjoner mul и add på maskinvarenivå. Du kan lese mer om GEP-instruksjonene .
Et annet interessant trekk ved denne mellomkoden er bruken av instruksjonen icmp. Dette er en generell instruksjon som brukes til å implementere heltallssammenligninger. Resultatet av å utføre denne instruksjonen er alltid en typeverdi i1 - logisk verdi. I dette tilfellet gjøres en sammenligning ved å bruke søkeordet slt (signert mindre enn), siden vi sammenligner to tall tidligere representert av typen int. Hvis vi sammenlignet to heltall uten fortegn, ville vi brukt icmp, og søkeordet som ble brukt i sammenligningen ville være ult. For å sammenligne tall med flyttall, brukes en annen instruksjon, fcmp, som fungerer på lignende måte.
Resultater av
Jeg tror at jeg i dette materialet har dekket de viktigste egenskapene til LLVM IR. Selvfølgelig er det mye mer her. Spesielt kan den mellomliggende representasjonen av koden inneholde mange merknader som tillater optimaliseringspasseringer for å ta hensyn til visse funksjoner i koden kjent for kompilatoren som ellers ikke kan uttrykkes i IR. Dette er for eksempel et flagg inbounds GEP-instruksjoner, eller flagg nsw и nuw, som kan legges til instruksjonene add. Det samme gjelder nøkkelordet private, som indikerer for optimalisereren at funksjonen den merker ikke vil bli referert fra utenfor gjeldende kompileringsenhet. Dette gir mulighet for mange interessante interprosessuelle optimaliseringer som å eliminere ubrukte argumenter.
Du kan lese mer om LLVM i , som du ofte vil referere til når du utvikler din egen LLVM-baserte kompilator. Her , som ser på å utvikle en kompilator for et veldig enkelt språk. Begge disse informasjonskildene vil være nyttige for deg når du lager din egen kompilator.
Kjære lesere! Bruker du LLVM?
Kilde: www.habr.com