2019-04-19

从LLVM实现新语言的入门教程分析LLVM技术系统的体系架构

本文是学习了LLVM入门教程后的总结，目的是对LLVM的整体技术架构进行梳理，让其更加清晰，了解LLVM的能力边界。

LLVM整体架构

首先，画出LLVM技术的架构的框架图

在整个LLVM实现新语言的教程的系列文章中，文章内容的展开也是，也是按照这个结构逐步展开的，

这篇教程的脉络如下图所示：

词法分析阶段

词法分析阶段的逻辑处理相对简单，每次处理识别出一个Token，此处不再多言。

语法分析阶段

在完成语法分析后，我们将会得到程序的抽象语法树（AST），因此教程中为AST定义了相应的数据结构，如下图所示：

接着，我们分析下，代码的执行路径：

代码生成阶段

在代码生成阶段却一反常态的，没有太多和编译原理相关的概念，更多是怎么运用LLVM::Builder生成指令的技术细节问题。首先在每个HandleXXX(...)函数中完成了AST的构建之后，将调用此次AST根部节点的codegen()函数来生成代码，由于AST节点是可以循环引用的，因此父节点再调用子节点的codegen()完成整棵树枝的代码生成：

static void HandleDefinition() {
  if (auto FnAST = ParseDefinition()) {
    if (auto *FnIR = FnAST->codegen()) {
      ……
      FnIR->print(errs());
    }
  } else
  ……
}

接下来就是为每个AST节点实现codegen()函数：

添加优化器和JIT支持

优化器属于更进一步的实现细节，因此很简略地跳过了，只要知道优化是通过FPM(Function PassManager)实现的，每个优化器是一个Pass实例，需要做什么优化只需要将对应的Pass实例添加到FPM即可：

static void InitializeModuleAndPassManager() {
  // 获得TheModule并为之绑定FPM
  TheModule = llvm::make_unique<Module>("my cool jit", TheContext);
  // 这一句属于JIT的初始化
  TheModule->setDataLayout(TheJIT->getTargetMachine().createDataLayout());

  // Create a new pass manager attached to it.
  TheFPM = llvm::make_unique<legacy::FunctionPassManager>(TheModule.get());

  // 通过一系列add设置优化策略
  //Do simple "peephole" optimizations and bit-twiddling optzns.
  TheFPM->add(createInstructionCombiningPass());
  // Reassociate expressions.
  TheFPM->add(createReassociatePass());
  // Eliminate Common SubExpressions.
  TheFPM->add(createGVNPass());
  // Simplify the control flow graph (deleting unreachable blocks, etc).
  TheFPM->add(createCFGSimplificationPass());

  TheFPM->doInitialization();
}

JIT是用来解释执行前面codegen()生成的LLVM IR代码，这是我比较关心的环节。在本教程中仅展示了JIT的使用，没有太深入到其实现。首先是初始化：

int main() {
  // 为创建JIT初始化环境
  InitializeNativeTarget();
  InitializeNativeTargetAsmPrinter();
  InitializeNativeTargetAsmParser();

  ……
  getNextToken();
  // 创建TheJIT
  TheJIT = llvm::make_unique<KaleidoscopeJIT>();

  InitializeModuleAndPassManager();

  // Run the main "interpreter loop" now.
  MainLoop();

  return 0;
}

都是些程式化的调用，需要注意TheJIT其实是自定义的KaleidoscopeJIT实例，而不直接来自LLVM API，想要了解细节应该深入到该类的内部，这是《Building a JIT in LLVM》中讨论的问题。

具体解析执行的代码如下：

static void HandleTopLevelExpression() {
  ……
  if (auto FnAST = ParseTopLevelExpr()) {
    if (FnAST->codegen()) {
      // 将包含顶级表达式的模块添加到JIT
      auto H = TheJIT->addModule(std::move(TheModule));
      InitializeModuleAndPassManager();

      // Search the JIT for the  __anon_expr symbol.
      auto ExprSymbol = TheJIT->findSymbol("__anon_expr");
      ……

      // Get the symbol's address and cast it to the right type (takes no
      // arguments, returns a double) so we can call it as a native function.
      double (*FP)() = (double (*)())(intptr_t)cantFail(ExprSymbol.getAddress());
      fprintf(stderr, "Evaluated to %f\n", FP());

      // Delete the anonymous expression module from the JIT.
      TheJIT->removeModule(H);
    }
  } ……
}

解释执行在大的步骤上分四步：

添加模块TheJit->addModule(...)。这一步很容易理解，函数、变量定义只有先添加进来，后面才能执行。
找到入口函数TheJIT->findSymbol(...)。和添加模块不同，仅在HandleTopLevelExpression()中有对findSymbol(...)的调用，这是因为只有顶层表达式需要执行，对于函数定义只需要添加到模块就可以了。
执行入口函数。对于顶层表达式，可能就是一段代码，没有函数入口，此时这段代码依然有个名字——__anon_expr，如上面代码所示。
删除模块。当次顶层表达式执行完成后，就应该立刻删除，因为进入了下一轮交互，再输入表达式和上一次的无关，如果不删除会导致重复执行。在这里有个细节：就是只删除可执行的表达式即可，定义还是要保留的，因此需要把可执行表达式和定义表达式分开添加。

编译为目标代码

更是一段程式化的操作了，需要注意的是LLVM可以执行交叉编译，编译成目标机器的代码，因此需要指定目标机器：

int main() {
  ……
  MainLoop();

  // Initialize the target registry etc.
  InitializeAllTargetInfos();
  InitializeAllTargets();
  InitializeAllTargetMCs();
  InitializeAllAsmParsers();
  InitializeAllAsmPrinters();

  auto TargetTriple = sys::getDefaultTargetTriple();
  TheModule->setTargetTriple(TargetTriple);
  ……
  auto Target = TargetRegistry::lookupTarget(TargetTriple, Error);
  ……
  // 指定目标机器
  auto CPU = "generic";
  auto Features = "";

  TargetOptions opt;
  auto RM = Optional<Reloc::Model>();
  auto TheTargetMachine =
      Target->createTargetMachine(TargetTriple, CPU, Features, opt, RM);

  TheModule->setDataLayout(TheTargetMachine->createDataLayout());
  // 准备发出目标代码
  auto Filename = "output.o";
  ……
  raw_fd_ostream dest(Filename, EC, sys::fs::F_None);
  ……

  legacy::PassManager pass;
  auto FileType = TargetMachine::CGFT_ObjectFile;

  if (TheTargetMachine->addPassesToEmitFile(pass, dest, FileType)) {
    ……
    return 1;
  }

  pass.run(*TheModule);   // 发出目标代码
  dest.flush();
  ……

  return 0;
}

Building a JIT

该教程在概念上只记住一个框架就可以了，就是JIT的基本调用流程：

addModule(Module &M)，使得指定的IR模块可用于执行
JITSymbol findSymbol(const std::string &Name)，从添加到JIT中的模块中查找符号的指针
void removeModule(Handle H)，从JIT中删除模块，释放所有与之相关的内存。

代码形式如下：

std::unique_ptr <Module> M = buildModule ();
JIT J ;
Handle H = J.addModule ( *M );
int (*Main)(int , char* []) = (int (*)(int , char* []))J.getSymbolAddress("main");
int Result = Main();
J.removeModule(H);