Kompilaatori arendamine on väga raske ülesanne. Kuid õnneks on LLVM-i sarnaste projektide arendamisel selle probleemi lahendus oluliselt lihtsustatud, mis võimaldab isegi üksikul programmeerijal luua uue keele, mis on jõudluses C-le lähedane. Töö LLVM-iga muudab keeruliseks asjaolu, et süsteemi esindab tohutu hulk koodi, mis on varustatud vähese dokumentatsiooniga. Selle puuduse parandamiseks demonstreerib materjali, mille tõlke me täna avaldame, autor Go-ga kirjutatud koodi näiteid ja näitab, kuidas need esmakordselt tõlgitakse ja seejärel LLVM IR-s, kasutades kompilaatorit . Go SSA ja LLVM IR koodi on veidi muudetud, et eemaldada asjad, mis siin toodud selgitustega ei puutu, et selgitused oleks arusaadavad.
Esimene näide
Esimene funktsioon, mida ma siin vaatan, on lihtne numbrite lisamise mehhanism:
func myAdd(a, b int) int{
return a + b
}See funktsioon on väga lihtne ja võib-olla pole midagi lihtsamat. See tõlgitakse järgmiseks Go SSA koodiks:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Selle vaate puhul on andmetüübi vihjed paigutatud paremale ja neid saab enamikul juhtudel ignoreerida.
See väike näide võimaldab juba näha SSA ühe aspekti olemust. Nimelt jagatakse koodi SSA-vormingusse teisendamisel iga avaldis kõige elementaarsemateks osadeks, millest see koosneb. Meie puhul käsk return a + b, esindab tegelikult kahte toimingut: kahe arvu liitmist ja tulemuse tagastamist.
Lisaks näete siin programmi põhiplokke, selles koodis on ainult üks plokk - sisestusplokk. Allpool räägime plokkidest lähemalt.
Go SSA kood teisendab hõlpsalt LLVM IR-ks:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Võite märgata, et kuigi siin kasutatakse erinevaid süntaktilisi struktuure, on funktsiooni struktuur põhimõtteliselt muutumatu. LLVM IR kood on veidi tugevam kui Go SSA kood, sarnaselt C-ga. Siin on funktsiooni deklaratsioonis esmalt selle tagastatava andmetüübi kirjeldus, argumendi tüüp näidatakse enne argumendi nime. Lisaks on IR-parsimise lihtsustamiseks globaalsete üksuste nimede ees sümbol @, ja kohalike nimede ees on sümbol % (funktsiooni peetakse ka globaalseks olemiks).
Üks asi, mida selle koodi puhul tähele panna, on see, et Go tüübi esitusotsus int, mida võib olenevalt kompilaatorist ja kompileerimise sihtmärgist esitada 32- või 64-bitise väärtusena, aktsepteeritakse, kui LLVM genereerib IR-koodi. See on üks paljudest põhjustest, miks LLVM IR-kood ei ole, nagu paljud arvavad, platvormist sõltumatu. Sellist ühele platvormile loodud koodi ei saa lihtsalt võtta ja kompileerida teisele platvormile (kui te ei sobi selle probleemi lahendamiseks ).
Veel üks huvitav punkt, mis väärib märkimist, on see, et tüüp i64 ei ole märgiga täisarv: see on arvu märgi esitamise mõttes neutraalne. Olenevalt juhisest võib see tähistada nii märgiga kui ka märgita numbreid. Liitmistehte esituse puhul pole sellel tähtsust, seega pole märgilise või märgita numbritega töötamisel vahet. Siinkohal tahaksin märkida, et C-keeles põhjustab märgilise täisarvu muutuja ületäitumine määratlemata käitumist, nii et Clangi kasutajaliides lisab toimingule lipu nsw (no signed wrap), mis ütleb LLVM-ile, et ta võib eeldada, et lisamine ei tule kunagi üle.
See võib mõne optimeerimise jaoks olla oluline. Näiteks kahe väärtuse lisamine i16 32-bitisel platvormil (32-bitiste registritega) nõuab vahemikus püsimiseks pärast lisamist märgilaiendustoimingut i16. Seetõttu on sageli efektiivsem teha täisarvulisi toiminguid masinaregistri suuruste põhjal.
Mis selle IR-koodiga edasi saab, ei paku meile praegu erilist huvi. Kood optimeeritakse (aga meiesuguse lihtsa näite puhul ei optimeerita midagi) ja teisendatakse seejärel masinkoodiks.
Teine näide
Järgmine näide, mida me vaatame, on veidi keerulisem. Nimelt räägime funktsioonist, mis summeerib täisarvude lõigu:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}See kood teisendab järgmiseks Go SSA koodiks:
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 t0Siin on juba näha rohkem SSA vormis koodi esitamiseks omaseid konstruktsioone. Võib-olla on selle koodi kõige ilmsem omadus asjaolu, et puuduvad struktureeritud voo juhtimise käsud. Arvutuste voo juhtimiseks on ainult tingimuslikud ja tingimusteta hüpped ning kui käsitleme seda käsku voo juhtimise käsuna, siis tagasikäsku.
Tegelikult võite siin pöörata tähelepanu asjaolule, et programm ei ole jaotatud plokkideks, kasutades lokkis sulgusid (nagu C-keelte perekonnas). See on jagatud montaažikeeli meenutavate siltidega ja esitatud põhiplokkide kujul. SSA-s defineeritakse põhiplokke kui külgnevaid koodijadasid, mis algavad sildiga ja lõpevad põhiliste ploki lõpetamise juhistega, näiteks - return и jump.
Selle koodi veel üks huvitav detail on esitatud juhises phi. Juhised on üsna ebatavalised ja nende mõistmine võib võtta aega. mäleta seda on lühend sõnast Static Single Assignment. See on kompilaatorite kasutatava koodi vahepealne esitus, milles igale muutujale omistatakse väärtus ainult üks kord. See on suurepärane lihtsate funktsioonide, näiteks meie funktsiooni väljendamiseks myAddülal näidatud, kuid ei sobi keerukamate funktsioonide jaoks, nagu selles jaotises käsitletud funktsioon sum. Eelkõige muutuvad tsükli täitmise ajal muutujad i и n.
SSA möödub muutujate väärtuste ühekordse määramise piirangust, kasutades niinimetatud juhiseid phi (selle nimi on võetud kreeka tähestikust). Fakt on see, et koodi SSA esituse genereerimiseks selliste keelte jaoks nagu C, peate kasutama mõningaid nippe. Selle käsu kutsumise tulemuseks on muutuja (i või n) ja selle parameetritena kasutatakse põhiplokkide loendit. Näiteks kaaluge seda juhist:
t0 = phi [entry: 0:int, for.body: t6] #n
Selle tähendus on järgmine: kui eelmine põhiplokk oli plokk entry (sisend), siis t0 on konstant 0, ja kui eelmine põhiplokk oli for.body, siis peate võtma väärtuse t6 sellest plokist. See kõik võib tunduda üsna salapärane, kuid see mehhanism paneb SSA tööle. Inimese vaatenurgast muudab see kõik koodi raskesti mõistetavaks, kuid asjaolu, et iga väärtus määratakse ainult üks kord, muudab paljud optimeerimised palju lihtsamaks.
Pange tähele, et kui kirjutate oma kompilaatori, ei pea te tavaliselt selliste asjadega tegelema. Isegi Clang ei genereeri kõiki neid juhiseid phi, see kasutab mehhanismi alloca (see meenutab tavaliste kohalike muutujatega töötamist). Seejärel kutsutakse käivitamisel LLVM-i optimeerimispass , juhised alloca teisendati SSA vormiks. TinyGo saab aga sisendi Go SSA-lt, mis on mugavalt teisendatud juba SSA-vormingusse.
Teiseks vaadeldava vahekoodi fragmendi uuenduseks on see, et indeksi kaudu juurdepääs viiluelementidele on esitatud aadressi arvutamise toiminguna ja saadud osuti viitamise tühistamise operatsioonina. Siin näete konstantide otsest lisamist IR-koodile (näiteks - 1:int). Näites funktsiooniga myAdd seda pole kasutatud. Nüüd, kui oleme need funktsioonid käest jätnud, vaatame, mis sellest koodist saab, kui see teisendatakse LLVM IR-vormingusse:
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
}
Siin, nagu varemgi, näeme sama struktuuri, mis hõlmab ka teisi süntaktilisi struktuure. Näiteks kõnedes phi väärtused ja sildid vahetatud. Siiski on siin midagi, millele tasub erilist tähelepanu pöörata.
Alustuseks näete siin täiesti erinevat funktsiooni allkirja. LLVM ei toeta lõikusid ja selle tulemusena jagas selle vahepealse koodi genereerinud TinyGo kompilaator selle andmestruktuuri kirjelduse osadeks. See võib esindada kolme viilu elementi (ptr, len и cap) struktuurina (struct), kuid nende esitamine kolme eraldi olemina võimaldab mõningaid optimeerimisi. Teised kompilaatorid võivad lõiku esindada muul viisil, olenevalt sihtplatvormi funktsioonide kutsumistavast.
Selle koodi teine huvitav omadus on juhise kasutamine getelementptr (sageli lühendatult GEP).
See juhend töötab osutitega ja seda kasutatakse viiluelemendile viidava viida saamiseks. Näiteks võrdleme seda järgmise koodiga, mis on kirjutatud C-s:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Või sellele järgmise ekvivalendiga:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
Kõige tähtsam on siin juhised getelementptr ei teosta viitamise tühistamise toiminguid. See lihtsalt arvutab uue osuti olemasoleva põhjal. Seda võib võtta juhisena mul и add riistvara tasemel. Lisateavet GEP-i juhiste kohta saate lugeda .
Selle vahepealse koodi teine huvitav omadus on juhise kasutamine icmp. See on üldotstarbeline juhend, mida kasutatakse täisarvude võrdlemiseks. Selle juhise tulemuseks on alati tüübi väärtus i1 — loogiline väärtus. Sel juhul tehakse võrdlus märksõna abil slt (märgiga vähem kui), kuna me võrdleme kahte varem tüübiga esindatud arvu int. Kui me võrdleksime kahte märgita täisarvu, siis kasutaksime icmp, ja võrdluses kasutatav märksõna oleks ult. Ujukomaarvude võrdlemiseks kasutatakse teist juhendit, fcmp, mis töötab sarnaselt.
Tulemused
Usun, et selles materjalis olen käsitlenud LLVM IR-i kõige olulisemaid omadusi. Muidugi on siin palju muudki. Eelkõige võib koodi vahepealne esitus sisaldada palju märkusi, mis võimaldavad optimeerimiskäikudel võtta arvesse teatud kompilaatorile teadaolevaid koodi omadusi, mida muidu IR-s väljendada ei saa. Näiteks on see lipp inbounds GEP juhised või lipud nsw и nuw, mille saab juhendile lisada add. Sama kehtib ka märksõna kohta private, mis näitab optimeerijale, et selle märgistatud funktsioonile ei viidata väljastpoolt praegust kompileerimisüksust. See võimaldab palju huvitavaid protseduuridevahelisi optimeerimisi, näiteks kasutamata argumentide kõrvaldamist.
Lisateavet LLVM-i kohta saate lugeda , millele oma LLVM-põhise kompilaatori arendamisel sageli viitate. Siin , mis vaatleb väga lihtsa keele jaoks kompilaatori väljatöötamist. Mõlemad teabeallikad on teile oma kompilaatori loomisel kasulikud.
Kallid lugejad! Kas kasutate LLVM-i?
Allikas: www.habr.com