Разработването на компилатор е много сложно начинание. Но, за щастие, с развитието на проекти като 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 p) {
entry:
br label %for.loop
for.loop: ; preds = %for.body, %entry
%0 = phi i64 [ 0, %entry ], [ %5, ref.next ]
%1 = phi i64 [ 0, %entry ], [ %6, ref.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
