Проклятие недетерминизма
Моя первая попытка написать проход LLVM — люблю эти сегфолты
Недавно я столкнулся с интересной задачей — мне понадобился детерминированный и кросплатформенный способ определения времени выполнения кода С++. Под словом «детерминированный» я подразумеваю, что один и тот же код будет выполняться за одно и то же количество единиц времени. Под кроссплатформенностью я понимаю, что один и тот же код под Windows и под Ubuntu будет выполняться за одно и то же количество единиц времени.
Естественно, измерение времени на CPU не удовлетворяет этим условиям. Машинный код меняется в зависимости от архитектуры и операционной системы, и один и тот же код займёт различное количество времени при выполнении. Даже на одной и той же машине, такие факторы, как промахи кэша, будут играть большую роль — достаточную для того, чтобы исказить результаты измерения времени выполнения одного и того же кода. Мне нужно было что-либо более умное…
Мотивация
Я столкнулся с этой проблемой, когда работал над моим проектом, Code Character. Code Character — это онлайновое соревнование AI, в котором участники пишут ботов для управления армией в пошаговой стратегии. Я хотел ограничить количество кода, которое участник может выполнить за один ход.
Моей первой мыслью было просто измерять время выполнения кода, но, как мы видим, эта стратегия не является детерминированной, и участник, пославший один и тот же код два раза, получит совершенно разные результаты. Фактически, мы пытались реализовать это решение, и результаты меняются настолько сильно, что участник может выиграть или проиграть с одним и тем же кодом. Результат будет совершенно случайным, и мы отбросили идею об измерении времени.
Байткод LLVM
Так как мы не можем измерять время мы решили вместо этого измерять количество выполненных инструкций. Следовательно, нам необходим инструментировать код участников. Если вам не знаком этот термин, это добавление некоторого кода к приложению, с целью мониторинга какого-либо параметра, например, использования CPU или времени исполнения. Естественно, мы не ожидаем, что участники будут делать это сами, мы должны автоматизировать процесс.
Мы хотели избежать накладных расходов на рантаймовые инструменты при работе на нашем сервере, и поэтому что-либо типа инструмента PIN не подходит для наших целей. Вместо этого, мы решили напрямую инструментировать код участников для того, чтобы подсчитать количество инструкций, которое будет выполнено. Вместо того, чтобы инструментировать бинарники (машинный код), мы решили использовать Clang для компиляции кода и инструментировать байткод LLVM.
Если вы не знакомы с LLVM, он представляет собой коллекцию модульных и повторно используемых технологий компилятора и тулчейна. Одним из главных проектов является LLVM IR и бэкенд. В простых терминах, разработано промежуточное представление (Intermediate Representation), в которое компилирующий фронтенд компилирует код. Затем этот код, LLVM IR, компилируется в машинный код бэкендом LLVM. Таким образом, если вы делаете новый язык, вы можете решить позволить LLVM поддерживать генерацию машинного кода и его оптимизацию, и написать фронтенд для преобразования вашего языка в LLVM IR.
Clang конвертирует код C++ в LLVM IR, который затем преобразуется в машинный код бэкендом LLVM.
Clang является фронтендом LLVM. Так как нам нужен кроссплатформенный метод измерения кода, мы не можем инструментировать бинарный код. LLVM IR, однако, является платформенно-независимым, так как это только промежуточное представление кода. Инструментирование IR кода с помощью библиотек LLVM является простым кросс-платформенным решением.
Решение
Простой подсчёт инструкций LLVM IR очевидно, не подходит, так как нам нужно количество инструкций, которые будут реально выполняться, а не просто количество инструкций в коде. В конце концов, мы разработали простой алгоритм, основанный на концепции базовых блоков кода.
Базовым блоком называется набор инструкций, в котором входной точкой может быть только первая инструкция, а выходной точкой — только последняя инструкция. (также запрещены любые переходы внутри базового блока — прим. перев.) Чтобы понять это, попробуйте разделить код на куски, в которых инструкции ветвления (переходов, циклов и возвратов) могут быть только последними в наборе, а вход в блок (первая инструкция в функции, цикле или блоке if/else) возможен только на первую инструкцию. В результате получается набор базовых блоков — блоков последовательного кода, который просто выполняется последовательно, без принятия решений о том, какая инструкция выполняется следующей.
Почему бы нам не попробовать прямо сейчас? Это фрагмент кода, предоставленного участником Code Character:
// Make the soldiers who aren't patrolling attack the enemy
for (int i = NUM_SOLDIERS / 2; i < NUM_SOLDIERS; ++i) {
auto &soldier = state.soldiers[i];
if (soldier.hp == 0) // If this soldier is dead, skip it
continue;
for (auto enemy_soldier : state.enemy_soldiers) {
if (enemy_soldier.hp != 0) { // Ensure your prospective target has
// not already been slain
soldier.soldier_target = enemy_soldier.id;
break;
}
}
}Ссылка на Github: https://gist.github.com/JHurricane96/8c9c3a45ec5e969de4d9fecb47ebef69#file-player_code-cpp
Используя факт, что базовый блок имеет только одну входную точку (первую инструкцию), мы можем разделить этот фрагмент на следующие базовые блоки:
//-------------------------------- BB 1 ----------------------------------
for (int i = NUM_SOLDIERS / 2; i < NUM_SOLDIERS; ++i) {
//-------------------------------- BB 2 ----------------------------------
auto &soldier = state.soldiers[i];
if (soldier.hp == 0)
//-------------------------------- BB 3 ----------------------------------
continue;
//-------------------------------- BB 4 ----------------------------------
for (auto enemy_soldier : state.enemy_soldiers) {
//-------------------------------- BB 5 ----------------------------------
if (enemy_soldier.hp != 0) {
//-------------------------------- BB 6 ----------------------------------
soldier.soldier_target = enemy_soldier.id;
break;
//-------------------------------- BB 7 ----------------------------------
}
}
}
Ссылка на Github: https://gist.github.com/JHurricane96/92452a27acb49ebe84a55a3bee46fe3e#file-player_code-cpp
Это помогло нам понять, как работают базовые блоки, теперь рассмотрим этот алгоритм в LLVM IR:
; <label>:140: ; preds = %181, %139
%141 = load i32, i32* %19, align 4
%142 = sext i32 %141 to i64
%143 = icmp slt i64 %142, 20
br i1 %143, label %144, label %184
; <label>:144: ; preds = %140
%145 = getelementptr inbounds %"struct.player_state::State",
%"struct.player_state::State"* %2, i32 0, i32 1
%146 = load i32, i32* %19, align 4
%147 = sext i32 %146 to i64
%148 = call dereferenceable(72) %"struct.player_state::Soldier"*
@_ZNSt5arrayIN12player_state7SoldierELm20EEixEm(
%"struct.std::array.10"* %145, i64 %147) #3
store %"struct.player_state::Soldier"* %148,
%"struct.player_state::Soldier"** %20, align 8
%149 = load %"struct.player_state::Soldier"*,
%"struct.player_state::Soldier"** %20, align 8
%150 = getelementptr inbounds %"struct.player_state::Soldier",
%"struct.player_state::Soldier"* %149, i32 0, i32 2
%151 = load i64, i64* %150, align 8
%152 = icmp eq i64 %151, 0
br i1 %152, label %153, label %154
; <label>:153: ; preds = %144
br label %181Ссылка на Github: https://gist.github.com/JHurricane96/743e0611319d63516014ad3c7a2dcf42#file-player_code-s
Если вы посмотрите внимательно, вы заметите, что фрагмент кода, приведённый выше, представляет собой первые три блока фрагмента кода С++, скомпилированный в LLVM IR (каждая строка — это начало базового блока).
В LLVM есть библиотеки, которые позволяют нам писать «проходы» — код, который может преобразовывать LLVM IR. LLVM API позволяет нам легко читать и анализировать LLVM IR путём итераций по модулям, функциям и базовым блокам, и модифицировать LLVM IR перед тем, как он будет скомпилирован в машинный код.
Сейчас у нас есть базовые блоки и LLVM API, становится простым делом подсчитать количество выполняемых инструкций при помощи такого простого алгоритма:
1. Напишем функцию IncrementCount, которая принимает целое и инкрементирует статическое целое этим значением, при каждом вызове. Её нужно слинковать с кодом участника.
2. Делаем итерации по всем базовым блокам. Для каждого базового блока выполняем шаги 3 и 4
3. Находим n — число инструкций в этом базовом блоке.
4. Вставляем вызов функции IncrementCount перед последней инструкцией базового блока, с аргументом n.
5. Статическое целое, с которым работает IncrementCount, и будет счётчиком инструкций после того, как код будет выполнен. Он может быть сохранён где-то и затем проверен.
Наш инструментированный IR работает так:
; <label>:140: ; preds = %181, %139
%141 = load i32, i32* %19, align 4
%142 = sext i32 %141 to i64
%143 = icmp slt i64 %142, 20
call void @_Z14IncrementCountm(i32 4)
br i1 %143, label %144, label %184
; <label>:144: ; preds = %140
%145 = getelementptr inbounds %"struct.player_state::State",
%"struct.player_state::State"* %2, i32 0, i32 1
%146 = load i32, i32* %19, align 4
%147 = sext i32 %146 to i64
%148 = call dereferenceable(72) %"struct.player_state::Soldier"*
@_ZNSt5arrayIN12player_state7SoldierELm20EEixEm(
%"struct.std::array.10"* %145, i64 %147) #3
store %"struct.player_state::Soldier"* %148,
%"struct.player_state::Soldier"** %20, align 8
%149 = load %"struct.player_state::Soldier"*,
%"struct.player_state::Soldier"** %20, align 8
%150 = getelementptr inbounds %"struct.player_state::Soldier",
%"struct.player_state::Soldier"* %149, i32 0, i32 2
%151 = load i64, i64* %150, align 8
%152 = icmp eq i64 %151, 0
call void @_Z14IncrementCountm(i32 10)
br i1 %152, label %153, label %154
; <label>:153: ; preds = %144
call void @_Z14IncrementCountm(i32 1)
br label %181Ссылка на Github: https://gist.github.com/JHurricane96/368c7ed79a113be860a73aeaadad371d#file-player_code-s
Как мы видим, вызов IncrementCount сделан в конце каждого базового блока прямо перед последней инструкцией. Используя статический int, с которым работает IncrementCount, мы можем получить число инструкций в конце каждого хода участника. Этот способ детерминированный и кросс-платформенный, т.к. один и тот же исходный код гарантированно порождает один и тот же LLVM IR, если мы используем ту же версию компилятора и те же флаги.
Заключение
Профилирование кода не такая простая вещь, как я когда-то думал. В процессе работы над такой относительно простой задачей, я ознакомился с тем, как работает компилятор, и как писать проходы LLVM. Если вам интересна генерация кода и вы хотите писать собственные проходы, LLVM имеет руководство для начинающих. также есть отличная статья в блоге, которую я использовал при написании моего собственного прохода. Так как LLVM API не имеет обратной совместимости между мажорными версиями, обращайте внимание на то, какую версию LLVM вы используете.
Исходный код прохода вы можете взять здесь.
Автор: 32bit_me
