It ûntwikkeljen fan in kompilator is in heul lestige taak. Mar, lokkigernôch, mei de ûntwikkeling fan projekten lykas LLVM, is de oplossing foar dit probleem sterk ferienfâldige, wêrtroch sels in inkele programmeur in nije taal kin meitsje dy't yn prestaasje ticht is by C. Wurkjen mei LLVM is komplisearre troch it feit dat dit systeem wurdt fertsjintwurdige troch in enoarme hoemannichte koade, foarsjoen fan in bytsje dokumintaasje. Om te besykjen dit tekoart te korrigearjen, sil de skriuwer fan it materiaal, de oersetting wêrfan wy hjoed publisearje, foarbylden sjen litte fan koade skreaun yn Go en sjen litte hoe't se earst oerset wurde yn , en dan yn LLVM IR mei de kompilator . De Go SSA en LLVM IR-koade is in bytsje bewurke om dingen te ferwiderjen dy't net relevant binne foar de hjir jûne taljochtingen, om de ferklearrings mear begryplik te meitsjen.
Earste foarbyld
De earste funksje wêr't ik hjir nei sil sjen is in ienfâldich meganisme foar it tafoegjen fan nûmers:
func myAdd(a, b int) int{
return a + b
}Dizze funksje is heul ienfâldich, en miskien kin neat ienfâldiger wêze. It fertaalt yn 'e folgjende Go SSA-koade:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Mei dizze werjefte wurde de hints fan it gegevenstype oan 'e rjochter pleatst en kinne yn' e measte gefallen wurde negearre.
Dit lytse foarbyld lit jo al sjen de essinsje fan ien aspekt fan SSA. Nammentlik, by it konvertearjen fan koade yn SSA-foarm, wurdt elke útdrukking opdield yn 'e meast elemintêre dielen wêrfan it is gearstald. Yn ús gefal, it kommando return a + b, yn feite, stiet foar twa operaasjes: it tafoegjen fan twa nûmers en it werombringen fan it resultaat.
Derneist kinne jo hjir de basisblokken fan it programma sjen; yn dizze koade is d'r mar ien blok - it yngongsblok. Wy sille hjirûnder mear oer blokken prate.
De Go SSA-koade konvertearret maklik nei LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Wat jo opfalle kinne is dat hoewol ferskate syntaktyske struktueren hjir brûkt wurde, de struktuer fan 'e funksje yn prinsipe net feroare is. De LLVM IR-koade is in bytsje sterker as de Go SSA-koade, fergelykber mei C. Hjir, yn 'e funksjeferklearring, is earst in beskriuwing fan it gegevenstype dat it werombringt, it arguminttype wurdt oanjûn foar de argumintnamme. Derneist, om IR-parsing te ferienfâldigjen, wurde de nammen fan globale entiteiten foarôfgien troch it symboal @, en foar lokale nammen is der in symboal % (in funksje wurdt ek beskôge as in globale entiteit).
Ien ding om te notearjen oer dizze koade is dat Go's type fertsjintwurdiging beslút int, dat kin wurde fertsjintwurdige as in 32-bit of 64-bit wearde, ôfhinklik fan de gearstaller en it doel fan 'e kompilaasje, wurdt akseptearre as LLVM genereart de IR-koade. Dit is ien fan de protte redenen dat LLVM IR-koade net is, lykas in protte minsken tinke, platfoarmûnôfhinklik. Sa'n koade, makke foar ien platfoarm, kin net gewoan wurde nommen en gearstald foar in oar platfoarm (útsein as jo geskikt binne foar it oplossen fan dit probleem ).
In oar nijsgjirrich punt wurdich opskriuwen is dat it type i64 is gjin tekene hiel getal: it is neutraal yn termen fan it fertsjintwurdigjen fan it teken fan it getal. Ofhinklik fan 'e ynstruksje kin it sawol ûndertekene as net-ûndertekene nûmers fertsjintwurdigje. Yn it gefal fan de fertsjintwurdiging fan de tafoeging operaasje, dit makket neat út, dus der is gjin ferskil yn wurkjen mei ûndertekene of net ûndertekene nûmers. Hjir wol ik opmerke dat yn 'e C-taal it oerstreamen fan in ûndertekene ynteger fariabele liedt ta ûndefinieare gedrach, sadat de Clang-frontend in flagge tafoege oan' e operaasje nsw (gjin ûndertekene wrap), dy't fertelt LLVM dat it kin oannimme dat tafoeging nea oerstreamt.
Dit kin wichtich wêze foar guon optimisaasjes. Bygelyks, it tafoegjen fan twa wearden i16 op in 32-bit platfoarm (mei 32-bit registers) fereasket, nei tafoeging, in tekenútwreidingsoperaasje om yn berik te bliuwen i16. Hjirtroch is it faaks effisjinter om integer operaasjes út te fieren basearre op masineregistergrutte.
Wat der neist bart mei dizze IR-koade is no net fan bysûnder belang foar ús. De koade wurdt optimalisearre (mar yn it gefal fan in ienfâldich foarbyld lykas ús, neat wurdt optimalisearre) en dan omset yn masine koade.
Twadde foarbyld
It folgjende foarbyld dat wy sille sjen sil in bytsje komplisearre wêze. Wy prate nammentlik oer in funksje dy't in stik fan heule getallen somt:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Dizze koade konvertearret nei de folgjende Go SSA-koade:
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 t0Hjir kinne jo al mear konstruksjes sjen dy't typysk binne foar it fertsjintwurdigjen fan koade yn it SSA-formulier. Miskien is it meast foar de hân lizzende skaaimerk fan dizze koade it feit dat d'r gjin strukturearre kommando's foar streamkontrôle binne. Om de stream fan berekkeningen te kontrolearjen, binne d'r allinich betingsten en sûnder betingsten sprongen, en, as wy dit kommando beskôgje as in kommando om de stream te kontrolearjen, in weromkommando.
Yn feite, hjir kinne jo betelje omtinken oan it feit dat it programma is net ferdield yn blokken mei help fan krullend beugels (lykas yn 'e C famylje fan talen). It is ferdield troch labels, dy't tinken docht oan assemblagetalen, en presintearre yn 'e foarm fan basisblokken. Yn SSA wurde basisblokken definieare as oanienkommende sekwinsjes fan koade dy't begjinne mei in label en einigje mei basisynstruksjes foar foltôging fan blokken, lykas - return и jump.
In oar nijsgjirrich detail fan dizze koade wurdt fertsjintwurdige troch de ynstruksje phi. De ynstruksjes binne frij ûngewoan en kinne wat tiid duorje om te begripen. ûnthâld dat is koart foar Static Single Assignment. Dit is in tuskenfoarstelling fan 'e koade brûkt troch kompilatoren, wêryn elke fariabele mar ien kear in wearde wurdt tawiisd. Dit is geweldich foar it útdrukken fan ienfâldige funksjes lykas ús funksje myAddhjirboppe werjûn, mar is net geskikt foar mear komplekse funksjes lykas de funksje besprutsen yn dizze paragraaf sum. Benammen fariabelen feroarje tidens de útfiering fan 'e loop i и n.
SSA omgiet de beheining op it tawizen fan fariabele wearden ienris mei in saneamde ynstruksje phi (syn namme komt fan it Grykske alfabet). It feit is dat om de SSA-fertsjintwurdiging fan koade te generearjen foar talen lykas C, jo moatte taflecht ta guon trúkjes. It resultaat fan it oproppen fan dizze ynstruksje is de hjoeddeistige wearde fan 'e fariabele (i of n), en in list mei basisblokken wurdt brûkt as syn parameters. Tink bygelyks oan dizze ynstruksje:
t0 = phi [entry: 0:int, for.body: t6] #n
De betsjutting dêrfan is as folget: as it foarige basisblok in blok wie entry (ynfier), dan t0 is in konstante 0, en as de foarige basis blok wie for.body, dan moatte jo de wearde nimme t6 út dit blok. Dit kin allegear heul mysterieus lykje, mar dit meganisme is wat de SSA makket. Fanút in minsklik perspektyf makket dit allegear de koade lestich te begripen, mar it feit dat elke wearde mar ien kear wurdt tawiisd makket in protte optimisaasjes folle makliker.
Tink derom dat as jo jo eigen kompilator skriuwe, jo meastentiids net mei dit soarte dingen moatte omgean. Sels Clang genereart al dizze ynstruksjes net phi, it brûkt in meganisme alloca (it liket op wurkjen mei gewoane lokale fariabelen). Dan, by it útfieren fan in LLVM-optimalisaasjepas neamd , ynstruksjes alloca omboud ta SSA foarm. TinyGo ûntfangt lykwols ynput fan Go SSA, dy't, handich, al is omboud ta SSA-foarm.
In oare ynnovaasje fan it fragmint fan tuskenlizzende koade ûnder behanneling is dat tagong ta slice eleminten troch yndeks wurdt fertsjintwurdige yn 'e foarm fan in operaasje fan it berekkenjen fan it adres en in operaasje fan dereferencing de resultearjende pointer. Hjir kinne jo de direkte tafoeging fan konstanten oan 'e IR-koade sjen (bygelyks - 1:int). Yn it foarbyld mei de funksje myAdd dit is net brûkt. No't wy dizze funksjes út 'e wei hawwe, litte wy ris sjen wat dizze koade wurdt as it wurdt omboud ta LLVM IR-foarm:
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
}
Hjir kinne wy, lykas earder, deselde struktuer sjen, dy't oare syntaktyske struktueren omfettet. Bygelyks yn petearen phi wearden en labels ruile. D'r is hjir lykwols wat dat it wurdich is om spesjaal omtinken oan te jaan.
Om te begjinnen, hjir kinne jo sjen in folslein oare funksje hântekening. LLVM stipet gjin plakjes, en as gefolch, as optimisaasje, splitst de TinyGo-kompiler dy't dizze tuskenkoade generearre de beskriuwing fan dizze gegevensstruktuer yn dielen. It kin trije stik eleminten fertsjintwurdigje (ptr, len и cap) as struktuer (struct), mar it fertsjintwurdigjen fan se as trije aparte entiteiten makket it mooglik foar guon optimisaasjes. Oare gearstallers kinne it plak op oare wizen fertsjintwurdigje, ôfhinklik fan de opropkonvinsjes fan 'e funksjes fan it doelplatfoarm.
In oar nijsgjirrich skaaimerk fan dizze koade is it brûken fan de ynstruksje getelementptr (faak ôfkoarte as GEP).
Dizze ynstruksje wurket mei oanwizers en wurdt brûkt om in oanwizer nei in stik elemint te krijen. Litte wy it bygelyks fergelykje mei de folgjende koade skreaun yn C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Of mei it folgjende lykweardich oan dit:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
It wichtichste ding hjir is dat de ynstruksjes getelementptr docht gjin dereferencing operaasjes. It berekkent gewoan in nije oanwizer basearre op de besteande. It kin wurde nommen as ynstruksjes mul и add op hardware nivo. Jo kinne mear lêze oer de GEP-ynstruksjes .
In oar nijsgjirrich skaaimerk fan dizze tuskenlizzende koade is it brûken fan de ynstruksje icmp. Dit is in ynstruksje foar algemiene doelen dy't brûkt wurdt om fergelikingen te realisearjen. It resultaat fan dizze ynstruksje is altyd in wearde fan type i1 - logyske wearde. Yn dit gefal wurdt in fergeliking makke mei it kaaiwurd slt (ûndertekene minder as), sûnt wy ferlykje twa nûmers earder fertsjintwurdige troch it type int. As wy twa net-ûndertekene heule getallen fergelykje, dan soene wy brûke icmp, en it kaaiwurd dat brûkt wurdt yn 'e fergeliking soe wêze ult. Om driuwende puntnûmers te fergelykjen, wurdt in oare ynstruksje brûkt, fcmp, dy't op in fergelykbere wize wurket.
Resultaten
Ik leau dat ik yn dit materiaal de wichtichste skaaimerken fan LLVM IR haw behannele. Fansels is der in protte mear hjir. Benammen de tuskenlizzende fertsjintwurdiging fan 'e koade kin in protte annotaasjes befetsje dy't optimisaasjepasses tastean om rekken te hâlden mei bepaalde skaaimerken fan' e koade dy't bekend is oan 'e kompilator dy't net oars kinne wurde útdrukt yn IR. Dit is bygelyks in flagge inbounds GEP ynstruksjes, of flaggen nsw и nuw, dat kin wurde tafoege oan de ynstruksjes add. Itselde jildt foar it kaaiwurd private, wat oanjout foar de optimizer dat de funksje dy't it markearret net ferwiisd wurdt fan bûten de hjoeddeistige kompilaasje-ienheid. Dit soarget foar in protte nijsgjirrige ynterprosedurele optimisaasjes lykas it eliminearjen fan net brûkte arguminten.
Jo kinne mear lêze oer LLVM yn , dêr't jo faaks nei ferwize by it ûntwikkeljen fan jo eigen LLVM-basearre kompilator. Hjir , dy't sjocht nei it ûntwikkeljen fan in gearstaller foar in heul ienfâldige taal. Beide fan dizze boarnen fan ynformaasje sille nuttich wêze foar jo by it meitsjen fan jo eigen kompilator.
Dear readers! Brûk jo LLVM?
Boarne: www.habr.com