参考

Kaleidoscope: Code generation to LLVM IR

1. 前言

在之前的文章中，已经完成了 AST 的生成，本文将讲述如何把生成的 AST 转换成 LLVM IR（中间表达）。

2. 设置

首先，我们每一个AST 类中定义一个代码生成的虚函数

/// 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()表示为节点极其所有依赖发出（emit）IR，并且返回的都是 LLVM Value 对象。Value 对象最独特的是他的值是在相关指令执行的时候计算的，并且在指令重新执行前，值都不会更新。当然除了用虚函数的方式，还可以用 visitor pattern 等其他模式实现。

首先，和Parser 一样，定义一个 LogError 的函数，同时定义需要试用到的 LLVM 对象。

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

涉及到的主要数据结构如下：

• LLVMContext TheContext：一个非透明的对象，包含了很多核心的 LLVM 数据结构，比如类型和常量值表。我们无需了解它的细节，只需要一个该对象的单例，传入到需要它的 api 中。
• IRBuilder<> Builder(TheContext)：一个helper 对象，以便于生成 LLVM 指令。IRBuilder 实例跟踪了指令插入的位置，提供了生成新指令的方法。
• std::unique_ptr<Module> TheModule： 一个包含函数和全局变量的 LLVM 结构体。在很多方面，他是LLVM IR 用来包含代码的顶层结构。他拥有我们生成的所有 IR的内存，这也是 codegen()方法为什么返回原始的 Value*而不是 unique_ptr<Value>。Module 是存放 JIT 函数的容器。
• std::map<std::string, Value *> NamedValues：跟踪当前范围定义了哪些值，以及他们的 LLVM 表达式什么（换句话说，他是代码的符号表）。在Kaleidoscope中，唯一能引用的就是函数参数。因此，函数参数在生成函数体代码的时候，会存放在这个 map 中。

3. 表达式的代码生成

四个表达节点的实现是很简单的。

3.1. 数字表达式

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

在 LLVM IR 中，数字常量用 ConstantFP 类（内部用APFloat来存放数值，可以表达浮点数据的任意精度）来表示。 LLVM IR 中，每个常量值都是唯一的、共享的。因此API 使用foo::get(…)，而不是new foo(..)或foo::Create(..)。

3.2. 变量表达式

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

在普通版本的Kaleidoscope中，我们假设变量已经产出（emit）且他的值是可获得的。实际中，NamedValues 映射表中唯一可用的值是函数参数。上述代码简单的检查指定的变量名字是否在映射表中，如果不存在，那么引用的是未知变量，如果存在，就返回对应的值。后续的章节，会在符号表中支持loop induction variables 和 local variables。

3.3. 二元表达式

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 Builder 类知道在哪里插入新创建的指令，你需要做的就是指定要创建的指令（比如 CreateFAdd）、要使用的操作数，并且可以为生成的指令指定一个名字（可选的）。
  这个名字仅仅是一个示意，比如说，如果有多个指令使用名字addtmp，LLVM 会自动给每一个名字增加递增、唯一的后缀。

• LLVM 指令是严格限制的，比如说，add 指令的左右操作数必须是相同的类型，add 的结果类型必须和操作数的类型一样。在Kaleidoscope中，因为所有的值都是 double 的，所以代码实现就很简单。

• LLVM定义 fcmp 指定总是范围一个 i1 （一个 bit 位的整型）。问题是根据Kaleidoscope的语义，希望值是0.0或者1.0。为了达到这个语义，使用了 uitofp 指令和 fcmp 指令的结合。uitofp 指令将输入的整型转为浮点型，转换时将输入视作无符号值。相反，如果使用sitofp指令，Kaleidoscope中的<就会根据输入返回0.0或者是-1.0。

3.4. 函数调用表达式

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 Module 中去查找函数名的符号表，之前提到过，LLVM Module 是存放 JIT 函数的容器。通过为每个函数指定与用户指定的名称相同的名称，我们可以使用LLVM符号表为我们解析函数名称。

一旦我们有了要调用的函数，我们递归的生成传入参数的代码，并创建 LLVM call instruction。注意，LLVM 默认使用的是本地 C 调用约定，从而允许这些调用标准库函数（如 sin、cos）而无需其他代价。

如有需要，在 LLVM language reference 可以查阅其他的LLVM指令。

3.5. 函数代码生成

函数体和 prototype 需要处理更多细节，所以比之前的表达式代码生成更麻烦。

3.5.1. prototype

prototype 用于函数体和函数的外部声明。首先看最开始的几行代码如下：

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 实际上是在讨论函数的外部接口，而不是一个表达式计算的值。

FunctionType::get的调用创建了prototype 需要用到的FunctionType。Kaleidoscope 的数据都是 double 类型的，第一行创建了一个长度为 N（等于函数参数个数） 的 LLVM double类型 vector。然后使用Functiontype::get方法创建一个 FunctionType 对象，这个函数对象使用 N 个对象作为传入参数，返回结果是一个 double 而不是vararg（由第三个参数false指明）。注意，LLVM 的 Types和 Constants 一样都是唯一的，所以不会去 new 一个 type，而是 get。

上述代码的最后一行，创建了 prototype 对应的 IR Function。它指明了类型、链接、名字以及要插入到哪个 module。external linkage意味着这个函数可以在当前 module 之外被定义或者被当前 module 之外的函数调用。Name 是用户定义的名字，将会注册到TheModule的符号表中。

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

return F;
}

最后，根据 prototype 里面给出的名字，设置每一个参数的名字。这个步骤不是严格必要的，但是保持名字一直可以让 IR 更易读，也可以让随后的代码可以通过名字直接引用到这些参数，而不用去 prototype 的 ast 中查找。

此时我们就获得了没有函数体的 prototype 。这就是 LLVM IR如何表示函数声明的过程。但是对于函数的定义，我们还需要函数体。

3.5.2. 函数体

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

对于函数定义，首先在Module中去查找这个函数，以防有人已经用extern创建过了。如果不存在，则调用 ProtoType 的 codegen 生成。在任一情况下，我们想在开始前断言函数是空的（没有函数体）。

// 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），插入到Function。第二行高速 Builder新指令应该插入到新创建的basic block末尾。在 LLVM 中，basic block 是函数重要的一个部分，定义了控制流程图(Control Flow Graph)。因为我们没有任何控制流程图，我们的函数只包含了一个 block。在第五章我们将修正这个情况。

然后我们把函数参数添加到 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() 方法。如果没有错误，将产出用于表达式计算的代码到 entry block 中，并且返回计算的结果。假设没有错误，然后创建一个ret instruction，用于完成函数。函数创建完毕之后，我们调用LLVM 提供的verifyFunction函数。这个函数会对生成的代码做各种一致性的检查，确定我们的编译器是否每件事都做得正确。检查是很有必要的，检查完成后就直接返回函数。

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

剩下的内容是错误处理得情况了。为了简化，我们只是通过eraseFromParent方法将函数删除。

目前的实现有个 bug，如果FunctionAST::codegen()发现一个存在的 IR Function，就不会根据定义的原型验证签名。也就是说使用 extern 的函数提前声明比函数定义的签名有更高的优先级，当声明和定义的变量不一样的时候就会出错。例如：

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

4. 结语

目前，LLVM codegen并没有给我们带来很多好处，除了让我们看到漂亮的 IR 调用。

样例代码把codegen的调用插入到HandleDefinition、 HandleExtern 等函数，然后 dump 出对应的 LLVM IR。比如：

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

上面的代码可以看到LLVM 隐式地对 Top-Level 的表达式做了简单的优化，下一章将会介绍如何显示的进行优化。

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
}

以上是 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
}

退出命令行的时候，会把Module 的所有 IR dump 出来。

完整代码清单参见Full Code Listing