LLVM фронтенд для Brainfuck
Всем привет!
А вот и вторая часть обещанной статьи.
Приступим же!
Введение
Для начала давайте определимся с терминологией.
Насчёт LLVM вики говорит нам следующее:
LLVM — проект программной инфраструктуры для создания компиляторов и сопутствующих им утилит. Состоит из набора компиляторов из языков высокого уровня (так называемых «фронтендов»), системы оптимизации, интерпретации и компиляции в машинный код.
В данном случае мы не будем сильно закапываться в архитектуру LLVM и ограничимся только его IR (или Intermediate Representation aka промежуточное представление).
Благо если у вас в системе установлен llvm, то есть возможность использовать следующие утилиты:
lli— интерпретатор байткодаllc— и компилятор соответственно
Нам же будет достаточно только lli, но если захотите собрать приложение, то llc вам в помощь.
Но прежде чем мы перейдём написанию своего мини фронтенда давайте сделаем более простую вещь — напишем транспайлер в си.
Транспайлер
Транспайлер или транслирующий компилятор довольно интересная вещь с точки зрения лени :)
Когда лень писать свой фронтенд, то мы всегда можем использовать мощности другого языка.
Просто реализуем перевод конструкций нашего языка в язык назначения (например C).
Большим плюсом мы можем получить возможности по оптимизации кода, но не всегда они могут быть успешными.
Хватит пустой болтовни... приступим к написанию кода.
Базироваться он будем на коде из прошлой статьи
use std::io::{self, Write};
use crate::command::Command;
use crate::emulator::Emulator;
// определим трейт описывающий наш транспилятор
pub trait TranspilerC {
// writer — туда будем писать результирующий код
// и про обработку ошибок не забудем
fn into_code<W: Write>(self, writer: &mut W) -> Result<(), io::Error>;
}
// реализуем трейт для нашего эмулятора (o_0)
impl TranspilerC for Emulator {
fn into_code<W: Write>(self, writer: &mut W) -> Result<(), io::Error> {
// буфер с кодом
let mut code = String::new();
// будем последовательно итерироваться по командам brainfuck
// iter_command() — это по сути доступ к slice::Iter<Command>
for token in self.iter_command() {
// для компактности я ужал код в однострочники, но в комментариях сделаю пояснения
match token {
// проверяем условие на выход за границы памяти, и если всё ок то увеличиваем наш счётчик
Command::Next => code.push_str("\tif (mp + 1 > MAX_MEM_SIZE) out_of_memory();\n\tmp += 1;\n"),
// так же проверям границы и уменьшаем счётчик
Command::Previous => code.push_str("\tif (mp == 0) negative_memory();\n\tmp -= 1;\n"),
// увеличиваем значение ячейки памяти
Command::Increment => code.push_str("\tmem[mp] += 1;\n"),
// аналогично, но с уменьшением
Command::Decrement => code.push_str("\tmem[mp] -= 1;\n"),
// вывод символа из ячейки памяти
Command::Put => code.push_str("\tputchar(mem[mp]);\n"),
// ввод символа с клавиатуры
Command::Read => code.push_str("\tmem[mp] = getchar();\n"),
// начало цикла while
Command::LoopBegin(_) => code.push_str("\twhile (mem[mp] != 0) {\n"),
// и условие завершение цикла
Command::LoopEnd(_) => code.push_str("\tif (mem[mp] == 0) break;\n\t}\n"),
}
}
// пишем весь код во writer
write!(writer, include_str!("../templates/c-template.txt"), mem_size = self.mem_size(), code = code)
}
}
Этого небольшого кода нам хватит чтобы преобразовать любую программу на Brainfuck в программу на C.
Внимательный читатель мог заметить include_str!("../templates/c-template.txt") — данный макрос сильно упрощает нам жизнь, когда нужно вставить большой кусок текста и не очень хочется захламлять код.
Содержимое файла c-template.txt — шаблонный код на языке C с возможностью подстановки нужных нам значений
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#define MAX_MEM_SIZE {mem_size}
{% raw %}
void out_of_memory() {{
{% endraw %}
puts("error: out of memory!");
exit(-1);
{% raw %}
}}
{% endraw %}
{% raw %}
void negative_memory() {{
{% endraw %}
puts("error: cannot access negative memory index!");
exit(-1);
{% raw %}
}}
{% endraw %}
{% raw %}
int main() {{
uint8_t mem[MAX_MEM_SIZE] = {{0}};
{% endraw %}
uint32_t mp = 0;
{code}
return 0;
{% raw %}
}}
{% endraw %}
Шаблон кода слишком простой чтобы его комментировать. Давайте сразу перейдём к результату транспиляции hello.bf из Brainfuck в C:
// ... шаблон опушен ...
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
while (mem[mp] != 0) {
if (mp + 1 > MAX_MEM_SIZE) out_of_memory();
mp += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
if (mp + 1 > MAX_MEM_SIZE) out_of_memory();
mp += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
if (mp + 1 > MAX_MEM_SIZE) out_of_memory();
mp += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
if (mp + 1 > MAX_MEM_SIZE) out_of_memory();
mp += 1;
mem[mp] += 1;
if (mp == 0) negative_memory();
mp -= 1;
if (mp == 0) negative_memory();
mp -= 1;
if (mp == 0) negative_memory();
mp -= 1;
if (mp == 0) negative_memory();
mp -= 1;
mem[mp] -= 1;
if (mem[mp] == 0) break;
}
if (mp + 1 > MAX_MEM_SIZE) out_of_memory();
mp += 1;
mem[mp] += 1;
mem[mp] += 1;
putchar(mem[mp]);
if (mp + 1 > MAX_MEM_SIZE) out_of_memory();
mp += 1;
mem[mp] += 1;
putchar(mem[mp]);
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
putchar(mem[mp]);
putchar(mem[mp]);
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
putchar(mem[mp]);
if (mp + 1 > MAX_MEM_SIZE) out_of_memory();
mp += 1;
mem[mp] += 1;
mem[mp] += 1;
putchar(mem[mp]);
if (mp == 0) negative_memory();
mp -= 1;
if (mp == 0) negative_memory();
mp -= 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
putchar(mem[mp]);
if (mp + 1 > MAX_MEM_SIZE) out_of_memory();
mp += 1;
putchar(mem[mp]);
mem[mp] += 1;
mem[mp] += 1;
mem[mp] += 1;
putchar(mem[mp]);
mem[mp] -= 1;
mem[mp] -= 1;
mem[mp] -= 1;
mem[mp] -= 1;
mem[mp] -= 1;
mem[mp] -= 1;
putchar(mem[mp]);
mem[mp] -= 1;
mem[mp] -= 1;
mem[mp] -= 1;
mem[mp] -= 1;
mem[mp] -= 1;
mem[mp] -= 1;
mem[mp] -= 1;
mem[mp] -= 1;
putchar(mem[mp]);
if (mp + 1 > MAX_MEM_SIZE) out_of_memory();
mp += 1;
mem[mp] += 1;
putchar(mem[mp]);
if (mp + 1 > MAX_MEM_SIZE) out_of_memory();
mp += 1;
putchar(mem[mp]);
// ...
Код конечно не самого лучшего качества, да и форматирование хромает, но зато это рабочая программа полученная из кода на Brainfuck, которая после запуска честно выводит на терминал
Hello World!
Здесь конечно ещё можно произвести всякие улучшения, как например объединение одинаковых инструкций идущих подряд, но мы на этом остановимся и перейдём к следующему этапу.
LLVM IR
Здесь так же будем использовать такой же шаблон как и в прошлом разделе, но тут стоит немного более подробно рассмотреть как каждая инструкция на Brainfuck преобразуется в LLVM IR.
// я ничего умнее не придумал и просто написал ещё один трейт
pub trait TranspilerLLVM {
fn into_code<W: Write>(self, writer: &mut W) -> Result<(), io::Error>;
}
IR в LLVM имеет довольно специфичные ограничения по сравнению с другими ассемблерами. Например нельзя увеличить значение ячейки памяти, не загрузив её в промежуточную переменную. Полные подробности можно найти по ссылке.
Начнём же с инкремента ячейки памяти:
; тут mp и mem те же переменные что и раньше (индекс и память)
; загружаем 32-битное значение из указателя на mp в регистр 1
%1 = load i32, i32* %mp
; получаем адрес элемента mem по индексу из регистра 1
%2 = getelementptr i8, i8* %mem, i32 %1
; загружаем байт значение по адресу из регистра 2
%3 = load i8, i8* %2
; увеличиваем данное значение на единицу и записываем в новый регистр
%4 = add i8 %3, 1
; записывем значение обратно в ячейку памяти
store i8 %4, i8* %2
Тут стоит немного прояснить синтаксис.
Символ % перед значением указывает на локальную переменную.
Для каждой новой команды (если она возвращает значение) нужно увеличивать индекс регистра. Да и количество регистров не ограничено.
Хотя мы всегда можем использовать именованные регистры, чтобы не мучиться с всё время увеличивающимся счётчиком регистров.
Для реализации декремента всего-то нужно изменить
%4 = add i8 %3, 1
; на
%4 = sub i8 %3, 1
Увеличение индекса mp реализуем вот так:
; загрузка значения
%v0 = load i32, i32* %mp
; инкремент
%v1 = add i32 %v0, 1
; проверяем выходит ли за границу
%v2 = icmp sgt i32 %v1, 30000
; если выходит, то переходим к коду ошибки, а иначе идём дальше по коду
br i1 %v2, label %OutOfMemory, label %NextOk
NextOk:
; записываем в mp
store i32 %v1, i32* %mp
Тут уже можно видеть, как вместо %1 и т.д. используются именованные переменные, да и появились несколько новых команд.
Уменьшение индекса будет аналогичным, но только условие проверки сменится на
%v2 = icmp slt i32 %v1, 0
и переход к метке с выводом ошибки будет другим.
Теперь давайте рассмотрим команды вывода символа в терминал.
; нам нужно объявить используемую функцию
declare i32 @putchar(i32)
; @ указывает на глобальную переменную
; ...
; тут всё понятно
%v0 = load i32, i32* %mp
%v1 = getelementptr i8, i8* %mem, i32 %v0
%v2 = load i8, i8* %v1
; знаковое расширение типа переменной с i8 до i32
%v3 = sext i8 %v2 to i32
; вызываем функцию
call i32 @putchar(i32 %v3)
А для чтения в память
declare i32 @getchar()
; ...
%v0 = load i32, i32* %mp
%v1 = getelementptr i8, i8* %mem, i32 %v0
; читаем
%v2 = call i32 @getchar()
; усекаем i32 до i8
%v3 = trunc i32 %v2 to i8
store i8 %v3, i8* %v1
Остаётся только разобраться с циклом и тут самое интересное. Пришлось схитрить, т.к. lli всё время не хотел нормально работать с метками. Всё оказалось из-за того, что нужно явно делать переходы на них с помощью br
br label %LoopStart
LoopStart:
%v0 = load i32, i32* %mp
%v1 = getelementptr i8, i8* %mem, i32 %v0
%v2 = load i8, i8* %v1
; переход если равно 0
%v3 = icmp eq i8 %v2, 0
br i1 %v3, label %LoopEnd, label %LoopNext
LoopNext:
; ... место для кода
%v4 = load i32, i32* %mp
%v5 = getelementptr i8, i8* %mem, i32 %v4
%v6 = load i8, i8* %v5
; переход если не равно 0
%v7 = icmp ne i8 %v5, 0
br i1 %v7, label %LoopStart, label %LoopEnd
LoopEnd:
Тут пришлось объединить код двух команд для того чтобы было полное понимание переходов между ними.
Вроде бы разобрали все команды и можно приступить к написанию кода.
use std::io::{self, Write};
use crate::command::Command;
use crate::emulator::Emulator;
// ... transpilerLLVM trait ...
impl TranspilerLLVM for Emulator {
fn into_code<W: Write>(self, writer: &mut W) -> Result<(), io::Error> {
use Command::*;
// буфер для кода
let mut code = String::new();
// итерируемся по командам с индексами
for (index, cmd) in self.iter_command().enumerate() {
// будем пушить шаблон кода с подстановкой своих значений
match &cmd {
Next => {
code.push_str(&format!(
// сам шаблон
include_str!("../templates/llvm/next.txt"),
// индекс инструкции нужен для именования временных переменных
index = index,
// максимальное количество ячеек памяти
max_size = self.mem_size()
));
}
Previous => {
code.push_str(&format!(include_str!("../templates/llvm/prev.txt"), index = index));
}
Increment => {
code.push_str(&format!(
// унифицированный шаблон
include_str!("../templates/llvm/inc-dec.txt"),
// где подставляется даже команда
cmd = "add",
// и значение на которое изменяется
amount = 1,
index = index
));
}
Decrement => {
code.push_str(&format!(
include_str!("../templates/llvm/inc-dec.txt"),
cmd = "sub",
amount = 1,
index = index
));
}
Put => code.push_str(&format!(include_str!("../templates/llvm/put.txt"), index = index)),
Read => code.push_str(&format!(include_str!("../templates/llvm/read.txt"), index = index)),
LoopBegin(end) => {
code.push_str(&format!(include_str!("../templates/llvm/loop-begin.txt"), start = index, end = end))
}
LoopEnd(start) => {
code.push_str(&format!(include_str!("../templates/llvm/loop-end.txt"), start = start, end = index));
}
}
}
// пишем в файл сформированный шаблонный код
write!(writer, include_str!("../templates/llvm/template.txt"), mem_size = self.mem_size(), code = code)
}
}
Тут уже стоит рассмотреть подробнее шаблонный код программы
; комментарий с именем модуля
; ModuleID = 'brainfuck app'
; константы ошибок
@err1 = private unnamed_addr constant [21 x i8] c"error: out of memory\00"
@err2 = private unnamed_addr constant [43 x i8] c"error: cannot access negative memory index\00"
; объявляем функции для выделения и освобождения памяти
declare i8* @calloc(i32, i32)
declare void @free(i8*)
; функции IO
declare i32 @getchar()
declare i32 @putchar(i32)
declare i32 @puts(i8*)
; определяем main функцию
{% raw %}
define i32 @main() {{
{% endraw %}
; выделяем {mem_size} ячеек памяти
%mem = call i8* @calloc(i32 {mem_size}, i32 1)
; аллоцируем указатель на стеке для индекса
%mp = alloca i32
; и инициализируем его нулём
store i32 0, i32* %mp
; тут будет подставлен код
{code}
; переходим к освобождению памяти
br label %AppEnd
OutOfMemory:
; вызовем функцию которая выведет текст ошибки на терминал
call i32 @puts(i8* getelementptr inbounds ([21 x i8], [21 x i8]* @err1, i64 0, i64 0))
br label %AppEnd
NegativeMemoryIndex:
call i32 @puts(i8* getelementptr inbounds ([43 x i8], [43 x i8]* @err2, i64 0, i64 0))
br label %AppEnd
AppEnd:
; деаллоцируем память и завершим программу
call void @free(i8* %mem)
ret i32 0
{% raw %}
}}
{% endraw %}
Шаблоны для каждой инструкции можно посмотреть в папке. Основное отличие от тех, что были описаны ранее — подстановка индексов для временных меток и регистров.
Теперь мы так же можешь преобразовать hello.bf из Brainfuck, но уже в LLVM IR.
Покажу только часть кода, т.к. он получился намного длиннее кода на C
; ...
store i8 %v38, i8* %v18
%v09 = load i32, i32* %mp
%v19 = getelementptr i8, i8* %mem, i32 %v09
%v29 = load i8, i8* %v19
%v39 = add i8 %v29, 1
store i8 %v39, i8* %v19
br label %LoopStart10
LoopStart10:
%v010 = load i32, i32* %mp
%v110 = getelementptr i8, i8* %mem, i32 %v010
%v210 = load i8, i8* %v110
; ...
Теперь этот код можно запустить с помощью lli:
$ lli hello.ll
Hello World!
Заключение
Весь код доступен в репозитории
А на сегодня это всё.
До следующего раза!