Розробка компілятора – дуже важке завдання. Але, на щастя, з розвитком проектів на кшталт 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