LLVM Go vaatenurgast

Kompilaatori arendamine on väga raske ülesanne. Kuid õnneks on projektide, nagu LLVM, elavdamisega see ülesanne oluliselt lihtsamaks muutunud, võimaldades isegi üksikprogrammeerijal luua uue keele, mis on jõudluse poolest C-le lähedane. Töö LLVM-iga on keeruline, kuna see süsteem sisaldab tohutul hulgal koodi, millel on vähe dokumentatsiooni. Selle puuduse parandamiseks kavatseb artikli autor, mille tõlget täna avaldame, demonstreerida Go-s kirjutatud koodinäiteid ja näidata, kuidas need kõigepealt tõlgitakse Go SSA, ja seejärel - LLVM IR-iks kasutades kompilaatorit TinyGO. Go SSA ja LLVM IR kood on veidi redigeeritud, eemaldatud on kõik, mis ei puuduta siin esitatud selgitusi, et need oleksid arusaadavamad.

Esimene näide

Esimene funktsioon, mida kavatseme siin analüüsida, on lihtne mehhanism numbrite liitmiseks:

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

See funktsioon on väga lihtne ja tõenäoliselt ei saaks midagi lihtsamat välja mõelda. See tõlgitakse järgnevaks Go SSA koodiks:

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

Sellise funktsiooni esituse korral on tüüpide vihjed paigutatud paremale; enamikul juhtudel ei pea nendele tähelepanu pöörama.

See väike näide võimaldab juba näha ühte SSA aspekti. Nimelt jagatakse koodi konverteerimisel SSA vormiks iga väljend kõige elementaarsemateks osadeks, millest see koosneb. Meie puhul käsk return a + b, kujutab tegelikult endast kaht tehte: kahe numbri liitmist ja tulemuse tagastamist.

Lisaks sellele on siit näha ka programmi baasklid, antud koodis on ainult üks blokk - sisendblokk (entry block). Räägime blokkidest lähemalt hiljem.

Go SSA kood tõlgitakse hõlpsasti 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 teisi süntaktilisi konstruktsioone, on funktsiooni struktuur põhimõtteliselt muutumatu. LLVM IR kood on pisut võimsam kui Go SSA kood, sarnanedes C-le. Siin, funktsiooni deklareerimisel, järgneb kõigepealt kirjeldus sellele, millist andmetüüpi see tagastab, ja argumendi tüüp näidatakse enne argumendi nime. Lisaks, IR-parsingu lihtsustamiseks, on globaalsete entiteetide nimede ees sümbol @, ja kohalike nimede ees on sümbol % (funktsioon loetakse samuti globaalsete entiteetideks).

Üks selle koodi omadustest, millele tuleks tähelepanu pöörata, on see, et Go tüübi esitlemise otsus int, mis võib olla 32-bitine või 64-bitine, sõltuvalt kompilaatorist ja kompileerimise eesmärgist, määratakse LLVM IR koodi loomisel. See on üks paljusid põhjuseid, miks LLVM IR kood ei ole, nagu paljud arvavad, platvormist sõltumatu. Üht platvormile loodud koodi ei saa lihtsalt võtta ja teisele platvormile kompileerida (kui ei läheneta sellele probleemile eriti ettevaatlikult).

. Veel üks huvitav punkt, mida tuleks märkida, on see, et tüüp i64 — ei ole allkirjastatud täisarv: see on neutraalne numbri tähistamise osas. Sõltuvalt käsust võib see esindada nii allkirjastatud kui ka allkirjastamata numbreid. Liitmise operatsiooni esitlemise puhul ei oma see tähtsust, seega pole siin erinevust allkirjastatud ja allkirjastamata numbrite käsitlemisel. Siinkohal tahaksin märkida, et C keeles toob allkirjastatud täisarvuvõrgu ületamine kaasa määramatut käitumist, seetõttu lisab Clangi frontend operatsioonile lipu nsw (no signed wrap), mis näitab LLVM-le, et see võib lähtuda eeldusest, et liitmisel ei toimu ületamist.

See võib olla oluline teatud optimeerimiste jaoks. Näiteks kahe i16 liitmine 32-bitisel platvormil (32-bitiste registritega) nõuab pärast liitmist allkirja laiendamise operatsiooni, et jääda vahemikku i16. Seetõttu on tihti tõhusam teostada täisarvutehteid masina registri suurusi arvesse võttes.

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

Teine näide

Järgmine näide, mida me vaatame, on pisut keerulisem. Nimelt räägime funktsioonist, mis summeerib täisarvude viilu:

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

See kood muudetakse järgnevaks 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 t0

Siit on juba näha rohkem konstruktsioone, mis on iseloomulikud koodi esitamiseks SSA vormis. Tõenäoliselt on kõige silmatorkavam omadus see, et siin puuduvad struktureeritud voosüsteemide juhtimise käsud. Voo juhtimiseks on siin ainult tingimuslikud ja tingimusteta üleminekud, ja kui arvestada seda käsku voojuhtimise käsuna, siis on ka tagastamiskäsk.

Tegelikult on tähelepanuväärne, et programm ei ole jagatud plokkideks kasutades sümboolseid kommatoote (nagu C-perekonna keeltes). See on jagatud siltide abil, mis meenutab assambleekeele ja esitatakse põhiblokkidena. SSA-s nimetatakse põhiblokkideks järjepidevaid koodijadasid, mis algavad sildist ja lõpevad põhibloki lõpetamiseks mõeldud käsklustega, nagu näiteks — return ja jump.

Veel üks huvitav detail selles koodis on käsk phi. See käsk on üsna ebatavaline ning selle mõistmiseks võib vajada aega. Pidage meeles, et SSA — on lühend Static Single Assignment. See on vahend, mida kompilaatorid kasutavad koodi esitlemiseks, kus igale muutujale antakse väärtus vaid ühe korra. See sobib suurepäraselt lihtsate funktsioonide jaoks, nagu meie funktsioon myAdd, nagu eelnevalt näidatud, kuid keerukamate funktsioonide, nagu selles jaotises käsitletud funktsioonide jaoks, ei sobi see. sum. Erinevate muutuja väärtuste muutumine toimub tsükli käigus. i ja n.

SSA ületab muutuja väärtuste ühekordse määramise piiri, kasutades niinimetatud käsku phi (nime, mis on pärit kreeka tähestikust). Nimelt, et SSA-koodi esitus saaks luua keeltele nagu C, peab rakendama teatud trikke. Käsk tagastab muutuja praeguse väärtuse (i või n), ja selle parameetriteks on põhiblokkide loend. Näiteks, vaatame sellist käsku:

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

Selle tähendus on järgmine: kui eelmine põhiblokk oli blokk entry sisse, siis t0 on konstant 0, ja kui eelmine põhiblokk oli for.body, siis tuleb võtta väärtus t6 sellelt blokilt. See võib tunduda üsna salapärane, kuid tänu sellele mehhanismile tõhusalt toimib SSA. Inimese vaatenurgast teeb see koodi arusaamise keerukaks, kuid see, et igale väärtusele määratakse väärtus vaid korra, lihtsustab oluliselt paljusid optimeerimisi.

Pange tähele, et kui te kirjutate oma kompilaatori, siis tavaliselt ei pea te selliste asjadega tegelema. I isegi Clang ei genereeri kõiki neid käsklusi phi, ta kasutab mehhanismi alloca (mis meenutab tavaliste kohalike muutujate käsitsemist). Siis, optimeerimise käigu ajal, mida nimetatakse mem2reg, käsud alloca muudetakse SSA vormi. TinyGo, aga, saab sisendi Go SSA-lt, mis on mugav, juba konverteeritud SSA vormi.

Veel üks uudsus käsitletud vahepealse koodi fragmendis on see, et juurdepääs viilu elementidele indeksi kaudu esitatakse aadressi arvutamise operaatorina ja saadud näidiku de-referentseerimise operaatorina. Siin on näha ka konstantide otsene lisamine IR-koodi (nt — 1:int). Näites koos funktsiooniga myAdd sarnast ei ole kasutatud. Nüüd, kui oleme nende eripäradega tutvunud, vaatame, kuidas see kood muutub, kui see muudetakse LLVM IR vormi:

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 ka varem, näeme sama struktuuri, mis sisaldab teisi süntaktilisi konstruktsioone. Näiteks kutses phi on vahetatud väärtused ja sildid. Siiski on siin midagi, millele tasub eraldi tähelepanu pöörata.

Esiteks, siin on näha täiesti erinev funktsiooni allkiri. LLVM ei toeta lõike, mistõttu optimeerimise tulemusena jagas TinyGo kompilaator, mis genereeris selle vahefaasi koodi, selle andmestruktuuri kirjelduse osadeks. Ta oleks võinud esitada kolm lõike elementi (ptr, len ja cap) struktuurina (struct), kuid nende esitlemine kui kolme eraldi сущности võimaldab teostada teatud optimiseerimisi. Teised kompilaatorid võivad lõike esitada veelgi muul viisil, see sõltub sihtplatvormi funktsioonide kutsumis kokkulepetest.

Teine huvitav joon selle koodi juures on käsu kasutamine getelementptr (sageli nimetatakse seda lühidalt GEP-ks).

See käsk töötab pointeritega ja seda kasutatakse lõike elemendi pointeri saamiseks. Näiteks võrrelgem seda järgmise C keeles kirjutatud koodiga:

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

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

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

Peamine asi on see, et käsk getelementptr ei teosta dereferentseerimise toiminguid. Ta ainult arvutab uue pointeri, põhinedes olemasoleval. Seda saab käsitleda nagu käsku mul ja add riistvaratasandil. Lisainfot GEP käsu kohta saab lugeda siin.

Veel üks huvitav joon selle vahefaasi koodi juures on käsu kasutamine icmp. See on juhend, mida kasutatakse täisarvude võrdlemiseks. Selle juhendi täitmise tulemuseks on alati väärtus tüübiga i1 — loogiline väärtus. Antud juhul toimub võrdlemine, kasutades märksõna slt (signaal vähem kui), kuna me võrdleme kahte numbrit, mis on varem esitatud tüübina int. Kui me võrdleksime kahte mitteallkirjastatud täisarvu, siis kasutaksime juhendina icmp, samas kui võrdlemisel kasutatav märksõna oleks ult. Ülejäänud ujuvkomaga numbrite võrdlemiseks kasutatakse teistsugust juhendit, fcmp, mis toimib sarnaselt.

Summary

Usun, et selles materjalis olen käsitlenud kõige olulisemaid LLVM IR-i omadusi. Loomulikult on veel palju muud. Eelkõige võivad vahekoodi esitluses olla mitmed annotatsioonid, mis võimaldavad optimeerimise läbimisel arvesse võtta teatud koodi omadusi, mis on kompilaatorile tuntud ja mida ei saa teisel viisil IR-is väljendada. Näiteks on see märk inbounds GEP-i juhendi puhul, või märgid nsw ja nuw, mida võib lisada juhendile add. Sama kehtib ka märksõna kohta private, mis näitab optimeerijale, et seda tähistatud funktsiooni ei kutsuta välja praegusest kompileerimise üksusest. See võimaldab läbi viia palju huvitavaid vahelisi optimeerimisi, näiteks mittekasutatavate argumentide kõrvaldamist.

Teavet LLVM-i kohta saate lugeda dokumentatsioon, millega te tihti kokku puutute, kui arendate oma LLVM-põhist kompilaatorit. Siin on juhend, mis käsitleb kompilaatori arendamist väga lihtsa keele jaoks. Need kaks allikat on teile kasulikud oma kompilaatori loomisel.

Lugupeetud lugejad! Kas kasutate LLVM-i?

Allikas: habr.com