Разработка → Создание языка программирования с использованием LLVM. Часть 6: Расширение языка: Операторы, определяемые пользователем

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



6.1. Введение


Добро пожаловать в главу 6 руководства “Создание языка программирования с использованием LLVM”. К данному моменту у нас есть полнофункциональный язык, хотя и минимальный, но, тем не менее, полезный. Но по-прежнему осталась одна проблема. В нашем языке мало полезных операторов (нет, например, деления, логического отрицания, и даже сравнений, за исключением оператора сравнения «меньше»).

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

В конце этой главы мы рассмотрим пример приложения на Калейдоскопе, которое выводит множество Мандельброта. Это будет примером того, что вы можете сделать с языком Калейдоскоп и его набором возможностей.

6.2. Операторы, определяемые пользователем: основная мысль


«Перегрузка операторов», которую мы введём в Калейдоскоп, является более обобщённой, чем в языках типа C++. В C++ вы можете только переопределять существующие операторы, вы не можете программно изменить их синтаксис, ввести новые операторы, изменить уровни приоритета, и т.п. В этой главе, мы добавим в Калейдоскоп все эти возможности, что даст пользователю самому определить набор поддерживаемых операторов.

Цель, с которой мы рассматриваем определяемые пользователем операторы в этом руководстве — показать мощь и гибкость использования «самописного» парсера. Парсер, который мы делали, использует рекурсивный спуск для большей части грамматики, и парсинг операторов с приоритетами для выражений (см. часть 2). Используя парсинг операторов с приоритетами, очень легко позволить программисту вводить новые операторы в грамматику: грамматика динамически расширяется при работе JIT.

Две специфических возможности, которые мы добавим, это унарные операторы (на данный момент Калейдоскоп не имеет унарных операторов) и бинарные операторы. Например:

# Логическое унарное отрицание.
def unary!(v)
  if v then
    0
  else
    1;

# Определяем > с тем же приоритетом, что и <.
def binary> 10 (LHS RHS)
  RHS < LHS;

# Бинарный оператор "логическое или"
def binary| 5 (LHS RHS)
  if LHS then
    1
  else if RHS then
    1
  else
    0;

# Определим = с несколько более низким приоритетом, чем сравнения.
def binary= 9 (LHS RHS)
  !(LHS < RHS | LHS > RHS);

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

Разобьём реализацию этих возможностей на две части: реализацию поддержки пользовательских бинарных операторов и унарных операторов.

6.3. Бинарные операторы, определяемые пользователем


Добавление поддержки определяемых пользователем бинарных операторов в нашем фреймворке делается очень просто. Сначала добавим поддержку ключевых слов «unary» и «binary»:

enum Token {
  ...
  // operators
  tok_binary = -11,
  tok_unary = -12
};
...
static int gettok() {
...
    if (IdentifierStr == "for")
      return tok_for;
    if (IdentifierStr == "in")
      return tok_in;
    if (IdentifierStr == "binary")
      return tok_binary;
    if (IdentifierStr == "unary")
      return tok_unary;
    return tok_identifier;

Этот код добавляет поддержку ключевых слов «unary» и «binary» в лексический анализатор, подобно тому, как мы это делали в предыдущих частях. Одна хорошая вещь в нашей реализации AST заключается в том, что мы представляем бинарные операторы полностью обобщёнными, используя их ASCII-код в качестве опкода. Для наших дополнительных операторов мы будем использовать то же представление, и нам не нужно дополнительной поддержки со стороны AST или парсера.

С другой стороны, мы можем представить определения этих новых операторов в виде определения функции. В нашей грамматике, «имя» в определении функции парсится как продукция прототипа функции и попадает в узел AST типа PrototypeAST. Чтобы представить наши новые определяемые пользователем операторы как прототипы, мы должны расширить узел PrototypeAST таким образом:

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

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

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

/// прототип
///   ::= id '(' id* ')'
///   ::= binary LETTER number? (id, 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_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, std::move(ArgNames), Kind != 0,
                                         BinaryPrecedence);
}

Достаточно прямолинейный код парсинга, мы уже видели много похожего кода ранее. Одна интересная часть в этом коде, это пара строк, в которой присваивается FnName для бинарного оператора. Для пользовательского оператора "@" прототипу будет присвоено имя «binary@». Здесь проявляются преимущества того факта, что имена символов в таблице символов LLVM могут иметь любые символы, включая нулевой.
Следующая интересная вещь, которую следует добавить, это поддержка кодогенерации для бинарных операторов. В нашей существующей структуре, это просто добавление «default»-а к нашему существующему узлу бинарного оператора:

Value *BinaryExprAST::codegen() {
  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 или 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[2] = { L, R };
  return Builder.CreateCall(F, Ops, "binop");
}

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

Последний кусок кода, который нам нужен, это просто кусок высокоуровневой магии:

Function *FunctionAST::codegen() {
  // Переносим владение прототипом в FunctionProtos map, но сохраняем 
  // ссылку для дальнейшего использования.
  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);
  ...

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

6.4. Унарные операторы, определяемые пользователем


Так как мы пока что не поддерживаем унарных операторов в языке Калейдоскоп, нам нужно добавить их поддержку. Выше мы добавили простую поддержку ключевого слова «unary» в лексический анализатор. Теперь нам нужен узел AST.

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

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

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

Грамматика которую мы добавили здесь, очень проста. Если мы видим унарный оператор, когда парсим первичный оператор, мы съедаем этот оператор как префикс и парсим оставшийся кусок как другой унарный оператор. Это позволяет нам обрабатывать множественные унарные операторы (такие, как "!!x"). Отметим, что унарные операторы не могут иметь неоднозначного парсинга, как бинарные операторы, и не нуждаются в информации о приоритете.
Проблема с этой функцией в том, что нам может понадобиться вызов ParseUnary откуда угодно. Для этого, мы заменяем предыдущий вызов ParsePrimary на ParseUnary:

/// binoprhs
///   ::= ('+' unary)*
static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
                                              std::unique_ptr<ExprAST> LHS) {
  ...
    // Парсим унарное выражение после бинарного оператора
    auto RHS = ParseUnary();
    if (!RHS)
      return nullptr;
  ...
}
/// выражение
///   ::= unary binoprhs
///
static std::unique_ptr<ExprAST> ParseExpression() {
  auto LHS = ParseUnary();
  if (!LHS)
    return nullptr;

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

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

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

  unsigned Kind = 0;  // 0 = identifier, 1 = unary, 2 = binary.
  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:
    ...

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

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

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

6.5. Пинаем шины


Трудно поверить, но введя несколько простых расширений, рассмотренных в последних частях, мы вырастили настоящий язык. С ним можно сделать много интересных вещей, включая ввод-вывод, математику, и много других вещей. Например, можно ввести оператор последовательности (функция printd выводит значение аргумента и переводит строку ):

ready> extern printd(x);
Read extern:
declare double @printd(double)

ready> def binary : 1 (x y) 0;  # Низкоприоритетный оператор, который игнорирует операнды
...
ready> printd(123) : printd(456) : printd(789);
123.000000
456.000000
789.000000
Evaluated to 0.000000

Мы можем также определить множество «простых» операторов, например:

# Логическое унарное отрицание
def unary!(v)
  if v then
    0
  else
    1;

# Унарный минус.
def unary-(v)
  0-v;

# Определяем > с тем же приоритетом, что и <.
def binary> 10 (LHS RHS)
  RHS < LHS;

# Бинарное логическое "или"
def binary| 5 (LHS RHS)
  if LHS then
    1
  else if RHS then
    1
  else
    0;

#  Бинарное логическое "и"
def binary& 6 (LHS RHS)
  if !LHS then
    0
  else
    !!RHS;

# Определяем = с более низким приоритетом, чем сравнения
def binary = 9 (LHS RHS)
  !(LHS < RHS | LHS > RHS);

# Определяем ':' для последовательностей: как низкоприоритетный оператор, игнорирующий операнды
# и просто возвращающий RHS.
def binary : 1 (x y) y;

Взяв поддержку if/then/else, мы можем определить интересные функции ввода-вывода. Например, следующий код выводит символ, чья «плотность» отражает переданное ему значение: чем меньше значение, тем темнее символ.

ready> extern putchard(char);
...
ready> def printdensity(d)
  if d > 8 then
    putchard(32)  # ' '
  else if d > 4 then
    putchard(46)  # '.'
  else if d > 2 then
    putchard(43)  # '+'
  else
    putchard(42); # '*'
...
ready> printdensity(1): printdensity(2): printdensity(3):
       printdensity(4): printdensity(5): printdensity(9):
       putchard(10);
**++.
Evaluated to 0.000000

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

# Определяем, расходится ли функция в данной точке
# Решение для z = z^2 + c на комплексной плоскости
def mandelconverger(real imag iters creal cimag)
  if iters > 255 | (real*real + imag*imag > 4) then
    iters
  else
    mandelconverger(real*real - imag*imag + creal,
                    2*real*imag + cimag,
                    iters+1, creal, cimag);

# Возвращаем количество итераций
def mandelconverge(real imag)
  mandelconverger(real, imag, 0, real, imag);

Эта функция (z = z2 + c) — прекрасное маленькое создание, основа вычисления множества Мандельброта. Наша функция mandelconverge возвращает число итераций, которое нужно комплексной орбите для ухода в бесконечность. Функция «насыщается» при значении 255. Сама по себе эта функция не очень полезна, но если вы построите график её значений на двумерной плоскости, вы увидите множество Мандельброта. Так как мы ограничены здесь использованием функции putchard, наш чудесный вывод графики также ограничен, но мы можем использовать функцию вывода «плотности», приведённую выше.

# Вычисляем и рисуем множество Мандельброта в определённом диапазоне значений 
# на двумерной плоскости
def mandelhelp(xmin xmax xstep   ymin ymax ystep)
  for y = ymin, y < ymax, ystep in (
    (for x = xmin, x < xmax, xstep in
       printdensity(mandelconverge(x,y)))
    : putchard(10)
  )

# mandel - удобная вспомогательная функция для отображения множества Мандельброта
# в определённой точке с определённым увеличением
def mandel(realstart imagstart realmag imagmag)
  mandelhelp(realstart, realstart+realmag*78, realmag,
             imagstart, imagstart+imagmag*40, imagmag);

Сейчас мы можем попробовать построить множество Мандельброта:

Развернуть
ready> mandel(-2.3, -1.3, 0.05, 0.07);
*******************************+++++++++++*************************************
*************************+++++++++++++++++++++++*******************************
**********************+++++++++++++++++++++++++++++****************************
*******************+++++++++++++++++++++.. ...++++++++*************************
*****************++++++++++++++++++++++.... ...+++++++++***********************
***************+++++++++++++++++++++++..... ...+++++++++*********************
**************+++++++++++++++++++++++.... ....+++++++++********************
*************++++++++++++++++++++++...... .....++++++++*******************
************+++++++++++++++++++++....... .......+++++++******************
***********+++++++++++++++++++.... ... .+++++++*****************
**********+++++++++++++++++....... .+++++++****************
*********++++++++++++++........... ...+++++++***************
********++++++++++++............ ...++++++++**************
********++++++++++... .......... .++++++++**************
*******+++++++++..... .+++++++++*************
*******++++++++...... ..+++++++++*************
*******++++++....... ..+++++++++*************
*******+++++...... ..+++++++++*************
*******.... .... ...+++++++++*************
*******.... . ...+++++++++*************
*******+++++...... ...+++++++++*************
*******++++++....... ..+++++++++*************
*******++++++++...... .+++++++++*************
*******+++++++++..... ..+++++++++*************
********++++++++++... .......... .++++++++**************
********++++++++++++............ ...++++++++**************
*********++++++++++++++.......... ...+++++++***************
**********++++++++++++++++........ .+++++++****************
**********++++++++++++++++++++.... ... ..+++++++****************
***********++++++++++++++++++++++....... .......++++++++*****************
************+++++++++++++++++++++++...... ......++++++++******************
**************+++++++++++++++++++++++.... ....++++++++********************
***************+++++++++++++++++++++++..... ...+++++++++*********************
*****************++++++++++++++++++++++.... ...++++++++***********************
*******************+++++++++++++++++++++......++++++++*************************
*********************++++++++++++++++++++++.++++++++***************************
*************************+++++++++++++++++++++++*******************************
******************************+++++++++++++************************************
*******************************************************************************
*******************************************************************************
*******************************************************************************
Evaluated to 0.000000
ready> mandel(-2, -1, 0.02, 0.04);
**************************+++++++++++++++++++++++++++++++++++++++++++++++++++++
***********************++++++++++++++++++++++++++++++++++++++++++++++++++++++++
*********************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
*******************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++...
*****************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++.....
***************++++++++++++++++++++++++++++++++++++++++++++++++++++++++........
**************++++++++++++++++++++++++++++++++++++++++++++++++++++++...........
************+++++++++++++++++++++++++++++++++++++++++++++++++++++..............
***********++++++++++++++++++++++++++++++++++++++++++++++++++........ .
**********++++++++++++++++++++++++++++++++++++++++++++++.............
********+++++++++++++++++++++++++++++++++++++++++++..................
*******+++++++++++++++++++++++++++++++++++++++.......................
******+++++++++++++++++++++++++++++++++++...........................
*****++++++++++++++++++++++++++++++++............................
*****++++++++++++++++++++++++++++...............................
****++++++++++++++++++++++++++...... .........................
***++++++++++++++++++++++++......... ...... ...........
***++++++++++++++++++++++............
**+++++++++++++++++++++..............
**+++++++++++++++++++................
*++++++++++++++++++.................
*++++++++++++++++............ ...
*++++++++++++++..............
*+++....++++................
*.......... ...........
*
*.......... ...........
*+++....++++................
*++++++++++++++..............
*++++++++++++++++............ ...
*++++++++++++++++++.................
**+++++++++++++++++++................
**+++++++++++++++++++++..............
***++++++++++++++++++++++............
***++++++++++++++++++++++++......... ...... ...........
****++++++++++++++++++++++++++...... .........................
*****++++++++++++++++++++++++++++...............................
*****++++++++++++++++++++++++++++++++............................
******+++++++++++++++++++++++++++++++++++...........................
*******+++++++++++++++++++++++++++++++++++++++.......................
********+++++++++++++++++++++++++++++++++++++++++++..................
Evaluated to 0.000000
ready> mandel(-0.9, -1.4, 0.02, 0.03);
*******************************************************************************
*******************************************************************************
*******************************************************************************
**********+++++++++++++++++++++************************************************
*+++++++++++++++++++++++++++++++++++++++***************************************
+++++++++++++++++++++++++++++++++++++++++++++**********************************
++++++++++++++++++++++++++++++++++++++++++++++++++*****************************
++++++++++++++++++++++++++++++++++++++++++++++++++++++*************************
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++**********************
+++++++++++++++++++++++++++++++++.........++++++++++++++++++*******************
+++++++++++++++++++++++++++++++.... ......+++++++++++++++++++****************
+++++++++++++++++++++++++++++....... ........+++++++++++++++++++**************
++++++++++++++++++++++++++++........ ........++++++++++++++++++++************
+++++++++++++++++++++++++++......... .. ...+++++++++++++++++++++**********
++++++++++++++++++++++++++........... ....++++++++++++++++++++++********
++++++++++++++++++++++++............. .......++++++++++++++++++++++******
+++++++++++++++++++++++............. ........+++++++++++++++++++++++****
++++++++++++++++++++++........... ..........++++++++++++++++++++++***
++++++++++++++++++++........... .........++++++++++++++++++++++*
++++++++++++++++++............ ...........++++++++++++++++++++
++++++++++++++++............... .............++++++++++++++++++
++++++++++++++................. ...............++++++++++++++++
++++++++++++.................. .................++++++++++++++
+++++++++.................. .................+++++++++++++
++++++........ . ......... ..++++++++++++
++............ ...... ....++++++++++
.............. ...++++++++++
.............. ....+++++++++
.............. .....++++++++
............. ......++++++++
........... .......++++++++
......... ........+++++++
......... ........+++++++
......... ....+++++++
........ ...+++++++
....... ...+++++++
....+++++++
.....+++++++
....+++++++
....+++++++
....+++++++
Evaluated to 0.000000
ready> ^D


На этой стадии мы можем считать Калейдоскоп настоящим, мощным языком. Он не является самоподобным :), но может использоваться, чтобы рисовать вещи, которые являются таковыми!

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

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

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


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

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

На некоторых платформах, вам нужно будет линковать с -rdynamic или -Wl,–export-dynamic. Тогда символы, определённые в исполняемом файле, будут экспортированы в динамический линковщик и доступны в рантайме. В этом нет необходимости, если вы компилируете код поддержки в разделяемую библиотеку, хотя это может вызвать проблемы под Windows.

Код:

Код к главе
#include "llvm/ADT/APFloat.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/TargetSelect.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/GVN.h"
#include "../include/KaleidoscopeJIT.h"
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <memory>
#include <string>
#include <vector>

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

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;
    return tok_identifier;
  }

  if (isdigit(LastChar) || LastChar == '.') { // Number: [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;
};

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

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

  // Call.
  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(); // eat the 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(); // eat '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));
}

/// primary
///   ::= identifierexpr
///   ::= numberexpr
///   ::= parenexpr
///   ::= ifexpr
///   ::= forexpr
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();
  }
}

/// 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(); // eat binop

    // Парсим унарное выражение после бинарного оператора
    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(); // eat ')'.

  // Проверяем, что количество аргументов правильно
  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(); // eat 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(); // eat extern.
  return ParsePrototype();
}

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

static LLVMContext TheContext;
static IRBuilder<> Builder(TheContext);
static std::unique_ptr<Module> TheModule;
static std::map<std::string, Value *> NamedValues;
static std::unique_ptr<legacy::FunctionPassManager> TheFPM;
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;

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

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

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

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

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() {
  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 как:
//   ...
//   start = startexpr
//   goto loop
// loop:
//   variable = phi [start, loopheader], [nextvariable, loopend]
//   ...
//   bodyexpr
//   ...
// loopend:
//   step = stepexpr
//   nextvariable = variable + step
//   endcond = endexpr
//   br endcond, loop, endloop
// outloop:
Value *ForExprAST::codegen() {
  // Генерируем сначала стартовый код, без переменной.
  Value *StartVal = Start->codegen();
  if (!StartVal)
    return nullptr;

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

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

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

  // Вставляем узел PHI в начало блока.
  PHINode *Variable =
      Builder.CreatePHI(Type::getDoubleTy(TheContext), 2, VarName);
  Variable->addIncoming(StartVal, PreheaderBB);

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

  // Генерируем тело цикла.  Оно, как любое другое выражение, может изменить
  // текущий 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 *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");

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

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

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

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

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

  // Добавляем новое вхождение в узел PHI.
  Variable->addIncoming(NextVar, LoopEndBB);

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

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

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())
    NamedValues[Arg.getName()] = &Arg;

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

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

    // Запускаем оптимизатор для функции
    TheFPM->run(*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);
  TheModule->setDataLayout(TheJIT->getTargetMachine().createDataLayout());

  // Создаём новый менеджер проходов для модуля
  TheFPM = llvm::make_unique<legacy::FunctionPassManager>(TheModule.get());

  // Делаем простую "peephole"-оптимизацию.
  TheFPM->add(createInstructionCombiningPass());
  // Переассоциация выражений
  TheFPM->add(createReassociatePass());
  // Удаление общих подвыражений
  TheFPM->add(createGVNPass());
  // Упрощение графа управления (удаление недостижимых блоков и т.п.).
  TheFPM->add(createCFGSimplificationPass());

  TheFPM->doInitialization();
}

static void HandleDefinition() {
  if (auto FnAST = ParseDefinition()) {
    if (auto *FnIR = FnAST->codegen()) {
      fprintf(stderr, "Read function definition:");
      FnIR->print(errs());
      fprintf(stderr, "\n");
      TheJIT->addModule(std::move(TheModule));
      InitializeModuleAndPassManager();
    }
  } 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() {
  // Вычисляем высокоуровневое выражения для анонимной функции
  if (auto FnAST = ParseTopLevelExpr()) {
    if (FnAST->codegen()) {
      //выполняем JIT для модуля, содержащего анонимное выражение
      // освободим его позже
      auto H = TheJIT->addModule(std::move(TheModule));
      InitializeModuleAndPassManager();

      // Ищем JIT для символа __anon_expr
      auto ExprSymbol = TheJIT->findSymbol("__anon_expr");
      assert(ExprSymbol && "Function not found");

      // Получаем адрес символа и преобразуем его к правильному типу(не принимаем
      // аргументов, возвращаем double) и мы можем вызывать нативную функцию.
      double (*FP)() = (double (*)())(intptr_t)cantFail(ExprSymbol.getAddress());
      fprintf(stderr, "Evaluated to %f\n", FP());

      //Удаляем модуль анонимного выражения из JIT.
      TheJIT->removeModule(H);
    }
  } else {
    // Пропускаем токен для восстановления после ошибки
    getNextToken();
  }
}

/// top ::= definition | external | expression | ';'
static void MainLoop() {
  while (true) {
    fprintf(stderr, "ready> ");
    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() {
  InitializeNativeTarget();
  InitializeNativeTargetAsmPrinter();
  InitializeNativeTargetAsmParser();

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

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

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

  InitializeModuleAndPassManager();

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

  return 0;
}

Проголосовать:
+47
Сохранить: