Crazy Rebel: викификация, оформление, иллюстрация

2011-03-14T07:56:28Z

викификация, оформление, иллюстрация

Новая статья

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

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

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

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

{{Врезка|Содержание=[[Изображение:LXF128_76_1.jpg|300px]] Так выглядит промежуточный код на языке ''LLVM''.|Ширина=300px}}

На основе ''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'' только по числу поддерживаемых языков и платформ и несколько уступает по остальным параметрам.

{|class=wikitable border=1 cellpadding=5|-
! LLVM
! GCC
|-
| Генерация и выполнение кода во время выполнения программы, статическая компиляция, мощная оптимизация, основанная на SSA-формах.
| Только статическая компиляция.
|-
| Генерация машинного и байт-кода виртуальной машины либо в файл, либо в оперативную память. Генерация ассемблерного кода.
| Генерация машинного кода в файл. Генерация ассемблерного кода.
|-
| Полноценная поддержка ''C'' и ''C++'' (на основе головной части компилятора ''GCC'') и ''Objective-C'', разрабатывается поддержка других языков.
| Поддерживает множество языков и архитектур, включая все, что доступно ''LLVM''.
|-
| Система типов данных основана на простых типах (элементарные типы, указатели массивы, структуры). Более сложнее типы комбинируются из простых (например, класс – структура с массивом указателей на функции).
| Базовая система типов содержит типы данных, соответствующие типам данных в языках высокого уровня.
|-
| API основан на классах C++, представляющих абстрактный промежуточный код и абстрактный машинный код.
|Структуры API имитируют структуры языков высокого уровня, для которых предназначен компилятор (из-за этого разработчикам ''GNU Pascal'', например, пришлось вносить изменения в сам API).
|}

Прежде чем перейти к исследованию ''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.

{{Врезка|Содержание=[[Изображение:LXF128_77_1.jpg|300px]] Внутренняя структура компилятора ''LLVM-GCC''.|Ширина=300px}}

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

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

в байт-код ''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 может при компиляции разбухнуть до нескольких десятков мегабайт.

{{Врезка|Содержание=[[Изображение:LXF128_78_1.jpg|300px]] Ассемблерный код, сгенерированный ''LLVM''.|Ширина=300px}}

Как уже говорилось, 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'').

<source lang=c>
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;
}
</source>

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

<source lang=c>
int main() {
return 2+3;
}
</source>

Состояние движка ''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

{{Врезка|Содержание=[[Изображение:LXF128_79_1.jpg|300px]] Результат анализа ''LLVM''-программы.|Ширина=300px}}

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

llvm-dis hello.bc

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

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

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

llc hello.ll -o hello.S

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

<source lang=asm>
movl $5, %eax
ret
</source>

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

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

LXF128:LLVM - История изменений

Crazy Rebel: викификация, оформление, иллюстрация