LLVM изнутри: как это работает
Приветствую хабраюзеров, в этой статье пойдет речь о внутреннем устройстве компилятора LLVM. О том, что LLVM вообще такое, можно прочитать здесь или на llvm.org. Как известно, LLVM (условно) состоит из трех частей — байткода, стратегии компиляции и окружения aka LLVM infrastructure. Я рассмотрю последнее.
В статье взят LLVM 2.7+, работающий под GNU/Linux (Ubuntu 10.04). Используются материалы официальной документации. Материалы основаны на полуторагодичном опыте исследования LLVM в ИСП РАН.
Сборка LLVM
Исходники LLVM можно взять с официальной страницы проекта, как в архиве, так и из репозитория. Сборка LLVM довольно проста, но в ней есть свои особенности: сначала собирается сам LLVM, затем front-end (в нашем случае llvm-gcc), без которого не получится компилировать C/C++ программы. предполагается, что все необходимые библиотеки присутствуют в системе, в противном случае вас все равно обругают при конфигурировании. Итак, мы находимся в корне дерева исходников, собираем LLVM:
# Конфигурация
.. / 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+
# Забираем код
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++
/ 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», так чтобы получилось «$/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»
// Объявление собираемых статистик.
// Каждая из них может быть только челым числом без знака.
// Общее количество базовых блоков
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» ) ;
// Структура (класс) прохода (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 ) ;
// Добавляем количество базовых блоков
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
===-------------------------------------------------------------------------===
. Statistics Collected .
===-------------------------------------------------------------------------===
8 basic-block-stats - Average number of instructions in a basic block
18871 basic-block-stats - Number of basic blocks in the module
153836 basic-block-stats - Number of instructions in the module
Итак, среднее значение инструкций в базовом блоке в коде SQLite равно 8.
Возможно, простота написания собственного прохода (pass) вдохновит читателя на изыскания в этой области, а я на этом закончу. Буду рад ответить на ваши вопросы.