Pull to refresh

Создание языка программирования с использованием LLVM. Часть 8: Компиляция в объектный код

Reading time 23 min
Views 7.5K
Original author: Chris Lattner
Оглавление:
Часть 1: Введение и лексический анализ
Часть 2: Реализация парсера и AST
Часть 3: Генерация кода LLVM IR
Часть 4: Добавление JIT и поддержки оптимизатора
Часть 5: Расширение языка: Поток управления
Часть 6: Расширение языка: Операторы, определяемые пользователем
Часть 7: Расширение языка: Изменяемые переменные
Часть 8: Компиляция в объектный код
Часть 9: Добавляем отладочную информацию
Часть 10: Заключение и другие вкусности LLVM



8.1. Введение


Добро пожаловать в главу 8 руководства “Создание языка программирования с использованием LLVM”. Эта глава описывает, как компилировать программы на нашем языке в объектные файлы.

8.2. Выбор цели


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

Чтобы определить архитектуру, которая послужит целью, мы используем строку, называемую «тройкой цели». Она имеет форму <arch><sub>-<vendor>-<sys>-<abi> (см. документацию по кросс-компиляции).

В качестве примера, давайте посмотрим, что clang считает нашей текущей тройкой цели:

$ clang --version | grep Target
Target: x86_64-unknown-linux-gnu

Выполнение этой команды на вашей машине может показать что-то другое, потому что вы можете использовать другую архитектуру или операционную систему.

К счастью, нам не нужно хардкодить тройку цели, чтобы она указывала текущую машину. LLVM предоставляет функцию sys::getDefaultTargetTriple, возвращающую тройку цели для текущей машины.

auto TargetTriple = sys::getDefaultTargetTriple();

LLVM не требует от нас использовать все функции целевой платформы (таргета). Например, если мы используем только JIT, нам не нужен принтер ассемблера. Аналогично, если мы нацелены только на определённую архитектуру, мы можем использовать только функиональность для этой архитектуры.

В этом примере, мы инициализируем все таргеты для генерации объектного кода.

InitializeAllTargetInfos();
InitializeAllTargets();
InitializeAllTargetMCs();
InitializeAllAsmParsers();
InitializeAllAsmPrinters();

Сейчас мы можем использовать тройку цели для получения объекта Target:


std::string Error;
auto Target = TargetRegistry::lookupTarget(TargetTriple, Error);
// Печатаем сообщение об ошибке и выходим, если не нашли запрошенного таргета
// Это обычно происходит, если мы забыли инициализировать 
// TargetRegistry или у нас неверная тройка цели.
if (!Target) {
  errs() << Error;
  return 1;
}

8.3. Объект Target Machine


Также нам нужен объект класса TargetMachine. Этот класс предоставляет полное описание машины, на которую мы нацелены. Если мы хотим иметь в целевой машине специфические возможности (например, SSE), или специфический CPU (например, Intel Sandylake), мы должны указать это сейчас.

Чтобы увидеть те возможности и те CPU, о которых знает LLVM, мы можем воспользоваться llc. Например, давайте посмотрим на x86:

$ llvm-as < /dev/null | llc -march=x86 -mattr=help

Доступные CPU для этого таргета:

amdfam10
athlon
athlon-4


Доступные возможности для этого таргета:

16bit-mode — 16-битный режим (i8086).
32bit-mode — 32-битный режим (80386).
3dnow — Разрешить инструкции 3DNow!
3dnowa — Разрешить инструкции 3DNow! Athlon.


Для нашего примера мы будем использовать обычный CPU без дополнительных возможностей, опций или модели релокации

auto CPU = "generic";
auto Features = "";

TargetOptions opt;
auto RM = Optional<Reloc::Model>();
auto TargetMachine = Target->createTargetMachine(TargetTriple, CPU, Features, opt, RM);

8.4. Конфигурация объекта Module


Сейчас мы готовы сконфигурировать модуль, чтобы определить таргет и модель данных. Это не является строго необходимым, но руководство по фронтенду рекомендует так сделать. Возможна лучшая оптимизация, если будет известен таргет и модель данных (data layout).

TheModule->setDataLayout(TargetMachine->createDataLayout());
TheModule->setTargetTriple(TargetTriple);

8.5. Генерация объектного кода


Мы готовы сгенерировать объектный код! Определим, куда мы хотим записать файл:

auto Filename = "output.o";
std::error_code EC;
raw_fd_ostream dest(Filename, EC, sys::fs::F_None);

if (EC) {
  errs() << "Could not open file: " << EC.message();
  return 1;
}

Наконец, мы определяем прооход, генерирующий объектный код, и запускаем его:

legacy::PassManager pass;
auto FileType = TargetMachine::CGFT_ObjectFile;

if (TargetMachine->addPassesToEmitFile(pass, dest, FileType)) {
  errs() << "TargetMachine can't emit a file of this type";
  return 1;
}

pass.run(*TheModule);
dest.flush();

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


Работает ли программа? Давайте попробуем. Нам нужно скомпилировать наш код, но заметим, что аргументы llvm-config другие, чем в предыдущих главах.

$ clang++ -g -O3 toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs all` -o toy

Давайте запустим, и определим простую функцию усреднения. Нажмите Ctrl-D, когда она закончит работу.

$ ./toy
ready> def average(x y) (x + y) * 0.5;
^D

Записан файл output.o
У нас есть объектный файл! Чтобы проверить его, напишем простую программу и слинкуем с этим файлом. Вот исходный код:

#include <iostream>

extern "C" {
    double average(double, double);
}

int main() {
    std::cout << "average of 3.0 and 4.0: " << average(3.0, 4.0) << std::endl;
}

Слинкуем нашу программу с output.o и проверим, что результат такой, какой мы ожидаем:

$ clang++ main.cpp output.o -o main
$ ./main
average of 3.0 and 4.0: 3.5

8.7. Полный листинг кода


Полный код
#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/LegacyPassManager.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Support/FileSystem.h"
#include "llvm/Support/Host.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/TargetRegistry.h"
#include "llvm/Support/TargetSelect.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <memory>
#include <string>
#include <system_error>
#include <utility>
#include <vector>

using namespace llvm;
using namespace llvm::sys;

//===----------------------------------------------------------------------===//
// Лексический анализатор
//===----------------------------------------------------------------------===//

// Лексический анализатор возвращает токены [0-255] если это неизвестный символ, либо один из
// известных
enum Token {
  tok_eof = -1,

  // команды
  tok_def = -2,
  tok_extern = -3,

  // первичные символы
  tok_identifier = -4,
  tok_number = -5,

  // управление
  tok_if = -6,
  tok_then = -7,
  tok_else = -8,
  tok_for = -9,
  tok_in = -10,

  // операторы
  tok_binary = -11,
  tok_unary = -12,

  // определение переменных
  tok_var = -13
};

static std::string IdentifierStr; // Заполняется для tok_identifier
static double NumVal;             // Заполняется для tok_number

/// gettok - Возвращает следующий токен из стандартного ввода
static int gettok() {
  static int LastChar = ' ';

  // Пропускаем пробелы
  while (isspace(LastChar))
    LastChar = getchar();

  if (isalpha(LastChar)) { идентификатор: [a-zA-Z][a-zA-Z0-9]*
    IdentifierStr = LastChar;
    while (isalnum((LastChar = getchar())))
      IdentifierStr += LastChar;

    if (IdentifierStr == "def")
      return tok_def;
    if (IdentifierStr == "extern")
      return tok_extern;
    if (IdentifierStr == "if")
      return tok_if;
    if (IdentifierStr == "then")
      return tok_then;
    if (IdentifierStr == "else")
      return tok_else;
    if (IdentifierStr == "for")
      return tok_for;
    if (IdentifierStr == "in")
      return tok_in;
    if (IdentifierStr == "binary")
      return tok_binary;
    if (IdentifierStr == "unary")
      return tok_unary;
    if (IdentifierStr == "var")
      return tok_var;
    return tok_identifier;
  }

  if (isdigit(LastChar) || LastChar == '.') { // Число: [0-9.]+
    std::string NumStr;
    do {
      NumStr += LastChar;
      LastChar = getchar();
    } while (isdigit(LastChar) || LastChar == '.');

    NumVal = strtod(NumStr.c_str(), nullptr);
    return tok_number;
  }

  if (LastChar == '#') {
    // Комментарий до конца строки
    do
      LastChar = getchar();
    while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');

    if (LastChar != EOF)
      return gettok();
  }

  // Проверяем конец файла.  Не съедаем EOF.
  if (LastChar == EOF)
    return tok_eof;

  // Иначе, возвращаем символ как его ascii-значение.
  int ThisChar = LastChar;
  LastChar = getchar();
  return ThisChar;
}

//===----------------------------------------------------------------------===//
// Абстрактное Синтаксическое Дерево (Дерево парсинга)
//===----------------------------------------------------------------------===//

namespace {

/// ExprAST - Базовый класс узла выражения.
class ExprAST {
public:
  virtual ~ExprAST() = default;

  virtual Value *codegen() = 0;
};

/// NumberExprAST - Класс выражения для числового литерала "1.0".
class NumberExprAST : public ExprAST {
  double Val;

public:
  NumberExprAST(double Val) : Val(Val) {}

  Value *codegen() override;
};

/// VariableExprAST -Класс выражения для переменной, например, "a".
class VariableExprAST : public ExprAST {
  std::string Name;

public:
  VariableExprAST(const std::string &Name) : Name(Name) {}

  Value *codegen() override;
  const std::string &getName() const { return Name; }
};

/// UnaryExprAST - Класс выражения для унарного оператора
class UnaryExprAST : public ExprAST {
  char Opcode;
  std::unique_ptr<ExprAST> Operand;

public:
  UnaryExprAST(char Opcode, std::unique_ptr<ExprAST> Operand)
      : Opcode(Opcode), Operand(std::move(Operand)) {}

  Value *codegen() override;
};

/// BinaryExprAST - Класс выражения для бинарного оператора
class BinaryExprAST : public ExprAST {
  char Op;
  std::unique_ptr<ExprAST> LHS, RHS;

public:
  BinaryExprAST(char Op, std::unique_ptr<ExprAST> LHS,
                std::unique_ptr<ExprAST> RHS)
      : Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}

  Value *codegen() override;
};

/// CallExprAST - Класс выражения для вызова функции
class CallExprAST : public ExprAST {
  std::string Callee;
  std::vector<std::unique_ptr<ExprAST>> Args;

public:
  CallExprAST(const std::string &Callee,
              std::vector<std::unique_ptr<ExprAST>> Args)
      : Callee(Callee), Args(std::move(Args)) {}

  Value *codegen() override;
};

/// IfExprAST - Класс выражения для if/then/else.
class IfExprAST : public ExprAST {
  std::unique_ptr<ExprAST> Cond, Then, Else;

public:
  IfExprAST(std::unique_ptr<ExprAST> Cond, std::unique_ptr<ExprAST> Then,
            std::unique_ptr<ExprAST> Else)
      : Cond(std::move(Cond)), Then(std::move(Then)), Else(std::move(Else)) {}

  Value *codegen() override;
};

/// ForExprAST - Класс выражения для for/in.
class ForExprAST : public ExprAST {
  std::string VarName;
  std::unique_ptr<ExprAST> Start, End, Step, Body;

public:
  ForExprAST(const std::string &VarName, std::unique_ptr<ExprAST> Start,
             std::unique_ptr<ExprAST> End, std::unique_ptr<ExprAST> Step,
             std::unique_ptr<ExprAST> Body)
      : VarName(VarName), Start(std::move(Start)), End(std::move(End)),
        Step(std::move(Step)), Body(std::move(Body)) {}

  Value *codegen() override;
};

/// VarExprAST - Класс выражения для var/in
class VarExprAST : public ExprAST {
  std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames;
  std::unique_ptr<ExprAST> Body;

public:
  VarExprAST(
      std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames,
      std::unique_ptr<ExprAST> Body)
      : VarNames(std::move(VarNames)), Body(std::move(Body)) {}

  Value *codegen() override;
};

/// PrototypeAST - Этот класс представляет "прототип" функции,
/// и захватывает её имя, и имена аргументов (и, неявно, количество
/// аргументов, принимаемых функцией), а также оператор.
class PrototypeAST {
  std::string Name;
  std::vector<std::string> Args;
  bool IsOperator;
  unsigned Precedence; // Precedence if a binary op.

public:
  PrototypeAST(const std::string &Name, std::vector<std::string> Args,
               bool IsOperator = false, unsigned Prec = 0)
      : Name(Name), Args(std::move(Args)), IsOperator(IsOperator),
        Precedence(Prec) {}

  Function *codegen();
  const std::string &getName() const { return Name; }

  bool isUnaryOp() const { return IsOperator && Args.size() == 1; }
  bool isBinaryOp() const { return IsOperator && Args.size() == 2; }

  char getOperatorName() const {
    assert(isUnaryOp() || isBinaryOp());
    return Name[Name.size() - 1];
  }

  unsigned getBinaryPrecedence() const { return Precedence; }
};

/// FunctionAST - Этот класс представляет определение функции
class FunctionAST {
  std::unique_ptr<PrototypeAST> Proto;
  std::unique_ptr<ExprAST> Body;

public:
  FunctionAST(std::unique_ptr<PrototypeAST> Proto,
              std::unique_ptr<ExprAST> Body)
      : Proto(std::move(Proto)), Body(std::move(Body)) {}

  Function *codegen();
};

} // конец анонимного пространства имен

//===----------------------------------------------------------------------===//
// Парсер
//===----------------------------------------------------------------------===//

/// CurTok/getNextToken - Представляет простой буфер токенов.  CurTok - текущий
/// токен, на котороый смотрит парсер.  getNextToken считывает другой токен из 
/// лексического анализатора и обновляет CurTok считанным результатом.
static int CurTok;
static int getNextToken() { return CurTok = gettok(); }

/// BinopPrecedence - Содержит приоритет каждого бинарного оператора,
/// который определён
static std::map<char, int> BinopPrecedence;

/// GetTokPrecedence - Возвращает приоритет бинарного оператора для текущего токена.
static int GetTokPrecedence() {
  if (!isascii(CurTok))
    return -1;

  // Убедимся, что бинарный оператор объявлен
  int TokPrec = BinopPrecedence[CurTok];
  if (TokPrec <= 0)
    return -1;
  return TokPrec;
}

/// Error* - Маленькая вспомогательная функция обработки ошибок.
std::unique_ptr<ExprAST> LogError(const char *Str) {
  fprintf(stderr, "Error: %s\n", Str);
  return nullptr;
}

std::unique_ptr<PrototypeAST> LogErrorP(const char *Str) {
  LogError(Str);
  return nullptr;
}

static std::unique_ptr<ExprAST> ParseExpression();

/// numberexpr ::= number
static std::unique_ptr<ExprAST> ParseNumberExpr() {
  auto Result = llvm::make_unique<NumberExprAST>(NumVal);
  getNextToken(); // съедаем число
  return std::move(Result);
}

/// parenexpr ::= '(' expression ')'
static std::unique_ptr<ExprAST> ParseParenExpr() {
  getNextToken(); // съедаем (.
  auto V = ParseExpression();
  if (!V)
    return nullptr;

  if (CurTok != ')')
    return LogError("expected ')'");
  getNextToken(); // съедаем ).
  return V;
}

/// identifierexpr
///   ::= identifier
///   ::= identifier '(' expression* ')'
static std::unique_ptr<ExprAST> ParseIdentifierExpr() {
  std::string IdName = IdentifierStr;

  getNextToken(); // // съедаем идентификатор.

  if (CurTok != '(') // Простая ссылка на переменную
    return llvm::make_unique<VariableExprAST>(IdName);

  // Вызов
  getNextToken(); // съедаем (
  std::vector<std::unique_ptr<ExprAST>> Args;
  if (CurTok != ')') {
    while (true) {
      if (auto Arg = ParseExpression())
        Args.push_back(std::move(Arg));
      else
        return nullptr;

      if (CurTok == ')')
        break;

      if (CurTok != ',')
        return LogError("Expected ')' or ',' in argument list");
      getNextToken();
    }
  }

  // Съедаем ')'.
  getNextToken();

  return llvm::make_unique<CallExprAST>(IdName, std::move(Args));
}

/// ifexpr ::= 'if' expression 'then' expression 'else' expression
static std::unique_ptr<ExprAST> ParseIfExpr() {
  getNextToken(); // съедаем if.

  // условие.
  auto Cond = ParseExpression();
  if (!Cond)
    return nullptr;

  if (CurTok != tok_then)
    return LogError("expected then");
  getNextToken(); // съедаем then

  auto Then = ParseExpression();
  if (!Then)
    return nullptr;

  if (CurTok != tok_else)
    return LogError("expected else");

  getNextToken();

  auto Else = ParseExpression();
  if (!Else)
    return nullptr;

  return llvm::make_unique<IfExprAST>(std::move(Cond), std::move(Then),
                                      std::move(Else));
}

/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
static std::unique_ptr<ExprAST> ParseForExpr() {
  getNextToken(); // съедаем for.

  if (CurTok != tok_identifier)
    return LogError("expected identifier after for");

  std::string IdName = IdentifierStr;
  getNextToken(); // съедаем идентификатор.

  if (CurTok != '=')
    return LogError("expected '=' after for");
  getNextToken(); // съедаем '='.

  auto Start = ParseExpression();
  if (!Start)
    return nullptr;
  if (CurTok != ',')
    return LogError("expected ',' after for start value");
  getNextToken();

  auto End = ParseExpression();
  if (!End)
    return nullptr;

  // Значение шага опционально.
  std::unique_ptr<ExprAST> Step;
  if (CurTok == ',') {
    getNextToken();
    Step = ParseExpression();
    if (!Step)
      return nullptr;
  }

  if (CurTok != tok_in)
    return LogError("expected 'in' after for");
  getNextToken(); // съедаем 'in'.

  auto Body = ParseExpression();
  if (!Body)
    return nullptr;

  return llvm::make_unique<ForExprAST>(IdName, std::move(Start), std::move(End),
                                       std::move(Step), std::move(Body));
}

/// varexpr ::= 'var' identifier ('=' expression)?
//                    (',' identifier ('=' expression)?)* 'in' expression
static std::unique_ptr<ExprAST> ParseVarExpr() {
  getNextToken(); // съедаем var.

  std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames;

  // Требуется как минимум одна переменная
  if (CurTok != tok_identifier)
    return LogError("expected identifier after var");

  while (true) {
    std::string Name = IdentifierStr;
    getNextToken(); // съедаем идентификатор.

    // Считываем опциональный инициализатор
    std::unique_ptr<ExprAST> Init = nullptr;
    if (CurTok == '=') {
      getNextToken(); // съедаем '='.

      Init = ParseExpression();
      if (!Init)
        return nullptr;
    }

    VarNames.push_back(std::make_pair(Name, std::move(Init)));

    // Конец списка переменных, выход из цикла.
    if (CurTok != ',')
      break;
    getNextToken(); // съедаем ','.

    if (CurTok != tok_identifier)
      return LogError("expected identifier list after var");
  }

  // в этой точке должно быть ключевое слово 'in'.
  if (CurTok != tok_in)
    return LogError("expected 'in' keyword after 'var'");
  getNextToken(); // съедаем 'in'.

  auto Body = ParseExpression();
  if (!Body)
    return nullptr;

  return llvm::make_unique<VarExprAST>(std::move(VarNames), std::move(Body));
}

/// primary
///   ::= identifierexpr
///   ::= numberexpr
///   ::= parenexpr
///   ::= ifexpr
///   ::= forexpr
///   ::= varexpr
static std::unique_ptr<ExprAST> ParsePrimary() {
  switch (CurTok) {
  default:
    return LogError("unknown token when expecting an expression");
  case tok_identifier:
    return ParseIdentifierExpr();
  case tok_number:
    return ParseNumberExpr();
  case '(':
    return ParseParenExpr();
  case tok_if:
    return ParseIfExpr();
  case tok_for:
    return ParseForExpr();
  case tok_var:
    return ParseVarExpr();
  }
}

/// unary
///   ::= primary
///   ::= '!' unary
static std::unique_ptr<ExprAST> ParseUnary() {
  // если текущий токен не является оператором, он должен быть первичным выражением.
  if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
    return ParsePrimary();

  // если это унарный оператор, считываем его
  int Opc = CurTok;
  getNextToken();
  if (auto Operand = ParseUnary())
    return llvm::make_unique<UnaryExprAST>(Opc, std::move(Operand));
  return nullptr;
}

/// binoprhs
///   ::= ('+' unary)*
static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
                                              std::unique_ptr<ExprAST> LHS) {
  // Если это бинарный оператор, находим его приоритет
  while (true) {
    int TokPrec = GetTokPrecedence();

    // Если это бинарный оператор, связанный с текущим
    // съедаем его, иначе выходим
    if (TokPrec < ExprPrec)
      return LHS;

    // Теперь мы знаем, что это бинарный оператор
    int BinOp = CurTok;
    getNextToken(); // съедаем бинарный оператор

    // Парсим унарное выражение после бинарного оператора
    auto RHS = ParseUnary();
    if (!RHS)
      return nullptr;

    // Если BinOp меньше связан с RHS, чем оператор после RHS, пусть
    // сохранённый оператор примет RHS как свой LHS.
    int NextPrec = GetTokPrecedence();
    if (TokPrec < NextPrec) {
      RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS));
      if (!RHS)
        return nullptr;
    }

    // Объединяем LHS/RHS.
    LHS =
        llvm::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS));
  }
}

/// expression
///   ::= unary binoprhs
///
static std::unique_ptr<ExprAST> ParseExpression() {
  auto LHS = ParseUnary();
  if (!LHS)
    return nullptr;

  return ParseBinOpRHS(0, std::move(LHS));
}

/// prototype
///   ::= id '(' id* ')'
///   ::= binary LETTER number? (id, id)
///   ::= unary LETTER (id)
static std::unique_ptr<PrototypeAST> ParsePrototype() {
  std::string FnName;

  unsigned Kind = 0; // 0 = идентификатор, 1 = унарный, 2 = бинарный.
  unsigned BinaryPrecedence = 30;

  switch (CurTok) {
  default:
    return LogErrorP("Expected function name in prototype");
  case tok_identifier:
    FnName = IdentifierStr;
    Kind = 0;
    getNextToken();
    break;
  case tok_unary:
    getNextToken();
    if (!isascii(CurTok))
      return LogErrorP("Expected unary operator");
    FnName = "unary";
    FnName += (char)CurTok;
    Kind = 1;
    getNextToken();
    break;
  case tok_binary:
    getNextToken();
    if (!isascii(CurTok))
      return LogErrorP("Expected binary operator");
    FnName = "binary";
    FnName += (char)CurTok;
    Kind = 2;
    getNextToken();

    // Считываем приоритет, если он есть
    if (CurTok == tok_number) {
      if (NumVal < 1 || NumVal > 100)
        return LogErrorP("Invalid precedence: must be 1..100");
      BinaryPrecedence = (unsigned)NumVal;
      getNextToken();
    }
    break;
  }

  if (CurTok != '(')
    return LogErrorP("Expected '(' in prototype");

  std::vector<std::string> ArgNames;
  while (getNextToken() == tok_identifier)
    ArgNames.push_back(IdentifierStr);
  if (CurTok != ')')
    return LogErrorP("Expected ')' in prototype");

  // успех.
  getNextToken(); // съедаем ')'.

  // Проверяем, что количество аргументов правильно
  if (Kind && ArgNames.size() != Kind)
    return LogErrorP("Invalid number of operands for operator");

  return llvm::make_unique<PrototypeAST>(FnName, ArgNames, Kind != 0,
                                         BinaryPrecedence);
}

/// definition ::= 'def' prototype expression
static std::unique_ptr<FunctionAST> ParseDefinition() {
  getNextToken(); // // съедаем def.
  auto Proto = ParsePrototype();
  if (!Proto)
    return nullptr;

  if (auto E = ParseExpression())
    return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E));
  return nullptr;
}

/// toplevelexpr ::= expression
static std::unique_ptr<FunctionAST> ParseTopLevelExpr() {
  if (auto E = ParseExpression()) {
    // Создаём анонимный прототип
    auto Proto = llvm::make_unique<PrototypeAST>("__anon_expr",
                                                 std::vector<std::string>());
    return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E));
  }
  return nullptr;
}

/// external ::= 'extern' prototype
static std::unique_ptr<PrototypeAST> ParseExtern() {
  getNextToken(); // съедаем extern.
  return ParsePrototype();
}

//===----------------------------------------------------------------------===//
// Генерация кода
//===----------------------------------------------------------------------===//

static LLVMContext TheContext;
static IRBuilder<> Builder(TheContext);
static std::unique_ptr<Module> TheModule;
static std::map<std::string, AllocaInst *> NamedValues;
static std::map<std::string, std::unique_ptr<PrototypeAST>> FunctionProtos;

Value *LogErrorV(const char *Str) {
  LogError(Str);
  return nullptr;
}

Function *getFunction(std::string Name) {
  // Вначале проверяем, добавлена ли уже функция в текущий модуль.
  if (auto *F = TheModule->getFunction(Name))
    return F;

  // Если нет, можем ли мы сгенерировать код из существующих объявлений
  // прототипа.
  auto FI = FunctionProtos.find(Name);
  if (FI != FunctionProtos.end())
    return FI->second->codegen();

  // Если нет существующего прототипа, возвращаем null.
  return nullptr;
}

/// CreateEntryBlockAlloca - Создаём инструкцию alloca во входном блоке
/// функции.  Она используется для изменяемых переменных.
static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,
                                          const std::string &VarName) {
  IRBuilder<> TmpB(&TheFunction->getEntryBlock(),
                   TheFunction->getEntryBlock().begin());
  return TmpB.CreateAlloca(Type::getDoubleTy(TheContext), nullptr, VarName);
}

Value *NumberExprAST::codegen() {
  return ConstantFP::get(TheContext, APFloat(Val));
}

Value *VariableExprAST::codegen() {
  // Смотрим, есть ли эта переменная в функции
  Value *V = NamedValues[Name];
  if (!V)
    return LogErrorV("Unknown variable name");

  // Загружаем значение
  return Builder.CreateLoad(V, Name.c_str());
}

Value *UnaryExprAST::codegen() {
  Value *OperandV = Operand->codegen();
  if (!OperandV)
    return nullptr;

  Function *F = getFunction(std::string("unary") + Opcode);
  if (!F)
    return LogErrorV("Unknown unary operator");

  return Builder.CreateCall(F, OperandV, "unop");
}

Value *BinaryExprAST::codegen() {
  // Особый случай для '=', т.к. мы не хотим генерировать LHS как выражение
  if (Op == '=') {
    // Присваивание требует, чтобы LHS было идентификатором
    // Подразумевается, что мы компилируем без RTTI, т.к. LLVM компилируется так
    // по умолчанию.  Если вы компилируете LLVM с RTTI здесь надо поменять на
    // dynamic_cast для автоматической проверки ошибок.
    VariableExprAST *LHSE = static_cast<VariableExprAST *>(LHS.get());
    if (!LHSE)
      return LogErrorV("destination of '=' must be a variable");
    // Генерируем код RHS.
    Value *Val = RHS->codegen();
    if (!Val)
      return nullptr;

    // Находим имя
    Value *Variable = NamedValues[LHSE->getName()];
    if (!Variable)
      return LogErrorV("Unknown variable name");

    Builder.CreateStore(Val, Variable);
    return Val;
  }

  Value *L = LHS->codegen();
  Value *R = RHS->codegen();
  if (!L || !R)
    return nullptr;

  switch (Op) {
  case '+':
    return Builder.CreateFAdd(L, R, "addtmp");
  case '-':
    return Builder.CreateFSub(L, R, "subtmp");
  case '*':
    return Builder.CreateFMul(L, R, "multmp");
  case '<':
    L = Builder.CreateFCmpULT(L, R, "cmptmp");
    // Преобразуем bool 0/1 в double 0.0 or 1.0
    return Builder.CreateUIToFP(L, Type::getDoubleTy(TheContext), "booltmp");
  default:
    break;
  }

  // Если это не встроенный бинарный оператор, он должен быть определён пользователем. Генерируем
  // вызов функции для него.
  Function *F = getFunction(std::string("binary") + Op);
  assert(F && "binary operator not found!");

  Value *Ops[] = {L, R};
  return Builder.CreateCall(F, Ops, "binop");
}

Value *CallExprAST::codegen() {
  // Ищем имя в глобальной таблице модуля
  Function *CalleeF = getFunction(Callee);
  if (!CalleeF)
    return LogErrorV("Unknown function referenced");

  // Ошибка, если аргументы не совпадают.
  if (CalleeF->arg_size() != Args.size())
    return LogErrorV("Incorrect # arguments passed");

  std::vector<Value *> ArgsV;
  for (unsigned i = 0, e = Args.size(); i != e; ++i) {
    ArgsV.push_back(Args[i]->codegen());
    if (!ArgsV.back())
      return nullptr;
  }

  return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
}

Value *IfExprAST::codegen() {
  Value *CondV = Cond->codegen();
  if (!CondV)
    return nullptr;

  // Преобразуем условие в булево значение путём проверки на неравенство 0.0.
  CondV = Builder.CreateFCmpONE(
      CondV, ConstantFP::get(TheContext, APFloat(0.0)), "ifcond");

  Function *TheFunction = Builder.GetInsertBlock()->getParent();

  // Создаём блоки для then и else.  Вставляем блок 'then' в
  // конец функции
  BasicBlock *ThenBB = BasicBlock::Create(TheContext, "then", TheFunction);
  BasicBlock *ElseBB = BasicBlock::Create(TheContext, "else");
  BasicBlock *MergeBB = BasicBlock::Create(TheContext, "ifcont");

  Builder.CreateCondBr(CondV, ThenBB, ElseBB);

  // Генерируем значение.
  Builder.SetInsertPoint(ThenBB);

  Value *ThenV = Then->codegen();
  if (!ThenV)
    return nullptr;

  Builder.CreateBr(MergeBB);
// Генерация кода для 'Then' может изменить текущий блок, обновляем ThenBB для PHI.
  ThenBB = Builder.GetInsertBlock();

  // Генерируем блок "else"
  TheFunction->getBasicBlockList().push_back(ElseBB);
  Builder.SetInsertPoint(ElseBB);

  Value *ElseV = Else->codegen();
  if (!ElseV)
    return nullptr;

  Builder.CreateBr(MergeBB);
  // Генерация кода для 'Else' может изменить текущий блок, обновляем ElseBB для PHI.
  ElseBB = Builder.GetInsertBlock();

  // Генерируем объединяющий блок
  TheFunction->getBasicBlockList().push_back(MergeBB);
  Builder.SetInsertPoint(MergeBB);
  PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(TheContext), 2, "iftmp");

  PN->addIncoming(ThenV, ThenBB);
  PN->addIncoming(ElseV, ElseBB);
  return PN;
}

// Выводим for-loop как:
//   var = alloca double
//   ...
//   start = startexpr
//   store start -> var
//   goto loop
// loop:
//   ...
//   bodyexpr
//   ...
// loopend:
//   step = stepexpr
//   endcond = endexpr
//
//   curvar = load var
//   nextvar = curvar + step
//   store nextvar -> var
//   br endcond, loop, endloop
// outloop:
Value *ForExprAST::codegen() {
  Function *TheFunction = Builder.GetInsertBlock()->getParent();

  // Создаем инструкцию alloca для переменной в начальном блоке
  AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);

  // Генерируем вначале стартовый код, без 'variable' в области видимости
  Value *StartVal = Start->codegen();
  if (!StartVal)
    return nullptr;

  // Сохраняем значение в alloca.
  Builder.CreateStore(StartVal, Alloca);

  // Создаём новый базовый блок для заголовка цикла, вставляем его после текущего
  // блока.
  BasicBlock *LoopBB = BasicBlock::Create(TheContext, "loop", TheFunction);

  // Вставляем явный переход с текущего блока в LoopBB.
  Builder.CreateBr(LoopBB);

  // Начинаем вставку в LoopBB.
  Builder.SetInsertPoint(LoopBB);

  // Внутри цикла, переменная определена равной PHI-узлу. Если она
  // перекрыта существующей переменной, мы должны восстановить её, сохраним её сейчас.
  AllocaInst *OldVal = NamedValues[VarName];
  NamedValues[VarName] = Alloca;

  // Генерируем тело цикла.  Оно, как любое другое выражение, может изменить
  // текущий BB. Отметим, что мы игнорируем значение, вычисленное телом цикла, но не
  // допускаем ошибки.
  if (!Body->codegen())
    return nullptr;

  // Генерируем значение шага
  Value *StepVal = nullptr;
  if (Step) {
    StepVal = Step->codegen();
    if (!StepVal)
      return nullptr;
  } else {
    // Если не определено, используем 1.0.
    StepVal = ConstantFP::get(TheContext, APFloat(1.0));
  }

  // Вычисляем условие конца
  Value *EndCond = End->codegen();
  if (!EndCond)
    return nullptr;

  // Загружаем, инкрементируем, и сохраняем alloca.  Обрабатываем случай
  // когда переменная цикла изменяется в теле цикла
  Value *CurVar = Builder.CreateLoad(Alloca, VarName.c_str());
  Value *NextVar = Builder.CreateFAdd(CurVar, StepVal, "nextvar");
  Builder.CreateStore(NextVar, Alloca);

  // Преобразуем условие в булевое значение путём проверки на неравенство 0.0.
  EndCond = Builder.CreateFCmpONE(
      EndCond, ConstantFP::get(TheContext, APFloat(0.0)), "loopcond");

  // Создаём блок "после цикла" и вставляем его
  BasicBlock *AfterBB =
      BasicBlock::Create(TheContext, "afterloop", TheFunction);

  // Вставляем условный переход в конец LoopEndBB.
  Builder.CreateCondBr(EndCond, LoopBB, AfterBB);

 // Любой новый код будет вставляться в AfterBB.
  Builder.SetInsertPoint(AfterBB);

  // Восстанавливаем ранее скрытую переменную.
  if (OldVal)
    NamedValues[VarName] = OldVal;
  else
    NamedValues.erase(VarName);

  // выражение всегда возвращает 0.0.
  return Constant::getNullValue(Type::getDoubleTy(TheContext));
}

Value *VarExprAST::codegen() {
  std::vector<AllocaInst *> OldBindings;

  Function *TheFunction = Builder.GetInsertBlock()->getParent();

  // Регистрируем все переменные и ненерируем инициализаторы
  for (unsigned i = 0, e = VarNames.size(); i != e; ++i) {
    const std::string &VarName = VarNames[i].first;
    ExprAST *Init = VarNames[i].second.get();

    // Генерируем инициализатор перед добавлением переменной, это предотвращает
    // инициализатор от ссылки на саму переменную, и разрешает
    // l такие вещи:
    //  var a = 1 in
    //    var a = a in ...   # ссылка на внешнюю 'a'.
    Value *InitVal;
    if (Init) {
      InitVal = Init->codegen();
      if (!InitVal)
        return nullptr;
    } else { // если значение не указано, используем 0.0.
      InitVal = ConstantFP::get(TheContext, APFloat(0.0));
    }

    AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
    Builder.CreateStore(InitVal, Alloca);

        // Запоминаем связку переменных

    OldBindings.push_back(NamedValues[VarName]);

    // Запоминаем связку
    NamedValues[VarName] = Alloca;
  }

  // Генерируем тело цикла со всеми переменными
  Value *BodyVal = Body->codegen();
  if (!BodyVal)
    return nullptr;

  // Извлекаем все переменные
  for (unsigned i = 0, e = VarNames.size(); i != e; ++i)
    NamedValues[VarNames[i].first] = OldBindings[i];

  // Возвращаем значение тела цикла
  return BodyVal;
}

Function *PrototypeAST::codegen() {
  // Создаём тип функции:  double(double,double) etc.
  std::vector<Type *> Doubles(Args.size(), Type::getDoubleTy(TheContext));
  FunctionType *FT =
      FunctionType::get(Type::getDoubleTy(TheContext), Doubles, false);

  Function *F =
      Function::Create(FT, Function::ExternalLinkage, Name, TheModule.get());

  // Устанавливаем имена аргументов
  unsigned Idx = 0;
  for (auto &Arg : F->args())
    Arg.setName(Args[Idx++]);

  return F;
}

Function *FunctionAST::codegen() {
  // Переносим владение прототипом в мэп FunctionProtos, но сохраняем
  // ссылку для дальнейшего использования.
  auto &P = *Proto;
  FunctionProtos[Proto->getName()] = std::move(Proto);
  Function *TheFunction = getFunction(P.getName());
  if (!TheFunction)
    return nullptr;

  // Если это оператор, устанавливаем его
  if (P.isBinaryOp())
    BinopPrecedence[P.getOperatorName()] = P.getBinaryPrecedence();

  // Создаём новый базовый блок для вставки кода
  BasicBlock *BB = BasicBlock::Create(TheContext, "entry", TheFunction);
  Builder.SetInsertPoint(BB);

  // Записываем аргументы функции в таблицу NamedValues.
  NamedValues.clear();
  for (auto &Arg : TheFunction->args()) {
    // Создаем инструкцию alloca для переменной
    AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, Arg.getName());

    // Сохраняем начальное значение в alloca.
    Builder.CreateStore(&Arg, Alloca);

    // Добавляем аргументы к таблице символов
    NamedValues[Arg.getName()] = Alloca;
  }

  if (Value *RetVal = Body->codegen()) {
    // Завершаем функцию.
    Builder.CreateRet(RetVal);

    // Проверяем сгенерированный код
    verifyFunction(*TheFunction);

    return TheFunction;
  }

  // Ошибка чтения тела функции, удаляем функцию
  TheFunction->eraseFromParent();

  if (P.isBinaryOp())
    BinopPrecedence.erase(P.getOperatorName());
  return nullptr;
}

//===----------------------------------------------------------------------===//
// Высокоуровневый парсинг и драйвер JIT
//===----------------------------------------------------------------------===//

static void InitializeModuleAndPassManager() {
  // Открываем новый модуль
  TheModule = llvm::make_unique<Module>("my cool jit", TheContext);
}

static void HandleDefinition() {
  if (auto FnAST = ParseDefinition()) {
    if (auto *FnIR = FnAST->codegen()) {
      fprintf(stderr, "Read function definition:");
      FnIR->print(errs());
      fprintf(stderr, "\n");
    }
  } else {
    // Пропускаем токен для восстановления после ошибки
    getNextToken();
  }
}

static void HandleExtern() {
  if (auto ProtoAST = ParseExtern()) {
    if (auto *FnIR = ProtoAST->codegen()) {
      fprintf(stderr, "Read extern: ");
      FnIR->print(errs());
      fprintf(stderr, "\n");
      FunctionProtos[ProtoAST->getName()] = std::move(ProtoAST);
    }
  } else {
    // Пропускаем токен для восстановления после ошибки
    getNextToken();
  }
}

static void HandleTopLevelExpression() {
  // Evaluate a top-level expression into an anonymous function.
  if (auto FnAST = ParseTopLevelExpr()) {
    FnAST->codegen();
  } else {
    // Пропускаем токен для восстановления после ошибки
    getNextToken();
  }
}

/// top ::= definition | external | expression | ';'
static void MainLoop() {
  while (true) {
    switch (CurTok) {
    case tok_eof:
      return;
    case ';': // игнорируем точки с запятой на верхнем уровне
      getNextToken();
      break;
    case tok_def:
      HandleDefinition();
      break;
    case tok_extern:
      HandleExtern();
      break;
    default:
      HandleTopLevelExpression();
      break;
    }
  }
}

//===----------------------------------------------------------------------===//
// "Библиотечные" функции, которые должны быть внешними для пользовательского кода
//===----------------------------------------------------------------------===//

#ifdef LLVM_ON_WIN32
#define DLLEXPORT __declspec(dllexport)
#else
#define DLLEXPORT
#endif

/// putchard - putchar, принимает double, возвращает 0.
extern "C" DLLEXPORT double putchard(double X) {
  fputc((char)X, stderr);
  return 0;
}

/// printd - printf, принимает double печатает его как"%f\n", возвращает 0.
extern "C" DLLEXPORT double printd(double X) {
  fprintf(stderr, "%f\n", X);
  return 0;
}

//===----------------------------------------------------------------------===//
// Код main
//===----------------------------------------------------------------------===//

int main() {
  // Устанавливаем стандартные бинарные операторы
  // 1 - самый низкий приоритет
  BinopPrecedence['<'] = 10;
  BinopPrecedence['+'] = 20;
  BinopPrecedence['-'] = 20;
  BinopPrecedence['*'] = 40; // самый высокий.

  // Обрабатываем первый токен
  fprintf(stderr, "ready> ");
  getNextToken();

  InitializeModuleAndPassManager();

  // Запускаем цикл интерпретации
  MainLoop();

  // Инициализируем таргет
  InitializeAllTargetInfos();
  InitializeAllTargets();
  InitializeAllTargetMCs();
  InitializeAllAsmParsers();
  InitializeAllAsmPrinters();

  auto TargetTriple = sys::getDefaultTargetTriple();
  TheModule->setTargetTriple(TargetTriple);

  std::string Error;
  auto Target = TargetRegistry::lookupTarget(TargetTriple, Error);

  // Печатаем ошибку и выходим, если мы не можем найти запрошенный таргет
  // Это обычно происходит, если мы забыли проинициализировать
  // TargetRegistry или неверно указана тройка цели
  if (!Target) {
    errs() << Error;
    return 1;
  }

  auto CPU = "generic";
  auto Features = "";

  TargetOptions opt;
  auto RM = Optional<Reloc::Model>();
  auto TheTargetMachine =
      Target->createTargetMachine(TargetTriple, CPU, Features, opt, RM);

  TheModule->setDataLayout(TheTargetMachine->createDataLayout());

  auto Filename = "output.o";
  std::error_code EC;
  raw_fd_ostream dest(Filename, EC, sys::fs::F_None);

  if (EC) {
    errs() << "Could not open file: " << EC.message();
    return 1;
  }

  legacy::PassManager pass;
  auto FileType = TargetMachine::CGFT_ObjectFile;

  if (TheTargetMachine->addPassesToEmitFile(pass, dest, FileType)) {
    errs() << "TheTargetMachine can't emit a file of this type";
    return 1;
  }

  pass.run(*TheModule);
  dest.flush();

  outs() << "Wrote " << Filename << "\n";

  return 0;
}

Tags:
Hubs:
+26
Comments 0
Comments Leave a comment

Articles