Как стать автором
Обновить

LLVM изнутри: как это работает

Время на прочтение 10 мин
Количество просмотров 26K
Приветствую хабраюзеров, в этой статье пойдет речь о внутреннем устройстве компилятора LLVM. О том, что LLVM вообще такое, можно прочитать здесь или на llvm.org. Как известно, LLVM (условно) состоит из трех частей — байткода, стратегии компиляции и окружения aka LLVM infrastructure. Я рассмотрю последнее.

Содержание:
  • Сборка LLVM
  • Привязка к Eclipse
  • Архитектура окружения
  • LLVM API
  • Оптимизация Hello, World!
В статье взят LLVM 2.7+, работающий под GNU/Linux (Ubuntu 10.04). Используются материалы официальной документации. Материалы основаны на полуторагодичном опыте исследования LLVM в ИСП РАН.

Сборка LLVM

Исходники LLVM можно взять с официальной страницы проекта, как в архиве, так и из репозитория. Сборка LLVM довольно проста, но в ней есть свои особенности: сначала собирается сам LLVM, затем front-end (в нашем случае llvm-gcc), без которого не получится компилировать C/C++ программы. предполагается, что все необходимые библиотеки присутствуют в системе, в противном случае вас все равно обругают при конфигурировании. Итак, мы находимся в корне дерева исходников, собираем LLVM:
mkdir build && cd build
 
# Конфигурация
../configure --enable-jit --enable-optimized --enable-shared --prefix=/prefix --enable-targets=host-only
 
# --enable-shared позволяет собрать ядро LLVM как одну большую shared library
# вместо /prefix задайте нужный путь для инсталляции
# --enable-targets=host-only означает поддержку только хозяйской архитектуры
# для дополнительного ускорения можно добавить --disable-assertions, их в коде на каждом шагу, в т.ч. в циклах
 
# Сборка
make -j2 CXXFLAGS=-O3
# -jN весьма символично, большую часть времени все равно все будет собираться в один поток,
# ничего с этим поделать нельзя

# CXXFLAGS=-O3 дает дополнительные оптимизации GCC.
# Можно еще добавить -flto для включения link-time оптимизаций в случае GCC 4.5+

 
# Инсталляция
make install
Теперь собираем llvm-gcc:
# Забираем код
svn co http://llvm.org/svn/llvm-project/llvm-gcc-4.2/trunk llvm-gcc
 
cd llvm-gcc && mkdir build && cd build
 
# Конфигурация
../configure --enable-llvm=/path/to/llvm/build --prefix=/prefix/of/llvm --program-prefix=llvm- --enable-languages=c,c++
# /path/to/llvm/build означает путь к той самой папке build, созданной на предыдущем этапе
# /prefix/of/llvm - для удобства, префикс совпадает с префиксом LLVM
# --program-prefix=llvm- нужно для получения общеупотребительных имен бинарников вроде llvm-gcc или llvm-g++
 
# Сборка
make -j2 CFLAGS=-O3
 
# Инсталляция
make install
Если все прошло успешно, то пройдет, например, такая проверка:
/prefix/of/llvm/llvm-gcc -v

gcc version 4.2.1 (Based on Apple Inc. build 5658) (LLVM build)

Привязка к Eclipse

Для удобства, расскажу как собирать и изучать исходный код LLVM в Eclipse (разумеется, с поддержкой C/C++). Создаем новый проект C++ /File-New — C++ Project/, Задаем название «llvm» /Project name/, снимаем галку с расположения по умолчанию /Use default location/ и задаем путь к дереву исходников LLVM, тип проекта ставим Makefile /Project type: Makefile project — Empty Project/. Далее жмем «Закончить» /Finish/. Пока Eclipse разбирает файлы и строит индекс навигации, заходим в свойства проекта /Project — Properties/. В настройках сборщика /Builder Settings/ снимаем галку с команды сборки по умолчанию /Use default build command/ и вписываем «make -j2 CXXFLAGS=-O3». В директории сборки /Build directory/ дописываем "/build", так чтобы получилось "${workspace_loc:/llvm}/build". Переходим во вкладку поведения /Behavior/ и справа от цели сборки /Build (Incremental build)/ стираем «all». Последнее не обязательно и нужно скорее для идентичности ручной сборке в консоли. Готово! Можно смело прыгать по классам, смотреть #define-ы и нажимать на кнопку сборки /Build/. Для избежания возможных проблем (у кого как) можно удалить из дерева тесты (tests).

Архитектура окружения

LLVM состоит из нескольких исполняемых файлов, использующих libLLVM2.x.so (ядро).
opt — инструмент, оперирующий байткодом: он может накатывать любые доступные машинно-независимые оптимизации в произвольном порядке, проводить различные виды анализа и добавлять профилирование. Существуют уровни оптимизации O0, O1, O2 и O3.
llc — кодогенератор из байткода в ассемблер целевой машины. Выполняет машинно-зависимые оптимизации. Так же существуют уровни оптимизации O0, O1, O2 и O3.
llvm-ld — линковщик байткода, т.е. инструмент соединяет несколько байткодных файлов в один большой BC файл. При этом накатываются link-time оптимизации, которыми так гордятся создатели.
lli — интерпретатор байткода с возможностью JIT компиляции.
llvm-dis — преобразователь байткода (bc) в эквивалентное текстовое представление (ll).
llvm-as — преобразователь текстового представления (ll) в байткод (bc).
llvm-ar — упаковщик нескольких файлов в один. Некий аналог bzip2.
llvmc — драйвер LLVM, вызывающий по очереди парсер языка (т.е. front-end: llvm-gcc или clang), opt, llc (указанный back-end для целевой машины), ассемблер и линковщик целевой машины. Общая схема изображена на рисунке.



Стоит отметить, что в качестве back-end поддерживаются все общеизвестные архитектуры (в т.ч. x86, x86-64, ARM), и даже такая экзотика как язык C. Последнее означает, что можно преобразовать байткод сразу в исходник на C… но вряд ли он вам понравится без имен переменных (вернее, с иными названиями, присвоенными в байткоде), с циклами на goto, измененным порядком следования команд и еще много с чем другим. А как же иначе, чудес не бывает. Кстати, байткод можно потенциально превращать и в код виртуальной машины Java или .NET.

Интересна реализация «железных» back-end-ов. На раннем этапе сборки LLVM появляется утилита под названием tblgen. Она в том числе преобразовывает описания ассемблеров на специфичном описательном языке в C++ код, который в дальнейшем #include-ится в классы, реализующие кодогенерацию. Таким образом, очень легко что-то изменить или добавить в систему команд, а поддержка унифицируется. В отличие от GCC, не надо сильно напрягаться над кросскомпиляцией: при вызове llc достаточно указать -march=armv7, где на месте armv7 может стоять любая поддерживаемая архитектура. Не могу не упомянуть здесь принципиальное отличие LLVM от, скажем, Java: байткод LLVM в общем случае зависит от платформы, на которой его получают и целевой машины, под которую компилируют. Первое объясняется линковкой с библиотеками, зависящими от ОС, второе — ассемблерными вставками и портированием кода (условной компиляцией) на различные архитектуры.

Значения некоторых папок с кодом:
  • include — загловочные файлы
  • tools — реализация перечисленных выше инструментов
  • runtime — реализация сбора профиля
  • tools — реализация служебных утилит LLVM, в т.ч. tblgen
  • examples — примеры использования LLVM
  • lib — главная часть
  • lib/Analysis — проходы, осуществляющие анализ (о проходах см. дальше)
  • lib/CodeGen — реализация кодогенерации, машинно-зависимых проходов
  • lib/Transforms — проходы, выполнимые над байткодом
В принципе, значения очевидны из названий, и эта очевидность не обманчива.

LLVM API

Ядро LLVM — очень мощная система. Все рутинные вещи спрятаны от рядовых разработчиков, давая возможность сосредоточиться над улучшением качества компилятора. Подробная документация, множество материалов позволяют быстро войти в курс дела. Имена классов, методов, схема наследования — все продумано до мелочей. Я немного расскажу об API, связанном с оптимизациями. Чтобы было не скучно, желательно знать, что означают такие термины как базовый блок (basic block) и граф потока управления (он же CFG, Control Flow Graph). Хватит информации из Wikipedia: базовый блок и граф потока управления.

Вообще принято говорить о проходах (passes), а не об оптимизациях. Проход это реализация конкретной оптимизации или ее части. У LLVM есть менеджер проходов (PassManager), который работает по принципу FIFO. Сначала добавляются описания проходов, а затем менеджер их одну за другой выполнит. Причем, если проход нуждается в данных некоторого анализа CFG, то менеджер предварительно проведет этот анализ, если его данные устарели. Проходы работают в рамках функции (наследуются от FunctionPass) или базового блока (BasicBlockPass). В первом случае на вход алгоритму будет подана функция, во втором — базовый блок. У функции можно стандартным образом итерировать по базовым блокам, у базового блока, соответственно, по инструкциям. Можно все переставлять местами, как вздумается, добавлять новые элементы.

LLVM opt поддерживает подключаемые модули — этакие shared passes. Во время вызова библиотека подгружается и принимается к сведению. Благодаря этому для расширения возможностей компилятора необязательно делать свою ветку кода и потом ее править, достаточно нужных заголовочных файлов. Как известно, в GCC такое появилось совсем недавно.

Как говорится, лучше один раз увидеть, чем сто раз услышать. Перейдем к практике.

Оптимизация Hello, World!

Применим полученные знания для написания собственной самой настоящей машинно-независимой оптимизации. Все, что она будет делать, это собирать статистику о среднем количестве инструкций в базовом блоке, и по факту ничего не оптимизировать. Соберем ее в виде подключаемого модуля opt, чтобы не править код LLVM. Создадим в корне дерева исходников LLVM папку plugins, а в ней — файл BasicBlockStats.cpp со следующим содержимым:
#define DEBUG_TYPE "basic-block-stats"
#include "llvm/Pass.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/BasicBlock.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Support/CFG.h"
 
using namespace llvm;
 
// Объявление собираемых статистик.
// Каждая из них может быть только челым числом без знака.
 
// Общее количество базовых блоков
STATISTIC(NumberOfBasicBlocks, "Number of basic blocks in the module");
 
// Общее количество инструкций
STATISTIC(NumberOfInstructions, "Number of instructions in the module");
 
// Среднее количество инструкций на базовый блок
STATISTIC(AverageInstructionsInBasicBlock, "Average number of instructions in a basic block");
 
namespace 
{
 
// Структура (класс) прохода (pass)
// В общепринятой терминологии оптимизации называются проходами, т.к.
// действие над модулем выполняется за один полный проход по его содержимому
struct BasicBlockStats : public FunctionPass
{
// Идентификационный номер прохода
  static char ID;
 
  BasicBlockStats() : FunctionPass(ID) { }
 
  // Перегрузка метода, сообщающего менеджеру проходов, что использует и меняет данный проход
  virtual void getAnalysisUsage(AnalysisUsage &AU) const
  {
   // Ничего не используем, ничего не меняем
    AU.setPreservesAll();
  }
 
  // Перегрузка метода, который несет смысл прохода - операции над функцией модуля
  virtual bool runOnFunction(Function &F);
 
  ~BasicBlockStats()
  {
   // При вызове деструктора считаем искомое число
   AverageInstructionsInBasicBlock = NumberOfInstructions / NumberOfBasicBlocks;
  }
};
 
// Идентифицировать себя нам незачем
char BasicBlockStats::ID = 0;
 
// Выполняем регистрацию прохода в менеджере проходов
RegisterPass<BasicBlockStats> X("basic-block-stats""Basic Block Statistics"true);
 
} // end of unnamed namespace
 
// Реализация основной логики
bool BasicBlockStats::runOnFunction(Function &F) 
{
// Проходим по каждому базовому блоку функции
  for (Function::iterator I = F.begin(), E = F.end(); I != E; I++)
  {
  NumberOfInstructions += I->size();
  }
 
  // Добавляем количество базовых блоков
  NumberOfBasicBlocks += F.size();
  return false;
}
Я постарался максимально снабдить код комментариями, чтобы было понятно. Теперь собираем наш подключаемый модуль:
g++ -c -fPIC BasicBlockStats.cpp -o BasicBlockStats.o -I../include -I../build/include -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROS
gcc -shared -s BasicBlockStats.o -o BasicBlockStats.so
Настало время проверить, а работает ли? Я предлагаю провести проверку в боевых условиях на коде SQLite. Качаем sqlite-amalgamation-A_B_C_D.zip, распаковываем куда-нибудь. Далее я предполагаю что путь к установленным исполняемым файлам LLVM и llvm-gcc, а также к BasicBlockStats.so прописан в $PATH.
# Собираем библиотеку SQLite в байткод
llvm-gcc -emit-llvm -c sqlite3.c -o sqlite3.bc
 
# Запускаем нашу оптимизацию
# -stats показывает все собранные статистики
opt sqlite3.bc -load BasicBlockStats.so -basic-block-stats -stats -o sqlite3.bc
 
===-------------------------------------------------------------------------===<br/>
                         ... Statistics Collected ...<br/>
===-------------------------------------------------------------------------===<br/>
 <br/>
      8   basic-block-stats - Average number of instructions in a basic block<br/>
  18871   basic-block-stats - Number of basic blocks in the module<br/>
 153836   basic-block-stats - Number of instructions in the module
Итак, среднее значение инструкций в базовом блоке в коде SQLite равно 8.

Возможно, простота написания собственного прохода (pass) вдохновит читателя на изыскания в этой области, а я на этом закончу. Буду рад ответить на ваши вопросы.
Теги:
Хабы:
+49
Комментарии 18
Комментарии Комментарии 18

Публикации

Истории

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн