Udviklingen af en compiler er en meget vanskelig opgave. Men heldigvis med udviklingen af projekter som LLVM, bliver løsningen på denne opgave betydeligt lettere, hvilket gør det muligt for endda en enkelt programmerer at skabe et nyt sprog, der er tæt på C i ydeevne. Arbejdet med LLVM kompliceres af, at dette system er præsenteret med en enorm mængde kode, der er ledsaget af lidt dokumentation. For at forsøge at afhjælpe denne mangel vil forfatteren af materialet, hvis oversættelse vi offentliggør i dag, demonstrere kodeeksempler skrevet i Go og vise, hvordan de oversættes først til , og derefter - til LLVM IR ved hjælp af compileren . Koden i Go SSA og LLVM IR er blevet lidt redigeret for at fjerne det, der ikke vedrører de medfølgende forklaringer, så forklaringerne bliver mere forståelige.
Det første eksempel
Den første funktion, jeg vil gennemgå her, er en simpel mekanisme til at lægge tal sammen:
func myAdd(a, b int) int{
return a + b
}Denne funktion er meget simpel, og der er næppe noget mere enkelt. Den oversættes til følgende Go SSA-kode:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0I denne repræsentation af funktionen placeres datatypernes hints til højre, og i de fleste tilfælde kan man ignorere dem.
Dette lille eksempel giver allerede et indblik i essensen af et af aspekterne ved SSA. Det vil sige, at når koden omdannes til SSA-form, opdeles hvert udtryk i de mest elementære dele, som det består af. I vores tilfælde udtrykket return a + b, repræsenterer faktisk to operationer: lægning af to tal og returnering af resultatet.
Desuden kan man også se programmets grundlæggende blokke; i denne kode er der kun én blok - indgangsblokken (entry block). Vi vil tale mere om blokke senere.
Go SSA-koden kan nemt omdannes til LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
} Det kan bemærkes, at selvom der her bruges andre syntaktiske konstruktioner, er funktionen stort set uændret. LLVM IR-koden er lidt mere kompleks end Go SSA-koden og ligner C. Her, i funktionsdeklarationen, kommer beskrivelsen af den returnerede datatypes type først, og argumenttypen angives før argumentnavnet. Derudover, for at forenkle IR-parsingen, står der et symbol foran navne på globale entiteter, @, mens der foran navne på lokale entiteter står et symbol % (funktionen betragtes også som en global entitet).
En af de træk ved denne kode, som er værd at bemærke, er, at beslutningen om repræsentationen af Go-typen int, som kan repræsenteres som et 32-bit eller 64-bit værdi afhængigt af compileren og kompilationsformålet, træffes ved oprettelsen af LLVM IR-koden. Dette er en af mange grunde til, at LLVM IR-koden ikke er, som mange tror, platform-uafhængig. Sådan en kode, der er lavet til én platform, kan ikke blot tages og kompilere til en anden platform (medmindre man nærmer sig denne opgave ).
Endnu et interessant punkt, der skal nævnes, er, at typen i64 ikke er et heltal med fortegn: det er neutrale med hensyn til tallets fortegn. Afhængigt af instruktionen kan det repræsentere både tal med fortegn og tal uden fortegn. I tilfælde af repræsentationen af additionsoperationen spiller dette ingen rolle, så der er ingen forskel i arbejdet med tal med eller uden fortegn. Her bør det bemærkes, at i C fører overløb af et heltalsvariabel med fortegn til udefineret adfærd, hvorfor Clang-frontenden tilføjer et flag til operationen nsw (no signed wrap), der angiver til LLVM, at den kan antage, at der aldrig sker et overløb ved addition.
Dette kan være vigtigt for visse optimeringer. For eksempel kræver additionen af to værdier i16 på en 32-bit platform (med 32-bit registre) efter additionen en operation til fortegnsevner for at forblive inden for intervallet i16. Derfor er det ofte mere effektivt at udføre heltalsoperationer med hensyn til maskinens registerstørrelser.
Det, der sker med denne IR-kode bagefter, er ikke vores primære interesse lige nu. Koden bliver optimeret (men i tilfælde af et så simpelt eksempel som vores, bliver der ikke optimeret nogen ting), hvorefter den bliver konverteret til maskinkode.
Det andet eksempel
Det næste eksempel, vi vil se på, vil være lidt mere komplekst. Nærmere bestemt handler det om en funktion, der summerer et slice af heltal:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Denne kode 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 man allerede se flere konstruktioner, der er karakteristiske for kodepræsentation i SSA-form. Den mest åbenlyse egenskab ved denne kode er, at der ikke er strukturerede kontrolflow-instruktioner. Kontrolflowet styres kun af betingede og ubetingede spring, og hvis man betragter denne instruktion som en flowkontrolinstruktion, er instruktionen for at returnere.
Faktisk kan man bemærke, at programmet ikke er opdelt i blokke ved hjælp af krøllede parenteser (som i C-familien af sprog). Det er opdelt med etiketter, hvilket minder om assembler-sprog, og det præsenteres i form af basisblokke. I SSA kaldes basisblokke for kontinuerlige sekvenser af kode, der starter med en etiket og afsluttes med instruktioner, der fuldfører basisblokken, for eksempel — returner og jump.
En anden interessant detalje ved denne kode præsenteres af instruktionen phi. Denne instruktion er ganske usædvanlig, og det kan tage lidt tid at forstå den. Husk, at — dette er en forkortelse for Static Single Assignment. Det er en mellemliggende repræsentation af koden, der anvendes af compilere, hvor hver variabel kun tildeles en værdi én gang. Dette er ideelt til at udtrykke enkle funktioner, ligesom vores funktion myAdd, som vist ovenfor, men ikke velegnet til mere komplekse funktioner — ligesom den, der overvejes i dette afsnit sum. Specifikt ændres variablerne under udførelsen af en løkke i og n.
SSA omgår begrænsningen for én gang tildeling af variablernes værdier ved hjælp af den såkaldte instruktions phi (dens navn er afledt fra det græske alfabet). For at SSA-repræsentationen af koden kan dannes for sprog som C, må man ty til nogle tricks. Resultatet af at kalde denne instruktions udførelse er den nuværende værdi af variablen (i eller n), og som parametre anvendes en liste over grundlæggende blokke. Lad os for eksempel overveje en sådan instruks:
t0 = phi [entry: 0:int, for.body: t6] #n Dens betydning er som følger: hvis den forrige grundlæggende blok var blokken entry (indgang), så t0 er en konstant 0, men hvis den forrige grundlæggende blok var for.body, så skal værdien t6 tages fra denne blok. Alt dette kan virke temmelig mystisk, men denne mekanisme sikrer, at SSA fungerer. Fra et menneskeligt perspektiv komplicerer alt dette forståelsen af koden, men det faktum, at hver værdi kun tildeles én gang, forenkler mange optimeringer betydeligt.
Bemærk, at hvis du skriver din egen compiler, har du normalt ikke med sådanne ting at gøre. Selv Clang genererer ikke alle disse instruktioner phi, det bruger mekanismen alloca (det minder om arbejdet med almindelige lokale variabler). Derefter, under udførelsen af en optimeringsgennemgang i LLVM, kaldet , omdannes instruktionerne alloca til SSA-form. TinyGo modtager imidlertid input fra Go SSA, som, bekvemt, allerede er konverteret til SSA-form.
En anden nyhed i det betragtede fragment af den mellemliggende kode er, at adgangen til elementerne i en slice via indeks er repræsenteret som en adresseberegningsoperation og en dereferenceringsoperation af den resulterende pointer. Her kan man også se direkte tilføjelse af konstanter i IR-koden (for eksempel — 1:int). I eksemplet med funktionen myAdd Sådanne er ikke blevet brugt. Nu, efter at have forstået disse funktioner, lad os se, hvordan denne kode vil se ud, når den omdannes til LLVM IR-form:
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
} Her, som før, kan vi se den samme struktur, der inkluderer andre syntaktiske konstruktioner. For eksempel i kald: phi værdier og etiketter er blevet byttet om. Men der er også noget, som fortjener særlig opmærksomhed.
For det første kan vi se en helt anden funktionssignatur her. LLVM understøtter ikke slices, derfor, som en optimering, har kompilatoren TinyGo, som genererede denne mellemkode, delt beskrivelsen af denne datatypes struktur op. Den kunne have repræsenteret tre elementer i slice'et (ptr, len og cap) som en struktur (struct), men at repræsentere dem som tre separate enheder muliggør nogle optimeringer. Andre kompiler kan repræsentere et slice på en anden måde, det afhænger af funktionskaldsaftalerne for den målplatform.
En anden interessant funktion ved denne kode er brugen af instruktionen getelementptr (ofte kaldet GEP i forkortet form).
Denne instruktion arbejder med pointers og bruges til at få en pointer til et element i slice'et. For eksempel, lad os sammenligne den med følgende kode skrevet i C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Eller med følgende, som er ækvivalent:
int* sliceptr(int *ptr, int index) {
return ptr + index;
} Det vigtigste her er, at instruktionen getelementptr ikke udfører dereferenceringsoperationer. Den beregner blot en ny pointer baseret på den eksisterende. Den kan betragtes som instruktioner mul og add på hardware niveau. Du kan læse mere om GEP-instruktionen .
En anden interessant funktion ved denne mellemkode er brugen af instruktionen icmp. Dette er en generel instruktion, der anvendes til at implementere sammenligning af heltal. Resultatet af at udføre denne instruktion vil altid være en værdi af typen i1 — en boolsk værdi. I dette tilfælde sammenlignes der ved hjælp af nøgleordet slt (signed less than), da vi sammenligner to tal, der tidligere er præsenteret som typen int. Hvis vi havde sammenlignet to usignerede heltal, ville vi have brugt icmp, og nøgleordet, der anvendes ved sammenligning, ville have været ult. Til sammenligning af flydende punkt tal benyttes en anden instruktion, fcmp, som fungerer på en lignende måde.
Resumé
Jeg mener, at jeg i dette materiale har dækket de vigtigste funktioner ved LLVM IR. Selvfølgelig er der stadig meget mere. Især kan der i den mellemliggende repræsentation af koden være mange annotationer, der tillader at tage visse kodefunktioner i betragtning ved optimeringsgange, som er kendt for compileren, og som ikke kan udtrykkes på en anden måde i IR. For eksempel er dette flag inbounds for GEP-instruktionen, eller flagene nsw og nuw, som kan tilføjes til instruktionen add. Det samme gælder nøgleordet private, der angiver til optimizeren, at den markerede funktion ikke vil blive refereret udefra den aktuelle kompilationsenhed. Dette muliggør mange interessante interprocedurale optimeringer såsom eliminering af ubrugte argumenter.
Du kan læse mere om LLVM i , som du ofte vil henvise til, når du udvikler din egen compiler baseret på LLVM. Her er , som omhandler udviklingen af en compiler til et meget enkelt sprog. Begge disse kilder vil være nyttige for dig, når du skal skabe din egen compiler.
Kære læsere! Bruger du LLVM?
Kilde: habr.com
