Обзор LLVM

LLVM (Low Level Virtual Machine) — это универсальная система анализа, трансформации и оптимизации программ или, как её называют разработчики, «compiler infrastucture».

LLVM — не просто очередной академический проект. Его история началась в 2000 году в Университете Иллинойса, а теперь LLVM используют такие гиганты индустрии как Apple и Adobe. В частности, на LLVM основана подсистема OpenGL в MacOS X 10.5, а iPhone SDK использует GCC с бэкэндом на LLVM. Apple является одним из основных спонсоров проекта, а вдохновитель LLVM — Крис Латтнер — теперь работает в Apple.

В основе LLVM лежит промежуточное представление кода (intermediate representation, IR), над которым можно производить трансформации во время компиляции, компоновки (linking) и выполнения. Из этого представления генерируется оптимизированный машинный код для целого ряда платформ, как статически, так и динамически (JIT-компиляция). LLVM поддерживает генерацию кода для x86, x86-64, ARM, PowerPC, SPARC, MIPS, IA-64, Alpha.

LLVM написана на C++ и портирована на большинство *nix-систем и Windows. Система имеет модульную структуру и может расширяться дополнительными алгоритмами трансформации (compiler passes) и кодогенераторами для новых аппаратных платформ. Пользовательский фронтенд, как правило, линкуется с LLVM и использует C++ API для генерации кода и его преобразований. Однако LLVM включает в себя и standalone утилиты.

Для тех, кто не без оснований считает C++ не лучшим языком для написания компиляторов, с недавних пор в LLVM включена обертка API для OCaml.

Чтобы понять, что можно сделать с помощью LLVM, и на каком уровне придётся работать, давайте разберёмся, что из себя представляет LLVM IR. В одном предложении его можно охарактеризовать как типизированный трёхадресный код в SSA-форме.

Здесь и далее мы будем использовать текстовую форму записи промежуточного кода, своеобразный «ассемблер» LLVM. На практике для хранения кода используется эффективное бинарное представление (bitcode). Генерировать же код обычно удобнее всего не в текстовой форме, и тем более не в бинарной, а с помощью специального API. До биткода в этом случае может и не доходить: код формируется в виде внтуренних структур в памяти, над которыми и проводятся все операции, вплоть до генерации машинного кода.

Типы данных

В LLVM поддерживаются следующие примитивные типы:

• Целые числа произвольной разрядности:
  

  i1 ; булево значение — 0 или 1<br/> i32 ; 32-разрядное целое<br/> i17 ; даже так<br/> i256 ; ого!

  Генерация машинного кода для типов очень большой разрядности не поддерживается. Например, для x86 вам придётся ограничиться i64, а для x86-64 и других 64-разрядных платформ — 128-битными целыми. Но для промежуточного представления никаких ограничений нет.
  Числа считаются представленными в дополнительном коде. Различий между знаковыми и беззнаковыми целыми на уровне типов не делается: в тех случаях, когда это имеет значение, с ними работают разные инструкции.
  
• Числа с плавающей точкой: float, double, а также ряд типов, специфичных для конкретной платформы (например, x86_fp80).
• void — пустое значение.
  

Производные типы:

• Указатели
  

  тип*<br/> i32* ; указатель на 32-битное целое<br/>

• Массивы
  

  [число элементов x тип]<br/> [10 x i32]<br/> [8 x double]<br/>

• Структуры
  

  { i32, i32, double }

• Вектор — специальный тип для упрощения SIMD-операций. Вектор состоит из 2ⁿ значений примитивного типа — целого или с плавающей точкой.
  

  < число элементов x тип ><br/> < 4 x float ><br/>

• Функции
  

  i32 (i32, i32)<br/> float ({ float, float }, { float, float })<br/>

Система типов рекурсивна, поэтому можно использовать многомерные массивы, массивы структур, указатели на структуры и функции, и т. д.

Операции

Большинство инструкций в LLVM принимают два аргумента (операнда) и возвращают одно значение (трёхадресный код). Значения определяются текстовым идентификатором. Локальные значения обозначаются префиксом %, а глобальные — @. Локальные значения также называют регистрами, а LLVM — виртуальной машиной с бесконечным числом регистров. Пример:

%sum = add i32 %n, 5<br/> %diff = sub double %a, %b<br/> %z = add <4 x float> %v1, %v2 ; поэлементное сложение<br/> %cond = icmp eq %x, %y ; Сравнение целых чисел. Результат имеет тип i1.<br/> %success = call i32 @puts(i8* %str)<br/>

Тип операндов всегда указывается явно, и однозначно определяет тип результата. Операнды арифметических инструкций должны иметь одинаковый тип, но сами инструкции «перегружены» для любых числовых типов и векторов.

Вместо утомительного перечисления инструкций (всего их 52) скажем, что LLVM поддерживает полный набор арифметических операций, побитовых логических операций и операций сдвига, а также специальные инструкции для работы с векторами.

LLVM IR строго типизирован, поэтому не обойтись без приведений типов, которые явно кодируются специальными инструкциями. Набор из 9 инструкций покрывает всевозможные приведения между различными числовыми типами: целыми и с плавающей точкой, со знаком и без, различной разрядности и пр. Кроме этого есть инструкции преобразования между целыми и указателями, а так же инструкция bitcast, которая приведёт всё ко всему, но за результат вы отвечаете сами.

Теперь должно быть понятно, как компилировать в LLVM простые выражения: каждый узел дерева выражения кроме листьев (констант и переменных) заменяется промежуточным значением-регистром — результатом инструкции, операндами которой являются дочерние узлы.

; x = (a + b) * c - d / e <br/> %tmp1 = add float %a, %b <br/> %tmp2 = mul float %tmp1, %c <br/> %tmp3 = fdiv float %d, %e <br/> %x = sub float %tmp2, %tmp3 <br/>

Забегая вперёд, за пределы этой статьи, заметим, что при использовании LLVM API для генерации кода всё становится ещё проще, потому что оно следует принципу «инструкция — это значение». Нам не придётся заниматься генерацией уникальных имён для промежуточных значений: функция, генерирующая инструкцию, возвращает значение (объект C++), которое может быть передано как аргумент в другие такие функции.

SSA

SSA (static single assignment form) — это такая форма промежуточного представления кода, в которой любое значение присваивается только один раз. Таким образом, нельзя написать:

%z = sum i32 %x, %y <br/> %z = sum i32 %z, 5 <br/>

Новое значение должно получить новое имя:

%z.1 = sum i32 %z, 5

Однако, спросите вы, как быть, если одна и та же переменная должна получить разные значения в зависимости от какого-то условия? Или как организовать переменную цикла?

Начнём немного издалека. Код в SSA-форме удобно рассматривать не как линейную последовательность инструкций, а как граф потока управления (control flow graph, CFG). Вершины этого графа — так называемые базовые блоки (basic blocks), содержащие последовательность инструкций, заканчивающуюся инструкцией-терминатором, явно передающей управление в другой блок. Базовые блоки в LLVM обозначаются метками, а терминаторами являются следующие инструкции:

• ret тип значение — возврат значения из функции
  
• br i1 условие, label метка_1, label метка_2 — условный переход. Например:
  

  define float @max(float %x, float %y) <br/> { <br/>     %cond = fcmp ogt float %x, %y <br/>     br i1 %cond, label %IfTrue, label %IfFalse <br/> IfTrue: <br/>     ret float %x <br/> IfFalse: <br/>     ret float %y <br/> }

  (Синтаксис определения функции, думаю, очевиден).
  Есть также форма безусловного перехода:
  

  br label метка

• switch — обобщение br, позволяет организовать таблицу переходов:
  

  switch i32 %n, label %Default, [i32 0, label %IfZero i32 5, label %IfFive]

• invoke и unwind — используются для организации исключений, в этой статье останавливаться на них мы не будем.
  
• unreachable — специальная инструкция, показывающая компилятору, что выполнение никогда не достигнет этой точки. Например, эта инструкция может быть вставлена после вызова системной функции завершения процесса.
  

Вернёмся к вопросу, как сделать переменные изменяемыми. В SSA-форме к прочим инструкциям добавляется специальная функция φ, которая возвращает одно из перечисленных значений в зависимости от того, какой блок передал управление текущему.

В LLVM этой функции соответствует инструкция phi, которая имеет следующую форму:

phi тип, [значение_1, label метка_1], ..., [значение_N, label метка_N]

В качестве примера рассмотрим функцию вычисления факториала, которую на Си можно было бы записать так:

int factorial(int n) <br/> { <br/>     int result = n; <br/>     int i; <br/>     for (i = n - 1; i > 1; --i) <br/>         result *= i; <br/>     return result; <br/> } <br/>

Примечание: блок, который начинается с входа в функцию обозначается %0.

define i32 @factorial(i32 %n) <br/> { <br/>     %i.start = sub i32 %n, 1 <br/>     br label %LoopEntry <br/> LoopEntry: <br/>     %result = phi i32 [%n, %0], [%result.next, %LoopBody] <br/>     %i = phi i32 [%i.start, %0], [%i.next, %LoopBody] <br/>     %cond = icmp sle i32 %i, 1 <br/>     br i1 %cond, label %Exit, label %LoopBody <br/> LoopBody: <br/>     %result.next = mul i32 %result, %i <br/>     %i.next = sub i32 %i, 1 <br/>     br label %LoopEntry <br/> Exit: <br/>     ret i32 %result <br/> }

Пусть вас не смущают бессмысленные на первый взгляд переходы на метку, следующую сразу за инструкцией перехода. Как мы уже сказали, базовый блок обязан заканчиваться явной передачей управления. LLVM также требует, чтобы все phi-инструкции шли в начале блока, и до них не было никаких других инструкций.
Здесь, наверное, многие воскликнут: но это же ужасно неудобно! Действительно, хотя SSA-форма позволяет производить много полезных трансформаций, непосредственно генерировать её из кода на императивном языке затруднительно, хотя есть хорошо известные алгоритмы преобразования в SSA. К счастью, при написании компилятора на основе LLVM нет никакой необходимости заниматься этим, потому что система умеет генерировать SSA самостоятельно. Как и из чего, мы сейчас узнаем.

Память

Помимо значений-регистров, в LLVM есть и работа с памятью. Значения в памяти адресуются типизированными указателями, о которых мы говорили выше. Обратиться к памяти можно только с помощью двух инструкций, названия которых говорят сами за себя: load и store. Например:

%x = load i32* %x.ptr        ; загрузили значение типа i32 по указателю %x.ptr <br/> %tmp = add i32 %x, 5         ; прибавили 5 <br/> store i32 %tmp, i32* %x.ptr  ; и положили обратно <br/>

Но чтобы пользоваться указателями, надо как-то выделять память под значения, на которые они указывают.

Инструкция malloc транслируется в вызов одноименной системной функции и выделяет память на куче, возвращая значение — указатель определенного типа. В паре с ней конечно же идёт инструкция free.

%struct.ptr = malloc { double, double } <br/> %string = malloc i8, i32 %length <br/> %array = malloc [16 x i32] <br/> free i8* %string <br/>

Официальной рекомендации не использовать инструкцию malloc нет, но разработчики признаются, что особого смысла в её существовании сейчас не имеется. Вы можете вызвать вместо неё функцию @malloc или написать свою собственную функцию-аллокатор, отвечающую каким-то особым требованиям.

А вот инструкция alloca незаменима и очень важна. Она имеет такой же формат, но выделяет память на стеке.

%x.ptr = alloca double ; %x.ptr имеет тип double* <br/> %array = alloca float, i32 8 ; %array имеет тип float*, а не [8 x float]! <br/>

Память, выделенная alloca, автоматически освобождается при выходе из функции при помощи инструкций ret или unwind.
С помощью alloca, load и store мы можем пользоваться локальными переменными так же, как и в любом императивном языке. Например, наша многострадальная функция факториала:

define i32 @factorial(i32 %n) <br/> { <br/>     %result.ptr = alloca i32     ; выделить память под result <br/>     %i.ptr = alloca i32          ; и под i <br/>     store i32 %n, i32* %result.ptr  ; инициализация result = n <br/>     %tmp1 = sub i32 %n, 1 <br/>     store i32 %tmp1, i32* %i.ptr ; i = n - 1 <br/>     br label %Loop <br/> Loop: <br/>     %i = load i32* %i.ptr        ; загружаем значение i <br/>     %cond = icmp sle i32 %i, 1   ; и проверяем условие i <= 1<br/>     br i1 %cond, label %Exit, label %LoopBody ; если да, переход к возврату значения <br/> LoopBody: <br/>     %tmp2 = load i32* %result.ptr <br/>     %tmp3 = mul i32 %tmp2, %i <br/>     store i32 %tmp3, i32* %result.ptr   ; result *= i <br/>     %i.next = sub i32 %i, 1 <br/>     store i32 %i.next, i32* %i.ptr      ; --i <br/>     br label %Loop <br/> Exit: <br/>     %result = load i32* %result.ptr <br/>     ret i32 %result ; return result <br/> } <br/>

Достаточно многословно, но скажите, где ещё кроме подобной статьи вы будете писать код на LLVM вручную? :-)
Хорошая новость в том, что из подобного кода LLVM умеет строить SSA-форму. Этот процесс называется «promote memory to register». Вот что получится из функции factorial после прохода этого алгоритма:

define i32 @factorial(i32 %n) { <br/> ; <label>:0 <br/>     %tmp1 = sub i32 %n, 1 <br/>     br label %Loop <br/> Loop: <br/>     %i.ptr.0 = phi i32 [ %tmp1, %0 ], [ %i.next, %LoopBody ] <br/>     %result.ptr.0 = phi i32 [ %n, %0 ], [ %tmp3, %LoopBody ] <br/>     %cond = icmp sle i32 %i.ptr.0, 1 <br/>     br i1 %cond, label %Exit, label %LoopBody <br/> LoopBody: <br/>     %tmp3 = mul i32 %result.ptr.0, %i.ptr.0 <br/>     %i.next = sub i32 %i.ptr.0, 1 <br/>     br label %Loop <br/> Exit: <br/>     ret i32 %result.ptr.0 <br/> } <br/>

Операции с указателями

Массивы в LLVM очень похожи на таковые в Си, но адресной арифметики, как в Си, нет. То есть нельзя написать:

%ptr = add i32* %array, i32 %index

Для вычисления адресов элементов массивов, структур и т. д. с правильной типизацией есть специальная инструкция getelementptr.

%array = alloca i32, i32 %size <br/> %ptr = getelementptr i32* %array, i32 %index ; значение типа i32* <br/>

getelementptr только вычисляет адрес, но не обращается к памяти. Инструкция принимает произвольное количество индексов и может разыменовывать структуры любой вложенности. Например, из следующего кода на Си:

struct s { <br/>     int n; <br/>     char *a[4]; <br/> }; <br/> struct *s = ...; <br/> char c = s->a[2][5]; <br/>

будет сгенерирована такая последовательность инструкций:

%ptr = getelementptr { i32, [4 x i8*] }* %s, i32 1, i32 2, i32 5 <br/> %c = load i8* %ptr <br/>

Как вы заметили, индексы отсчитываются от нуля.
Есть очень похожая на getelementptr пара инструкций extractvalue и insertvalue. Они отличаются тем, что принимают не указатель на агрегатный тип данных (массив или структуру), а самое значение такого типа. extractvalue возвращает соответственное значение подэлемента, а не указатель на него, а insertvalue порождает новое значение агрегатного типа.

%n = extractvalue { i32, [4 x i8*] } %s, 0 <br/> %tmp = add i32 %n, 1 <br/> %s.1 = insertvalue { i32, [4 x i8*] } %s, i32 %tmp, 0 <br/>

Встроенные функции и аннотации

Ряд примитивов представляются в LLVM не инструкциями, а встроенными функциями (intrinsic functions). Например, некоторые математические функции: @llvm.sqrt.*, @llvm.sin.* и т. д. Есть также примитивы для атомарных операций и некоторые другие.

Интересно то, что вызовы этих функций в промежуточном коде вовсе не обязаны превращаться в вызовы функций в машинном коде, или даже в инлайн-подстановки функций. Они могут просто нести служебную информацию для какой-то подсистемы компилятора. Например, так организована генерация отладочной информации в формате DWARF: в IR вставляются вызовы функций %llvm.dbg.stoppoint (задаёт соответствие между строками исходного кода и генерируемым кодом), %llvm.dbg.declare (задаёт описание локальной переменной) и др., в качестве аргументов которым передаются указатели на специальные структуры.

Аналогичным образом реализована поддержка сборки мусора. LLVM не содержит какого-либо алгоритма сборки мусора, вместо этого предоставляя интерфейс для написания собственного точного GC. Примитивы @llvm.gcroot, @llvm.gcread и @llvm.gc.write позволяют закодировать информацию, необходимую для работы GC, а интерфейс плагина к компилятору LLVM — сгенерировать по этой информации нужные структуры данных и вставить обращения к рантайму.

Что умеет оптимизатор LLVM

Просто перечислим часть алгоритмов. Все они платформо-независимы и преобразуют IR. Проходы оптимизатора могут быть вызваны независимо в нужном порядке.

• Удаление неиспользуемого кода (dead code elimination).
  
• Выделение одинаковых подвыражений (common subexpression elimination).
  
• Распространение констант (constant propagation, condition propagation).
  
• Инлайн-подстановка функций.
  
• Разворот хвостовой рекурсии. LLVM также умеет в некоторых случаях разворачивать не хвостовые рекурсивные вызовы за счёт ввода дополнительной переменной-аккумулятора, как это зачастую делают в функциональных языках. Например, в этой функции рекурсивный вызов будет успешно заменён условным переходом.
  

  int factorial(int n) <br/> { <br/>     if (n < 2) return 1; <br/>     return n * factorial(n - 1); <br/> } <br/>

• Раскрутка и размыкание циклов, вынос инвариантов за пределы цикла.
  

Преобразование может быть не только оптимизирующим, но и использоваться для анализа и инструментации. Например, LLVM может генерировать CFG в формате Graphviz.

Вместо заключения

Из этого краткого обзора видно, что промежуточное представление LLVM достаточно близко соответствует коду на низкоуровневых процедурных языках вроде Си. Транслятор Си на основе LLVM будет достаточно прост и прямолинеен, но при этом сгенерированный им машинный код по производительности сможет тягаться с последними версиями GCC.

При трансляции высокоуровневых языков — объектно-ориентированных, функциональных, динамических — придётся выполнить гораздо больше промежуточных преобразований, а также написать специализированный рантайм. Но и в этом случае LLVM снимает с разработчика компилятора проблемы кодогенерации для конкретной платформы, берёт на себя большинство независимых от языка оптимизаций — и делает их качественно. Помимо этого, мы получаем готовую инфраструктуру для JIT-компиляции и возможность link-time оптимизации между различными языками, компилируемыми в LLVM.

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

Полноценный фронтенд на сегодняшний день существуют только для C, C++, Ada и Fortran — это llvm-gcc. Идёт работа по созданию независимого от GCC компилятора C/C++ — clang. Оба проекта поддерживаются основной командой LLVM.

Остальные проекты компиляторов известных языков на базе LLVM пока не достигли уровня практической применимости. Но перспективы заманчивы. Увидим ли мы компилятор современного функционального или динамического (PyPy?) языка на LLVM — покажет время.

продолжение следует…