3. 万花筒：代码生成到 LLVM IR

3.1. 第 3 章 简介

欢迎来到“使用 LLVM 实现语言”教程的第 3 章。本章将向您展示如何将第 2 章中构建的抽象语法树转换为 LLVM IR。这将使您对 LLVM 的工作原理有所了解，并展示其易用性。构建词法分析器和解析器比生成 LLVM IR 代码要复杂得多。 :)

请注意：本章及以后的代码需要 LLVM 3.7 或更高版本。LLVM 3.6 及更早版本无法使用它。另请注意，您需要使用与您的 LLVM 版本匹配的本教程版本：如果您使用的是官方 LLVM 版本，请使用随您的版本一起提供的或在llvm.org 发布页面上的文档版本。

3.2. 代码生成设置

为了生成 LLVM IR，我们需要一些简单的设置来开始。首先，我们在每个 AST 类中定义虚拟代码生成 (codegen) 方法

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

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(TheContext);
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<Value> 的原因。

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

有了这些基础，我们就可以开始讨论如何为每个表达式生成代码了。请注意，这假设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() {
  // Look this variable up in the function.
  Value *V = NamedValues[Name];
  if (!V)
    LogErrorV("Unknown variable name");
  return V;
}

使用 LLVM 对变量的引用也很简单。在万花筒的简单版本中，我们假设变量已经在某个地方发出，并且其值可用。实际上，唯一可能在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");
    // 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");
  }
}

二元运算符开始变得更有意思。这里的基本思想是我们递归地为表达式的左侧发出代码，然后是右侧，然后我们计算二元表达式的结果。在此代码中，我们对操作码执行简单的切换以创建正确的 LLVM 指令。

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

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

LLVM 指令 受严格规则的约束：例如，加法指令的左操作数和右操作数必须具有相同的类型，并且加法的结果类型必须与操作数类型匹配。因为万花筒中的所有值都是双精度数，所以这使得加法、减法和乘法的代码非常简单。

另一方面，LLVM 指定fcmp 指令 始终返回一个“i1”值（一个一位整数）。问题在于万花筒希望该值为 0.0 或 1.0 值。为了获得这些语义，我们将 fcmp 指令与uitofp 指令结合起来。此指令通过将输入视为无符号值将其输入整数转换为浮点值。相反，如果我们使用sitofp 指令，则万花筒“<”运算符将返回 0.0 和 -1.0，具体取决于输入值。

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

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

一旦我们有了要调用的函数，我们就会递归地为要传入的每个参数生成代码，并创建一个 LLVM 调用指令。请注意，LLVM 默认使用本机 C 调用约定，允许这些调用也调用标准库函数（如“sin”和“cos”），而无需任何额外工作。

这结束了我们对万花筒中迄今为止的四个基本表达式的处理。随意添加更多。例如，通过浏览LLVM 语言参考，您会发现一些其他有趣的指令，这些指令非常容易插入到我们的基本框架中。

3.4. 函数代码生成

原型和函数的代码生成必须处理许多细节，这使得它们的代码不如表达式代码生成美观，但使我们能够说明一些要点。首先，让我们讨论原型代码的生成：它们既用于函数体也用于外部函数声明。代码以以下内容开头

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

此代码在几行代码中包含了强大的功能。首先请注意，此函数返回“Function*”而不是“Value*”。因为“原型”实际上谈论的是函数的外部接口（而不是表达式计算的值），所以它在代码生成时返回它对应的 LLVM 函数是有意义的。

对FunctionType::get 的调用创建了应用于给定原型的FunctionType。由于万花筒中的所有函数参数都是双精度数，因此第一行创建了一个“N”个 LLVM 双精度数类型的向量。然后，它使用Functiontype::get 方法创建一个函数类型，该类型将“N”个双精度数作为参数，返回一个双精度数作为结果，并且不是可变参数（false 参数表示这一点）。请注意，LLVM 中的类型就像常量一样是唯一的，因此您不会“新建”类型，而是“获取”类型。

上面最后一行实际上创建了与原型对应的 IR 函数。这指示了要使用的类型、链接和名称，以及要插入哪个模块。“外部链接”表示该函数可以在当前模块之外定义和/或可被模块外部的函数调用。传递的名称是用户指定的名称：由于指定了“TheModule”，因此此名称将在“TheModule”的符号表中注册。

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

return F;

最后，我们根据原型中给出的名称设置每个函数参数的名称。此步骤并非严格必要，但保持名称一致可以使 IR 更具可读性，并允许后续代码直接引用参数的名称，而不是必须在原型 AST 中查找它们。

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

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;

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

对于函数定义，我们首先在 TheModule 的符号表中搜索此函数的现有版本，以防它已经使用 ‘extern’ 语句创建。如果 Module::getFunction 返回 null，则表示不存在以前的版本，因此我们将根据原型生成一个。在任何一种情况下，我们都希望在开始之前断言该函数为空（即还没有函数体）。

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

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

接下来，我们将函数参数添加到 NamedValues 映射中（首先将其清空），以便它们可供 VariableExprAST 节点访问。

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

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

  return TheFunction;
}

设置插入点并填充 NamedValues 映射后，我们调用函数根表达式的 codegen() 方法。如果没有发生错误，这将发出代码以将表达式计算到入口块中并返回计算出的值。假设没有错误，然后我们创建一个 LLVM ret 指令，它完成了函数。构建函数后，我们调用 LLVM 提供的 verifyFunction。此函数对生成的代码执行各种一致性检查，以确定我们的编译器是否一切正常。使用此功能非常重要：它可以捕获许多错误。函数完成并验证后，我们将其返回。

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

这里唯一剩下的部分是错误情况的处理。为简单起见，我们通过使用 eraseFromParent 方法简单地删除我们生成的函数来处理此问题。这允许用户重新定义他们之前输入错误的函数：如果我们不删除它，它将保留在符号表中，并带有函数体，从而阻止将来重新定义。

但是，此代码确实存在一个错误：如果 FunctionAST::codegen() 方法找到现有的 IR 函数，则它不会根据定义自己的原型验证其签名。这意味着较早的 ‘extern’ 声明将优先于函数定义的签名，这可能导致代码生成失败，例如，如果函数参数的命名不同。有多种方法可以修复此错误，看看你能想出什么！这是一个测试用例

extern foo(a);     # ok, defines foo.
def foo(b) b;      # Error: Unknown variable name. (decl using 'a' takes precedence).

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 上发送 CTRL+D 或在 Windows 上发送 CTRL+Z 和 ENTER 来发送 EOF）时，它会转储生成的整个模块的 IR。在这里，您可以看到包含所有函数相互引用的全局图。

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

3.6. 完整代码清单

这是我们正在运行的示例的完整代码清单，并增强了 LLVM 代码生成器。因为这使用了 LLVM 库，所以我们需要将它们链接进来。为此，我们使用llvm-config工具来告知我们的 makefile/命令行要使用哪些选项

# Compile
clang++ -g -O3 toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core` -o toy
# Run
./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;
}

下一步：添加 JIT 和优化器支持