LLVM学习入门(3):生成 LLVM 中间代码 IR

本文是使用 LLVM 开发新语言 Kaleidoscope 教程第三篇文章，本文承接上篇 LLVM学习入门(2):实现解析器 Parser 和语法树 AST，主要实现 AST 转化为 LLVM IR 的功能。同时，本篇还会告诉我们一些 LLVM 如何工作的知识，并演示它的易用性。注意：本章及更高版本中的代码要求LLVM 3.7或更高版本。

3.1 Code Generation Setup 中间代码生成配置

为了生成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();
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

codegen()方法表示要为 AST 节点生成中间代码 IR 及其依赖的所有东西，并且它们都返回 LLVM Value 对象。“Value”是用于表示 LLVM 中的 “静态单一赋值（SSA）寄存器”或“SSA value”的类。SSA 值最明显的方面是，它们的值是在相关指令执行时计算的，并且直到重新执行前，它都不会获得新值。简而言之，就是没办法改变 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;
}
1
2
3
4
5
6
7
8
9

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

该 Builder 对象是一个帮助程序对象，可轻松生成 LLVM 指令。IRBuilder 类模板的实例跟踪要插入指令的当前位置，并具有创建新指令的方法。

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

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

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

3.2 Expression Code Generation 表达式代码生成

表达式节点生成 LLVM IR 代码非常简单：

首先，对于数字表达式：

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

在 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;
}
1
2
3
4
5
6
7

使用 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");
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这里的基本思想是我们递归地为表达式的左侧生成代码，然后再为右侧生成代码，然后计算二进制表达式结果。在此代码中，我们对操作码进行了简单的切换以创建正确的 LLVM 指令。

在上面的示例中， LLVM 构建器类开始显示其值。IRBuilder 知道在何处插入新创建的指令，我们要做的就是指定要创建的指令，例如：使用 CreateFAdd。还有就是要使用操作数（L 和 R），并可以选择为生成的指令提供名称，例如：addtemp。

LLVM 的一个好处是名称只是一个提示。例如，如果上面的代码发出多个 addtemp 变量，则 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");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

一旦有了要调用的函数，就可以递归地对要传递的每个参数进行代码生成，并创建 LLVM调用指令 。

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

3.3 Function Code Generation 函数代码生成

原型和函数的代码生成必须处理许多细节，接下来举例一些重点。

首先，我们看原型的代码生成：它们既用于函数体，又用于外部函数声明，该段代码以以下内容开头：

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);
  // 创建一个IR函数，指明使用的类型，链接和名称，以及要插入的模块
  Function *F =
    Function::Create(FT, Function::ExternalLinkage, Name, TheModule.get());
1
2
3
4
5
6
7
8
9
10

此代码将大量功能打包成几行，此函数返回的是 Function * ,而不是 Value * 。因为 ‘’“prototype” 实际上是在谈论函数的外部接口（而不是表达式计算的值），所以有意义的是，它返回的是代码生成是对应的 LLVM 函数。

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

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

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

return F;
1
2
3
4
5
6

最后，我们根据 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());
	// 如果为 NULL，则不存在以前的版本，从 Prototype 中返回一个
  if (!TheFunction)
    TheFunction = Proto->codegen();

  if (!TheFunction)
    return nullptr;

  if (!TheFunction->empty())
    return (Function*)LogErrorV("Function cannot be redefined.");
1
2
3
4
5
6
7
8
9
10
11
12
13

对于函数定义，我们首先在 TheModule 的符号表中搜索该函数的现有版本（如果已经使用 extern 语句创建了该版本）。如果 TheModule->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;
1
2
3
4
5
6
7
8

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

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

// 将表达式计算到输入块中，并返回计算出的值
if (Value *RetVal = Body->codegen()) {
  // Finish off the function.
  // 创建 LLVM ret instruction
  Builder.CreateRet(RetVal);

  // Validate the generated code, checking for consistency.
  // 对生成的代码一致性进行检查，捕获很多 error
  verifyFunction(*TheFunction);

  return TheFunction;
}
1
2
3
4
5
6
7
8
9
10
11
12

设置插入点并填充 NamedValues 映射后，我们将调用该 codegen() 方法作为函数的根表达式。如果没有错误发生，它将发出代码以将表达式计算到输入快中，并返回计算出的值。假设没有错误，我们然后创建

LLVM ret instruction ,以完成该功能。构建函数后，我们将调用 LLVM 提供的 verifyFunction ,该函数对生成的代码进行各种一致性检查，以确定我们编译器是否正确执行所有操作。使用 verifyFunction 很重要：它可以捕获很多 error 。函数完成并验证后，我们将其返回。

  // Error reading body, remove function.
  // 错误处理，直接删掉函数
  TheFunction->eraseFromParent();
  return nullptr;
}
1
2
3
4
5

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

此段代码存在一个漏洞：如果该 FunctionAST::codegen() 方法找到了现有的 IR 函数，则不会根据自己定义的原型来验证 signature。这意味着较早的 extern 声明将优先于函数定义的 signature （A function’s signature includes the function’s name and the number, order and type of its formal parameters. ），这可能导致代码生成失败。例如，如果函数参数的命名不同。有很多方法解决这个 bug，看你怎么解决。下面这个例子：

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

3.4 Driver Changes and Closing Thoughts 驱动程序和思路总结

就目前而言， LLVM 的代码生成并不能真正为我们带来很多好处，只是我们可以查看漂亮的 IR 调用。示例代码将对代码生成的调用插入 HandleDefinition ,HandleExtern 等函数中，然后转储 LLVM IR。这为查看 LLVM IR 的简单功能提供了一种好的方法。例如：

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

注意：解析器如何将 top-level expression 转换为 anonymous functions。这个将会在LLVM学习入门(4):添加 JIT 和 Optimizer 支持 中的 4.4 Adding a JIT Compiler 中介绍。

还有注意，该代码是按字面意思转录的，除了 IRBuilder 进行的简单常量折叠外，没有执行任何优化。我们将在下一篇LLVM学习入门(4):添加 JIT 和 Optimizer 支持 添加优化。

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
}
1
2
3
4
5
6
7
8
9
10
11
12

这显示了一些简单的算法。注意，它与我们用来创建指令的 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
}
1
2
3
4
5
6
7
8
9

这显示了一些函数调用，注意，如果调用此函数，将花费很长时间执行。后续，我们将添加条件控制流来让递归真正有用。

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
}
1
2
3
4
5
6
7
8
9
10
11

这显示了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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

退出当前演示时，它将退出生成的整个模块的 IR。在这里，我们可以看到具有互相参照的所有功能的全景图。

接下来，我们将开启LLVM学习入门(4):添加 JIT 和 Optimizer 支持。