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

Пример к статье доступен на github

Нововведения

Данный транслятор был получен путём доработки интерпретатора из примера lemon-8 с использованием LLVM для генерации кода. Была реализована только часть языка:

• функции и определение функции main
• выражения

На данный момент не работают:

• кодогенерация для типов Boolean, String
• кодогенерация для циклов и ветвлений

Пример компилируемого кода:

function main()
  x = 2 + 34 / 2
  print x - 4 * 0.5
end

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

; комментарии начинаются с ';'
; ModuleID = 'main module'
; source_filename - атрибут для отладочных целей
source_filename = "main module"

; @str - глобальная строковая константа, содержит строку "%lf\n"
@str = internal constant [5 x i8] c"%lf\0A\00"

; @printf - внешняя функция, реализация находится в стандартной библиотеке
;  языка C и есть в каждой операционной системе
declare i32 @printf(i8*, ...)

; @main - точка входа программы по соглашениям LLVM-IR
define i32 @main() {
; entry - метка, открывающая первый блок инструкций функции
entry:
; инструкция call вызывает функцию printf
  %0 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @str, i32 0, i32 0), double 0x4030FFFFFF800000)
  ret i32 0
}

Также изменилась грамматика:

• теперь инструкции должны находится строго внутри функций
• точкой входа служит функция main без аргументов и без return

Транслятор читает входной поток целиком, и затем пишет в выходной поток LLVM-IR код в человекочитаемом виде. Этот код можно скомпилировать в исполняемый файл командой "clang main.ll".

Класс CCompilerDriver

Класс имеет очень простой интерфейс и реализует паттерн “Фасад” (“Facade”), т.е. его основная цель - объединить подсистемы компилятора в простой и удобный интерфейс.

class CCompilerDriver
{
public:
    CCompilerDriver(std::ostream &errors);
    ~CCompilerDriver();

    void StartDebugTrace();
    bool Compile(std::istream &input, std::ostream &output);

private:
    // Используется идиома pointer-to-implementation.
    class Impl;
    std::unique_ptr<Impl> m_pImpl;
};

Метод CCompilerDriver::Compile работает в два шага: сначала разбирает исходный текст и конструирует AST, а затем обходит AST в глубину и генерирует код. Именно генерация кода представляет наибольший интерес, поэтому рассмотрим её подробнее.

Паттерн “Посетитель” (“Visitor”) для узлов AST

В интерпретаторе был использован паттерн “Интерпретатор”, т.е. каждый узел AST имел метод, который принимал контекст выполнения и выполнял рекурсивное вычисление узла с учётом текущего контекста выполнения:

// Вычисление выражения возвращает результат в виде CValue
class IExpressionAst
{
public:
    virtual ~IExpressionAst() = default;
    virtual CValue Evaluate(CInterpreterContext& context) const = 0;
};

// Выполнение инструкции результата не возвращает
class IStatementAst
{
public:
    virtual ~IStatementAst() = default;
    virtual void Execute(CInterpreterContext& context) const = 0;
};

// Вычисление функции требует список аргументов и возвращает результат в виде CValue
class IFunctionAst
{
public:
    virtual ~IFunctionAst() = default;
    virtual CValue Call(CInterpreterContext& context, std::vector<CValue> const& arguments) const = 0;
    virtual unsigned GetNameId() const = 0;
};

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

• сначала должна произойти проверка типов и других семантических правил путём обхода AST
• затем путём ещё одного обхода AST нужно сгенерировать промежуточный код на языке LLVM-IR
• уже после генерации промежуточного кода он может быть превращён в машинный (это тема следующих статей) и использован для обработки входных данных

Для множественной обработки AST лучше подходит паттерн “Посетитель”, который позволяет абстрагироваться от узлов AST. Для реализации паттерна достаточно создать у каждого узла дерева метод, например void Accept(IVisitor&), который будет вызывать правильную перегрузку метода IVisitor::Visit, соответствующую типу текущего узла, и рекурсивно вызывать Accept для дочерних узлов:

Генерация кода выражений

Для генерации кода выражений мы реализуем интерфейс IExpressionVisitor

class CExpressionCodeGenerator : protected IExpressionVisitor
{
public:
    CExpressionCodeGenerator(llvm::IRBuilder<>& builder, CFrontendContext& context);

    // Can throw std::exception.
    llvm::Value* Codegen(IExpressionAST& ast);

protected:
    void Visit(CBinaryExpressionAST& expr) override;
    void Visit(CUnaryExpressionAST& expr) override;
    void Visit(CLiteralAST& expr) override;
    void Visit(CCallAST& expr) override;
    void Visit(CVariableRefAST& expr) override;

private:
    // Стек используется для временного хранения
    // по мере рекурсивного обхода дерева выражения.
    std::vector<llvm::Value*> m_values;
    CFrontendContext& m_context;
    llvm::IRBuilder<>& m_builder;
};

Для генерации списка инструкций нам потребуется принцип стековых вычислений

Принцип стековых вычислений описан в статье Стековые и регистровые машины

Для стековых вычислений есть нюанс: в нашем распоряжении есть только регистры, в них находятся операнды инструкций и попадают результаты выполнения. В языке LLVM-IR бесконечно много регистров, и для создания нового регистра достаточно просто присвоить его. Так может выглядеть вычисление “28 / 9 + 7 + 5.5” на LLVM-IR:

; Программа вычисляет выражение 28.0 / 9.0 + 7.0 * 5.5 и печатает в консоль результат

; @str - глобальная строковая константа, содержит строку "%lf\n"
@str = internal constant [5 x i8] c"%lf\0A\00"


; @printf - внешняя функция, реализация находится в стандартной библиотеке
;  языка C и есть в каждой операционной системе
declare i32 @printf(i8*, ...)

define i32 @main() {
entry:
  %0 = fdiv double 28.0, 9.0
  %1 = fmul double 7.0, 5.5
  %2 = fadd double %0, %1
  %3 = getelementptr inbounds [5 x i8], [5 x i8]* @str, i32 0, i32 0
  %4 = call i32 (i8*, ...) @printf(i8* %3, double %2)
  
  ret i32 0
}

Нетрудно заметить, что здесь можно применить разложение выражения в линейный список инструкций с помощью стека. При этом в ячейках стека следует хранить не значения, а регистры, потому что на момент компиляции входных данных и соответственно значений ещё нет.

В библиотеках LLVM объекты регистров представляются указателями типа llvm::Value*, а в качестве стека подойдёт обычный std::vector. Класс CExpressionCodeGenerator по мере рекурсивного обхода одного выражения сохраняет регистры с результатами подвыражений в поле std::vector<llvm::Value*> m_values;. В конце обхода (в случае, если кодогенератор написан правильно) на стеке останется ровно один регистр, который и будет хранить в себе значение после выполнения всех инструкций.

Value* CExpressionCodeGenerator::Codegen(IExpressionAST& ast)
{
    llvm::Value* pValue = nullptr;
    try
    {
        ast.Accept(*this);
        pValue = m_values.at(0);
        m_values.clear();
    }
    catch (std::exception const& ex)
    {
        m_context.PrintError(ex.what());
    }
    return pValue;
}

Генерация инструкций выполняется с помощью объекта llvm::IRBuilder<>& m_builder;:

Value* GenerateUnaryExpr(IRBuilder<>& builder, LLVMContext& context, UnaryOperation op, Value* x)
{
    (void)context;
    switch (op)
    {
    case UnaryOperation::Plus:
        return x;
    case UnaryOperation::Minus:
        // Генерация инструкции negtmp
        return builder.CreateFNeg(x, "negtmp");
    }
    throw std::runtime_error("Unknown unary operation");
}

void CExpressionCodeGenerator::Visit(CUnaryExpressionAST& expr)
{
    expr.GetOperand().Accept(*this);
    Value* x = m_values.at(m_values.size() - 1);
    m_values.pop_back();

    auto pValue = GenerateUnaryExpr(m_builder, m_context.GetLLVMContext(), expr.GetOperation(), x);
    m_values.push_back(pValue);
}

Генерация кода инструкций

В процедурных языках программирования есть цепочки инструкций, и в языках ассемблера они тоже есть. Поэтому генерация кода инструкций заключается в простом последовательном отображении высокоуровневых инструкций вашего языка на низкоуровневые инструкции ассемблера. Однако, с некоторыми высокоуровневыми конструкциями могут возникнуть сложности: мы рассмотрим основные случаи. Для генерации кода цепочек инструкций служит класс CBlockCodeGenerator:

class CBlockCodeGenerator : protected IStatementVisitor
{
public:
    CBlockCodeGenerator(CFrontendContext& context);

    void Codegen(llvm::BasicBlock& bb, const StatementsList& block);
    void AddExitMain();

    // IStatementVisitor interface
protected:
    void Visit(CPrintAST& ast) override;
    void Visit(CAssignAST& expr) override;
    void Visit(CReturnAST& expr) override;
    void Visit(CWhileAst& expr) override;
    void Visit(CRepeatAst& expr) override;
    void Visit(CIfAst& expr) override;

private:
    CFrontendContext& m_context;
    llvm::IRBuilder<> m_builder;
    CExpressionCodeGenerator m_exprGen;
};

Начнём с самой простой инструкции возврата, которая должна просто привести в вызову инструкции ret языка LLVM-IR:

// Выбрасывает ret double %имя_регистра
void CBlockCodeGenerator::Visit(CReturnAST& expr)
{
    if (auto* pValue = m_exprGen.Codegen(expr.GetValue()))
    {
        m_builder.CreateRet(pValue);
    }
}

Немного сложнее будет реализация присваивания: по сути переменные - это отображение имени (идентификатора) на некоторую ячейку памяти, а для построения такого отображения в памяти компилятора подойдёт структура данных “хеш-массив” (известная как ассоциативный массив или словарь). В примере ниже вызывается метод AssignVariable, который получает регистр, имя переменной (в виде целочисленного ID) и сохраняет отображение имени на регистр в хеш-таблице. Пока что у нас нет обработки областей видимости, поэтому хеш-таблица единая на всю программу.

void CBlockCodeGenerator::Visit(CAssignAST& ast)
{
    llvm::Value* pValue = m_exprGen.Codegen(ast.GetValue());
    m_context.AssignVariable(ast.GetNameId(), pValue);
}

Остальные изменения в сравнении с lemon-8-types

• новые классы CCodeGenerator, CBlockCodeGenerator, CExpressionCodeGenerator генерируют код для программы целиком, для тела функции и для выражения соответственно
• класс CInterpreterContext переименован в CFrontendContext и претерпел изменения в типах данных, с которыми он работает.
• класс CValue был удалён за ненадобностью
• методы Evaluate и Execute у выражений и инструкций были удалены, теперь узлы AST лишь дают возможность обхода посетителем, но сами не содержат логики генерации кода.

Использованная литература

• язык Kaleidoscope, глава 3 (llvm.org)
• передача строковой константы как аргумента фукнции (stackoverflow.com)
• как заставить Clang скомпилировать C++ в LLVM-IR (stackoverflow.com)