3. Kaleidoscope：代码生成到 LLVM IR

• 第3章介绍

• 代码生成设置

• 表达式代码生成

• 函数代码生成

• 驱动更改和结束语

• 完整代码列表

3.1. 第3章介绍

欢迎来到“用 LLVM 实现语言”教程的第3章。本章将展示如何将第2章构建的抽象语法树转换成 LLVM IR。这将让你对 LLVM 的工作方式有所了解，并展示使用 LLVM 是多么简单。构建词法分析器和解析器比生成 LLVM IR 代码要复杂得多。

请注意：本章及后续章节的代码需要 LLVM 3.7 或更高版本。LLVM 3.6 及更早版本将无法使用。同样请注意，你需要使用与你的 LLVM 版本相匹配的教程文档：如果你使用的是官方 LLVM 发布版，请使用随你的发布版或在 llvm.org 发布页面上包含的文档版本。

3.2. 代码生成设置

为了生成 LLVM IR，我们希望有一个简单的设置来开始。首先，我们在每个 AST 类中定义虚拟的代码生成（codegen）方法：

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

codegen() 方法表示为该 AST 节点及其所有依赖项生成 IR，并返回一个 LLVM Value 对象。“Value”是 LLVM 中用于表示“静态单赋值（SSA）寄存器”或“SSA 值”的类。SSA 值最显著的特点是它们的值在相关指令执行时计算，并且在指令重新执行之前（如果重新执行）不会获得新值。换句话说，没有办法“改变”一个 SSA 值。有关更多信息，请阅读有关静态单赋值的文章 - 一旦你理解了它们，这些概念是非常自然的。

注意，除了向 ExprAST 类层次结构添加虚拟方法外，使用访问者模式或其他方式来建模也是有意义的。再次强调，本教程不会深入讨论良好的软件工程实践：对于我们的目的而言，添加一个虚拟方法是最简单的。

我们想要的第二件事是一个类似于我们用于解析器的“LogError”方法，它将用于报告代码生成期间发现的错误（例如，使用未声明的参数）：

static std::unique_ptr<LLVMContext> TheContext;
static std::unique_ptr<IRBuilder<>> Builder;
static std::unique_ptr<Module> TheModule;
static std::map<std::string, Value *> NamedValues;

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

这些静态变量将在代码生成期间使用。TheContext 是一个不透明的对象，它拥有许多核心 LLVM 数据结构，例如类型和常量值表。我们不需要详细了解它，我们只需要一个实例来传递给需要它的 API。

Builder 对象是一个辅助对象，它使得生成 LLVM 指令变得容易。IRBuilder 类模板的实例会跟踪当前插入指令的位置，并具有创建新指令的方法。

TheModule 是一个 LLVM 结构，包含函数和全局变量。在许多方面，它是 LLVM IR 用于包含代码的顶级结构。它将拥有我们生成的所有 IR 的内存，这就是为什么 codegen() 方法返回一个原始的 Value*，而不是 unique_ptr 的原因。

NamedValues 映射表跟踪当前作用域中定义的哪些值以及它们的 LLVM 表示是什么。（换句话说，它是代码的符号表）。在 Kaleidoscope 的这种形式中，唯一可以引用的是函数参数。因此，在为其函数体生成代码时，函数参数将在该映射表中。

有了这些基础知识，我们可以开始讨论如何为每个表达式生成代码。请注意，这假设 Builder 已经被设置为生成代码到某个地方。现在，我们将假设这已经完成，我们只会使用它来发出代码。

3.3. 表达式代码生成

为表达式节点生成 LLVM 代码是非常直接的：不到 45 行注释代码涵盖了所有四个表达式节点。首先，我们处理数字字面量：

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

在 LLVM IR 中，数字常量由 ConstantFP 类表示，该类在内部使用 APFloat 持有数值（APFloat 能够持有任意精度的浮点常量）。这段代码基本上只是创建并返回一个 ConstantFP。请注意，在 LLVM IR 中，常量都是唯一的，并且共享的。因此，API 使用“foo::get(…)”习惯用法而不是“new foo(…)”或“foo::Create(…)”。

Value *VariableExprAST::codegen() {
  // 在函数中查找此变量。
  Value *V = NamedValues[Name];
  if (!V)
    LogErrorV("Unknown variable name");
  return V;
}

使用 LLVM 引用变量也非常简单。在 Kaleidoscope 的简单版本中，我们假设变量已经在某个地方发出，其值是可用的。实际上，NamedValues 映射表中唯一可以有的值是函数参数。这段代码简单地检查指定名称是否在映射表中（如果没有，就是引用了一个未知变量）并返回它的值。在后续章节中，我们将添加对循环计数器变量和局部变量的支持。

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

  switch (Op) {
  case '+':
    return Builder->CreateFAdd(L, R, "addtmp");
  case '-':
    return Builder->CreateFSub(L, R, "subtmp");
  case '*':
    return Builder->CreateFMul(L, R, "multmp");
  case '<':
    L = Builder->CreateFCmpULT(L, R, "cmptmp");
    // 将布尔值 0/1 转换为双精度 0.0 或 1.0
    return Builder->CreateUIToFP(L, Type::getDoubleTy(*TheContext), "booltmp");
  default:
    return LogErrorV("invalid binary operator");
  }
}

二元运算符开始变得更有趣。这里的基本思想是递归地发出表达式左侧的代码，然后是右侧的代码，然后计算二元表达式的结果。在这段代码中，我们对操作码做一个简单的 switch 来创建正确的 LLVM 指令。

在上面的例子中，LLVM 构建器类开始显示它的价值。IRBuilder 知道在哪里插入新创建的指令，你只需要指定要创建的指令是什么（例如，CreateFAdd），使用哪些操作数（这里使用 L 和 R），并为生成的指令提供一个可选的名称。

关于 LLVM 的一个好处是，名称只是一个提示。例如，如果上面的代码多次发出“addtmp”变量，LLVM 将自动为每一个提供一个递增的唯一数字后缀。指令的局部值名称完全是可选的，但它使阅读 IR 转储变得容易得多。

LLVM 指令受到严格规则的约束：例如，add 指令的左右操作数必须具有相同的类型，add 的结果类型必须与操作数类型匹配。由于 Kaleidoscope 中的所有值都是双精度的，这使得 add、sub 和 mul 的代码非常简单。

另一方面，LLVM 规定 fcmp 指令总是返回一个‘i1’值（一个位整数）。问题是 Kaleidoscope 希望值是 0.0 或 1.0。为了获得这些语义，我们将 fcmp 指令与 uitofp 指令结合起来。这个指令通过将输入视为无符号值，将其输入整数转换为浮点值。相比之下，如果我们使用 sitofp 指令，Kaleidoscope 的‘<’操作符将根据输入值返回 0.0 和 -1.0。

Value *CallExprAST::codegen() {
  // 在全局模块表中查找名称。
  Function *CalleeF = TheModule->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");
}

使用 LLVM 生成函数调用代码是相当直接的。上面的代码最初在 LLVM 模块的符号表中进行函数名称查找。回想一下，LLVM 模块是包含我们正在 JIT 的函数的容器。通过为每个函数提供与用户指定的相同名称，我们可以使用 LLVM 符号表为我们解析函数名称。

一旦我们有了要调用的函数，我们就递归地为要传递的每个参数生成代码，并创建一个 LLVM call 指令。请注意，默认情况下 LLVM 使用本地 C 调用约定，这允许这些调用也调用标准库函数，如“sin”和“cos”，无需额外努力。

3.4. 函数代码生成

原型和函数的代码生成必须处理许多细节，这使得它们的代码不如表达式代码生成那么美观，但它允许我们说明一些重要的观点。首先，让我们谈谈原型的代码生成：它们既用于函数体，也用于外部函数声明。代码从以下开始：

Function *PrototypeAST::codegen() {
  // 制作函数类型：double(double,double)等。
  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());

这段代码包含了大量的功能。首先，这个函数返回一个“Function”而不是一个“Value”。因为“原型”实际上讨论的是函数的外部接口（而不是由表达式计算的值），所以它在代码生成时返回对应的 LLVM 函数是有意义的。

对 FunctionType::get 的调用创建了给定原型应该使用的 FunctionType。由于 Kaleidoscope 中的所有函数参数都是 double 类型，第一行创建了一个“N”个 LLVM double 类型的向量。然后使用 FunctionType::get 方法创建一个接受“N”个 double 作为参数，返回一个 double 结果的函数类型，并且不是变长参数（false 参数表示这一点）。请注意，LLVM 中的类型就像常量一样是唯一的，所以你不会“new”一个类型，你会“get”它。

上面的最后一行实际上创建了对应于原型的 IR 函数。这表明了要使用的类型、链接方式和名称，以及要插入哪个模块。“external linkage”意味着该函数可能在当前模块之外定义，并且/或者它可以被模块之外的函数调用。传入的名称是用户指定的名称：由于指定了“TheModule”，这个名称在“TheModule”的符号表中注册。

// 为所有参数设置名称。
unsigned Idx = 0;
for (auto &Arg : F->args())
  Arg.setName(Args[Idx++]);

return F;

最后，我们根据原型中给出的名称为每个函数参数设置名称。这一步不是绝对必要的，但保持名称一致使得 IR 更易读，并且允许后续代码直接引用参数的名称，而不是在原型 AST 中查找它们。

此时，我们有一个没有主体的函数原型。这就是 LLVM IR 表示函数声明的方式。对于 Kaleidoscope 中的 extern 语句，我们需要走到这一步。对于函数定义，我们需要代码生成并附加一个函数体。

Function *FunctionAST::codegen() {
    // 首先，检查之前是否有使用 'extern' 声明的现有函数。
  Function *TheFunction = TheModule->getFunction(Proto->getName());

  if (!TheFunction)
    TheFunction = Proto->codegen();

  if (!TheFunction)
    return nullptr;

  if (!TheFunction->empty())
    return (Function*)LogErrorV("Function cannot be redefined.");

对于函数定义，我们首先在 TheModule 的符号表中搜索这个函数的现有版本，以防已经使用 ‘extern’ 语句创建过。如果 Module::getFunction 返回 null，则表示之前没有版本存在，所以我们将从原型生成一个。无论哪种情况，我们都希望在开始之前断言函数是空的（即，还没有主体）。

// 创建一个新的基本块以开始插入。
BasicBlock *BB = BasicBlock::Create(*TheContext, "entry", TheFunction);
Builder->SetInsertPoint(BB);

// 在 NamedValues 映射中记录函数参数。
NamedValues.clear();
for (auto &Arg : TheFunction->args())
  NamedValues[std::string(Arg.getName())] = &Arg;

现在我们到了设置 Builder 的地方。第一行创建了一个新的基本块（命名为 “entry”），它被插入到 TheFunction 中。第二行然后告诉构建器新指令应该插入到新基本块的末尾。LLVM 中的基本块是定义控制流图的重要部分。由于我们没有任何控制流，我们的功能目前将只包含一个块。我们将在第5章修复这个问题。

接下来，我们在 NamedValues 映射中添加函数参数（首先清除它），以便它们可以被 VariableExprAST 节点访问。

if (Value *RetVal = Body->codegen()) {
  // 完成函数。
  Builder->CreateRet(RetVal);

  // 验证生成的代码，检查一致性。
  verifyFunction(*TheFunction);

  return TheFunction;
}

一旦插入点设置好并且 NamedValues 映射填充好，我们调用函数根表达式的 codegen() 方法。如果没有错误发生，这将发出代码以计算表达式到入口块并返回计算的值。假设没有错误，我们然后创建一个 LLVM ret 指令，这完成了函数。一旦函数构建完成并通过验证，我们返回它。

  // 读取主体时出错，删除函数。
  TheFunction->eraseFromParent();
  return nullptr;
}

这里剩下的部分是错误处理。为了简单起见，我们通过使用 eraseFromParent 方法删除我们生成的函数来处理这个问题。这允许用户重新定义他们之前错误输入的函数：如果我们不删除它，它将以一个主体存在于符号表中，阻止未来的重新定义。

这段代码确实有一个错误：如果 FunctionAST::codegen() 方法找到了一个现有的 IR 函数，它不会验证其签名与定义自己的原型是否匹配。这意味着早期的 ‘extern’ 声明将优先于函数定义的签名，这可能导致 codegen 失败，例如，如果函数参数的名称不同。有多种方法可以修复这个错误，看看你能想到什么！这里有一个测试用例：

extern foo(a);     # 好的，定义了 foo。
def foo(b) b;      # 错误：未知变量名称。（使用 'a' 的声明优先）。

3.5. 驱动更改和结束语

目前，代码生成到 LLVM 并没有给我们带来太多好处，除了我们可以查看漂亮的 IR 调用。示例代码将 codegen 调用插入到 “HandleDefinition”、“HandleExtern” 等函数中，然后转储出 LLVM IR。这为查看简单函数的 LLVM IR 提供了一个很好的方式。例如：

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

注意，解析器如何将顶层表达式转换为我们的匿名函数。当我们在下一章添加 JIT 支持时，这将非常有用。同样请注意，代码非常直接地转录，除了 IRBuilder 完成的简单常量折叠外，没有执行任何优化。我们将在下一章显式添加优化。

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

这显示了一些简单的算术。注意与我们用来创建指令的 LLVM 构建器调用的惊人相似性。

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

这显示了一些函数调用。请注意，如果你调用这个函数，它将需要很长时间才能执行。将来我们将添加条件控制流，使递归真正有用。

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

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

这显示了对 libm “cos”函数的 extern，以及对其的调用。

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

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

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

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

declare double @cos(double)

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

当你退出当前演示（通过在 Linux 上发送 EOF，或在 Windows 上发送 CTRL+Z 和 ENTER），它会转储出整个模块生成的 IR。在这里，你可以看到所有函数相互引用的大局。

这结束了 Kaleidoscope 教程的第三章。接下来，我们将描述如何添加 JIT 代码生成和优化器支持，以便我们实际上可以开始运行代码！

3.6. 完整代码列表

以下是我们运行示例的完整代码列表，增强了 LLVM 代码生成器。因为这使用了 LLVM 库，我们需要将它们链接进来。为此，我们使用 llvm-config 工具来告知我们的 makefile/command line 使用哪些选项：

bash
# 编译
clang++ -g -O3 toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core` -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/IRBuilder.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Verifier.h"
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <memory>
#include <string>
#include <vector>

using namespace llvm;

//===----------------------------------------------------------------------===//
// Lexer
//===----------------------------------------------------------------------===//

// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
// of these for known things.
enum Token {
  tok_eof = -1,

  // commands
  tok_def = -2,
  tok_extern = -3,

  // primary
  tok_identifier = -4,
  tok_number = -5
};

static std::string IdentifierStr; // Filled in if tok_identifier
static double NumVal;             // Filled in if tok_number

/// gettok - Return the next token from standard input.
static int gettok() {
  static int LastChar = ' ';

  // Skip any whitespace.
  while (isspace(LastChar))
    LastChar = getchar();

  if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
    IdentifierStr = LastChar;
    while (isalnum((LastChar = getchar())))
      IdentifierStr += LastChar;

    if (IdentifierStr == "def")
      return tok_def;
    if (IdentifierStr == "extern")
      return tok_extern;
    return tok_identifier;
  }

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

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

  if (LastChar == '#') {
    // Comment until end of line.
    do
      LastChar = getchar();
    while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');

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

  // Check for end of file.  Don't eat the EOF.
  if (LastChar == EOF)
    return tok_eof;

  // Otherwise, just return the character as its ascii value.
  int ThisChar = LastChar;
  LastChar = getchar();
  return ThisChar;
}

//===----------------------------------------------------------------------===//
// Abstract Syntax Tree (aka Parse Tree)
//===----------------------------------------------------------------------===//

namespace {

/// ExprAST - Base class for all expression nodes.
class ExprAST {
public:
  virtual ~ExprAST() = default;

  virtual Value *codegen() = 0;
};

/// NumberExprAST - Expression class for numeric literals like "1.0".
class NumberExprAST : public ExprAST {
  double Val;

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

  Value *codegen() override;
};

/// VariableExprAST - Expression class for referencing a variable, like "a".
class VariableExprAST : public ExprAST {
  std::string Name;

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

  Value *codegen() override;
};

/// BinaryExprAST - Expression class for a binary operator.
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 - Expression class for function calls.
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;
};

/// PrototypeAST - This class represents the "prototype" for a function,
/// which captures its name, and its argument names (thus implicitly the number
/// of arguments the function takes).
class PrototypeAST {
  std::string Name;
  std::vector<std::string> Args;

public:
  PrototypeAST(const std::string &Name, std::vector<std::string> Args)
      : Name(Name), Args(std::move(Args)) {}

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

/// FunctionAST - This class represents a function definition itself.
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();
};

} // end anonymous namespace

//===----------------------------------------------------------------------===//
// Parser
//===----------------------------------------------------------------------===//

/// CurTok/getNextToken - Provide a simple token buffer.  CurTok is the current
/// token the parser is looking at.  getNextToken reads another token from the
/// lexer and updates CurTok with its results.
static int CurTok;
static int getNextToken() { return CurTok = gettok(); }

/// BinopPrecedence - This holds the precedence for each binary operator that is
/// defined.
static std::map<char, int> BinopPrecedence;

/// GetTokPrecedence - Get the precedence of the pending binary operator token.
static int GetTokPrecedence() {
  if (!isascii(CurTok))
    return -1;

  // Make sure it's a declared binop.
  int TokPrec = BinopPrecedence[CurTok];
  if (TokPrec <= 0)
    return -1;
  return TokPrec;
}

/// LogError* - These are little helper functions for error handling.
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 = std::make_unique<NumberExprAST>(NumVal);
  getNextToken(); // consume the number
  return std::move(Result);
}

/// parenexpr ::= '(' expression ')'
static std::unique_ptr<ExprAST> ParseParenExpr() {
  getNextToken(); // eat (.
  auto V = ParseExpression();
  if (!V)
    return nullptr;

  if (CurTok != ')')
    return LogError("expected ')'");
  getNextToken(); // eat ).
  return V;
}

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

  getNextToken(); // eat identifier.

  if (CurTok != '(') // Simple variable ref.
    return std::make_unique<VariableExprAST>(IdName);

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

  // Eat the ')'.
  getNextToken();

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

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

/// binoprhs
///   ::= ('+' primary)*
static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
                                              std::unique_ptr<ExprAST> LHS) {
  // If this is a binop, find its precedence.
  while (true) {
    int TokPrec = GetTokPrecedence();

    // If this is a binop that binds at least as tightly as the current binop,
    // consume it, otherwise we are done.
    if (TokPrec < ExprPrec)
      return LHS;

    // Okay, we know this is a binop.
    int BinOp = CurTok;
    getNextToken(); // eat binop

    // Parse the primary expression after the binary operator.
    auto RHS = ParsePrimary();
    if (!RHS)
      return nullptr;

    // If BinOp binds less tightly with RHS than the operator after RHS, let
    // the pending operator take RHS as its LHS.
    int NextPrec = GetTokPrecedence();
    if (TokPrec < NextPrec) {
      RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS));
      if (!RHS)
        return nullptr;
    }

    // Merge LHS/RHS.
    LHS =
        std::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS));
  }
}

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

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

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

  std::string FnName = IdentifierStr;
  getNextToken();

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

  // success.
  getNextToken(); // eat ')'.

  return std::make_unique<PrototypeAST>(FnName, std::move(ArgNames));
}

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

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

/// toplevelexpr ::= expression
static std::unique_ptr<FunctionAST> ParseTopLevelExpr() {
  if (auto E = ParseExpression()) {
    // Make an anonymous proto.
    auto Proto = std::make_unique<PrototypeAST>("__anon_expr",
                                                 std::vector<std::string>());
    return std::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();
}

//===----------------------------------------------------------------------===//
// Code Generation
//===----------------------------------------------------------------------===//

static std::unique_ptr<LLVMContext> TheContext;
static std::unique_ptr<Module> TheModule;
static std::unique_ptr<IRBuilder<>> Builder;
static std::map<std::string, Value *> NamedValues;

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

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

Value *VariableExprAST::codegen() {
  // Look this variable up in the function.
  Value *V = NamedValues[Name];
  if (!V)
    return LogErrorV("Unknown variable name");
  return V;
}

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

  switch (Op) {
  case '+':
    return Builder->CreateFAdd(L, R, "addtmp");
  case '-':
    return Builder->CreateFSub(L, R, "subtmp");
  case '*':
    return Builder->CreateFMul(L, R, "multmp");
  case '<':
    L = Builder->CreateFCmpULT(L, R, "cmptmp");
    // Convert bool 0/1 to double 0.0 or 1.0
    return Builder->CreateUIToFP(L, Type::getDoubleTy(*TheContext), "booltmp");
  default:
    return LogErrorV("invalid binary operator");
  }
}

Value *CallExprAST::codegen() {
  // Look up the name in the global module table.
  Function *CalleeF = TheModule->getFunction(Callee);
  if (!CalleeF)
    return LogErrorV("Unknown function referenced");

  // If argument mismatch error.
  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");
}

Function *PrototypeAST::codegen() {
  // Make the function type:  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());

  // Set names for all arguments.
  unsigned Idx = 0;
  for (auto &Arg : F->args())
    Arg.setName(Args[Idx++]);

  return F;
}

Function *FunctionAST::codegen() {
  // First, check for an existing function from a previous 'extern' declaration.
  Function *TheFunction = TheModule->getFunction(Proto->getName());

  if (!TheFunction)
    TheFunction = Proto->codegen();

  if (!TheFunction)
    return nullptr;

  // Create a new basic block to start insertion into.
  BasicBlock *BB = BasicBlock::Create(*TheContext, "entry", TheFunction);
  Builder->SetInsertPoint(BB);

  // Record the function arguments in the NamedValues map.
  NamedValues.clear();
  for (auto &Arg : TheFunction->args())
    NamedValues[std::string(Arg.getName())] = &Arg;

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

    // Validate the generated code, checking for consistency.
    verifyFunction(*TheFunction);

    return TheFunction;
  }

  // Error reading body, remove function.
  TheFunction->eraseFromParent();
  return nullptr;
}

//===----------------------------------------------------------------------===//
// Top-Level parsing and JIT Driver
//===----------------------------------------------------------------------===//

static void InitializeModule() {
  // Open a new context and module.
  TheContext = std::make_unique<LLVMContext>();
  TheModule = std::make_unique<Module>("my cool jit", *TheContext);

  // Create a new builder for the module.
  Builder = std::make_unique<IRBuilder<>>(*TheContext);
}

static void HandleDefinition() {
  if (auto FnAST = ParseDefinition()) {
    if (auto *FnIR = FnAST->codegen()) {
      fprintf(stderr, "Read function definition:");
      FnIR->print(errs());
      fprintf(stderr, "\n");
    }
  } else {
    // Skip token for error recovery.
    getNextToken();
  }
}

static void HandleExtern() {
  if (auto ProtoAST = ParseExtern()) {
    if (auto *FnIR = ProtoAST->codegen()) {
      fprintf(stderr, "Read extern: ");
      FnIR->print(errs());
      fprintf(stderr, "\n");
    }
  } else {
    // Skip token for error recovery.
    getNextToken();
  }
}

static void HandleTopLevelExpression() {
  // Evaluate a top-level expression into an anonymous function.
  if (auto FnAST = ParseTopLevelExpr()) {
    if (auto *FnIR = FnAST->codegen()) {
      fprintf(stderr, "Read top-level expression:");
      FnIR->print(errs());
      fprintf(stderr, "\n");

      // Remove the anonymous expression.
      FnIR->eraseFromParent();
    }
  } else {
    // Skip token for error recovery.
    getNextToken();
  }
}

/// top ::= definition | external | expression | ';'
static void MainLoop() {
  while (true) {
    fprintf(stderr, "ready> ");
    switch (CurTok) {
    case tok_eof:
      return;
    case ';': // ignore top-level semicolons.
      getNextToken();
      break;
    case tok_def:
      HandleDefinition();
      break;
    case tok_extern:
      HandleExtern();
      break;
    default:
      HandleTopLevelExpression();
      break;
    }
  }
}

//===----------------------------------------------------------------------===//
// Main driver code.
//===----------------------------------------------------------------------===//

int main() {
  // Install standard binary operators.
  // 1 is lowest precedence.
  BinopPrecedence['<'] = 10;
  BinopPrecedence['+'] = 20;
  BinopPrecedence['-'] = 20;
  BinopPrecedence['*'] = 40; // highest.

  // Prime the first token.
  fprintf(stderr, "ready> ");
  getNextToken();

  // Make the module, which holds all the code.
  InitializeModule();

  // Run the main "interpreter loop" now.
  MainLoop();

  // Print out all of the generated code.
  TheModule->print(errs(), nullptr);

  return 0;
}