Оглавление:

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

9.1. Введение


Добро пожаловать в главу 9 руководства “Создание языка программирования с использованием LLVM”. В главах с 1 по 8, мы построили маленький язык программирования с функциями и переменными. Что случится, если что-то пойдёт не так, как тогда отлаживать программу?

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

Краткое резюме этой главы состоит в том, что мы рассмотрим различные вещи, которые вы должны добавить в язык программирования для поддержки отладочной информации, и как преобразовать её в DWARF.

Предупреждение: сейчас мы не сможем отлаживать в режиме JIT, нам нужно будет скомпилировать нашу программу. Мы сделаем несколько изменений, касающихся как работы языка, так и компиляции. Сейчас у нас будет происходить компиляция из исходного файла на языке Калейдоскоп, а не JIT-исполнение в интерактивном режиме. Введём ограничение, заключающееся в том, что у нас будет только одна команда на «верхнем уровне», для того, чтобы уменьшить количество необходимых изменений.

Пример программы, которую мы будем компилировать:

def fib(x)
  if x < 3 then
    1
  else
    fib(x-1)+fib(x-2);

fib(10)

9.2. Почему это трудная задача?


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

9.3. Режим компиляции AOT (Ahead-of-Time Compilation)


Мы осветим только аспекты добавления отладочной информации в исходный язык, и не будем беспокоиться о сложностях отладки в режиме JIT, и мы сделаем несколько изменений в Калейдоскопе для поддержки компиляции IR, сгенерированного фронтендом в самостоятельную программу, которую можно выполнить, отладить, и увидеть результат.

Вначале сделаем, чтобы анонимная функция, которая содержит верхний уровень кода, называлась «main»:

-    auto Proto = llvm::make_unique<PrototypeAST>("", std::vector<std::string>());
+    auto Proto = llvm::make_unique<PrototypeAST>("main", std::vector<std::string>());

это маленькое изменение даёт функции имя.

Затем мы удаляем весь код, относящийся к командной строке:

@@ -1129,7 +1129,6 @@ static void HandleTopLevelExpression() {
 /// top ::= definition | external | expression | ';'
 static void MainLoop() {
   while (1) {
-    fprintf(stderr, "ready> ");
     switch (CurTok) {
     case tok_eof:
       return;
@@ -1184,7 +1183,6 @@ int main() {
   BinopPrecedence['*'] = 40; // самый высокий приоритет.

   // Первый токен является первичным
-  fprintf(stderr, "ready> ");
   getNextToken();

И наконец, мы выключаем все проходы оптимизации и JIT, так, чтобы остались только парсинг и генерация кода LLVM IR:

@@ -1108,17 +1108,8 @@ static void HandleExtern() {
 static void HandleTopLevelExpression() {
   // Выражение верхнего уровня считается анонимной функцией
   if (auto FnAST = ParseTopLevelExpr()) {
-    if (auto *FnIR = FnAST->codegen()) {
-      // Убеждаемся, что оно выполняется
-      TheExecutionEngine->finalizeObject();
-      // выполняем функцию в JIT, возвращаем указатель на функцию
-      void *FPtr = TheExecutionEngine->getPointerToFunction(FnIR);
-
-      // Преобразуем в нужный тип (не принимает аргументов, возвращает double), так что
-      // мы можем вызывать функцию нативно.
-      double (*FP)() = (double (*)())(intptr_t)FPtr;
-      // Игнорируем возвращаемое значение.
-      (void)FP;
+    if (!F->codegen()) {
+      fprintf(stderr, "Error generating code for top level expr");
     }
   } else {
     // Пропускаем токен для восстановления после ошибки
@@ -1439,11 +1459,11 @@ int main() {
   // модель данных таргета
   TheModule->setDataLayout(TheExecutionEngine->getDataLayout());
   OurFPM.add(new DataLayoutPass());
+#if 0
   OurFPM.add(createBasicAliasAnalysisPass());
   // Преобразуем alloca в регистры
   OurFPM.add(createPromoteMemoryToRegisterPass());
@@ -1218,7 +1210,7 @@ int main() {
   OurFPM.add(createGVNPass());
   // Упрощаем граф потока управления (удаляем недостижимые блоки, итд).
   OurFPM.add(createCFGSimplificationPass());
-
+  #endif
   OurFPM.doInitialization();

Этот относительно маленький набор изменений прииводит нас к точке, в которой мы можем скомпилировать кусок на Калейдоскопе в исполняемую программу с помощью командной строки:

Kaleidoscope-Ch9 < fib.ks | & clang -x ir -

и получить a.out/a.exe в текущей рабочей директории.

9.4. Единица компиляции


Контейнер верхнего уровня для секции кода в DWARF — это единица компиляции (compile unit).
Она содержит данные о типах и функциях для отдельного модуля трансляции (т.е. одного файла модуля трансляции). И первое, что нам нужно, это построить такую единицу для нашего файла fib.ks.

9.5. Настройка генерации DWARF


Аналогично классу IRBuilder, существует класс DIBuilder, который помогает сконструировать метаданные для файла LLVM IR. Он 1:1 соответствует IRBuilder и LLVM IR. Его использование требует, чтобы вы были более знакомы с терминологией DWARF, чем для IRBuilder было необходимо знание названий инструкций, но если вы прочитаете документацию по формату метаданных, то всё станет яснее. Мы будем использовать этот класс для конструирования всех описаний IR-уровня. Их конструирование происходит сразу после того, как мы построили объект модуля. Все эти описания строятся как глобальные статические переменные, потому что так их проще использовать.

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

static DIBuilder *DBuilder;

struct DebugInfo {
  DICompileUnit *TheCU;
  DIType *DblTy;

  DIType *getDoubleTy();
} KSDbgInfo;

DIType *DebugInfo::getDoubleTy() {
  if (DblTy)
    return DblTy;

  DblTy = DBuilder->createBasicType("double", 64, 64, dwarf::DW_ATE_float);
  return DblTy;
}

И затем, далее в функции main создаём модуль:

DBuilder = new DIBuilder(*TheModule);

KSDbgInfo.TheCU = DBuilder->createCompileUnit(
    dwarf::DW_LANG_C, "fib.ks", ".", "Kaleidoscope Compiler", 0, "", 0);

Здесь нужно заметить пару вещей. Во первых, хотя мы создаём единицу компиляции для языка, наываемого Калейдоскоп, мы используем константу языка С. Так происходит потому, что отладчик не обязан понимать соглашение о вызовах или ABI для языков, которые он не опознал, и мы придерживаемся C ABI в нашем генераторе кода. В этом случае мы можем быть уверены, что мы вызываем функцию из отладчика и она выполнится. Во-вторых, вы видите “fib.ks” в вызове createCompileUnit. Это значение по умолчанию, так как мы используем перенаправление команд шеллом для того, чтобы наш исходник попал в компилятор Калейдоскопа. В обычном фронтенде у вас было бы в этом месте имя входного файла.

И последнее, что касается генерации отладочной информации через DIBuilder, это то, что нам нужно «финализировать» отладочную информацию. Причина этого кроется в API DIBuilder-а, и нам нужно сделать это ближе к концу функции main:

DBuilder->finalize();

перед тем, как мы выведем дамп модуля.

9.6. Функции


Сейчас у нас есть наша единица компиляции и наши локации исходного кода, и мы можем добавить определения функций в отладочеую информацию. В PrototypeAST::codegen() мы добавляем несколько строк кода, для того, чтобы описать контекст нашей подпрограммы, в этом случае “File”, и реальное определение самой функции.

Итак, контекст:

DIFile *Unit = DBuilder->createFile(KSDbgInfo.TheCU.getFilename(),
                                    KSDbgInfo.TheCU.getDirectory());

даёт нам DIFile, и запрашивая единицу компиляции, которую мы создали выше для директории и имени файла, где мы в данный момент находимся. Затем, мы используем локации исходного кода для нуля (так как наше AST пока не имеет информации о локациях кода), и конструируем наше определение функции:

DIScope *FContext = Unit;
unsigned LineNo = 0;
unsigned ScopeLine = 0;
DISubprogram *SP = DBuilder->createFunction(
    FContext, P.getName(), StringRef(), Unit, LineNo,
    CreateFunctionType(TheFunction->arg_size(), Unit),
    false /* internal linkage */, true /* definition */, ScopeLine,
    DINode::FlagPrototyped, false);
TheFunction->setSubprogram(SP);

и мы сейчас имеем DISubprogram, содержащую ссылку на все наши метаданные для функции.

9.7. Локации исходного кода


Самая важная вещь для отладочной информации, это точность локаций исходного кода, она даёт возможность обратного нахождения места в исходном коде. Сейчас наша проблема заключается в том, что Калейдоскоп не имеет никакой информации о локациях исходника в лексическом анализаторе и в парсере, и мы должны её добавить.

struct SourceLocation {
  int Line;
  int Col;
};
static SourceLocation CurLoc;
static SourceLocation LexLoc = {1, 0};

static int advance() {
  int LastChar = getchar();

  if (LastChar == '\n' || LastChar == '\r') {
    LexLoc.Line++;
    LexLoc.Col = 0;
  } else
    LexLoc.Col++;
  return LastChar;
}

В этом куске кода мы добавляем функциональность, которая отслеживает строку и столбец исходного файла. По мере лексического разбора каждого токенамы устанавливаем нашу «лексическую локацию» в соответствующую строку и столбец для начала токена. Мы делаем это путём замены всех вызовов getchar() на новую функцию advance(), которая отслеживает информацию и затем мы добавляем ко всем нашим классам AST локацию исходного текста.

class ExprAST {
  SourceLocation Loc;

  public:
    ExprAST(SourceLocation Loc = CurLoc) : Loc(Loc) {}
    virtual ~ExprAST() {}
    virtual Value* codegen() = 0;
    int getLine() const { return Loc.Line; }
    int getCol() const { return Loc.Col; }
    virtual raw_ostream &dump(raw_ostream &out, int ind) {
      return out << ':' << getLine() << ':' << getCol() << '\n';
    }

и мы передаём эти локации, когда создаём новое выражение:

LHS = llvm::make_unique<BinaryExprAST>(BinLoc, BinOp, std::move(LHS),
                                       std::move(RHS));

и локации присваиваются каждому выражению и переменной.

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

void DebugInfo::emitLocation(ExprAST *AST) {
  DIScope *Scope;
  if (LexicalBlocks.empty())
    Scope = TheCU;
  else
    Scope = LexicalBlocks.back();
  Builder.SetCurrentDebugLocation(
      DebugLoc::get(AST->getLine(), AST->getCol(), Scope));
}

Это сообщает объекту IRBuilder где мы находимся, а также, в какой области видимости. Область видимости может быть либо уровня единицы компиляции, либо ближайшим окружающим лексическим блоком, например, текущей функцией. Чтобы представить это, создаём стек областей видимости:

std::vector<DIScope *> LexicalBlocks;

и помещаем область видимости (функцию) на вершину стека когда начинаем генерацию кода для каждой функции:

KSDbgInfo.LexicalBlocks.push_back(SP);

Также мы не должны забывать снять область видимости со стека в конце генерации кода для функции:

// Снимаем со стека лексический блок для функции
KSDbgInfo.LexicalBlocks.pop_back();

Затем мы убеждаемся в том, что сгенерировали локацию каждый раз, когда мы начинаем генерацию кода для нового объекта AST:

KSDbgInfo.emitLocation(this);

9.8. Переменные


Сейчас у нас есть функции, и нам нужна возможность выводить переменные в области видимости. Давайте возьмём набор аргументов нашей функции, и сделаем так, чтобы мы могли проследить и увидеть, как функция была вызвана. Здесь немного кода, и мы производим все действия, когда мы создаём аллокации аргументов в FunctionAST::codegen.

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

  // Создаём отладочный дескриптор для переменной
  DILocalVariable *D = DBuilder->createParameterVariable(
      SP, Arg.getName(), ++ArgIdx, Unit, LineNo, KSDbgInfo.getDoubleTy(),
      true);

  DBuilder->insertDeclare(Alloca, D, DBuilder->createExpression(),
                          DebugLoc::get(LineNo, 0, SP),
                          Builder.GetInsertBlock());

  // Записываем начальное значение в alloca.
  Builder.CreateStore(&Arg, Alloca);

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

Здесь мы впервые создаём переменную, присваиваем ей область видимости (SP), имя, локацию исходного кода, тип, и, если это аргумент, индекс аргумента. Затем мы создаём вызов lvm.dbg.declare для того, чтобы на уровне IR показать, что у нас есть переменная в alloca (и задать стартовую локацию переменной), и устанавливаем локацию исходного текста для начала области видимости.

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

// Не устанавливаем локацию для пролога (инструкции без локации
// в функции рассматриваются как пролог, и отладчик
// будет их пропускать при останове внутри функции
KSDbgInfo.emitLocation(nullptr);

и затем генерируем новую локацию когда мы на самом деле начинаем генерировать код для тела функции:

KSDbgInfo.emitLocation(Body.get());

Сейчас у нас достаточно отладочной информации для установки точки останова в функции, вывода переменных-аргументов функции и вызова функции. Неплохо для всего лишь нескольких строк кода!

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


Ниже приведён полный листинг кода для нашего рабочего примера, расширенный отладочной информацией. Для того, чтобы собрать пример, выполните:

# Компиляция
clang++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core mcjit native` -O3 -o toy
# Запуск
./toy

Полный код

#include "llvm/ADT/STLExtras.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/Passes.h"
#include "llvm/IR/DIBuilder.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/LegacyPassManager.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Support/TargetSelect.h"
#include "llvm/Transforms/Scalar.h"
#include <cctype>
#include <cstdio>
#include <map>
#include <string>
#include <vector>
#include "../include/KaleidoscopeJIT.h"

using namespace llvm;
using namespace llvm::orc;

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

// Лексический анализатор возвращает токены [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
};

std::string getTokName(int Tok) {
  switch (Tok) {
  case tok_eof:
    return "eof";
  case tok_def:
    return "def";
  case tok_extern:
    return "extern";
  case tok_identifier:
    return "identifier";
  case tok_number:
    return "number";
  case tok_if:
    return "if";
  case tok_then:
    return "then";
  case tok_else:
    return "else";
  case tok_for:
    return "for";
  case tok_in:
    return "in";
  case tok_binary:
    return "binary";
  case tok_unary:
    return "unary";
  case tok_var:
    return "var";
  }
  return std::string(1, (char)Tok);
}

namespace {
class PrototypeAST;
class ExprAST;
}
static LLVMContext TheContext;
static IRBuilder<> Builder(TheContext);
struct DebugInfo {
  DICompileUnit *TheCU;
  DIType *DblTy;
  std::vector<DIScope *> LexicalBlocks;

  void emitLocation(ExprAST *AST);
  DIType *getDoubleTy();
} KSDbgInfo;

struct SourceLocation {
  int Line;
  int Col;
};
static SourceLocation CurLoc;
static SourceLocation LexLoc = {1, 0};

static int advance() {
  int LastChar = getchar();

  if (LastChar == '\n' || LastChar == '\r') {
    LexLoc.Line++;
    LexLoc.Col = 0;
  } else
    LexLoc.Col++;
  return LastChar;
}

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

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

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

  CurLoc = LexLoc;

  if (isalpha(LastChar)) { // идентификатор: [a-zA-Z][a-zA-Z0-9]*
    IdentifierStr = LastChar;
    while (isalnum((LastChar = advance())))
      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 = advance();
    } while (isdigit(LastChar) || LastChar == '.');

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

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

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

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

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

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

raw_ostream &indent(raw_ostream &O, int size) {
  return O << std::string(size, ' ');
}

/// ExprAST - Базовый класс узла выражения.
class ExprAST {
  SourceLocation Loc;

public:
  ExprAST(SourceLocation Loc = CurLoc) : Loc(Loc) {}
  virtual ~ExprAST() {}
  virtual Value *codegen() = 0;
  int getLine() const { return Loc.Line; }
  int getCol() const { return Loc.Col; }
  virtual raw_ostream &dump(raw_ostream &out, int ind) {
    return out << ':' << getLine() << ':' << getCol() << '\n';
  }
};

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

public:
  NumberExprAST(double Val) : Val(Val) {}
  raw_ostream &dump(raw_ostream &out, int ind) override {
    return ExprAST::dump(out << Val, ind);
  }
  Value *codegen() override;
};

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

public:
  VariableExprAST(SourceLocation Loc, const std::string &Name)
      : ExprAST(Loc), Name(Name) {}
  const std::string &getName() const { return Name; }
  Value *codegen() override;
  raw_ostream &dump(raw_ostream &out, int ind) override {
    return ExprAST::dump(out << Name, ind);
  }
};

/// 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;
  raw_ostream &dump(raw_ostream &out, int ind) override {
    ExprAST::dump(out << "unary" << Opcode, ind);
    Operand->dump(out, ind + 1);
    return out;
  }
};

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

public:
  BinaryExprAST(SourceLocation Loc, char Op, std::unique_ptr<ExprAST> LHS,
                std::unique_ptr<ExprAST> RHS)
      : ExprAST(Loc), Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}
  Value *codegen() override;
  raw_ostream &dump(raw_ostream &out, int ind) override {
    ExprAST::dump(out << "binary" << Op, ind);
    LHS->dump(indent(out, ind) << "LHS:", ind + 1);
    RHS->dump(indent(out, ind) << "RHS:", ind + 1);
    return out;
  }
};

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

public:
  CallExprAST(SourceLocation Loc, const std::string &Callee,
              std::vector<std::unique_ptr<ExprAST>> Args)
      : ExprAST(Loc), Callee(Callee), Args(std::move(Args)) {}
  Value *codegen() override;
  raw_ostream &dump(raw_ostream &out, int ind) override {
    ExprAST::dump(out << "call " << Callee, ind);
    for (const auto &Arg : Args)
      Arg->dump(indent(out, ind + 1), ind + 1);
    return out;
  }
};

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

public:
  IfExprAST(SourceLocation Loc, std::unique_ptr<ExprAST> Cond,
            std::unique_ptr<ExprAST> Then, std::unique_ptr<ExprAST> Else)
      : ExprAST(Loc), Cond(std::move(Cond)), Then(std::move(Then)),
        Else(std::move(Else)) {}
  Value *codegen() override;
  raw_ostream &dump(raw_ostream &out, int ind) override {
    ExprAST::dump(out << "if", ind);
    Cond->dump(indent(out, ind) << "Cond:", ind + 1);
    Then->dump(indent(out, ind) << "Then:", ind + 1);
    Else->dump(indent(out, ind) << "Else:", ind + 1);
    return out;
  }
};

/// 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;
  raw_ostream &dump(raw_ostream &out, int ind) override {
    ExprAST::dump(out << "for", ind);
    Start->dump(indent(out, ind) << "Cond:", ind + 1);
    End->dump(indent(out, ind) << "End:", ind + 1);
    Step->dump(indent(out, ind) << "Step:", ind + 1);
    Body->dump(indent(out, ind) << "Body:", ind + 1);
    return out;
  }
};

/// 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;
  raw_ostream &dump(raw_ostream &out, int ind) override {
    ExprAST::dump(out << "var", ind);
    for (const auto &NamedVar : VarNames)
      NamedVar.second->dump(indent(out, ind) << NamedVar.first << ':', ind + 1);
    Body->dump(indent(out, ind) << "Body:", ind + 1);
    return out;
  }
};

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

public:
  PrototypeAST(SourceLocation Loc, 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), Line(Loc.Line) {}
  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; }
  int getLine() const { return Line; }
};

/// 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();
  raw_ostream &dump(raw_ostream &out, int ind) {
    indent(out, ind) << "FunctionAST\n";
    ++ind;
    indent(out, ind) << "Body:";
    return Body ? Body->dump(out, ind) : out << "null\n";
  }
};
} // конец анонимного пространства имен

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

/// 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;
}

/// LogError* - Маленькая вспомогательная функция обработки ошибок.
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;

  SourceLocation LitLoc = CurLoc;

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

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

  // Call.
  getNextToken(); // съедаем (
  std::vector<std::unique_ptr<ExprAST>> Args;
  if (CurTok != ')') {
    while (1) {
      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>(LitLoc, IdName, std::move(Args));
}

/// ifexpr ::= 'if' expression 'then' expression 'else' expression
static std::unique_ptr<ExprAST> ParseIfExpr() {
  SourceLocation IfLoc = CurLoc;

  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>(IfLoc, 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 (1) {
    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 (1) {
    int TokPrec = GetTokPrecedence();

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

    // Теперь мы знаем, что это бинарный оператор
    int BinOp = CurTok;
    SourceLocation BinLoc = CurLoc;
    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>(BinLoc, 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;

  SourceLocation FnLoc = CurLoc;

  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>(FnLoc, 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() {
  SourceLocation FnLoc = CurLoc;
  if (auto E = ParseExpression()) {
    // Создаём анонимный прототип
    auto Proto = llvm::make_unique<PrototypeAST>(FnLoc, "__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(); // eat extern.
  return ParsePrototype();
}

//===----------------------------------------------------------------------===//
// Поддержка отладочной информации
//===----------------------------------------------------------------------===//

static std::unique_ptr<DIBuilder> DBuilder;

DIType *DebugInfo::getDoubleTy() {
  if (DblTy)
    return DblTy;

  DblTy = DBuilder->createBasicType("double", 64, 64, dwarf::DW_ATE_float);
  return DblTy;
}

void DebugInfo::emitLocation(ExprAST *AST) {
  if (!AST)
    return Builder.SetCurrentDebugLocation(DebugLoc());
  DIScope *Scope;
  if (LexicalBlocks.empty())
    Scope = TheCU;
  else
    Scope = LexicalBlocks.back();
  Builder.SetCurrentDebugLocation(
      DebugLoc::get(AST->getLine(), AST->getCol(), Scope));
}

static DISubroutineType *CreateFunctionType(unsigned NumArgs, DIFile *Unit) {
  SmallVector<Metadata *, 8> EltTys;
  DIType *DblTy = KSDbgInfo.getDoubleTy();

  // Добавить тип результата
  EltTys.push_back(DblTy);

  for (unsigned i = 0, e = NumArgs; i != e; ++i)
    EltTys.push_back(DblTy);

  return DBuilder->createSubroutineType(DBuilder->getOrCreateTypeArray(EltTys));
}

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

static std::unique_ptr<Module> TheModule;
static std::map<std::string, AllocaInst *> NamedValues;
static std::unique_ptr<KaleidoscopeJIT> TheJIT;
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.c_str());
}

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

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

  KSDbgInfo.emitLocation(this);
  // Загружаем значение
  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");

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

Value *BinaryExprAST::codegen() {
  KSDbgInfo.emitLocation(this);

  // Особый случай для '=', т.к. мы не хотим генерировать 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() {
  KSDbgInfo.emitLocation(this);

  // Ищем имя в глобальной таблице модуля
  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() {
  KSDbgInfo.emitLocation(this);

  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);

  KSDbgInfo.emitLocation(this);

  // Генерируем вначале стартовый код, без '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;
  }

  KSDbgInfo.emitLocation(this);

  // Генерируем тело цикла со всеми переменными
  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);

  // создаём подпрограмму DIE для функции
  DIFile *Unit = DBuilder->createFile(KSDbgInfo.TheCU->getFilename(),
                                      KSDbgInfo.TheCU->getDirectory());
  DIScope *FContext = Unit;
  unsigned LineNo = P.getLine();
  unsigned ScopeLine = LineNo;
  DISubprogram *SP = DBuilder->createFunction(
      FContext, P.getName(), StringRef(), Unit, LineNo,
      CreateFunctionType(TheFunction->arg_size(), Unit),
      false /* internal linkage */, true /* definition */, ScopeLine,
      DINode::FlagPrototyped, false);
  TheFunction->setSubprogram(SP);

  // сохраняем текущую область видимости
  KSDbgInfo.LexicalBlocks.push_back(SP);

  // Не устанавливаем локацию при генерации пролога (инструкции в начале функции
  // без локации рассматриваются как пролог и отладчик
  // будет их пропускать при установке точки останова)
  KSDbgInfo.emitLocation(nullptr);

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

    // Создаём отладочный дескриптор для переменной
    DILocalVariable *D = DBuilder->createParameterVariable(
        SP, Arg.getName(), ++ArgIdx, Unit, LineNo, KSDbgInfo.getDoubleTy(),
        true);

    DBuilder->insertDeclare(Alloca, D, DBuilder->createExpression(),
                            DebugLoc::get(LineNo, 0, SP),
                            Builder.GetInsertBlock());

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

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

  KSDbgInfo.emitLocation(Body.get());

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

    // Извлекаем лексический блок для функции.
    KSDbgInfo.LexicalBlocks.pop_back();

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

    return TheFunction;
  }

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

  if (P.isBinaryOp())
    BinopPrecedence.erase(Proto->getOperatorName());

  // Извлекаем лексический блок для функции
  KSDbgInfo.LexicalBlocks.pop_back();

  return nullptr;
}

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

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

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

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

static void HandleTopLevelExpression() {
  // Вычисляем высокоуровневое выражение для анонимной функции
  if (auto FnAST = ParseTopLevelExpr()) {
    if (!FnAST->codegen()) {
      fprintf(stderr, "Error generating code for top level expr");
    }
  } else {
    // Пропускаем токен для восстановления после ошибки
    getNextToken();
  }
}

/// top ::= definition | external | expression | ';'
static void MainLoop() {
  while (1) {
    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 - принимает double печатает его как"%f\n", возвращает 0.
extern "C" DLLEXPORT double printd(double X) {
  fprintf(stderr, "%f\n", X);
  return 0;
}

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

int main() {
  InitializeNativeTarget();
  InitializeNativeTargetAsmPrinter();
  InitializeNativeTargetAsmParser();

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

  // Обрабатываем первый токен
  getNextToken();

  TheJIT = llvm::make_unique<KaleidoscopeJIT>();

  InitializeModule();

  // Добавляем текущую отладочную информацию в модуль
  TheModule->addModuleFlag(Module::Warning, "Debug Info Version",
                           DEBUG_METADATA_VERSION);

  // Darwin поддерживает только dwarf2.
  if (Triple(sys::getProcessTriple()).isOSDarwin())
    TheModule->addModuleFlag(llvm::Module::Warning, "Dwarf Version", 2);

  // Создаём DIBuilder, делаем это здесь, т.к. нам нужен модуль
  DBuilder = llvm::make_unique<DIBuilder>(*TheModule);

  // Создаём единицу компиляции для модуля
  // Устанавливаем "fib.ks" как имя файла, потому что мы перенаправляем stdin
  // но далае, как будто это реальный исходный файл.
  KSDbgInfo.TheCU = DBuilder->createCompileUnit(
      dwarf::DW_LANG_C, "fib.ks", ".", "Kaleidoscope Compiler", 0, "", 0);

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

  // Финализируем отладочную информацию
  DBuilder->finalize();

  // Выводим сгенерированный код.
  TheModule->print(errs(), nullptr);

  return 0;
}

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


  1. Eredun
    07.09.2017 03:06

    Какой процент языков программирования создаётся по этому принципу?


    1. 32bit_me Автор
      07.09.2017 03:12
      +1

      Как-то не очень понятен вопрос. По какому принципу?
      Сколько языков имеют компилятор на LLVM? Очень многие: C, C++, Objective C, Go, Rust, D, и многие другие.
      Просто здесь не очень корректно само название (это перевод): должно быть «создание компилятор языка программирования», потому что для создания собственно языка достатоно описать его синтаксис и семантику, но без компилятора он вряд ли кому-то будет нужен.


  1. eugenk
    09.09.2017 04:10

    Владимир, прошу прощения, о какой версии llvm тут идёт речь? Дело в том что серия статей начиналась в 2011-м году, а наверняка с тех пор много чего поменялось. Хотел немного в это поиграться, просто для общего развития. В результате сейчас не знаю, какую версию llvm качать.


    1. 32bit_me Автор
      09.09.2017 05:15

      Да, в 2011 году перевод начал Amper, части 1-5. Части 1-10 переведены мной (10-я будет скоро).
      Лучше всего качать всегда последнюю версию (сейчас это 5.0). Отличия возможны, но в первых частях, где идёт описание лексического анализатора, парсера и AST, на сам LLVM ничего не завязано, там отличий быть не должно. Какие-то отличия могут быть в частях 3-5, где происходит генерация LLVM IR и подключение JIT, но в таких случаях лучше всего смотреть в оригинальный исходник проекта (он входит в общее дерево исходников LLVM) и в оригинальный текст документа.
      Если будут вопросы, обращайтесь, постараюсь ответить, если смогу.


      1. 32bit_me Автор
        09.09.2017 06:48

        Поправка: Части 1-10 части 6-10


  1. 32bit_me Автор
    09.09.2017 06:48

    .