Хабрахабр

[Перевод] Профилирование кода с LLVM

Проклятие недетерминизма


Моя первая попытка написать проход LLVM — люблю эти сегфолты

Под словом «детерминированный» я подразумеваю, что один и тот же код будет выполняться за одно и то же количество единиц времени. Недавно я столкнулся с интересной задачей — мне понадобился детерминированный и кросплатформенный способ определения времени выполнения кода С++. Под кроссплатформенностью я понимаю, что один и тот же код под Windows и под Ubuntu будет выполняться за одно и то же количество единиц времени.

Машинный код меняется в зависимости от архитектуры и операционной системы, и один и тот же код займёт различное количество времени при выполнении. Естественно, измерение времени на CPU не удовлетворяет этим условиям. Мне нужно было что-либо более умное…
Даже на одной и той же машине, такие факторы, как промахи кэша, будут играть большую роль — достаточную для того, чтобы исказить результаты измерения времени выполнения одного и того же кода.

Мотивация

Я столкнулся с этой проблемой, когда работал над моим проектом, Code Character. Code Character — это онлайновое соревнование AI, в котором участники пишут ботов для управления армией в пошаговой стратегии. Я хотел ограничить количество кода, которое участник может выполнить за один ход.

Фактически, мы пытались реализовать это решение, и результаты меняются настолько сильно, что участник может выиграть или проиграть с одним и тем же кодом. Моей первой мыслью было просто измерять время выполнения кода, но, как мы видим, эта стратегия не является детерминированной, и участник, пославший один и тот же код два раза, получит совершенно разные результаты. Результат будет совершенно случайным, и мы отбросили идею об измерении времени.

Байткод LLVM

Так как мы не можем измерять время мы решили вместо этого измерять количество выполненных инструкций. Следовательно, нам необходим инструментировать код участников. Если вам не знаком этот термин, это добавление некоторого кода к приложению, с целью мониторинга какого-либо параметра, например, использования CPU или времени исполнения. Естественно, мы не ожидаем, что участники будут делать это сами, мы должны автоматизировать процесс.

Вместо этого, мы решили напрямую инструментировать код участников для того, чтобы подсчитать количество инструкций, которое будет выполнено. Мы хотели избежать накладных расходов на рантаймовые инструменты при работе на нашем сервере, и поэтому что-либо типа инструмента PIN не подходит для наших целей. Вместо того, чтобы инструментировать бинарники (машинный код), мы решили использовать Clang для компиляции кода и инструментировать байткод LLVM.

Одним из главных проектов является LLVM IR и бэкенд. Если вы не знакомы с LLVM, он представляет собой коллекцию модульных и повторно используемых технологий компилятора и тулчейна. Затем этот код, LLVM IR, компилируется в машинный код бэкендом LLVM. В простых терминах, разработано промежуточное представление (Intermediate Representation), в которое компилирующий фронтенд компилирует код. Таким образом, если вы делаете новый язык, вы можете решить позволить LLVM поддерживать генерацию машинного кода и его оптимизацию, и написать фронтенд для преобразования вашего языка в LLVM IR.


Clang конвертирует код C++ в LLVM IR, который затем преобразуется в машинный код бэкендом LLVM.

Так как нам нужен кроссплатформенный метод измерения кода, мы не можем инструментировать бинарный код. Clang является фронтендом LLVM. Инструментирование IR кода с помощью библиотек LLVM является простым кросс-платформенным решением. LLVM IR, однако, является платформенно-независимым, так как это только промежуточное представление кода.

Решение

Простой подсчёт инструкций 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) }
}

Ссылка на 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
Это помогло нам понять, как работают базовые блоки, теперь рассмотрим этот алгоритм в 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

Если вы посмотрите внимательно, вы заметите, что фрагмент кода, приведённый выше, представляет собой первые три блока фрагмента кода С++, скомпилированный в LLVM IR (каждая строка — это начало базового блока).

LLVM API позволяет нам легко читать и анализировать LLVM IR путём итераций по модулям, функциям и базовым блокам, и модифицировать LLVM IR перед тем, как он будет скомпилирован в машинный код. В LLVM есть библиотеки, которые позволяют нам писать «проходы» — код, который может преобразовывать 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

Используя статический int, с которым работает IncrementCount, мы можем получить число инструкций в конце каждого хода участника. Как мы видим, вызов IncrementCount сделан в конце каждого базового блока прямо перед последней инструкцией. один и тот же исходный код гарантированно порождает один и тот же LLVM IR, если мы используем ту же версию компилятора и те же флаги. Этот способ детерминированный и кросс-платформенный, т.к.

Заключение

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

Исходный код прохода вы можете взять здесь.

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

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

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

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

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