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

    • 第3章简介
    • 代码生成设置
    • 表达代码生成
    • 功能代码生成
    • 驱动变动与结束思考
    • 完整的代码清单

    3.2 代码生成设置

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

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

    请注意，不是将虚方法添加到ExprAST类层次结构中，而是使用访问者模式或其他方式对此进行建模也是有意义的。同样，本教程将不再讨论良好的软件工程实践：出于我们的目的，添加虚拟方法是最简单的。

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

    2. static IRBuilder<> Builder(TheContext);
    3. static std::unique_ptr<Module> TheModule;
    4. static std::map<std::string, Value *> NamedValues;
    6. Value *LogErrorV(const char *Str) {
    7.   LogError(Str);
    8.   return nullptr;
    9. }

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

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

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

    该NamedValues地图跟踪哪些值在当前范围以及他们LLVM表示被定义。（换句话说，它是代码的符号表）。在这种形式的万花筒中，唯一可以引用的是功能参数。因此，在为其函数体生成代码时，函数参数将在此映射中。

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

    为表达式节点生成LLVM代码非常简单：所有四个表达式节点的注释代码少于45行。首先，我们将做数字文字：

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

    在LLVM IR中，数字常量用ConstantFP类表示 ，它在APFloat 内部保存数值（APFloat能够保持任意精度的浮点常量）。这段代码基本上只是创建并返回一个ConstantFP。请注意，在LLVM IR中，常量都是唯一的并且共享。出于这个原因，API使用“foo :: get（…）”成语而不是“new foo（..）”或“foo :: Create（..）”。

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

    使用LLVM对变量的引用也非常简单。在简单版的Kaleidoscope中，我们假设变量已经在某处发出并且其值可用。实际上，NamedValues映射中唯一的值是函数参数。此代码只是检查指定的名称是否在映射中（如果没有，则引用未知变量）并返回其值。在以后的章节中，我们将在符号表和局部变量中添加对循环归纳变量的支持。

    1. Value *BinaryExprAST::codegen() {
    2.   Value *L = LHS->codegen();
    3.   Value *R = RHS->codegen();
    4.   if (!L || !R)
    5.     return nullptr;
    7.   switch (Op) {
    8.   case '+':
    9.     return Builder.CreateFAdd(L, R, "addtmp");
    10.   case '-':
    11.     return Builder.CreateFSub(L, R, "subtmp");
    12.   case '*':
    13.     return Builder.CreateFMul(L, R, "multmp");
    14.   case '<':
    15.     L = Builder.CreateFCmpULT(L, R, "cmptmp");
    16.     // Convert bool 0/1 to double 0.0 or 1.0
    17.     return Builder.CreateUIToFP(L, Type::getDoubleTy(TheContext),
    18.                                 "booltmp");
    19.   default:
    20.     return LogErrorV("invalid binary operator");
    21.   }
    22. }
    1. Value *CallExprAST::codegen() {
    2.   // Look up the name in the global module table.
    3.   Function *CalleeF = TheModule->getFunction(Callee);
    4.   if (!CalleeF)
    5.     return LogErrorV("Unknown function referenced");
    7.   // If argument mismatch error.
    8.     return LogErrorV("Incorrect # arguments passed");
    10.   std::vector<Value *> ArgsV;
    11.   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
    12.     ArgsV.push_back(Args[i]->codegen());
    13.     if (!ArgsV.back())
    14.       return nullptr;
    15.   }
    17.   return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
    18. }

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

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

    这包含了我们对Kaleidoscope中迄今为止的四个基本表达式的处理。随意进入并添加更多。例如，通过浏览LLVM语言参考，您将找到其他一些非常容易插入基本框架的有趣指令。

    3.4 功能代码生成

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

    这段代码将很多功能集成到几行中。首先请注意，此函数返回“Function ”而不是“Value ”。因为“原型”真的是在谈论函数的外部接口（而不是由表达式计算的值），所以它返回与codegen时相对应的LLVM函数是有意义的。

    FunctionType::get创建FunctionType它的调用应该用于给定的Prototype。由于Kaleidoscope中的所有函数参数都是double类型，因此第一行创建了一个“N”LLVM double类型的向量。然后它使用该Functiontype::get方法创建一个函数类型，该函数类型将“N”双精度作为参数，结果返回一个double，而不是vararg（false参数表示这一点）。请注意，LLVM中的类型与常量一样是唯一的，所以你不要“新”一个类型，你“得到”它。

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

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

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

    在这一点上，我们有一个没有身体的功能原型。这是LLVM IR表示函数声明的方式。对于Kaleidoscope中的外部声明，这是我们需要的。但是对于函数定义，我们需要codegen并附加一个函数体。

    1. Function *FunctionAST::codegen() {
    2.     // First, check for an existing function from a previous 'extern' declaration.
    3.   Function *TheFunction = TheModule->getFunction(Proto->getName());
    5.   if (!TheFunction)
    6.     TheFunction = Proto->codegen();
    8.   if (!TheFunction)
    9.     return nullptr;
    11.   if (!TheFunction->empty())
    12.     return (Function*)LogErrorV("Function cannot be redefined.");
    1. // Create a new basic block to start insertion into.
    2. BasicBlock *BB = BasicBlock::Create(TheContext, "entry", TheFunction);
    3. Builder.SetInsertPoint(BB);
    5. // Record the function arguments in the NamedValues map.
    6. NamedValues.clear();
    7. for (auto &Arg : TheFunction->args())
    8.   NamedValues[Arg.getName()] = &Arg;

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

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

    1. if (Value *RetVal = Body->codegen()) {
    2.   // Finish off the function.
    3.   Builder.CreateRet(RetVal);
    5.   // Validate the generated code, checking for consistency.
    6.   verifyFunction(*TheFunction);
    8.   return TheFunction;
    9. }
    1.   // Error reading body, remove function.
    2.   TheFunction->eraseFromParent();
    3.   return nullptr;
    4. }

    这里留下的唯一一件事是处理错误案例。为简单起见，我们仅通过删除使用该eraseFromParent方法生成的函数来处理此问题 。这允许用户重新定义之前错误输入的函数：如果我们没有删除它，它将存在于带有正文的符号表中，从而阻止将来重新定义。

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

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

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

    请注意解析器如何将顶级表达式转换为我们的匿名函数。当我们在下一章中添加JIT支持时，这将非常方便。另请注意，代码非常精确地转录，除了IRBuilder完成的简单常量折叠之外，不会执行任何优化。我们将在下一章中明确添加优化。

    1. ready> def foo(a b) a*a + 2*a*b + b*b;
    2. Read function definition:
    3. define double @foo(double %a, double %b) {
    4. entry:
    5.   %multmp1 = fmul double 2.000000e+00, %a
    6.   %multmp2 = fmul double %multmp1, %b
    7.   %addtmp = fadd double %multmp, %multmp2
    8.   %multmp3 = fmul double %b, %b
    10.   ret double %addtmp4
    11. }

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

    1. ready> def bar(a) foo(a, 4.0) + bar(31337);
    2. Read function definition:
    3. define double @bar(double %a) {
    4. entry:
    5.   %calltmp = call double @foo(double %a, double 4.000000e+00)
    6.   %calltmp1 = call double @bar(double 3.133700e+04)
    7.   %addtmp = fadd double %calltmp, %calltmp1
    8.   ret double %addtmp
    9. }

    这显示了一些函数调用。请注意，如果您调用此函数将需要很长时间才能执行。在未来我们将添加条件控制流以实际使递归有用:)。

    1. ready> extern cos(x);
    2. Read extern:
    3. declare double @cos(double)
    5. ready> cos(1.234);
    6. Read top-level expression:
    7. define double @1() {
    8. entry:
    9.   %calltmp = call double @cos(double 1.234000e+00)
    10.   ret double %calltmp
    11. }

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

    1. ready> ^D
    2. ; ModuleID = 'my cool jit'
    4. define double @0() {
    5. entry:
    6.   %addtmp = fadd double 4.000000e+00, 5.000000e+00
    7.   ret double %addtmp
    8. }
    10. define double @foo(double %a, double %b) {
    11. entry:
    12.   %multmp = fmul double %a, %a
    13.   %multmp1 = fmul double 2.000000e+00, %a
    14.   %multmp2 = fmul double %multmp1, %b
    15.   %addtmp = fadd double %multmp, %multmp2
    16.   %multmp3 = fmul double %b, %b
    17.   %addtmp4 = fadd double %addtmp, %multmp3
    18.   ret double %addtmp4
    19. }
    21. define double @bar(double %a) {
    22. entry:
    23.   %calltmp = call double @foo(double %a, double 4.000000e+00)
    24.   %calltmp1 = call double @bar(double 3.133700e+04)
    25.   %addtmp = fadd double %calltmp, %calltmp1
    26.   ret double %addtmp
    27. }
    29. declare double @cos(double)
    31. define double @1() {
    32. entry:
    33.   %calltmp = call double @cos(double 1.234000e+00)

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

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

    3.6 完整的代码清单