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

Создание языка программирования с использованием LLVM. Часть 5: Расширение языка: Поток управления

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

If/Then/Else


Расширение Kaleidoscope до возможности использования if/then/else является довольно простой задачей. Требуется добавление поддержки этой «новой» концепции в лексический и синтаксический анализаторы, AST и кодогенератор. Этот хороший пример, потому что он показывает, как легко «наращивать» язык в течение времени, постепенно расширяя его по мере появления новых идей.

Перед тем, как мы добавим это расширение, необходимо поговорить о том, что же мы хотим получить в итоге. А мы хотим иметь возможность писать примерно так:

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

В Kaleidoscope каждая конструкция является выражением. Таким образом, выражение if/then/else, как и любые другие, должно возвращать значение. Так как мы используем в основном функциональную форму, мы должны вычислить условие, а затем вернуть значение "then" или "else" в зависимости от его значения. Это очень похоже на C-выражение "?:".

Семантика выражения if/then/else в том, что он вычисляет условие как логическое значение: 0.0 считается ложным, а всё остальное истинным. Если условие истинно, то вычисляется и возвращается первое подвыражение, если условие ложно — вычисляется и возвращается второе подвыражение. Так как Kaleidoscope позволяет побочные эффекты, это поведение важно закрепить.

Теперь, когда мы знаем, чего «хотим», начнём разбираться по частям.

Доработка лексического анализатора для поддержки If/Then/Else

Здесь всё просто. Сначала добавим новые значения для соответствующих токенов в перечисление:

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

Теперь мы распознаем новые ключевые слова в лексическом анализе. Это тоже просто:

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


Доработка AST для поддержки If/Then/Else

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

/// IfExprAST - Класс узла выражения для if/then/else.
class IfExprAST : public ExprAST {
  ExprAST *Cond, *Then, *Else;
public:
  IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
    : Cond(cond), Then(then), Else(_else) {}
  virtual Value *Codegen();
};

Узел AST имеет указатели на различные подвыражения.

Доработка парсера для поддержки If/Then/Else

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

/// ifexpr ::= 'if' expression 'then' expression 'else' expression
static ExprAST *ParseIfExpr() {
  getNextToken();  // Получаем if.
  
  // условие.
  ExprAST *Cond = ParseExpression();
  if (!Cond) return 0;
  
  if (CurTok != tok_then)
    return Error("expected then");
  getNextToken();  // Получаем then
  
  ExprAST *Then = ParseExpression();
  if (Then == 0) return 0;
  
  if (CurTok != tok_else)
    return Error("expected else");
  
  getNextToken();
  
  ExprAST *Else = ParseExpression();
  if (!Else) return 0;
  
  return new IfExprAST(Cond, Then, Else);
}

Далее подключим его в качестве первичного выражения:

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();
  case tok_if:         return ParseIfExpr();
  }
}


LLVM IR для If/Then/Else

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

Давайте рассмотрим простой пример:

extern foo();
extern bar();
def baz(x) if x then foo() else bar();

Если отключить оптимизации, то код, который вы получите (вскоре) от Kaleidoscope выглядит следующим образом:

declare double @foo()

declare double @bar()

define double @baz(double %x) {
entry:
	%ifcond = fcmp one double %x, 0.000000e+00
	br i1 %ifcond, label %then, label %else

then:		; preds = %entry
	%calltmp = call double @foo()
	br label %ifcont

else:		; preds = %entry
	%calltmp1 = call double @bar()
	br label %ifcont

ifcont:		; preds = %else, %then
	%iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
	ret double %iftmp
}

Для визуализации графа потока управления, вы можете использовать отличная фичу инструмента LLVM "opt". Если вы поместите этот LLVM IR в «t.ll» и запустите "llvm-as < t.ll | opt -analyze -view-cfg", появится окно, в котором вы увидите этот граф:

image

Другой способ получить его — вызвать "F->viewCFG()" или "F->viewCFGOnly()" (где F является "Function*") путем фактического включения вызова в код и перекомпилирования или вызова в отладчике. LLVM имеет много полезных возможностей для визуализации различных графиков.

Вернёмся к сгенерированному коду, он довольно прост: входной блока вычисляет условное выражение ( в нашем случае "x") и сравнивает результат с 0.0 с помощью инструкции "fcmp one". На основании результата этого выражения, код переходит либо в блок "then", либо в блок "else", которые содержат выражения для истиного/ложного случаев.

Как только блоки then/else завершились, обе эти ветки переходят к блоку "ifcont" для выполнения кода, который расположен после if/then/else. В данном случае единственное, что остается сделать — это вернуться в вызывающую функцию. Тогда возникает вопрос: как узнать код выражения для возврата?

Ответ на этот вопрос включает в себя важную операцию SSA: операцию Phi. Если вы не знакомы с SSA, то статья в википедии будет неплохим введением, а так же существуют и другие вводные статьи о нём, которые легко обнаружатся вашим любимым поисковиком. Краткая версия: «исполнение» операции Phi требует «запоминания» блока, из которого мы пришли. Операции Phi принимает значения и соответствующие входные блоки управления. В этом случае, если управление приходит из блока "then", он получает значение "calltmp". Если управление происходит от блока "else", он получает значение "calltmp1".

Сейчас вы, вероятно, начинаете думать: «О, нет! Это значит, что моему простому и элегантному фронт-энду придется начать генерировать SSA-форму, чтобы использовать LLVM!». К счастью, это не так, и мы настоятельно советуем НЕ реализовывать алгоритм построения SSA в вашем фронт-энде, если для этого нет по-настоящему важной причины. На практике, есть два вида значений в коде, написанном для среднестатистического императивного языка программирования, которым могли бы потребоваться узлы Phi:
  1. Код, предусматривающий пользовательские переменные: х = 1; х = х + 1;
  2. Значения, которые подразумеваются в структуре вашего AST, такие как узел Phi в данном случае.
В Главе 7 этого учебника («изменяемые переменные»), мы поговорим о №1. А пока просто поверьте мне, что вам не нужно построение SSA, чтобы справиться с этим случаем. Для №2 у вас есть выбор: использовать методы, которые мы опишем для №1, или вы можете непосредственно вставлять узлы Phi, если это удобно вам. В этом случае действительно очень просто генерировать узлы Phi, поэтому мы решили сделать именно так.

Ладно, пора генерировать код!

Кодогенерация для If/Then/Else

Для кодогенерации мы реализуем метод Codegen для IfExprAST:

Value *IfExprAST::Codegen() {
  Value *CondV = Cond->Codegen();
  if (CondV == 0) return 0;
  
  // Конвертация условия в булево сравнением с 0.0.
  CondV = Builder.CreateFCmpONE(CondV, 
                              ConstantFP::get(getGlobalContext(), APFloat(0.0)),
                                "ifcond");

Этот код прост и похож на то, что мы видели раньше. Мы получаем выражение для условия, а затем сравниваем это значение с нулём, чтобы получить его истинность как 1-битное (bool) значение.

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

  Builder.CreateCondBr(CondV, ThenBB, ElseBB);

Этот код создает базовые блоки, которые имеют отношение к if/then/else и соответствуют блокам в примере выше. Первая строка получает текущий объект Function (формируемой функции). Она получает его, спрашивая Builder о текущем базовом блоке и получая его «родителя» (текущую функцию).

Затем он создает три блока. Обратите внимание, что он передаёт "TheFunction" в конструктор блока "then". Это вызывает конструктор с автоматической вставкой нового блока в конец указанной функции. Два других блоков тоже создаются, но еще не вставлены в функцию.

После создания блоков мы можем сгенерировать условный переход, который выбирает между ними. Отметим, что неявное создание новых блоков никак не влияет на IRBuilder, так что вставка по прежнему происходим в том же блоке, в котором мы вошли. Также отметим, что он создает ветку для блока "then" и блока "else", хотя блок "else" ещё не вставлен в функцию. Но всё в порядке: это является стандартным способом поддержки LLVM ссылок «вперёд».

  // Генерируем значение.
  Builder.SetInsertPoint(ThenBB);
  
  Value *ThenV = Then->Codegen();
  if (ThenV == 0) return 0;
  
  Builder.CreateBr(MergeBB);
  // Codegen of 'Then' может изменить текущий блок, обновляем ThenBB для PHI.
  ThenBB = Builder.GetInsertBlock();

После вставки условного перехода, мы указываем Builder'у начать вставку в блок "then". Строго говоря, этот вызов перемещает курсор в конец указанного блока. Однако, поскольку блок "then" пуст, он также начинает нашу вставку в начале блока. :)

Как только курсор установлен, мы рекурсивно вызываем кодогенерацию выражения "then" из AST. Чтобы завершить блок "then", мы создаем безусловный переход к блоку слияния ветвей. Одним из интересных (и очень важных) аспектов LLVM IR является то, что он требует все базовые блоки «завершать» инструкцией потока управления, такой как return или branch. Это означает, что весь поток управления, включая передачу управления другому коду (fall throughs), должен явно присутствовать в LLVM IR. При нарушении этого правила верификатор вернёт ошибку.

Последняя строка здесь важна. При создании узла Phi в блоке слияния ветвей, мы должны задать пары блок/значение, указывающие как будет работать Phi. Важно отметить, что узел Phi ожидает получить входную точку для каждого предшественника блока в CFG. Почему же тогда мы получаем текущий блок, когда мы только что задали его в ThenBB пятью строками выше? Проблема в том, что выражение "then" может на самом деле может само изменить блок, который генерирует Builder, например, если оно содержит вложенные выражения "if/then/else". Так как рекурсивный вызов Codegen может произвольно менять текущий блок, мы должны получать текущие актуальные значения для кода, который будет создан в узле Phi.

  // Генерируем блок else.
  TheFunction->getBasicBlockList().push_back(ElseBB);
  Builder.SetInsertPoint(ElseBB);
  
  Value *ElseV = Else->Codegen();
  if (ElseV == 0) return 0;
  
  Builder.CreateBr(MergeBB);
  // Кодогенерация 'Else' может изменить текущий блок, обновляем ElseBB для PHI.
  ElseBB = Builder.GetInsertBlock();

Кодогенерация для блока "else" почти идентична кодогенерации для блока "then". Единственное существенное различие в первой строке, которая добавляет блок "else" в функцию. Напомним, ранее блок "else" был создан, но не добавлен в функцию. Теперь, когда блоки "then" и "else" сгенерированны, мы можем закончить с кодом их слияния:

  // Генерация блока слияния.
  TheFunction->getBasicBlockList().push_back(MergeBB);
  Builder.SetInsertPoint(MergeBB);
  PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2,
                                  "iftmp");
  
  PN->addIncoming(ThenV, ThenBB);
  PN->addIncoming(ElseV, ElseBB);
  return PN;
}

Первые две строки вам уже знакомы: первая добавляет блок "merge" для объекта функции. Второй блок перемещает курсор вставки так, что вновь созданный код будет всталяться в блок "merge". Затем нам нужно создать узел PHI и задать пары блок/значение для PHI.

Наконец, функция CodeGen возвращает узел Phi в качестве значения, вычисленного для выражения if/then/else. В нашем вышеприведённом примере, это возвращаемое значение будет поступать в код функции верхнего уровня, который создаст инструкцию возврата.

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

Цикл 'for'


Теперь, когда мы знаем, как добавлять основные управляющие конструкции в язык, у нас есть инструмент для добавления более мощных вещей. Попробуем добавить что-то более агрессивное — выражение "for":

 extern putchard(char)
 def printstar(n)
   for i = 1, i < n, 1.0 in
     putchard(42);  # ascii 42 = '*'
     
 # выводим 100 символов '*'
 printstar(100);

Это выражение определяет новую переменную (в данном случае "i"), которая итерируется от начального значения, пока условие (в данном случае "i < n") не станет истинным, увеличиваясь на значение шага (в этом случае "1.0"). Если значение шага опущено, то по-умолчанию оно равно 1.0. Цикл выполняет свое тело выражения. Так как у нас нет ничего лучше для возврата, мы просто определим цикл как всегда возвращающий 0.0. Позже, когда мы добавим изменяемые переменные, он окажется более полезным.

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

Доработка лексического анализатора для поддержки цикла 'for'

Лексический анализатор дополняется точно также, как и в случае с if/then/else:

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

  ... in gettok ...
  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;
  return tok_identifier;


Доработка AST для поддержки цикла 'for'

Узел AST тоже прост. Она хранит в своих узлах имя переменной и выражение тела цикла.

/// ForExprAST - Класс узла выражения для for/in.
class ForExprAST : public ExprAST {
  std::string VarName;
  ExprAST *Start, *End, *Step, *Body;
public:
  ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
             ExprAST *step, ExprAST *body)
    : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
  virtual Value *Codegen();
};


Доработка парсера для поддержки цикла 'for'

Изменения в коде синтаксического анализатора также довольно стандартные. Единственным интересным моментом здесь является обработка опционального значения шага. Парсер обрабатывает его, проверяя, присутствует ли вторая запятая. Если нет, он устанавливает значение шага в null в узле AST:

/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
static ExprAST *ParseForExpr() {
  getNextToken();  // получаем for.

  if (CurTok != tok_identifier)
    return Error("expected identifier after for");
  
  std::string IdName = IdentifierStr;
  getNextToken();  // получаем идентификатор.
  
  if (CurTok != '=')
    return Error("expected '=' after for");
  getNextToken();  // получаем '='.
  
  
  ExprAST *Start = ParseExpression();
  if (Start == 0) return 0;
  if (CurTok != ',')
    return Error("expected ',' after for start value");
  getNextToken();
  
  ExprAST *End = ParseExpression();
  if (End == 0) return 0;
  
  // Значение шага опционально.
  ExprAST *Step = 0;
  if (CurTok == ',') {
    getNextToken();
    Step = ParseExpression();
    if (Step == 0) return 0;
  }
  
  if (CurTok != tok_in)
    return Error("expected 'in' after for");
  getNextToken();  // Получаем 'in'.
  
  ExprAST *Body = ParseExpression();
  if (Body == 0) return 0;

  return new ForExprAST(IdName, Start, End, Step, Body);
}


LLVM IR для цикла 'for'

Теперь мы перейдем к интересной части: возьмёмся за генерацию LLVM IR. Для нашего вышеприведённого примера мы получаем вот такой LLVM IR (заметим, что этот дамп для ясности сгенерирован с отключённой оптимизацией ):

declare double @putchard(double)

define double @printstar(double %n) {
entry:
        ; initial value = 1.0 (inlined into phi)
	br label %loop

loop:		; preds = %loop, %entry
	%i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
        ; тело
	%calltmp = call double @putchard(double 4.200000e+01)
        ; инкремент
	%nextvar = fadd double %i, 1.000000e+00

        ; завершение
	%cmptmp = fcmp ult double %i, %n
	%booltmp = uitofp i1 %cmptmp to double
	%loopcond = fcmp one double %booltmp, 0.000000e+00
	br i1 %loopcond, label %loop, label %afterloop

afterloop:		; preds = %loop
        ; loop always returns 0.0
	ret double 0.000000e+00
}

Этот цикл содержит все те же конструкции, которые мы видели раньше: узел phi, несколько выражений и некоторые базовые блоки. Давайте посмотрим, как это совмещается.

Кодогенерация для цикла 'for'

Первая часть Codegen очень проста: мы просто получаем выражение для начального значения цикла:

Value *ForExprAST::Codegen() {
  // Emit the start code first, without 'variable' in scope.
  Value *StartVal = Start->Codegen();
  if (StartVal == 0) return 0;

Следующим шагом является создание базового блока LLVM для начала тела цикла. В вышеприведённом случае все тело цикла — это один блок, но помните, что код тела сам может состоять из нескольких блоков (например, если он содержит выражения if/then/else или for/in).

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

Этот код похож на тот, что мы видели для if/then/else. Мы запоминаем блок, из которого попали в цикл, так как он понадобится нам для создания узла Phi. Затем мы создаем фактический блок, начинающий цикл, и создаём безусловный переход между двумя блоками.

  // Начинаем вставку в LoopBB.
  Builder.SetInsertPoint(LoopBB);
  
  // Начинаем узел PHI с точки входа Start.
  PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str());
  Variable->addIncoming(StartVal, PreheaderBB);

Теперь, когда заголовок "preheader" для цикла задан, мы переходим к генерации кода тела цикла. Во-первых, мы перемещаем курсор и создаём узел PHI для переменной цикла. Так как мы уже знаем начальное значение, мы добавляем его в узел Phi. Обратите внимание, что Phi в конечном итоге получит второе значение, но мы пока не можем установить его (потому что оно ещё не существует!).

  // В цикле переменная определена равной узлу PHI.  Если она перекрывает 
  // существующую переменную, мы должны восстановить её так, чтобы сохранить.
  Value *OldVal = NamedValues[VarName];
  NamedValues[VarName] = Variable;
  
  // Генерируем тело цикла. Здесь, как и в любом другом выражении, может измениться
  // текущий базовый блок. Обратите внимание, что мы игнорируем значение, 
  // вычисленное телом, но не продолжаем при ошибке.
  if (Body->Codegen() == 0)
    return 0;

Теперь код становится более интересным. Наш цикл "for" вводит новую переменную в таблицу символов. Это означает, что наша таблица символов может содержать либо аргументы функции, либо переменные цикла. Прежде чем мы генерируем код тела цикла, мы добавляем переменную цикла как текущее значение для её наименования. Обратите внимание — вполне возможно, что уже есть переменная с тем же именем во внешней области. Можно легко сделать это ошибкой (выдавать ошибку и возвращать null, если уже есть запись для VarName), но мы разрешим перекрытие переменных. Для правильной обработки мы запоминаем потенциально перекрываемое значение в OldVal (который будет равно null, если нет перекрываемой переменной).

После задания переменной цикла в таблице символов, код рекурсивно генерируется в теле. Это позволяет телу использовать переменную цикла: любые ссылки на ней естественно находятся в таблице символов.

  // Генерируем значение шага.
  Value *StepVal;
  if (Step) {
    StepVal = Step->Codegen();
    if (StepVal == 0) return 0;
  } else {
    // Если не задан, используем 1.0.
    StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
  }
  
  Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");

Когда тело сгенерированно, вычисляем следующее значение переменной итерации, добавляя значение шага или 1.0, если оно не задано. "NextVar" будет значением переменной цикла на следующем шаге цикла.

  // Рассчитываем значение для условия завершения цикла.
  Value *EndCond = End->Codegen();
  if (EndCond == 0) return EndCond;
  
  // Конвертируем условие в булево сравнением с 0.0.
  EndCond = Builder.CreateFCmpONE(EndCond, 
                              ConstantFP::get(getGlobalContext(), APFloat(0.0)),
                                  "loopcond");

Наконец, мы рассчитываем значение выхода из цикла, чтобы определить, должен ли цикл быть завершён. Это почти тоже самое, что вычисление условия в if/then/else.

  // Создаём блок "после цикла" и вставляем его.
  BasicBlock *LoopEndBB = Builder.GetInsertBlock();
  BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
  
  // Вставляем условный переход в конец LoopEndBB.
  Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
  
  // Любой новый код будет вставлен в AfterBB.
  Builder.SetInsertPoint(AfterBB);

С полным кодом тела цикла, нам нужно только завершить поток управления для него. Этот код запоминает конец блока (для узла phi), а затем создает блок для выхода цикла ("afterloop"). На основании значения условия выхода он создает условный переход, который выбирает между выполнением цикла снова или выхода из цикла. Любое последующий код добавляется в блок "afterloop", так мы перемещаем курсор вставки именно туда.

  // Добавляем новый вход для узла PHI.
  Variable->addIncoming(NextVar, LoopEndBB);
  
  // Восстанавливаем перекрытую переменную.
  if (OldVal)
    NamedValues[VarName] = OldVal;
  else
    NamedValues.erase(VarName);
  
  // выражение for всегда возвращает 0.0.
  return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
}

Заключительный код делает уборку: теперь у нас есть значение "NextVar" и мы можем добавить входящее в узел PHI значение цикла. После этого мы удаляем переменную цикла из таблицы символов, так что её нет в области видимости после цикла. Наконец, генерируемый для цикла код всегда возвращает 0.0, так что мы возвращаемся из ForExprAST::Codegen.

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

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


Вот полный листинг кода, расширенный выражениями if/then/else и for… Собирается следующим образом:

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

И сам код:

#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,
  
  // управляющие конструкции
  tok_if = -6, tok_then = -7, tok_else = -8,
  tok_for = -9, tok_in = -10
};

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

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

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

  if (isdigit(LastChar) || LastChar == '.') {   // Число: [0-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;
    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(), 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();
};

/// IfExprAST - Класс узла выражения для if/then/else.
class IfExprAST : public ExprAST {
  ExprAST *Cond, *Then, *Else;
public:
  IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
  : Cond(cond), Then(then), Else(_else) {}
  virtual Value *Codegen();
};

/// ForExprAST - Класс узла выражения для for/in.
class ForExprAST : public ExprAST {
  std::string VarName;
  ExprAST *Start, *End, *Step, *Body;
public:
  ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
             ExprAST *step, ExprAST *body)
    : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
  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;
}

/// ifexpr ::= 'if' expression 'then' expression 'else' expression
static ExprAST *ParseIfExpr() {
  getNextToken();  // Получаем if.
  
  // условие.
  ExprAST *Cond = ParseExpression();
  if (!Cond) return 0;
  
  if (CurTok != tok_then)
    return Error("expected then");
  getNextToken();  // Получаем then
  
  ExprAST *Then = ParseExpression();
  if (Then == 0) return 0;
  
  if (CurTok != tok_else)
    return Error("expected else");
  
  getNextToken();
  
  ExprAST *Else = ParseExpression();
  if (!Else) return 0;
  
  return new IfExprAST(Cond, Then, Else);
}

/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
static ExprAST *ParseForExpr() {
  getNextToken();  // получаем for.

  if (CurTok != tok_identifier)
    return Error("expected identifier after for");
  
  std::string IdName = IdentifierStr;
  getNextToken();  // получаем идентификатор.
  
  if (CurTok != '=')
    return Error("expected '=' after for");
  getNextToken();  // получаем '='.
  
  
  ExprAST *Start = ParseExpression();
  if (Start == 0) return 0;
  if (CurTok != ',')
    return Error("expected ',' after for start value");
  getNextToken();
  
  ExprAST *End = ParseExpression();
  if (End == 0) return 0;
  
  // Значение шага опционально.
  ExprAST *Step = 0;
  if (CurTok == ',') {
    getNextToken();
    Step = ParseExpression();
    if (Step == 0) return 0;
  }
  
  if (CurTok != tok_in)
    return Error("expected 'in' after for");
  getNextToken();  // Получаем 'in'.
  
  ExprAST *Body = ParseExpression();
  if (Body == 0) return 0;

  return new ForExprAST(IdName, Start, End, Step, Body);
}

/// primary
///   ::= identifierexpr
///   ::= numberexpr
///   ::= parenexpr
///   ::= ifexpr
///   ::= forexpr
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();
  case tok_if:         return ParseIfExpr();
  case tok_for:        return ParseForExpr();
  }
}

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

Value *IfExprAST::Codegen() {
  Value *CondV = Cond->Codegen();
  if (CondV == 0) return 0;
  
  // Конвертация условия в булево сравнением с 0.0.
  CondV = Builder.CreateFCmpONE(CondV, 
                              ConstantFP::get(getGlobalContext(), APFloat(0.0)),
                                "ifcond");
  
  Function *TheFunction = Builder.GetInsertBlock()->getParent();
  
  // Создаём блоки для веток then и else.  Вставляем блок 'then' в
  // конец функции.
  BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
  BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
  BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
  
  Builder.CreateCondBr(CondV, ThenBB, ElseBB);
  
  // Генерируем значение.
  Builder.SetInsertPoint(ThenBB);
  
  Value *ThenV = Then->Codegen();
  if (ThenV == 0) return 0;
  
  Builder.CreateBr(MergeBB);
  // Кодогенерация 'Then' может изменить текущий блок, обновляем ThenBB для PHI.
  ThenBB = Builder.GetInsertBlock();
  
  // Генерируем блок else.
  TheFunction->getBasicBlockList().push_back(ElseBB);
  Builder.SetInsertPoint(ElseBB);
  
  Value *ElseV = Else->Codegen();
  if (ElseV == 0) return 0;
  
  Builder.CreateBr(MergeBB);
  // Кодогенерация 'Else' может изменить текущий блок, обновляем ElseBB для PHI.
  ElseBB = Builder.GetInsertBlock();
  
  // Генерация блока слияния.
  TheFunction->getBasicBlockList().push_back(MergeBB);
  Builder.SetInsertPoint(MergeBB);
  PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2,
                                  "iftmp");
  
  PN->addIncoming(ThenV, ThenBB);
  PN->addIncoming(ElseV, ElseBB);
  return PN;
}

Value *ForExprAST::Codegen() {
  // Output this as:
  //   ...
  //   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:
  
  // Emit the start code first, without 'variable' in scope.
  Value *StartVal = Start->Codegen();
  if (StartVal == 0) return 0;
  
  // Создаём новый базовый блок для заголовка цикла, вставляя после него
  // текущий блок.
  Function *TheFunction = Builder.GetInsertBlock()->getParent();
  BasicBlock *PreheaderBB = Builder.GetInsertBlock();
  BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
  
  // Вставляем явно безусловный переход из текущего блока к LoopBB.
  Builder.CreateBr(LoopBB);

  // Начинаем вставку в LoopBB.
  Builder.SetInsertPoint(LoopBB);
  
  // Начинаем узел PHI с точки входа Start.
  PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str());
  Variable->addIncoming(StartVal, PreheaderBB);
  
  // В цикле переменная определена равной узлу PHI.  Если она перекрывает 
  // существующую переменную, мы должны восстановить её так, чтобы сохранить.
  Value *OldVal = NamedValues[VarName];
  NamedValues[VarName] = Variable;
  
  // Генерируем тело цикла. Здесь, как и в любом другом выражении, может измениться
  // текущий базовый блок. Обратите внимание, что мы игнорируем значение, 
  // вычисленное телом, но не продолжаем при ошибке.
  if (Body->Codegen() == 0)
    return 0;
  
  // Генерируем значение шага.
  Value *StepVal;
  if (Step) {
    StepVal = Step->Codegen();
    if (StepVal == 0) return 0;
  } else {
    // Если не задан, используем 1.0.
    StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
  }
  
  Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");

  // Рассчитываем значение для условия завершения цикла.
  Value *EndCond = End->Codegen();
  if (EndCond == 0) return EndCond;
  
  // Конвертируем условие в булево сравнением с 0.0.
  EndCond = Builder.CreateFCmpONE(EndCond, 
                              ConstantFP::get(getGlobalContext(), APFloat(0.0)),
                                  "loopcond");
  
  // Создаём блок "после цикла" и вставляем его.
  BasicBlock *LoopEndBB = Builder.GetInsertBlock();
  BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "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);

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

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() {
  // Заворачиваем верхнеуровневое выражение в анонимную функцию.
  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;  // наибольший приоритет.

  // Prime the first token.
  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;
}
Tags:
Hubs:
Total votes 21: ↑19 and ↓2+17
Comments3
167
Karma
0
Rating
Alexander Marshalov @Amper

User

Send message

Articles

Show the best of all time

Your account

Sections

Information

Services

Support
© 2006–2024, Habr