Pull to refresh

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

Reading time 37 min
Views 7.8K
Original author: Chris Lattner
Оглавление:

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



7.1. Введение


Добро пожаловать в главу 7 руководства “Создание языка программирования с использованием LLVM”. В главах 1-6 мы построили полноценный, хотя и простой, функциональный язык программирования. На этом пути мы изучили некоторые техники парсинга, изучили, как строить и и как представлять AST, как построить LLVM IR, и как оптимизировать результирующий код, и как JIT компилирует его.

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

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

7.2. Почему это сложная задача?


Чтобы понять, почему изменяемые переменные вызывают трудности с построением SSA, рассмотрим предельно простой пример на C:

int G, H;
int test(_Bool Condition) {
  int X;
  if (Condition)
    X = G;
  else
    X = H;
  return X;
}

В этом примере есть переменная «Х», значение которой зависит от пути исполнения программы. Так как есть два возможных значения Х перед командой возврата, вставляется PHI-узел, объединяющий оба значения. LLVM IR для этого примера будет выглядеть как-то так:

@G = weak global i32 0   ; type of @G is i32*
@H = weak global i32 0   ; type of @H is i32*

define i32 @test(i1 %Condition) {
entry:
  br i1 %Condition, label %cond_true, label %cond_false

cond_true:
  %X.0 = load i32* @G
  br label %cond_next

cond_false:
  %X.1 = load i32* @H
  br label %cond_next

cond_next:
  %X.2 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
  ret i32 %X.2
}

В этом примере, загрузка из глобальных переменных G и H в LLVM IR производится явно, и они живы в ветках then/else оператора if (cond_true/cond_false). Для объединения входных значений, узел X.2 phi в блоке cond_next выбирает правильное значение в зависимости от того, откуда пришел поток управления: если из блока cond_false, то X.2 получает значение X.1.
Если же поток управления пришел из cond_true, переменная получает значение X.0. В этой главе мы не будем объяснить детали SSA-формы. За более подробной информацией обращайтесь к одному из многочисленных online-справочников.

Вопрос этой главы в том, кто разещает phi-узлы при спуске присваивания к изменяемой переменной. Эта проблема в том, что LLVM требует, чтобы IR был в SSA-форме: не существует режима «без SSA». Однако, конструирование SSA требует нетривиальных алгоритмов и структур данных, и было бы неудобно и затратно в каждом фонтенде воспроизводить эту логику.

7.3. Память в LLVM


Трюк в том, что, несмотря на то, что LLVM требует, чтобы все регистровые значения были в SSA-форме, он не требует (и не допускает), чтобы объекты памяти были в SSA-форме. В примере выше, заметим, что команды загрузки из G и H имеют прямой доступ к G и H: они не переименованы и не пронумерованы. В этом состоит отличие от некоторых других систем компиляторов, которые пытаются присвоить номера версий объектам в памяти. В LLVM, вместо того, чтобы производить анализ потока данных памяти в LLVM IR, это происходит в аналитических проходах, которые запускаются по требованию.

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

В LLVM, все операции доступа к памяти происходят явно, с помощью команд load/store, и тщательно спроектированы так, что нет необходимости в операторе взятия адреса. Отметим, что тп глобальных переменных @G/@H на самом деле «i32*», несмотря на то, что сами переменные объявлены как «i32». Это означает, что @G определяет место для i32 в области глобальных данных, но имя этой переменной на самом деле ссылается на адрес этого пространства. Стековые переменные работают так же, но, в отличие от глобальных переменных, они объявлены с командой alloca:

define i32 @example() {
entry:
  %X = alloca i32           ; тип %X - i32*.
  ...
  %tmp = load i32* %X       ; загрузка стекового значения %X из стека.
  %tmp2 = add i32 %tmp, 1   ; инкрементируем
  store i32 %tmp2, i32* %X  ; сохраняем
  ...

Этот код показывает пример того, как вы можете объявлять стековые переменные в LLVM IR и манипулировать ими. Стековая память, выделенная командой alloca, полностью обобщённая: вы можете передать адрес стекового слота в функцию, сохранить его в другой переменной, и т.п. В приведённом выше примере, мы можем переписать этот пример для использования техники «alloca» и избежать использования PHI-узлов.

@G = weak global i32 0   ; type of @G is i32*
@H = weak global i32 0   ; type of @H is i32*

define i32 @test(i1 %Condition) {
entry:
  %X = alloca i32           ; type of %X is i32*.
  br i1 %Condition, label %cond_true, label %cond_false

cond_true:
  %X.0 = load i32* @G
  store i32 %X.0, i32* %X   ; Сохраняем X
  br label %cond_next

cond_false:
  %X.1 = load i32* @H
  store i32 %X.1, i32* %X   ; Сохраняем  X
  br label %cond_next

cond_next:
  %X.2 = load i32* %X       ; Читаем X
  ret i32 %X.2
}

Итак, мы открыли способ обрабатывать произвольные изменяемые переменные без необходимости создания PHI-узлов:

Каждая изменяемая переменная становится стековой областью.
Каждое чтение переменной становится загрузкой из стека.
Каждая запись в переменную становится сохранением в стек.
Взятие адреса переменной — это просто непосредственное использование значения адреса в стеке.

Хотя мы решили нашу проблему, появилась другая: сейчас у нас происходит интенсивный обмен со стеком для очень простых и распространённых операций, что ухудшает производительность. К счастью для нас, оптимизатор LLVM имеет хорошо настроенный проход оптимизации под названием «mem2reg», обрабатывающий такие случаи, превращающий команды alloca в регистры SSA и вставляющий Phi-узлы, где это необходимо. Если вы пропустите код из примера выше через этот проход, вы получите:

$ llvm-as < example.ll | opt -mem2reg | llvm-dis
@G = weak global i32 0
@H = weak global i32 0

define i32 @test(i1 %Condition) {
entry:
  br i1 %Condition, label %cond_true, label %cond_false

cond_true:
  %X.0 = load i32* @G
  br label %cond_next

cond_false:
  %X.1 = load i32* @H
  br label %cond_next

cond_next:
  %X.01 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
  ret i32 %X.01
}

Проход mem2reg реализует стандартный алгоритм «iterated dominance frontier» для построения SSA-формы и имеет ряд оптимизаций, ускоряющих (очень общие) вырожденные случаи. Проход оптимизации mem2reg является ответом на вопрос, что делать с изменяемыми переменными, и мы очень рекомендуем положиться на него. Отметим, что mem2reg работает с переменными только при некоторых условиях:

  • mem2reg ориентирован на команды «alloca» (выделение памяти на стеке): он ищет команды «alloca» и, если может их обработать, делает это. Он не работает с глобальными переменными и выделением памяти в куче.
  • mem2reg ищет команды alloca только во входном блоке функции. Размещение во входном блоке гарантирует, что alloca выполняется однократно, что упрощает анализ.
  • mem2reg преобразует только те команды alloca, которые используются в прямых командах load и store. Если адрес стековой переменной передан в функцию, или используется некая забавная арифметика указателей, команда alloca не будет преобразована.
  • mem2reg работает только с командами alloca для значений первого класса (таких, как указатели, скалярные и векторные значения), и только если размер массива для выделения памяти равен 1 (или пропущен в файле .ll). mem2reg не способен преобразовать структуру или массив в регистры. Заметим, что проход «sroa» более мощный и может преобразовывать структуры, объединения и массивы во многих случаях.

Все эти свойства легко достижимы в большинстве императивных языков, и мы проиллюстрируем их ниже на примере Калейдоскопа. Последний вопрос, который вы можете задать: должен ли я беспокоится обо всём этом в моём фронтенде? Разве не лучше ли было, если бы я конструировал SSA-фрму напрямую, избежав использования оптимизирующего прохода mem2reg? Если коротко, мы настоятельно рекомендуем, чтобы вы использовали эту технику для построения SSA-формы, если только нет очень веских оснований этого не делать.

Эта техника:

Доказана и хорошо протестирована: clang использует эту технику для локальных изменяемых переменных. Также, в большинстве распространённых клиентах LLVM эта техника используется для их переменных. Вы можете быть уверены, что баги находятся быстро и исправляются на ранних стадиях.

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

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

И наконец, она проста для встраивания в ваш фронтенд и работы, и проста в реализации. Давайте сейчас расширим Калейдоскоп для работы с изменяемыми переменными!

7.4. Изменяеме пременные в Калейдоскопе


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

Возможность изменять переменную с помощью оператора "=".
Возможность определять новые переменные.

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

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

# рекурсивный вызов fib, мы уже делали это
def fib(x)
  if (x < 3) then
    1
  else
    fib(x-1)+fib(x-2);

# итеративная функция fib.
def fibi(x)
  var a = 1, b = 1, c in
  (for i = 3, i < x in
     c = a + b :
     a = b :
     b = c) :
  b;

# вызываем функцию.
fibi(10);

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

7.5. Переделываем существующие переменные в изменяемую форму¶


Таблица символов в Калейдоскопе во время кодогенерации представлена таблицей (map) «NamedValues». Таблица содержит указатели на значения LLVM «Value*», которые содержат значения двойной точности для именованных переменных. Для того, чтобы поддержать изменяемость переменных, нам нужно немного их изменить, так, чтобы таблица NamedValues содержала локации памяти переменных. Это изменеие является рефакторингом: оно изменяет структуру кода, но (само по себе) не изменяет поведения компилятора. Все эти изменения изолированы в кодогенераторе Калейдоскопа.

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

Чтобы начать переделывать Калейдоскоп, мы изменим таблицу NamedValues так, чтобы она содержала AllocaInst* вместо Value*. Когда мы сделаем это, компилятор C++ скажет нам, какие части кода нам нужно изменить:

static std::map<std::string, AllocaInst*> NamedValues;

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

/// CreateEntryBlockAlloca - Создаём команду alloca во входном блоке
/// функции. Она используется для изменяемых переменных и т.п.
static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,
                                          const std::string &VarName) {
  IRBuilder<> TmpB(&TheFunction->getEntryBlock(),
                 TheFunction->getEntryBlock().begin());
  return TmpB.CreateAlloca(Type::getDoubleTy(TheContext), 0,
                           VarName.c_str());
}

Этот забавно выглядящий код создаёт объект IRBuilder, указывающий на первую команду (.begin()) входного блока. Он создаёт инструкцию alloca с нужным именем и возвращает её. Так как все значения в Кадейдоскопе — вещественные числа с двойной точностью, нам не нужно передавать тип, чтобы использовать эту инструкцию.

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

Value *VariableExprAST::codegen() {
  // Находим переменную в функции
  Value *V = NamedValues[Name];
  if (!V)
    return LogErrorV("Unknown variable name");

  // Загрузка значения
  return Builder.CreateLoad(V, Name.c_str());
}

Как видите, всё совершенно прямолинейно. Сейчас нам нужно обновить те места кода, которые определяют переменную, чтобы вставить инструкцию alloca. Начнём с ForExprAST::codegen() (см. полный листинг кода для полной версии):

Function *TheFunction = Builder.GetInsertBlock()->getParent();

// Создаём инструкцию alloca для переменной во входном блоке
AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);

// Вначале генерируем стартовый код, без переменной.
Value *StartVal = Start->codegen();
if (!StartVal)
  return nullptr;

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

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

// Загружаем, инкрементируем, и сохраняем alloca.  Здесь обрабатывается случай
// когда переменная изменяется в теле цикла.
Value *CurVar = Builder.CreateLoad(Alloca);
Value *NextVar = Builder.CreateFAdd(CurVar, StepVal, "nextvar");
Builder.CreateStore(NextVar, Alloca);
...

Этот код фактически идентичен приведённому ранее коду, в котором мы разрешаем изменяемые переменные. Большая разница состоит в том, что мы больше не должны конструировать PHI-узел, и мы используем load/store для доступа к переменной, когда нам это нужно.

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

Function *FunctionAST::codegen() {
  ...
  Builder.SetInsertPoint(BB);

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

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

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

  if (Value *RetVal = Body->codegen()) {
    ...

Для каждого аргумента, мы создаём инструкцию alloca, записываем входное значение в alloca и регистрируем alloca как локацию памяти для аргумента. Этот метод вызывается FunctionAST::codegen() непосредственно после генерации входного блока функции.

Последняя часть миссии — добавить проход mem2reg, позволяющий нам снова сгенерировать хороший код:

// Преобразовать инструкции alloca в регистры.
TheFPM->add(createPromoteMemoryToRegisterPass());
// Делаем простую peephole-оптимизацию и оптимизацию битовых операций.
TheFPM->add(createInstructionCombiningPass());
// Переассоциация выражений
TheFPM->add(createReassociatePass());
...

Интересно посмотреть, как выглядит код до и после работы оптимизации mem2reg. Например, вот код нашей рекурсивной функции fib до и после оптимизации. До оптимизации:

define double @fib(double %x) {
entry:
  %x1 = alloca double
  store double %x, double* %x1
  %x2 = load double, double* %x1
  %cmptmp = fcmp ult double %x2, 3.000000e+00
  %booltmp = uitofp i1 %cmptmp to double
  %ifcond = fcmp one double %booltmp, 0.000000e+00
  br i1 %ifcond, label %then, label %else

then:       ; preds = %entry
  br label %ifcont

else:       ; preds = %entry
  %x3 = load double, double* %x1
  %subtmp = fsub double %x3, 1.000000e+00
  %calltmp = call double @fib(double %subtmp)
  %x4 = load double, double* %x1
  %subtmp5 = fsub double %x4, 2.000000e+00
  %calltmp6 = call double @fib(double %subtmp5)
  %addtmp = fadd double %calltmp, %calltmp6
  br label %ifcont

ifcont:     ; preds = %else, %then
  %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
  ret double %iftmp
}

Здесь только одна переменная (x, входной аргумент), но вы всё равно можете увидеть простую стратегию кодогенерации, которую мы используем. Во входном блоке, создаётся alloca, и начальное входное значение сохраняется туда. Каждая ссылка на переменную вызывает чтение из стека. Также, заметим, что мы не модифицируем выражение if/then/else, и оно по-прежнему вставляет PHI-узлы. Хотя мы можем сделать alloca и в этом случае, на самом деле проще создать PHI-узел, поэтому просто так и сделаем.

Вот код после прохода mem2reg:

define double @fib(double %x) {
entry:
  %cmptmp = fcmp ult double %x, 3.000000e+00
  %booltmp = uitofp i1 %cmptmp to double
  %ifcond = fcmp one double %booltmp, 0.000000e+00
  br i1 %ifcond, label %then, label %else

then:
  br label %ifcont

else:
  %subtmp = fsub double %x, 1.000000e+00
  %calltmp = call double @fib(double %subtmp)
  %subtmp5 = fsub double %x, 2.000000e+00
  %calltmp6 = call double @fib(double %subtmp5)
  %addtmp = fadd double %calltmp, %calltmp6
  br label %ifcont

ifcont:     ; preds = %else, %then
  %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
  ret double %iftmp
}

Это тривиальный случай для mem2reg, так как здесь нет посторных объявлений переменной. Цель, с которой мы показываем это — уберечь вас от желания сделать код неэффективным. После того, как выполнится остальная оптимизация, получаем:

define double @fib(double %x) {
entry:
  %cmptmp = fcmp ult double %x, 3.000000e+00
  %booltmp = uitofp i1 %cmptmp to double
  %ifcond = fcmp ueq double %booltmp, 0.000000e+00
  br i1 %ifcond, label %else, label %ifcont

else:
  %subtmp = fsub double %x, 1.000000e+00
  %calltmp = call double @fib(double %subtmp)
  %subtmp5 = fsub double %x, 2.000000e+00
  %calltmp6 = call double @fib(double %subtmp5)
  %addtmp = fadd double %calltmp, %calltmp6
  ret double %addtmp

ifcont:
  ret double 1.000000e+00
}

Здесь мы видим, что упрощающий проход решил клонировать инструкцию возврата в конец блока «else». Это позволило удалить некоторые ветки и PHI-узел.

Сейчас, когда таблица символов обновлена и содержит стековые переменные, добавим оператор присваивания.

7.6. Новый оператор присваивания


В нашем фреймворке добавление нового оператора присваивания делается очень просто. Парсим его, как любой другой бинарный оператор, но обрабатываем его сами (вместо того, чтобы позволить сделать это пользователю). Первым делом назначаем ему приоритет:

int main() {
  // Вводим стандартный бинарный оператор
  // 1 - самый низкий приоритет
  BinopPrecedence['='] = 2;
  BinopPrecedence['<'] = 10;
  BinopPrecedence['+'] = 20;
  BinopPrecedence['-'] = 20;

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

Value *BinaryExprAST::codegen() {
  // '=' - особый случай, т.к. мы не хотим генерировать выражение для LHS
  if (Op == '=') {
    // Присваивание требует, чтобы LHS было идентификатором.
    VariableExprAST *LHSE = dynamic_cast<VariableExprAST*>(LHS.get());
    if (!LHSE)
      return LogErrorV("destination of '=' must be a variable");

В отличие от других бинарных операторов, наш оператор присваивания не следует модели «сгенерировать LHS, сгенерировать RHS, выполлнить вычисления». Он обрабатывается как особый случай до того, как обрабатываются другие бинарные операторы. Другая странная вещь состоитт в том, что LHS обязательно должен быть переменной. Неверным будет написать "(x+1) = expr" — только выражения типа «x = expr» допустимы.

  // Генерируем код для RHS.
  Value *Val = RHS->codegen();
  if (!Val)
    return nullptr;

  // Находим имя
  Value *Variable = NamedValues[LHSE->getName()];
  if (!Variable)
    return LogErrorV("Unknown variable name");

  Builder.CreateStore(Val, Variable);
  return Val;
}
...

Когда у нас есть переменная, генерация кода для присваивания очень проста: мы генерируем RHS для присваивания, создаём инструкцию store, и возвращаем вычисленное значение. Возвращаемое значение позволяет составлять цепочки присваиваний, например «X = (Y = Z)».

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

# Function to print a double.
extern printd(x);

# Define ':' for sequencing: as a low-precedence operator that ignores operands
# and just returns the RHS.
def binary : 1 (x y) y;

def test(x)
  printd(x) :
  x = 4 :
  printd(x);

test(123);

При запуске, этот пример напечатает «123», затем «4», показав, что мы на самом деле изменили значение переменной! Хорошо, сейчас мы достигли цели, чтобы это заработало, в общем случае нужно конструировать SSA-форму. Однако, было бы реально полезно, если бы мы могли вводить наши собственные локальные переменные, давайте сделаем это!

7.7. Локальные переменные, определяемые пользователем


Добавление «var» и «in» похоже на любые другие расширения, которые мы сделали в Калейдоскопе: мы расширяем лексический анализатор, парсер, AST, и кодогенератор. Первый шаг для добавления нашей конструкции «var/in» — расширение лексического анализатора. Как и раньше, это тривиально, код будет выглядеть так:

enum Token {
  ...
  // определяем var 
  tok_var = -13
...
}
...
static int gettok() {
...
    if (IdentifierStr == "in")
      return tok_in;
    if (IdentifierStr == "binary")
      return tok_binary;
    if (IdentifierStr == "unary")
      return tok_unary;
    if (IdentifierStr == "var")
      return tok_var;
    return tok_identifier;
...

Следующий шаг — определить узел AST, который мы конструируем. Для «var/in», это выглядит так:

/// VarExprAST - класс выражения для var/in
class VarExprAST : public ExprAST {
  std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames;
  std::unique_ptr<ExprAST> Body;

public:
  VarExprAST(std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames,
             std::unique_ptr<ExprAST> Body)
    : VarNames(std::move(VarNames)), Body(std::move(Body)) {}

  Value *codegen() override;
};

«var/in» допускает определять сразу список имен, и каждое имя может опционально иметь инициализирующее значение. Мы сохраняем информацию в векторе VarNames. Также, var/in has имеет тело, тело может иметь доступ к переменным, определённым в var/in.
Когда это сделано, мы можем определить части парсера. Первое, что мы сделаем, добавим первичное выражение:

/// primary
///   ::= identifierexpr
///   ::= numberexpr
///   ::= parenexpr
///   ::= ifexpr
///   ::= forexpr
///   ::= varexpr
static std::unique_ptr<ExprAST> ParsePrimary() {
  switch (CurTok) {
  default:
    return LogError("unknown token when expecting an expression");
  case tok_identifier:
    return ParseIdentifierExpr();
  case tok_number:
    return ParseNumberExpr();
  case '(':
    return ParseParenExpr();
  case tok_if:
    return ParseIfExpr();
  case tok_for:
    return ParseForExpr();
  case tok_var:
    return ParseVarExpr();
  }
}

Затем определим ParseVarExpr:

/// varexpr ::= 'var' identifier ('=' expression)?
//                    (',' identifier ('=' expression)?)* 'in' expression
static std::unique_ptr<ExprAST> ParseVarExpr() {
  getNextToken();  // съедаем var.

  std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames;

  // Требуется по крайней мере одно имя
  if (CurTok != tok_identifier)
    return LogError("expected identifier after var");

Первая часть этого кода парсит список пар идентификатор/выражение в локальном векторе VarNames.

while (1) {
  std::string Name = IdentifierStr;
  getNextToken();  // съедаем идентификатор

  // читаем опциональный инициализатор
  std::unique_ptr<ExprAST> Init;
  if (CurTok == '=') {
    getNextToken(); // съедаем '='.

    Init = ParseExpression();
    if (!Init) return nullptr;
  }

  VarNames.push_back(std::make_pair(Name, std::move(Init)));

  // Конец списка переменных, выходим из цикла
  if (CurTok != ',') break;
  getNextToken(); // съедаем ','.

  if (CurTok != tok_identifier)
    return LogError("expected identifier list after var");
}

Когда все переменные распарсены, парсим тело и создаём узел AST.

  // В этой точке должно быть 'in'.
  if (CurTok != tok_in)
    return LogError("expected 'in' keyword after 'var'");
  getNextToken();  // eat 'in'.

  auto Body = ParseExpression();
  if (!Body)
    return nullptr;

  return llvm::make_unique<VarExprAST>(std::move(VarNames),
                                       std::move(Body));
}

Сейчас мы можем распарсить и представить код, и нам нужно поддержать генерацию кода LLVM IR для него. Это начало кода:

Value *VarExprAST::codegen() {
  std::vector<AllocaInst *> OldBindings;

  Function *TheFunction = Builder.GetInsertBlock()->getParent();

  // Регистрируем все переменные и генерируем инициализаторы
  for (unsigned i = 0, e = VarNames.size(); i != e; ++i) {
    const std::string &VarName = VarNames[i].first;
    ExprAST *Init = VarNames[i].second.get();

По сути, код циклически обходит все переменные, и обрабатывает их по одной за раз. Для каждой переменной, помещённой в таблицу символов, мы запоминаем предыдущее значение, которое мы заменяем на OldBindings.

  // Генерируем инициализатор перед добавлением переменной в область видимости, это предотвращает
  // инициализатор от ссылки на саму переменную,
  // и разрешает вещи вроде этого:
  //  var a = 1 in
  //    var a = a in ...   # ссылка на внешнюю переменную 'a'.
  Value *InitVal;
  if (Init) {
    InitVal = Init->codegen();
    if (!InitVal)
      return nullptr;
  } else { // если не определено, используем 0.0.
    InitVal = ConstantFP::get(TheContext, APFloat(0.0));
  }

  AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
  Builder.CreateStore(InitVal, Alloca);

  // Запоминаем старую связку переменных, чтобы можно было
  // восстановить её потом
  OldBindings.push_back(NamedValues[VarName]);

  // Запоминаем связку
  NamedValues[VarName] = Alloca;
}

В этом коде больше комментариев. Основная идея состоит в том, что мы генерируем инициализатор, создаём команду alloca, затем обновляем символ в таблице, чтобы он указывал на alloca. Когда все переменные записаны в таблицу символов, вычисляем тело выражения var/in:

// Генерируем код для тела, сейчас все переменные в области видимости
Value *BodyVal = Body->codegen();
if (!BodyVal)
  return nullptr;

Наконец, перед возвратом, восстанавливаем предыдущую связку переменных:

  // Все наши переменные в области видимости
  for (unsigned i = 0, e = VarNames.size(); i != e; ++i)
    NamedValues[VarNames[i].first] = OldBindings[i];

  // Возвращаем вычисленное значение
  return BodyVal;
}

Конечный результат всего этого состоит в том, что мы получили правильно размещённые в области видимости переменные, и мы даже (тривиальным образом) разрешили их изменять.

Сейчас мы закончили то, что хотели сделать. Наш пример итеративной функции fib из введения компилируется и прекрасно работает. Проход оптимизации mem2reg оптимизирует все наши стековые переменные в SSA-регистры, вставляя PHI-узлы где это необходимо, и наш фронтенд остался простым: нет никаких сложных алгоритмов и вычислений.

7.8. Полный листинг


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

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

Исходный код:

Код
#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/LegacyPassManager.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Support/TargetSelect.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/GVN.h"
#include "../include/KaleidoscopeJIT.h"
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <memory>
#include <string>
#include <utility>
#include <vector>

using namespace llvm;
using namespace llvm::orc;

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

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

 // команды
  tok_def = -2,
  tok_extern = -3,

  // первичные символы
  tok_identifier = -4,
  tok_number = -5,

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

  // операторы
  tok_binary = -11,
  tok_unary = -12,

  // определение переменных
  tok_var = -13
};

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

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

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

  if (isalpha(LastChar)) { // идентификатор: [a-zA-Z][a-zA-Z0-9]*
    IdentifierStr = LastChar;
    while (isalnum((LastChar = getchar())))
      IdentifierStr += LastChar;

    if (IdentifierStr == "def")
      return tok_def;
    if (IdentifierStr == "extern")
      return tok_extern;
    if (IdentifierStr == "if")
      return tok_if;
    if (IdentifierStr == "then")
      return tok_then;
    if (IdentifierStr == "else")
      return tok_else;
    if (IdentifierStr == "for")
      return tok_for;
    if (IdentifierStr == "in")
      return tok_in;
    if (IdentifierStr == "binary")
      return tok_binary;
    if (IdentifierStr == "unary")
      return tok_unary;
    if (IdentifierStr == "var")
      return tok_var;
    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(), nullptr);
    return tok_number;
  }

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

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

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

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

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

namespace {

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

  virtual Value *codegen() = 0;
};

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

public:
  NumberExprAST(double Val) : Val(Val) {}

  Value *codegen() override;
};

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

public:
  VariableExprAST(const std::string &Name) : Name(Name) {}

  Value *codegen() override;
  const std::string &getName() const { return Name; }
};

/// UnaryExprAST - Класс выражения для унарного оператора
class UnaryExprAST : public ExprAST {
  char Opcode;
  std::unique_ptr<ExprAST> Operand;

public:
  UnaryExprAST(char Opcode, std::unique_ptr<ExprAST> Operand)
      : Opcode(Opcode), Operand(std::move(Operand)) {}

  Value *codegen() override;
};

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

public:
  BinaryExprAST(char Op, std::unique_ptr<ExprAST> LHS,
                std::unique_ptr<ExprAST> RHS)
      : Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}

  Value *codegen() override;
};

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

public:
  CallExprAST(const std::string &Callee,
              std::vector<std::unique_ptr<ExprAST>> Args)
      : Callee(Callee), Args(std::move(Args)) {}

  Value *codegen() override;
};

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

public:
  IfExprAST(std::unique_ptr<ExprAST> Cond, std::unique_ptr<ExprAST> Then,
            std::unique_ptr<ExprAST> Else)
      : Cond(std::move(Cond)), Then(std::move(Then)), Else(std::move(Else)) {}

  Value *codegen() override;
};

/// ForExprAST - Класс выражения для for/in.
class ForExprAST : public ExprAST {
  std::string VarName;
  std::unique_ptr<ExprAST> Start, End, Step, Body;

public:
  ForExprAST(const std::string &VarName, std::unique_ptr<ExprAST> Start,
             std::unique_ptr<ExprAST> End, std::unique_ptr<ExprAST> Step,
             std::unique_ptr<ExprAST> Body)
      : VarName(VarName), Start(std::move(Start)), End(std::move(End)),
        Step(std::move(Step)), Body(std::move(Body)) {}

  Value *codegen() override;
};

/// VarExprAST - Класс выражения для var/in
class VarExprAST : public ExprAST {
  std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames;
  std::unique_ptr<ExprAST> Body;

public:
  VarExprAST(
      std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames,
      std::unique_ptr<ExprAST> Body)
      : VarNames(std::move(VarNames)), Body(std::move(Body)) {}

  Value *codegen() override;
};

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

public:
  PrototypeAST(const std::string &Name, std::vector<std::string> Args,
               bool IsOperator = false, unsigned Prec = 0)
      : Name(Name), Args(std::move(Args)), IsOperator(IsOperator),
        Precedence(Prec) {}

  Function *codegen();
  const std::string &getName() const { return Name; }

  bool isUnaryOp() const { return IsOperator && Args.size() == 1; }
  bool isBinaryOp() const { return IsOperator && Args.size() == 2; }

  char getOperatorName() const {
    assert(isUnaryOp() || isBinaryOp());
    return Name[Name.size() - 1];
  }

  unsigned getBinaryPrecedence() const { return Precedence; }
};

/// FunctionAST - Этот класс представляет определение функции
class FunctionAST {
  std::unique_ptr<PrototypeAST> Proto;
  std::unique_ptr<ExprAST> Body;

public:
  FunctionAST(std::unique_ptr<PrototypeAST> Proto,
              std::unique_ptr<ExprAST> Body)
      : Proto(std::move(Proto)), Body(std::move(Body)) {}

  Function *codegen();
};

} // конец анонимного пространства имен

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

/// CurTok/getNextToken - Представляет простой буфер токенов.  CurTok - текущий
/// токен, на котороый смотрит парсер.  getNextToken считывает другой токен из 
/// лексического анализатора и обновляет CurTok считанным результатом.
static int CurTok;
static int getNextToken() { return CurTok = gettok(); }

/// BinopPrecedence - Содержит приоритет каждого бинарного оператора,
/// который определён
static std::map<char, int> BinopPrecedence;

/// GetTokPrecedence - Возвращает приоритет бинарного оператора для текущего токена.
static int GetTokPrecedence() {
  if (!isascii(CurTok))
    return -1;

  // Убедимся, что бинарный оператор объявлен
  int TokPrec = BinopPrecedence[CurTok];
  if (TokPrec <= 0)
    return -1;
  return TokPrec;
}

/// Error* - Маленькая вспомогательная функция обработки ошибок.
std::unique_ptr<ExprAST> LogError(const char *Str) {
  fprintf(stderr, "Error: %s\n", Str);
  return nullptr;
}

std::unique_ptr<PrototypeAST> LogErrorP(const char *Str) {
  LogError(Str);
  return nullptr;
}

static std::unique_ptr<ExprAST> ParseExpression();

/// numberexpr ::= number
static std::unique_ptr<ExprAST> ParseNumberExpr() {
  auto Result = llvm::make_unique<NumberExprAST>(NumVal);
  getNextToken(); // съедаем число
  return std::move(Result);
}

/// parenexpr ::= '(' expression ')'
static std::unique_ptr<ExprAST> ParseParenExpr() {
  getNextToken(); // съедаем (.
  auto V = ParseExpression();
  if (!V)
    return nullptr;

  if (CurTok != ')')
    return LogError("expected ')'");
  getNextToken(); // съедаем ).
  return V;
}

/// identifierexpr
///   ::= identifier
///   ::= identifier '(' expression* ')'
static std::unique_ptr<ExprAST> ParseIdentifierExpr() {
  std::string IdName = IdentifierStr;

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

  if (CurTok != '(') // Простая переменная
    return llvm::make_unique<VariableExprAST>(IdName);

  // Call.
  getNextToken(); // съедаем (
  std::vector<std::unique_ptr<ExprAST>> Args;
  if (CurTok != ')') {
    while (true) {
      if (auto Arg = ParseExpression())
        Args.push_back(std::move(Arg));
      else
        return nullptr;

      if (CurTok == ')')
        break;

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

 // съедаем ')'.
  getNextToken();

  return llvm::make_unique<CallExprAST>(IdName, std::move(Args));
}

/// ifexpr ::= 'if' expression 'then' expression 'else' expression
static std::unique_ptr<ExprAST> ParseIfExpr() {
  getNextToken(); // eat the if.

  // условие
  auto Cond = ParseExpression();
  if (!Cond)
    return nullptr;

  if (CurTok != tok_then)
    return LogError("expected then");
  getNextToken(); // съедаем then

  auto Then = ParseExpression();
  if (!Then)
    return nullptr;

  if (CurTok != tok_else)
    return LogError("expected else");

  getNextToken();

  auto Else = ParseExpression();
  if (!Else)
    return nullptr;

  return llvm::make_unique<IfExprAST>(std::move(Cond), std::move(Then),
                                      std::move(Else));
}

/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
static std::unique_ptr<ExprAST> ParseForExpr() {
  getNextToken(); // eat the for.

  if (CurTok != tok_identifier)
    return LogError("expected identifier after for");

  std::string IdName = IdentifierStr;
  getNextToken(); // съедаем идентификатор

  if (CurTok != '=')
    return LogError("expected '=' after for");
  getNextToken(); // съедаем '='.

  auto Start = ParseExpression();
  if (!Start)
    return nullptr;
  if (CurTok != ',')
    return LogError("expected ',' after for start value");
  getNextToken();

  auto End = ParseExpression();
  if (!End)
    return nullptr;

  // значение шага опционально
  std::unique_ptr<ExprAST> Step;
  if (CurTok == ',') {
    getNextToken();
    Step = ParseExpression();
    if (!Step)
      return nullptr;
  }

  if (CurTok != tok_in)
    return LogError("expected 'in' after for");
  getNextToken(); // съедаем 'in'.

  auto Body = ParseExpression();
  if (!Body)
    return nullptr;

  return llvm::make_unique<ForExprAST>(IdName, std::move(Start), std::move(End),
                                       std::move(Step), std::move(Body));
}

/// varexpr ::= 'var' identifier ('=' expression)?
//                    (',' identifier ('=' expression)?)* 'in' expression
static std::unique_ptr<ExprAST> ParseVarExpr() {
  getNextToken(); // съедаем var.

  std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames;

  // Требуется как минимум одна переменная
  if (CurTok != tok_identifier)
    return LogError("expected identifier after var");

  while (true) {
    std::string Name = IdentifierStr;
    getNextToken(); // съедаем идентификатор

    // Read the optional initializer.
    std::unique_ptr<ExprAST> Init = nullptr;
    if (CurTok == '=') {
      getNextToken(); // съедаем '='.

      Init = ParseExpression();
      if (!Init)
        return nullptr;
    }

    VarNames.push_back(std::make_pair(Name, std::move(Init)));

    // End of var list, exit loop.
    if (CurTok != ',')
      break;
    getNextToken(); // съедаем ','.

    if (CurTok != tok_identifier)
      return LogError("expected identifier list after var");
  }

  // At this point, we have to have 'in'.
  if (CurTok != tok_in)
    return LogError("expected 'in' keyword after 'var'");
  getNextToken(); // съедаем 'in'.

  auto Body = ParseExpression();
  if (!Body)
    return nullptr;

  return llvm::make_unique<VarExprAST>(std::move(VarNames), std::move(Body));
}

/// primary
///   ::= identifierexpr
///   ::= numberexpr
///   ::= parenexpr
///   ::= ifexpr
///   ::= forexpr
///   ::= varexpr
static std::unique_ptr<ExprAST> ParsePrimary() {
  switch (CurTok) {
  default:
    return LogError("unknown token when expecting an expression");
  case tok_identifier:
    return ParseIdentifierExpr();
  case tok_number:
    return ParseNumberExpr();
  case '(':
    return ParseParenExpr();
  case tok_if:
    return ParseIfExpr();
  case tok_for:
    return ParseForExpr();
  case tok_var:
    return ParseVarExpr();
  }
}

/// unary
///   ::= primary
///   ::= '!' unary
static std::unique_ptr<ExprAST> ParseUnary() {
  // если текущий токен не является оператором, он должен быть первичным выражением.
  if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
    return ParsePrimary();

  // если это унарный оператор, считываем его
  int Opc = CurTok;
  getNextToken();
  if (auto Operand = ParseUnary())
    return llvm::make_unique<UnaryExprAST>(Opc, std::move(Operand));
  return nullptr;
}

/// binoprhs
///   ::= ('+' unary)*
static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
                                              std::unique_ptr<ExprAST> LHS) {
  // Если это бинарный оператор, находим его приоритет
  while (true) {
    int TokPrec = GetTokPrecedence();

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

    // Теперь мы знаем, что это бинарный оператор
    int BinOp = CurTok;
    getNextToken(); // eat binop

    // Парсим унарное выражение после бинарного оператора
    auto RHS = ParseUnary();
    if (!RHS)
      return nullptr;

    // Если BinOp меньше связан с RHS, чем оператор после RHS, пусть
    // сохранённый оператор примет RHS как свой LHS.
    int NextPrec = GetTokPrecedence();
    if (TokPrec < NextPrec) {
      RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS));
      if (!RHS)
        return nullptr;
    }

    // Объединяем LHS/RHS.
    LHS =
        llvm::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS));
  }
}

/// expression
///   ::= unary binoprhs
///
static std::unique_ptr<ExprAST> ParseExpression() {
  auto LHS = ParseUnary();
  if (!LHS)
    return nullptr;

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

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

  unsigned Kind = 0; // 0 = идентификатор, 1 = унарный, 2 = бинарный.
  unsigned BinaryPrecedence = 30;

  switch (CurTok) {
  default:
    return LogErrorP("Expected function name in prototype");
  case tok_identifier:
    FnName = IdentifierStr;
    Kind = 0;
    getNextToken();
    break;
  case tok_unary:
    getNextToken();
    if (!isascii(CurTok))
      return LogErrorP("Expected unary operator");
    FnName = "unary";
    FnName += (char)CurTok;
    Kind = 1;
    getNextToken();
    break;
  case tok_binary:
    getNextToken();
    if (!isascii(CurTok))
      return LogErrorP("Expected binary operator");
    FnName = "binary";
    FnName += (char)CurTok;
    Kind = 2;
    getNextToken();

    // Считываем приоритет, если он есть
    if (CurTok == tok_number) {
      if (NumVal < 1 || NumVal > 100)
        return LogErrorP("Invalid precedence: must be 1..100");
      BinaryPrecedence = (unsigned)NumVal;
      getNextToken();
    }
    break;
  }

  if (CurTok != '(')
    return LogErrorP("Expected '(' in prototype");

  std::vector<std::string> ArgNames;
  while (getNextToken() == tok_identifier)
    ArgNames.push_back(IdentifierStr);
  if (CurTok != ')')
    return LogErrorP("Expected ')' in prototype");

  // успех.
  getNextToken(); // eat ')'.

  // Проверяем, что количество аргументов правильно
  if (Kind && ArgNames.size() != Kind)
    return LogErrorP("Invalid number of operands for operator");

  return llvm::make_unique<PrototypeAST>(FnName, ArgNames, Kind != 0,
                                         BinaryPrecedence);
}

/// definition ::= 'def' prototype expression
static std::unique_ptr<FunctionAST> ParseDefinition() {
  getNextToken(); // съедаем def.
  auto Proto = ParsePrototype();
  if (!Proto)
    return nullptr;

  if (auto E = ParseExpression())
    return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E));
  return nullptr;
}

/// toplevelexpr ::= expression
static std::unique_ptr<FunctionAST> ParseTopLevelExpr() {
  if (auto E = ParseExpression()) {
    // Создаём анонимный прототип
    auto Proto = llvm::make_unique<PrototypeAST>("__anon_expr",
                                                 std::vector<std::string>());
    return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E));
  }
  return nullptr;
}

/// external ::= 'extern' prototype
static std::unique_ptr<PrototypeAST> ParseExtern() {
  getNextToken(); // eat extern.
  return ParsePrototype();
}

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

static LLVMContext TheContext;
static IRBuilder<> Builder(TheContext);
static std::unique_ptr<Module> TheModule;
static std::map<std::string, AllocaInst *> NamedValues;
static std::unique_ptr<legacy::FunctionPassManager> TheFPM;
static std::unique_ptr<KaleidoscopeJIT> TheJIT;
static std::map<std::string, std::unique_ptr<PrototypeAST>> FunctionProtos;

Value *LogErrorV(const char *Str) {
  LogError(Str);
  return nullptr;
}

Function *getFunction(std::string Name) {
  // Вначале проверяем, добавлена ли уже функция в текущий модуль.
  if (auto *F = TheModule->getFunction(Name))
    return F;

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

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

/// CreateEntryBlockAlloca - Создаём инструкцию alloca во входном блоке
/// функции.  Она используется для изменяемых переменных.
static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,
                                          const std::string &VarName) {
  IRBuilder<> TmpB(&TheFunction->getEntryBlock(),
                   TheFunction->getEntryBlock().begin());
  return TmpB.CreateAlloca(Type::getDoubleTy(TheContext), nullptr, VarName);
}

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

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

  // Загружаем значение
  return Builder.CreateLoad(V, Name.c_str());
}

Value *UnaryExprAST::codegen() {
  Value *OperandV = Operand->codegen();
  if (!OperandV)
    return nullptr;

  Function *F = getFunction(std::string("unary") + Opcode);
  if (!F)
    return LogErrorV("Unknown unary operator");

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

Value *BinaryExprAST::codegen() {
  // Особый случай для '=', т.к. мы не хотим генерировать LHS как выражение
  if (Op == '=') {
    // Присваивание требует, чтобы LHS было идентификатором
    // Подразумевается, что мы компилируем без RTTI, т.к. LLVM компилируется так
    // по умолчанию.  Если вы компилируете LLVM с RTTI здесь надо поменять на
    // dynamic_cast для автоматической проверки ошибок.
    VariableExprAST *LHSE = static_cast<VariableExprAST *>(LHS.get());
    if (!LHSE)
      return LogErrorV("destination of '=' must be a variable");
    // Генерируем код RHS.
    Value *Val = RHS->codegen();
    if (!Val)
      return nullptr;

    // Находим имя
    Value *Variable = NamedValues[LHSE->getName()];
    if (!Variable)
      return LogErrorV("Unknown variable name");

    Builder.CreateStore(Val, Variable);
    return Val;
  }

  Value *L = LHS->codegen();
  Value *R = RHS->codegen();
  if (!L || !R)
    return nullptr;

  switch (Op) {
  case '+':
    return Builder.CreateFAdd(L, R, "addtmp");
  case '-':
    return Builder.CreateFSub(L, R, "subtmp");
  case '*':
    return Builder.CreateFMul(L, R, "multmp");
  case '<':
    L = Builder.CreateFCmpULT(L, R, "cmptmp");
    // Преобразуем bool 0/1 в double 0.0 or 1.0
    return Builder.CreateUIToFP(L, Type::getDoubleTy(TheContext), "booltmp");
  default:
    break;
  }

  // Если это не встроенный бинарный оператор, он должен быть определён пользователем. Генерируем
  // вызов функции для него.
  Function *F = getFunction(std::string("binary") + Op);
  assert(F && "binary operator not found!");

  Value *Ops[] = {L, R};
  return Builder.CreateCall(F, Ops, "binop");
}

Value *CallExprAST::codegen() {
  // Ищем имя в глобальной таблице модуля
  Function *CalleeF = getFunction(Callee);
  if (!CalleeF)
    return LogErrorV("Unknown function referenced");

  // Ошибка, если аргументы не совпадают.
  if (CalleeF->arg_size() != Args.size())
    return LogErrorV("Incorrect # arguments passed");

  std::vector<Value *> ArgsV;
  for (unsigned i = 0, e = Args.size(); i != e; ++i) {
    ArgsV.push_back(Args[i]->codegen());
    if (!ArgsV.back())
      return nullptr;
  }

  return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
}

Value *IfExprAST::codegen() {
  Value *CondV = Cond->codegen();
  if (!CondV)
    return nullptr;

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

  Function *TheFunction = Builder.GetInsertBlock()->getParent();

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

  Builder.CreateCondBr(CondV, ThenBB, ElseBB);

  // Генерируем значение.
  Builder.SetInsertPoint(ThenBB);

  Value *ThenV = Then->codegen();
  if (!ThenV)
    return nullptr;

  Builder.CreateBr(MergeBB);
  // Генерация кода для 'Then' может изменить текущий блок, обновляем ThenBB для PHI.
  ThenBB = Builder.GetInsertBlock();

  // Генерируем блок "else"
  TheFunction->getBasicBlockList().push_back(ElseBB);
  Builder.SetInsertPoint(ElseBB);

  Value *ElseV = Else->codegen();
  if (!ElseV)
    return nullptr;

  Builder.CreateBr(MergeBB);
  // Генерация кода для 'Else' может изменить текущий блок, обновляем ElseBB для PHI.
  ElseBB = Builder.GetInsertBlock();

  // Генерируем объединяющий блок
  TheFunction->getBasicBlockList().push_back(MergeBB);
  Builder.SetInsertPoint(MergeBB);
  PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(TheContext), 2, "iftmp");

  PN->addIncoming(ThenV, ThenBB);
  PN->addIncoming(ElseV, ElseBB);
  return PN;
}

// Выводим for-loop как:
//   var = alloca double
//   ...
//   start = startexpr
//   store start -> var
//   goto loop
// loop:
//   ...
//   bodyexpr
//   ...
// loopend:
//   step = stepexpr
//   endcond = endexpr
//
//   curvar = load var
//   nextvar = curvar + step
//   store nextvar -> var
//   br endcond, loop, endloop
// outloop:
Value *ForExprAST::codegen() {
  Function *TheFunction = Builder.GetInsertBlock()->getParent();

  // Создаем инструкцию alloca для переменной в начальном блоке
  AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);

  // Генерируем вначале стартовый код, без 'variable' в области видимости
  Value *StartVal = Start->codegen();
  if (!StartVal)
    return nullptr;

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

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

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

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

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

  // Генерируем тело цикла.  Оно, как любое другое выражение, может изменить
  // текущий BB. Отметим, что мы игнорируем значение, вычисленное телом цикла, но не
  // допускаем ошибки.
  if (!Body->codegen())
    return nullptr;

  // Генерируем значение шага
  Value *StepVal = nullptr;
  if (Step) {
    StepVal = Step->codegen();
    if (!StepVal)
      return nullptr;
  } else {
    // Если не определено, используем 1.0.
    StepVal = ConstantFP::get(TheContext, APFloat(1.0));
  }

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

  // Загружаем, инкрементируем, и сохраняем alloca.  Обрабатываем случай
  // когда переменная цикла изменяется в теле цикла
  Value *CurVar = Builder.CreateLoad(Alloca, VarName.c_str());
  Value *NextVar = Builder.CreateFAdd(CurVar, StepVal, "nextvar");
  Builder.CreateStore(NextVar, Alloca);

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

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

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

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

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

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

Value *VarExprAST::codegen() {
  std::vector<AllocaInst *> OldBindings;

  Function *TheFunction = Builder.GetInsertBlock()->getParent();

  // Регистрируем все переменные и ненерируем инициализаторы
  for (unsigned i = 0, e = VarNames.size(); i != e; ++i) {
    const std::string &VarName = VarNames[i].first;
    ExprAST *Init = VarNames[i].second.get();

    // Генерируем инициализатор перед добавлением переменной, это предотвращает
    // инициализатор от ссылки на саму переменную, и разрешает
    // l такие вещи:
    //  var a = 1 in
    //    var a = a in ...   # ссылка на внешнюю 'a'.
    Value *InitVal;
    if (Init) {
      InitVal = Init->codegen();
      if (!InitVal)
        return nullptr;
    } else { // If not specified, use 0.0.
      InitVal = ConstantFP::get(TheContext, APFloat(0.0));
    }

    AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
    Builder.CreateStore(InitVal, Alloca);

    // Запоминаем связку переменных
    OldBindings.push_back(NamedValues[VarName]);

    // Запоминаеи связку
    NamedValues[VarName] = Alloca;
  }

  // Генерируем тело цикла со всеми переменными
  Value *BodyVal = Body->codegen();
  if (!BodyVal)
    return nullptr;

  // Извлекаем все переменные
  for (unsigned i = 0, e = VarNames.size(); i != e; ++i)
    NamedValues[VarNames[i].first] = OldBindings[i];

  // Возвращаем значение тела цикла
  return BodyVal;
}

Function *PrototypeAST::codegen() {
  // Создаём тип функции:  double(double,double) etc.
  std::vector<Type *> Doubles(Args.size(), Type::getDoubleTy(TheContext));
  FunctionType *FT =
      FunctionType::get(Type::getDoubleTy(TheContext), Doubles, false);

  Function *F =
      Function::Create(FT, Function::ExternalLinkage, Name, TheModule.get());

  // Устанавливаем имена аргументов
  unsigned Idx = 0;
  for (auto &Arg : F->args())
    Arg.setName(Args[Idx++]);

  return F;
}

Function *FunctionAST::codegen() {
  // Переносим владение прототипом в мэп FunctionProtos, но сохраняем
  // ссылку для дальнейшего использования.
  auto &P = *Proto;
  FunctionProtos[Proto->getName()] = std::move(Proto);
  Function *TheFunction = getFunction(P.getName());
  if (!TheFunction)
    return nullptr;

  // Если это оператор, устанавливаем его
  if (P.isBinaryOp())
    BinopPrecedence[P.getOperatorName()] = P.getBinaryPrecedence();

  // Создаём новый базовый блок для вставки кода
  BasicBlock *BB = BasicBlock::Create(TheContext, "entry", TheFunction);
  Builder.SetInsertPoint(BB);

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

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

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

  if (Value *RetVal = Body->codegen()) {
    // Finish off the function.
    Builder.CreateRet(RetVal);

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

    // Запускаем оптимизатор для функции
    TheFPM->run(*TheFunction);

    return TheFunction;
  }

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

  if (P.isBinaryOp())
    BinopPrecedence.erase(P.getOperatorName());
  return nullptr;
}

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

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

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

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

  TheFPM->doInitialization();
}

static void HandleDefinition() {
  if (auto FnAST = ParseDefinition()) {
    if (auto *FnIR = FnAST->codegen()) {
      fprintf(stderr, "Read function definition:");
      FnIR->print(errs());
      fprintf(stderr, "\n");
      TheJIT->addModule(std::move(TheModule));
      InitializeModuleAndPassManager();
    }
  } else {
    // Пропускаем токен для восстановления после ошибки
    getNextToken();
  }
}

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

static void HandleTopLevelExpression() {
  // Вычисляем высокоуровневое выражения для анонимной функции
  if (auto FnAST = ParseTopLevelExpr()) {
    if (FnAST->codegen()) {
      //выполняем JIT для модуля, содержащего анонимное выражение
      // освободим его позже
      auto H = TheJIT->addModule(std::move(TheModule));
      InitializeModuleAndPassManager();

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

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

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

/// top ::= definition | external | expression | ';'
static void MainLoop() {
  while (true) {
    fprintf(stderr, "ready> ");
    switch (CurTok) {
    case tok_eof:
      return;
    case ';': //игнорируем точки с запятой на верхнем уровне
      getNextToken();
      break;
    case tok_def:
      HandleDefinition();
      break;
    case tok_extern:
      HandleExtern();
      break;
    default:
      HandleTopLevelExpression();
      break;
    }
  }
}

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

#ifdef LLVM_ON_WIN32
#define DLLEXPORT __declspec(dllexport)
#else
#define DLLEXPORT
#endif

/// putchard - putchar, принимает double, возвращает 0.
extern "C" DLLEXPORT double putchard(double X) {
  fputc((char)X, stderr);
  return 0;
}

/// printd - printf, принимает double печатает его как"%f\n", возвращает 0.
extern "C" DLLEXPORT double printd(double X) {
  fprintf(stderr, "%f\n", X);
  return 0;
}

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

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

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

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

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

  InitializeModuleAndPassManager();

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

  return 0;
}

Tags:
Hubs:
+23
Comments 0
Comments Leave a comment

Articles