ЛЛВМ из перспективе Го

Развој компајлера је веома тежак задатак. Али, на срећу, развојем пројеката попут ЛЛВМ-а, решење овог проблема је у великој мери поједностављено, што омогућава чак и једном програмеру да креира нови језик који је по перформансама близак Ц. Рад са ЛЛВМ-ом је компликован чињеницом да је ово систем је представљен огромном количином кода, опремљен са мало документације. Да би покушао да исправи овај недостатак, аутор материјала, чији превод данас објављујемо, демонстрираће примере кода написаног у Го-у и показати како се они прво преводе у Иди ССА, а затим у ЛЛВМ ИР користећи компајлер ТиниГО. Го ССА и ЛЛВМ ИР код је мало измењен да би се уклониле ствари које нису релевантне за објашњења која су овде дата, како би објашњења била разумљивија.

Први пример

Прва функција коју ћу овде погледати је једноставан механизам за додавање бројева:

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

Ова функција је веома једноставна и, можда, ништа не може бити једноставније. Преводи се у следећи Го ССА код:

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

Са овим приказом, наговештаји за тип података се постављају са десне стране и могу се занемарити у већини случајева.

Овај мали пример вам већ омогућава да видите суштину једног аспекта ССА. Наиме, приликом конвертовања кода у ССА форму, сваки израз се разлаже на најелементарније делове од којих је састављен. У нашем случају команда return a + b, у ствари, представља две операције: сабирање два броја и враћање резултата.

Поред тога, овде можете видети основне блокове програма; у овом коду постоји само један блок - блок за унос. У наставку ћемо више причати о блоковима.

Го ССА код се лако претвара у ЛЛВМ ИР:

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

Оно што можете приметити је да иако се овде користе различите синтаксичке структуре, структура функције је у основи непромењена. ЛЛВМ ИР код је мало јачи од Го ССА кода, сличан Ц. Овде, у декларацији функције, прво постоји опис типа података који враћа, тип аргумента је назначен пре имена аргумента. Поред тога, да би се поједноставило ИР рашчлањивање, именима глобалних ентитета претходи симбол @, а испред локалних назива стоји симбол % (функција се такође сматра глобалним ентитетом).

Једна ствар коју треба приметити у вези са овим кодом је одлука Го о представљању типа int, који може бити представљен као 32-битна или 64-битна вредност, у зависности од компајлера и циља компилације, прихвата се када ЛЛВМ генерише ИР код. Ово је један од многих разлога зашто ЛЛВМ ИР код није, како многи мисле, независан од платформе. Такав код, креиран за једну платформу, не може се једноставно узети и компајлирати за другу платформу (осим ако нисте погодни за решавање овог проблема са изузетном пажњом).

Још једна занимљива ствар коју вреди напоменути је да тип i64 није цео број са предзнаком: неутралан је у смислу представљања предзнака броја. У зависности од инструкције, може представљати и потписане и непотписане бројеве. У случају представљања операције сабирања, ово није битно, тако да нема разлике у раду са бројевима са предзнаком или без предзнака. Овде бих желео да приметим да у језику Ц, прекорачење потписане променљиве целог броја доводи до недефинисаног понашања, тако да Цланг фронтенд додаје заставицу операцији nsw (без потписаног омота), што говори ЛЛВМ-у да може претпоставити да се сабирање никада не прелива.

Ово може бити важно за неке оптимизације. На пример, додавање две вредности i16 на 32-битној платформи (са 32-битним регистрима) захтева, након додавања, операцију проширења знака да би остао у домету i16. Због тога је често ефикасније изводити целобројне операције на основу величина регистра машина.

Шта се даље дешава са овим ИР кодом нас сада не занима. Код се оптимизује (али у случају једноставног примера као што је наш, ништа није оптимизовано) и затим се конвертује у машински код.

Други пример

Следећи пример који ћемо погледати биће мало компликованији. Наиме, говоримо о функцији која сабира исечак целих бројева:

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

Овај код се претвара у следећи Го ССА код:

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

Овде већ можете видети више конструкција типичних за представљање кода у ССА форми. Можда је најочигледнија карактеристика овог кода чињеница да не постоје структуриране команде за контролу тока. За контролу тока прорачуна постоје само условни и безусловни скокови, и, ако ову команду сматрамо командом за контролу тока, командом за повратак.

У ствари, овде можете обратити пажњу на чињеницу да програм није подељен на блокове помоћу витичастих заграда (као у породици језика Ц). Подељен је ознакама, који подсећају на асемблерске језике, и представљен у облику основних блокова. У ССА, основни блокови су дефинисани као непрекидне секвенце кода које почињу ознаком и завршавају основним упутствима за завршетак блока, као што је – return и jump.

Још један занимљив детаљ овог кода представља инструкција phi. Упутства су прилично необична и може потрајати неко време да се разумеју. запамтите да ССА је скраћеница од Статиц Сингле Ассигнмент. Ово је средњи приказ кода који користе компајлери, у којем се свакој променљивој додељује вредност само једном. Ово је одлично за изражавање једноставних функција као што је наша функција myAddприказано изнад, али није погодно за сложеније функције као што је функција о којој се говори у овом одељку sum. Конкретно, променљиве се мењају током извршавања петље i и n.

ССА заобилази ограничење за додељивање вредности променљивих једном користећи такозвану инструкцију phi (име му је преузето из грчког алфабета). Чињеница је да да би се ССА репрезентација кода генерисала за језике као што је Ц, морате да прибегнете неким триковима. Резултат позивања ове инструкције је тренутна вредност променљиве (i или n), а као његови параметри се користи листа основних блокова. На пример, размотрите ово упутство:

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

Његово значење је следеће: ако је претходни основни блок био блок entry (унос), затим t0 је константа 0, а ако је претходни основни блок био for.body, онда треба да узмете вредност t6 из овог блока. Све ово може изгледати прилично мистериозно, али овај механизам је оно што чини ССА да функционише. Из људске перспективе, све ово чини код тешким за разумевање, али чињеница да се свака вредност додељује само једном чини многе оптимизације много лакшим.

Имајте на уму да ако пишете сопствени компајлер, обично нећете морати да се бавите оваквим стварима. Чак ни Цланг не генерише сва ова упутства phi, користи механизам alloca (личи на рад са обичним локалним варијаблама). Затим, када се покреће ЛЛВМ оптимизацијски пролаз позван мем2рег, упутства alloca претворен у ССА облик. ТиниГо, међутим, прима податке од Го ССА, који је, згодно, већ конвертован у ССА облик.

Још једна иновација фрагмента међукода који се разматра је да је приступ елементима пресека по индексу представљен у облику операције израчунавања адресе и операције дереференцирања резултујућег показивача. Овде можете видети директно додавање константи у ИР код (на пример - 1:int). У примеру са функцијом myAdd ово није коришћено. Сада када смо склонили те функције са пута, хајде да погледамо шта овај код постаје када се конвертује у ЛЛВМ ИР облик:

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 вредности и ознаке замењене. Ипак, овде постоји нешто на шта вреди обратити посебну пажњу.

За почетак, овде можете видети потпуно другачији потпис функције. ЛЛВМ не подржава резове, и као резултат тога, као оптимизација, ТиниГо компајлер који је генерисао овај међукод поделио је опис ове структуре података на делове. Може представљати три елемента пресека (ptr, len и cap) као структура (структура), али њихово представљање као три одвојена ентитета омогућава неке оптимизације. Други преводиоци могу представљати исечак на друге начине, у зависности од конвенција позивања функција циљне платформе.

Још једна занимљива карактеристика овог кода је употреба инструкције getelementptr (често скраћено као ГЕП).

Ово упутство ради са показивачима и користи се за добијање показивача на елемент пресека. На пример, упоредимо га са следећим кодом написаним у Ц:

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

Или са следећим еквивалентом овоме:

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

Овде је најважније да упутства getelementptr не врши операције дереференцирања. Само израчунава нови показивач на основу постојећег. Може се узети као упутства mul и add на нивоу хардвера. Можете прочитати више о ГЕП упутствима овде.

Још једна занимљива карактеристика овог међукода је употреба инструкције icmp. Ово је инструкција опште намене која се користи за имплементацију поређења целих бројева. Резултат извршавања ове инструкције је увек вредност типа i1 — логичка вредност. У овом случају, поређење се врши помоћу кључне речи slt (потписано мање од), пошто упоређујемо два броја претходно представљена типом int. Ако бисмо упоређивали два неозначена цела броја, онда бисмо користили icmp, а кључна реч која се користи у поређењу би била ult. За упоређивање бројева са плутајућим зарезом користи се друга инструкција, fcmp, који ради на сличан начин.

Резултати

Верујем да сам у овом материјалу покрио најважније карактеристике ЛЛВМ ИР. Наравно, овде има још много тога. Конкретно, средња репрезентација кода може садржати много напомена које омогућавају оптимизацијске пролазе како би се узеле у обзир одређене карактеристике кода познате компајлеру које се другачије не могу изразити у ИР. На пример, ово је застава inbounds ГЕП упутства, или заставице nsw и nuw, који се може додати упутствима add. Исто важи и за кључну реч private, што указује оптимизатору да функција коју он означава неће бити референцирана изван тренутне јединице компилације. Ово омогућава много занимљивих међупроцедуралних оптимизација као што је елиминисање неискоришћених аргумената.

Више о ЛЛВМ-у можете прочитати у документација, на коју ћете се често позивати када развијате сопствени компајлер заснован на ЛЛВМ-у. Ево вођство, који се бави развојем компајлера за веома једноставан језик. Оба ова извора информација ће вам бити од користи када правите сопствени компајлер.

Драги читаоци! Да ли користите ЛЛВМ?

Извор: ввв.хабр.цом