Het ontwikkelen van een compiler is een zeer moeilijke taak. Maar gelukkig is met de ontwikkeling van projecten als LLVM de oplossing voor dit probleem aanzienlijk vereenvoudigd, waardoor zelfs één enkele programmeur een nieuwe taal kan creëren die qua prestaties dicht bij C ligt. Werken met LLVM wordt gecompliceerd door het feit dat dit systeem wordt vertegenwoordigd door een enorme hoeveelheid code, uitgerust met weinig documentatie. Om te proberen deze tekortkoming te corrigeren, gaat de auteur van het materiaal, waarvan we de vertaling vandaag publiceren, voorbeelden demonstreren van code geschreven in Go en laten zien hoe deze eerst worden vertaald naar en vervolgens in LLVM IR met behulp van de compiler . De Go SSA- en LLVM IR-code zijn enigszins aangepast om zaken te verwijderen die niet relevant zijn voor de hier gegeven uitleg, om de uitleg begrijpelijker te maken.
Eerste voorbeeld
De eerste functie die ik hier ga bekijken is een eenvoudig mechanisme voor het optellen van getallen:
func myAdd(a, b int) int{
return a + b
}Deze functie is heel eenvoudig en misschien is niets eenvoudiger. Het vertaalt zich in de volgende Go SSA-code:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0In deze weergave worden de gegevenstypehints aan de rechterkant geplaatst en kunnen ze in de meeste gevallen worden genegeerd.
Dit kleine voorbeeld laat je al de essentie van één aspect van SSA zien. Bij het converteren van code naar SSA-vorm wordt namelijk elke expressie opgesplitst in de meest elementaire delen waaruit deze is samengesteld. In ons geval de opdracht return a + bvertegenwoordigt in feite twee bewerkingen: twee getallen optellen en het resultaat retourneren.
Bovendien kunt u hier de basisblokken van het programma zien; in deze code is er slechts één blok: het invoerblok. We zullen hieronder meer over blokken praten.
De Go SSA-code wordt eenvoudig geconverteerd naar LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Wat je kunt opmerken is dat, hoewel hier verschillende syntactische structuren worden gebruikt, de structuur van de functie in principe onveranderd is. De LLVM IR-code is iets sterker dan de Go SSA-code, vergelijkbaar met C. Hier, in de functiedeclaratie, is er eerst een beschrijving van het gegevenstype dat het retourneert, het argumenttype wordt aangegeven vóór de argumentnaam. Om het parseren van IR te vereenvoudigen, worden de namen van globale entiteiten bovendien voorafgegaan door het symbool @, en vóór lokale namen staat een symbool % (een functie wordt ook beschouwd als een globale entiteit).
Een ding om op te merken over deze code is dat Go's typerepresentatiebeslissing int, die kan worden weergegeven als een 32-bits of 64-bits waarde, afhankelijk van de compiler en het doel van de compilatie, wordt geaccepteerd wanneer LLVM de IR-code genereert. Dit is een van de vele redenen dat de LLVM IR-code niet, zoals veel mensen denken, platformonafhankelijk is. Dergelijke code, gemaakt voor het ene platform, kan niet zomaar worden overgenomen en gecompileerd voor een ander platform (tenzij je geschikt bent om dit probleem op te lossen ).
Een ander interessant punt dat het vermelden waard is, is het type i64 is geen geheel getal met teken: het is neutraal in termen van weergave van het teken van het getal. Afhankelijk van de instructie kan het zowel ondertekende als niet-ondertekende nummers vertegenwoordigen. In het geval van de weergave van de optelbewerking maakt dit niet uit, er is dus geen verschil tussen het werken met ondertekende of niet-ondertekende getallen. Hier zou ik willen opmerken dat in de C-taal het overlopen van een ondertekende integer-variabele leidt tot ongedefinieerd gedrag, dus de Clang-frontend voegt een vlag toe aan de bewerking nsw (geen ondertekende wrap), wat LLVM vertelt dat het ervan uit kan gaan dat de toevoeging nooit overloopt.
Dit kan belangrijk zijn voor sommige optimalisaties. Voeg bijvoorbeeld twee waarden toe i16 op een 32-bits platform (met 32-bits registers) vereist na toevoeging een tekenuitbreidingsoperatie om binnen bereik te blijven i16. Hierdoor is het vaak efficiënter om gehele bewerkingen uit te voeren op basis van de machineregistergroottes.
Wat er vervolgens met deze IR-code gebeurt, is voor ons op dit moment niet van bijzonder belang. De code wordt geoptimaliseerd (maar in het geval van een eenvoudig voorbeeld als het onze is er niets geoptimaliseerd) en vervolgens omgezet in machinecode.
Tweede voorbeeld
Het volgende voorbeeld dat we zullen bekijken zal iets ingewikkelder zijn. We hebben het namelijk over een functie die een deel van gehele getallen optelt:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Deze code wordt geconverteerd naar de volgende Go SSA-code:
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 t0Hier ziet u al meer constructies die typisch zijn voor het weergeven van code in het SSA-formulier. Misschien wel het meest voor de hand liggende kenmerk van deze code is het feit dat er geen gestructureerde stroombesturingsopdrachten zijn. Om de stroom van berekeningen te beheersen, zijn er alleen voorwaardelijke en onvoorwaardelijke sprongen, en, als we dit commando beschouwen als een commando om de stroom te beheersen, een retourcommando.
In feite kun je hier op letten dat het programma niet in blokken is verdeeld met behulp van accolades (zoals in de C-talenfamilie). Het is verdeeld door labels, die doen denken aan assembleertalen, en gepresenteerd in de vorm van basisblokken. In SSA worden basisblokken gedefinieerd als aaneengesloten codereeksen, beginnend met een label en eindigend met basisinstructies voor het voltooien van blokken, zoals - return и jump.
Een ander interessant detail van deze code wordt weergegeven door de instructie phi. De instructies zijn vrij ongebruikelijk en het kan enige tijd duren om ze te begrijpen. onthoud dat is een afkorting voor Statische Enkele Toewijzing. Dit is een tussenweergave van de code die door compilers wordt gebruikt, waarbij aan elke variabele slechts één keer een waarde wordt toegewezen. Dit is geweldig voor het uitdrukken van eenvoudige functies zoals onze functie myAddhierboven weergegeven, maar is niet geschikt voor complexere functies zoals de functie die in deze sectie wordt besproken sum. In het bijzonder veranderen variabelen tijdens de uitvoering van de lus i и n.
SSA omzeilt de beperking op het eenmalig toekennen van variabele waarden met behulp van een zogenaamde instructie phi (de naam is ontleend aan het Griekse alfabet). Feit is dat je, om de SSA-representatie van code te genereren voor talen als C, je toevlucht moet nemen tot een aantal trucjes. Het resultaat van het aanroepen van deze instructie is de huidige waarde van de variabele (i of n), en een lijst met basisblokken wordt gebruikt als parameters. Overweeg bijvoorbeeld deze instructie:
t0 = phi [entry: 0:int, for.body: t6] #n
De betekenis ervan is als volgt: als het vorige basisblok een blok was entry (invoer), dan t0 is een constante 0, en of het vorige basisblok dat was for.body, dan moet je de waarde nemen t6 uit dit blok. Dit lijkt misschien allemaal nogal mysterieus, maar dit mechanisme zorgt ervoor dat de SSA werkt. Vanuit menselijk perspectief maakt dit alles de code moeilijk te begrijpen, maar het feit dat elke waarde slechts één keer wordt toegewezen, maakt veel optimalisaties veel eenvoudiger.
Houd er rekening mee dat als u uw eigen compiler schrijft, u meestal niet met dit soort dingen te maken krijgt. Zelfs Clang genereert niet al deze instructies phi, het maakt gebruik van een mechanisme alloca (het lijkt op het werken met gewone lokale variabelen). Vervolgens wordt bij het uitvoeren van een LLVM-optimalisatiepas aangeroepen , instructies alloca omgezet naar SSA-formulier. TinyGo ontvangt echter input van Go SSA, die handig al is omgezet naar SSA-vorm.
Een andere innovatie van het beschouwde fragment van de tussencode is dat toegang tot segmentelementen door index wordt weergegeven in de vorm van een bewerking van het berekenen van het adres en een bewerking van het derefereren van de resulterende aanwijzer. Hier ziet u de directe toevoeging van constanten aan de IR-code (bijvoorbeeld - 1:int). In het voorbeeld met de functie myAdd deze is niet gebruikt. Nu we deze functies uit de weg hebben geruimd, laten we eens kijken naar wat deze code wordt wanneer deze wordt geconverteerd naar het LLVM IR-formulier:
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
}
Hier kunnen we, net als voorheen, dezelfde structuur zien, die andere syntactische structuren omvat. Bijvoorbeeld bij bellen phi waarden en labels verwisseld. Er is hier echter iets dat de moeite waard is om speciale aandacht aan te besteden.
Om te beginnen ziet u hier een geheel andere functiesignatuur. LLVM ondersteunt geen segmenten, en als gevolg daarvan splitste de TinyGo-compiler die deze tussencode genereerde, als optimalisatie, de beschrijving van deze datastructuur in delen. Het zou drie segmentelementen kunnen vertegenwoordigen (ptr, len и cap) als een structuur (struct), maar door ze als drie afzonderlijke entiteiten weer te geven zijn enkele optimalisaties mogelijk. Andere compilers kunnen de slice op andere manieren weergeven, afhankelijk van de aanroepconventies van de functies van het doelplatform.
Een ander interessant kenmerk van deze code is het gebruik van de instructie getelementptr (vaak afgekort als GEP).
Deze instructie werkt met pointers en wordt gebruikt om een pointer naar een slice-element te verkrijgen. Laten we het bijvoorbeeld vergelijken met de volgende code geschreven in C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Of met het volgende equivalent hiervan:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
Het belangrijkste hier is dat de instructies getelementptr voert geen dereferentiebewerkingen uit. Het berekent gewoon een nieuwe aanwijzer op basis van de bestaande. Het kan als instructies worden opgevat mul и add op hardwareniveau. U kunt meer lezen over de GEP-instructies .
Een ander interessant kenmerk van deze tussencode is het gebruik van de instructie icmp. Dit is een instructie voor algemene doeleinden die wordt gebruikt om vergelijkingen van gehele getallen te implementeren. Het resultaat van deze instructie is altijd een waarde van het type i1 – logische waarde. In dit geval wordt er een vergelijking gemaakt met behulp van het trefwoord slt (kleiner getekend dan), omdat we twee getallen vergelijken die eerder door het type werden weergegeven int. Als we twee gehele getallen zonder teken zouden vergelijken, zouden we gebruiken icmp, en het trefwoord dat in de vergelijking wordt gebruikt, zou zijn ult. Om drijvende-kommagetallen te vergelijken, wordt een andere instructie gebruikt, fcmp, dat op een vergelijkbare manier werkt.
Resultaten van
Ik geloof dat ik in dit materiaal de belangrijkste kenmerken van LLVM IR heb behandeld. Natuurlijk is er hier nog veel meer. In het bijzonder kan de tussenrepresentatie van de code veel annotaties bevatten die het mogelijk maken dat optimalisaties rekening houden met bepaalde kenmerken van de code die bekend zijn bij de compiler en die anderszins niet in IR kunnen worden uitgedrukt. Dit is bijvoorbeeld een vlag inbounds GEP-instructies of vlaggen nsw и nuw, die aan de instructies kan worden toegevoegd add. Hetzelfde geldt voor het trefwoord private, wat aan de optimalisatie aangeeft dat er niet naar de functie die het markeert zal worden verwezen van buiten de huidige compilatie-eenheid. Dit maakt veel interessante interprocedurele optimalisaties mogelijk, zoals het elimineren van ongebruikte argumenten.
U kunt meer lezen over LLVM in , waarnaar u vaak zult verwijzen bij het ontwikkelen van uw eigen op LLVM gebaseerde compiler. Hier , waarin wordt gekeken naar het ontwikkelen van een compiler voor een zeer eenvoudige taal. Beide informatiebronnen zullen nuttig voor u zijn bij het maken van uw eigen compiler.
Beste lezers! Maakt u gebruik van LLVM?
Bron: www.habr.com