Хабрахабр

[Перевод] LLVM с точки зрения Go

Разработка компилятора — очень тяжёлая задача. Но, к счастью, с развитием проектов наподобие LLVM решение этой задачи значительно упрощается, что позволяет даже программисту-одиночке создать новый язык, близкий по производительности к C. Работа с LLVM осложняется тем, что эта система представлена огромным объёмом кода, снабжённого небольшой документацией. Для того чтобы попытаться этот недостаток исправить, автор материала, перевод которого мы сегодня публикуем, собирается продемонстрировать примеры кода, написанного на Go, и показать, как они транслируются сначала в Go SSA, а потом — в LLVM IR с использованием компилятора TinyGO. Код Go SSA и LLVM IR был немного отредактирован, из него было удалено то, что не относится к приводимым тут пояснениям, ради того, чтобы эти пояснения оказались бы более понятными.

image

Первый пример

Первая функция, которую я собираюсь тут разобрать, представляет собой простой механизм для сложения чисел:

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-парсинга, перед именами глобальных сущностей стоит символ @, а перед именами локальных — символ % (функция тоже считается глобальной сущностью).

Это — одна из многих причин того, что LLVM IR-код не является, как многие думают, платформенно-независимым. Одна из особенностей этого кода, на которую нужно обратить внимание, заключается в том, что решение о представлении типа Go int, который может быть представлен 32-битным или 64-битным значением, в зависимости от компилятора и от цели компиляции, принимается при создании LLVM IR-кода. Такой код, созданный для одной платформы, нельзя просто взять и скомпилировать для другой платформы (если только не подойти к решению этой задачи с особой осторожностью).

В зависимости от инструкции он может представлять как числа со знаком, так и числа без знака. Ещё один интересный момент, который стоит отметить, заключается в том, что тип i64 — это не целое число со знаком: он нейтрален в плане представления знака числа. Тут хотелось бы отметить, что в языке C переполнение целочисленной переменной со знаком приводит к неопределённому поведению, поэтому фронтенд Clang добавляет к операции флаг nsw (no signed wrap), что указывает LLVM на то, что он может исходить из предположения о том, что при сложении никогда не происходит переполнения. В случае с представлением операции сложения это роли не играет, поэтому здесь нет разницы в работе с числами со знаком или без знака.

Например, сложение двух значений i16 на 32-битной платформе (с 32-битными регистрами) нуждается, после выполнения сложения, в операции расширения знака, для того чтобы оставаться в диапазоне i16. Это может быть важным для некоторых оптимизаций. Из-за этого часто более эффективным оказывается выполнение целочисленных операций с учётом машинных размеров регистра.

Код оптимизируется (но в случае с таким простым примером, как наш, ничего уже не оптимизируется), а затем преобразуется в машинный код. То, что происходит в дальнейшем с этим IR-кодом, сейчас нас не особенно интересует.

Второй пример

Следующий пример, который мы рассмотрим, будет немного сложнее. А именно, речь идёт о функции, которая суммирует слайс целых чисел:

func sum(numbers []int) int 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. В частности, в ходе выполнения цикла меняются переменные i и n. Это отлично подходит для выражения простых функций, наподобие нашей функции myAdd, показанной выше, но не подходит для более сложных функций — наподобие рассматриваемой в этом разделе функции sum.

Дело в том, что для того чтобы SSA-представление кода можно было бы сформировать для языков наподобие C, приходится прибегать к некоторым хитростям. SSA обходит ограничение на однократное присваивание значений переменных с использованием так называемой инструкции phi (её название взято из греческого алфавита). Например, рассмотрим такую инструкцию: Результатом вызова этой инструкции является текущее значение переменной (i или n), а в качестве её параметров используется список базовых блоков.

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

Её смысл заключается в следующем: если предыдущим базовым блоком был блок entry (входной), то t0 — это константа 0, а если предыдущим базовым блоком был for.body, то нужно взять значение t6 из этого блока. Выглядеть всё это может довольно-таки таинственным, но благодаря этому механизму обеспечивается работа SSA. С человеческой точки зрения всё это усложняет понимание кода, но тот факт, что каждое значение назначается лишь один раз, значительно упрощает многие оптимизации.

Даже Clang не генерирует все эти инструкции phi, он использует механизм alloca (он напоминает работу с обычными локальными переменными). Обратите внимание на то, что если вы пишете собственный компилятор, то вам обычно не приходится иметь дело с подобными вещами. TinyGo, однако, получает входные данные от Go SSA, которые, что удобно, уже преобразованы в форму SSA. Затем, при выполнении прохода оптимизации LLVM, называемого mem2reg, инструкции alloca преобразуются в форму SSA.

Тут можно видеть и непосредственное добавление констант в IR-код (например — 1:int). Ещё одно новшество рассматриваемого фрагмента промежуточного кода заключается в том, что доступ к элементам слайса по индексу представлен в виде операции вычисления адреса и операции разыменования полученного указателя. Теперь, разобравшись с этими особенностями, взглянем на то, во что превратится этот код при преобразовании его в форму LLVM IR: В примере с функцией 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 поменялись местами значения и метки. Однако тут есть и кое-что такое, на что стоит обратить особое внимание.

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. В данном случае производится сравнение с использованием ключевого слова slt (signed less than), так как сравниваем мы два числа, ранее представленных типом int. Результатом выполнения этой инструкции всегда является значение типа i1 — логическое значение. Для сравнения чисел с плавающей точкой используется другая инструкция, fcmp, работающая похожим образом. Если бы мы сравнивали два целых числа без знака, тогда в качестве инструкции мы воспользовались бы icmp, а ключевым словом, используемым при сравнении, было бы ult.

Итоги

Полагаю, что в этом материале я рассмотрел самые важные особенности LLVM IR. Конечно, тут есть ещё очень много всего. В частности, в промежуточном представлении кода может присутствовать множество аннотаций, позволяющих учитывать при проходах оптимизации определённые особенности кода, известные компилятору, которые нельзя другим способом выразить в IR. Например, это флаг inbounds инструкции GEP, или флаги nsw и nuw, которые могут быть добавлены к инструкции add. То же самое касается и ключевого слова private, указывающего оптимизатору на то, что на отмеченную им функцию не будут ссылаться извне текущей единицы компиляции. Это позволяет выполнять множество интересных межпроцедурных оптимизаций наподобие устранения неиспользуемых аргументов.

Вот руководство, в котором рассматривается разработка компилятора для очень простого языка. Подробности о LLVM можно почитать в документации, к которой вы будете часто обращаться, разрабатывая собственный компилятор, основанный на LLVM. Оба этих источника информации пригодятся вам при создании собственного компилятора.

Уважаемые читатели! Пользуетесь ли вы LLVM?

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть