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

本贴最后更新于 1639 天前,其中的信息可能已经时过境迁

原文链接: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 调用。示例代码将对代码生成的调用插入 HandleDefinitionHandleExtern 等函数中,然后转储 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

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...