Создание языка программирования с использованием LLVM. Часть 3: Генерация кода LLVM IR

Добро пожаловать в Главу 3 учебника «Создание языка программирования с LLVM». В этой главе мы рассмотрим, как преобразовать AST (Абстрактное Синтаксическое дерево), построенное в Главе 2, в LLVM IR. Она расскажет вам о некоторых аспектах работы LLVM, а также продемонстрирует, насколько он прост в использовании. Вы увидите, что гораздо больше труда потребовалось на лексический и синтаксический анализ, чем на непосредственное создание кода LLVM IR.

Обратите внимание: код из этой главы требует наличия LLVM 2.2 или более поздней версии. С версиями по LLVM 2.1 включительно этот код работать не будет. Также стоит отметить, что вам стоит использовать версию этого учебника, которая соответствует вашему релизу LLVM: вы можете использовать документацию, которая прилагается к официальным выпускам или посетить страницу с релизами на llvm.org.

Настраиваемся на кодогенерацию

Для генерации LLVM IR нам понадобятся некоторые простые установки. Сначала определим виртуальные методы кодогенерации (Codegen) для каждого AST-класса:

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

  virtual Value *Codegen() = 0;

};

/// NumberExprAST - Класс узла выражения для числовых литералов "1.0".
class NumberExprAST : public ExprAST {
  double Val;
public:
  NumberExprAST(double val) : Val(val) {}

  virtual Value *Codegen();

};
...

Метод Codegen() вернёт IR для данного узла AST вместе со всеми зависимыми от него, и все они возвращают объект LLVM Value. "Value" является классом, используемым для представления «регистра Static Single Assigment (SSA)» или «Значения SSA» в LLVM. Наиболее важным моментом в SSA является то, что их значение рассчитывается как выполнение связанной инструкции и они не могут получить новое значение пока (и если) инструкция не будет выполнена повторно. Другими словами, нет никакой возможности «изменить» значение SSA. Для получения дополнительной информации, прочтите о Static Single Assignment — эти концепции действительно кажутся вполне естественными, как только вы обратите внимание на них.

Заметим, что вместо добавления виртуальных методов для иерархии классов ExprAST, может иметь смысл использовать шаблон проектирования «Visitor» («Посетитель») или какой-либо другой способ. Опять же, в этот учебнике мы не будем останавливаться на хороших методах разработки ПО: наша цель простота — и для нас проще добавить виртуальный метод.

Ещё нам нужен метод для обработки ошибок, похожий на тот, который был использован для парсера. Мы будем использовать этот метод для сообщений об ошибках, найденных при генерации кода (например, использование необъявленных параметров):

Value *ErrorV(const char *Str) { Error(Str); return 0; }

static Module *TheModule;
static IRBuilder<> Builder(getGlobalContext());
static std::map<std::string, Value*> NamedValues;

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

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

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

Зная всё это, мы сможем поговорить о генерации кода для любых выражений. Отметим, предполагается, что уже был создан Builder для генерации кода во «что-либо». Пока что мы предположим, что это уже сделано, и мы будем использовать его, чтобы сохранять код.

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

Генерация LLVM-кода для узлов выражений очень проста: менее чем 45 строк комментированного кода для всех наших четырех типов узлов выражений. Для начала займёмся числовыми литералами:

Value *NumberExprAST::Codegen() {
  return ConstantFP::get(getGlobalContext(), APFloat(Val));
}

В LLVM IR числовые константы представлены классом ConstantFP, который содержит внутри числовое значение в виде APFloat (APFloat имеет возможность приведения действительных констант к числам произвольной точности). Этот код создает и возвращает ConstantFP. Отметим, что в LLVM IR все константы являются уникальными (uniqued) и совместно используемыми (shared). Именно по этой причине API использует идиому "foo::get(...)", а не "new foo(..)" или "foo::Create(..)".

Value *VariableExprAST::Codegen() {
  // Ищем эту переменную в текущей функции.
  Value *V = NamedValues[Name];
  return V ? V : ErrorV("Unknown variable name");
}

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

Value *BinaryExprAST::Codegen() {
  Value *L = LHS->Codegen();
  Value *R = RHS->Codegen();
  if (L == 0 || R == 0) return 0;
  
  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");
    // Преобразование булевых 0 или 1 в вещественные 0.0 или 1.0
    return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
                                "booltmp");
  default: return ErrorV("invalid binary operator");
  }
}

С бинарных операторов начинается всё самое интересное. Основная идея здесь в том, что мы рекурсивно генерируем код для левой части выражения, затем для правой, вычисляя результат бинарного выражения. В этом коде мы сделали простой switch относительно бинарного оператора для создания инструкции LLVM.

В приведенном выше примере класс LLVM Builder, наконец, показывает своё значение. IRBuilder знает, куда вставлять вновь созданные инструкции, и всё, что нужно сделать вам — это указать, какие инструкции создавать (например, "CreateFAdd"), какие операнды использовать (в данном случае L и R) и, если требуется, то какое использовать имя для генерируемой инструкции.

Ещё одна великолепная фишка в LLVM — это назначение имён. Например, если вышеприведённый несколько раз использует переменную "addtmp", LLVM будет автоматически назначать каждый раз уникальный числовой суффикс. Локальные имена значений для инструкций необязательны, но они делают гораздо легче читаемыми дампы IR.

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

С другой стороны, спецификация LLVM говорит, что инструкция fcmp всегда возвращает значение «i1» (однобитное целое число). Проблема в том, что нам в Kaleidoscope нужно значение 0.0 или 1.0. Для этого мы объединяем инструкцию fcmp с инструкцией uitofp. Эта инструкция преобразует беззнаковое целое число в действительное с плавающей запятой. В противоположность этому, если бы мы использовали инструкцию sitofp, оператор '<' возвращал бы 0.0 и -1.0 в зависимости от входного значения.

Value *CallExprAST::Codegen() {
  // Ищем имя в глобальной таблице модуля.
  Function *CalleeF = TheModule->getFunction(Callee);
  if (CalleeF == 0)
    return ErrorV("Unknown function referenced");
  
  // Ошибка при несоответствии аргументов.
  if (CalleeF->arg_size() != Args.size())
    return ErrorV("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() == 0) return 0;
  }
  
  return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
}

Генерация кода LLVM для вызова функции достаточно проста. Вышеприведённый код сначала производит поиск имени функции в таблице символов модуля LLVM. Напомним, что модуль LLVM является контейнером, который содержит все функции, которые мы можем использовать для JIT-компиляции. Давая каждой функции какое-либо наименование, мы можем использовать таблицу символов LLVM для разрешения поиска имён функций.

После получения функции для вызова, мы рекурсивно генерируем код каждого аргумента, который должен быть передан и создаём инструкцию вызова LLVM. Обратите внимание, что LLVM по-умолчанию использует соглашения о вызове функций как в языке C, что позволяет без дополнительных усилий использовать эти вызовы для стандартных библиотечных функций, таких как "sin" и "cos".

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

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

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

Function *PrototypeAST::Codegen() {
  // Задаём тип функции:  double(double,double) и т.д..
  std::vector<const Type*> Doubles(Args.size(),
                                   Type::getDoubleTy(getGlobalContext()));
  FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
                                       Doubles, false);
  
  Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);

Этот код в несколько строк на самом деле показывает настоящую мощь. Для начала заметим, что эта функция возвращает "Function*" вместо "Value*". Так как «прототип» на самом деле говорит о внешнем интерфейсе для функции (а не вычисляемом выражении), то имеет смысл для него возвращать LLVM-функцию, соответствующую сгенерированному для функции коду.

Вызов "FunctionType::get" создает FunctionType, который должен быть использованы для данного прототипа. Так как все аргументы функции в Kaleidoscope — это действительные числа, то первая строка создает вектор LLVM из «N» действительных чисел. Затем используется метод FunctionType::get для создания функционального типа, который принимает «N» действительных аргументов и возвращает один действительный аргумент в качестве результата. Обратите внимание, что типы в LLVM являются уникальными, как константы, так что вам нужен не "new", а "get" (в оригинале игра слов: «… так что вы не "создаёте" его, а "получаете".»).

Последняя строка фактически создает функцию, соответствующую прототипу. Она указывает тип, связь и наименование для использования, а модуль для вставки. «external linkage» означает, что функция может быть определена вне текущего модуля и/или что она может вызываться вне модуля. "Name" определяет наименование, указанное пользователем, "TheModule" указывает, что это наименование зарегистрировано в таблице символов "TheModule".

  // Если функция (F) конфликтует с с добавленными функциями, значит уже использовано имя 'Name'.  
  // Если функция уже имеет тело, то не разрешаем переопределение или переоткрытие.
  if (F->getName() != Name) {
    // Удаляем ту функцию, что мы создали и используем существующую.
    F->eraseFromParent();
    F = TheModule->getFunction(Name);

Когда дело доходит до конфликтов имен, таблица символов Модуля работает так же, как таблица символов Функции: если новая функция создана с именем, которое уже ранее добавили в таблицу символов, то при добавлении в модуль она будет неявно переименована. Вышеприведённый код использует этот факт для того, чтобы определить, была ли ранее объявлена такая же функция.

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

Для реализации этого, вышеприведённый код сначала проверяет — есть ли конфликт имён функций. Если есть, то удаляет только что созданную функцию (с помощью вызова "eraseFromParent"), а затем вызывает "getFunction" для получения существующей функции с данным именем. Стоит отметить, что многие API в LLVM имеют как форму "erase", так и форму "remove". Метод "remove" отсоединяет (unlink) объект от его родительского объекта (например, Функцию от Модуля) и возвращает его. Метод "erase" отсоединяет (unlink) объект, а затем удаляет его.

    // Если функция (F) уже имеет тело, ругаемся.
    if (!F->empty()) {
      ErrorF("redefinition of function");
      return 0;
    }
    
    // Если функция (F)  принимает другое число аргументов, ругаемся.
    if (F->arg_size() != Args.size()) {
      ErrorF("redefinition of function with different # args");
      return 0;
    }
  }

Для того, чтобы подтвердить вышеуказанные рассуждения, мы сначала проверяем, что «уже существующая» функция является «пустой». В этом случае, пустота означает, что она не содержит базовых блоков, то есть тела функции. Если же функция имеет тело, то это повторное объявление, поэтому в данном случае мы отвергаем код. Если предыдущая функция является "extern"-функцией, мы просто сверяем её число аргументов с числом аргументов текущего определения. Если они не совпадают, то отображаем ошибку.

  // Задаём наименования для всех аргументов.
  unsigned Idx = 0;
  for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
       ++AI, ++Idx) {
    AI->setName(Args[Idx]);
    
    // Добавляем аргументы в таблицу символов переменных.
    NamedValues[Args[Idx]] = AI;
  }
  return F;
}

Последняя часть кода обработки прототипов функций является циклом аргументам в функции, задающим наименования объектов LLVM, соответствующим аргументам, и региструющим аргументы в карте NamedValues для последующего использования AST-узлом VariableExprAST. Затем он возвращает объект функции. Обратите внимание, что мы не проверяем конфликтующие имена аргументов (например, "extern Foo (a b a)"). Но это можно достаточно просто и прямолинейно сделать с использованием способа, который мы использовали выше.

Function *FunctionAST::Codegen() {
  NamedValues.clear();
  
  Function *TheFunction = Proto->Codegen();
  if (TheFunction == 0)
    return 0;

Генерация кода для определения функций начинается достаточно просто: мы просто вызываем кодогенерацию прототипа (Proto) и убеждаемся, что всё нормально. Мы также очищаем карту NamedValues, чтобы быть уверенными, что ничего не осталось от последней обрабатываемой нами функции. Генерация кода прототипа гарантирует, что у нас есть готовый функциональный объект LLVM, так что мы можем двигаться дальше.

  // Создаёт новый базовый блок для вставки.
  BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
  Builder.SetInsertPoint(BB);
  
  if (Value *RetVal = Body->Codegen()) {

Теперь мы перейдем к работе с Builder'ом. В первой строке создаётся новый базовый блок [en] (названный "entry"), который вставляется в TheFunction. Вторая строка указывает Builder'у, что новые инструкции должны будут вставляться в конец нового базового блока. Базовые блоки в LLVM являются важной частью функций, которая определяет Граф потока управления [en]. Поскольку у нас пока нет никакого потока управления, наши функции будут содержать только один блок. Но мы исправим это в главе 5 :).

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

    // Валидация сгенерированного код, проверка на непротиворечивость (связность).
    verifyFunction(*TheFunction);

    return TheFunction;
  }

Как только задана точка вставки, мы вызываем кодогенерацию с помощью CodeGen() для корневого выражения функции. Если ошибок не происходит, то добавляем код вычисления выражения в входной блок и возвращаем значение, которое будет вычислено. Затем, при отсутствии ошибок, мы создаём LLVM-инструкцию "ret", которая завершает функцию. После построения функции мы называем встроенную в LLVM процедуру "verifyFunction". Она производит различные проверки консистентности сгенерированного кода, чтобы определить, что наш компилятор делает все правильно. Использование этой процедуры очень важно: она может отловить множество багов. Когда функция закончена и проверена, мы возвращаем её.

  // При ошибке, удаляем созданную функцию.
  TheFunction->eraseFromParent();
  return 0;
}

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

На самом деле, этот код имеет баг. "PrototypeAST:: Codegen" может вернуть ранее определенные преддекларации, наш код может фактически удалить их. Есть несколько способов исправить этот баг, подумайте, что можно придумать! Вот небольшой тесткейс:

extern foo(a b);     # oк, определили "foo".
def foo(a b) c;      # ошибка, неизвестный символ 'c'.
def bar() foo(1, 2); # ошибка, неизвестная функция "foo"

Изменения в основной программе и заключительные мысли

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

ready> 4+5;
Read top-level expression:
define double @""() {
entry:
        ret double 9.000000e+00
}

Обратите внимание на то, как парсер возвращает верхнеуровневое выражение в виде анонимной функции. Это будет удобно, когда мы добавим поддержку JIT в следующей главе. Также отметим, что код транслируeтся «очень буквально», «прямолинейно», нет никаких оптимизаций за исключением простого свертывания констант, сделанного IRBuilder. Мы добавим оптимизации явно в следующей главе.

ready> def foo(a b) a*a + 2*a*b + b*b;
Read function definition:
define double @foo(double %a, double %b) {
entry:
        %multmp = fmul double %a, %a
        %multmp1 = fmul double 2.000000e+00, %a
        %multmp2 = fmul double %multmp1, %b
        %addtmp = fadd double %multmp, %multmp2
        %multmp3 = fmul double %b, %b
        %addtmp4 = fadd double %addtmp, %multmp3
        ret double %addtmp4
}

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

ready> def bar(a) foo(a, 4.0) + bar(31337);
Read function definition:
define double @bar(double %a) {
entry:
        %calltmp = call double @foo(double %a, double 4.000000e+00)
        %calltmp1 = call double @bar(double 3.133700e+04)
        %addtmp = fadd double %calltmp, %calltmp1
        ret double %addtmp
}

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

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

ready> cos(1.234);

Read top-level expression:
define double @""() {
entry:
        %calltmp = call double @cos(double 1.234000e+00)
        ret double %calltmp
}

Здесь показан extern для библиотечной функции "cos" и её вызов.

ready> ^D
; ModuleID = 'my cool jit'

define double @""() {
entry:
        %addtmp = fadd double 4.000000e+00, 5.000000e+00
        ret double %addtmp
}

define double @foo(double %a, double %b) {
entry:
        %multmp = fmul double %a, %a
        %multmp1 = fmul double 2.000000e+00, %a
        %multmp2 = fmul double %multmp1, %b
        %addtmp = fadd double %multmp, %multmp2
        %multmp3 = fmul double %b, %b
        %addtmp4 = fadd double %addtmp, %multmp3
        ret double %addtmp4
}

define double @bar(double %a) {
entry:
        %calltmp = call double @foo(double %a, double 4.000000e+00)
        %calltmp1 = call double @bar(double 3.133700e+04)
        %addtmp = fadd double %calltmp, %calltmp1
        ret double %addtmp
}

declare double @cos(double)

define double @""() {
entry:
        %calltmp = call double @cos(double 1.234000e+00)
        ret double %calltmp
}

При выходе из текущего демо, будет возвращён дамп IR для всего сгенерированного модуля. Здесь вы можете видеть полную картину со всеми ссылающимися друг на друга функциями.

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

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

Здесь представлен полный листинг кода нашего работающего примера, например, расширенного генератором кода LLVM. Так как мы используем библиотеки LLVM, мы должны связать их с нашим кодом. Для этого используем инструмент llvm-config следующим образом:

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


Ну и, наконец, сам код:

#include "llvm/DerivedTypes.h"
#include "llvm/LLVMContext.h"
#include "llvm/Module.h"
#include "llvm/Analysis/Verifier.h"
#include "llvm/Support/IRBuilder.h"
#include <cstdio>
#include <string>
#include <map>
#include <vector>
using namespace llvm;

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

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

  // команды (ключевые слова)
  tok_def = -2, tok_extern = -3,

  // операнды (первичные выражения: идентификаторы, числа)
  tok_identifier = -4, tok_number = -5
};

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

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

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

  if (LastChar == '#') {
    // Комментарий до конца строки
    do LastChar = getchar();
    while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
    
    if (LastChar != EOF)
      return gettok();
  }
  
  // Проверка конца файла.
  if (LastChar == EOF)
    return tok_eof;

  // В противном случае просто возвращаем символ как значение ASCII
  int ThisChar = LastChar;
  LastChar = getchar();
  return ThisChar;
}

//===----------------------------------------------------------------------===//
// Abstract Syntax Tree (Абстрактное Синтаксическое Дерево или Дерево Парсинга)
//===----------------------------------------------------------------------===//

/// ExprAST - Базовый класс для всех узлов выражений.
class ExprAST {
public:
  virtual ~ExprAST() {}
  virtual Value *Codegen() = 0;
};

/// NumberExprAST - Класс узла выражения для числовых литералов (Например, "1.0").
class NumberExprAST : public ExprAST {
  double Val;
public:
  NumberExprAST(double val) : Val(val) {}
  virtual Value *Codegen();
};

/// VariableExprAST - Класс узла выражения для переменных (например, "a").
class VariableExprAST : public ExprAST {
  std::string Name;
public:
  VariableExprAST(const std::string &name) : Name(name) {}
  virtual Value *Codegen();
};

/// BinaryExprAST - Класс узла выражения для бинарных операторов.
class BinaryExprAST : public ExprAST {
  char Op;
  ExprAST *LHS, *RHS;
public:
  BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs) 
    : Op(op), LHS(lhs), RHS(rhs) {}
  virtual Value *Codegen();
};

/// CallExprAST - Класс узла выражения для вызова функции.
class CallExprAST : public ExprAST {
  std::string Callee;
  std::vector<ExprAST*> Args;
public:
  CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
    : Callee(callee), Args(args) {}
  virtual Value *Codegen();
};

/// PrototypeAST - Этот класс представляет "прототип" для функции,
/// который хранит её имя и имена аргументов (и, таким образом, 
/// неявно хранится число аргументов).
class PrototypeAST {
  std::string Name;
  std::vector<std::string> Args;
public:
  PrototypeAST(const std::string &name, const std::vector<std::string> &args)
    : Name(name), Args(args) {}
  
  Function *Codegen();
};

/// FunctionAST - Представляет определение самой функции
class FunctionAST {
  PrototypeAST *Proto;
  ExprAST *Body;
public:
  FunctionAST(PrototypeAST *proto, ExprAST *body)
    : Proto(proto), Body(body) {}
  
  Function *Codegen();
};

//===----------------------------------------------------------------------===//
// Parser (Парсер или Синтаксический Анализатор)
//===----------------------------------------------------------------------===//

/// 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* - Это небольшие вспомогательные функции для обработки ошибок.
ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }

static ExprAST *ParseExpression();

/// identifierexpr
///   ::= identifier
///   ::= identifier '(' expression* ')'
static ExprAST *ParseIdentifierExpr() {
  std::string IdName = IdentifierStr;
  
  getNextToken();  // получаем идентификатор.
  
  if (CurTok != '(') // Обычная переменная.
    return new VariableExprAST(IdName);
  
  // Вызов функции.
  getNextToken();  // получаем (
  std::vector<ExprAST*> Args;
  if (CurTok != ')') {
    while (1) {
      ExprAST *Arg = ParseExpression();
      if (!Arg) return 0;
      Args.push_back(Arg);

      if (CurTok == ')') break;

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

  // Получаем ')'.
  getNextToken();
  
  return new CallExprAST(IdName, Args);
}

/// numberexpr ::= number
static ExprAST *ParseNumberExpr() {
  ExprAST *Result = new NumberExprAST(NumVal);
  getNextToken(); // получаем число
  return Result;
}

/// parenexpr ::= '(' expression ')'
static ExprAST *ParseParenExpr() {
  getNextToken();  // получаем (.
  ExprAST *V = ParseExpression();
  if (!V) return 0;
  
  if (CurTok != ')')
    return Error("expected ')'");
  getNextToken(); // получаем ).
  return V;
}

/// primary
///   ::= identifierexpr
///   ::= numberexpr
///   ::= parenexpr
static ExprAST *ParsePrimary() {
  switch (CurTok) {
  default: return Error("unknown token when expecting an expression");
  case tok_identifier: return ParseIdentifierExpr();
  case tok_number:     return ParseNumberExpr();
  case '(':            return ParseParenExpr();
  }
}

/// binoprhs
///   ::= ('+' primary)*
static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
  // Если это бинарный оператор, получаем его приоритет
  while (1) {
    int TokPrec = GetTokPrecedence();
    
    // Если этот бинарный оператор связывает выражения по крайней мере так же, 
    // как текущий, то используем его
    if (TokPrec < ExprPrec)
      return LHS;
    
    // Отлично, мы знаем, что это бинарный оператор.
    int BinOp = CurTok;
    getNextToken();  // получаем бинарный оператор
    
    // Разобрать первичное выражение после бинарного оператора
    ExprAST *RHS = ParsePrimary();
    if (!RHS) return 0;
    
    // Если BinOp связан с RHS меньшим приоритетом, чем оператор после RHS, 
    // то берём часть вместе с RHS как LHS.
    int NextPrec = GetTokPrecedence();
    if (TokPrec < NextPrec) {
      RHS = ParseBinOpRHS(TokPrec+1, RHS);
      if (RHS == 0) return 0;
    }
    
    // Собираем LHS/RHS.
    LHS = new BinaryExprAST(BinOp, LHS, RHS);
  }
}

/// expression
///   ::= primary binoprhs
///
static ExprAST *ParseExpression() {
  ExprAST *LHS = ParsePrimary();
  if (!LHS) return 0;
  
  return ParseBinOpRHS(0, LHS);
}

/// prototype
///   ::= id '(' id* ')'
static PrototypeAST *ParsePrototype() {
  if (CurTok != tok_identifier)
    return ErrorP("Expected function name in prototype");

  std::string FnName = IdentifierStr;
  getNextToken();
  
  if (CurTok != '(')
    return ErrorP("Expected '(' in prototype");
  
  // Считываем список наименований аргументов.
  std::vector<std::string> ArgNames;
  while (getNextToken() == tok_identifier)
    ArgNames.push_back(IdentifierStr);
  if (CurTok != ')')
    return ErrorP("Expected ')' in prototype");
  
  // Все отлично.
  getNextToken();  // получаем ')'.
  
  return new PrototypeAST(FnName, ArgNames);
}

/// definition ::= 'def' prototype expression
static FunctionAST *ParseDefinition() {
  getNextToken();  // Получаем def.
  PrototypeAST *Proto = ParsePrototype();
  if (Proto == 0) return 0;

  if (ExprAST *E = ParseExpression())
    return new FunctionAST(Proto, E);
  return 0;
}

/// toplevelexpr ::= expression
static FunctionAST *ParseTopLevelExpr() {
  if (ExprAST *E = ParseExpression()) {
    // Создаём анонимный прототип.
    PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
    return new FunctionAST(Proto, E);
  }
  return 0;
}

/// external ::= 'extern' prototype
static PrototypeAST *ParseExtern() {
  getNextToken();  // получаем extern.
  return ParsePrototype();
}

//===----------------------------------------------------------------------===//
// Code Generation (Кодогенерация)
//===----------------------------------------------------------------------===//

static Module *TheModule;
static IRBuilder<> Builder(getGlobalContext());
static std::map<std::string, Value*> NamedValues;

Value *ErrorV(const char *Str) { Error(Str); return 0; }

Value *NumberExprAST::Codegen() {
  return ConstantFP::get(getGlobalContext(), APFloat(Val));
}

Value *VariableExprAST::Codegen() {
  // Ищем эту переменную в текущей функции.
  Value *V = NamedValues[Name];
  return V ? V : ErrorV("Unknown variable name");
}

Value *BinaryExprAST::Codegen() {
  Value *L = LHS->Codegen();
  Value *R = RHS->Codegen();
  if (L == 0 || R == 0) return 0;
  
  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");
    // Преобразование булевых 0 или 1 в вещественные 0.0 или 1.0
    return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
                                "booltmp");
  default: return ErrorV("invalid binary operator");
  }
}

Value *CallExprAST::Codegen() {
  // Ищем имя в глобальной таблице модуля.
  Function *CalleeF = TheModule->getFunction(Callee);
  if (CalleeF == 0)
    return ErrorV("Unknown function referenced");
  
  // Ошибка при несоответствии аргументов.
  if (CalleeF->arg_size() != Args.size())
    return ErrorV("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() == 0) return 0;
  }
  
  return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
}

Function *PrototypeAST::Codegen() {
  // Задаём тип функции:  double(double,double) и т.д.
  std::vector<const Type*> Doubles(Args.size(),
                                   Type::getDoubleTy(getGlobalContext()));
  FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
                                       Doubles, false);
  
  Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
  
  // Если функция (F) конфликтует с с добавленными функциями, значит уже использовано имя 'Name'.  
  // Если функция уже имеет тело, то не разрешаем переопределение или переоткрытие.
  if (F->getName() != Name) {
    // Удаляем ту функцию, что мы создали и используем существующую.
    F->eraseFromParent();
    F = TheModule->getFunction(Name);
    
    // Если функция (F) уже имеет тело, ругаемся.
    if (!F->empty()) {
      ErrorF("redefinition of function");
      return 0;
    }
    
    // Если функция (F) принимает другое число аргументов, ругаемся.
    if (F->arg_size() != Args.size()) {
      ErrorF("redefinition of function with different # args");
      return 0;
    }
  }
  
  // Задаём наименования для всех аргументов.
  unsigned Idx = 0;
  for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
       ++AI, ++Idx) {
    AI->setName(Args[Idx]);
    
    // Добавляем аргументы в таблицу символов переменных.
    NamedValues[Args[Idx]] = AI;
  }
  
  return F;
}

Function *FunctionAST::Codegen() {
  NamedValues.clear();
  
  Function *TheFunction = Proto->Codegen();
  if (TheFunction == 0)
    return 0;
  
  // Создаёт новый базовый блок для вставки.
  BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
  Builder.SetInsertPoint(BB);
  
  if (Value *RetVal = Body->Codegen()) {
    // Завершаем функцию.
    Builder.CreateRet(RetVal);

    // Валидация сгенерированного кода, проверка на непротиворечивость (связность).
    verifyFunction(*TheFunction);

    return TheFunction;
  }
  
  // При ошибке, удаляем созданную функцию.
  TheFunction->eraseFromParent();
  return 0;
}

//===----------------------------------------------------------------------===//
// Top-Level parsing (Парсинг верхнего уровня) и движок JIT
//===----------------------------------------------------------------------===//

static void HandleDefinition() {
  if (FunctionAST *F = ParseDefinition()) {
    if (Function *LF = F->Codegen()) {
      fprintf(stderr, "Read function definition:");
      LF->dump();
    }
  } else {
    // Пропускаем токен для восстановления после ошибки.
    getNextToken();
  }
}

static void HandleExtern() {
  if (PrototypeAST *P = ParseExtern()) {
    if (Function *F = P->Codegen()) {
      fprintf(stderr, "Read extern: ");
      F->dump();
    }
  } else {
    // Пропускаем токен для восстановления после ошибки.
    getNextToken();
  }
}

static void HandleTopLevelExpression() {
  // Evaluate a top-level expression into an anonymous function.
  if (FunctionAST *F = ParseTopLevelExpr()) {
    if (Function *LF = F->Codegen()) {
      fprintf(stderr, "Read top-level expression:");
      LF->dump();
    }
  } else {
    // Пропускаем токен для восстановления после ошибки.
    getNextToken();
  }
}

/// top ::= definition | external | expression | ';'
static void MainLoop() {
  while (1) {
    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;
    }
  }
}

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

/// putchard - выводит символ с переданным кодом и возвращает 0.
extern "C" 
double putchard(double X) {
  putchar((char)X);
  return 0;
}

//===----------------------------------------------------------------------===//
// Main driver code (Код основной программы)
//===----------------------------------------------------------------------===//

int main() {
  LLVMContext &Context = getGlobalContext();

  // Задаём стандартные бинарные операторы.
  // 1 - наименьший приоритет.
  BinopPrecedence['<'] = 10;
  BinopPrecedence['+'] = 20;
  BinopPrecedence['-'] = 20;
  BinopPrecedence['*'] = 40;  // наибольший приоритет.

  fprintf(stderr, "ready> ");
  getNextToken();

  // Создаём модуль, который будет хранить весь код.
  TheModule = new Module("my cool jit", Context);

  // Теперь запускаем основной "цикл интерпретатора".
  MainLoop();

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

  return 0;
}