LLVM-ն Go տեսանկյունից

Կոմպիլյատոր մշակելը շատ բարդ խնդիր է։ Բայց, բարեբախտաբար, LLVM-ի նման նախագծերի մշակմամբ, այս խնդրի լուծումը մեծապես պարզեցվում է, ինչը թույլ է տալիս նույնիսկ մեկ ծրագրավորողի ստեղծել նոր լեզու, որն իր կատարողականությամբ մոտ է C-ին: LLVM-ի հետ աշխատանքը բարդանում է նրանով, որ սա համակարգը ներկայացված է հսկայական քանակությամբ կոդով, որը հագեցած է փոքր փաստաթղթերով: Այս թերությունը շտկելու համար նյութի հեղինակը, որի թարգմանությունը մենք այսօր հրապարակում ենք, պատրաստվում է ցուցադրել Go-ում գրված կոդերի օրինակներ և ցույց տալ, թե ինչպես են դրանք սկզբում թարգմանվել։ Գնացեք SSA, իսկ հետո LLVM IR-ում՝ օգտագործելով կոմպիլյատորը tinyGO. Go SSA և LLVM IR ծածկագիրը փոքր-ինչ խմբագրվել է՝ հեռացնելու բաները, որոնք չեն համապատասխանում այստեղ տրված բացատրություններին, որպեսզի բացատրություններն ավելի հասկանալի լինեն:

Առաջին օրինակը

Առաջին գործառույթը, որը ես պատրաստվում եմ նայել այստեղ, թվեր գումարելու պարզ մեխանիզմ է.

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

Այս ֆունկցիան շատ պարզ է, և, հավանաբար, ավելի պարզ բան չի կարող լինել։ Այն թարգմանվում է հետևյալ Go SSA կոդով.

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

Այս դիտմամբ տվյալների տիպի ակնարկները տեղադրվում են աջ կողմում և շատ դեպքերում կարող են անտեսվել:

Այս փոքրիկ օրինակն արդեն թույլ է տալիս տեսնել SSA-ի մեկ ասպեկտի էությունը: Մասնավորապես, ծածկագիրը SSA ձևի վերածելիս յուրաքանչյուր արտահայտություն բաժանվում է ամենատարրական մասերի, որոնցից այն կազմված է: Մեր դեպքում հրամանը return a + b, փաստորեն, ներկայացնում է երկու գործողություն՝ երկու թվերի գումարում և արդյունքի վերադարձ:

Բացի այդ, այստեղ կարող եք տեսնել ծրագրի հիմնական բլոկները, այս կոդում կա միայն մեկ բլոկ՝ մուտքի բլոկ: Բլոկների մասին ավելի շատ կխոսենք ստորև:

Go SSA կոդը հեշտությամբ փոխակերպվում է LLVM IR.

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

Այն, ինչ կարող եք նկատել, այն է, որ չնայած այստեղ օգտագործվում են տարբեր շարահյուսական կառույցներ, ֆունկցիայի կառուցվածքը հիմնականում անփոփոխ է: LLVM IR կոդը մի փոքր ավելի ուժեղ է, քան Go SSA կոդը, որը նման է C-ին: Այստեղ, ֆունկցիայի հռչակագրում, նախ կա նկարագրություն այն տվյալների տեսակի, որը նա վերադարձնում է, փաստարկի տեսակը նշվում է արգումենտի անունից առաջ: Բացի այդ, IR վերլուծությունը պարզեցնելու համար գլոբալ սուբյեկտների անուններին նախորդում է խորհրդանիշը @, իսկ տեղական անուններից առաջ խորհրդանիշ կա % (գործառույթը համարվում է նաև գլոբալ միավոր):

Մի բան, որ պետք է նշել այս կոդի վերաբերյալ, այն է, որ Go-ի տիպի ներկայացման որոշումը int, որը կարող է ներկայացվել որպես 32-բիթանոց կամ 64-բիթանոց արժեք՝ կախված կոմպիլյատորից և կոմպիլյացիայի թիրախից, ընդունվում է, երբ LLVM-ն ստեղծում է IR կոդը։ Սա այն բազմաթիվ պատճառներից մեկն է, որ LLVM IR կոդը, ինչպես շատերն են կարծում, անկախ հարթակ չէ: Նման ծածկագիրը, որը ստեղծվել է մեկ հարթակի համար, չի կարող պարզապես վերցվել և կազմվել մեկ այլ հարթակի համար (եթե դուք հարմար չեք այս խնդիրը լուծելու համար ծայրահեղ զգուշությամբ).

Մեկ այլ հետաքրքիր կետ, որը արժե ուշադրություն դարձնել, այն է, որ տեսակը i64 ստորագրված ամբողջ թիվ չէ. այն չեզոք է թվի նշանը ներկայացնելու առումով: Կախված հրահանգից, այն կարող է ներկայացնել ինչպես ստորագրված, այնպես էլ անստորագիր թվեր: Գումարման գործողության ներկայացման դեպքում դա նշանակություն չունի, ուստի ստորագրված կամ անստորագիր թվերի հետ աշխատելու տարբերություն չկա։ Այստեղ ես կցանկանայի նշել, որ C լեզվում ստորագրված ամբողջ փոփոխականի հորդառատությունը հանգեցնում է անորոշ պահվածքի, ուստի Clang ճակատը դրոշակ է ավելացնում գործողությանը: nsw (ստորագրված փաթեթ չկա), ինչը LLVM-ին ասում է, որ կարող է ենթադրել, որ հավելումը երբեք չի հորդում:

Սա կարող է կարևոր լինել որոշ օպտիմալացումների համար: Օրինակ՝ ավելացնելով երկու արժեք i16 32-բիթանոց հարթակում (32-բիթանոց ռեգիստրներով) ավելացումից հետո անհրաժեշտ է նշանի ընդլայնման գործողություն՝ տիրույթում մնալու համար i16. Դրա պատճառով հաճախ ավելի արդյունավետ է ամբողջ թվով գործողություններ կատարելը` հիմնված մեքենաների ռեգիստրի չափերի վրա:

Այն, ինչ տեղի կունենա հետո այս IR ծածկագրի հետ, այժմ մեզ առանձնապես չի հետաքրքրում: Կոդը օպտիմիզացված է (բայց մեր նման պարզ օրինակի դեպքում ոչինչ օպտիմիզացված չէ) և այնուհետև վերածվում մեքենայի կոդի։

Երկրորդ օրինակ

Հաջորդ օրինակը, որը մենք կանդրադառնանք, կլինի մի փոքր ավելի բարդ: Մասնավորապես, մենք խոսում ենք մի ֆունկցիայի մասին, որն ամփոփում է ամբողջ թվերի մի հատված.

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

Այս կոդը վերածվում է հետևյալ Go SSA կոդի.

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

Այստեղ դուք արդեն կարող եք տեսնել ավելի շատ կոնստրուկցիաներ, որոնք բնորոշ են կոդը SSA ձևով ներկայացնելու համար: Թերևս այս կոդի ամենաակնառու առանձնահատկությունն այն է, որ չկան կառուցվածքային հոսքի կառավարման հրամաններ: Հաշվարկների հոսքը վերահսկելու համար կան միայն պայմանական և անվերապահ թռիչքներ, իսկ եթե այս հրամանը դիտարկենք որպես հոսքը վերահսկելու հրաման, ապա վերադարձի հրաման:

Փաստորեն, այստեղ դուք կարող եք ուշադրություն դարձնել այն փաստին, որ ծրագիրը չի բաժանվում բլոկների, օգտագործելով գանգուր braces (ինչպես C լեզուների ընտանիքում): Այն բաժանված է պիտակներով, որոնք հիշեցնում են անսամբլի լեզուները և ներկայացված են հիմնական բլոկների տեսքով: SSA-ում հիմնական բլոկները սահմանվում են որպես կոդերի հարակից հաջորդականություններ, որոնք սկսվում են պիտակով և ավարտվում հիմնական բլոկների ավարտման հրահանգներով, ինչպիսիք են − return и jump.

Այս կոդի մեկ այլ հետաքրքիր մանրամասն ներկայացված է հրահանգով phi. Հրահանգները բավականին անսովոր են և կարող են որոշ ժամանակ պահանջել հասկանալու համար: հիշիր, որ SSA- ն կարճ է Static Single Assignment-ի համար: Սա կոմպիլյատորների կողմից օգտագործվող կոդի միջանկյալ ներկայացումն է, որում յուրաքանչյուր փոփոխականի արժեք է վերագրվում միայն մեկ անգամ։ Սա հիանալի է մեր գործառույթի նման պարզ գործառույթներ արտահայտելու համար myAddցուցադրված է վերևում, բայց հարմար չէ ավելի բարդ գործառույթների համար, ինչպիսին է այս բաժնում քննարկված գործառույթը sum. Մասնավորապես, փոփոխականները փոփոխվում են օղակի կատարման ընթացքում i и n.

SSA-ն շրջանցում է այսպես կոչված հրահանգի միջոցով մեկ անգամ փոփոխական արժեքներ նշանակելու սահմանափակումը phi (նրա անունը վերցված է հունական այբուբենից): Փաստն այն է, որ որպեսզի SSA-ի կոդերի ներկայացումը ստեղծվի C-ի նման լեզուների համար, դուք պետք է դիմեք որոշ հնարքների: Այս հրահանգը կանչելու արդյունքը փոփոխականի ընթացիկ արժեքն է (i կամ n), և որպես դրա պարամետրեր օգտագործվում է հիմնական բլոկների ցանկը: Օրինակ, հաշվի առեք այս հրահանգը.

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

Դրա իմաստը հետևյալն է՝ եթե նախորդ հիմնական բլոկը բլոկ էր entry (մուտք), ապա t0 հաստատուն է 0, և եթե նախորդ հիմնական բլոկը եղել է for.body, ապա դուք պետք է վերցնեք արժեքը t6 այս բլոկից: Այս ամենը կարող է բավականին առեղծվածային թվալ, բայց հենց այս մեխանիզմն է ստիպում SSA-ին աշխատել: Մարդկային տեսանկյունից այս ամենը դժվարացնում է կոդը հասկանալը, բայց այն փաստը, որ յուրաքանչյուր արժեք նշանակվում է միայն մեկ անգամ, շատ օպտիմալացումներ շատ ավելի հեշտացնում է:

Նկատի ունեցեք, որ եթե դուք գրում եք ձեր սեփական կոմպիլյատորը, ապա սովորաբար ստիպված չեք լինի զբաղվել նման բաների հետ: Նույնիսկ Clang-ը չի առաջացնում այս բոլոր հրահանգները phi, այն օգտագործում է մեխանիզմ alloca (դա նման է սովորական տեղական փոփոխականների հետ աշխատելուն): Այնուհետև, երբ աշխատում է LLVM օպտիմալացման անցագիր, որը կոչվում է mem2reg, հրահանգներ alloca փոխարկվել է SSA ձևի: TinyGo-ն, այնուամենայնիվ, մուտքագրում է ստանում Go SSA-ից, որը հարմար կերպով արդեն փոխարկվել է SSA ձևի:

Քննարկվող միջանկյալ կոդի հատվածի մեկ այլ նորամուծություն այն է, որ ինդեքսի կտրվածքի տարրերին հասանելիությունը ներկայացված է հասցեի հաշվարկման գործողության և ստացված ցուցիչի վերաբերման գործողության տեսքով: Այստեղ դուք կարող եք տեսնել հաստատունների ուղղակի ավելացումը IR կոդին (օրինակ. 1:int) Գործառույթով օրինակում myAdd սա չի օգտագործվել: Այժմ, երբ մենք դուրս ենք եկել այդ հնարավորություններից, եկեք տեսնենք, թե ինչ է դառնում այս կոդը 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
}

Այստեղ, ինչպես նախկինում, կարող ենք տեսնել նույն կառուցվածքը, որն իր մեջ ներառում է այլ շարահյուսական կառույցներ։ Օրինակ՝ զանգերի մեջ phi արժեքները և պիտակները փոխվել են: Այնուամենայնիվ, այստեղ կա մի բան, որի վրա արժե հատուկ ուշադրություն դարձնել.

Սկզբից այստեղ դուք կարող եք տեսնել բոլորովին այլ գործառույթի ստորագրություն: LLVM-ն չի աջակցում հատվածներին, և արդյունքում, որպես օպտիմալացում, TinyGo կոմպիլյատորը, որը ստեղծեց այս միջանկյալ կոդը, բաժանեց այս տվյալների կառուցվածքի նկարագրությունը մասերի: Այն կարող է ներկայացնել երեք կտոր տարրեր (ptr, len и cap) որպես կառուցվածք (struct), բայց դրանք որպես երեք առանձին կազմավորումներ ներկայացնելը թույլ է տալիս որոշակի օպտիմալացումներ: Այլ կոմպիլյատորներ կարող են ներկայացնել հատվածը այլ կերպ՝ կախված թիրախային հարթակի գործառույթների կանչի պայմանից:

Այս կոդի մեկ այլ հետաքրքիր առանձնահատկությունը հրահանգի օգտագործումն է getelementptr (հաճախ կրճատվում է որպես GEP):

Այս հրահանգը աշխատում է ցուցիչների հետ և օգտագործվում է կտոր տարրի ցուցիչ ստանալու համար: Օրինակ, եկեք այն համեմատենք C-ով գրված հետևյալ կոդի հետ.

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

Կամ սրան հետևյալ համարժեքով.

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

Այստեղ ամենակարեւորն այն է, որ հրահանգները getelementptr չի կատարում վերաբերման գործողություններ. Այն պարզապես հաշվարկում է նոր ցուցիչը՝ հիմնվելով գոյություն ունեցողի վրա: Այն կարող է ընդունվել որպես հրահանգ mul и add ապարատային մակարդակում: Դուք կարող եք ավելին կարդալ GEP հրահանգների մասին այստեղ.

Այս միջանկյալ կոդի մեկ այլ հետաքրքիր առանձնահատկությունն է հրահանգի օգտագործումը icmp. Սա ընդհանուր նշանակության հրահանգ է, որն օգտագործվում է ամբողջ թվերի համեմատություններ իրականացնելու համար: Այս հրահանգի արդյունքը միշտ տիպի արժեք է i1 - տրամաբանական արժեք. Այս դեպքում համեմատությունը կատարվում է հիմնաբառի օգտագործմամբ slt (ստորագրված է ավելի քիչ, քան), քանի որ մենք համեմատում ենք երկու թվեր, որոնք նախկինում ներկայացված էին տիպով int. Եթե ​​համեմատեինք երկու անստորագիր ամբողջ թվեր, ապա կօգտագործեինք icmp, և համեմատության մեջ օգտագործվող հիմնաբառը կլինի ult. Լողացող կետով թվերը համեմատելու համար օգտագործվում է մեկ այլ հրահանգ. fcmp, որն աշխատում է նույն կերպ։

Արդյունքները

Կարծում եմ, որ այս նյութում ես լուսաբանել եմ LLVM IR-ի ամենակարևոր հատկանիշները: Իհարկե, այստեղ շատ ավելին կա: Մասնավորապես, կոդի միջանկյալ ներկայացումը կարող է պարունակել բազմաթիվ անոտացիաներ, որոնք թույլ են տալիս օպտիմալացման անցումները հաշվի առնել կոմպիլյատորին հայտնի կոդի որոշ առանձնահատկություններ, որոնք այլ կերպ չեն կարող արտահայտվել IR-ով: Օրինակ, սա դրոշ է inbounds GEP հրահանգներ կամ դրոշներ nsw и nuw, որը կարող է ավելացվել հրահանգներին add. Նույնը վերաբերում է բանալի բառին private, նշելով օպտիմիզատորին, որ այն գործառույթը, որը նա նշում է, չի հղում կատարվող ընթացիկ կոմպիլյացիայի միավորից դուրս: Սա թույլ է տալիս շատ հետաքրքիր միջընթացակարգային օպտիմալացումներ, ինչպիսիք են չօգտագործված փաստարկների վերացումը:

LLVM-ի մասին ավելին կարող եք կարդալ այստեղ փաստաթղթավորում, որին դուք հաճախ կանդրադառնաք ձեր սեփական LLVM վրա հիմնված կոմպիլյատորը մշակելիս: Այստեղ ղեկավարությունը, որը նայում է շատ պարզ լեզվի համար կոմպիլյատոր մշակելուն: Տեղեկատվության այս երկու աղբյուրներն էլ ձեզ օգտակար կլինեն ձեր սեփական կոմպիլյատոր ստեղծելիս:

Հարգելի ընթերցողներ: Դուք օգտվո՞ւմ եք LLVM-ից:

Source: www.habr.com