LXF128:LLVM

Материал из Linuxformat.

LLVM Мощная виртуальная машина для встраивания в ваши приложения

LLVM: Генератор быстрого кода

Lua – неплохой, но далеко не единственный вариант встраиваемого языка программирования. Андрей Боровский предлагает альтернативу для тех, кому нужно нечто более мощное.

Некоторые мои коллеги испытывают паническую боязнь перед труднопроизносимыми акронимами, а у меня проекты с названием наподобие LLVM вызывают повышенное доверие. Сразу видно, что разработчики заботятся о существе дела, а не о внешней привлекательности. Что же такое LLVM, кому и зачем он может пригодиться? Коротко на эти вопросы можно ответить так: LLVM (Low Level Virtual Machine, Низкоуровневая виртуальная машина) – это набор инструментов для тех, кому требуется собственный контролируемый компилятор. LLVM предоставляет программисту API для генерации исполняемого кода. Он может создавать байт-код для выполнения на виртуальной машине, а также машинный код непосредственно для процессора. Сгенерированный модуль может быть скомпонован в исполняемый файл, а может выполняться «на лету», из памяти. Таким образом, с помощью LLVM можно создать и статический компилятор, такой как GCC, и среду наподобие 'Java или .NET, и интерпретатор языка программирования в стиле Perl или Lua. И первое, и второе, и третье уже существует на практике.

На основе LLVM создан компилятор для языков C/C++, Fortran, Objective-C, Ada, D. Компания Apple использует LLVM для компиляции кода шейдеров OpenGL во время выполнения программ (Apple также использует LLVM в качестве основы компилятора для нового языка программирования CLang). LLVM может применяться для выполнения или «докомпиляции» байт-кода Java и CIL (.NET). Но он пригодится не только тем, кто пишет собственный компилятор. LLVM применяют в приложениях, которым требуется встроенный язык программирования, причем скорость выполнения встроенной программы имеет значение.

LLVM против GCC

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

Краткое сравнение LLVM и ядра GCC приведено в таблице. В общем и целом можно сказать, что GCC обгоняет LLVM только по числу поддерживаемых языков и платформ и несколько уступает по остальным параметрам.

Прежде чем перейти к исследованию LLVM на практике, нужно уточнить, чем он не является. LLVM не содержит средств для построения лексических и синтаксических анализаторов (головная часть компилятора C/C++ LLVM позаимствована из проекта GCC).

Приступая к работе

Пакеты LLVM входят в репозитории всех популярных дистрибутивов Linux, а исходные тексты последних релизов можно загрузить из Subversion-репозитория проекта на сайте http://llvm.org. Для сборки LLVM потребуется CMake не младше версии 2.6.2 (даже если вы не компилируете сам LLVM, последняя версия CMake все равно пригодится, так как примеры, поставляемые с LLVM, используют CMake). Помимо библиотек и утилит LLVM, вы можете установить головную часть компилятора LLVM-GCC (С/C++ LLVM front-end), который использует LLVM для генерации машинного кода.

Как уже было сказано, LLVM можно использовать в качестве ядра «обычного» компилятора. Если вы установите LLVM-GCC, в недрах вашей системы появятся программы llvm-gcc, llvm-g++ и другие (у меня они расположены в директории /usr/lib/llvm/llvm/gcc-4.2/bin/). Чтобы проверить, как работает компилятор на основе LLVM, замените в Make-файле любого проекта значения переменных CC и CXX со стандартных компиляторов GCC на компиляторы LLVM и соберите проект. Полученный машинный код несколько лучше оптимизирован по размеру и несколько хуже – по быстродействию, но эти различия не слишком существенны. Главное преимущество LLVM заключается в скорости компиляции модулей встроенным JIT-компилятором, что очень важно для сборки во время выполнения.

В состав LLVM входит несколько утилит, которые, в отличие от головной части компилятора C/C++, необходимы при использовании LLVM в собственных проектах:

• llvm-ld – компоновщик объектного кода, сгенерированного LLVM (превращает объектные файлы в исполняемые модули);
• llvm-as – ассемблер, собирающий промежуточные файлы LLVM в байт-код;
• lli – динамический компилятор байт-кода LLVM (преобразует байт-код в машинный и выполняет на лету, используя JIT-компилятор или интерпретатор);
• llc – преобразует байт-код LLVM в ассемблерный текст, который может быть передан «родному» ассемблеру системы для генерации программы в машинных кодах;
• llvmc – компилирует программу на языке LLVM в исполняемый файл операционной системы;
• llvm-nm – аналог утилиты nm для файлов виртуальной машины LLVM.;
• llvm-ar – аналог утилиты ar;
• llvm-prof – профилировщик программ LLVM;
• llvm-bcanalyzer – анализатор исполняемых файлов виртуальной машины LLVM;
• llvm-dis – дизассемблер байт-кода LLVM.

Кроме этих утилит, в состав LLVM входит множество библиотек, которые реализуют интерфейс программирования LLVM API.

Скомпилируем простую программу на языке C –

#include <stdio.h>
 int main() {
   printf(“hello world\n”);
   return 0;
 }

в байт-код LLVM. Как мы уже знаем, по умолчанию компилятор llvm-gcc генерирует обычный машинный код. Чтобы создать исполняемый файл виртуальной машины LLVM, компилятор необходимо вызвать со специальным ключом -emit-llvm:

llvm-gcc helloworld.c -emit-llvm -c -o helloworld.bc

В результате будет создан файл helloworld.bc, который может быть выполнен с помощью программы lli:

lli ./helloworld.bc

Программа сделает то, чего мы от нее и ожидали. Все это выглядит тривиально, пока мы не зададим себе вопрос: откуда приложение, скомпилированное в байт-код LLVM, взяло функцию printf()? Для ответа на него нам понадобится провести небольшой анализ. Скомандуем:

llvm-gcc -emit-llvm helloworld.c -S -o helloworld.ll

Ключ -S, используемый совместно с -emit-llvm, заставляет компилятор генерировать файл программы на промежуточном языке LLVM (обычно ему присваивается расширение .ll). Этот язык можно сравнить с Microsoft Intermediate Language, используемым наплатформе .NET. Именно в него дизассемблирует скомпилированный код утилита llvm-dis (аналог ildasm для .NET). Файл helloworld.ll содержит следующее:

; ModuleID = 'helloworld.c'
target datalayout = “e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-
i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-
s0:64:64-f80:128:128”
target triple = “x86_64-linux-gnu”
@.str = private constant [12 x i8] c”hello world\00”, align 1 ; <[12 x
i8]*> [#uses=1]
define i32 @main() nounwind {
entry:
%retval = alloca i32; <i32*> [#uses=2]
%0 = alloca i32 ; <i32*> [#uses=2]
%”alloca point” = bitcast i32 0 to i32; <i32> [#uses=0]
%1 = call i32 @puts(i8* getelementptr inbounds ([12 x i8]* @.str,
i64 0, i64 0)) nounwind ; <i32> [#uses=0]
store i32 0, i32* %0, align 4
%2 = load i32* %0, align 4; <i32> [#uses=1]
store i32 %2, i32* %retval, align 4
br label %return
return: ; preds = %entry
%retval1 = load i32* %retval ; <i32> [#uses=1]
ret i32 %retval1
}

Язык LLVM – типичный способ промежуточного представления кода программы, построенный по принципу статического однократного присваивания (Static Single Assignment, SSA).

В этой модели в левой части каждого присваивания используется уникальная переменная, даже если в исходном тексте в двух присваиваниях использовалась одна и та же. На первый взгляд, использование переменных в SSA кажется расточительством, но следует помнить, что речь идет о промежуточном представлении кода, а не о выделении ресурсов реальной системы. При генерации исполняемого кода из SSA-формы лишние переменные (в том числе объявленные программистом) удаляются. Если вас интересуют подробности промежуточного языка LLVM, вы можете обратиться к обширному руководству http://llvm.org/docs/LangRef.html. Мы же обратим внимание на то, что вместо функции printf() в коде LLVM вызывается функция puts(). LLVM поддерживает функции стандартной библиотеки C по умолчанию (а также позволяет импортировать их из разделяемых библиотек явным образом).

Программа на языке LLVM может быть скомпилирована в байт-код виртуальной машины LLVM –

llvm-as helloworld.ll -o helloworld

или в исполняемый файл Linux:

llvmc helloworld.ll -o helloworld

Если мы хотим увидеть, как код на языке LLVM превращается в ассемблерный код, к нашим услугам команда

llc helloworld.ll -o helloworld.S

LLVM API

LLVM API, позволяющий генерировать промежуточный код LLVM из любой программы, написанной на C++, представляет собой набор классов C++, объявленных в пространстве имен llvm. Доступная в Сети документация не всегда может нам помочь, так как LLVM API все еще не обрел стабильности. Впрочем, его элементы неплохо документированы по месту своего объявления, так что лучшим источником информации для нас будут заголовочные файлы. Для сборки примеров использования LLVM API рекомендуется применять CMake, однако, как это нередко бывает с активно развивающимися проектами, исходные тексты, которые хорошо собираются на машинах своих разработчиков, иногда отказываются компилироваться на других машинах. Убедитесь, что у вас установлена новейшая версия CMake и что проектам примеров доступны вспомогательные файлы *.cmake, поставляемые вместе с LLVM. Если все это не помогает, придется спуститься на один уровень ниже.

Утилита llvm-config позволяет получить наборы флагов препроцессора, компилятора и компоновщика, необходимые для сборки проектов LLVM «вручную». Вот как, например, должна выглядеть командная строка для сборки примера из директории llvm/examples/Fibonacci:

/usr/lib/llvm/llvm/gcc-4.2/bin/llvm-g++ fibonacci.cpp `llvm-config --cppflags` `llvm-config --libs engine backend interpreter
scalaropts` `llvm-config --ldflags` -c –o fibonacci

LLVM API разбит на несколько модулей. Для компоновки требуемых библиотек имена модулей необходимо указывать в качестве аргумента утилиты llvm-config, вызванной с ключом --libs.

Полный список модулей должен быть доступен при вызове

llvm-config --libs all

но у меня эта опция почему-то не работала, так что пришлось перечислять модули явным образом. Модуль engine включает в себя библиотеки, ответственные за JIT-компиляцию. Backend охватывает библиотеки, выполняющие генерацию машинного кода или кода на C. Модули bitreader и bitwriter предназначены для работы с исполняемыми файлами, содержащими байт-код. Помимоэтих модулей, в различных проектах могут понадобиться модули scalaropts, interpreter, transformutils, analysis, linker, archive, ipo.

По умолчанию реализация классов LLVM API хранится в статических библиотеках, так что даже простая программа-пример использования API может при компиляции разбухнуть до нескольких десятков мегабайт.

Как уже говорилось, LLVM API является абстрактным представлением промежуточного кода LLVM, в котором каждому элементу языка LLVM соответствует свой класс. Минимальной единицей компиляции кода LLVM является модуль. Модули языка LLVM очень похожи на модули языка Pascal – они содержат объявления типов данных, переменных, констант и функций, находящиеся в общей области видимости. Модули языка LLVM (которые не следует путать с упомянутыми выше модулями LLVM API) представлены в LLVM API классом Module, объявленным в заголовочном файле llvm/Module.h. Каждому типу данных языка LLVM соответствует свой собственный класс, унаследованный от Type (llvm/Type.h), например, IntegerType (целые числа), ArrayType (массивы), PointerType (указатели), VectorType (векторы, разновидность массивов), StructType (структуры) и FunctionType (заголовки функций), OpaqueType (пользовательский тип), FloatType и DoubleType (числа с плавающей точкой), VoidType (пустой тип для заголовков функций и указателей). Эти классы объявлены в заголовочном файле llvm/DerivedTypes.h. На самом деле перечисленные типы правильнее назвать мета-типами. Например, тип данных для работы с целыми числами имеет несколько подтипов, соответствующих разному числу двоичных разрядов. Такие классы, как FunctionType и StructType, и вовсе охватывают бесконечные множества типов, каждый из которых генерируется специальным конструктором.

Константные значения, соответствующие типам LLVM, представляются классом Value, объявленном в llvm/Value.h. Глобальные переменные представлены классом GlobalVariable, а функции – классом Function. В соответствии с принципами модели SSA локальные переменные не объявляются явно, а создаются по месту для сохранения результатов операций (глобальные переменные, видимые за пределами модуля, должны быть, разумеется, объявлены явным образом). Класс BasicBlock представляет базовый блок – последовательность инструкций с одной точкой входа и (возможно) несколькими точками выхода. Все операции языка LLVM представлены потомками класса Instruction (операнды этих инструкций представлены объектами класса Value).

Попробуем в деле

Рассмотрим простейший пример генерации кода с помощью LLVM API (файл codegen.cpp представляет собой видоизмененный пример из дистрибутива LLVM).

int main(int argc, char ** argv) {
  int fdd;
  if(argc < 2)
    fdd = 0;
  else
    fdd = creat(argv[1], 0666);
  LLVMContext Context;
  raw_fd_ostream fd(fdd, false);
  Module *M = new Module(“test”, Context);
  FunctionType *FT = FunctionType::get(Type::getInt32Ty(Context), false);
  Function *F = Function::Create(FT, Function::ExternalLinkage, “main”, M);
   BasicBlock *BB = BasicBlock::Create(Context, “EntryBlock”, F);
   Value *Two = ConstantInt::get(Type::getInt32Ty(Context), 2);
   Value *Three = ConstantInt::get(Type::getInt32Ty(Context), 3);
   Instruction *Add = BinaryOperator::Create(Instruction::Add, Two, Three, “addresult”);
   BB->getInstList().push_back(Add);
   BB->getInstList().push_back(ReturnInst::Create(Context, Add));
   WriteBitcodeToFile(M, fd);
   delete M;
   return 0;
 }

В этом примере мы создаем модуль, состоящий из одной-единственной функции main(). Его аналог на C выглядит так:

int main() {
  return 2+3;
 }

Состояние движка LLVM представлено объектом класса Context. Создавая объекты, представляющие элементы языка LLVM, мы передаем ссылку на него функциям-конструкторам. Генерация кода начинается с создания объекта класса Module. Первый аргумент конструктора – имя модуля. Далее мы создаем функцию main(), которую в программе представляет объект F класса Function. Предварительно создается соответствующий тип (объект FT класса FunctionType) – это выполняется с помощью статического метода FunctionType::get(), первым аргументом которого является тип возвращаемого функцией значения, а второй указывает, вызывается ли функция с переменным числом параметров. Статический метод Type::getInt32Ty() создает объект-потомок класса Type, представляющий 32‑битное целое. Создавая объект, представляющий саму функцию, мы передаем конструктору ее тип, указание на области видимости (Function::ExternalLinkage – функция видима за пределами модуля), строку с именем функции и указатель на объект-модуль. Функция должна содержать как минимум один базовый блок. В нашей программе он представлен объектом BB класса BasicBlock. Второй аргумент конструктора базового блока – имя; оно дается для наглядности. Если нам не требуется называть блок осмысленным именем, можно передать конструктору пустую строку.

Теперь у нас есть заготовка функции, которую можно заполнять инструкциями. Их в нашем примере будет две: сложение целых чисел и возврат из функции. Численные константы 2 и 3 представлены в программе объектами-потомками класса Value. Они создаются с помощью статического метода ConstantInt::get() (который, как видно из его имени, позволяет определять целочисленные константы). Первый аргумент метода ConstantInt::get() – подтип константы, второй – ее значение. Теперь мы создаем саму инструкцию сложения (объект Add) с помощью статического метода BinaryOperator::Create() (класс BinaryOperator представляет инструкции, являющиеся бинарными операциями). Первый аргумент конструктора – константа Instruction::Add – указывает на то, что нам требуется операция сложения. Последний аргумент конструктора – имя переменной, в которой будет сохранен результат операции. На помню, что в модели кода LLVM результат любой операции должен быть сохранен в своей собственной переменной. Имя переменной, как и имя базового блока, задается нами для собственного удобства. Если вместо имени мы укажем пустую строку, LLVM создаст для переменной имя вида %xxx, где xxx – некоторое число. Теперь мы добавляем инструкцию Add в базовый блок. Метод getInstList() класса BasicBlock позволяет нам получить доступ к списку инструкций блока. Метод push_back() добавляет инструкцию в конец списка. Инструкция возврата из функции создается с помощью конструктора ReturnInst::Create(). Второй аргумент конструктора указывает на операцию Add. Это требуется для того, чтобы инструкция возврата знала, результат какой операции она должна использовать в качестве возвращаемого значения функции.

Итак, нам понадобился десяток строк довольно сложного кода на C++, чтобы сгенерировать функцию, C-эквивалент которой состоит из двух строк. Теперь вы можете на практике оценить, сколько труда экономят нам компиляторы. Нам остается сгенерировать байт-код LLVM и сохранить его в файле, что мы и делаем с помощью функции WriteBitcodeToFile().

Для компиляции программы командуем:

llvm-g++ codegen.cpp `llvm-config --cppflags` `llvm-config --libsbitwriter` `llvm-config --ldflags` -o codegen

затем

codegen hello.bc

и получаем файл hello.bc – исполняемый файл виртуальной машины LLVM. Можно выполнить его с помощью утилиты lli, однако, поскольку наша функция main() никак не взаимодействует с внешним миром, ничего интересного не случится. Вместо этого продизассемблируем файл hello.bc:

llvm-dis hello.bc

В результате получим файл hello.ll следующего содержания:

; ModuleID = 'hello.bc'
 define i32 @main() {
 %1 = add i32 2, 3 ; <i32> [#uses=1]
 ret i32 %1
 }

Переменная %1 в этом коде явно избыточна. Я обещал вам, что оптимизатор LLVM удалит лишние переменные, и теперь вы можете меня проверить:

llc hello.ll -o hello.S

Откроем ассемблерный файл и увидим, что функция main() для процессоров Intel состоит из двух ассемблерных инструкций:

movl $5, %eax
 ret

Компилятор не только избавился от промежуточной переменной, но и заменил сложение двух констант результатом. Вызывая утилиту llc с ключами -mrach=ppc32, -march=arm и другими, можно убедиться в том, что чудеса оптимизации доступны и на других процессорах.

Возвращаясь к началу, повторим: система LLVM не может сделать за вас компилятор или интерпретатор, но она может помочь в той точке, где многие проекты компиляторов входят в мучительный тупик – в генерации исполняемого кода промышленного качества.