Это руководство посвящено написанию простейшего компилятора на LLVM. Никакой предварительной подготовки не требуется.



Входным языком нашего компилятора будет BF. Это классический «игрушечный» язык для компиляторов, и даже есть компилятор BF в примерах к LLVM! В этом посте я приведу процесс написания компилятора с пояснениями.

Первая программа на LLVM

Инфраструктура LLVM построена вокруг языка программирования LLVM IR. Вначале мы напишем самую простую программу LLVM IR, насколько это возможно.

Так как LLVM уже использует LLVM IR, мы можем просто использовать clang, чтобы посмотреть, как выглядит простая программа. Возьмём простую программу на C

int main() {
    return 42;
}

Пропустим её через clang:

# -O3 ensures we discard any unnecessary instructions.
$ clang -S -emit-llvm -O3 forty_two.c

Получаем файл forty_two.ll, который выглядит так:

define i32 @main() {
  ret i32 42
}

Наша первая программа на LLVM IR! Мы можем использовать lli, чтобы запустить её:

$ lli forty_two.ll 
$ echo $?
42

Пишем скелет

Мы будем компилировать команды BF в последовательность инструкций LLVM IR. Однако, эти инструкции должны быть помещены внутрь функции main, чтобы LLVM знал, где находится точка входа. Нам также будет нужно аллоцировать и инициализировать ячейки памяти и индекс ячейки.

И снова мы просто напишем эквивалент на С и посмотрим на код LLVM IR, который сгенерирует Clang. Вот скелет программы, который мы будем использовать:

declare i8* @calloc(i32, i32)
declare void @free(i8*)

define i32 @main() {
  ; Allocate 30,000 cells on the heap.
  %cells = call i8* @calloc(i32 30000, i32 1)

  ; Allocate a stack variable to track the cell index.
  %cell_index_ptr = alloca i32
  ; Initialise it to zero.
  store i32 0, i32* %cell_index_ptr

  ;;;;;;;;;;;;;;;;;;;;
  ; Our BF code will go here!
  ;;;;;;;;;;;;;;;;;;;;

  ; Free the memory for the cells.
  call void @free(i8* %cells)
  ret i32 0
}

Вручную компилируем >

">" — это самая простая для компиляции команда BF. Откроем текстовый редактор и запишем её эквивалент на LLVM IR.

Если ваши познания BF немного заржавели, ">" просто инкрементирует индекс ячейки.

%cell_index = load i32* %cell_index_ptr
%new_cell_index = add i32 1, %cell_index
store i32 %new_cell_index, i32* %cell_index_ptr

Чтобы проверить, что код правильный, запустим его. Просто вставим его в наш скелет, запустим в lli, и посмотрим, что получилось. Реализация ">" прямолинейна, и мы также напишем программу для "<".

Вручную компилируем +

Команда BF "+" инкрементирует текущую ячейку. От нас требуется разыменовать указатель ячейки, вычислить новое значение и сохранить его. В C это выглядит так:

char *cell_ptr = cells + cell_index;
char current_value = *cell_ptr;
char new_value = current_value + 1;
*cell_ptr = new_value;

LLVM использует инструкцию getelementptr для вычисления указателя. Код будет выглядеть так:

%cell_index = load i32* %cell_index_ptr
%cell_ptr = getelementptr i8* %cells, i32 %cell_index

%current_value = load i8* %cell_ptr
%new_value = add i8 %current_value, 1
store i8 %new_value, i8* %cell_ptr

Снова тестируем это, помещая в наш скелет программы, и делаем то же самое для "-".

Ввод-вывод

BF имеет две команды ввода-вывода: "," которая читает из stdin в ячейку, и "." которая записывает из ячейки в stdout. Нам нужно вызывать функции C для этого: putchar и getchar.

Нам нужно объявить эти функции, как мы сделали это ранее для malloc:

declare i32 @putchar(i32)
declare i32 @getchar()

Для реализации команды, мы вызываем getchar, обрезаем результат до char, и записываем в текущую ячейку.

%cell_index = load i32* %cell_index_ptr
%cell_ptr = getelementptr i8* %cells, i32 %cell_index

%input_int = call i32 @getchar()
%input_byte = trunc i32 %input_int to i8
store i8 %input_byte, i8* %cell_ptr

"." работает в обратном порядке: читаем из ячейки, делаем знаковое расширение, и вызываем putchar.

%cell_index = load i32* %cell_index_ptr
%cell_ptr = getelementptr i8* %cells, i32 %cell_index

%current_cell = load i8* %cell_ptr
%current_cell_word = sext i8 %current_cell to i32
call i32 @putchar(i32 %current_cell_word)

Циклы

Инструкции LLVM IR организованы в базовые блоки; последовательности инструкций без переходов внутри блока. В конце каждого базового блока вы должны либо выполнить переход на другой базовый блок, либо выполнить возврат.

Для компиляции "[ x ] y", нам нужно проверить текущую ячейку, затем либо перейти к x, нашему телу цикла, либо к y. В конце x, нам нужно сделать переход к началу.

loop_header:
  %cell_index = load i32* %cell_index_ptr
  %cell_ptr = getelementptr i8* %cells, i32 %cell_index
  %cell_value = load i8* %cell_ptr
  %is_zero = icmp eq i8 %cell_value, 0
  br i1 %is_zero, label %loop_after, label %loop_body

loop_body:
  ; x
  br label %loop_header

loop_after:
  ; y

Отметим, что здесь есть рекурсия, x может также содержать циклы. Пример программы здесь.

Собираем всё вместе

Мы сделали самое сложное! Сейчас используем LLVM API для генерации инструкций. Каждая инструкция IR имеет соответствующий объект C++, который вы можете добавить в ваш базовый блок.

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

Вот код C++ для генерации LLVM IR для ">". Прекрасное руководство по LLVM включает в себя инструкции для компиляции простой программы C++ с использованием LLVM API.

BasicBlock *BB;

// Instantiate an IRBuilder that appends to our
// current basic block.
IRBuilder<> Builder(getGlobalContext());
Builder.SetInsertPoint(BB);

// We want to increment by 1, but since cell_index is
// 32-bit, our constant must be 32-bit too.
Value *IncrementAmount =
    ConstantInt::get(getGlobalContext(), APInt(32, 1));

// Emit the load, add and store instructions.
Value *CellIndex = Builder.CreateLoad(CellIndexPtr, "cell_index");
Value *NewCellIndex =
    Builder.CreateAdd(CellIndex, IncrementAmount, "new_cell_index");
Builder.CreateStore(NewCellIndex, CellIndexPtr);

Компиляция других команд BF — это простая трансляция наших написанных вручную сниппетов. Вы можете увидеть полностью работающий компилятор здесь.

Генерация машинного кода

Наш компилятор генерирует только LLVM IR. Настоящие компиляторы генерируют машинный код. Используем llc для преобразования в объектный файл, а затем слинкуем для получения исполняемого файла.

$ ./compiler hello_world.bf
$ llc -filetype=obj hello_world.ll
$ gcc hello_world.o -o hello_world
$ ./hello_world
Hello World!

Вот и всё!

Приложение: Оптимизация

Можно делать оптимизации, чтобы получить более быстрые исполняемые файлы из программ BF. Однако, LLVM достаточно умён для компиляции простой BF-программы без циклов в оптимальное представление LLVM IR!

$ cat exclamation.bf 
+++++ +++++
+++++ +++++
+++++ +++++
+++ ASCII 33 is '!'
. Write ! to stdout
$ ./compiler exclamation.bf 
$ opt -S -O3 exclamation.ll -o optimised_exclamation.ll

Получаем:

define i32 @main() {
entry:
  %0 = tail call i32 @putchar(i32 33)
  ret i32 0
}