Всем привет. Представляю вам перевод статьи о LLVM IR. Текст профессионально-ориентирован и не подойдет для широкого круга читателей. Перевод выполнен специально для форума xss.pro и выкладывается только на данном форуме. (оригинал статьи)
Краткое знакомство с LLVM IR.
На днях я увидел этот твит. В нем, Эндрю Галлант утверждает что внедрение LLVM IR (низкоуровневых виртуальных машин с промежуточным представлением) вместо ассемблера является полезным инструментом для тех кто работает над производительностью. К сожалению, учебный материал по LLVM обычно предназначен для инженеров-программистов компилятора, а не для специалистов широкого профиля.
Итак, поскольку я являюсь таковым, мой ответ это: «конечно вам следует знать, какое промежуточное представление у вашего оптимизатора». Но я считаю, что существует оправданная причина иметь возможность прочитать его, так же как и возможность чтения ассемблера, так как это мощный инструмент для понимания того, что делает ваш процессор. Сначала я рекомендую прочитать первую часть статьи о знакомстве с ассемблером, которую я написал более года назад (и до сих пор не выложил продолжение...
).Изучение LLVM IR схоже, но статья поможет вам понять что делает ваш компилятор для создания высокооптимизированного кода. LLVM IR очень популярен, достаточно обоснован и сформулирован так, что мы можем относиться к нему, как к слегка своеобразному языку программирования.
В этой статье я хочу углубиться в то, чем является LLVM IR и как его прочитать.
Что такое LLVM IR?
“LLVM” это общий термин для некоторых компонентов оборудования. Он может быть использован для создания компиляторов. Если вы писали код, влияющий на производительность, вы скорее всего слышали о нем.
Его основным продуктом является Clang, компилятор-флагман для C/C++/Objective-C. Он имеет традиционную архитектуру компилятора: фронтенд, который анализирует исходный код в AST и переводит его в промежуточное представление (ПП), затем оптимизатор (или «посредник») переводит ПП в более лучший вид и далее бэкенд конвертирует ПП в машинный код под необходимую платформу.
Часто, LLVM относится только к оптимизатору и бэкенду Clang. Это можно рассматривать как компилятор для «языка LLVM» или «ассемблера LLVM». Фактически, Clang, как и другие фронтенды вроде Rust, компилируют в LLVM IR, который затем компилирует все в машинный код.
LLVM IR широко распространен и... в известной мере, стабилен, что делает его очень хорошим инструментом для компиляций, поскольку разработчики языка могут сэкономить тысячи вложенных в него часов. Источником истины в вопросе «что такое LLVM IR?» является LangRef.
LLVM IR имеет также бинарный формат (иногда называемый «биткодом»), хотя мы будем работать исключительно с его текстовым форматом (который использует расширение
.ll).LLVM-ориентированные компиляторы будут иметь флаги отладки, заставляющие их выводить ПП вместо конечного результата. К примеру, для Clang это выглядит так:
clang++ -S -emit-llvm foo.cc, когда для Rust это: rustc --emit=llvm-ir foo.rs. Godbolt также способен воспроизвести данные указания и верно отобразить конечный результат LLVM IR.Вернемся к базовым блокам
LLVM IR может быть довольно пугающим при чтении, поскольку содержит намного больше вспомогательной информации чем дамп сборки. Рассмотрим это значение:
Если вы нажмете на виджет “Godbolt”, вы попадете на его сайт, где он производит это значение в LLVM IR. Большая часть кода это просто метаданные, но выглядит по-настоящему жутко!
Начиная с выходных данных компилятора, кривая сложности будет крутой, потому что нам придется столкнуться со всеми трудностями LLVM IR. Для Rust, это, скорее всего, будет означать столкновение с обработкой исключений, функционированием атрибутов, которые обеспечивают его гарантии для LLVM (к примеру, необнуленные указатели), а также с тем, каким образом реализованы паники.
Но начнем мы со знакомства с базовым синтаксисом LLVM IR, и только потом займемся чтением выходных данных.
Элементарное значение
Основой LLVM IR являются определения значений, представленные командой define. Также присутствует команда
declare, которая имеет ту же цель, что и значение не имеющее тела в языке C: она вводит внешний символ в поле видимости.К примеру, она не получает аргументов и сразу проводит возврат:
Тип возвращаемого значения (
void) идет сразу за ключевым словом define. Значение начинается с @, что напоминает нам принцип сигилов: каждый задаваемый пользователем символ начинается с сигила, обозначая какого вида является этот символ. @ используется для глобальных переменных и значений: для того, к чему вы можете обратиться (когда @ используется с переменными, они всегда используются с типизацией ptr)Тело значения похоже на ассемблер: список меток и команд. Однако, в отличии от стандартного ассемблера, существуют значительные ограничения в структуре этих команд.
В данном случае, у нас только одна команда: возврат с
void типизацией. В отличие от большинства языков-ассемблеров, LLVM IR сильно типизирован и почти везде запрашивает точную сигнатуру типа.Вот еще одно элементарное значение.
Это значение спровоцирует неопределенное поведение: команда
unreachable предоставляет путь выполнения кода, который для компилятора может показаться не исполненным; это, к примеру, не похоже на нереализованную команду ud2 в архитектуре x86, которая гарантированно выдаст ошибку.Это является важным отличием между LLVM IR и любым другим языком-ассемблером: некоторые операции специально оставлены неопределенными для освобождения места приоритетным оптимизациям. Например, LLVM IR может вести себя так, потому что команда
@do_not_call сразу провоцирует неопределенное поведение. Все вызовы этой команды являются также недоступными (и начиная с нее создают недоступность).Код скалярного типа
Начнем с базовых значений, которые могут выполняться только с целыми числами. Рассмотрим следующее значение, которое возводит 32-битное целое число в квадрат:
Сейчас наше значение получает аргумент и содержит несколько команд.
Аргумент указан как
i32 %x. А имена с сигилом % являются чем-то вроде локальных переменных, но с некоторыми ограничениями, что делает их более поддатливыми для оптимизации. Как мы увидим дальше, это не совсем «переменные». Иногда, LLVM называет их регистрами; в каком-то смысле, LLVM IR это ассемблер для абстрактных машин с бесконечным количеством регистров. Далее в этой статье, %-присвоенные имена я буду называть «регистрами».i32 это примитивные типы целых чисел. Все типы целых чисел в LLVM имеют форму iN для всех N (даже не кратных восьми). Здесь нет знаковых или беззнаковых типов, вместо этого, команды которые относятся к «знаковости» определяют используемую ими семантику.Первая команда это
mul i32, которая возводит два i32 операнда вместе и производит возврат значения, а мы назначаем ему новый регистр %11[1]. Следующая команда возвращает это значение.Остальные операторы арифметических вычислений имеют ожидаемые вами названия:
add, sub, and, or, xor, shl (сдвигает результат смены битов влево). Также существуют две команды для деления и остатка, знаковые (sdiv, srem) и беззнаковые (udiv, urem). И две команды для сдвига вправо, опять-же, знаковая (ashr) и беззнаковая (lshr).Задача для читателя: почему
/, %, и >> единственные операции для знаковых и беззнаковых версий?Мы можем также конвертировать из одного типа целых чисел в другой, используя
trunc, zext, и sext, которые отсекают, расширяют до нуля и повышают кол-во битов (sext и zext еще одна знаковая/беззнаковая пара). К примеру, если мы хотим чтобы значение square не переполнилось, мы можем написать:
Здесь мы переводим
%x в i64 путем повышения кол-ва битов (поскольку мы решили что возводим в квадрат целые числа) и затем возводим в квадрат имеющийся результат. trunc и zext имеют такой-же синтаксис, как и sext.«Я еще вернусь»
Разумеется, что интересующая нас функция имеет поток управления. Представьте, что нам требуется функция безопасного деления. Так как деление на ноль вызывает неопределенное поведение, нам нужно провести его с точностью.
Получается что-то вроде этого:
Мы могли-бы попробовать
select («тернарный» оператор LLVM).
Однако, здесь мы сталкиваемся с проблемой: деление на ноль = неопределенное поведение[2], а
select не проводит вычислений по сокращенной схеме (его семантика ближе к семантике cmov в архитектуре x86).Чтобы все верно скомпилировать, следует использовать команду
br, которая представляет общую операцию ветвления[3]. В терминалах языка С, br i1 %cond, label %a, label %b равняются if (cond) goto a; else goto b;.Вот как мы могли-бы это написать:
Теперь у нашей функции есть метки, которые используются командой
br в качестве меток перехода.В первом блоке мы проведем проверку
d == 0, вызываемую командой icmp eq. Она проводит возврат i1 (типа LLVM, который используется для булевских значений). Затем передаем результат br, которая переходит к первой метке в случае, если та является нулем, в любом другом случае – ко второй.Второй блок – это блок предварительных возвратов. Он проводит возврат «контрольного» значения. Третий не требует объяснений.
Каждый из них является «базовым»: последовательный поток неконтролируемых операций вместе с командой, которая выводит управляющий поток из блока. Эти блоки формируют граф потока управления (ГПУ) функции.
Вот также несколько команд «блока-терминатора». Форме
br с одним аргументом присвоена одна метка и простая безусловная команда goto. Тут также используется switch, что схожа со switch в языке С:
switch должна иметь целочисленный тип. Хоть вы и могли-бы отобразить эту операцию с цепочкой br-ов, команда switch облегчит LLVM генерацию таблиц переходов.Команда
unreachable, что мы видели ранее, является особым ограничителем, не вызывающим управляющую конструкцию, но она может завершить блок при достижении им неопределенного поведения. Что, например, является равноценным команде std::unreachable() в языке C++.LLVM удалил мой код!
Команда
unreachable является хорошим примером того, почему LLVM использует базовый блок ГПУ. Вот простейший этап оптимизации удаления мертвого кода:
1. Заполните группу каждым блоком, который заканчивается на
unreachable.
2. Если ограничитель каждого блока ссылается на недоступную группу, удалите эту метку из ограничителя. К примеру, если у нас есть
br i1 %c, label %a, label %b и недоступная группа содержит %a, то мы можем заменить его на br label %b.
3. Если каждое исходящее соединение от блока удалено на 2 пункте, то замените ограничитель командой
unreachable.
4. Удалите все блоки в недоступной группе.
5. Повторите процедуру столько раз, сколько пожелаете.
Шар из
unreachable по наитию взлетает до ГПУ, растворяя в себе его части. Остальные пути доступа, могут генерировать некоторое кол-во unreachable и отобразить неопределенное поведение. Это взаимодействие вместе с процедурой удаления мертвого кода является причиной для фразы «компилятор удалит ваш код».
Текущий путь доступа к удалению мертвого кода более сложен, поскольку вызовы функций затрудняют понимание того, является-ли блок «чистым», и соответственно прозрачно удаляемым.
Но что если мы хотим произвести что-нибудь более сложное, вроде
a / b + 1? Это выражение имеет промежуточный результат, поэтому мы не можем использовать два возврата, как раньше.Работать с этим не так-то просто: если мы попытаемся назначить один и тот-же регистр в разных блоках, то верификатор IR пожалуется. Это подводит нас к концепции статического одиночного присвоения.
Враки! Враки!
LLVM IR это единственное статическое присваивание (ЕСП). Появилось LLVM IR в начале столетия для создания современного ЕСП-оптимизатора в качестве учебного проекта. ЕСП сегодня – широко популярно для оптимизации императивного кода.
ЕСП означает, что каждому регистру присвоено не более одной команды на функцию. Разные исполнения одного и того же блока в одной и той же функции могут производить разные значения для определенных регистров, но мы не можем модифицировать те регистры, которым уже присвоена команда.
Другими словами:
1. Каждый регистр гарантированно будет инициализирован одним-единственным выражением.
2. Каждый регистр зависит только от значений регистров, присвоенных до его определения.
Здесь присутствует множество полезных функций для написания оптимизаций. К примеру, внутри простого блока, каждое использование определенного регистра
%x всегда относится к одному значению, которое делает такие оптимизации как: «глобальное вычисление значений» и «сворачивание констант», более простыми для написания, поскольку здесь не требуется отдельно отслеживать состояние каждого регистра по всему блоку.В ЕСП мы рассматриваем модификацию как множество версий одной переменной. Так, мы можем понизить
x += y как:
Здесь мы использовали соглашение var.n для определения версии переменной, которую представляет указанный регистр. (LLVM не обеспечивает никаких соглашений о наименованиях).
Однако, при появлении циклов становится неясно, как управлять версиями, ведь количество регистров в функции статично, а количество цикличных итераций динамично.
Как конкретно мы реализуем эту функцию?
Мы могли-бы попробовать так:
Но тут есть проблема! Какие определения для
%r и %i являются настоящими? Верификатор ПП пожалуется, что эти регистры зависят напрямую сами от себя, что является нарушением в ЕСП. Так как правильно воспроизвести эту функцию?Одним из выходов может быть обращение к LLVM! Мы неправильно реализуем эту функцию и позволим оптимизатору подчистить ее для нас.
Сначала для проведения модификации, давайте напишем функцию, используя такие операциии по управлению памятью, как
load-ы и store-ы. Мы можем использовать команду alloca для создания слотов стека неизменного размера. Эти команды производят возврат ptr [^clang-codegen].Clang намусорил, а LLVM за ним подчистил
Кстати, именно так Clang и Rust генерируют LLVM IR: переменные стека преобразуются в
alloca-и и управляются через загрузки и хранилища. Временные переменные в основном превращаются в %regs-ы, но иногда компилятор генерирует дополнительные alloca-и чтобы долго не думать о необходимости создания команд phi.
Это довольно удобно, ведь позволяет не задумываться об ЕСП за пределами LLVM, а LLVM в свою очередь может с легкостью избавиться от ненужных
alloca-ов. Код, который я написал для кодогенерации из @pow очень схож с тем, что Rust отправил-бы в LLVM (хотя из-за использования итератора, там присутствует слишком много произведенного Rust-ом мусора, с которым LLVM придется справляться.)
Затем, мы можем передать это оптимизатору LLVM. Команда opt, являющаяся частью дистрибуции LLVM, запускает определенные проходы оптимизатора в ПП. В нашем случае, мы хотим
opt -p mem2reg, которая запускает одиночный проход «память-регистр». Мы также можем запустить opt --O2 или похожую для получения аналогичной оптимизации[4], что запускает clang -O2.Вот результат:
alloca-и изчесли, но мы встретились с новой командой: phi. «φ-узел» это жаргонная форма из документов ЕСП. Греческая буква φ означает «врун, обманщик, жулик». Эти команды выбирают значение из списка на основе того, из какого базового блока к какому блоку мы перешли.Например, в
phi i32 [0, %start], [%i.new, %loop] говорится: «это значение должно быть 0, в случае если мы пришли из начального блока, в любом другом случае %i.new, если пришли из %loop».В отличии от других команд,
phi может относиться к неустановленным значениям во всех блоках, доминирующих в текущем блоке. Это позволяет нам иметь динамическое количество версий переменных! Вот как это выглядит в контексте динамического исполнения.Блок
%a доминирует над блоком %b если каждый из предыдущих блоков является %a или блоком в котором доминирует %a. Другими словами, каждый путь из первого блока к блоку %b проходит через блок %a. В общем, команды могут относиться только к значениям определенным предыдущими командами в конкретном блоке или значениям из других блоков, доминирующих над оным.1.
%start переходит прямо в %loop_start. Первый блок не может быть целью перехода, пока он не имеет нод phi, потому что предыдущие блоки включают в себя место вызова функции.2. С того момента, как мы вывели
%loop_start из %start, %i.0 и %r.0 были выбраны в качестве первых версий (теоретических) переменных I и r, то есть их изначальных значений, мы переходим к %loop.3. После того, как
%loop_start доминирует над %loop, мы можем прямо использовать %i.0 и %r.0 (это является операциями *= и +=). И затем мы снова возвращаемся к %loop_start.4. Вернувшись в
%loop_start, phi-сы теперь выбирают %i.new и %r.new, так что %i.0 и %r.0 теперь являются вторыми версиями I и r. В ходе индукции, N-ное количество исполнения %loop_start будет иметь N-ное количество версий Iи r.5. Когда мы, в конце концов доберемся до
%exit, мы можем использовать %r.0 (поскольку над ним доминирует %loop_start), что будет являться %y-нными версиями r. Это наше значение возврата.Здесь стоит остановиться и подумать о том, что мы сделали. ЕСП, доминация и
phi-сы могут не уложиться к вас в голове и они являются необходимыми для чтения большинства ПП. Но это является очень ценным знанием, потому что затрагивает то, как компиляторы видят код[5].Вместе с
phi и br, мы сможем построить поток управления любой сложности внутри функции[6].Типы и агрегаты
Теперь, когда мы рассмотрели основные скалярные функции, давайте коснемся системы типов LLVM.
Мы рассмотрели
i32 и соответствующих ему. Они имеют произвольные биты с целыми числами. I1 особенный, потому что является логическим типом. Оптимизации LLVM известны своими генерациями целочисленных типов с размерами отличными от степени двойки.LLVM также имеет
float и double, вместе с несколькими особенными float-типами, как bfloat. Они используют собственные арифметические команды с различными опциями. Я расскажу о них далее; для большей информации рассмотрите fadd и подобные по ссылке: LangRef.Мы также ознакомились с
void, которая используется в качестве возвратного значения, а также ptr используемый как безтиповый[7] указатель.Вместе с тем рассмотрели псевдо-тип
label, представляющий метку блока. Он не отображается в момент использования и имеет ограниченный спектр действия (аналогичные с ним: token и metadata).Массивы пишутся так:
[n x T]. Число должно быть целым и его тип должен иметь определенный размер (пример: [1024 x i8]). Массивы нулевого размера также поддерживаются.Структуры выглядят так:
{T1, T2, ...} (пример: {i64, ptr} это из Rust). Поля структур не имеют названий, вместо этого они индексируются. Форма <{...}> это упакованная структура, которая удаляет заполнение между полями (пример: #[repr(packed)] компилируется до такой формы).Векторы похожи на массивы, но пишутся так:
<n x T>. Эксплуатируются для представления типов используемых в SIMD (ОКМД) операциях. Например: добавление двух <4 x i32> понижает векторное добавление AVX2 на архитектуре x86. Я не буду затрагивать SIMD в этой статье, хотя на более высоких уровнях оптимизации, LLVM объединит скалярные операции с векторными, так что вы можете с ним встретиться.Псевдонимы типов могут быть созданы в области действия файла с помощью синтаксиса:
Это означает, что
%T может быть как типом, так и регистром/меткой внутри функции, в зависимости от синтаксической позиции.Операции с агрегатами
insertvalue и extractvalue могут использоваться как со структурным, так и с типом массивов для статического доступа к полю. Например:
insertvalue наоборот производит копию агрегата с особым измененным полем. Оно НЕ модифицируется, потому что ЕСП не позволяет это сделать.
Вот похожие операции:
insertelement и extractelement работающие с векторами, но имеющие немного другой синтксис и семантику.И наконец, -
getelementptr, «арифметическая команда с указателем». Часто сокращается до GEP и может использоваться для вычисления смещенного указателя в структуре. Например:
Она принимает указатель, который якобы указывает на индекс и массив из
%MyStructs-ов. Также производит возврат указателя в поле i64 %idx-го элемента %p.Несколько важных различий между GEP и
extractvalue:1. Принимает безтиповый указатель вместо значения конкретного типа структуры/массива.
2. Существует дополнительный параметр определения индекса: с точки зрения GEP, каждый указатель - это указатель к массиву с неопределенной привязкой. Проводя операции с указателем, который не указывает (в момент работы) на массив, все равно будет запрашиваться индексный операнд равный нулю. В качестве альтернативы, можете рассмотреть указатель к
T, как указатель к одноэлементному массиву.3. Параметры индекса требуют точности типов.
LLVM предлагает полезное[8] FAQ об использовании GEP: https://llvm.org/docs/GetElementPtr.html.
Другие операции
Остальные операции очень актуальны для чтения ПП, но они не попадают ни под одну определенную категорию. Как всегда, LangRef предлагает полное описание их функционала.
Вызовы функций
Команда
call вызывает любую ptr в качестве функции. Например:
Заметьте, что вместо
@global могло быть %reg, что означает вызов указателя функции.Иногда, вы будете видеть
invoke, используемую для «реализации функции внутри блока C++ try {}». В Rust это встречается редко, но может появиться в некоторых кодах языка C++.Вызовы функций часто являются замусоренными областями ПП, потому что они слишком аннотированы.
Синхронизация
Ранее рассмотренные команды
load и store могут быть аннотированы как atomic, используемая для реализации, например: AtomicU32::load в Rust. Это также требует определения атомарного порядка. Пример:
Операция
fence это главная барьерная операция с памятью, относящаяся, например, к функции Rust: std::sync::atomic::fence.сmpxchg производит элементарную операцию сравнения с обменом (ССО). Она возвращает {T, i1} вместе с предыдущим значением и информацию о том, успешно-ли прошла ССО. cmpxchg weak реализует примитив “weak CAS” вызывающий ложный сбой.В конце концов,
atomicrmw атомарно проводит цикл чтения-модицикации и записи (пример: *p = op(*p, val)). Используется для реализации функции AtomicU32::fetch_add и подобных.Все эти операции кроме fence, могут быть отмечены как
volatile. В LLVM IR, как и в Rust, но не в C/C++, одиночные загрузки и хранилища являются изменчивыми (оказывают на компьютер невидимые для него побочные действия). volatile можно совместить с атомарными операциями (пример: load atomic volatile), хотя большинство языков не предоставляют такую возможность (кроме старых версий C++).Перетолкование сложных махинаций
bitcast это то, во что в конечном счете компилируются mem::transmute и reinterpret_cast в Rust и C++ соответственно. Она может конвертировать любой неагрегатный тип (целые числа, векторы) в любой тип с сохранением той-же ширины бита. Например, ее можно использовать для получения битов значения с плавающей точкой:
Она также использовалась для приведения типов указателей (например: из
i32* в i8*). Сейчас все указатели безтиповые (ptr), поэтому в ней нет необходимости.Однако,
bitcast не может выполнять преобразование между указателями и целочисленными данными. Для этого нам следует использовать команды inttoptr и ptrtoint[9]. Они имеют одинаковый синтаксис, но взаимодействуют со схематической семантикой преобразования указателя в целое число и происхождения указателя. Эта часть семантики LLVM походит на длительное горение мусора. Посмотрите пост Ральфа Юнга о знакомстве с этой проблемой.Встроенные функции
В LLVM существует также большое количество внутренних функций, которые описаны в LangRef. Например, если мы хотим провести встроенное
memcpy (копирование памяти), то мы можем обозначить это с помощью команды declare:
Все внутренние функции LLVM начинаются с
llvm.: и для рассмотрения всех у нас не хватит никакой статьи.Я также не берусь за обсуждение плавающей точки, SIMD (ОКМД) и обработку исключений. Каждая из этих тем требует написания отдельной статьи!
Неопределенное поведение
LLVM существует для геренации оптимизированного кода, и оптимизации требуют чтобы мы описывали некоторые состояния машины как «невозможные», таким образом мы сможем определить когда нам необходимо упростить код. Это является «неопределенным поведением».
Например, мы уже сталкивались с
unreachable, что как предполагает LLVM не может быть выполнено. Деление на ноль и попытка доступа к памяти за пределеами допустимых значений тоже являются неопределенным поведением.Большинство факторов LLVM UB основаны на концепции «отравленных значений». «Отравленное значение» воспринимается как «принятие каждого значения только один раз» в зависимости от того, что для данной оптимизации более удобно в данный момент без учета других проходов. Это означает, что если при оптимизации не обнаруживается сбоев, то с точки зрения LLVM выдать вам «мусорные значения» будет считаться нормальным. Чаще всего это заметно при
-O0, которая проводит минимальную оптимизацию.Использование «отравленных значений» как указателя в
load, store или call считаются неопределенным поведением, потому что LLVM может определить их как нулевой указатель. Они также не могут быть знаменателями к udiv и подобным. Добавление т.н. «яда» в br или switch тоже считается неопределенным поведением.LLVM может выполнить анализ потока данных для определения операций с «отравленным значением» от которых происходит неопределенное поведение, и таким образом предположить что эти операции не могут являться его источником. Это происходит потому что все операции (кроме
phi и select) приводят к сбою, а противоположное суждение LLVM только позволяет распространять его дальше. Вот откуда появляется так называемое «путешествующее во времени неопределенное поведение».Множество операций приводят к сбою. В языке C, например, знаковое переполнение является неопределенным поведением, поэтому добавление заменяется на
add nsw (nsw означает «оболочка без подписи»). И вместо того, чтобы завершить работу при переполнении, команда дает сбой. Вот также неподписанная версия аннотаций: nuw.Другие операции имеют «менее определенные» версии, которые либо генерируются оптимизаторами, либо вставляются непосредственно компилятором, что в свою очередь вызывает LLVM в том случае, если правила языка позволяют (см. C выше). Прилагаю пару примеров:
1.
udiv и другие имеют точную аннотацию, которая требует чтобы деление имело нулевой остаток, либо дают сбой.2.
getelementptr имеет аннотацию inbounds, которая вызывает сбой в случае доступа за допустимыми пределами. Это меняет ее от чисто арифметической операции до еще одной точно соотносимой с арифметическими ограничениями указателя языка С. GEP без inbounds соответствует функции <*mut T>::wrapping_offset() в Rust.3. Операции с плавающей точкой маркированные
nnan и ninf вызовут сбой вместо NaN или бесконечного значения соответственно (либо же когда NaN или бесконечное значение являются аргументами).Однако, создание сбоев это не неопределенное поведение, это только его использование. Это проще чем работа неопределенного поведения в большинстве языков. В языке С переполнение постоянно вызывает неопределенное поведение, но переполнение в LLVM которое никогда «не происходит» просто игнорируется. Это простейшая операционная семантика для определения правильности оптимизаций: неопределенное поведение чаще стоит рассматривать как побочный эффект, потому что компилятор сгенерирует код который введет программу в неработающее состояние. Например, деление на ноль станет причиной ошибок в множестве архитектур. Это оозначает, что операции ставшие причиной неопределенного поведения не всегда могут быть правильно упорядочены. Переставляя «причины неопределенного поведения» с «причинами сбоев» гарантирует то, что боьшинство операций являются чистыми и могут быть легко переупорядочены.
Чтение некоторых методов Codegen
Вернемся к первому примеру с Rust!
Виджет Godbolt
Это полученный результат с отредактированными метаданными и некоторыми изменениями для удобного чтения.
Основная функция это
@_ZN7example6square17hb32bcde4463f37c3E, что является скоректированным названием example::square. Поскольку он был сгенерирован в режиме отладки, возникает паника при переполнении, поэтому для этого нужно сгенерировать еще код. Первая операция это call базовых функций LLVM для «умножения и сообщения о переполнении». Она возвращает равное значение (i32, bool), мы извлекаем оба значения с помощью extractvalue. Затем мы пропускаем тип bool через @llvm.expect, испольуемый для сообщения оптимизатору отработать ветку паники как «холодную». Основная ветка дает возврат произведения; если нет, мы идем к функции core::panicking::panic(), чтобы она провела панику в текущем потоке. Данная функция не дает возвратов, поэтому мы можем завершить блок с помощью unreachable.Остальная часть файла состоит из:
1.
declare-ы которые мы использовали для базовых функций LLVM.2.
declare для core::panicking::panic. Любая внешняя функция должна быть заdeclare-на. Также это дает возможность отключить атрибуты для функции.3. Глобальные константы для
core::panic::Location и сообщений о панике.4. Атрибуты для выше описанных функций.
Сейчас как раз время отметить атрибуты. LLVM имеет в наличии все виды атрибутов которые могут быть помещены в функции (и вызовы функций) для записи необходимой информации об оптимизации. Например,
@llvm.expect.i1 аннотирован как willreturn: это означает, что в конечном итоге эта функция проведет возврат, а также то, что если, например, любое неопределенное поведение появляющееся после функции, то оно гарантированно появится после окончания, поэтому LLVM может сделать заключение, что код является недостижимым несмотря на вызов @llvm.expect.i1. Полный список атрибутов огромен, но LangRef описывает их все!Заключение
LLVM огромен и намного больше любой личной АРК(Архитектуры Системы Команд), потому что он захватывает любую интересную ему операцию. Он также имеет богатый язык аннотиций, поэтому проходы могут записывать информацию для использования ее будущими проходами. Его операционная семантика старается оставить достаточно пространства для осуществления оптимизации, в то же время убедившись что множество успешных оптимизаций в последствии не окажутся неудачными (последняя часть еще в стадии разработки).
Умея читать ассемблер, можно посмотреть что случится прямо во время выполнения кода, а чтение ПП перед и после оптимизации показывает как компилятор рассматривает ваш код. Использование
opt для запуска индивидуальных проходов оптимизации также поможет для дальнейшего понимания (по сути, «разделение на проходах» мощнейшая техника отладки в разработке компилятора).Я познакомился с компиляторами благодаря чтению LLVM IR. Надеюсь эта статья также вдохновит вас на изучение!
[1] Регистры внутри функций могут иметь числовое название. Они должны быть разделены по порядку: сначала
%0 (будь то регистр или метка), затем %1, %2 и т.д. Часто, они используются для отображения «временных результатов». Если значение не устанавливает названия для своих параметров, им автоматически будут даны названия %0, %1 и т.д., что влияет на порядок использования вами точных чисел. Таким-же образом, если значение начинается не с метки, ему будет присвоено порядковое число в качестве имени. Это может стать причиной сплошной путаницы, ведь если у нас есть define void @foo(i32, i32) { ... }, то аргументы будут %0 и %1, но если мы попробуем написать %2 = add i32 %0, %1, то мы получим чудовищно запутанную ошибку парсера, потому что %2 уже используется как название для первого блока.[2] По какой-то причине, оптимизатор не может понять, что
select является избыточной. Alive2 (SMT-решатель для проверки правильности оптимизации) похоже, соглашается с правильностью оптимизации. Так что я решил поделиться этим багом. 
[3] Если вы читали мою статью об ассемблере, вы вспомните, что там присутствет множество команд по ветвлению. В RISC-V мы имеем такие команды, как:
beq, bne, bgt, и bge. Позже, в процессе компиляции после запуска оптимизатора, LLVM произведет выборку команд (isel) для определения лучших машинных команд и осуществления определенной команды LLVM (или последовательности команд), которые являются чрезвычайно контекстно-зависимыми. Например, мы хотим объединить icmp eq, за которым идет br, а результатом является beq. Команда Isel за пределами моего понимания и ее правильное выполнение является активным вопросом в сфере научных исследований.[4] Не одно и то же. Фронтенды языков, типа Clang и Rust проводят собственные оптимизации. К примеру, у меня есть нерешенный баг, в котором LLVM не может концертировать
&& в & в некоторых случаях. Этого никогда не замечали, потому что Clang оптимизирует с помощью перехода от C/C++ к LLVM, а Rust нет.[5] MLIR (Multi-Layer Intermediate Representative) – это более интуитивно понятная модель используемая в современных ПП. В ней вы не можете использовать переменные, которые были определены другими блоками. Вместо этого, каждый блок принимает ряд аргументов, прямо как вызов функции. Он аналогичен командам
phi, за исключением того, что сейчас вместо выбора значения которое мы хотим использовать в качестве цели, каждый предшествующий блок определяет что он хочет отправить цели.Если вместо этого, мы будем считать, что каждый блок имеет «аргументы», мы сможем переписать его в ниже показанном импровизированном синтаксисе, где имена регистров ограничены областью действия их блока.
[6] Как выглядит ГПУ? LLVM содержит в себе «оптимизационные» проходы, и выводит ГПУ в качестве файла с расширением
.dot, который может быть произведен командой dot. Для @safe_div мы получаем что-то вроде этого:
Это помогает понимать сложные функции. Рассмотрите эту функцию шестнадцатеричного анализа в Rust:
Затем мы можем генерировать наш ГПУ с помощью внешних команд:
Получаем вот такой беспорядок:
Без оптимизации он будет еще больше (большинство этапов оптимизации, - это различные очистки ГПУ).
Задание: попробуйте отследить, через что работает каждый отдельный базовый блок. Для этого вам нужно открыть .svg-файлы (
–О0? все alloca-и, в –O2? ни одной![7] Когда-то давно мы имели дело с типовыми указателями, вроде
i32*. Он создавал больше проблем чем решений, запрашивая множество запросов в ПП в обмен на посредственную сохранность типа. Пройдите по ссылке чтобы ознакомиться более детально.[8] Сарказм.
[9] Я молча осуждаю LLVM за подобные названия, ведь
int2ptr читается намного приятнее.