ProHoster > Blogs > Administrācija > LLVM no Go perspektīvas

LLVM no Go perspektīvas

Kompilatora izstrāde ir ļoti grÅ«ts uzdevums. Bet, par laimi, attÄ«stot tādus projektus kā LLVM, Ŕīs problēmas risinājums ir ievērojami vienkārÅ”ots, kas ļauj pat vienam programmētājam izveidot jaunu valodu, kas pēc veiktspējas ir tuva C. Darbu ar LLVM sarežģī fakts, ka Å”is sistēma ir attēlota ar milzÄ«gu koda daudzumu, kas aprÄ«kots ar nelielu dokumentāciju. Lai mēģinātu labot Å”o trÅ«kumu, materiāla, kura tulkojumu mēs Å”odien publicējam, autors demonstrēs Go rakstÄ«tā koda piemērus un parādÄ«s, kā tie pirmo reizi tiek tulkoti Dodieties uz SSA, un pēc tam LLVM IR, izmantojot kompilatoru tinyGO. Go SSA un LLVM IR kods ir nedaudz rediģēts, lai noņemtu lietas, kas nav saistÄ«tas ar Å”eit sniegtajiem paskaidrojumiem, lai padarÄ«tu skaidrojumus saprotamākus.

LLVM no Go perspektīvas

Pirmais piemērs

Pirmā funkcija, ko es Ŕeit apskatīŔu, ir vienkārŔs skaitļu pievienoŔanas mehānisms:

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

Å Ä« funkcija ir ļoti vienkārÅ”a, un, iespējams, nekas nevar bÅ«t vienkārŔāks. Tas tiek tulkots Ŕādā Go SSA kodā:

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

Šajā skatā datu tipu padomi tiek novietoti labajā pusē, un vairumā gadījumu tos var ignorēt.

Å is nelielais piemērs jau ļauj saskatÄ«t viena SSA aspekta bÅ«tÄ«bu. Proti, pārvērÅ”ot kodu SSA formā, katra izteiksme tiek sadalÄ«ta elementārākajās daļās, no kurām tā sastāv. MÅ«su gadÄ«jumā komanda return a + b, patiesÄ«bā, ir divas darbÄ«bas: divu skaitļu pievienoÅ”ana un rezultāta atgrieÅ”ana.

Turklāt Å”eit jÅ«s varat redzēt programmas pamata blokus, Å”ajā kodā ir tikai viens bloks - ievades bloks. Tālāk mēs runāsim vairāk par blokiem.

Go SSA kods viegli pārvērÅ”as par LLVM IR:

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

Var pamanÄ«t, ka, lai gan Å”eit tiek izmantotas dažādas sintaktiskās struktÅ«ras, funkcijas struktÅ«ra bÅ«tÄ«bā nemainās. LLVM IR kods ir nedaudz spēcÄ«gāks par Go SSA kodu, lÄ«dzÄ«gi kā C. Å eit funkcijas deklarācijā vispirms ir aprakstÄ«ts datu tips, kuru tas atgriež, argumenta tips ir norādÄ«ts pirms argumenta nosaukuma. Turklāt, lai vienkārÅ”otu IS parsÄ“Å”anu, pirms globālo entÄ«tiju nosaukumiem ir simbols @, un pirms vietējiem nosaukumiem ir simbols % (funkcija tiek uzskatÄ«ta arÄ« par globālu entÄ«tiju).

Viena lieta, kas jāņem vērā Å”ajā kodā, ir Go tipa reprezentācijas lēmums int, ko var attēlot kā 32 bitu vai 64 bitu vērtÄ«bu atkarÄ«bā no kompilatora un kompilācijas mērÄ·a, tiek pieņemts, kad LLVM Ä£enerē IR kodu. Tas ir viens no daudzajiem iemesliem, kāpēc LLVM IR kods nav, kā daudzi cilvēki domā, no platformas neatkarÄ«gs. Šādu kodu, kas izveidots vienai platformai, nevar vienkārÅ”i paņemt un kompilēt citai platformai (ja vien jÅ«s neesat piemērots Ŕīs problēmas risināŔanai ar ārkārtÄ«gu rÅ«pÄ«bu).

Vēl viens interesants punkts, ko vērts atzÄ«mēt, ir tas, ka veids i64 nav vesels skaitlis ar zÄ«mi: tas ir neitrāls skaitļa zÄ«mes attēlojuma ziņā. AtkarÄ«bā no instrukcijas tas var attēlot gan parakstÄ«tus, gan neparakstÄ«tus numurus. PievienoÅ”anas darbÄ«bas attēlojuma gadÄ«jumā tam nav nozÄ«mes, tāpēc nav atŔķirÄ«bas darbā ar skaitļiem ar parakstÄ«tiem vai neparakstÄ«tiem numuriem. Å eit es vēlos atzÄ«mēt, ka C valodā mainÄ«gā ar zÄ«mi pārpildÄ«Å”ana noved pie nedefinētas darbÄ«bas, tāpēc Clang priekÅ”gals pievieno darbÄ«bai karodziņu. nsw (bez paraksta iesaiņojuma), kas norāda LLVM, ka tā var pieņemt, ka pievienoÅ”ana nekad nepārplÅ«st.

Tas var bÅ«t svarÄ«gi dažām optimizācijām. Piemēram, pievienojot divas vērtÄ«bas i16 32 bitu platformā (ar 32 bitu reÄ£istriem) pēc pievienoÅ”anas ir nepiecieÅ”ama zÄ«mes paplaÅ”ināŔanas darbÄ«ba, lai paliktu diapazonā i16. Å Ä« iemesla dēļ bieži vien ir efektÄ«vāk veikt darbÄ«bas ar veseliem skaitļiem, pamatojoties uz maŔīnu reÄ£istra izmēriem.

Tas, kas notiek tālāk ar Å”o IR kodu, mÅ«s Å”obrÄ«d Ä«paÅ”i neinteresē. Kods tiek optimizēts (bet tāda vienkārÅ”a piemēra kā mÅ«su gadÄ«jumā nekas netiek optimizēts) un pēc tam pārveidots maŔīnkodā.

Otrais piemērs

Nākamais piemērs, ko mēs apskatīsim, būs nedaudz sarežģītāks. Proti, mēs runājam par funkciju, kas summē veselu skaitļu daļu:

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

Šis kods tiek pārveidots par Ŕādu Go SSA kodu:

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

Å eit jau var redzēt vairāk konstrukcijas, kas raksturÄ«gas koda attēloÅ”anai SSA formā. Iespējams, ka Ŕī koda acÄ«mredzamākā iezÄ«me ir fakts, ka nav strukturētu plÅ«smas vadÄ«bas komandu. Lai kontrolētu aprēķinu plÅ«smu, ir tikai nosacÄ«juma un beznosacÄ«juma lēcieni, un, ja mēs uzskatām Å”o komandu par komandu plÅ«smas kontrolei, tad atgrieÅ”anās komanda.

Faktiski Å”eit jÅ«s varat pievērst uzmanÄ«bu tam, ka programma nav sadalÄ«ta blokos, izmantojot cirtainus lencēs (kā C valodu saimē). Tas ir sadalÄ«ts ar etiÄ·etēm, kas atgādina montāžas valodas, un tiek parādÄ«ts pamata bloku veidā. SSA pamata bloki tiek definēti kā blakus esoÅ”as koda secÄ«bas, kas sākas ar etiÄ·eti un beidzas ar pamata bloka pabeigÅ”anas instrukcijām, piemēram, - return Šø jump.

Vēl viena interesanta Ŕī koda detaļa ir attēlota instrukcijā phi. NorādÄ«jumi ir diezgan neparasti, un to izpratne var aizņemt kādu laiku. atcerieties, ka SSA ir saÄ«sinājums no Static Single Assignment. Å is ir kompilatoru izmantotā koda starpposma attēlojums, kurā katram mainÄ«gajam tiek pieŔķirta vērtÄ«ba tikai vienu reizi. Tas ir lieliski piemērots tādu vienkārÅ”u funkciju izteikÅ”anai kā mÅ«su funkcija myAddparādÄ«ts iepriekÅ”, bet nav piemērots sarežģītākām funkcijām, piemēram, Å”ajā sadaļā apskatÄ«tajai funkcijai sum. Konkrēti, mainÄ«gie mainās cilpas izpildes laikā i Šø n.

SSA apiet ierobežojumu vienreiz pieŔķirt mainÄ«gās vērtÄ«bas, izmantojot tā saukto instrukciju phi (tā nosaukums ir ņemts no grieÄ·u alfabēta). Fakts ir tāds, ka, lai SSA koda attēlojums tiktu Ä£enerēts tādām valodām kā C, jums ir jāizmanto daži triki. Å Ä«s instrukcijas izsaukÅ”anas rezultāts ir mainÄ«gā (i vai n), un kā tā parametri tiek izmantots pamata bloku saraksts. Piemēram, apsveriet Å”o instrukciju:

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

Tā nozÄ«me ir Ŕāda: ja iepriekŔējais pamatbloks bija bloks entry (ievade), tad t0 ir konstante 0, un ja iepriekŔējais pamatbloks bija for.body, tad jums ir jāņem vērtÄ«ba t6 no Ŕī bloka. Tas viss var Ŕķist diezgan noslēpumaini, taču Å”is mehānisms ir tas, kas liek SSA darboties. No cilvēka viedokļa tas viss padara kodu grÅ«ti saprotamu, taču fakts, ka katra vērtÄ«ba tiek pieŔķirta tikai vienu reizi, daudzu optimizāciju padara daudz vienkārŔāku.

Ņemiet vērā, ka, rakstot pats savu kompilatoru, jums parasti nebÅ«s jāsaskaras ar Ŕāda veida lietām. Pat Clang neÄ£enerē visus Å”os norādÄ«jumus phi, tas izmanto mehānismu alloca (tas atgādina darbu ar parastajiem vietējiem mainÄ«gajiem). Pēc tam, palaižot, tiek izsaukta LLVM optimizācijas caurlaide mem2reg, instrukcijas alloca pārveidots SSA formā. Tomēr TinyGo saņem ievadi no Go SSA, kas ērti jau ir pārveidota SSA formā.

Vēl viens aplÅ«kojamā starpposma koda fragmenta jauninājums ir tāds, ka piekļuve Ŕķēluma elementiem pēc indeksa tiek attēlota kā adreses aprēķināŔanas operācija un iegÅ«tā rādÄ«tāja atsauces atcelÅ”anas darbÄ«ba. Å eit jÅ«s varat redzēt tieÅ”u konstantu pievienoÅ”anu IR kodam (piemēram - 1:int). Piemērā ar funkciju myAdd Å”is nav izmantots. Tagad, kad Ŕīs funkcijas vairs nav pieejamas, apskatÄ«sim, kāds kods kļūst, kad tas tiek pārveidots par LLVM IR formu:

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
}

Å eit, tāpat kā iepriekÅ”, mēs varam redzēt to paÅ”u struktÅ«ru, kas ietver citas sintaktiskās struktÅ«ras. Piemēram, zvanos phi vērtÄ«bas un etiÄ·etes apmainÄ«tas. Tomēr Å”eit ir kaut kas, kam ir vērts pievērst Ä«paÅ”u uzmanÄ«bu.

Sākumā Å”eit jÅ«s varat redzēt pavisam citu funkcijas parakstu. LLVM neatbalsta slāņus, un tā rezultātā TinyGo kompilators, kas Ä£enerēja Å”o starpkodu, sadalÄ«ja Ŕīs datu struktÅ«ras aprakstu daļās. Tas varētu attēlot trÄ«s Ŕķēles elementus (ptr, len Šø cap) kā struktÅ«ru (struct), taču to attēloÅ”ana kā trÄ«s atseviŔķas entÄ«tijas ļauj veikt dažas optimizācijas. Citi kompilatori var attēlot Ŕķēli citos veidos atkarÄ«bā no mērÄ·a platformas funkciju izsaukÅ”anas konvencijām.

Vēl viena interesanta Ŕī koda iezÄ«me ir instrukcijas izmantoÅ”ana getelementptr (bieži saÄ«sināts kā GEP).

Å Ä« instrukcija darbojas ar rādÄ«tājiem un tiek izmantota, lai iegÅ«tu rādÄ«tāju uz Ŕķēluma elementu. Piemēram, salÄ«dzināsim to ar Ŕādu kodu, kas rakstÄ«ts C:

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

Vai ar Ŕo ekvivalentu:

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

VissvarÄ«gākais Å”eit ir instrukcijas getelementptr neveic atsauces atcelÅ”anas darbÄ«bas. Tas tikai aprēķina jaunu rādÄ«tāju, pamatojoties uz esoÅ”o. To var uztvert kā norādÄ«jumus mul Šø add aparatÅ«ras lÄ«menÄ«. JÅ«s varat lasÄ«t vairāk par GEP instrukcijām Å”eit.

Vēl viena interesanta Ŕī starpkoda Ä«paŔība ir instrukcijas izmantoÅ”ana icmp. Å Ä« ir vispārÄ«ga instrukcija, ko izmanto, lai Ä«stenotu veselu skaitļu salÄ«dzinājumus. Å Ä«s instrukcijas rezultāts vienmēr ir tipa vērtÄ«ba i1 ā€” loÄ£iskā vērtÄ«ba. Å ajā gadÄ«jumā salÄ«dzinājums tiek veikts, izmantojot atslēgvārdu slt (parakstÄ«ts mazāk nekā), jo mēs salÄ«dzinām divus skaitļus, kurus iepriekÅ” attēloja tips int. Ja mēs salÄ«dzinātu divus neparakstÄ«tus veselus skaitļus, tad mēs izmantotu icmp, un salÄ«dzināŔanā izmantotais atslēgvārds bÅ«tu ult. Lai salÄ«dzinātu peldoŔā komata skaitļus, tiek izmantota cita instrukcija, fcmp, kas darbojas lÄ«dzÄ«gi.

Rezultāti

Uzskatu, ka Å”ajā materiālā esmu apskatÄ«jis svarÄ«gākās LLVM IR iezÄ«mes. Protams, Å”eit ir daudz vairāk. Konkrēti, koda starpposma attēlojums var saturēt daudzas anotācijas, kas ļauj optimizācijas gaitā ņemt vērā noteiktas kompilatoram zināmas koda iezÄ«mes, kuras citādi nevar izteikt IR. Piemēram, tas ir karogs inbounds GEP instrukcijas vai karodziņi nsw Šø nuw, ko var pievienot instrukcijām add. Tas pats attiecas uz atslēgvārdu private, norādot optimizētājam, ka tā atzÄ«mētā funkcija netiks atsaukta ārpus paÅ”reizējās kompilācijas vienÄ«bas. Tas ļauj veikt daudzas interesantas starpprocedÅ«ru optimizācijas, piemēram, novērst neizmantotos argumentus.

Vairāk par LLVM varat lasÄ«t dokumentācija, uz kuru jÅ«s bieži atsauksities, izstrādājot savu uz LLVM balstÄ«tu kompilatoru. Å eit vadÄ«ba, kurā aplÅ«kota kompilatora izstrāde ļoti vienkārÅ”ai valodai. Abi Å”ie informācijas avoti jums noderēs, veidojot savu kompilatoru.

Cienījamie lasītāji! Vai jūs izmantojat LLVM?

LLVM no Go perspektīvas

Avots: www.habr.com

Pievieno komentāru