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

    Приветствую хабраюзеров, в этой статье пойдет речь о внутреннем устройстве компилятора 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) вдохновит читателя на изыскания в этой области, а я на этом закончу. Буду рад ответить на ваши вопросы.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 18

      +2
      К сожалению, с проектом такого размера Eclipse CDT как-то не очень хорошо справляется. Залипает. Но есть еще один способ изучения его исходников — это Microsoft Visual Studio.

      Как подготовить и собрать LLVM с MSVS (нужно предварительно установить CMake 2.8):

      cmake -G"Visual Studio 10"
      msbuild LLVM.sln /t:Build /p:Configuration=Debug
      


      Если при этом собирается еще и Clang, то msbuild придется прогнать три раза, первые два выпадут с ошибками.

      Между прочим, тот же самый метод подходит и для Eclipse (только потребуется небольшое изменение в CMakeLists.txt).

      И, кстати, TableGen вовсе не только для бекендов используется. У него множество разнообразных возможностей.
        +1
        Да, спасибо, с tblgen переформулировал.

        Eclipse глючит на коде llvm-gcc, с самим LLVM вроде справляется нормально
          –1
          С LLVM+Clang подтормаживает (на 2Gb памяти).
        0
        Жаль lldb на не-OSX, похоже, не будет.
          0
          на FreeBSD будет
            0
            Пруфлинк? Гугол не в курсе.
            0
            А знаете почему не будет? потому GNU/GPL ^_^

              0
              Нет, там все завязано на mach-специфичные сисколы навроде OSReadSwapInt* и kern_return_t. Со стабами все компилируется несмотря на gpl и прочую eula, но не работает.
                0
                Все там будет. И на линуксе тоже. Я на рассылку подписан, поэтому и в курсе.
            0
            вы бы пояснили, что такое базовый блок. не думаю, что все в курсе
            0
            «Материалы основаны на полуторагодичном опыте исследования LLVM в ИСП РАН.»

            Так вот чем русские учёные занимаются!
              0
              Да, кстати, было бы интересно услышать об этом подробнее.
              0
              Автор, а почему не clang? Используете ли вы KLEE? VMKit? Automatic Pool Allocator?
              Я давно слежу за проектом, но все не знаю откуда к нему подступиться.
                0
                А вы бы попробовали програмно генерить AST кланга. Он, к моему глубочайшему сожалению, для этих целей не годится ни разу. API самого LLVM намного доступнее.
                  0
                  Здесь все равно какой фронтенд, т.к. в обоих случаях от него требуется только сгенерировать LLVM IR. Просто llvm-gcc, на мой взгляд, и собрать сложнее, и старее он.
                    0
                    clang еще очень молод, и некоторое количество кода он не в состоянии скомпилировать. Например, он лишь недавно научился собирать Boost. Ядро Linux он по-моему так и не может собрать до сих пор. Насчет старости — да, он уже немного староват, зато стабилен и им можно с гарантией собрать ВСЕ. Есть проект DragonEgg — плагин к GCC4.5+, который по сути применяет LLVM после парсинга исходников. В общем, можно много интересного еще написать, ждите новых статей от меня и моих коллег!

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое