Het ontwikkelen van een compiler is een zeer zware taak. Maar gelukkig, met de ontwikkeling van projecten zoals LLVM, wordt het oplossen van dit probleem aanzienlijk eenvoudiger, waardoor zelfs een solo-programmeur een nieuwe taal kan creƫren die qua prestaties dicht bij C ligt. Het werken met LLVM wordt bemoeilijkt door het enorme volume aan code dat met weinig documentatie is voorzien. Om deze tekortkoming te verhelpen, is de auteur van dit materiaal, waarvan we vandaag de vertaling publiceren, van plan om voorbeelden van code geschreven in Go te demonstreren en te laten zien hoe ze eerst worden omgezet in , en vervolgens in LLVM IR met behulp van de compiler . De Go SSA- en LLVM IR-code is een beetje bewerkt; wat niet relevant is voor de hier gepresenteerde uitleg is verwijderd, zodat deze uitleg duidelijker zou zijn.
Het eerste voorbeeld
De eerste functie die ik hier ga bespreken is een eenvoudige functie voor het optellen van getallen:
func myAdd(a, b int) int{
return a + b
}Deze functie is heel eenvoudig, en er is waarschijnlijk niets eenvoudiger te bedenken. Het wordt omgezet in de volgende Go SSA-code:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0In deze weergave van de functie worden type-informatie rechts geplaatst, waar je in de meeste gevallen niet op hoeft te letten.
Dit kleine voorbeeld laat al Ć©Ć©n van de aspecten van SSA zien. Namelijk, bij het omzetten van de code naar SSA-vorm wordt elke expressie opgesplitst in de meest elementaire delen waaruit het bestaat. In ons geval vertegenwoordigt de opdracht return a + b, in feite, twee operaties: het optellen van twee getallen en het retourneren van het resultaat.
Bovendien zijn hier ook de basiselementen van het programma zichtbaar; in deze code is er maar Ć©Ć©n blok ā het invoerblok (entry block). Meer over blokken zullen we later bespreken.
De Go SSA-code kan gemakkelijk worden omgezet naar LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
} Het is op te merken dat, hoewel hier andere syntactische constructies worden gebruikt, de structuur van de functie in grote lijnen niet is veranderd. LLVM IR-code is iets krachtiger dan Go SSA-code en lijkt op C. Hier, in de functiedefinitie, staat eerst de beschrijving van het geretourneerde datatype, en het type van de argumenten wordt vĆ³Ć³r de naam van het argument aangegeven. Bovendien staat er, ter vereenvoudiging van de IR-parsing, een symbool voor de namen van globale entiteiten. @, terwijl er voor lokale namen een symbool staat. % (de functie wordt ook als een globale entiteit beschouwd).
Een van de kenmerken van deze code waar je op moet letten, is dat de beslissing over de representatie van het Go-type int, dat kan worden weergegeven door een 32-bits of 64-bits waarde, afhankelijk van de compiler en het compilatiedoel, wordt genomen bij het aanmaken van de LLVM IR-code. Dit is een van de vele redenen waarom LLVM IR-code, zoals velen denken, niet platformonafhankelijk is. Dergelijke code die voor Ć©Ć©n platform is gemaakt, kan niet eenvoudig worden genomen en voor een ander platform worden gecompileerd (tenzij deze taak ).
Een nog interessanter punt om op te merken is dat het type i64 geen ondertekened geheel getal is: het is neutraal wat betreft de weergave van het teken van het getal. Afhankelijk van de instructie kan het zowel als ondertekende als als ongetekende getallen worden gepresenteerd. In het geval van de representatie van de optelling speelt dit geen rol, en daarom is er hier geen verschil in het werken met ondertekende of ongetekende getallen. Hier zou ik willen opmerken dat in de C-taal het overstromen van een ondertekend geheel getal leidt tot onbepaald gedrag, daarom voegt de Clang-frontend een vlag toe aan de operatie nsw (no signed wrap), wat LLVM aangeeft dat het kan uitgaan van de veronderstelling dat er nooit een overstroming optreedt bij het optellen.
Dit kan belangrijk zijn voor sommige optimalisaties. Bijvoorbeeld, het optellen van twee waarden i16 op een 32-bits platform (met 32-bits registers) heeft, na de optelling, een operatie voor het uitbreiden van het teken nodig om binnen het bereik te blijven. i16. Daarom is het vaak efficiƫnter om gehele getal operaties uit te voeren rekening houdend met de machinegrootte van het register.
Wat er verder met deze IR-code gebeurt, is momenteel niet van bijzonder belang voor ons. De code wordt geoptimaliseerd (maar bij zo'n eenvoudig voorbeeld als het onze, wordt er niets meer geoptimaliseerd), en vervolgens omgezet naar machinecode.
Tweede voorbeeld
Het volgende voorbeeld dat we gaan bekijken, zal iets ingewikkelder zijn. Namelijk, het gaat over een functie die een slice 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 omgezet in 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 kunnen we al meer constructies zien die typerend zijn voor de weergave van code in SSA-vorm. Waarschijnlijk is het meest opvallende kenmerk van deze code het feit dat er geen gestructureerde controle-instructies voor de stroom van berekeningen zijn. Voor de controle van de stroom zijn er alleen conditionele en onvoorwaardelijke sprongen, en, als we deze instructie als een instructie voor stroombeheer beschouwen, is de terugkeerinstructie ook een stroomcontrole-instructie.
In feite valt op dat het programma niet is opgedeeld in blokken met behulp van accolades (zoals in talen van de C-familie). Het is verdeeld in labels, wat doet denken aan assemblertalen, en wordt gepresenteerd in de vorm van basisblokken. In SSA worden basisblokken gedefinieerd als continue reeks codes die beginnen met een label en eindigen met instructies die het basisblok beĆ«indigen, bijvoorbeeld ā terug en jump.
Een ander interessant detail van deze code wordt gepresenteerd door de instructie phi. Deze instructie is vrij ongebruikelijk en het kan enige tijd duren om deze te begrijpen. Vergeet niet dat ā dit is een afkorting voor Static Single Assignment. Dit is een tussentijdse representatie van code die door compilers wordt gebruikt, waarin elke variabele slechts Ć©Ć©n keer een waarde krijgt toegewezen. Dit is zeer geschikt voor het uitdrukken van eenvoudige functies, zoals onze functie myAdd, die hierboven is getoond, maar niet geschikt voor meer complexe functies ā zoals de functie die in dit gedeelte wordt behandeld sum. In het bijzonder veranderen variabelen tijdens de uitvoering van een lus i en n.
SSA omzeilt de beperking van het ƩƩnmalig toewijzen van waarden aan variabelen door gebruik te maken van de zogenaamde phi-instructie phi (de naam is ontleend aan het Griekse alfabet). Het probleem is dat om een SSA-representatie van de code te creƫren voor talen zoals C, men bepaalde trucs moet toepassen. Het resultaat van het aanroepen van deze instructie is de huidige waarde van de variabele (i of n), en een lijst van basale blokken wordt als parameters gebruikt. Laten we zo'n instructie beschouwen:
t0 = phi [entry: 0:int, for.body: t6] #n De betekenis ervan is als volgt: als het voorgaande basale blok het blok entry (invoeren), dan is t0 een constante 0, en als het voorgaande basale blok for.body, dan moet de waarde t6 uit dat blok worden genomen. Dit kan er nogal mysterieus uitzien, maar dankzij dit mechanisme wordt de werking van SSA mogelijk gemaakt. Vanuit menselijk oogpunt maakt het alles ingewikkelder om de code te begrijpen, maar het feit dat elke waarde slechts Ć©Ć©n keer wordt toegewezen, vereenvoudigt veel optimalisaties aanzienlijk.
Houd er rekening mee dat als je je eigen compiler schrijft, je meestal niet met dit soort dingen te maken hebt. Zelfs Clang genereert al deze instructies niet phi, het gebruikt het mechanisme alloca (het lijkt op het werken met gewone lokale variabelen). Vervolgens, tijdens de optimalisatiepass van LLVM, genaamd , worden de instructies omgevormd tot de SSA-vorm. TinyGo ontvangt echter zijn input van Go SSA, die, wat handig is, al is omgevormd tot de SSA-vorm. alloca Een andere innovatie van het besprak fragment van tussentijdse code is dat de toegang tot elementen van een slice op index wordt weergegeven als een adresberekeningsoperatie en een dereferentieoperatie van de verkregen pointer. Hier kunnen we ook directe toevoegingen van constanten aan de IR-code zien (bijvoorbeeld ā
1:int ). In het voorbeeld met de functie). In het voorbeeld met de functie myAdd Er was niets dergelijks gebruikt. Nu we deze bijzonderheden hebben begrepen, laten we eens kijken naar hoe deze code eruit zal zien wanneer deze wordt omgezet naar LLVM IR-vorm:
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
} Hier zien we, net als voorheen, dezelfde structuur met andere syntactische constructies. Bijvoorbeeld, in de aanroepen phi zijn de waarden en labels verwisseld. Echter, er is hier ook iets dat speciale aandacht verdient.
Om te beginnen is er hier een totaal andere functiehandtekening te zien. LLVM ondersteunt geen slices, waardoor de TinyGo-compiler die deze tussentijdse code heeft gegenereerd, de beschrijving van deze datatypes in delen heeft verdeeld. Het had drie elementen van een slice kunnen presenteren (ptr, len en cap) in de vorm van een structuur (struct), maar het presenteren van hen als drie afzonderlijke entiteiten maakt bepaalde optimalisaties mogelijk. Andere compilers kunnen slices op een andere manier presenteren, afhankelijk van de functie-aanroepconventies van het doelsysteem.
Een andere interessante eigenschap van deze code is het gebruik van de instructie getelementptr (vaak afgekort tot GEP).
Deze instructie werkt met pointers en wordt gebruikt om een pointer naar een element van een slice te verkrijgen. Laten we deze vergelijken met de volgende C-code:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Of met de volgende, die hiermee equivalent is:
int* sliceptr(int *ptr, int index) {
return ptr + index;
} Het belangrijkste hier is dat de instructie getelementptr geen dereferentiebewerkingen uitvoert. Het berekent alleen een nieuwe pointer op basis van de bestaande. Het kan worden opgevat als de instructie mul en add op hardware-niveau. Details over de GEP-instructie kunnen worden gelezen .
Een andere interessante eigenschap van deze tussentijdse code is het gebruik van de instructie icmpDit is een algemene instructie die wordt gebruikt voor het vergelijken van gehele getallen. Het resultaat van deze instructie is altijd een waarde van het type i1 ā een logisch waarde. In dit geval wordt de vergelijking uitgevoerd met het sleutelwoord slt (signed less than), omdat we twee getallen vergelijken die eerder zijn voorgesteld als type int. Als we twee ongetekende gehele getallen zouden vergelijken, zouden we de instructie icmpgebruiken, en het sleutelwoord dat wordt gebruikt bij de vergelijking zou zijn ult. Voor het vergelijken van drijvende getallen wordt een andere instructie gebruikt, fcmp, die op een vergelijkbare manier werkt.
Conclusies
Ik geloof dat ik in dit materiaal de belangrijkste kenmerken van LLVM IR heb behandeld. Natuurlijk is er nog veel meer te leren. In het tussentijdse code-voorstelling kunnen veel annotaties aanwezig zijn die het optimalisatieproces helpen door bepaalde kenmerken van de code die de compiler kent, uit te drukken, en die anders niet in IR kunnen worden uitgedrukt. Bijvoorbeeld, dit is de vlag inbounds van de GEP-instructie, of de vlaggen nsw en nuw, die aan de instructie kunnen worden toegevoegd. addHetzelfde geldt voor het sleutelwoord private, dat de optimizer aangeeft dat de functie die ermee is gemarkeerd niet van buiten de huidige compilatie-eenheid zal worden aangesproken. Dit maakt verschillende interessante interprocedurale optimalisaties mogelijk, zoals het verwijderen van ongebruikte argumenten.
Details over LLVM kunt u lezen in , waar u vaak naar zult verwijzen als u uw eigen compiler op basis van LLVM ontwikkelt. Hier is , waarin de ontwikkeling van een compiler voor een zeer eenvoudige taal wordt besproken. Beide van deze informatiebronnen zullen nuttig zijn bij het creƫren van uw eigen compiler.
Geachte lezers! Maakt u gebruik van LLVM?
Bron: habr.com
