Att utveckla en kompilator är en mycket svår uppgift. Men lyckligtvis, med utvecklingen av projekt som LLVM, är lösningen på detta problem avsevärt förenklad, vilket gör att även en enda programmerare kan skapa ett nytt språk som är nära C i prestanda. Att arbeta med LLVM kompliceras av det faktum att detta systemet representeras av en enorm mängd kod, utrustad med lite dokumentation. För att försöka rätta till denna brist kommer författaren till materialet, vars översättning vi publicerar idag, visa exempel på kod skriven i Go och visa hur de först översätts till , och sedan i LLVM IR med hjälp av kompilatorn . Go SSA och LLVM IR-koden har redigerats något för att ta bort saker som inte är relevanta för förklaringarna som ges här, för att göra förklaringarna mer begripliga.
Första exemplet
Den första funktionen jag ska titta på här är en enkel mekanism för att lägga till tal:
func myAdd(a, b int) int{
return a + b
}Den här funktionen är väldigt enkel, och kanske kan ingenting vara enklare. Det översätts till följande Go SSA-kod:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Med denna vy placeras datatyptipsen till höger och kan ignoreras i de flesta fall.
Detta lilla exempel låter dig redan se essensen av en aspekt av SSA. När man konverterar kod till SSA-form bryts nämligen varje uttryck ner i de mest elementära delarna som det består av. I vårt fall kommandot return a + b, i själva verket representerar två operationer: att lägga till två siffror och returnera resultatet.
Dessutom kan du här se grundblocken i programmet; i denna kod finns det bara ett block - ingångsblocket. Vi kommer att prata mer om block nedan.
Go SSA-koden konverteras enkelt till LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Vad du kan lägga märke till är att även om olika syntaktiska strukturer används här är strukturen på funktionen i princip oförändrad. LLVM IR-koden är lite starkare än Go SSA-koden, liknande C. Här, i funktionsdeklarationen, finns först en beskrivning av datatypen den returnerar, argumenttypen indikeras före argumentnamnet. Dessutom, för att förenkla IR-analys, föregås namnen på globala enheter av symbolen @, och före lokala namn finns det en symbol % (en funktion anses också vara en global enhet).
En sak att notera om den här koden är att Gos typrepresentationsbeslut int, som kan representeras som ett 32-bitars eller 64-bitars värde, beroende på kompilatorn och målet för kompileringen, accepteras när LLVM genererar IR-koden. Detta är en av många anledningar till att LLVM IR-kod inte är, som många tror, plattformsoberoende. Sådan kod, skapad för en plattform, kan inte helt enkelt tas och kompileras för en annan plattform (såvida du inte är lämplig för att lösa detta problem ).
En annan intressant punkt värd att notera är att typen i64 är inte ett heltal med tecken: det är neutralt när det gäller att representera talets tecken. Beroende på instruktionen kan den representera både signerade och osignerade nummer. När det gäller representationen av additionsoperationen spelar detta ingen roll, så det är ingen skillnad i att arbeta med signerade eller osignerade nummer. Här skulle jag vilja notera att i C-språket leder överfyllning av en signerad heltalsvariabel till odefinierat beteende, så Clang-gränssnittet lägger till en flagga till operationen nsw (ingen signerad wrap), som säger till LLVM att man kan anta att tillägg aldrig svämmar över.
Detta kan vara viktigt för vissa optimeringar. Till exempel att lägga till två värden i16 på en 32-bitars plattform (med 32-bitars register) kräver, efter tillägg, en teckenexpansionsoperation för att förbli inom räckvidd i16. På grund av detta är det ofta mer effektivt att utföra heltalsoperationer baserat på maskinregisterstorlekar.
Vad som händer sedan med den här IR-koden är inte av särskilt intresse för oss nu. Koden optimeras (men i fallet med ett enkelt exempel som vårt optimeras ingenting) och omvandlas sedan till maskinkod.
Andra exemplet
Nästa exempel vi ska titta på kommer att vara lite mer komplicerat. Vi pratar nämligen om en funktion som summerar en del av heltal:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Denna kod konverteras till följande Go SSA-kod:
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 t0Här kan du redan se fler konstruktioner som är typiska för att representera kod i SSA-formuläret. Den kanske mest uppenbara egenskapen hos denna kod är det faktum att det inte finns några strukturerade flödeskontrollkommandon. För att kontrollera flödet av beräkningar finns det bara villkorade och ovillkorliga hopp, och om vi betraktar detta kommando som ett kommando för att styra flödet, ett returkommando.
Faktum är att här kan du vara uppmärksam på det faktum att programmet inte är uppdelat i block med lockiga hängslen (som i C-familjen av språk). Den är uppdelad av etiketter, som påminner om assemblerspråk, och presenteras i form av grundläggande block. I SSA definieras grundläggande block som sammanhängande kodsekvenser som börjar med en etikett och slutar med grundläggande blockkompletterande instruktioner, som − return и jump.
En annan intressant detalj i denna kod representeras av instruktionen phi. Instruktionerna är ganska ovanliga och kan ta lite tid att förstå. kom ihåg det är en förkortning för Static Single Assignment. Detta är en mellanrepresentation av koden som används av kompilatorer, där varje variabel endast tilldelas ett värde en gång. Detta är bra för att uttrycka enkla funktioner som vår funktion myAddvisas ovan, men är inte lämplig för mer komplexa funktioner som funktionen som diskuteras i det här avsnittet sum. I synnerhet ändras variabler under exekveringen av slingan i и n.
SSA går förbi begränsningen att tilldela variabelvärden en gång med hjälp av en så kallad instruktion phi (dess namn är hämtat från det grekiska alfabetet). Faktum är att för att SSA-representationen av kod ska genereras för språk som C måste du ta till några knep. Resultatet av att anropa denna instruktion är det aktuella värdet av variabeln (i eller n), och en lista över grundläggande block används som dess parametrar. Tänk till exempel på den här instruktionen:
t0 = phi [entry: 0:int, for.body: t6] #n
Dess betydelse är följande: om det föregående grundblocket var ett block entry (ingång), alltså t0 är en konstant 0, och om det föregående grundblocket var for.body, då måste du ta värdet t6 från detta block. Detta kan allt verka ganska mystiskt, men det är denna mekanism som gör att SSA fungerar. Ur ett mänskligt perspektiv gör allt detta koden svår att förstå, men det faktum att varje värde bara tilldelas en gång gör många optimeringar mycket enklare.
Observera att om du skriver din egen kompilator behöver du vanligtvis inte ta itu med den här typen av saker. Inte ens Clang genererar alla dessa instruktioner phi, den använder en mekanism alloca (det påminner om att arbeta med vanliga lokala variabler). Sedan, när du kör ett LLVM-optimeringspass anropas , instruktioner alloca konverteras till SSA-form. TinyGo får dock input från Go SSA, som bekvämt redan är konverterad till SSA-form.
En annan innovation av fragmentet av mellankod som övervägs är att åtkomst till segmentelement genom index representeras i form av en operation för att beräkna adressen och en operation för att avleda den resulterande pekaren. Här kan du se det direkta tillägget av konstanter till IR-koden (till exempel - 1:int). I exemplet med funktionen myAdd detta har inte använts. Nu när vi har fått dessa funktioner ur vägen, låt oss ta en titt på vad den här koden blir när den konverteras till 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
}
Här, som tidigare, kan vi se samma struktur, som inkluderar andra syntaktiska strukturer. Till exempel i samtal phi värden och etiketter utbytta. Det finns dock något här som är värt att ägna särskild uppmärksamhet.
Till att börja med kan du här se en helt annan funktionssignatur. LLVM stöder inte segment, och som ett resultat, som en optimering, delade TinyGo-kompilatorn som genererade denna mellankod upp beskrivningen av denna datastruktur i delar. Det kan representera tre segmentelement (ptr, len и cap) som en struktur (struct), men att representera dem som tre separata enheter möjliggör vissa optimeringar. Andra kompilatorer kan representera segmentet på andra sätt, beroende på anropskonventionerna för målplattformens funktioner.
En annan intressant funktion i denna kod är användningen av instruktionen getelementptr (ofta förkortat som GEP).
Denna instruktion arbetar med pekare och används för att få en pekare till ett skivelement. Låt oss till exempel jämföra det med följande kod skriven i C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Eller med följande motsvarighet till detta:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
Det viktigaste här är att instruktionerna getelementptr utför inte hänvisningsoperationer. Den beräknar bara en ny pekare baserat på den befintliga. Det kan tas som instruktioner mul и add på hårdvarunivå. Du kan läsa mer om GEP-instruktionerna .
En annan intressant egenskap hos denna mellankod är användningen av instruktionen icmp. Detta är en allmän instruktion som används för att implementera heltalsjämförelser. Resultatet av denna instruktion är alltid ett typvärde i1 — logiskt värde. I det här fallet görs en jämförelse med hjälp av nyckelordet slt (undertecknad mindre än), eftersom vi jämför två siffror som tidigare representerats av typen int. Om vi jämförde två heltal utan tecken, skulle vi använda icmp, och nyckelordet som används i jämförelsen skulle vara ult. För att jämföra flyttalstal används en annan instruktion, fcmp, som fungerar på liknande sätt.
Resultat av
Jag tror att jag i detta material har täckt de viktigaste egenskaperna hos LLVM IR. Naturligtvis finns det mycket mer här. I synnerhet kan den mellanliggande representationen av koden innehålla många anteckningar som tillåter optimeringspass för att ta hänsyn till vissa egenskaper hos koden som är kända för kompilatorn och som inte annars kan uttryckas i IR. Detta är till exempel en flagga inbounds GEP-instruktioner eller flaggor nsw и nuw, som kan läggas till i instruktionerna add. Detsamma gäller nyckelordet private, vilket indikerar för optimeraren att funktionen den markerar inte kommer att refereras från utanför den aktuella kompileringsenheten. Detta möjliggör många intressanta interproceduroptimeringar som att eliminera oanvända argument.
Du kan läsa mer om LLVM i , som du ofta hänvisar till när du utvecklar din egen LLVM-baserade kompilator. Här , som tittar på att utveckla en kompilator för ett mycket enkelt språk. Båda dessa informationskällor kommer att vara användbara för dig när du skapar din egen kompilator.
Kära läsare! Använder du LLVM?
Källa: will.com