Kaleidoscope 系列第三章：生成 LLVM 中间代码 IR

原文链接:Kaleidoscope 系列第三章：生成 LLVM 中间代码 IR

本文是使用 LLVM 开发新语言 Kaleidoscope 教程系列第三章，主要实现将 AST 转化为 LLVM IR 的功能。

第三章简介

欢迎来到“使用 LLVM 开发新语言 Kaleidoscope 教程”教程的第三章。本章介绍如何将第二章中构建的抽象语法树转换为 LLVM IR。本章将告诉我们一些有关 LLVM 如何工作的知识，并演示它的易用性。构建词法分析器和解析器要比生成 LLVM IR 代码多得多。

请注意：本章及更高版本中的代码要求 LLVM 3.7 或更高版本。LLVM 3.6 及更低版本将无法使用。还要注意，我们需要使用与您的 LLVM 版本匹配的本教程版本：如果你使用的是官方 LLVM 版本，请使用你的版本随附的文档版本或 llvm.org 版本页面上的文档版本。

中间代码生成配置

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

/// ExprAST - Base class for all expression nodes.
class ExprAST {
public:
  virtual ~ExprAST() {}
  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) {}
  virtual Value *codegen();
};
...

codegen() 方法表示要为该 AST 节点生成中间代码 IR 及其依赖的所有东西，并且它们都返回 LLVM Value 对象。“Value”是用于表示 LLVM 中的“静态单一赋值（SSA）寄存器”或“ SSA value”的类。SSA 值最明显的方面是，它们的值是在相关指令执行时计算的，并且直到（如果有）指令重新执行前，它都不会获得新值。换句话说，没有办法“change” SSA 值。有关更多信息，请阅读“静态单一赋值”。一旦掌握了这些概念，理解它们就会非常自然。

请注意，与其将虚拟方法添加到 ExprAST 类层次结构中，还可以使用 访问者模式或其他方式对此建模。再次说明，本教程将不讨论良好的软件工程实践：就我们的目的而言，添加虚拟方法最简单。

我们要做的第二件事是像用于解析器那样的“ LogError”方法，该方法将用于报告在代码生成过程中发现的错误（例如，使用未声明的参数）：

static LLVMContext TheContext;
static 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 的原因。

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

有了这些基础知识之后，我们就可以开始讨论如何为每个表达式生成代码了。请注意，这假设 Builder 已将设置为将代码生成的配置。现在，我们假设这已经完成，并且仅使用它来生成 IR 代码。

表达式代码生成

为表达式节点生成 LLVM IR 代码非常简单：对于我们所有四个表达式节点，少于 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，对变量的引用也非常简单。在 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");
    // 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 指令受到严格的规则约束：例如，一条 add 指令的 Left 和 Right 运算符必须具有相同的类型，并且 add 的结果类型必须与操作数类型匹配。因为 Kaleidoscope 中的所有值都是双精度的，所以这使得用于 add，sub 和 mul 的代码非常简单。

另一方面，LLVM 指定 fcmp 指令始终返回 i1 值（一位整数）。问题在于 Kaleidoscope 希望该值为 0.0 或 1.0。为了获得这些语义，我们将 fcmp 指令与 uitofp 指令结合在一起。该指令通过将输入视为无符号值，将其输入整数转换为浮点值。相反，如果我们使用 sitofp 指令，则 Kaleidoscope < 运算符将根据输入值返回 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 模块是包含我们正在 JITing 的功能的容器。通过为每个函数指定与用户指定的名称相同的名称，我们可以使用 LLVM 符号表为我们解析函数名称。

一旦有了要调用的函数，就可以递归地对要传递的每个参数进行代码生成，并创建 LLVM 调用指令。请注意，默认情况下，LLVM 使用本机 C 调用约定，从而使这些调用也可以调用标准库函数（如“ sin”和“ cos”）而无需付出额外的努力。

这总结了我们到目前为止在 Kaleidoscope 中使用的四个基本表达式的处理。我们也可以随意进入并添加更多内容。例如，通过浏览 LLVM 语言手册我们会发现其他一些有趣的指令，这些指令确实很容易插入到我们的基本框架中。

函数代码生成

原型和函数的代码生成必须处理许多细节，这使得它们的代码不如表达式代码生成简单，但可以让我们举例说明一些重点。首先，我们首先看原型的代码生成：它们既用于函数体，又用于外部函数声明。该代码以以下内容开头：

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 * 。因为“prototype”实际上是在谈论函数的外部接口（而不是表达式计算的值），所以有意义的是，它返回的是代码生成时对应的 LLVM 函数。

调用 FunctionType::get create FunctionType 应该用于给定的原型。由于 Kaleidoscope 中的所有函数参数均为 double 类型，因此第一行将创建一个 N 个 LLVM double 类型的向量。然后，它使用该 Functiontype::get 方法创建一个函数类型，该函数类型将 N 个双精度值作为参数，并返回一个双精度值，而不是 vararg（假参数表明了这一点）。请注意，LLVM 中的类型就像常量一样是唯一的，因此我们不必“新建”一个类型，而是直接“获取”它。

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

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

return F;

最后，我们根据 Prototype 中提供的名称设置函数的每个参数的名称。此步骤不是绝对必要的，但是保持名称的一致性可使 IR 更具可读性，并允许后续代码直接引用其名称的参数，而不必在 Prototype AST 中进行查找。

至此，我们有了一个没有主体的函数原型。这就是 LLVM IR 表示函数声明的方式。对于万花筒中的外部陈述，这是我们需要做的。但是对于函数定义，我们需要代码生成并附加一个函数体。

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 ，则不存在以前的版本，因此我们将从 Prototype 中返回一个。无论哪种情况，我们都想在开始之前断言该函数为空（即没有主体）。

// 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[Arg.getName()] = &Arg;

现在，我们开始进行 Builder 设置。第一行创建一个新的 basic block（名为 entry ），将其插入 TheFunction 。然后第二行告诉构建者，新指令应插入到新基本块的末尾。LLVM 中的基本块是定义 Control Flow Graph 的功能的重要组成部分。由于我们没有任何控制流，因此我们的函数此时仅包含一个块。我们将在第五章中解决此问题：)。

接下来，我们将函数参数添加到 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() 方法作为函数的根表达式。如果没有错误发生，它将发出代码以将表达式计算到输入块中，并返回计算出的值。假设没有错误，我们然后创建 LLVMret 指令，以完成该功能。构建函数后，我们将调用 LLVM 提供的 verifyFunction，该函数对生成的代码进行各种一致性检查，以确定我们的编译器是否在正确执行所有操作。使用它很重要：它可以捕获很多错误。函数完成并验证后，我们将其返回。

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

这里剩下的唯一内容是错误情况的处理。为简单起见，我们仅通过删除使用该 eraseFromParent 方法生成的函数来处理此问题。这使用户可以重新定义以前错误输入的函数：如果我们不删除它，该函数将与主体一起存在于符号表中，以防止将来重新定义。

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

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

驱动代码及思路总结

就目前而言，LLVM 的代码生成并不能真正为我们带来很多好处，只是我们可以查看漂亮的 IR 调用。示例代码将对代码生成的调用插入 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”函数的外部，以及对其的调用。

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 和 Optimizer 支持]，以便我们实际上可以开始运行代码！

完整代码清单

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

# Compile
clang++ -g -O3 chapter3-Code-generation-to-LLVM-IR.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core` -o toy
# Run
./toy

以下是代码清单：

chapter3-Code-generation-to-LLVM-IR.cpp

参考: Kaleidoscope: Code generation to LLVM IR