Распрацоўка кампілятара - вельмі цяжкая задача. Але, на шчасце, з развіццём праектаў накшталт LLVM, рашэнне гэтай задачы значна спрашчаецца, што дазваляе нават праграмісту-адзіночцы стварыць новую мову, блізкую па прадукцыйнасці да C. Праца з LLVM ускладняецца тым, што гэтая сістэма прадстаўлена велізарным аб'ёмам кода, забяспечанага невялікай дакументацыяй . Для таго каб паспрабаваць гэты недахоп выправіць, аўтар матэрыялу, пераклад якога мы сёння публікуем, збіраецца прадэманстраваць прыклады кода, напісанага на Go, і паказаць, як яны транслююцца спачатку ў , а потым - у LLVM IR з выкарыстаннем кампілятара . Код 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, на самай справе, уяўляе сабой дзве аперацыі: складанне двух лікаў і вяртанне выніку.
Акрамя таго, тут можна бачыць і базавыя блокі праграмы, у дадзеным кодзе маецца ўсяго адзін блок - уваходны (entry block). Больш падрабязна пра блокі мы пагаворым ніжэй.
Код 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 (no signed wrap), што паказвае 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. Верагодна, найбольш відавочнай асаблівасцю гэтага кода з'яўляецца той факт, што тут няма структураваных каманд кіравання патокам вылічэнняў. Для кіравання патокам вылічэнняў тут ёсць толькі ўмоўныя і безумоўныя пераходы, і, калі лічыць гэтую каманду камандай для кіравання патокам, каманда вяртання.
Насамрэч, тут можна звярнуць увагу на тое, што праграма не падзелена на блокі з выкарыстаннем фігурных дужак (як у мовах сямейства C). Яна падзелена пазнакамі, што нагадвае асэмблерныя мовы, і прадстаўлена ў выглядзе базавых блокаў. У SSA базавымі блокамі завуцца бесперапынныя паслядоўнасці кода, якія пачынаюцца з пазнакі і сканчаюцца інструкцыямі завяршэння базавага блока, напрыклад — return и jump.
Яшчэ адна цікавая дэталь гэтага кода прадстаўлена інструкцыяй phi. Інструкцыя гэтая даволі незвычайная, на тое, каб з ёй разабрацца, можа спатрэбіцца некаторы час. Памятайце, што - гэта скарачэнне для 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, званага , інструкцыі 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 (signed less than), бо параўноўваем мы два лікі, раней прадстаўленых тыпам int. Калі б мы параўноўвалі два цэлыя лікі без знака, тады ў якасці інструкцыі мы скарысталіся б icmp, а ключавым словам, выкарыстоўваным пры параўнанні, было б ult. Для параўнання лікаў з якая плавае кропкай выкарыстоўваецца іншая інструкцыя, fcmp, Якая працуе падобным чынам.
Вынікі
Мяркую, што ў гэтым матэрыяле я разгледзеў найважнейшыя асаблівасці LLVM IR. Вядома, тут ёсьць яшчэ вельмі шмат усяго. У прыватнасці, у прамежкавым уяўленні кода можа прысутнічаць мноства анатацый, якія дазваляюць улічваць пры праходах аптымізацыі вызначаныя асаблівасці кода, вядомыя кампілятару, якія нельга іншым спосабам выказаць у IR. Напрыклад, гэта сцяг inbounds інструкцыі GEP, ці сцягі nsw и nuw, якія могуць быць дададзены да інструкцыі add. Тое ж самае тычыцца і ключавога слова private, Які паказвае аптымізатар на тое, што на адзначаную ім функцыю не будуць спасылацца звонку бягучай адзінкі кампіляцыі. Гэта дазваляе выконваць мноства цікавых міжпрацэдурных аптымізацый накшталт ухілення невыкарыстоўваных аргументаў.
Падрабязнасці аб LLVM можна пачытаць у , Да якой вы будзеце часта звяртацца, распрацоўваючы ўласны кампілятар, заснаваны на LLVM. Вось , у якім разглядаецца распрацоўка кампілятара для вельмі простай мовы. Абодва гэтыя крыніцы інфармацыі спатрэбяцца вам пры стварэнні ўласнага кампілятара.
Паважаныя чытачы! Ці карыстаецеся вы LLVM?
Крыніца: habr.com