24 февраля 2016 в 04:09

LLVM: компилятор своими руками. Введение

Представим себе, что в один прекрасный день вам пришла в голову идея процессора собственной, ни на что не похожей архитектуры, и вам очень захотелось эту идею реализовать «в железе». К счастью, в этом нет ничего невозможного. Немного верилога, и вот ваша идея реализована. Вам уже снятся прекрасные сны про то, как Intel разорилась, Microsoft спешно переписывает Windows под вашу архитектуру, а Linux-сообщество уже написало под ваш микропроцессор свежую версию системы с весьма нескучными обоями.
Однако, для всего этого не хватает одной мелочи: компилятора!
Да, я знаю, что многие не считают наличие компилятора чем-то важным, считая, что все должны программировать строго на ассемблере. Если вы тоже так считаете, я не буду с вами спорить, просто не читайте дальше.
Если вы хотите, чтобы для вашей оригинальной архитектуры был доступен хотя бы язык С, прошу под кат.
В статье будет рассматриваться применение инфраструктуры компиляторов LLVM для построения собственных решений на её основе.
Область применения LLVM не ограничивается разработкой компиляторов для новых процессоров, инфраструктура компиляторов LLVM также может применяться для разработки компиляторов новых языков программирования, новых алгоритмов оптимизации и специфических инструментов статического анализа программного кода (поиск ошибок, сбор статистики и т.п.).
Например, вы можете использовать какой-то стандартный процессор (например, ARM) в сочетании с специализированным сопроцессором (например, матричный FPU), в этом случае вам может понадобиться модифицировать существующий компилятор для ARM так, чтобы он мог генерировать код для вашего FPU.
Также интересным применением LLVM может быть генерация исходных текстов на языке высокого уровня («перевод» с одного языка на другой). Например, можно написать генератор кода на Verilog по исходному коду на С.



КДПВ


Почему LLVM?


На сегодняшний день существует только два реалистичных пути разработки компилятора для собственной архитектуры: использование GCC либо использование LLVM. Другие проекты компиляторов с открытым исходным кодом либо не достигли той степени развития, как GCC и LLVM, либо устарели и перестали развиваться, они не обладают развитыми алгоритмами оптимизации, и могут не обеспечивать полной совместимости даже со стандартом языка С, не говоря уже о поддержке других языков программирования. Разработка собственного компилятора “с нуля", это весьма нерациональный путь, т.к. существующие опенсорсные решения уже реализуют фронтенд компилятора с множеством весьма нетривиальных алгоритмов оптимизации, которые, к тому же, хорошо протестированы и используются уже длительное время.
Какой из этих двух open-source проектов выбрать в качестве основы для своего компилятора? GCC (GNU Compiler Collection) является более старым проектом, первый релиз которого состоялся в 1987 году, его автором является Ричард Столлман, известный деятель open-source движения [4]. Он поддерживает множество языков программирования: C, C++, Objective C, Fortran, Java, Ada, Go. Также существуют фронтенды для многих других языков программирования, не включенных в основную сборку. Компилятор GCC поддерживает большое количество процессорных архитектур и операционных систем, и является в настоящее время наиболее распространённым компилятором. Сам GCC написан на языке С (в комментариях меня поправили, что он уже по большей части переписан на С++).
LLVM гораздо «моложе», его первый релиз состоялся в 2003 году, он (а точнее, его фронтенд Clang) поддерживает языки программирования C, C++, Objective-C and Objective-C++, и также имеет фронтенды для языков Common Lisp, ActionScript, Ada, D, Fortran, OpenGL Shading Language, Go, Haskell, Java bytecode, Julia, Swift, Python, Ruby, Rust, Scala, C# и Lua. Он разработан в университете Иллинойса, в США, и является основным компилятором для разработки под операционную систему OS X. LLVM написан на языке С++ (С++11 для последних релизов) [5].

Относительная «молодость» LLVM не является недостатком, он достаточно зрелый, чтобы в нём не было критических багов, и при этом он не несёт в себе огромного груза устаревших архитектурных решений, как GCC. Модульная структура компилятора позволяет использовать фронтенд LLVM-GCC, который обеспечивает полную поддержку стандартов GCC, при этом генерация кода целевой платформы будет осуществляться LLC (бэкенд LLVM). Также можно использовать Clang — оригинальный фронтенд LLVM.
LLVM хорошо документирован, и для него большое количество примеров кода.

Модульная архитектура компилятора


Инфраструктура компиляторов LLVM состоит из различных инструментов, рассматривать их все в рамках данной статьи не имеет смысла. Ограничимся основными инструментами, которые образуют как таковой компилятор.
Компилятор LLVM, как и некоторые другие компиляторы, состоит из фронтенда, оптимизатора (миддленда), и бэкенда. Такая структура позволяет разделить разработку компилятора нового языка программирования, разработку методов оптимизации и разработку кодогенератора для конкретного процессора (такие компиляторы называют «перенацеливаемыми», retargetable).
Связующим звеном между ними является промежуточный язык LLVM, ассемблер «виртуальной машины». Фронтенд (например, Clang) преобразует текст программы на языке высокого уровня в текст на промежуточном языке, оптимизатор (opt) производит над ним различные оптимизации, а бэкенд (llc) генерирует код целевого процессора (на ассемблере или непосредственно в виде бинарного файла). Помимо этого, LLVM может работать в режиме JIT (just-in-time) компиляции, когда компиляция происходит непосредственно во время исполнения программы.
Промежуточное представление программы может быть как в виде текстового файла на языке ассемблера LLVM, так и в виде двоичного формата, «биткода». По умолчанию clang генерирует именно биткод (файл .bc), но для отладки и изучения LLVM нам нужно будет генерировать текстовое промежуточное представление на ассемблере LLVM (он также называется IR-кодом, от слов Intermediate Representation, промежуточное представление).


Рис. 1. Модульная архитектура компилятора

Кроме вышеперечисленных программ, LLVM включает в себя и другие утилиты [6].
Итак, напишем простейшую программу на C.
int foo(int x, int y) {
  return x + y;
}

И скомпилируем её:
clang-3.5 -c add.c -O0 --target=xcore -emit-llvm -S -o add_o0.ll

Некоторые пояснения:
-c add.c — входной файл;
-O0 — уровень оптимизации 0, оптимизация отсутствует;
--target=xcore — ядро процессора xcore не имеет каких-либо сложных особенностей при компиляции в IR-код, поэтому является идеальным объектом для исследований. Это ядро имеет разрядность 32, и clang выравнивает все переменные по границам 32-битных слов;
-emit-llvm -S — указание clang-у сгенерировать файл llvm в текстовом виде (на ассемблере LLVM);
-o add_o0.ll — выходной файл
Посмотрим на результат:
; ModuleID = 'add.c'
target datalayout = "e-m:e-p:32:32-i1:8:32-i8:8:32-i16:16:32-i64:32-f64:32-a:0:32-n32"
target triple = "xcore"

; Function Attrs: nounwind
define i32 @foo(i32 %x, i32 %y) #0 {
%1 = alloca i32, align 4
%2 = alloca i32, align 4
store i32 %x, i32* %1, align 4
store i32 %y, i32* %2, align 4
%3 = load i32* %1, align 4
%4 = load i32* %2, align 4
%5 = add nsw i32 %3, %4
ret i32 %5
}

attributes #0 = { nounwind "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.ident = !{!0}
!xcore.typestrings = !{!1}

!0 = metadata !{metadata !"Ubuntu clang version 3.5.0-4ubuntu2~trusty2 (tags/RELEASE_350/final) (based on LLVM 3.5.0)"}
!1 = metadata !{i32 (i32, i32)* @foo, metadata !"f{si}(si,si)"}

Выглядит довольно сложно, не так ли? Однако давайте разберёмся, что тут написано. Итак:
target datalayout = «e-m:e-p:32:32-i1:8:32-i8:8:32-i16:16:32-i64:32-f64:32-a:0:32-n32»
описание разрядности переменных и самых основных особенностей архитектуры. e- little-endian архитектура. Для big-endian здесь была бы буква E. m:e — mangling, соглашение о преобразовании имён. Нам пока это не понадобится. p:32:32 — указатели имеют 32 бита и выровнены по границам 32-битных слов. i1:8:32 — булевые переменные (i1) выражаются 8-ибитными значениями и выровнены по границам 32-битных слов. Далее аналогично для целочисленных переменных i8 — i64 (от 8 до 64 бит соответственно), и f64 — для вещественных переменных двойной точности. a:0:32 — агрегатные переменные (т.е. массивы и структуры) имеют выравнивание 32 бита, n32 — разрядность чисел, обрабатываемых АЛУ процессора (native integer width).
Далее следует название таргета (т.е. целевого процессора): target triple = «xcore». Хотя код IR часто называют «машинно-независимым», на самом деле мы видим, это не так. Он отражает некоторые особенности целевой архитектуры. Это является одной из причин, по которой мы должны указывать целевую архитектуру не только для бэкенда, но и для фронтенда.
Далее следует код функции foo:
define i32 @foo(i32 %x, i32 %y) #0 {
%1 = alloca i32, align 4
%2 = alloca i32, align 4
store i32 %x, i32* %1, align 4
store i32 %y, i32* %2, align 4
%3 = load i32* %1, align 4
%4 = load i32* %2, align 4
%5 = add nsw i32 %3, %4
ret i32 %5
}

Код довольно громоздкий, хотя исходная функция очень проста. Вот что он делает.
Сразу отметим, что все имена переменных в LLVM имеют префикс либо % (для локальных переменных), либо @ — для глобальных. В данном примере все переменные локальные.
%1 = alloca i32, align 4 — выделяет на стеке 4 байта для переменной, указателем на эту область является указатель %1.
store i32 %x, i32* %1, align 4 — копирует в выделенную область один из аргументов функции (%x).
%3 = load i32* %1, align 4 — извлекает значение в переменную %3. Теперь в %3 хранится локальная копия %x.
Делает то же самое для аргумента %y
%5 = add nsw i32 %3, %4 — складывает локальные копии %x и %y, помещает результат в %5. Есть ещё атрибут nsw, но он пока для нас не важен.
Возвращает значение %5.
Из приведённого примера видно, что при нулевом уровне оптимизации clang генерирует код, буквально следуя исходному коду, создаёт локальные копии всех аргументов и не делает каких-либо попыток удалить избыточные команды. Это может показаться плохим свойством компилятора, но на самом деле это очень полезная особенность при отладке программ и при отладке кода самого компилятора.
Посмотрим, что произойдёт, если поменять уровень оптимизации на O1:
define i32 @foo(i32 %x, i32 %y) #0 {
%1 = add nsw i32 %y, %x
ret i32 %1
}

Мы видим, что ни одной лишней команды не осталось. Теперь программа складывает непосредственно аргументы функции и возвращает результат.
Есть и более высокие уровни оптимизации, но в этом конкретном случае они не дадут лучшего результата, т.к. максимальный уровень оптимизации уже достигнут.
Остальная часть LLVM-кода (атрибуты, метаданные), несёт в себе служебную информацию, которая пока нам неинтересна.

Структура кода LLVM


Структура кода LLVM очень проста. Код программы состоит из модулей, компилятор обрабатывает по одному модулю за раз. В модуле есть глобальные объявления (переменные, константы и объявления заголовков функций, находящихся в других модулях) и функции. Функции имеют аргументы и возвращаемые типы. Функции состоят из базовых блоков. Базовый блок — это последовательность команд ассемблера LLVM, имеющая одну точку входа и одну точку выхода. Базовый блок не содержит внутри себя никаких ветвлений и циклов, он выполняется строго последовательно от начала до конца и должен заканчиваться терминирующей командой (возвратом из функции или переходом на другой блок).
И, наконец, базовый блок состоит из команд ассемблера. Список команд приведён в документации на LLVM [7].
Итак, ещё раз: базовый блок имеет одну точку входа, помеченную меткой, и обязательно должен заканчиваться командой безусловного перехода br или командой возврата ret. Перед ними может быть команда условного перехода, в этом случае она должна быть непосредственно перед терминирующей командой. Базовый блок имеет список predecessors — базовых блоков, из которых управление может приходить на него, и successors — базовых блоков, которым он может передавать управление. На основе этой информации строится CFG — Control Flow Graph, граф потока управления, важнейшая структура, представляющая программу в компиляторе.
Рассмотрим тестовый пример на языке С:
Пусть исходный код на языке С имеет цикл:
//функция вычисляет сумму 10 элементов массива
int for_loop(int x[]) {
  int sum = 0;
  for(int i = 0; i < 10; ++i) {
    sum += x[i];
  }
  return sum;
}

Его CFG имеет вид:

Ещё одним видом графов в LLVM является DAG — directed acyclic graph, направленный ациклический граф, представляющий собой базовый блок.
Он представляет команды ассемблера и зависимости между ними. На рисунке ниже приведён DAG базового блока, представляющий тело цикла в примере выше, при уровне оптимизации -O1:


SSA-форма


Ключевой особенностью IR-кода, отличающей его от языков высокого уровня является то, что он представлен в так называемой SSA-форме (Static Single Assignment form). Эта особенность очень важна для понимания при разработке компилятора на платформе LLVM, поэтому уделим ей некоторое внимание. Если формулировать кратко, то в SSA-форме каждой переменной значение присваивается ровно один раз и только в одной точке программы. Все алгоритмы оптимизации и преобразования IR-кода работают только с такой формой.
Однако, как преобразовать обычную программу на языке высокого уровня в такую форму? Ведь в обычных языках программирования значение переменной может присваиваться несколько раз в разных местах программы, или, например, в цикле.
Для реализации такого поведения программы используется один из двух приемов. Первый прием заключается в использовании пар команд load/store, как в вышеприведённом коде. Ограничение единственного присваивания распространяется только на именованные переменные LLVM, и не распространяется на ячейки памяти, на которые ссылаются указатели. То есть, можно неограниченное количество раз производить запись в ячейку памяти командой store, и формальное правило SSA будет соблюдено, так как указатель на эту ячейку не меняется. Этот способ используется обычно при уровне оптимизации -O0, и мы не будем на нём подробно останавливаться. Второй прием использует φ-функции, ещё одну интересную концепцию IR-кода.

Код в SSA-форме: load/store


Воспользуемся тестовым примером из предыдущего раздела.
Скомпилируем с уровнем оптимизации -O0:
define i32 @for_loop(i32* %x) #0 {
%1 = alloca i32*, align 4
%sum = alloca i32, align 4
%i = alloca i32, align 4
store i32* %x, i32** %1, align 4
store i32 0, i32* %sum, align 4
store i32 0, i32* %i, align 4
br label %2

; :2 ; preds = %12, %0
%3 = load i32* %i, align 4
%4 = icmp slt i32 %3, 10
br i1 %4, label %5, label %15

; :5 ; preds = %2
%6 = load i32* %i, align 4
%7 = load i32** %1, align 4
%8 = getelementptr inbounds i32* %7, i32 %6
%9 = load i32* %8, align 4
%10 = load i32* %sum, align 4
%11 = add nsw i32 %10, %9
store i32 %11, i32* %sum, align 4
br label %12

; :12 ; preds = %5
%13 = load i32* %i, align 4
%14 = add nsw i32 %13, 1
store i32 %14, i32* %i, align 4
br label %2

; :15 ; preds = %2
%16 = load i32* %sum, align 4
ret i32 %16
}

Здесь мы видим то, о чем было написано выше: переменная цикла, это просто ячейка памяти, на которую ссылается указатель %i.

Код в SSA-форме: φ-функции


Теперь попробуем уровень оптимизации O1:
define i32 @for_loop(i32* nocapture readonly %x) #0 {
br label %1

; :1 ; preds = %1, %0
%i.02 = phi i32 [ 0, %0 ], [ %5, %1 ]
%sum.01 = phi i32 [ 0, %0 ], [ %4, %1 ]
%2 = getelementptr inbounds i32* %x, i32 %i.02
%3 = load i32* %2, align 4, !tbaa !2
%4 = add nsw i32 %3, %sum.01
%5 = add nsw i32 %i.02, 1
%exitcond = icmp eq i32 %5, 10
br i1 %exitcond, label %6, label %1

; :6 ; preds = %1
ret i32 %4
}

Здесь мы видим, что переменной цикла является %i.02 (имена переменных в LLVM могут содержать точки), и это не указатель, а обычная 32-битная переменная, а присваивание значения происходит с помощью функции phi i32 [ 0, %0 ], [ %5, %1 ]. Это означает, что функция примет значение 0, если переход произошёл с базового блока %0 (первый базовый блок в функции), и значение переменной %5, если переход произошёл с базового блока %1 (т.е. с выходной точки этого же базового блока). Таким образом, генератор IR-кода избавился от двух присваиваний переменной, строго следуя формальным правилам SSA. Далее видно, что сходным образом происходит присваивание переменной %sum.01.
Итак, смысл φ-функции состоит в том, что её значение зависит от того, из какого базового блока был произведён переход на неё. φ-функции могут находиться только в начале базового блока. Если их несколько, они должны следовать непрерывно, начиная с первой инструкции базового блока.

Moar optimization!


Что будет при уровне оптимизации -O2?
define i32 @for_loop(i32* nocapture readonly %x) #0 {
%1 = load i32* %x, align 4, !tbaa !2
%2 = getelementptr inbounds i32* %x, i32 1
%3 = load i32* %2, align 4, !tbaa !2
%4 = add nsw i32 %3, %1
%5 = getelementptr inbounds i32* %x, i32 2
%6 = load i32* %5, align 4, !tbaa !2
%7 = add nsw i32 %6, %4
%8 = getelementptr inbounds i32* %x, i32 3
%9 = load i32* %8, align 4, !tbaa !2
%10 = add nsw i32 %9, %7
%11 = getelementptr inbounds i32* %x, i32 4
%12 = load i32* %11, align 4, !tbaa !2
%13 = add nsw i32 %12, %10
%14 = getelementptr inbounds i32* %x, i32 5
%15 = load i32* %14, align 4, !tbaa !2
%16 = add nsw i32 %15, %13
%17 = getelementptr inbounds i32* %x, i32 6
%18 = load i32* %17, align 4, !tbaa !2
%19 = add nsw i32 %18, %16
%20 = getelementptr inbounds i32* %x, i32 7
%21 = load i32* %20, align 4, !tbaa !2
%22 = add nsw i32 %21, %19
%23 = getelementptr inbounds i32* %x, i32 8
%24 = load i32* %23, align 4, !tbaa !2
%25 = add nsw i32 %24, %22
%26 = getelementptr inbounds i32* %x, i32 9
%27 = load i32* %26, align 4, !tbaa !2
%28 = add nsw i32 %27, %25
ret i32 %28
}

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

Компоновка IR-кода


Реальные программы состоят не из одного модуля. Традиционный компилятор компилирует модули по отдельности, превращая их в объектные файлы, а затем передаёт их компоновщику (линкеру), который объединяет их в один исполняемый файл. LLVM тоже позволяет так делать.
Но LLVM имеет также возможность компоновки IR-кода. Проще всего рассмотреть это на примере. Пусть есть два исходных модуля: foo.c и bar.c:
//bar.h
#ifndef BAR_H
#define BAR_H
int bar(int x, int k);
#endif

//bar.c
int bar(int x, int k) {
  return x * x * k;
}

//foo.c
#include "bar.h"
int foo(int x, int y) {
  return bar(x, 2) + bar(y, 3);
}

Если программа будет скомпилирована «традиционным» образом, то оптимизатор не сможет сделать с ней практически ничего: при компиляции foo.c компилятор не знает, что находится внутри функции bar, и может поступить единственным очевидным способом, вставить вызовы bar().
Но если мы скомпонуем IR-код, то мы получим один модуль, который после оптимизации с уровнем -O2 будет выглядеть так (для ясности заголовок модуля и метаданные опущены):
define i32 @foo(i32 %x, i32 %y) #0 {
%1 = shl i32 %x, 1
%2 = mul i32 %1, %x
%3 = mul i32 %y, 3
%4 = mul i32 %3, %y
%5 = add nsw i32 %4, %2
ret i32 %5
}

; Function Attrs: nounwind readnone
define i32 @bar(i32 %x, i32 %k) #0 {
%1 = mul nsw i32 %x, %x
%2 = mul nsw i32 %1, %k
ret i32 %2
}

Здесь видно, что в функции foo не происходит никаких вызовов, компилятор перенёс в неё содержимое bar() полностью, попутно подставив константные значения k. Хотя функция bar() осталась в модуле, она будет исключена при компиляции исполняемого файла, при условии, что она не вызывается нигде больше в программе.
Нужно отметить, что в GCC также есть возможность компоновки и оптимизации промежуточного кода (LTO, link-time optimization) [6].
Разумеется, оптимизация в LLVM не исчерпывается оптимизацией IR-кода. Внутри бэкенда также происходят различные оптимизации на разных стадиях преобразования IR-кода в машинное представление. Часть таких оптимизаций LLVM производит самостоятельно, но разработчик бэкенда может (и должен) разработать собственные алгоритмы оптимизации, которые позволят в полной мере использовать особенности архитектуры процессора.

Генерация кода целевой платформы


Разработка компилятора для оригинальной архитектуры процессора, это, в основном, разработка бэкенда. Вмешательство в алгоритмы фронтенда, как правило, не является необходимым, или, во всяком случае, требует весьма веских оснований. Если проанализировать исходный код Clang, можно увидеть, что большая часть «особенных» алгоритмов приходится на процессоры x86 и PowerPC с их нестандартными форматами вещественных чисел. Для большинства других процессоров нужно указать только размеры базовых типов и endianness (big-endian или little-endian). Чаще всего можно просто найти аналогичный (в плане разрядности) процессор среди множества поддерживаемых.
Генерация кода для целевой платформы происходит в бэкенде LLVM, LLC. LLC поддерживает множество различных процессоров, и вы можете на его основе сделать генератор кода для вашего собственного оригинального процессора. Эта задача упрощается ещё и благодаря тому, что весь исходный код, включая модули для каждой поддерживаемой архитектуры, полностью открыт и доступен для изучения.
Именно генератор кода для целевой платформы (таргета) является наиболее трудоёмкой задачей при разработке компилятора на основе инфрастуктуры LLVM. Я решил не останавливаться подробно здесь на особенностях реализации бэкенда, так как они существенным образом зависят от архитектуры целевого процессора. Впрочем, если у уважаемой аудитории хабра возникнет интерес к данной теме, я готов описать ключевые моменты разработки бэкенда в следующей статье.

Заключение


В рамках небольшой статьи нельзя рассмотреть подробно ни архитектуру LLVM, ни синтаксис языка LLVM IR, ни процесс разработки бэкенда. Однако эти вопросы подробно освещаются в документации. Автор скорее старался дать общее представление об инфраструктуре компиляторов LLVM, сделав упор на то, что эта платформа является современной, мощной, универсальной, и независимой ни от входного языка, ни от целевой архитектуры процессора, позволяя реализовать и то, и другое по желанию разработчика.
Помимо рассмотренных, LLVM содержит и другие утилиты, однако их рассмотрение выходит за рамки статьи.
LLVM позволяет реализовать бэкенд для любой архитектуры (см. примечание), включая архитектуры с конвейеризацией, с внеочередным выполнением команд, с различными вариантами параллелизации, VLIW, для классических и стековых архитектур, в общем, для любых вариантов.
Вне зависимости от того, насколько нестандартные решения лежат в основе процессорной архитектуры, это всего лишь вопрос написания большего или меньшего объёма кода.
примечание
для любой, в пределах разумного. Вряд ли возможно реализовать компилятор языка С для 4-хбитной архитектуры, т.к. стандарт языка явно требует, чтобы разрядность была не меньше 8.


Литература



Компиляторы
[1] Книга дракона
[2] Вирт Н. Построение компиляторов
GCC
[3] gcc.gnu.org — сайт проекта GCC
[4] Richard M. Stallman and the GCC Developer Community. GNU Compiler Collection Internals
LLVM
[5] http://llvm.org/ — сайт проекта LLVM
[6] http://llvm.org/docs/GettingStarted.html Getting Started with the LLVM System
[7] http://llvm.org/docs/LangRef.html LLVM Language Reference Manual
[8] http://llvm.org/docs/WritingAnLLVMBackend.html Writing An LLVM Backend
[9] http://llvm.org/docs/WritingAnLLVMPass.html Writing An LLVM Pass
[10] Chen Chung-Shu. Creating an LLVM Backend for the Cpu0 Architecture
[11] Mayur Pandey, Suyog Sarda. LLVM Cookbook
[12] Bruno Cardoso Lopes. Getting Started with LLVM Core Libraries
[13] Suyog Sarda, Mayur Pandey. LLVM Essentials
Автор будет рад ответить на ваши вопросы в комментариях и в личке.
Просьба обо всех замеченных опечатках сообщать в личку. Заранее спасибо.
Владимир @32bit_me
карма
110,0
рейтинг 0,0
Программист
Похожие публикации
Самое читаемое Разработка

Комментарии (55)

  • +4
    Спасибо за статью. Стало действительно немного понятнее, как это работает.
  • +6
    Хорошо, что все больше статей по LLVM появляется на русском языке, спасибо.

    В качестве дополнительных материалов могу предложить послушать мой доклад на прошедшей конференции C++ Siberia.

    А еще, буквально в эту пятницу я буду читать доклад на конференции в Санкт-Петербурге об LLVM и проблемах алиасинга. Будет рассказано о технике Alias Analysis, преимуществах, недостатках и о том, как оно применяется в современных компиляторах.
    • 0
      Спасибо, послушаю.
      Проблемы алиасинга, даже не слышал, если честно. Буду рад узнать, что это такое.
  • +4
    Ещё пример использования llvm как независимого от входного языка — это LabVIEW. Начиная с версии 2010 они используют именно llvm. Там графическая блок-диаграмма представляется как DFIR (dataflow intermediate representation) граф, который транслируется в llvm IR код. Это даёт возможность иметь компилируемый графический язык, при этом платформонезависимый — это работает не только в windows, но и на линуксе и на маке.
    Вот тут можно чуть-чуть почитать: The LabVIEW Compiler — Under the Hood
    Ну ещё любопытно обратить внимание на то, где llvm используется: LLVM Users
    • +1
      Вот это интересно, не знал.
    • НЛО прилетело и опубликовало эту надпись здесь
      • 0
        Хорошие курсовые, у нас таких не было. Трансляция из блок-схемы в С, это же очень полезная вещь для различных визуальных сред разработки. Программируемые логические контроллеры так и программируются, в целом, например IsaGraf перегоняет разные блоковые диаграммы в С, потом компилирует обычным компилятором, чуть ли не Turbo C.
  • +1
    Хорошая статья! Спасибо :)
  • +2
    Маленькое замечание: "Сам GCC написан на языке С."

    GCC начали переписывать на C++ в 2012 году, а на текущий момент бОльшая его часть уже на C++.
    • 0
      Спасибо, внёс дополнение в текст.
  • +2
    Отличная статья! Требую продолжения!
    Вряд ли возможно реализовать компилятор языка С для 4-хбитной архитектуры
    То есть, для Z80 можно?
    • +1
      Да, и даже такие проекты существуют. Не знаю, насколько они закончены и сколько там багов, но на гитхабе я видел.
    • +1
      Даже целых три штуки: https://github.com/search?utf8=%E2%9C%93&q=llvm+z80
  • 0
    Как раз хотел разработать свой процессор! :-)
    Но возникла проблема — в нем не предусмотренно обращения к памяти по указателю, только по индексу в массиве.
    Если я не ошибаюсь, обращения по индексу в LLVM не сделано отдельной операцией, а транслируется в получение указателя и обращение по нему. Можно ли это как-то обойти?
    • 0
      Вы именно ошибаетесь.
      Для обращения по индексу в LLVM служит инструкция getelementptr, которая возвращает указатель, получая в качестве аргументов базовый указатель и индексы.
      В обычных случаях она преобразуется в сложения и умножения очевидным образом, но при желании её можно обработать как угодно.
      • 0
        Именно. А для моей архитектуры я не могу реализовать getelementptr, там просто нет такого понятия, как указатель. Потучается, что LLVM для нее нельзя реализовать, хотя бы частично (для программ, которые явно не используют указателей).
        • 0
          Ну хорошо, а каким образом в вашей архитектуре происходит доступ к элементу массива?
          Не нужно также забывать, что в языке С указатели не просто есть, они составляют основу языка, и с этим придётся смириться.
          • 0
            Примерно как в i*86 к сегментам (точнее, как в i432 к полям объекта) — по индексному регистру и фиксированному смещению или целочисленному регистру.
            Я готов смириться, что значитальная чаcть C/C++ программ не ней не пойдут. Но LLVM — это еще и Rust, и еще куча приятных языков, для реализации которых на этой архитектуре особых проблем нет.
            • 0
              То есть индексный регистр + смещение = адрес ячейки, я правильно понял?
              Никаких проблем здесь нет. Аргументы инструкции getelementptr можно привести к такому виду без особых проблем. Они как бы к такому виду и приводятся обычно, т. к. в большинстве стандартных архитектур адрес и задаётся как индексный регистр+ смещение.
              Я не знаю Rust, увы, может быть, там не указателей с точки зрения пользователя, но на всякий случай попробуйте скомпилировать какую-либо тестовую программу в LLVM IR. Что-то мне подсказывает, что там будут и указатели, и всё вот это.
              • 0
                На уровне системы команд там вообще нет понятия адреса. Индексные регистры получают значение только в результате операций аллокации, вызова подпрограммы (аллокация аналога фрейма стека), получения подобъекта другого объекта или чтения индексной части объекта в памяти.
                Можно эмулировать указатель объектом с одним индексным полем и одним целочисленным. Но боюсь это будет сложно в реализации и плохо поддаваться оптимизации.
                • 0
                  Я всё равно не понимаю, чем это отличается от стандарной схемы.
                  Например, код на с:

                  //сумма эл-тов массива
                  int foo(int arr[10]) {
                    int sum = 0;
                    for(int i = 0; i < 10; ++i) {
                      sum += arr[i];
                    }
                    return sum;
                  }

                  Код на LLVM IR: (служебная информация опущена)
                  `
                  entry:
                  br label %for.body

                  for.cond.cleanup:; preds = %for.body
                  ret i32 %add

                  for.body:; preds = %for.body, %entry
                  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
                  %sum.06 = phi i32 [ 0, %entry ], [ %add, %for.body ]
                  %arrayidx = getelementptr inbounds i32, i32 %arr, i64 %indvars.iv
                  %0 = load i32, i32
                  %arrayidx, align 4, !tbaa !1
                  %add = add nsw i32 %0, %sum.06
                  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
                  %exitcond = icmp eq i64 %indvars.iv.next, 10
                  br i1 %exitcond, label %for.cond.cleanup, label %for.body
                  }
                  Видно, что доступ к элементам массива происходит через gelelementptr/load Код на асме ARM:
                  foo: # foo

                  BB#0: # %entry
                  mov r2, 0
                  mov r3, 0

                  LBB0_1: # %for.body

                  =>This Inner Loop Header: Depth=1
                  mov r4, r1
                  add r4, r2
                  ldw r0, 0(r4)
                  add r0, r3
                  addi    r2, 4
                  mov r3, r0
                  jeqi    r2, 40 goto LBB0_2
                  jmp LBB0_1

                  LBB0_2: # %for.cond.cleanup
                  ret
                  `

                  Доступ к элементам массива происходит через индексный регистр r4. Никаких проблем нет.

                  (парсер хабра что-то чудит с разметкой, но вроде всё понятно)
                  • 0
                    (1) %arrayidx = getelementptr inbounds i32, i32 %arr, i64 %indvars.iv
                    (2) %0 = load i32, i32 %arrayidx, align 4, !tbaa !1

                    Что бы откомпилировать команду (2), мне надо разобрать на части команду (1). Без (1) это сделать невозможно.
                    Хотя, благодаря SSA, скорее всего команду getelementptr всегда можно найти.
                    Надо подумать в эту сторону.
                    • 0
                      Разберите сразу обе команды, например.
                      • 0
                        Они могут быть разнесены оптимизатором далеко друг от друга. Да и на одну getelementptr может приходится несколько load/store. Так что вся надежда на SSA.
                        • 0
                          Ну не знаю, я особых сложностей не вижу, если честно.
                • 0
                  В конечном итоге, если в вашем процессоре доступ к элементу массива вообще как-то осуществляется, т.е сущ-вует соответствующая последовательность команд, вы можете просто вручную (в смысле, своим кастомным кодом) заменять пару getelementptr/load этой последовательностью.
  • 0
    каждой переменной значение присваивается ровно один раз и только в одной точке программы.
    Напомнило Erlang — там переменные присваиваются тоже только один раз.
  • +1
    Посмотреть и сравнить выхлоп ассемблера для gcc, clang-llvm разных версий можно на https://gcc.godbolt.org/
  • 0
    Знакомился с LLVM и не нашёл, как можно изменить содержимое указателя стека. В x86 можно написать так: «xchg esp,other_stack». А как сделать что-то подобное на LLVM? Заранее спасибо.
    • 0
      Не совсем уловил суть вопроса. У вас есть какой-то процессор, в нём есть регистр указателя стека, и есть команды, которые изменяют его содержимое. Вы разрабатываете для этого процессора бэкенд LLVM. В нём вы можете генерировать нужные вам команды, для этого есть множество способов.
      А в самом по себе LLVM никакого указателя стека нет.
  • 0
    У меня есть обычный процессор x86. Если я пишу компилятор и желаю переключаться между стеками, то какой код генерировать для этого: машинный код х86 или же LLVM, в котором всё таки есть что-то похожее на «xchg esp,other_stack», но которое я не увидел?
    • 0
      Если я вас правильно понял, то под написанием компилятора вы подразумеваете генерацию машинного кода x86 из промежуточного кода LLVM. В таком случае и генерируйте нужные вам команды для изменения стека, когда сочтете нужным. Я правда не понимаю, зачем вам это, разве то, что уже написано, вас не устраивает? Если бы вы писали под другой процессор, тогда еще понятно, но под древний, как мир, x86???
    • 0
      Промежуточный код LLVM не работает с физическими регистрами. Нужно генерировать машинную инструкцию.
  • 0
    Под компиляцией и генерацией машинного кода я имею в виду варианты:
    1) генерация напрямую: программа на языке высокого уровня -> промежуточное представление -> нативный код,
    2) генерация через LLVM: программа на языке высокого уровня -> промежуточное представление -> LLVM -> нативный код.

    Первый вариант имеет преимущества:
    1) быстрая компиляция
    2) полное и эффективное использование возможностей конкретного процессора

    Недостаток: необходимость разработки кодогенератора для каждой платформы

    Во втором варианте преимущества и недостатки зеркально меняются местами: нет быстрой компиляции, нет полного и эффективного использования возможностей конкретного процессора, но есть избавление от необходимости писать кодогенератор под каждую платформу.

    Мне интересно, насколько сильно обрезаны возможности LLVM в сравнении с традиционными ассемблерами, осталась ли там возможность изменения указатели вершины стека. Почему это интересует – написал в личном сообщении.

    Архитектура x86 – живее всех живых, сейчас она существует в своей 64-разрядной инкарнации. Когда-то в ней был регистр SP, потом ESP, теперь RSP. Ну суть осталась та же: он указывает вершину стека. А архитектуре ARM на вершину стека указывает регистр № 13. И ARM, и x86 позволяют загружать эти регистры новым содержимым, т.е. после «xchg esp,other_stack» в 32-разрядной архитектуре x86 он указывает на другое место. А вот в LLVM такой возможности не увиделось. Возможно, плохо искал. Но, может быть, её вообще нет.

    Вот в чём суть моих вопросов.
    • 0
      Это не так. Все современные компиляторы, включая LLVM, работают по варианту 1. Более точно это показано на рисунке 1.
      Далее я буду писать только про бэкенд, т.е. преобразование из промежуточного кода в код таректа.
      По поводу преимуществ:

      1. LLVM имеет возможность быстрой компиляции, в основном для работы в режиме JIT.
      2. Насколько полно и эффективно будут использованы возможности процессора, зависит только от разработчика бэкенда. LLVM не ограничивает его ни в чём.
      3. Разумеется, нужно писать кодогенератор под каждую платформу (если под кодогенератором вы понимаете бэкенд).
      4. В LLVM есть возможность генерации любых машинных инструкций.
      • 0
        Генерация кода из моего собственного промежуточного представления в нативный код быстрее, нежели из собственного промежуточного представления в промежуточное представление LLVM, из которого уже потом получается нативный код. Просто потому, что этапов меньше.

        Для полного задействования возможностей x86, в т.ч. загрузки новым значением указателя стека, нужно переписать соответствующий бэкенд? Я правильно понял? Т.е. сейчас в LLVM указатель стека не может быть загружен новым значением по ходу работы? Или я не всё понял в устройстве LLVM?
        • 0
          1. Зачем нужно собственное промежуточное представление, и генерировать из него LLVM IR? Чем вас не устраивает clang, который просто генерирует LLVM IR?

          2. нужно переписать соответствующий бэкенд?
            Вероятно, да.

          3. Т.е. сейчас в LLVM указатель стека не может быть загружен новым значением по ходу работы?
            Давайте различать LLVM и конкретный бэкенд LLVM. Я не знаю устройство именно бэкенда x86, и не знаю, как он работает со стеком.
  • 0
    Простите, личное сообщение было 32bit_me.

    Но в LLVM есть понятие стека, следовательно, стек LLVM опирается на какое-то физическое воплощение в виде регистров. Когда запускается программа, указатель стека в LLVM инициализируется каким-то значением – иначе концепция стека работать не будет. Но как это происходит? Если указатель стека приобретает своё значение в начале работы программы, то он может быть загружен новым значением по ходу её работы?
    • 0
      Но в LLVM есть понятие стека

      Нет, не так. На уровне IR (промежуточного кода) никакого стека нет, он работает только с виртуальными (не физическими) регистрами.
      Дальше генерируются другие промежуточные представления, где действительно есть стек (точнее, Frame Index, индексы в кадре стека). Их обработка и преобразование в конкретные машинные инструкции остаётся целиком за разработчиком бэкенда. При этом процессор может иметь отдельно регистр стека и регистр фрейма, или только регистр стека, например (хотя при этом будет нельзя работать со стеком, динамически изменяющим размер в run-time).
      В командах Selection DAG (которое является следующим за IR промежуточным представлением) операнды работы со стеком имеют вид, например FI+1, где FI — текущий кадр стека. Его значение не определено, команды оперируют только относительным смещением.
      Указатель стека вы можете изменять, как и любой другой физический регистр, соответствующими командами таргета.
      • 0
        На уровне IR (промежуточного кода) никакого стека нет, он работает только с виртуальными (не физическими) регистрами.

        Хотелось бы, чтобы были не только виртуальные регистры, но и виртуальный стек.

        Дальше генерируются другие промежуточные представления, где действительно есть стек (точнее, Frame Index, индексы в кадре стека)

        «Дальше» – это значит после уровня IR (промежуточного кода)? Если взглянуть на рис. 1. (модульная архитектура компилятора), то в центре стоит оптимизатор. На каком этапе существует IR и на каком появляется стек? Вроде бы выходит, что есть несколько промежуточных представлений. И какое из них всё ещё универсальное, не завязанное на конкретную архитектуру?

        В чём притягательная сила LLVM? При написании компилятора нет необходимости делать сотню бэкендов, достаточно сделать единственное преобразование в LLVM IR (это так видится!). О преобразовании в код конкретной архитектуры позаботится инфраструктура LLVM. Главное – написать правильный бит-код для LLVM IR и запустить преобразование с правильными опциями.

        Но, оказывается (такой вывод можно сделать из ваших слов), генерацию кода для целевой машины надо допиливать, сто раз для ста платформ. И в чём тогда притягательность LLVM? Для разработчиков новых архитектур она полезна: разработал свой бэкенд, и в твоём распоряжении компиляторы Си, Фортрана, Хаскелла. Но для разработчиков компиляторов новых языков – не вполне.
        • 0
          Хотелось бы, чтобы были не только виртуальные регистры, но и виртуальный стек.

          Зачем? IR обходится без этого.

          На каком этапе существует IR

          Код IR поступает в бэкенд и там преобразуется в SelectionDAG, который уже зависит от таргета. IR не зависит от таргета (если на вдаваться в тонкости).

          Притягательная сила LLVM состоит в том, чтобы сделать только то, что вам нужно, а остальное сделает LLVM. Если вы хотите сделать компилятор для нового языка программирования, то вам не нужно писать множество бэкендов, достаточно сгенерировать правильный IR-код. Если вы хотите сделать оптимизации нативного кода для конкретной архитектуры, то вам не нужно заниматься формированием IR-кода, нужно написать только бэкенд (или модифицировать существующий).
        • 0
          Если вам очень хочется изменять регистр стека из IR-кода, можно сделать ассемблерную вставку с нужной командой.
          • 0
            сделать ассемблерную вставку с нужной командой.
            Да, такой «костыль» мог бы стать решением, вот только ещё надо знать, как это сделать. На Си я это делал как раз такой вставкой. Конечно, после вставки нативного кода универсальность теряется.
            Если вы хотите сделать оптимизации нативного кода для конкретной архитектуры, то вам не нужно заниматься формированием IR-кода, нужно написать только бэкенд (или модифицировать существующий).
            Вероятно, надо модифицировать существующий бэкенд, но потом из IR-кода надо ещё как-то воспользоваться этой модификацией. Короче, надо изучать и вникать. Литературы на русском мало, а с английской всё будет дольше.
            Спасибо за проявленное терпение!
            • 0
              Конечно, после вставки нативного кода универсальность теряется.

              Вы говорили, что вам нужно только под платформу x86.
              Если нужно всё-таки для разных, можно вставлять разный код для разных архитектур.

              из IR-кода надо ещё как-то воспользоваться этой модификацией.

              Так часто практикуется. Clang может генерировать разный IR-код для разных аппаратных платформ, в расчёте на то, что конкретный бэкенд умеет оптимизировать определённые структуры в IR-коде.
              • 0
                Вы говорили, что вам нужно только под платформу x86.
                Да, нет, я начал с этого:
                Знакомился с LLVM и не нашёл, как можно изменить содержимое указателя стека. В x86 можно написать так: «xchg esp,other_stack». А как сделать что-то подобное на LLVM?
                Если есть какой-то универсальный механизм, то кто ж тогда откажется, чтобы его компилятор работал сразу на многих платформах? Честно говоря, написать бэкенд для x86 для меня проще, чем для LLVM, потому что всё знакомо. Но если LLVM позволит сделать многоплатформенный компилятор, то стоит задуматься об изучении LLVM – игра будет стоить свеч.
                • 0
                  написать бэкенд для x86 для меня проще, чем для LLVM

                  Бэкенд для x86 уже написан, и он входит в состав LLVM. Я не знаю точно, что вы хотите сделать, но вам нужно внести изменения в Clang, наверное.
                  Вы хотите реализовать какой-то свой язык программирования?
                  • 0
                    Бэкенд для x86 уже написан, и он входит в состав LLVM. Я не знаю точно, что вы хотите сделать, но вам нужно внести изменения в Clang, наверное.
                    Вы хотите реализовать какой-то свой язык программирования?
                    Имею в виду преобразование (бэкенд) «своё промежуточное представление -> код x86» (которое для меня проще), нежели «своё промежуточное представление -> код LLVM IR»
                    Вы хотите реализовать какой-то свой язык программирования?
                    Мы, по-видимому, смотрим на LLVM под разным углом зрения: я – как состыковать свой язык программирования с LLVM, а Вы – как состыковать с ним своё железо :)
                    • 0
                      своё промежуточное представление

                      Если вы удалите из этой схемы своё промежуточное представление, вы существенно упростите себе жизнь.
                      Свой язык программирования можно реализовать в Clang-е, есть хорошие примеры, описания и т.д.
                      • 0
                        Промежуточное представление – это очень общее понятие, это может быть и ориентированный граф, и трёхадресный код, и обратная польская запись и т.д. Лексический, синтаксический, семантический анализ должны каким-то образом хранить анализируемую программу, для этого ПП и служит. Разным по стилю языкам можно подобрать наиболее удобную форму. Если я удалю своё ПП – то как я проанализирую? Воспользоваться ПП от LLVM? Но это опять проблемы. Где взять его описание, какие он оно вообще работает? Много вопросов. Больше, чем если бы просто делал по обычным учебникам.
                        • 0
                          Да, разумеется, пользоваться библиотекой LLVM и Clang.
                          Описание взять здесь: llvm.org.
                          • 0
                            Кстати, если вспомнить, что LLVM – это виртуальная машина низкого уровня, то можно ли запустить её в режиме интерпретации? Т.е. подаёшь на вход какой-то код, а LLVM его выполняет? Не с целью генерации кода, а чтобы "поиграться", попробовать. В LLVM Projects нет намёков на это.
                            • 0
                              интерпретатор LLI
                            • 0
                              .
  • 0
    Из Википедии:
    «В основе LLVM лежит промежуточное представление кода (Intermediate Representation, IR)… Из этого представления генерируется оптимизированный машинный код для целого ряда платформ, как статически, так и динамически (JIT-компиляция)».

    Мне хотелось узнать, какими средствами LLVM IR нужно пользоваться, чтобы генератор кода (уже написанный для x86) делал переключение стеков. Меня не интересует конкретный бэкенд LLVM. Мне хочется узнать, как это сделать на уровне LLVM IR. Если LLVM IR это имеет, то и конкретный бэкенд сделает то, что я хочу. Может, он придумает что-то более оптимальное, нежели «xchg esp,other_stack».
    • 0
      На уровне LLVM IR стека нет (см. ответ выше).

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