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 (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. Инструкциите са доста необичайни и може да отнеме известно време, за да ги разберете. не забравяйте, че 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?

Източник: www.habr.com