Ang pagbuo ng isang compiler ay isang napakahirap na gawain. Ngunit, sa kabutihang palad, sa pagbuo ng mga proyekto tulad ng LLVM, ang solusyon sa problemang ito ay lubos na pinasimple, na nagpapahintulot sa kahit na isang programmer na lumikha ng isang bagong wika na malapit sa pagganap sa C. Ang pagtatrabaho sa LLVM ay kumplikado sa pamamagitan ng katotohanan na ito system ay kinakatawan ng isang malaking halaga ng code, nilagyan ng maliit na dokumentasyon . Upang subukang iwasto ang pagkukulang na ito, ang may-akda ng materyal, ang pagsasalin na aming inilalathala ngayon, ay magpapakita ng mga halimbawa ng code na nakasulat sa Go at ipakita kung paano sila unang isinalin sa , at pagkatapos ay sa LLVM IR gamit ang compiler . Ang Go SSA at LLVM IR code ay bahagyang na-edit upang alisin ang mga bagay na hindi nauugnay sa mga paliwanag na ibinigay dito, upang gawing mas nauunawaan ang mga paliwanag.
Unang halimbawa
Ang unang function na titingnan ko dito ay isang simpleng mekanismo para sa pagdaragdag ng mga numero:
func myAdd(a, b int) int{
return a + b
}Ang function na ito ay napaka-simple, at, marahil, walang mas simple. Isinasalin ito sa sumusunod na Go SSA code:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Sa view na ito, ang mga pahiwatig ng uri ng data ay inilalagay sa kanan at maaaring balewalain sa karamihan ng mga kaso.
Binibigyang-daan ka na ng maliit na halimbawang ito na makita ang kakanyahan ng isang aspeto ng SSA. Ibig sabihin, kapag nagko-convert ng code sa anyo ng SSA, ang bawat expression ay pinaghiwa-hiwalay sa pinakapangunahing bahagi kung saan ito binubuo. Sa aming kaso, ang utos return a + b, sa katunayan, ay kumakatawan sa dalawang operasyon: pagdaragdag ng dalawang numero at pagbabalik ng resulta.
Bilang karagdagan, dito makikita mo ang mga pangunahing bloke ng programa; sa code na ito mayroon lamang isang bloke - ang entry block. Pag-uusapan natin ang higit pa tungkol sa mga bloke sa ibaba.
Ang Go SSA code ay madaling na-convert sa LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Ang mapapansin mo ay kahit na iba't ibang mga syntactic na istruktura ang ginagamit dito, ang istraktura ng function ay karaniwang hindi nagbabago. Ang LLVM IR code ay medyo mas malakas kaysa sa Go SSA code, katulad ng C. Dito, sa function declaration, unang mayroong isang paglalarawan ng uri ng data na ibinabalik nito, ang uri ng argumento ay ipinahiwatig bago ang pangalan ng argumento. Bilang karagdagan, upang gawing simple ang pag-parse ng IR, ang mga pangalan ng mga pandaigdigang entity ay pinangungunahan ng simbolo @, at bago ang mga lokal na pangalan ay mayroong simbolo % (ang isang function ay itinuturing din na isang pandaigdigang entity).
Ang isang bagay na dapat tandaan tungkol sa code na ito ay ang desisyon ng representasyon ng uri ni Go int, na maaaring kinakatawan bilang isang 32-bit o 64-bit na halaga, depende sa compiler at ang target ng compilation, ay tinatanggap kapag ang LLVM ay bumubuo ng IR code. Isa ito sa maraming dahilan kung bakit ang LLVM IR code ay hindi, gaya ng iniisip ng maraming tao, na independyente ang platform. Ang nasabing code, na nilikha para sa isang platform, ay hindi basta-basta kunin at i-compile para sa isa pang platform (maliban kung angkop ka para sa paglutas ng problemang ito ).
Ang isa pang kawili-wiling punto na dapat tandaan ay ang uri i64 ay hindi isang sign na integer: ito ay neutral sa mga tuntunin ng kumakatawan sa tanda ng numero. Depende sa pagtuturo, maaari itong kumatawan sa parehong pinirmahan at hindi nalagdaan na mga numero. Sa kaso ng representasyon ng pagpapatakbo ng karagdagan, hindi ito mahalaga, kaya walang pagkakaiba sa pagtatrabaho sa mga pinirmahan o hindi nilagdaan na mga numero. Dito nais kong tandaan na sa wikang C, ang pag-uumapaw sa isang naka-sign integer na variable ay humahantong sa hindi natukoy na pag-uugali, kaya ang Clang frontend ay nagdaragdag ng isang bandila sa operasyon nsw (walang naka-sign na pambalot), na nagsasabi sa LLVM na maaari nitong ipalagay na ang karagdagan ay hindi kailanman umaapaw.
Maaaring mahalaga ito para sa ilang pag-optimize. Halimbawa, pagdaragdag ng dalawang halaga i16 sa isang 32-bit na platform (na may 32-bit na mga rehistro) ay nangangailangan, pagkatapos ng karagdagan, ng isang sign expansion operation upang manatili sa saklaw i16. Dahil dito, kadalasan ay mas mahusay na magsagawa ng mga pagpapatakbo ng integer batay sa mga laki ng rehistro ng makina.
Ang susunod na mangyayari sa IR code na ito ay hindi partikular na interes sa amin ngayon. Ang code ay na-optimize (ngunit sa kaso ng isang simpleng halimbawa tulad ng sa amin, walang na-optimize) at pagkatapos ay na-convert sa machine code.
Pangalawang halimbawa
Ang susunod na halimbawa na titingnan natin ay magiging mas kumplikado. Ibig sabihin, pinag-uusapan natin ang tungkol sa isang function na nagsusuma ng isang slice ng integers:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Ang code na ito ay nagko-convert sa sumusunod na Go SSA code:
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 t0Dito maaari ka nang makakita ng higit pang mga konstruksyon na tipikal para sa kumakatawan sa code sa SSA form. Marahil ang pinaka-halatang tampok ng code na ito ay ang katotohanan na walang mga structured flow control command. Upang kontrolin ang daloy ng mga kalkulasyon, mayroon lamang kondisyonal at walang kondisyong mga pagtalon, at, kung isasaalang-alang natin ang utos na ito bilang isang utos upang kontrolin ang daloy, isang utos na bumalik.
Sa katunayan, dito maaari mong bigyang-pansin ang katotohanan na ang programa ay hindi nahahati sa mga bloke gamit ang mga kulot na braces (tulad ng sa C pamilya ng mga wika). Ito ay hinati sa pamamagitan ng mga etiketa, nakapagpapaalaala sa mga wika ng pagpupulong, at ipinakita sa anyo ng mga pangunahing bloke. Sa SSA, ang mga pangunahing bloke ay tinukoy bilang magkadikit na pagkakasunud-sunod ng code na nagsisimula sa isang label at nagtatapos sa mga pangunahing tagubilin sa pagkumpleto ng bloke, tulad ng β return ΠΈ jump.
Ang isa pang kawili-wiling detalye ng code na ito ay kinakatawan ng pagtuturo phi. Ang mga tagubilin ay medyo hindi pangkaraniwan at maaaring tumagal ng ilang oras upang maunawaan. tandaan mo, yan ay maikli para sa Static Single Assignment. Ito ay isang intermediate na representasyon ng code na ginagamit ng mga compiler, kung saan ang bawat variable ay itinalaga ng isang halaga nang isang beses lamang. Ito ay mahusay para sa pagpapahayag ng mga simpleng function tulad ng aming function myAddipinapakita sa itaas, ngunit hindi angkop para sa mas kumplikadong mga function tulad ng function na tinalakay sa seksyong ito sum. Sa partikular, nagbabago ang mga variable sa panahon ng pagpapatupad ng loop i ΠΈ n.
Ang SSA ay lumalampas sa paghihigpit sa pagtatalaga ng mga variable na halaga kapag gumagamit ng tinatawag na pagtuturo phi (Ang pangalan nito ay kinuha sa alpabetong Griyego). Ang katotohanan ay upang ang SSA na representasyon ng code ay mabuo para sa mga wika tulad ng C, kailangan mong gumamit ng ilang mga trick. Ang resulta ng pagtawag sa pagtuturo na ito ay ang kasalukuyang halaga ng variable (i o n), at isang listahan ng mga pangunahing bloke ang ginagamit bilang mga parameter nito. Halimbawa, isaalang-alang ang tagubiling ito:
t0 = phi [entry: 0:int, for.body: t6] #n
Ang kahulugan nito ay ang mga sumusunod: kung ang nakaraang pangunahing bloke ay isang bloke entry (input), pagkatapos t0 ay isang pare-pareho 0, at kung ang nakaraang pangunahing bloke ay for.body, pagkatapos ay kailangan mong kunin ang halaga t6 mula sa bloke na ito. Ang lahat ay maaaring mukhang misteryoso, ngunit ang mekanismong ito ay kung bakit gumagana ang SSA. Mula sa pananaw ng tao, lahat ng ito ay nagpapahirap sa code na maunawaan, ngunit ang katotohanan na ang bawat value ay isang beses lang itinalaga ay nagpapadali sa maraming pag-optimize.
Tandaan na kung isusulat mo ang iyong sariling compiler, kadalasan ay hindi mo na kailangang harapin ang ganitong uri ng mga bagay-bagay. Kahit na ang Clang ay hindi bumubuo ng lahat ng mga tagubiling ito phi, gumagamit ito ng mekanismo alloca (ito ay kahawig ng pagtatrabaho sa mga ordinaryong lokal na variable). Pagkatapos, kapag nagpapatakbo ng isang LLVM optimization pass na tinatawag , mga tagubilin alloca na-convert sa SSA form. Gayunpaman, ang TinyGo ay tumatanggap ng input mula sa Go SSA, na, sa madaling paraan, ay na-convert na sa SSA form.
Ang isa pang pagbabago ng fragment ng intermediate code na isinasaalang-alang ay ang pag-access sa mga elemento ng slice sa pamamagitan ng index ay kinakatawan sa anyo ng isang operasyon ng pagkalkula ng address at isang operasyon ng dereferencing sa resultang pointer. Dito makikita mo ang direktang pagdaragdag ng mga constant sa IR code (halimbawa - 1:int). Sa halimbawa na may function myAdd hindi ito nagamit. Ngayong naalis na natin ang mga feature na iyon, tingnan natin kung ano ang nagiging code na ito kapag na-convert sa LLVM IR form:
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
}
Dito, tulad ng dati, makikita natin ang parehong istraktura, na kinabibilangan ng iba pang mga syntactic na istruktura. Halimbawa, sa mga tawag phi pinalitan ang mga halaga at label. Gayunpaman, mayroong isang bagay dito na nagkakahalaga ng pagbibigay ng espesyal na pansin.
Upang magsimula sa, dito maaari mong makita ang isang ganap na naiibang function signature. Hindi sinusuportahan ng LLVM ang mga slice, at bilang resulta, bilang isang pag-optimize, hinati ng TinyGo compiler na bumuo ng intermediate code na ito ang paglalarawan ng istruktura ng data na ito sa mga bahagi. Maaari itong kumatawan sa tatlong elemento ng slice (ptr, len ΠΈ cap) bilang isang istraktura (struct), ngunit kinakatawan ang mga ito bilang tatlong magkakahiwalay na entity ay nagbibigay-daan para sa ilang mga pag-optimize. Ang ibang mga compiler ay maaaring kumatawan sa slice sa ibang mga paraan, depende sa mga calling convention ng mga function ng target na platform.
Ang isa pang kawili-wiling tampok ng code na ito ay ang paggamit ng pagtuturo getelementptr (madalas na dinaglat bilang GEP).
Gumagana ang pagtuturo na ito sa mga pointer at ginagamit upang makakuha ng pointer sa isang slice element. Halimbawa, ihambing natin ito sa sumusunod na code na nakasulat sa C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}O may sumusunod na katumbas nito:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
Ang pinakamahalagang bagay dito ay ang mga tagubilin getelementptr hindi nagsasagawa ng mga pagpapatakbo ng dereferencing. Kinakalkula lamang nito ang isang bagong pointer batay sa umiiral na. Maaari itong kunin bilang mga tagubilin mul ΠΈ add sa antas ng hardware. Maaari kang magbasa nang higit pa tungkol sa mga tagubilin sa GEP .
Ang isa pang kawili-wiling tampok ng intermediate code na ito ay ang paggamit ng pagtuturo icmp. Ito ay isang pangkalahatang layunin ng pagtuturo na ginagamit upang ipatupad ang mga paghahambing ng integer. Ang resulta ng pagpapatupad ng pagtuturo na ito ay palaging isang halaga ng uri i1 - lohikal na halaga. Sa kasong ito, ang isang paghahambing ay ginawa gamit ang keyword slt (mas kaunti ang nilagdaan), dahil naghahambing kami ng dalawang numero na dating kinakatawan ng uri int. Kung kami ay naghahambing ng dalawang unsigned integer, pagkatapos ay gagamitin namin icmp, at ang keyword na ginamit sa paghahambing ay ult. Upang ihambing ang mga numero ng floating point, isa pang tagubilin ang ginagamit, fcmp, na gumagana sa katulad na paraan.
Mga resulta ng
Naniniwala ako na sa materyal na ito nasaklaw ko ang pinakamahalagang katangian ng LLVM IR. Syempre, marami pa dito. Sa partikular, ang intermediate na representasyon ng code ay maaaring maglaman ng maraming anotasyon na nagpapahintulot sa mga optimization pass na isaalang-alang ang ilang mga tampok ng code na kilala ng compiler na hindi maaaring ipahayag sa IR. Halimbawa, ito ay isang bandila inbounds Mga tagubilin sa GEP, o mga flag nsw ΠΈ nuw, na maaaring idagdag sa mga tagubilin add. Ganoon din sa keyword private, na nagpapahiwatig sa optimizer na ang function na minarkahan nito ay hindi ire-reference mula sa labas ng kasalukuyang compilation unit. Nagbibigay-daan ito para sa maraming kawili-wiling interprocedural na pag-optimize tulad ng pag-aalis ng mga hindi nagamit na argumento.
Maaari kang magbasa nang higit pa tungkol sa LLVM sa , na madalas mong tinutukoy kapag bumubuo ng iyong sariling compiler na nakabatay sa LLVM. Dito , na tumitingin sa pagbuo ng isang compiler para sa isang napakasimpleng wika. Pareho sa mga mapagkukunang ito ng impormasyon ay magiging kapaki-pakinabang sa iyo kapag lumilikha ng iyong sariling compiler.
Minamahal na mambabasa! Gumagamit ka ba ng LLVM?
Pinagmulan: www.habr.com