How to become an author
Search
Write a publication
Pull to refresh

Создание языка программирования с использованием LLVM. Часть 4: Добавление JIT и поддержки оптимизатора

Reading time20 min
Views10K
Compilers*
Translation
Original author: Chris Lattner
Добро пожаловать в Главу 4 учебника «Создание языка программирования с LLVM». Предыдущие главы (1-я, 2-я и 3-я) описывали реализацию простейшего языка программирования и добавление в него ​​поддержки генерации LLVM IR. В этой главе описаны две новых техники: добавление поддержки оптимизатора и добавление поддержки JIT-компилятора. Эти дополнения продемонстрируют как получить хороший, эффективный код для нашего языка программирования Kaleidoscope.

Простейшее свёртывание констант (constant folding)


Наша демонстрация к Главе 3 элегантна и легко расширяема. К сожалению, она генерирует далеко не прекрасный код. IRBuilder, однако, предоставляет нам очевидные оптимизации при компиляции простого кода:

ready> def test(x) 1+2+x;
Read function definition:
define double @test(double %x) {
entry:
        %addtmp = fadd double 3.000000e+00, %x
        ret double %addtmp
}

Этот код — не буквальная транскрипция AST, построенного разбором входных данных. Иначе, было бы:

ready> def test(x) 1+2+x;
Read function definition:
define double @test(double %x) {
entry:
        %addtmp = fadd double 2.000000e+00, 1.000000e+00
        %addtmp1 = fadd double %addtmp, %x
        ret double %addtmp1
}

Свёртывание констант (constant folding), как мы видели выше, является очень часто применяемой и очень важной оптимизацией: настолько, что многие разработчики языков программирования осуществляют поддержку свёртки констант в AST.

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

Ну, это было легко :). На практике, мы рекомендуем всегда использовать IRBuilder при генерации кода. Он не имеет «синтаксических накладных расходов» при использовании (вам не придётся уродовать компилятор проверками констант повсюду), и в некоторых случаях это может значительно снизить количество генерируемого LLVM IR (особенно для языков с макропрепроцессорами или тех, которые используют много констант).

С другой стороны IRBuilder ограничен тем фактом, что он делает весь анализа кода «как есть», то есть с уже построенным кодом. Если взять чуть более сложный пример:

ready> def test(x) (1+2+x)*(x+(1+2));
ready> Read function definition:
define double @test(double %x) {
entry:
        %addtmp = fadd double 3.000000e+00, %x
        %addtmp1 = fadd double %x, 3.000000e+00
        %multmp = fmul double %addtmp, %addtmp1
        ret double %multmp
}

В этом случае левая и правая части произведения являются одним и тем же значением. Нам бы очень хотелось, чтобы генерировалось что-то вроде «tmp = х+3; result = tmp*tmp;» вместо двукратного вычисления «х+3».

К сожалению, никакой локальный анализ будет в не состоянии обнаружить и исправить это. Это требует двух преобразований: реассоциации выражения (для добавления лексической идентичности) и ликвидации общих подвыражений (Common Subexpression Elimination, CSE) для удаления избыточной инструкции сложения. К счастью, LLVM предоставляет широкий спектр оптимизаций, которые можно использовать в виде «проходов».

Проходы оптимизаций LLVM


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

LLVM поддерживает и включает в себя как полные проходы «по модулям», так и проходы «по функциям», просто работающие на одной функции, не учитывая при этом остальные. Для получения дополнительной информации о проходах и том, как они работают, смотрите документ "Как написать Проход" и "Список проходов LLVM".

Для Kaleidoscope в настоящее время мы генерируем функции «на лету» по одной за раз при вводе пользователем. Мы не ставим целью получение максимальной отдачи от оптимизации в текущем виде, но, тем не менее, мы хотим получать лёгкий и быстрый код. Таким образом, мы выберем несколько оптимизаций «по функциям», вводимым пользователем. Если бы мы хотели сделать «статический компилятор Kaleidoscope», то мы бы использовали почти то же код за исключением того, что мы бы откладывали запуск оптимизатора, пока весь файл не будет разобран.

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

  FunctionPassManager OurFPM(TheModule);

  // Настройка конвейера оптимизатора. Начинаем с информации о том, какие
  // структуры данных будут использованы в последующих проходах.
  OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
  // Обеспечиваем поддержку AliasAnalysis для GVN.
  OurFPM.add(createBasicAliasAnalysisPass());
  // Делаем оптимизации "peephole" и "bit-twiddling".
  OurFPM.add(createInstructionCombiningPass());
  // Реассоциация выражений.
  OurFPM.add(createReassociatePass());
  // Ликвидация общих подвыражений.
  OurFPM.add(createGVNPass());
  // Упрощение графа потока управления (удаление недоступных блоков и т.д.).
  OurFPM.add(createCFGSimplificationPass());

  OurFPM.doInitialization();

  // Сделаем его глобальным, чтобы другие его могли использовать.
  TheFPM = &OurFPM;

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

Этот код определяет FunctionPassManager с именем "OurFPM". При создании ему необходимо передавать указатель на модуль. Как только это сделано, мы используем ряд вызовов "add" для добавления проходов LLVM. Первый проход в большинстве случаев шаблонный, он необходим для того, чтобы последующие оптимизации знали о том, какие структуры данных использованы в программе. Переменная "TheExecutionEngine" связана с JIT, который мы получим в следующем разделе.

В данном случае мы решили добавить 4 прохода оптимизации. Проходы, которые мы выбрали, являются довольно стандартным набором «очищающих» оптимизаций, которые полезны для широкого спектра кода. Я не буду углубляться в то, что они делают, но поверьте, они являются хорошей отправной точкой :).

После настройки PassManager, мы должны его использовать. Мы запускаем его после генерации нашей новой функции (в FunctionAST::Codegen), но перед возвратом пользователю:

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

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

    // Оптимизация функции.
    TheFPM->run(*TheFunction);
    
    return TheFunction;
  }

Насколько вы видите, это довольно просто. FunctionPassManager оптимизирует и сразу обновляет LLVM Function*, улучшая (очень на это надеюсь) тело функции. Теперь попытаемся протестировать наш код еще раз:

ready> def test(x) (1+2+x)*(x+(1+2));
ready> Read function definition:
define double @test(double %x) {
entry:
        %addtmp = fadd double %x, 3.000000e+00
        %multmp = fmul double %addtmp, %addtmp
        ret double %multmp
}

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

LLVM предоставляет широкий спектр оптимизаций, которые могут быть использованы при определенных обстоятельствах. Доступна кое-какая документация о различных проходах, но она не очень-то полная. Другим хорошим источником идей для начала может послужить просмотр проходов, которые используют llvm-gcc или llvm-ld. Инструмент «opt» позволяет вам экспериментировать с проходами из командной строки и видеть, что они делают.

Теперь, когда у нас есть довольно неплохой код из нашего фронт-энда, можно поговорить о его выполнении!

Добавление JIT-компилятора


К коду, который доступен в LLVM IR можно применять разнообразные инструменты. Например, вы можете запустить оптимизацию для него (как мы это делали выше), вы можете вывести его в текстовой или бинарной формах, вы можете скомпилировать код в ассемблерный файл LLVM (.s) для некоторой платформы, или вы можете применить к нему JIT-компиляцию. Отличной штукой в представлении LLVM IR является то, что оно является «единым» между различными частями компилятора.

В этом разделе мы добавим поддержку JIT-компиляции для нашего интерпретатора. Основная идея Kaleidoscope том, что пользователь может ввести функцию или верхнеуровневое выражение и сразу же получать результат. Например, при вводе «1 + 2;», мы должны рассчитать и вывести 3, а при определении функции её можно будет вызывать ее из командной строки.

Для начала мы объявим и инициализируем JIT. Это делается с помощью добавления глобальной переменной и вызова в main:

static ExecutionEngine *TheExecutionEngine;
...
int main() {
  ..
  // Создание JIT.  Передаётся ссылка на модуль.
  TheExecutionEngine = EngineBuilder(TheModule).create();
  ..
}

Это создает абстрактный "Execution Engine" (Исполняющий движок), который может быть либо компилятором, либо LLVM-интерпретатором. LLVM автоматически выберет для вас JIT-компилятор, если он существует для вашей платформы, в противном случае он вернётся обратно к интерпретатору.

После создания ExecutionEngine, JIT готов к использованию. Существуют различные полезные API, но простейшим из них является метод "getPointerToFunction(F)". Этот метод JIT-компилирует указанную функцию LLVM и возвращает функциональный указатель на сгенерированный машинный код. В нашем случае это означает, что мы можем изменить код, разбирающий верхнеуровневое выражение, следующим образом:

static void HandleTopLevelExpression() {
  // Выполнение верхнеуровнего выражения в анонимной функции.
  if (FunctionAST *F = ParseTopLevelExpr()) {
    if (Function *LF = F->Codegen()) {
      LF->dump();  // Дамп функции.
    
      // JIT-функция, возвращающая функциональный указатель.
      void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
      
      // Приведение к верному типу (без аргументов, возращает double),
      // который может быть вызван как нативная функция.
      double (*FP)() = (double (*)())(intptr_t)FPtr;
      fprintf(stderr, "Evaluated to %f\n", FP());
    }

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

С помощью эти всего-лишь двух изменений мы теперь можем увидеть работу Kaleidoscope!

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

Evaluated to 9.000000

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

ready> def testfunc(x y) x + y*2;
Read function definition:
define double @testfunc(double %x, double %y) {
entry:
        %multmp = fmul double %y, 2.000000e+00
        %addtmp = fadd double %multmp, %x
        ret double %addtmp
}

ready> testfunc(4, 10);
define double @""() {
entry:
        %calltmp = call double @testfunc(double 4.000000e+00, double 1.000000e+01)
        ret double %calltmp
}

Evaluated to 24.000000

Это показывает, что мы можем выполнять пользовательский код, но есть один тонкий момент. Обратите внимание, что мы вызываем JIT на анонимной функции, вызывающей testfunc, но никогда не вызываем его для самой testfunc. На самом деле что JIT для всех неанонимных функций транзитивно вызван и скомпилирован из анонимной функции до возвращения из getPointerToFunction().

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

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

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

ready> sin(1.0);
Evaluated to 0.841471

ready> def foo(x) sin(x)*sin(x) + cos(x)*cos(x);
Read function definition:
define double @foo(double %x) {
entry:
        %calltmp = call double @sin(double %x)
        %multmp = fmul double %calltmp, %calltmp
        %calltmp2 = call double @cos(double %x)
        %multmp4 = fmul double %calltmp2, %calltmp2
        %addtmp = fadd double %multmp, %multmp4
        ret double %addtmp
}

ready> foo(4.0);
Evaluated to 1.000000

Вау, как же JIT узнал о sin и cos? Ответ на удивление прост: в этом примере JIT приступил к исполнению функции и добрался до вызова функции. Он понял, что функция еще не была скомпилирована ​​JIT и вызвал стандартный набор процедур для вычисления функции. В этом случае, для функции не определено её тело, поэтому JIT закончит вызовом "dlsym("sin")". Так как "sin" определён в адресном пространстве JIT, он просто напрямую вызывает библиотечную функцию.

LLVM JIT предоставляет ряд интерфейсов (смотрите в файле ExecutionEngine.h) для управления тем, как обрабатывается получение неопределённой функции. Это позволяет установить явное отображение между IR-объектами и адресами, позволяя динамически «на лету» разрешать имена функции, и даже позволяя ленивую JIT-компиляцию функций при их первом использовании.

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

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

Теперь мы можем производить простой вывод в консоль, используя что-то вроде такого кода: "extern putchard(х); putchard(120);", который печатает строчную 'x' в консоли (120 — это ASCII-код для 'x'). Аналогичный код может быть использован в Kaleidoscope для реализации файлового ввода-вывода, консольного ввода и многих других возможностей.

На этом завершается глава, посвящённая JIT и оптимизатору. На данный момент, мы можем JIT-компилировать и оптимизировать код не-Тьюринг-полного языка программирования, ориентированного на пользовательский ввод. Далее мы рассмотрим расширение нашего языка контролем потока управления, затрагивая по пути некоторые интересные вопросы LLVM IR.

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


А теперь, как всегда, полный листинг кода для наших работает, собрать который вы сможете так:

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

При компиляции на Linux, добавьте опцию "-rdynamic". Это гарантирует, что внешние функции во время выполнения будут разрешены должным образом.

А вот сам код:

#include "llvm/DerivedTypes.h"
#include "llvm/ExecutionEngine/ExecutionEngine.h"
#include "llvm/ExecutionEngine/JIT.h"
#include "llvm/LLVMContext.h"
#include "llvm/Module.h"
#include "llvm/PassManager.h"
#include "llvm/Analysis/Verifier.h"
#include "llvm/Analysis/Passes.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetSelect.h"
#include "llvm/Transforms/Scalar.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();  // eat binop
    
    // Разобрать первичное выражение после бинарного оператора
    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;
static FunctionPassManager *TheFPM;

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

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

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

static ExecutionEngine *TheExecutionEngine;

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()) {
      // JIT-функция, возвращающая функциональный указатель.
      void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
      
      // Приведение к верному типу (без аргументов, возращает double),
      // который может быть вызван как нативная функция.
      double (*FP)() = (double (*)())(intptr_t)FPtr;
      fprintf(stderr, "Evaluated to %f\n", FP());
    }
  } 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() {
  InitializeNativeTarget();
  LLVMContext &Context = getGlobalContext();

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

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

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

  // Создание JIT.  Необходимо передавать ссылку на модуль.
  std::string ErrStr;
TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create();
  if (!TheExecutionEngine) {
    fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
    exit(1);
  }

  FunctionPassManager OurFPM(TheModule);

  // Настройка конвейера оптимизатора. Начинаем с информации о том, какие
  // структуры данных будут использованы в последующих проходах.
  OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
  // Обеспечиваем поддержку AliasAnalysis для GVN.
  OurFPM.add(createBasicAliasAnalysisPass());
  // Делаем оптимизации "peephole" и "bit-twiddling".
  OurFPM.add(createInstructionCombiningPass());
  // Реассоциация выражений.
  OurFPM.add(createReassociatePass());
  // Ликвидация общих подвыражений.
  OurFPM.add(createGVNPass());
  // Упрощение графа потока управления (удаление недоступных блоков и т.д.).
  OurFPM.add(createCFGSimplificationPass());

  OurFPM.doInitialization();

  // Сделаем его глобальным, чтобы другие его могли использовать.
  TheFPM = &OurFPM;

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

  TheFPM = 0;

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

  return 0;
}


P.S. Дополнительные ссылки, полезные для изучения:
Tags:
Hubs:
Total votes 25: ↑21 and ↓4+17
Comments4
168
Karma
0
Rating
Alexander Marshalov @Amper

User

Send message

Articles

Your account

Sections

Information

Services

Support
© 2006–2024, Habr