Приветствую хабраюзеров, в этой статье пойдет речь о внутреннем устройстве компилятора LLVM. О том, что LLVM вообще такое, можно прочитать здесь или на llvm.org. Как известно, LLVM (условно) состоит из трех частей — байткода, стратегии компиляции и окружения aka LLVM infrastructure. Я рассмотрю последнее.
Исходники LLVM можно взять с официальной страницы проекта, как в архиве, так и из репозитория. Сборка LLVM довольно проста, но в ней есть свои особенности: сначала собирается сам LLVM, затем front-end (в нашем случае llvm-gcc), без которого не получится компилировать C/C++ программы. предполагается, что все необходимые библиотеки присутствуют в системе, в противном случае вас все равно обругают при конфигурировании. Итак, мы находимся в корне дерева исходников, собираем LLVM:
Для удобства, расскажу как собирать и изучать исходный код 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 в общем случае зависит от платформы, на которой его получают и целевой машины, под которую компилируют. Первое объясняется линковкой с библиотеками, зависящими от ОС, второе — ассемблерными вставками и портированием кода (условной компиляцией) на различные архитектуры.
Значения некоторых папок с кодом:
Ядро LLVM — очень мощная система. Все рутинные вещи спрятаны от рядовых разработчиков, давая возможность сосредоточиться над улучшением качества компилятора. Подробная документация, множество материалов позволяют быстро войти в курс дела. Имена классов, методов, схема наследования — все продумано до мелочей. Я немного расскажу об API, связанном с оптимизациями. Чтобы было не скучно, желательно знать, что означают такие термины как базовый блок (basic block) и граф потока управления (он же CFG, Control Flow Graph). Хватит информации из Wikipedia: базовый блок и граф потока управления.
Вообще принято говорить о проходах (passes), а не об оптимизациях. Проход это реализация конкретной оптимизации или ее части. У LLVM есть менеджер проходов (PassManager), который работает по принципу FIFO. Сначала добавляются описания проходов, а затем менеджер их одну за другой выполнит. Причем, если проход нуждается в данных некоторого анализа CFG, то менеджер предварительно проведет этот анализ, если его данные устарели. Проходы работают в рамках функции (наследуются от FunctionPass) или базового блока (BasicBlockPass). В первом случае на вход алгоритму будет подана функция, во втором — базовый блок. У функции можно стандартным образом итерировать по базовым блокам, у базового блока, соответственно, по инструкциям. Можно все переставлять местами, как вздумается, добавлять новые элементы.
LLVM opt поддерживает подключаемые модули — этакие shared passes. Во время вызова библиотека подгружается и принимается к сведению. Благодаря этому для расширения возможностей компилятора необязательно делать свою ветку кода и потом ее править, достаточно нужных заголовочных файлов. Как известно, в GCC такое появилось совсем недавно.
Как говорится, лучше один раз увидеть, чем сто раз услышать. Перейдем к практике.
Применим полученные знания для написания собственной самой настоящей машинно-независимой оптимизации. Все, что она будет делать, это собирать статистику о среднем количестве инструкций в базовом блоке, и по факту ничего не оптимизировать. Соберем ее в виде подключаемого модуля opt, чтобы не править код LLVM. Создадим в корне дерева исходников LLVM папку plugins, а в ней — файл BasicBlockStats.cpp со следующим содержимым:
Возможно, простота написания собственного прохода (pass) вдохновит читателя на изыскания в этой области, а я на этом закончу. Буду рад ответить на ваши вопросы.
Содержание:
- Сборка LLVM
- Привязка к Eclipse
- Архитектура окружения
- LLVM API
- Оптимизация Hello, World!
Сборка LLVM
Исходники LLVM можно взять с официальной страницы проекта, как в архиве, так и из репозитория. Сборка LLVM довольно проста, но в ней есть свои особенности: сначала собирается сам LLVM, затем front-end (в нашем случае llvm-gcc), без которого не получится компилировать C/C++ программы. предполагается, что все необходимые библиотеки присутствуют в системе, в противном случае вас все равно обругают при конфигурировании. Итак, мы находимся в корне дерева исходников, собираем LLVM:
mkdir build && cd buildТеперь собираем llvm-gcc:
# Конфигурация
../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
# Забираем кодЕсли все прошло успешно, то пройдет, например, такая проверка:
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Настало время проверить, а работает ли? Я предлагаю провести проверку в боевых условиях на коде SQLite. Качаем sqlite-amalgamation-A_B_C_D.zip, распаковываем куда-нибудь. Далее я предполагаю что путь к установленным исполняемым файлам LLVM и llvm-gcc, а также к BasicBlockStats.so прописан в $PATH.
gcc -shared -s BasicBlockStats.o -o BasicBlockStats.so
# Собираем библиотеку SQLite в байткодИтак, среднее значение инструкций в базовом блоке в коде SQLite равно 8.
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
Возможно, простота написания собственного прохода (pass) вдохновит читателя на изыскания в этой области, а я на этом закончу. Буду рад ответить на ваши вопросы.