L-iżvilupp ta' kompilatur huwa kompitu diffiċli ħafna. Iżda, fortunatament, bl-iżvilupp ta 'proġetti bħal LLVM, is-soluzzjoni għal din il-problema hija ssimplifikata ħafna, li tippermetti anke programmatur wieħed li joħloq lingwa ġdida li hija qrib fil-prestazzjoni C. Il-ħidma ma' LLVM hija kkumplikata mill-fatt li dan sistema hija rappreżentata minn ammont kbir ta 'kodiċi, mgħammra bi ftit dokumentazzjoni . Sabiex jipprova jikkoreġi dan in-nuqqas, l-awtur tal-materjal, li t-traduzzjoni tiegħu qed nippubblikaw illum, se juri eżempji ta’ kodiċi miktuba f’Go u juri kif l-ewwel jiġu tradotti f’ , u mbagħad f'LLVM IR billi tuża l-kompilatur . Il-kodiċi Go SSA u LLVM IR ġie editjat kemmxejn biex jitneħħew affarijiet li mhumiex rilevanti għall-ispjegazzjonijiet mogħtija hawn, sabiex l-ispjegazzjonijiet jinftiehmu aktar.
L-ewwel eżempju
L-ewwel funzjoni li ser inħares lejha hawn hija mekkaniżmu sempliċi biex inżidu n-numri:
func myAdd(a, b int) int{
return a + b
}Din il-funzjoni hija sempliċi ħafna, u, forsi, xejn ma jista 'jkun aktar sempliċi. Jissarraf fil-kodiċi Go SSA li ġej:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0B'din il-fehma, il-ħjiel tat-tip tad-dejta jitqiegħdu fuq il-lemin u jistgħu jiġu injorati f'ħafna każijiet.
Dan l-eżempju żgħir diġà jippermettilek tara l-essenza ta 'aspett wieħed tal-SSA. Jiġifieri, meta tikkonverti l-kodiċi f'forma SSA, kull espressjoni hija maqsuma fil-partijiet l-aktar elementari li hija komposta minnhom. Fil-każ tagħna, il-kmand return a + b, fil-fatt, tirrappreżenta żewġ operazzjonijiet: li żżid żewġ numri u tirritorna r-riżultat.
Barra minn hekk, hawn tista 'tara l-blokki bażiċi tal-programm; f'dan il-kodiċi hemm blokka waħda biss - il-blokk tad-dħul. Aħna ser nitkellmu aktar dwar blokki hawn taħt.
Il-kodiċi Go SSA faċilment jikkonverti għal LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Dak li tista 'tinnota huwa li għalkemm strutturi sintattiċi differenti huma użati hawn, l-istruttura tal-funzjoni hija bażikament l-istess. Il-kodiċi LLVM IR huwa ftit aktar b'saħħtu mill-kodiċi Go SSA, simili għal C. Hawnhekk, fid-dikjarazzjoni tal-funzjoni, l-ewwel hemm deskrizzjoni tat-tip ta 'dejta li jirritorna, it-tip tal-argument huwa indikat qabel l-isem tal-argument. Barra minn hekk, biex tissimplifika l-parsing IR, l-ismijiet tal-entitajiet globali huma preċeduti mis-simbolu @, u qabel l-ismijiet lokali hemm simbolu % (funzjoni titqies ukoll bħala entità globali).
Ħaġa waħda li wieħed jinnota dwar dan il-kodiċi hija li d-deċiżjoni tar-rappreżentazzjoni tat-tip Go int, li jista 'jiġi rappreżentat bħala valur ta' 32-bit jew 64-bit, skond il-kompilatur u l-mira tal-kumpilazzjoni, huwa aċċettat meta LLVM jiġġenera l-kodiċi IR. Din hija waħda mill-ħafna raġunijiet li l-kodiċi LLVM IR mhuwiex, kif jaħsbu ħafna nies, indipendenti mill-pjattaforma. Kodiċi bħal dan, maħluq għal pjattaforma waħda, ma jistax sempliċement jittieħed u kkumpilat għal pjattaforma oħra (sakemm ma tkunx adattat biex issolvi din il-problema ).
Punt ieħor interessanti ta 'min jinnota huwa li t-tip i64 mhuwiex numru sħiħ iffirmat: huwa newtrali f'termini li jirrappreżenta s-sinjal tan-numru. Skont l-istruzzjoni, tista' tirrappreżenta kemm numri ffirmati kif ukoll mhux iffirmati. Fil-każ tar-rappreżentazzjoni tal-operazzjoni ta 'żieda, dan ma jimpurtax, għalhekk m'hemm l-ebda differenza fil-ħidma b'numri ffirmati jew mhux iffirmati. Hawnhekk nixtieq ninnota li fil-lingwa C, overflowing varjabbli numru sħiħ iffirmat iwassal għal imġieba mhux definita, għalhekk il-frontend Clang iżid bandiera għall-operazzjoni nsw (l-ebda wrap iffirmat), li jgħid lil LLVM li jista' jassumi li ż-żieda qatt ma tfur.
Dan jista 'jkun importanti għal xi ottimizzazzjonijiet. Per eżempju, żżid żewġ valuri i16 fuq pjattaforma ta’ 32 bit (b’reġistri ta’ 32 bit) teħtieġ, wara żieda, operazzjoni ta’ espansjoni tas-sinjali sabiex tibqa’ fil-medda i16. Minħabba dan, ħafna drabi huwa aktar effiċjenti li jitwettqu operazzjonijiet sħaħ ibbażati fuq id-daqsijiet tar-reġistru tal-magni.
X'jiġri wara b'dan il-kodiċi IR mhuwiex ta 'interess partikolari għalina issa. Il-kodiċi huwa ottimizzat (iżda fil-każ ta 'eżempju sempliċi bħal tagħna, xejn mhu ottimizzat) u mbagħad ikkonvertit f'kodiċi tal-magni.
It-tieni eżempju
L-eżempju li jmiss li ser inħarsu lejh se jkun ftit aktar ikkumplikat. Jiġifieri, qed nitkellmu dwar funzjoni li tiġbor slice ta 'numri interi:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Dan il-kodiċi jikkonverti għall-kodiċi Go SSA li ġej:
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 t0Hawnhekk diġà tista 'tara aktar kostruzzjonijiet tipiċi għar-rappreżentazzjoni tal-kodiċi fil-formola SSA. Forsi l-aktar karatteristika ovvja ta 'dan il-kodiċi hija l-fatt li m'hemm l-ebda kmandi strutturati ta' kontroll tal-fluss. Biex tikkontrolla l-fluss tal-kalkoli, hemm biss qbiż kundizzjonali u inkondizzjonali, u, jekk inqisu dan il-kmand bħala kmand biex jikkontrolla l-fluss, kmand tar-ritorn.
Fil-fatt, hawnhekk tista 'tagħti attenzjoni għall-fatt li l-programm mhuwiex maqsum fi blokki bl-użu ta' ċineg kaboċċi (bħal fil-familja C tal-lingwi). Huwa maqsum b'tikketti, reminixxenti tal-lingwi tal-assemblaġġ, u ppreżentat fil-forma ta 'blokki bażiċi. Fl-SSA, il-blokki bażiċi huma definiti bħala sekwenzi kontigwi ta' kodiċi li jibdew b'tikketta u jispiċċaw b'struzzjonijiet bażiċi ta' tlestija ta' blokki, bħal - return и jump.
Dettall ieħor interessanti ta 'dan il-kodiċi huwa rappreżentat mill-istruzzjoni phi. L-istruzzjonijiet huma pjuttost mhux tas-soltu u jistgħu jieħdu xi żmien biex jifhmu. Ftakar li huwa qasir għal Static Single Assignment. Din hija rappreżentazzjoni intermedja tal-kodiċi użat mill-kompilaturi, li fiha kull varjabbli tiġi assenjata valur darba biss. Dan huwa kbir biex jesprimu funzjonijiet sempliċi bħall-funzjoni tagħna myAddmuri hawn fuq, iżda mhux adattat għal funzjonijiet aktar kumplessi bħall-funzjoni diskussa f'din it-taqsima sum. B'mod partikolari, il-varjabbli jinbidlu matul l-eżekuzzjoni tal-linja i и n.
SSA tevita r-restrizzjoni fuq l-assenjazzjoni ta' valuri varjabbli darba billi tuża l-hekk imsejħa struzzjoni phi (ismu huwa meħud mill-alfabett Grieg). Il-fatt hu li sabiex ir-rappreżentazzjoni SSA tal-kodiċi tiġi ġġenerata għal lingwi bħal C, trid tirrikorri għal xi tricks. Ir-riżultat tas-sejħa ta' din l-istruzzjoni huwa l-valur kurrenti tal-varjabbli (i jew n), u lista ta' blokki bażiċi tintuża bħala l-parametri tagħha. Pereżempju, ikkunsidra din l-istruzzjoni:
t0 = phi [entry: 0:int, for.body: t6] #n
It-tifsira tagħha hija kif ġej: jekk il-blokk bażiku preċedenti kien blokk entry (input), imbagħad t0 hija kostanti 0, u jekk il-blokk bażiku preċedenti kien for.body, allura għandek bżonn tieħu l-valur t6 minn dan il-blokk. Dan kollu jista 'jidher pjuttost misterjuż, iżda dan il-mekkaniżmu huwa dak li jagħmel l-SSA taħdem. Minn perspettiva umana, dan kollu jagħmel il-kodiċi diffiċli biex jinftiehem, iżda l-fatt li kull valur huwa assenjat darba biss jagħmel ħafna ottimizzazzjonijiet ħafna aktar faċli.
Innota li jekk tikteb il-kompilatur tiegħek, normalment ma jkollokx għalfejn tittratta ma 'dan it-tip ta' għalf. Anke Clang ma jiġġenerax dawn l-istruzzjonijiet kollha phi, juża mekkaniżmu alloca (tixbah li taħdem ma 'varjabbli lokali ordinarji). Imbagħad, meta tmexxi pass ta 'ottimizzazzjoni LLVM imsejjaħ , struzzjonijiet alloca maqluba għall-forma SSA. TinyGo, madankollu, jirċievi input minn Go SSA, li, b'mod konvenjenti, diġà huwa kkonvertit għal forma SSA.
Innovazzjoni oħra tal-framment tal-kodiċi intermedju taħt konsiderazzjoni hija li l-aċċess għall-elementi tal-porzjon bl-indiċi huwa rappreżentat fil-forma ta 'operazzjoni ta' kalkolu tal-indirizz u operazzjoni ta 'dereferencing tal-pointer li jirriżulta. Hawnhekk tista 'tara ż-żieda diretta ta' kostanti mal-kodiċi IR (per eżempju - 1:int). Fl-eżempju bil-funzjoni myAdd dan ma ntużax. Issa li għandna dawk il-karatteristiċi barra mill-mod, ejja nagħtu ħarsa lejn dak li jsir dan il-kodiċi meta kkonvertit fil-forma LLVM IR:
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
}
Hawnhekk, bħal qabel, nistgħu naraw l-istess struttura, li tinkludi strutturi sintattiċi oħra. Per eżempju, fis-sejħiet phi valuri u tikketti mibdula. Madankollu, hawn xi ħaġa li ta' min tingħata attenzjoni speċjali għaliha.
Biex tibda, hawnhekk tista 'tara firma ta' funzjoni kompletament differenti. LLVM ma jappoġġjax slices, u bħala riżultat, bħala ottimizzazzjoni, il-kompilatur TinyGo li ġġenera dan il-kodiċi intermedju qasam id-deskrizzjoni ta 'din l-istruttura tad-dejta f'partijiet. Jista 'jirrappreżenta tliet elementi porzjon (ptr, len и cap) bħala struttura (struct), iżda li tirrappreżentahom bħala tliet entitajiet separati tippermetti xi ottimizzazzjonijiet. Kompilaturi oħra jistgħu jirrappreżentaw il-porzjon b'modi oħra, skont il-konvenzjonijiet tas-sejħa tal-funzjonijiet tal-pjattaforma fil-mira.
Karatteristika oħra interessanti ta 'dan il-kodiċi hija l-użu tal-istruzzjoni getelementptr (spiss imqassar bħala GEP).
Din l-istruzzjoni taħdem b'pointers u tintuża biex tikseb pointer għal element slice. Pereżempju, ejja nqabbluha mal-kodiċi li ġej miktub f'C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Jew bl-ekwivalenti li ġej għal dan:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
L-iktar ħaġa importanti hawnhekk hija li l-istruzzjonijiet getelementptr ma jwettaqx operazzjonijiet ta' dereferenzi. Jikkalkula biss pointer ġdid ibbażat fuq dak eżistenti. Jista' jittieħed bħala struzzjonijiet mul и add fil-livell tal-ħardwer. Tista' taqra aktar dwar l-istruzzjonijiet tal-GEP .
Fattur ieħor interessanti ta 'dan il-kodiċi intermedju huwa l-użu tal-istruzzjoni icmp. Din hija struzzjoni għal skop ġenerali użata biex timplimenta paraguni sħaħ. Ir-riżultat ta 'din l-istruzzjoni huwa dejjem valur tat-tip i1 — valur loġiku. F'dan il-każ, isir paragun bl-użu tal-kelma prinċipali slt (iffirmat inqas minn), peress li qed inqabblu żewġ numri rappreżentati qabel mit-tip int. Kieku konna nqabblu żewġ interi mhux iffirmati, allura nużaw icmp, u l-kelma prinċipali użata fit-tqabbil tkun ult. Biex tqabbel in-numri b'punt li jvarja, tintuża struzzjoni oħra, fcmp, li jaħdem b'mod simili.
Riżultati ta '
Nemmen li f'dan il-materjal kopriet l-aktar karatteristiċi importanti ta 'LLVM IR. Naturalment, hawn ħafna aktar. B'mod partikolari, ir-rappreżentazzjoni intermedja tal-kodiċi jista' jkun fiha ħafna annotazzjonijiet li jippermettu pass ta' ottimizzazzjoni biex iqisu ċerti karatteristiċi tal-kodiċi magħrufa mill-kompilatur li ma jistgħux jiġu espressi mod ieħor f'IR. Per eżempju, din hija bandiera inbounds Istruzzjonijiet GEP, jew bnadar nsw и nuw, li jistgħu jiġu miżjuda mal-istruzzjonijiet add. L-istess jgħodd għall-keyword private, li tindika lill-ottimizzatur li l-funzjoni li timmarka mhux se tkun referenzjata minn barra l-unità tal-kumpilazzjoni attwali. Dan jippermetti ħafna ottimizzazzjonijiet interproċedurali interessanti bħall-eliminazzjoni ta 'argumenti mhux użati.
Tista' taqra aktar dwar LLVM fi , li int ser tirreferi għaliha spiss meta tiżviluppa l-kompilatur tiegħek ibbażat fuq LLVM. Hawn , li tħares lejn l-iżvilupp ta 'kompilatur għal lingwa sempliċi ħafna. Dawn iż-żewġ sorsi ta’ informazzjoni jkunu utli għalik meta toħloq il-kompilatur tiegħek stess.
Għeżież qarrejja! Qed tuża LLVM?
Sors: www.habr.com