LLVM с точки зрения Go

Разработка компилятора — очень тяжёлая задача. Но, к счастью, с развитием проектов наподобие LLVM, решение этой задачи значительно упрощается, что позволяет даже программисту-одиночке создать новый язык, близкий по производительности к C. Работа с LLVM осложняется тем, что эта система представлена огромным объёмом кода, снабжённого небольшой документацией. Для того чтобы попытаться этот недостаток исправить, автор материала, перевод которого мы сегодня публикуем, собирается продемонстрировать примеры кода, написанного на Go, и показать, как они транслируются сначала в 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, на самом деле, представляет собой две операции: сложение двух чисел и возврат результата.

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

Итоги

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

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

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