LLVM Go vaatenurgast

Kompilaatori arendamine on väga keeruline ülesanne. Kuid õnneks on projektide nagu LLVM arenguga see probleem märgatavalt lihtsamaks muutunud, võimaldades isegi ühe mehe programmeerijal luua uue keele, mis on jõudluselt C-le lähedane. LLVM-iga töötamine on keeruline, sest see süsteem sisaldab tohutut koodihulka, mille kohta on vähe dokumentatsiooni. Käesoleva materjali autori, keda me täna esitame, eesmärk on demonstreerida Go-s kirjutatud koodinäiteid ja näidata, kuidas need kõigepealt tõlgitakse Go SSA, ja seejärel — LLVM IR-ks, kasutades kompilaatorit TinyGO. Go SSA ja LLVM IR-i kood on veidi redigeeritud ning eemaldatud on need osad, mis ei ole antud seletustega seotud, et need seletused oleksid arusaadavamad.

Esimene näide

Esimene funktsioon, mida ma siin käsitlen, on lihtne mehhanism kahe arvu liitmiseks:

func myAdd(a, b int) int{
    return a + b
}

See funktsioon on väga lihtne ning ilmselt ei ole midagi lihtsamat. See tõlgitakse järgmisse Go SSA koodi:

func myAdd(a int, b int) int:
entry:
    t0 = a + b                                                    int
    return t0

Selle funktsiooni esituse korral kuvatakse tüüpide vihjed paremal ja enamikul juhtudel võib neile mitte tähelepanu pöörata.

See väike näide võimaldab juba näha üht SSA aspekti. Nimelt, koodi konverteerimisel SSA vormi jaguneb iga väljendus oma elementaarseteks osadeks. Meie puhul on käsk return a + b, tegelikult, esindab kahte operatsiooni: kahe numbri liitmine ja tulemuse tagastamine.

Lisaks on siin nähtavad ka programmi põhiblokid, selles koodis on ainult üks blok — sissejuhatav (entry block). Blokkidest räägime lähemalt allpool.

Go SSA kood on lihtsalt konverteeritav LLVM IR-iks:

define i64 @myAdd(i64 %a, i64 %b) {
entry:
  %0 = add i64 %a, %b
  ret i64 %0
}

On võib märgata, et kuigi siin kasutatakse teistsuguseid süntaktilisi konstruktsioone, on funktsiooni struktuur peamiselt muutumatuks jäänud. LLVM IR kood on natuke tugevam kui Go SSA kood, olles sarnane C-le. Funktsiooni deklaratsioonis järgnevad esmalt tagastatava andmetüübi kirjeldus, argumentide tüüp on näidatud argumendi nime ees. Lisaks, IR-parsingu lihtsustamiseks, on globaalsete entiteetide nimede ees sümbol @, ja kohalike nimede ees sümbol % (funktsioon loetakse samuti globaalseks entiteediks).

Üks selle koodi eripära, millele tasub tähelepanu pöörata, on see, et Go tüübi esitlemise otsus int, mis võib olla esindatud 32-bitise või 64-bitise väärtusena, olenevalt kompilaatorist ja kompileerimise eesmärgist, tehakse LLVM IR koodi loomisel. See on üks paljusid põhjusi, miks LLVM IR kood ei ole, nagu paljud arvatavad, platvormist sõltumatu. Sellist koodi, mis on loodud ühe platvormi jaoks, ei saa lihtsalt võtta ja kompileerida teisele platvormile (kui mitte läheneda sellele ülesande lahendamisele erilise ettevaatusega).

Veel huvitav moment, mida tuleks märkida, on see, et tüüp i64 — ei ole signeeritud täisarv: see on numbrimärgistuse osas neutraalne. Vastavalt juhisele võib see esindada nii signeeritud kui ka mitte-signeeritud arve. Summeerimise operatsiooni puhul ei mängi see rolli, seega ei ole siin vahet signeeritud või mitte-signeeritud arvude töötlemisel. Tuleb märkida, et C keeles põhjustab signeeritud täisarvu ületäitumine määramatut käitumist, mistõttu Clangi esiplaan lisab operatsioonile lipu nsw (no signed wrap), mis näitab LLVM-le, et see võib eeldada, et summade liitmisel ei toimu kunagi ületäitumist.

See võib olla oluline mõningate optimeerimiste jaoks. Näiteks kahe i16 väärtuse liitmine 32-bitises platvormis (32-bitiste registritega) vajab pärast liitmist märke laiendamise operatsiooni, et jääda vahemikku i16. Selle tõttu on sageli efektiivsem täisarvute operatsioonide täitmine, arvestades masinaregistri suurusi.

See, mis juhtub selle IR-koodiga edasi, ei huvita meid praegu eriti. Kood optimeeritakse (kuid sellise lihtsa näite puhul, nagu meie oma, ei optimeerita enam midagi) ja seejärel muudetakse see masinkoodiks.

Teine näide

Järgmine näide, millega me tegeleme, on veidi keerulisem. Täpsemalt öeldes räägime funktsioonist, mis summeerib täisarvude slice'i:

func sum(numbers []int) int {
    n := 0
    for i := 0; i < len(numbers); i++ {
        n += numbers[i]
    }
    return n
}

See kood muudetakse järgmisesse Go SSA koodi:

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 t0

Siin on juba rohkem näha konstruktsioone, mis on iseloomulikud SSA-s vormistatud koodi esitlemisele. Eriti silmatorkav omadus selle koodi juures on see, et siin puuduvad struktureeritud käsklused arvutuste voogude juhtimiseks. Arvutuste voogude juhtimiseks on siin vaid tingimuslikud ja tingimusteta üleminekud ning kui pidada seda käsku voo juhtimise käsuks, siis on see tagasipöördumise käsk.

Tegelikult võib tähele panna, et programm ei ole plokkidesse jagatud, nagu pereliikmete C-keeltel, kasutadesid kaar- või nurksulgusid. See jaguneb siltide järgi, mis meenutab assemblerikeeli, ja on esitatud baasplokkidena. SSA-s nimetatakse baasplokkideks pidevaid koodijadasid, mis algavad sildiga ja lõppevad baasploki lõpetamise käskudega, näiteks — return ja jump.

Veel üks huvitav detail selle koodi juures on käsk phi. See käsk on üsna eriline ning selle mõistmiseks võib kuluda veidi aega. Pidage meeles, et SSA — on lühend Static Single Assignment. See on vahepealne kood esitus, mida kompilaatorid kasutavad, kus igale muutujale antakse väärtus ainult üks kord. See sobib suurepäraselt lihtsate funktsioonide, nagu meie funktsioon myAdd, nagu on näidatud eespool, kuid ei sobi keerukamate funktsioonide jaoks — nagu näiteks selle jaotise käsitletav funktsioon sum. Eelkõige muudetakse silmuse käigus muutujad i ja n.

SSA ületab piirangu, et muutujaid võib muuta ainult ühe korra, kasutades nn phi-käsku phi (tema nimi on tulnud Kreeka tähestikust). Nimelt, et SSA-koodi esitamine oleks võimalik, tuleb kasutada teatud trikke keeltes nagu C. Selle käsu kutsumise tulemus on muutuja praegune väärtus (i või n), samas kui tema parameetriteks on põhiblokkide loetelu. Näiteks vaatame sellist käsku:

t0 = phi [entry: 0:int, for.body: t6] #n

Selle sisu on järgmine: kui eelmine põhiblokk oli blokk entry (sissepääsu), siis t0 on konstant 0, ja kui eelmine põhiblokk oli for.body, siis tuleb võtta väärtus t6 sellest plokist. Kõik see võib tunduda üsna salapärane, kuid tänu sellele mehhanismile tagatakse SSA toimimine. Inimese seisukohalt muudab see koodi mõistmise keerulisemaks, kuid fakt, et iga väärtus määratakse vaid üks kord, lihtsustab palju optimeerimisi.

Pange tähele, et kui kirjutate enda kompilaatorit, siis ei pea te tavaliselt tegelema selliste asjadega. Isegi Clang ei genereeri kõiki neid käske phi, ta kasutab mehhanismi alloca (see sarnaneb tavapäraste kohalike muutujatega töötamisega). Seejärel, LLVM-i optimeerimise läbimise käigus, mis on nimetatud mem2reg, käsud alloca muudetakse SSA vormi. TinyGo saab siiski sisendi Go SSA-st, mis on mugavalt juba SSA vormi muudetud.

Veel üks uudsus antud vahepealse koodi fragmendis on see, et juurdepääs sliisi elementidele indeksi järgi on esitatud aadressi arvutamise ja saadud näidiku lahendamise operatsioonina. Siin on näha ka konstandi otsene lisamine IR-koodile (näiteks — 1:int). Näites funktsiooniga myAdd sarnaseid ei olnud kasutatud. Nüüd, kui oleme need omadused läbi vaadanud, vaatame, milliseks see kood muutub, kui see konverteeritakse LLVM IR formaati:

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
}

Siin, nagu ennegi, saame näha sama struktuuri, mis sisaldab muid süntaktilisi konstruktsioone. Näiteks on funktsiooni kutsungites phi väärtused ja silbid omavahel vahetanud. Siiski on siin ka midagi, millele tasub erilist tähelepanu pöörata.

Esiteks, siin on täiesti erinev funktsiooni signatuur. LLVM ei toeta lõike, mistõttu optimeerimise käigus jagas TinyGo kompilaator, mis genereeris selle vahe- koodi, nende andmestruktuuride kirjelduse osadeks. Ta oleks võinud esitada kolm lõike elementi (ptr, len ja cap) struktuuri (struct), kuid nende esitlemine kolmeks eraldi üksuseks võimaldab teatud optimeerimisi. Teised kompilaatorid võivad viilutust esitada ka muul viisil, sõltuvalt sihtplatvormi funktsiooni kutsumise kokkulepetest.

Veel ühe huvitava omadusena on selle koodi kasutamine getelementptr (sageli lühendatakse GEP-iks).

See käsk töötab osutitega ja seda kasutatakse viilu elemendi osutaja saamiseks. Näiteks, vaatame, kuidas see sobitub järgmise C keeles kirjutatud koodiga:

int* sliceptr(int *ptr, int index) {
   return &ptr[index];
}

Või järgmise, mis on sellele ekvivalentne:

int* sliceptr(int *ptr, int index) {
   return ptr + index;
}

Peamine asi siin on see, et käsk getelementptr ei teosta dereferentseerimise operatsioone. See arvutab vaid uue osutaja, tuginedes olemasolevale. Seda võib tõlgendada käskudena mul ja add riistvara tasemel. GEP käsu kohta võib lugeda rohkem üksikasju. siit.

Veel üks huvitav omadus sellest vahekoodeksist on käsku icmp. See on üldine juhend, mida kasutatakse täisarvude võrdlemise teostamiseks. Selle käsu täitmise tulemus on alati tüüpi väärtus i1 — loogiline väärtus. Antud juhul toimub võrdlemine märksõna slt (signed less than) abil, kuna võrreldavad on kaks arvu, mis on varem esitatud tüüpi int. Kui me oleksime võrrelnud kahte mitte-märgiga täisarvu, oleksime kasutanud icmp, samas kui võrdlemisel oleks märksõna ult. Tõhusate liikuvate punktide võrdlemiseks kasutatakse muud käsku, fcmp, mis töötab sarnaselt.

Kokkuvõte

Arvan, et selles materjalis olen käsitlenud LLVM IR-i kõige olulisemaid omadusi. Loomulikult on siin veel palju muud. Eelkõige võivad vahepealse koodi esitus sisaldada mitmeid annotatsioone, mis võimaldavad optimeerimise käikudel arvesse võtta teatud koodi omadusi, mis on kompilaatorile teada ja mida ei saa muul viisil IR-is väljendada. Näiteks on see lipp inbounds GEP-käskluses, või lipud nsw ja nuw, mis võivad olla lisatud käsule add. Sama kehtib ka märksõna private, näidates optimeerijale, et tähistatud funktsiooni ei kutsuta käesoleva kompileerimise ühikust välja. See võimaldab teha mitmeid huvitavaid vaheprotseduurilisi optimeerimisi, nagu kasutamata argumentide eemaldamine.

LLVM kohta saab rohkem lugeda dokumentatsioonis, mille poole te sageli pöördute, arendades oma kompilaatorit, mis põhineb LLVM. Siin on juhend, kus käsitletakse kompilaatori arendust väga lihtsa keele jaoks. Need kaks allikat on kasulikud oma kompilaatori loomisel.

Lugupidamisega lugejad! Kas kasutate LLVM?

Allikas: habr.com