Mae datblygu casglwr yn dasg anodd iawn. Ond, yn ffodus, gyda datblygiad prosiectau fel LLVM, mae'r ateb i'r broblem hon wedi'i symleiddio'n fawr, sy'n caniatáu hyd yn oed un rhaglennydd i greu iaith newydd sy'n agos at C. Mae gweithio gyda LLVM wedi'i gymhlethu gan y ffaith bod hyn yn digwydd. system yn cael ei gynrychioli gan lawer iawn o god , offer gyda dogfennau ychydig . Er mwyn ceisio cywiro’r diffyg hwn, mae awdur y deunydd, yr ydym yn ei gyhoeddi heddiw, yn mynd i ddangos enghreifftiau o god a ysgrifennwyd yn Go a dangos sut y cânt eu cyfieithu gyntaf i , ac yna yn LLVM IR gan ddefnyddio'r casglwr . Mae cod Go SSA a LLVM IR wedi'i olygu ychydig i ddileu pethau nad ydynt yn berthnasol i'r esboniadau a roddir yma, er mwyn gwneud yr esboniadau yn fwy dealladwy.
Enghraifft gyntaf
Y swyddogaeth gyntaf rydw i'n mynd i edrych arni yma yw mecanwaith syml ar gyfer ychwanegu rhifau:
func myAdd(a, b int) int{
return a + b
}Mae'r swyddogaeth hon yn syml iawn, ac, efallai, ni allai dim fod yn symlach. Mae'n trosi i'r cod Go SSA canlynol:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Gyda'r farn hon, mae'r awgrymiadau math o ddata yn cael eu gosod ar y dde a gellir eu hanwybyddu yn y rhan fwyaf o achosion.
Mae'r enghraifft fach hon eisoes yn caniatáu ichi weld hanfod un agwedd ar SSA. Sef, wrth drosi cod yn ffurf SSA, mae pob mynegiant yn cael ei dorri i lawr i'r rhannau mwyaf elfennol y mae'n cael ei gyfansoddi ohonynt. Yn ein hachos ni, y gorchymyn return a + b, mewn gwirionedd, yn cynrychioli dau weithrediad: adio dau rif a dychwelyd y canlyniad.
Yn ogystal, yma gallwch weld blociau sylfaenol y rhaglen; dim ond un bloc sydd yn y cod hwn - y bloc mynediad. Byddwn yn siarad mwy am flociau isod.
Mae cod Go SSA yn trosi'n hawdd i LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Yr hyn y gallwch chi sylwi yw, er bod gwahanol strwythurau cystrawennol yn cael eu defnyddio yma, nid yw strwythur y swyddogaeth wedi newid yn y bôn. Mae'r cod LLVM IR ychydig yn gryfach na'r cod Go SSA, yn debyg i C. Yma, yn y datganiad swyddogaeth, yn gyntaf mae disgrifiad o'r math o ddata y mae'n ei ddychwelyd, mae'r math o ddadl wedi'i nodi cyn enw'r ddadl. Yn ogystal, er mwyn symleiddio dosrannu IR, mae'r symbol yn rhagflaenu enwau endidau byd-eang. @, a chyn enwau lleol mae symbol % (ystyrir swyddogaeth hefyd yn endid byd-eang).
Un peth i'w nodi am y cod hwn yw penderfyniad cynrychiolaeth math Go int, y gellir ei gynrychioli fel gwerth 32-did neu 64-did, yn dibynnu ar y casglwr a tharged y crynhoad, yn cael ei dderbyn pan fydd LLVM yn cynhyrchu'r cod IR. Dyma un o'r nifer o resymau pam nad yw cod LLVM IR, fel y mae llawer o bobl yn meddwl, yn annibynnol ar blatfform. Ni ellir cymryd cod o'r fath, a grëwyd ar gyfer un platfform, a'i lunio ar gyfer platfform arall (oni bai eich bod yn addas ar gyfer datrys y broblem hon ).
Pwynt diddorol arall sy'n werth nodi yw bod y math i64 nid yw'n gyfanrif wedi'i lofnodi: mae'n niwtral o ran cynrychioli arwydd y rhif. Yn dibynnu ar y cyfarwyddyd, gall gynrychioli rhifau llofnodi a heb eu llofnodi. Yn achos cynrychiolaeth y gweithrediad adio, nid yw hyn o bwys, felly nid oes gwahaniaeth o ran gweithio gyda rhifau wedi'u llofnodi neu heb eu llofnodi. Yma hoffwn nodi, yn yr iaith C, bod gorlifo newidyn cyfanrif wedi'i lofnodi yn arwain at ymddygiad heb ei ddiffinio, felly mae blaen Clang yn ychwanegu baner i'r llawdriniaeth nsw (dim papur lapio wedi'i lofnodi), sy'n dweud wrth LLVM y gall gymryd yn ganiataol nad yw adio byth yn gorlifo.
Gall hyn fod yn bwysig ar gyfer rhai optimizations. Er enghraifft, ychwanegu dau werth i16 ar blatfform 32-did (gyda chofrestrau 32-did) angen, ar ôl ychwanegu, gweithrediad ehangu arwydd er mwyn aros yn yr ystod i16. Oherwydd hyn, mae'n aml yn fwy effeithlon cyflawni gweithrediadau cyfanrif yn seiliedig ar faint cofrestr peiriannau.
Nid yw'r hyn sy'n digwydd nesaf gyda'r cod IR hwn o ddiddordeb arbennig i ni nawr. Mae'r cod wedi'i optimeiddio (ond yn achos enghraifft syml fel ein un ni, nid oes dim wedi'i optimeiddio) ac yna'n cael ei drawsnewid yn god peiriant.
Ail enghraifft
Bydd yr enghraifft nesaf y byddwn yn edrych arni ychydig yn fwy cymhleth. Sef, rydym yn sôn am swyddogaeth sy'n crynhoi sleisen o gyfanrifau:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Mae'r cod hwn yn trosi i'r cod Go SSA canlynol:
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 t0Yma gallwch eisoes weld mwy o gystrawennau sy'n nodweddiadol ar gyfer cynrychioli cod yn y ffurflen SSA. Efallai mai nodwedd amlycaf y cod hwn yw'r ffaith nad oes unrhyw orchmynion rheoli llif strwythuredig. Er mwyn rheoli llif y cyfrifiadau, dim ond neidiau amodol a diamod sydd, ac, os ydym yn ystyried y gorchymyn hwn fel gorchymyn i reoli'r llif, gorchymyn dychwelyd.
Mewn gwirionedd, yma gallwch chi dalu sylw at y ffaith nad yw'r rhaglen wedi'i rhannu'n flociau gan ddefnyddio braces cyrliog (fel yn y teulu C o ieithoedd). Fe'i rhennir gan labeli, sy'n atgoffa rhywun o ieithoedd cydosod, a'i gyflwyno ar ffurf blociau sylfaenol. Yn SSA, diffinnir blociau sylfaenol fel dilyniannau cod cyffiniol gan ddechrau gyda label ac yn gorffen gyda chyfarwyddiadau cwblhau bloc sylfaenol, megis − return и jump.
Cynrychiolir manylyn diddorol arall o'r cod hwn gan y cyfarwyddyd phi. Mae'r cyfarwyddiadau yn eithaf anarferol a gall gymryd peth amser i'w deall. cofiwch, bod yn fyr ar gyfer Aseiniad Sengl Statig. Mae hwn yn gynrychiolaeth ganolraddol o'r cod a ddefnyddir gan gasglwyr, lle rhoddir gwerth unwaith yn unig i bob newidyn. Mae hyn yn wych ar gyfer mynegi swyddogaethau syml fel ein swyddogaeth myAdda ddangosir uchod, ond nid yw'n addas ar gyfer swyddogaethau mwy cymhleth fel y swyddogaeth a drafodir yn yr adran hon sum. Yn benodol, mae newidynnau'n newid wrth weithredu'r ddolen i и n.
Mae SSA yn osgoi'r cyfyngiad ar aseinio gwerthoedd newidiol unwaith gan ddefnyddio cyfarwyddyd fel y'i gelwir phi (cymerir ei henw o'r wyddor Roeg). Y ffaith yw, er mwyn i gynrychiolaeth cod SSA gael ei gynhyrchu ar gyfer ieithoedd fel C, mae'n rhaid i chi droi at rai triciau. Canlyniad galw'r cyfarwyddyd hwn yw gwerth cyfredol y newidyn (i neu n), a defnyddir rhestr o flociau sylfaenol fel ei baramedrau. Er enghraifft, ystyriwch y cyfarwyddyd hwn:
t0 = phi [entry: 0:int, for.body: t6] #n
Mae ei ystyr fel a ganlyn: pe bai'r bloc sylfaenol blaenorol yn bloc entry (mewnbwn), yna t0 yn gyson 0, ac os oedd y bloc sylfaenol blaenorol for.body, yna mae angen i chi gymryd y gwerth t6 o'r bloc hwn. Gall hyn i gyd ymddangos yn eithaf dirgel, ond y mecanwaith hwn sy'n gwneud i'r SSA weithio. O safbwynt dynol, mae hyn i gyd yn gwneud y cod yn anodd ei ddeall, ond mae'r ffaith bod pob gwerth yn cael ei neilltuo unwaith yn unig yn gwneud llawer o optimeiddiadau yn llawer haws.
Sylwch, os byddwch chi'n ysgrifennu'ch casglwr eich hun, fel arfer ni fydd yn rhaid i chi ddelio â'r math hwn o bethau. Nid yw hyd yn oed Clang yn cynhyrchu'r holl gyfarwyddiadau hyn phi, mae'n defnyddio mecanwaith alloca (mae'n debyg i weithio gyda newidynnau lleol cyffredin). Yna, wrth redeg pas optimeiddio LLVM o'r enw , cyfarwyddiadau alloca trosi i ffurflen SSA. Mae TinyGo, fodd bynnag, yn derbyn mewnbwn gan Go SSA, sydd, yn gyfleus, eisoes wedi'i drosi i ffurflen SSA.
Arloesedd arall o'r darn o god canolradd sy'n cael ei ystyried yw bod mynediad at elfennau tafell yn ôl mynegai yn cael ei gynrychioli ar ffurf gweithrediad o gyfrifo'r cyfeiriad a gweithrediad dadgyfeirio'r pwyntydd canlyniadol. Yma gallwch weld ychwanegu cysonion yn uniongyrchol at y cod IR (er enghraifft - 1:int). Yn yr enghraifft gyda'r swyddogaeth myAdd nid yw hwn wedi cael ei ddefnyddio. Nawr ein bod wedi cael y nodweddion hynny allan o'r ffordd, gadewch i ni edrych ar yr hyn y daw'r cod hwn wrth ei drosi i ffurflen IR LLVM:
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
}
Yma, fel o'r blaen, gallwn weld yr un strwythur, sy'n cynnwys strwythurau cystrawennol eraill. Er enghraifft, mewn galwadau phi gwerthoedd a labeli wedi'u cyfnewid. Fodd bynnag, mae rhywbeth yma y mae'n werth rhoi sylw arbennig iddo.
I ddechrau, yma gallwch weld llofnod swyddogaeth hollol wahanol. Nid yw LLVM yn cefnogi tafelli, ac o ganlyniad, fel optimeiddio, mae'r casglwr TinyGo a gynhyrchodd y cod canolradd hwn yn rhannu'r disgrifiad o'r strwythur data hwn yn rhannau. Gallai gynrychioli tair elfen tafell (ptr, len и cap) fel strwythur (strwythur), ond mae eu cynrychioli fel tri endid ar wahân yn caniatáu rhai optimeiddio. Gall casglwyr eraill gynrychioli'r dafell mewn ffyrdd eraill, yn dibynnu ar gonfensiynau galw swyddogaethau'r platfform targed.
Nodwedd ddiddorol arall o'r cod hwn yw'r defnydd o'r cyfarwyddyd getelementptr (a dalfyrrir yn aml fel GEP).
Mae'r cyfarwyddyd hwn yn gweithio gydag awgrymiadau ac fe'i defnyddir i gael pwyntydd i elfen tafell. Er enghraifft, gadewch i ni ei gymharu â'r cod canlynol sydd wedi'i ysgrifennu yn C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Neu gyda'r canlynol yn cyfateb i hyn:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
Y peth pwysicaf yma yw bod y cyfarwyddiadau getelementptr nad yw'n perfformio gweithrediadau dadgyfeirio. Mae'n cyfrifo pwyntydd newydd yn seiliedig ar yr un presennol. Gellir ei gymryd fel cyfarwyddiadau mul и add ar lefel caledwedd. Gallwch ddarllen mwy am y cyfarwyddiadau GEP .
Nodwedd ddiddorol arall o'r cod canolradd hwn yw'r defnydd o'r cyfarwyddyd icmp. Mae hwn yn gyfarwyddyd pwrpas cyffredinol a ddefnyddir i weithredu cymariaethau cyfanrif. Mae canlyniad gweithredu'r cyfarwyddyd hwn bob amser yn werth math i1 - gwerth rhesymegol. Yn yr achos hwn, gwneir cymhariaeth gan ddefnyddio'r allweddair slt (llwyddo na), gan ein bod yn cymharu dau rif a gynrychiolwyd yn flaenorol gan y math int. Pe baem yn cymharu dau gyfanrif heb eu llofnodi, yna byddem yn defnyddio icmp, a byddai'r allweddair a ddefnyddir yn y gymhariaeth ult. I gymharu rhifau pwynt arnawf, defnyddir cyfarwyddyd arall, fcmp, sy'n gweithio mewn ffordd debyg.
Canlyniadau
Credaf fy mod wedi ymdrin â nodweddion pwysicaf LLVM IR yn y deunydd hwn. Wrth gwrs, mae llawer mwy yma. Yn benodol, gall cynrychiolaeth ganolraddol y cod gynnwys llawer o anodiadau sy'n caniatáu pasiau optimeiddio i ystyried rhai nodweddion o'r cod sy'n hysbys i'r casglwr na ellir eu mynegi fel arall yn IR. Er enghraifft, baner yw hon inbounds Cyfarwyddiadau GEP, neu fflagiau nsw и nuw, y gellir ei ychwanegu at y cyfarwyddiadau add. Mae'r un peth yn wir am yr allweddair private, gan nodi i'r optimizer na chyfeirir at y swyddogaeth y mae'n ei nodi o'r tu allan i'r uned grynhoi gyfredol. Mae hyn yn caniatáu ar gyfer llawer o optimeiddiadau rhyng-weithdrefnol diddorol fel dileu dadleuon nas defnyddiwyd.
Gallwch ddarllen mwy am LLVM yn , y byddwch yn cyfeirio ato'n aml wrth ddatblygu eich casglwr LLVM eich hun. Yma , sy'n edrych ar ddatblygu casglwr ar gyfer iaith syml iawn. Bydd y ddwy ffynhonnell wybodaeth hyn yn ddefnyddiol i chi wrth greu eich casglwr eich hun.
Annwyl ddarllenwyr! Ydych chi'n defnyddio LLVM?
Ffynhonnell: hab.com