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. Можеби најочигледната карактеристика на овој код е фактот дека нема структурирани команди за контрола на протокот. За да се контролира текот на пресметките, постојат само условни и безусловни скокови, а ако ја сметаме оваа команда како команда за контрола на протокот, команда за враќање.

Всушност, овде можете да обрнете внимание на фактот дека програмата не е поделена на блокови со помош на кадрави загради (како во семејството на јазици 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 оптимизација помине повикан 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) како структура (структура), но нивното претставување како три посебни ентитети овозможува некои оптимизации. Други компајлери може да го претставуваат парчето на други начини, во зависност од конвенциите за повикување на функциите на целната платформа.

Друга интересна карактеристика на овој код е употребата на инструкцијата 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?

Извор: www.habr.com