denisfrolov Sep 1 2015 at 10:43

LLVM для исследователей

14 min

50K

Content AI corporate blogProgramming*Compilers*

Tutorial

Translation

Original author: Adrian Sampson

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

Что такое LLVM?

LLVM — это по-настоящему удобный для разборки и сборки «ранний» компилятор для таких традиционных языков программирования, как C и C++.

LLVM настолько хорош, что считается «больше, чем просто компилятором» (это динамический компилятор, он работает с языками, не относящимися к семейству C, он представляет собой новый формат доставки для App Store и т. д. и т. п.). Все перечисленное верно, но для нашей статьи важно лишь приведенное выше определение.

LLVM имеет несколько ключевых отличий от других компиляторов:

Главное новшество — промежуточное представление (ПП). LLVM работает с ПП, которое действительно можно прочитать (если вы умеете читать ассемблерный код). Возможно, кому-то это не покажется столь уж большим откровением, однако это свойство очень важно. ПП других компиляторов обычно имеют настолько сложную структуру, что их невозможно записать вручную, трудно понять и использовать.
LLVM довольно изящно написан: его архитектура носит более модульный характер, чем у других компиляторов. Одна из причин подобного изящества — то, что разработчиком первоначальной версии был один из нас.
LLVM является не только предпочтительным инструментом исследований для академических хакеров типа нас, но и компилятором промышленного уровня, за которым стоит крупнейшая компания планеты. Это означает, что вам не придется искать компромисс между отличным компилятором и настраиваемым компилятором (как это происходит в землях Java при выборе между HotSpot и Jikes).

Зачем исследователю LLVM?

LLVM — отличный инструмент. Но какое вам дело, если ваше исследование не о компиляторах?

Инфраструктура компилятора позволяет делать с программами много любопытного. Например, можно анализировать программу, чтобы понять, как часто она выполняет определенные действия. Можно преобразовывать программу, чтобы она лучше работала на конкретной системе. Ещё можно менять программу, чтобы представить, как она будет использовать гипотетическую новую архитектуру или ОС, для которой еще не изготовлен новый чип или не написан модуль ядра. Инфраструктура компилятора может пригодиться исследователям гораздо чаще, чем думают многие. Я советую обращаться к LLVM в первую очередь, до того как вы попробуете запилить один из этих инструментов (если только у вас нет на это особых причин):

архитектурный симулятор;
средство динамического бинарного инструментирования, например, Pin;
преобразование на уровне исходного кода (от простых средств, например sed, до продвинутых наборов инструментов, включающих разбор и сериализацию АСД);
подпиливание ядра для перехвата системных вызовов;
любой инструмент, похожий на гипервизор.

Даже если компилятор не выглядит как идеальное решение для вашей задачи, он зачастую облегчает 90% работы, например при переводе одного исходного кода в другой.

Ниже приведены удачные примеры исследовательских проектов, которые не так уж и похожи на компилятор:

Virtual Ghost Иллинойского университета в Урбане-Шампейне (США) демонстрирует, как можно использовать проход компилятора для защиты процессов от взломанного ядра ОС.
CoreDet Вашингтонского университета (США) делает многопоточные программы детерминированными.
В приближенных вычислениях мы используем проход LLVM для добавления ошибок в программы, чтобы смоделировать работу аппаратных средств, подверженных сбоям.

Еще раз подчеркну: LLVM предназначен не только для разработки новых оптимизаций в компиляторе.

Подробности

На рисунке ниже показаны основные компоненты архитектуры LLVM (и общей архитектуры любого современного компилятора):

Frontend разбирает исходный код и превращает его в промежуточное представление (ПП). Благодаря этому упрощается работа остальной части компилятора, которому тяжело «переварить» крайне сложный исходный код C++. Такому бесстрашному исследователю, как вы, вероятно, не придется ничего допиливать в этой части, поэтому вы можете использовать Clang без изменений.
Проходы выполняют преобразование одного ПП в другое. В обычных обстоятельствах проходы оптимизируют код, то есть на выходе они дают программу в ПП, которая делает то же, что и ПП, поданное на вход, но только быстрее. Именно здесь вы и захотите что-нибудь допилить. Ваша доработка сможет, например, читать и изменять ПП, проходящее через компилятор.
Backend непосредственно генерирует машинный код. Скорее всего, вам не придется что-либо менять в этой части системы.
Архитектура LLVM соответствует архитектуре большинства современных компиляторов, однако обратите внимание на одно новшество: в отличие от других компиляторов, где на каждом проходе создается уникальная форма программного кода, в LLVM на протяжении всего процесса используется одно и то же ПП. Это идеально подходит для нас, хакеров: нам не нужно беспокоиться о том, на каком этапе процесса выполняется код, если это происходит между frontend и backend .

Подготовка к работе

Итак, давайте что-нибудь поковыряем.

Установка LLVM

Сначала нужно установить LLVM. В дистрибутивы Linux часто входят пакеты LLVM и Clang, полностью готовые к использованию. Убедитесь, что полученная версия включает в себя все необходимые заголовки для допиливания программ с помощью компилятора. Например, сборка OS X, поставляемая с Xcode, является недостаточно полной. К счастью, нетрудно собрать LLVM из исходного кода с помощью CMake. Обычно нужно выполнить только сборку самого LLVM. Clang, поставляемый вместе с ОС, прекрасно справляется с этой задачей, если совпадают соответствующие версии (впрочем, имеются инструкции по сборке Clang).

В частности, Брэндон Холт (Brandon Holt) написал для OS X хорошую инструкцию, имеется также рецепт для системы Homebrew.

Учите матчасть

Вам необходимо внимательно изучить документацию. По-моему, особенно полезными будут следующие материалы:

Очень важная информация содержится на автоматически сгенерированных страницах Doxygen. Чтобы научиться успешно ковырять программы с помощью LLVM, вам придется надолго поселиться среди этих документов по API. Однако учитывая сложность навигации по страницам, я рекомендую «гуглить» информацию. Если добавить «LLVM» к названию любой функции или имени класса, Google обычно находит нужную страницу Doxygen (если постараться, можно обучить Google находить информацию о компиляторе даже без ввода названия «LLVM»!). Я понимаю, что это звучит смешно, однако чтобы выжить, вам действительно придется поплясать с бубном вокруг документации API LLVM. Может, и существует более удобный способ навигации по документам API, но я о нем не слышал.
Справка по LLVM пригодится, если вам будет непонятно что-то в синтаксисе ПП.
В руководстве программиста описаны инструменты для работы со структурами данных, специфичными для LLVM (эффективными строками, альтернативами STL для карт, векторов и т. д.), а также средства для работы с типами (isa, cast и dyn_cast), которыми вы будете пользоваться повсеместно.
Обращайтесь к пособию о написании прохода LLVM, если возникнут вопросы о возможностях отдельного прохода. Учитывая, что вы — исследователь, а не просто так ковыряете компилятор, хотелось бы отметить, что автор данной статьи не согласен с отдельными моментами этого учебного пособия. (Прежде всего, не обращайте внимания на инструкции по сборке системы с помощью Makefile и переходите непосредственно к инструкциям по сборке вне дерева исходного кода.) Тем не менее, в целом руководство является каноническим источником информации о проходах.
В отдельных случаях удобно пользоваться зеркалом GitHub — веб-ресурсом для просмотра исходного кода LLVM.

Написание прохода

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

«Скелет»

Я создал репозиторий шаблонов, где имеется один бесполезный проход LLVM. Рекомендую начать с шаблона, ведь при создании с нуля могут возникнуть проблемы с конфигурацией сборки.
Клонируйте репозиторий llvm-pass-skeleton с GitHub:

$ git clone git@github.com:sampsyo/llvm-pass-skeleton.git

Содержательная работа выполняется в файле skeleton/Skeleton.cpp, поэтому откройте его. Именно здесь все и происходит:

virtual bool runOnFunction(Function &F) {   
   errs() << "I saw a function called " << F.getName() << "!\n";
   return false; 
}

Существует несколько типов проходов LLVM. Мы используем один из них – function pass (он идеально подходит для начинающих). Как и следовало ожидать, LLVM вызывает описанный выше метод для каждой функции, которую он находит в компилируемой нами программе. Пока метод только выводит имя функции.

Подробности:

Элемент под названием errs() — это поток вывода C++, предоставленный с помощью LLVM. Он используется для вывода в консоль.
Функция возвращает false, чтобы показать, что не меняла F. Позже, когда мы начнем менять ПП, нужно будет возвращать true.

Сборка

Выполните сборку прохода с помощью CMake:

$ cd llvm-pass-skeleton 
$ mkdir build 
$ cd build 
$ cmake ..  # Generate the Makefile. 
$ make  # Actually build the pass.

Если LLVM не установлен глобально, то для CMake необходимо указать его расположение. Для этого задайте путь к каталогу share/llvm/cmake/, где находится LLVM, в переменной среды LLVM_DIR. Ниже приведен пример пути для системы Homebrew:

$ LLVM_DIR=/usr/local/opt/llvm/share/llvm/cmake cmake ..

В результате сборки получается разделяемая библиотека. Она находится в файле build/skeleton/libSkeletonPass.so или в файле со схожим именем в зависимости от используемой платформы. На следующем шаге мы загрузим эту библиотеку, чтобы выполнить проход для реального программного кода.

Проход

Для выполнения прохода скомпилируйте какую-нибудь программу на C с флагами, указывающими, что нужно использовать только что полученную библиотеку:

$ clang -Xclang -load -Xclang build/skeleton/libSkeletonPass.* something.c 
I saw a function called main!

Этот танец с процедурой -Xclang -load -Xclang path/to/lib.so — все, что вам нужно для загрузки и активации прохода в Clang. Поэтому при работе с крупными проектами можно добавить эти аргументы в список переменных CFLAGS Makefile или соответствующий эквивалент вашей системы сборки.

(Кроме того, можно выполнять проходы сами по себе, не запуская clang: этот метод, использующий команду LLVM opt, рекомендован в официальной документации. Однако я не буду описывать его в данной статье).

Поздравляю, вы только что допилили компилятор! На следующих этапах мы увидим, как доработать наш проход уровня «Hello, world!» до более интересных вещей.

Структура промежуточного представления LLVM

Для работы с программами в LLVM неплохо бы разбираться в структуре ПП.

Модули (Modules) содержат функции (Functions), которые, в свою очередь, включают в себя базовые блоки (BasicBlock), содержащие инструкции (Instructions). Все классы, кроме Module, являются производными от Value.

Контейнер

Ниже приведен обзор наиболее важных компонентов программы LLVM:

Модуль представляет собой просто исходный файл (грубо говоря) или единицу преобразования (если подойти строго). В модуле содержатся все остальные сущности.
Прежде всего, модули содержат функции, которые полностью соответствуют своему названию и являются именованными блоками исполняемого кода (и функции, и методы в C++ соответствуют функциям LLVM).
Помимо объявления имени и аргументов функция служит контейнером базовых блоков (BasicBlock). Базовый блок — это знакомое понятие из теории компиляторов. Однако в нашей статье мы будем рассматривать его просто как непрерывный блок инструкций.
В свою очередь, инструкция является одной операцией с кодом; ее уровень абстракции примерно такой же, что и в машинном коде RISC. Например, инструкцией может быть сложение целых чисел, деление с плавающей точкой или сохранение в память.

Большинство сущностей LLVM (функции, базовые блоки и инструкции) — это классы C++, производные от вездесущего базового класса Value. Значением являются любые данные, которые можно использовать в вычислениях (например, число или адрес кода), а также глобальные переменные и константы (известные как «литералы» или «непосредственные значения», например, 5).

Инструкция

Ниже показан пример инструкции в удобочитаемой текстовой форме ПП LLVM:

%5 = add i32 %4, 2

Инструкция складывает два 32-битных числа (на это указывает i32). Она складывает число в регистре 4 (обозначен %4) и константу 2 (собственно 2) и записывает результат в регистр 5. Именно это я имею в виду, когда говорю, что ПП LLVM выглядит как идеальный машинный код RISC. Мы даже используем ту же терминологию, например регистр, однако количество регистров бесконечно.

Эта же инструкция представлена внутри компилятора как экземпляр класса C++ Instruction. Объект имеет код операции, указывающий, что это сложение, а также тип и список операндов, которые служат указателями на другие объекты Value. В нашем случае он указывает на объект Constant (константа), представляющий число 2, а другой объект Instruction (инструкция) соответствует регистру %5. (Учитывая, что ПП LLVM имеет форму статического одноразового присваивания, в действительности регистры и инструкции совпадают. Номера регистра являются артефактом текстового представления.)

Кстати, если вы захотите увидеть ПП LLVM своей программы, то можете попросить об этом Сlang:

$ clang -emit-llvm -S -o - something.c

Проверка промежуточного представления при проходе

Вернемся к проходу LLVM, над которым мы работали. Мы можем проверить все важные объекты ПП с помощью удобного общего метода dump(), который выводит на экран удобочитаемое представление объекта в ПП. Учитывая, что наш проход для каждой обрабатываемой функции получает объект Function, будем один за другим получать доступ к базовым блокам функций и инструкциям каждого блока.

Вот код, который это делает. Его можно взять из ветви containers репозитория llvm-pass-skeleton:

errs() << "Function body:\n"; 
F.dump();  

for (auto& B : F) {
   errs() << "Basic block:\n";
   B.dump();   

   for (auto& I : B) {
      errs() << "Instruction: ";
      I.dump();   
   } 
}

С модными auto и foreach из C ++11 удобно обходить иерархию ПП LLVM.
Если вы пересоберете проход и запустите его, вы увидите в выводе разные сущности LLVM в порядке их обхода.

Использование прохода для решения более сложных задач

Настоящие чудеса происходят при поиске шаблонов в программе и изменении кода после их обнаружения. Рассмотрим простой пример. Предположим, необходимо заменить первый бинарный оператор («+», «–» и т. д.) в каждой функции на умножение. Может пригодиться, не правда ли?

Вот код, который это делает. Данная версия, а также пример программы, на которой ее можно попробовать, доступны в ветке mutate git-репозитория LLVM:

for (auto& B : F) {
   for (auto& I : B) {
     if (auto* op = dyn_cast<BinaryOperator>(&I)) {
      // Insert at the point where the instruction `op` appears.
      IRBuilder<> builder(op);        

      // Make a multiply with the same operands as `op`.
      Value* lhs = op->getOperand(0);
      Value* rhs = op->getOperand(1);
      Value* mul = builder.CreateMul(lhs, rhs);

       // Everywhere the old instruction was used as an operand, use our
       // new multiply instruction instead.
       for (auto& U : op->uses()) {
          User* user = U.getUser();  // A User is anything with operands.
          user->setOperand(U.getOperandNo(), mul);       
       }
        
       // We modified the code.
       return true;     
     }   
   } 
}

Подробности:

Конструкция dyn_cast(p) специфична для LLVM и выполняет динамическое приведение типа. Она использует заботливо продуманные механизмы LLVM, позволяющие быстро выполнять динамические проверки типов, – компиляторы все время ими пользуются. Конструкция возвращает нулевой указатель, если I не является бинарным оператором BinaryOperator, поэтому идеально подходит для обработки особых случаев, как в нашем коде.
IRBuilder предназначен для построения кода. Он предоставляет миллион методов для создания любой инструкции, какую вы пожелаете.
Для встраивания нашей новой инструкции в код необходимо найти все места, где она используется, и вставить в них эту инструкцию в качестве аргумента. Напомним, что инструкция Instruction также является и значением (Value). В данном случае инструкция умножения используется в качестве операнда в другой инструкции, т. е. результат будет являться аргументом.
Кроме того, нам нужно будет удалить старую инструкцию. Однако я опустил этот шаг, чтобы не загромождать описание.

Теперь мы можем скомпилировать программу (example.c в репозитории):

#include <stdio.h>
int main(int argc, const char** argv) {
     int num;
     scanf("%i", &num);
     printf("%i\n", num + 2);
     return 0; 
}

Обычный компилятор дает код с ожидаемым поведением, а после работы нашего модуля код вместо прибавления двойки умножает на два:

$ cc example.c
$ ./a.out
10
12
$ clang -Xclang -load -Xclang build/skeleton/libSkeletonPass.so example.c
$ ./a.out
10
20

Волшебство!

Компоновка с библиотекой исполняемого кода

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

Вот код программы, который это делает, взятый из ветви rtlib репозитория llvm-pass-skeleton:

// Get the function to call from our runtime library.
LLVMContext& Ctx = F.getContext();
Constant* logFunc = F.getParent()->getOrInsertFunction(
  "logop", Type::getVoidTy(Ctx), Type::getInt32Ty(Ctx), NULL
);

for (auto& B : F) {
  for (auto& I : B) {
    if (auto* op = dyn_cast<BinaryOperator>(&I)) {
      // Insert *after* `op`.
      IRBuilder<> builder(op);
      builder.SetInsertPoint(&B, ++builder.GetInsertPoint());

      // Insert a call to our function.
      Value* args[] = {op};
      builder.CreateCall(logFunc, args);

      return true;
    }
  }
}

Необходимыми инструментами являются Module::getOrInsertFunction и IRBuilder::CreateCall. Первый добавляет объявление функции logop, как если бы в коде на C было объявление функции void logop(int i); без тела. Этому добавленному объявлению соответствует определение функции logop в библиотеке (rtlib.c в репозитории):

#include <stdio.h>
void logop(int i) {
  printf("computed: %i\n", i);
}

Чтобы запустить доработанную программу, скомпонуйте ее со своей библиотекой:

$ cc -c rtlib.c
$ clang -Xclang -load -Xclang build/skeleton/libSkeletonPass.so -c example.c
$ cc example.o rtlib.o
$ ./a.out
12
computed: 14
14

При желании можно связать программу и библиотеку до компиляции в машинный код. Вам поможет утилита llvm-link, которую можно рассматривать как грубый эквивалент ld на уровне ПП.

Примечания

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

Практичным и хакерским способом является использование «магических» функций. Объявите в заголовочной файле функции с пустым телом и специальными, по возможности, уникальными именами. Включите данный файл в свой исходный код и добавьте вызовы этих функций. Затем при выполнении прохода найдите инструкции CallInst, вызывающие ваши функции, и используйте их для запуска «магических» функций. Например можно использовать вызовы __enable_instrumentation() и __disable_instrumentation(), чтобы программа ограничила вносимые вами изменения кода конкретными областями.
Если вы хотите разрешить программистам добавлять маркеры к объявлениям функций или переменных, то конструкция Clang __attribute__((Annotate(«foo»))) добавит метаданные с указанной строкой, которую можно обрабатывать при проходе. Брэндон Холт написал об этом приеме манускрипт. Если нужно пометить не объявления, а выражения, подойдет конструкция __builtin_annotation(e, «foo») intrinsic, которая, к сожалению, не задокументирована и имеет ограниченные возможности.
Можно рискнуть и внести изменения непосредственно в Clang для интерпретации вашего нового синтаксиса. Но я не советую это делать.
Если необходимо создать примечания для типов (что, по-моему, требуется довольно часто, даже если вы этого и не осознаете), то сейчас я занимаюсь разработкой системы Quala. Она добавляет в Clang поддержку пользовательских квалификаторов типов и подключаемых систем типов, типа JSR-308 для Java. Сообщите мне, если вы заинтересованы в совместной работе над этим проектом!

Надеюсь рассказать более подробно о перечисленных методах в своих будущих публикациях.

И многое другое…

LLVM обладает огромными возможностями. Перечислю лишь несколько тем, не затронутых в этой статье:

Использование широкого спектра классических инструментов анализа компилятора, доступных в «бардачке» LLVM.
Создание специальных машинных инструкций, необходимых архитекторам, путем доработки backend’а.
Использование отладочной информации для получения данных о номере строки и символа в строке исходного кода, соответствующих определенной точке ПП.
Написание плагинов для backend’а Clang.

Надеюсь, что предоставил вам достаточно информации, чтобы вы смогли создать что-то стоящее. Исследуйте, создавайте и пишите мне, если статья оказалась полезной!
________________________________________

Выражаю благодарность сотрудникам Вашингтонского университета из групп архитектуры и систем, которые присутствовали на презентации устной версии этой статьи и задали много поразительно полезных вопросов.

Дополнение от моих дорогих читателей:

Эмери Бергер (Emery Berger) отметил, что динамические средства бинарного инструментирования, например, Pin, по-прежнему остаются правильным выбором, если необходимо соблюсти конкретные требования архитектуры (регистры, иерархия памяти, кодирование команд и т. д.).
Брэндон Холт (Brandon Holt) только что опубликовал советы по отладке в LLVM, в том числе по составлению диаграмм потока управления с помощью GraphViz.
Джон Регер (John Regehr) прокомментировал, почему не очень хорошо в своем проекте зависеть от блестящего LLVM – API постоянно меняется. Внутренние компоненты LLVM существенно меняются от выпуска к выпуску, поэтому для сохранения проекта необходимо идти в ногу с этими изменениями.
Алекс Брэдбери (Alex Bradbury) издает LLVM Weekly newsletter («Еженедельный информационный бюллетень LLVM») — отличный ресурс для отслеживания событий в экосистеме LLVM.

Перевод выполнен ABBYY Language Services

Tags:

Hubs: