Att utveckla en kompilator är en mycket svår uppgift. Men tack och lov, med utvecklingen av projekt som LLVM, blir denna uppgift betydligt enklare, vilket gör det möjligt för även en ensam programmerare att skapa ett nytt språk som är nära C i prestanda. Arbetet med LLVM kompliceras av att detta system presenteras med en enorm mängd kod som har lite dokumentation. För att försöka åtgärda denna brist avser författaren till materialet, vars översättning vi publicerar idag, att demonstrera exempel på kod skriven i Go och visa hur de transkriberas först till , och sedan – till LLVM IR med hjälp av kompileraren . Koden i Go SSA och LLVM IR har redigerats något för att ta bort det som inte är relevant för de förklaringar som ges här, för att göra dessa förklaringar mer förståeliga.
Det första exemplet
Den första funktionen som jag ska gå igenom här är en enkel mekanism för att addera tal:
func myAdd(a, b int) int{
return a + b
}Denna funktion är mycket enkel och det är nog svårt att göra något enklare. Den transkriberas till följande Go SSA-kod:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0I denna representation av funktionen placeras typinformation till höger, vilket i de flesta fall kan bortses ifrån.
Detta lilla exempel gör det möjligt att se essensen av en av aspekterna av SSA. Nämligen, vid omvandlingen av koden till SSA-form delas varje uttryck upp i de mest elementära delar som den består av. I vårt fall representerar kommandot return a + b, i själva verket, två operationer: addering av två tal och återlämnande av resultatet.
Dessutom kan vi se de grundläggande blocken i programmet, i denna kod finns det bara ett block – ingångsblocket (entry block). Vi kommer att prata mer om block nedan.
Koden i Go SSA kan enkelt omvandlas till LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
} Man kan notera att även om andra syntaktiska konstruktioner används här, har funktionsstrukturen i huvudsak inte förändrats. LLVM IR-koden är något starkare än Go SSA-koden och liknar C. Här, i funktionsdeklarationen, anges först typen av det värde som ska returneras, och typ av argumentet anges före argumentets namn. Dessutom, för att förenkla IR-parsning, går en symbol före namnen på globala entiteter. @, medan en symbol står före namnen på lokala entiteter. % (funktionen anses också vara en global entitet).
En av de intressanta egenskaperna hos denna kod, som är värd att notera, är att beslutet om hur typen Go int, som kan representeras som ett 32-bitars eller 64-bitars värde beroende på kompilatorn och kompilationsmålet, fattas vid skapandet av LLVM IR-koden. Detta är en av många anledningar till att LLVM IR-koden inte är, som många tror, plattformsoberoende. Denna kod, skapad för en plattform, kan inte bara tas och kompileras för en annan plattform (såvida man inte närmar sig lösningen av detta problem ).
En annan intressant punkt som är värd att nämna är att typen i64 inte är ett heltal med tecken: det är neutralt vad gäller teckenrepresentationen av talet. Beroende på instruktionen kan det representera både tecknade och o0tecknade tal. När det gäller representationen av additio är det inte av betydelse, så det finns ingen skillnad i arbetet med tecknade eller o0tecknade tal. Här vill jag påpeka att i C-språket leder överflödet av ett tecknat heltalsvariabel till odefinierat beteende, så frontend Clang lägger till en flagga nsw (no signed wrap), vilket indikerar för LLVM att det kan utgå ifrån att överflöd aldrig inträffar vid addition.
Detta kan vara viktigt för vissa optimeringar. Till exempel behöver addition av två värden i16 på en 32-bitar plattform (med 32-bitar register) efter att additionen genomförts en operation för teckenextention för att förbli inom intervallet. i16. Därför visar det sig ofta vara mer effektivt att utföra heltalsoperationer med hänsyn till maskinens registerstorlek.
Det som händer härnäst med denna IR-kod är inte av särskilt intresse för oss just nu. Koden optimeras (men i fallet med ett så enkelt exempel som vårt optimeras ingenting längre), och omvandlas sedan till maskinkod.
Det andra exemplet
Nästa exempel som vi ska titta på kommer att vara något svårare. Det handlar specifikt om en funktion som summerar en slice av heltal:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Den här koden omvandlas 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 vi redan se fler konstruktioner som är typiska för att representera kod i SSA-form. Förmodligen är den mest uppenbara egenskapen hos denna kod det faktum att det inte finns några strukturerade kontrollkommandon för flöde av beräkningar. För att kontrollera flödet av beräkningar finns det bara villkorliga och ovillkorliga hopp, och om man räknar detta kommando som ett kommando för att styra flödet, är returkommandot också ett sådant.
I själva verket kan man notera att programmet inte är uppdelat i block med hjälp av klamrar (som i språk i C-familjen). Det är uppdelat med etiketter, vilket påminner om assembleringsspråk, och presenteras i form av grundblock. I SSA kallas grundblock för sammanhängande kodsekvenser som börjar med en etikett och slutar med instruktioner för att avsluta grundblocket, exempelvis — återvända och jump.
En annan intressant detalj i denna kod presenteras av instruktionen phi. Denna instruktion är ganska ovanlig, och det kan ta lite tid att förstå den. Kom ihåg att — är en förkortning för Static Single Assignment. Detta är en mellanrepresentation av koden som används av kompilatorer, där varje variabel får sitt värde tilldelat endast en gång. Detta är utmärkt för att uttrycka enkla funktioner, såsom vår funktion myAdd, som nämndes ovan, men fungerar inte för mer komplexa funktioner — som den som diskuteras i detta avsnitt. sum. Specifikt förändras variabler under körningen av en loop. i och n.
SSA kringgår begränsningen av enkelvärdes tilldelning av variabler genom att använda så kallade instruktioner phi (namnet kommer från det grekiska alfabetet). För att SSA-representation av koden ska kunna bildas för språk som C, måste vissa knep användas. Resultatet av att anropa denna instruktion är det aktuella värdet av variabeln (i eller n), och som parametrar används en lista av grundläggande block. Låt oss titta på en sådan instruktion:
t0 = phi [entry: 0:int, for.body: t6] #n Dess innebörd är följande: om det föregående grundläggande blocket var blocket entry (ingång), då är t0 en konstant 0, och om det föregående grundläggande blocket var for.body, då måste värdet t6 hämtas från detta block. Allt detta kan verka ganska mystiskt, men tack vare denna mekanism fungerar SSA. Från ett mänskligt perspektiv komplicerar detta förståelsen av koden, men faktumet att varje värde tilldelas endast en gång förenklar många optimeringar avsevärt.
Observera att om du skriver din egen kompilator, så behöver du vanligtvis inte hantera sådana saker. Till och med Clang genererar inte alla dessa instruktioner phi, det använder mekanismen alloca (den liknar arbetet med vanliga lokala variabler). Sedan, under genomfart optimeringen LLVM, kallad , omvandlas instruktionerna alloca till SSA-form. TinyGo, å andra sidan, får indata från Go SSA, som, bekvämt nog, redan är omvandlade till SSA-form.
En annan nyhet i den diskuterade fragmentet av mellanliggande kod är att åtkomst till element i en slice via index representeras som en adressberäkningsoperation och en avdereferensieringsoperation av den erhållna pekaren. Här kan man även se direkta tillägg av konstanter i IR-kod (till exempel — 1:int). I exemplet med funktionen myAdd Inga liknande saker har använts. Nu, efter att ha förstått dessa egenskaper, låt oss se hur denna kod kommer att se ut när den omvandlas 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 konstruktioner. Till exempel i anrop. phi Värdena och etiketterna har bytt plats. Men här finns också något som är värt att särskilt uppmärksamma.
För det första kan vi se en helt annan funktionssignatur här. LLVM stöder inte skivor, vilket ledde till att TinyGo-kompilatorn som genererade denna mellanliggande kod delade upp beskrivningen av denna datatyp i delar. Den skulle kunna presentera tre element av skivan (ptr, len och cap) som en struktur, men att presentera dem som tre separata enheter möjliggör vissa optimeringar. Andra kompilatorer kan presentera skivan på andra sätt, beroende på anropskonventionerna för målplattformen.
En annan intressant egenskap med denna kod är användningen av instruktionen getelementptr (den kallas ofta för GEP).
Denna instruktion fungerar med pekare och används för att få pekaren till ett element av skivan. Låt oss till exempel jämföra den med följande kod som är skriven i C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Eller med följande, som är ekvivalent med detta:
int* sliceptr(int *ptr, int index) {
return ptr + index;
} Det viktigaste här är att instruktionen getelementptr inte utför avreferensoperationer. Den beräknar bara en ny pekare baserat på den existerande. Den kan ses som instruktionen mul och add på hårdvarunivå. Detaljer om instruktionen GEP kan läsas. .
En annan intressant egenskap med denna mellanliggande kod är användningen av instruktionen icmp. Detta är en allmän instruktion som används för att genomföra jämförelser av heltal. Resultatet av att utföra denna instruktion är alltid ett värde av typen i1 — ett logiskt värde. I detta fall görs jämförelsen med hjälp av nyckelordet slt (signed less than), eftersom vi jämför två tal av typen int. Om vi hade jämfört två osignerade heltal, skulle vi ha använt icmp, och nyckelordet som används vid jämförelsen skulle ha varit ult. För jämförelse av flyttal används en annan instruktion, fcmp, som fungerar på ett liknande sätt.
Sammanfattning
Jag tror att jag har täckt de mest viktiga aspekterna av LLVM IR i detta material. Självklart finns det mycket mer här. Specifikt kan det i mellanrepresentationskoden finnas många anteckningar som gör det möjligt att ta hänsyn till specifika egenskaper i koden under optimeringspass, kända för kompilatorn, som inte kan uttryckas på något annat sätt i IR. Till exempel, detta flagga inbounds för GEP-instruktionen, eller flaggorna nsw och nuw, som kan läggas till instruktionen add. Detsamma gäller nyckelordet private, som informerar optimeraren om att den markerade funktionen inte kommer att refereras utanför den aktuella kompileringselementet. Detta möjliggör många intressanta interprocedurala optimeringar, såsom att eliminera oanvända argument.
För detaljer om LLVM kan du läsa i , som du ofta kommer att referera till när du utvecklar din egen kompilator baserad på LLVM. Här är , som behandlar utvecklingen av en kompilator för ett mycket enkelt språk. Dessa två informationskällor kommer att vara till nytta för dig när du skapar din egen kompilator.
Kära läsare! Använder du LLVM?
Källa: habr.com
