Ang pagpalambo sa usa ka compiler usa ka lisud kaayo nga buluhaton. Apan, maayo na lang, sa pag-uswag sa mga proyekto sama sa LLVM, ang solusyon niini nga problema gipasimple kaayo, nga nagtugot bisan sa usa ka programmer sa paghimo og bag-ong pinulongan nga duol sa pasundayag sa C. Ang pagtrabaho kauban ang LLVM komplikado sa kamatuoran nga kini sistema girepresentar sa usa ka dako nga kantidad sa code, himan uban sa gamay nga dokumentasyon . Aron masulayan ang pagtul-id niini nga mga kakulangan, ang tagsulat sa materyal, ang paghubad nga among gipatik karon, magpakita sa mga pananglitan sa code nga gisulat sa Go ug ipakita kung giunsa kini unang gihubad ngadto sa , ug dayon sa LLVM IR gamit ang compiler . Ang Go SSA ug LLVM IR code gamay ra nga gi-edit aron matangtang ang mga butang nga walaβy kalabotan sa mga pagpasabut nga gihatag dinhi, aron mas masabtan ang mga pagpasabut.
Unang pananglitan
Ang una nga function nga akong tan-awon dinhi usa ka yano nga mekanismo sa pagdugang mga numero:
func myAdd(a, b int) int{
return a + b
}Kini nga function yano ra kaayo, ug, tingali, walaβy mahimo nga labi ka yano. Kini gihubad ngadto sa mosunod nga Go SSA code:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Uban niini nga pagtan-aw, ang mga tip sa tipo sa datos gibutang sa tuo ug mahimong ibaliwala sa kadaghanan nga mga kaso.
Kining gamay nga pananglitan nagtugot kanimo nga makita ang esensya sa usa ka aspeto sa SSA. Sa ato pa, kung gi-convert ang code sa porma sa SSA, ang matag ekspresyon gibuak sa labing elementarya nga mga bahin diin kini gilangkuban. Sa among kaso, ang mando return a + b, sa pagkatinuod, nagrepresentar sa duha ka operasyon: pagdugang og duha ka numero ug pagbalik sa resulta.
Dugang pa, dinhi makita nimo ang sukaranan nga mga bloke sa programa; sa kini nga code adunay usa ra ka bloke - ang bloke sa pagsulod. Maghisgot pa kami bahin sa mga bloke sa ubos.
Ang Go SSA code dali nga nakabig sa LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Ang imong mamatikdan mao nga bisan kung lainlain nga mga istruktura sa syntactic ang gigamit dinhi, ang istruktura sa function walaβy pagbag-o. Ang LLVM IR code usa ka gamay nga mas lig-on kay sa Go SSA code, susama sa C. Dinhi, sa deklarasyon sa function, una adunay usa ka paghulagway sa tipo sa datos nga gibalik niini, ang tipo sa argumento gipakita sa wala pa ang ngalan sa argumento. Dugang pa, aron mapasimple ang pag-parse sa IR, ang mga ngalan sa mga global nga entidad giunhan sa simbolo @, ug sa wala pa ang lokal nga mga ngalan adunay simbolo % (usa ka function giisip usab nga usa ka global nga entidad).
Usa ka butang nga matikdan bahin sa kini nga code mao nga ang tipo nga representasyon nga desisyon ni Go int, nga mahimong irepresentar isip 32-bit o 64-bit nga bili, depende sa compiler ug sa target sa compilation, gidawat sa dihang ang LLVM IR code namugna. Kini usa sa daghang mga hinungdan nga ang LLVM IR code dili, sama sa gihunahuna sa daghang mga tawo, independente sa plataporma. Ang ingon nga kodigo, nga gihimo alang sa usa ka plataporma, dili basta-basta makuha ug i-compile alang sa lain nga plataporma (gawas kung angay ka nga masulbad kini nga problema. ).
Ang laing makapaikag nga punto nga angay hinumdoman mao nga ang tipo i64 dili usa ka pinirmahan nga integer: kini neyutral sa termino sa pagrepresentar sa timaan sa numero. Depende sa instruksyon, kini mahimong magrepresentar sa pinirmahan ug wala mapirmahan nga mga numero. Sa kaso sa representasyon sa dugang nga operasyon, kini dili igsapayan, mao nga walay kalainan sa pagtrabaho uban sa gipirmahan o unsigned nga mga numero. Dinhi gusto nakong timan-an nga sa C nga pinulongan, ang pag-awas sa usa ka gipirmahan nga integer variable mosangpot sa dili matino nga kinaiya, mao nga ang Clang frontend nagdugang sa usa ka bandila sa operasyon nsw (walay gipirmahan nga wrap), nga nagsulti sa LLVM nga kini mahimong maghunahuna nga ang pagdugang dili gayud mag-awas.
Mahimong hinungdanon kini alang sa pipila nga pag-optimize. Pananglitan, pagdugang og duha ka bili i16 sa usa ka 32-bit nga plataporma (nga adunay 32-bit nga mga rehistro) nanginahanglan, pagkahuman sa pagdugang, usa ka operasyon sa pagpalapad sa timaan aron magpabilin sa range i16. Tungod niini, kasagaran mas episyente ang paghimo sa mga operasyon nga integer base sa mga gidak-on sa rehistro sa makina.
Unsa ang sunod nga mahitabo sa niini nga IR code dili sa partikular nga interes kanato karon. Ang code gi-optimize (apan sa kaso sa usa ka yano nga pananglitan sama sa amon, walaβy na-optimize) ug dayon gi-convert sa code sa makina.
Ikaduha nga pananglitan
Ang sunod nga pananglitan nga atong tan-awon mahimong mas komplikado. Sa ato pa, naghisgot kami bahin sa usa ka function nga nagsumaryo sa usa ka hiwa sa mga integer:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Kini nga code nakabig ngadto sa mosunod nga 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 t0Dinhi makita na nimo ang daghang mga konstruksyon nga kasagaran sa pagrepresentar sa code sa porma sa SSA. Tingali ang labing klaro nga bahin sa kini nga code mao ang kamatuoran nga walaβy structured flow control commands. Aron makontrol ang dagan sa mga kalkulasyon, adunay kondisyon lamang ug walay kondisyon nga paglukso, ug, kung atong isipon kini nga sugo isip usa ka sugo sa pagkontrolar sa dagan, usa ka pagbalik nga sugo.
Sa tinuud, dinhi mahimo nimong hatagan pagtagad ang kamatuoran nga ang programa wala gibahin sa mga bloke gamit ang mga curly braces (sama sa C pamilya sa mga pinulongan). Gibahin kini sa mga label, nagpahinumdom sa mga pinulongan sa asembliya, ug gipresentar sa porma sa mga batakang bloke. Sa SSA, ang sukaranan nga mga bloke gihubit ingon nga magkatakdo nga mga han-ay sa code nga nagsugod sa usa ka label ug natapos sa sukaranan nga mga panudlo sa pagkompleto sa bloke, sama sa - return ΠΈ jump.
Ang laing makapaikag nga detalye niini nga code girepresentahan sa instruksyon phi. Ang mga instruksyon medyo talagsaon ug mahimong magdugay aron masabtan. hinumdumi, nga mubo alang sa Static Single Assignment. Kini usa ka intermediate nga representasyon sa code nga gigamit sa mga compiler, diin ang matag variable gihatagan og bili kausa lang. Maayo kini alang sa pagpahayag sa yano nga mga gimbuhaton sama sa among gimbuhaton myAddgipakita sa ibabaw, apan dili angay alang sa mas komplikado nga mga gimbuhaton sama sa function nga gihisgutan niini nga seksyon sum. Sa partikular, ang mga variable nagbag-o sa panahon sa pagpatuman sa loop i ΠΈ n.
Gilaktawan sa SSA ang pagdili sa pag-assign sa mga variable nga kantidad sa makausa gamit ang usa ka gitawag nga panudlo phi (ang ngalan niini gikuha gikan sa Gregong alpabeto). Ang tinuod mao nga aron ang SSA nga representasyon sa code mamugna alang sa mga pinulongan sama sa C, kinahanglan ka nga mogamit sa pipila ka mga limbong. Ang resulta sa pagtawag niini nga instruksiyon mao ang kasamtangang bili sa variable (i o n), ug usa ka lista sa mga batakang bloke ang gigamit isip mga parameter niini. Pananglitan, tagda kini nga instruksyon:
t0 = phi [entry: 0:int, for.body: t6] #n
Ang kahulogan niini mao ang mosunod: kung ang naunang batakang bloke usa ka bloke entry (input), unya t0 mao ang usa ka makanunayon 0, ug kung ang miaging batakang bloke mao for.body, unya kinahanglan nimo nga kuhaon ang kantidad t6 gikan niini nga block. Mahimong misteryoso kining tanan, apan kini nga mekanismo mao ang naghimo sa SSA nga molihok. Gikan sa panan-aw sa tawo, kining tanan naghimo sa code nga lisud sabton, apan ang kamatuoran nga ang matag kantidad gi-assign kausa lang naghimo sa daghang mga pag-optimize nga labi ka dali.
Timan-i nga kung magsulat ka sa imong kaugalingon nga compiler, kasagaran dili nimo kinahanglan nga atubangon kini nga klase nga butang. Bisan ang Clang wala makamugna sa tanan niini nga mga panudlo phi, kini naggamit ug mekanismo alloca (kini susama sa pagtrabaho sa ordinaryo nga lokal nga mga baryable). Pagkahuman, kung nagdagan ang usa ka LLVM optimization pass nga gitawag , mga instruksyon alloca gi-convert sa SSA nga porma. Ang TinyGo, bisan pa niana, nakadawat og input gikan sa Go SSA, nga, sayon, nakabig na ngadto sa SSA nga porma.
Ang laing kabag-ohan sa tipik sa intermediate code nga gikonsiderar mao nga ang pag-access sa mga elemento sa slice pinaagi sa indeks girepresentahan sa porma sa usa ka operasyon sa pagkalkula sa adres ug usa ka operasyon sa dereferencing sa resulta nga pointer. Dinhi imong makita ang direkta nga pagdugang sa mga constants sa IR code (pananglitan - 1:int). Sa pananglitan nga adunay function myAdd wala kini gigamit. Karon nga wala na namo kana nga mga bahin, atong tan-awon kung unsa kini nga kodigo kung nakabig sa LLVM IR nga porma:
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
}
Dinhi, sama kaniadto, atong makita ang parehas nga istruktura, nga naglakip sa ubang mga istruktura sa syntactic. Pananglitan, sa mga tawag phi gibaylo ang mga kantidad ug label. Bisan pa, adunay usa ka butang dinhi nga angay hatagan espesyal nga pagtagad.
Sa pagsugod, dinhi makita nimo ang usa ka hingpit nga lahi nga pirma sa function. Ang LLVM wala nagsuporta sa mga hiwa, ug isip resulta, isip usa ka pag-optimize, ang TinyGo compiler nga nagmugna niining intermediate code nagbahin sa paghulagway niini nga data structure ngadto sa mga bahin. Kini mahimong magrepresentar sa tulo ka mga elemento sa hiwa (ptr, len ΠΈ cap) isip usa ka istruktura (struct), apan ang pagrepresentar kanila isip tulo ka managlahing entidad nagtugot sa pipila ka mga pag-optimize. Ang ubang mga compiler mahimong magrepresentar sa slice sa ubang mga paagi, depende sa calling conventions sa mga function sa target platform.
Ang laing makaiikag nga bahin niini nga kodigo mao ang paggamit sa instruksiyon getelementptr (kasagaran gipamubo nga GEP).
Kini nga panudlo magamit sa mga pointer ug gigamit aron makakuha usa ka pointer sa usa ka elemento sa slice. Pananglitan, atong itandi kini sa mosunod nga code nga gisulat sa C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}O uban sa mosunod nga katumbas niini:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
Ang labing hinungdanon nga butang dinhi mao nga ang mga panudlo getelementptr wala maghimo sa mga operasyon sa dereferencing. Nagkalkula lang kini og bag-ong pointer base sa naa na. Mahimo kini isip mga instruksyon mul ΠΈ add sa lebel sa hardware. Makabasa ka og dugang mahitungod sa mga instruksyon sa GEP .
Ang laing makaiikag nga bahin niining intermediate code mao ang paggamit sa instruksiyon icmp. Kini usa ka kinatibuk-ang katuyoan nga panudlo nga gigamit sa pagpatuman sa mga pagtandi sa integer. Ang resulta niini nga instruksyon kanunay nga usa ka bili sa tipo i1 - lohikal nga bili. Sa kini nga kaso, ang usa ka pagtandi gihimo gamit ang keyword slt (gipirmahan ubos sa), tungod kay kita nagtandi sa duha ka mga numero nga kaniadto girepresentahan sa matang int. Kung gikumpara namo ang duha ka unsigned integer, nan among gamiton icmp, ug ang keyword nga gigamit sa pagtandi mao ang ult. Aron itandi ang mga numero sa floating point, laing instruksiyon ang gigamit, fcmp, nga naglihok sa susamang paagi.
Mga resulta
Nagtuo ko nga sa kini nga materyal natabunan nako ang labing hinungdanon nga mga bahin sa LLVM IR. Siyempre, daghan pa dinhi. Sa partikular, ang intermediate nga representasyon sa code mahimong adunay daghang mga anotasyon nga nagtugot sa optimization pass sa pagkonsiderar sa pipila ka mga bahin sa code nga nahibal-an sa compiler nga dili mahimong ipahayag sa IR. Pananglitan, kini usa ka bandila inbounds Mga instruksyon sa GEP, o mga bandera nsw ΠΈ nuw, nga mahimong idugang sa mga instruksyon add. Ang sama nga moadto alang sa keyword private, nga nagpaila sa optimizer nga ang function nga gimarkahan niini dili i-reference gikan sa gawas sa kasamtangan nga compilation unit. Gitugotan niini ang daghang makapaikag nga interprocedural nga pag-optimize sama sa pagwagtang sa wala magamit nga mga argumento.
Mahimo nimong mabasa ang dugang bahin sa LLVM sa , nga imong hisgotan kanunay kung nag-develop sa imong kaugalingon nga LLVM-based compiler. Dinhi , nga nagtan-aw sa pagpalambo sa usa ka compiler alang sa usa ka yano kaayo nga pinulongan. Kining duha ka tinubdan sa impormasyon mahimong mapuslanon kanimo sa paghimo sa imong kaugalingong compiler.
Minahal nga magbabasa! Gigamit ba nimo ang LLVM?
Source: www.habr.com