At udvikle en compiler er en meget vanskelig opgave. Men heldigvis, med udviklingen af projekter som LLVM, er løsningen på dette problem meget forenklet, hvilket gør det muligt for selv en enkelt programmør at skabe et nyt sprog, der i ydeevne er tæt på C. Arbejdet med LLVM er kompliceret af det faktum, at dette systemet er repræsenteret af en enorm mængde kode, udstyret med lidt dokumentation. For at forsøge at rette op på denne mangel vil forfatteren af materialet, hvis oversættelse vi udgiver i dag, demonstrere eksempler på kode skrevet i Go og vise, hvordan de først er oversat til , og derefter i LLVM IR ved hjælp af compileren . Go SSA og LLVM IR-koden er blevet redigeret lidt for at fjerne ting, der ikke er relevante for forklaringerne her, for at gøre forklaringerne mere forståelige.
Første eksempel
Den første funktion, jeg skal se på her, er en simpel mekanisme til at tilføje tal:
func myAdd(a, b int) int{
return a + b
}Denne funktion er meget enkel, og måske kunne intet være enklere. Det oversættes til følgende Go SSA-kode:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Med denne visning placeres datatypetipsene til højre og kan ignoreres i de fleste tilfælde.
Dette lille eksempel giver dig allerede mulighed for at se essensen af et aspekt af SSA. Når kode konverteres til SSA-form, bliver hvert udtryk nemlig opdelt i de mest elementære dele, som det er sammensat af. I vores tilfælde kommandoen return a + b, faktisk repræsenterer to operationer: tilføjelse af to tal og returnering af resultatet.
Derudover kan du her se programmets grundlæggende blokke; i denne kode er der kun én blok - indtastningsblokken. Vi vil tale mere om blokke nedenfor.
Go SSA-koden konverteres nemt til LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Hvad du kan bemærke er, at selvom forskellige syntaktiske strukturer bruges her, er strukturen af funktionen stort set uændret. LLVM IR-koden er lidt stærkere end Go SSA-koden, svarende til C. Her i funktionsdeklarationen er der først en beskrivelse af den datatype den returnerer, argumenttypen er angivet før argumentnavnet. For at forenkle IR-parsing er navnene på globale enheder desuden foranstillet af symbolet @, og før lokale navne er der et symbol % (en funktion betragtes også som en global enhed).
En ting at bemærke ved denne kode er, at Go's type repræsentationsbeslutning int, som kan repræsenteres som en 32-bit eller 64-bit værdi, afhængigt af compileren og målet for kompileringen, accepteres, når LLVM genererer IR-koden. Dette er en af de mange grunde til, at LLVM IR-kode ikke, som mange mennesker tror, er platformsuafhængig. En sådan kode, der er oprettet til én platform, kan ikke blot tages og kompileres til en anden platform (medmindre du er egnet til at løse dette problem ).
Et andet interessant punkt, der er værd at bemærke, er, at typen i64 er ikke et heltal med fortegn: det er neutralt i forhold til at repræsentere tallets fortegn. Afhængigt af instruktionen kan den repræsentere både signerede og usignerede numre. I tilfælde af repræsentationen af additionsoperationen er dette ligegyldigt, så der er ingen forskel på at arbejde med fortegns- eller usignerede tal. Her vil jeg gerne bemærke, at i C-sproget fører overløb af en signeret heltalsvariabel til udefineret adfærd, så Clang-frontenden tilføjer et flag til operationen nsw (ingen signeret ombrydning), som fortæller LLVM, at den kan antage, at tilføjelse aldrig løber over.
Dette kan være vigtigt for nogle optimeringer. For eksempel at tilføje to værdier i16 på en 32-bit platform (med 32-bit registre) kræver, efter tilføjelse, en tegnudvidelsesoperation for at forblive inden for rækkevidde i16. På grund af dette er det ofte mere effektivt at udføre heltalsoperationer baseret på maskinregisterstørrelser.
Hvad der derefter sker med denne IR-kode er ikke af særlig interesse for os nu. Koden optimeres (men i tilfælde af et simpelt eksempel som vores, er intet optimeret) og konverteres derefter til maskinkode.
Andet eksempel
Det næste eksempel, vi vil se på, vil være lidt mere kompliceret. Vi taler nemlig om en funktion, der summerer et udsnit 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 du allerede se flere konstruktioner, der er typiske for at repræsentere kode i SSA-formularen. Måske det mest åbenlyse træk ved denne kode er det faktum, at der ikke er nogen strukturerede flowkontrolkommandoer. For at kontrollere flowet af beregninger er der kun betingede og ubetingede spring, og hvis vi betragter denne kommando som en kommando til at kontrollere flowet, en returkommando.
Faktisk kan du her være opmærksom på, at programmet ikke er opdelt i blokke ved hjælp af krøllede seler (som i C-familien af sprog). Det er opdelt af etiketter, der minder om assemblersprog, og præsenteret i form af grundlæggende blokke. I SSA defineres basisblokke som sammenhængende kodesekvenser, der starter med en etiket og slutter med grundlæggende blokudførelsesinstruktioner, såsom − return и jump.
En anden interessant detalje i denne kode er repræsenteret af instruktionen phi. Instruktionerne er ret usædvanlige og kan tage lidt tid at forstå. huske på, at er en forkortelse for Static Single Assignment. Dette er en mellemrepræsentation af den kode, der bruges af compilere, hvor hver variabel kun tildeles en værdi én gang. Dette er fantastisk til at udtrykke simple funktioner som vores funktion myAddvist ovenfor, men er ikke egnet til mere komplekse funktioner, såsom den funktion, der er beskrevet i dette afsnit sum. Især variabler ændres under udførelsen af løkken i и n.
SSA omgår begrænsningen for at tildele variable værdier én gang ved hjælp af en såkaldt instruktion phi (dets navn er taget fra det græske alfabet). Faktum er, at for at SSA-repræsentationen af kode kan genereres for sprog som C, skal du ty til nogle tricks. Resultatet af at kalde denne instruktion er den aktuelle værdi af variablen (i eller n), og en liste over grundlæggende blokke bruges som dens parametre. Overvej for eksempel denne instruktion:
t0 = phi [entry: 0:int, for.body: t6] #n
Dens betydning er som følger: hvis den forrige grundblok var en blok entry (input), så t0 er en konstant 0, og hvis den tidligere grundblok var for.body, så skal du tage værdien t6 fra denne blok. Dette kan alt sammen virke ret mystisk, men denne mekanisme er det, der får SSA til at fungere. Fra et menneskeligt perspektiv gør alt dette koden svær at forstå, men det faktum, at hver værdi kun tildeles én gang, gør mange optimeringer meget nemmere.
Bemærk, at hvis du skriver din egen compiler, vil du normalt ikke skulle beskæftige dig med denne slags ting. Selv Clang genererer ikke alle disse instruktioner phi, den bruger en mekanisme alloca (det minder om at arbejde med almindelige lokale variabler). Derefter, når du kører et LLVM-optimeringspas kaldet , instruktioner alloca konverteret til SSA-form. TinyGo modtager dog input fra Go SSA, som bekvemt allerede er konverteret til SSA-form.
En anden nyskabelse af fragmentet af mellemkode, der er under overvejelse, er, at adgang til udsnitselementer ved indeks er repræsenteret i form af en operation til at beregne adressen og en operation med at dereferere den resulterende pointer. Her kan du se den direkte tilføjelse af konstanter til IR-koden (f.eks. - 1:int). I eksemplet med funktionen myAdd dette er ikke blevet brugt. Nu hvor vi har fået disse funktioner af vejen, lad os tage et kig på, hvad denne kode bliver, 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 struktur, som omfatter andre syntaktiske strukturer. For eksempel i opkald phi værdier og etiketter byttet. Der er dog noget her, som er værd at være særlig opmærksom på.
Til at begynde med kan du her se en helt anden funktionssignatur. LLVM understøtter ikke udsnit, og som et resultat, som en optimering, opdelte TinyGo-kompileren, der genererede denne mellemkode, beskrivelsen af denne datastruktur i dele. Det kunne repræsentere tre udsnitselementer (ptr, len и cap) som en struktur (struct), men at repræsentere dem som tre separate entiteter giver mulighed for nogle optimeringer. Andre compilere kan repræsentere udsnittet på andre måder, afhængigt af kaldekonventionerne for målplatformens funktioner.
Et andet interessant træk ved denne kode er brugen af instruktionen getelementptr (ofte forkortet til GEP).
Denne instruktion arbejder med pointere og bruges til at få en pointer til et udsnitselement. Lad os for eksempel sammenligne det med følgende kode skrevet i C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Eller med følgende svarende til dette:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
Det vigtigste her er, at instruktionerne getelementptr udfører ikke dereferencing-operationer. Den beregner bare en ny pointer baseret på den eksisterende. Det kan tages som instruktioner mul и add på hardwareniveau. Du kan læse mere om GEP-vejledningen .
Et andet interessant træk ved denne mellemkode er brugen af instruktionen icmp. Dette er en generel instruktion, der bruges til at implementere heltalssammenligninger. Resultatet af denne instruktion er altid en typeværdi i1 - logisk værdi. I dette tilfælde foretages en sammenligning ved hjælp af søgeordet slt (underskrevet mindre end), da vi sammenligner to tal tidligere repræsenteret af typen int. Hvis vi sammenlignede to heltal uden fortegn, ville vi bruge icmp, og det søgeord, der blev brugt i sammenligningen ville være ult. For at sammenligne tal med flydende komma bruges en anden instruktion, fcmp, som fungerer på samme måde.
Resultaterne af
Jeg mener, at jeg i dette materiale har dækket de vigtigste funktioner i LLVM IR. Selvfølgelig er der meget mere her. Især kan den mellemliggende repræsentation af koden indeholde mange annotationer, der tillader optimeringsgennemgange for at tage hensyn til visse funktioner i koden, som er kendt af compileren, og som ellers ikke kan udtrykkes i IR. For eksempel er dette et flag inbounds GEP instruktioner eller flag nsw и nuw, som kan tilføjes til instruktionerne add. Det samme gælder for søgeordet private, hvilket indikerer over for optimeringsværktøjet, at den funktion, den markerer, ikke vil blive refereret uden for den aktuelle kompileringsenhed. Dette giver mulighed for en masse interessante interprocessuelle optimeringer som at eliminere ubrugte argumenter.
Du kan læse mere om LLVM i , som du ofte vil referere til, når du udvikler din egen LLVM-baserede compiler. Her , som ser på at udvikle en compiler til et meget simpelt sprog. Begge disse informationskilder vil være nyttige for dig, når du opretter din egen compiler.
Kære læsere! Bruger du LLVM?
Kilde: www.habr.com