使用LLVM实现一个简单编译器

见贤思齐

作者：tomoyazhang，腾讯PCG后台开发工程师1.目标这个系列来自LLVM的Kaleidoscope教程，增加了我对代码的注释以及一些理解，修改了部分代码。现在开始我们要使用LLVM实现一个编译器，完成对如下代码的编译运行。# 斐波那契数列函数定义def fib(x)    if x  lhs,                std::unique_ptr rhs)      : op_(op), lhs_(std::move(lhs)), rhs_(std::move(rhs)) {} private:  char op_;  std::unique_ptr lhs_;  std::unique_ptr rhs_;};// 函数调用表达式class CallExprAST : public ExprAST { public:  CallExprAST(const std::string& callee,              std::vector> args)      : callee_(callee), args_(std::move(args)) {} private:  std::string callee_;  std::vector> args_;};为了便于理解，关于条件表达式的内容放在后面，这里暂不考虑。接着我们定义函数声明和函数的ASTNode：// 函数接口class rototypeAST { public:  rototypeAST(const std::string& name, std::vector args)      : name_(name), args_(std::move(args)) {}  const std::string& name() const { return name_; } private:  std::string name_;  std::vector args_;};// 函数class FunctionAST { public:  FunctionAST(std::unique_ptr  proto,              std::unique_ptr body)      : proto_(std::move(proto)), body_(std::move(body)) {} private:  std::unique_ptr  proto_;  std::unique_ptr body_;};接下来我们要进行Parse,在正式Parse前，定义如下函数方便后续处理：int g_current_token;  // 当前待处理的Tokenint GetNextToken() {  return g_current_token = GetToken();}首先我们处理最简单的字面值：// numberexpr ::= numberstd::unique_ptr arseNumberExpr() {  auto result = std::make_unique(g_number_val);  GetNextToken();  return std::move(result);}这段程序非常简单，当前Token为TOKEN_NUMBER时被调用，使用g_number_val，创建一个NumberExprAST,因为当前Token处理完毕，让Lexer前进一个Token,最后返回。接着我们处理圆括号操作符、变量、函数调用：// parenexpr ::= ( expression )std::unique_ptr arseParenExpr() {  GetNextToken();  // eat (  auto expr = arseExpression();  GetNextToken();  // eat )  return expr;}/// identifierexpr///   ::= identifier///   ::= identifier ( expression, expression, ..., expression )std::unique_ptr arseIdentifierExpr() {  std::string id = g_identifier_str;  GetNextToken();  if (g_current_token != '(') {    return std::make_unique(id);  } else {    GetNextToken();  // eat (    std::vector> args;    while (g_current_token != ')') {      args.push_back(ParseExpression());      if (g_current_token == ')') {        break;      } else {        GetNextToken();  // eat ,      }    }    GetNextToken();  // eat )    return std::make_unique(id, std::move(args));  }}上面代码中的ParseExpression与ParseParenExpr等存在循环依赖，这里按照其名字理解意思即可，具体实现在后面。我们将NumberExpr、ParenExpr、IdentifierExpr视为PrimaryExpr,封装ParsePrimary方便后续调用：/// primary///   ::= identifierexpr///   ::= numberexpr///   ::= parenexprstd::unique_ptr arsePrimary() {  switch (g_current_token) {    case TOKEN_IDENTIFIER: return arseIdentifierExpr();    case TOKEN_NUMBER: return arseNumberExpr();    case '(': return arseParenExpr();    default: return nullptr;  }}接下来我们考虑如何处理二元操作符，为了方便，Kaleidoscope只支持4种二元操作符，优先级为：' g_binop_precedence = {    {'second;  } else {    return -1;  }}对于带优先级的二元操作符的解析，我们会将其分成多个片段。比如一个表达式：a + b + (c + d) * e * f + g首先解析a,然后处理多个二元组：[+, b], [+, (c+d)], [*, e], [*, f], [+, g]即，复杂表达式可以抽象为一个PrimaryExpr跟着多个[binop,PrimaryExpr]二元组，注意由于圆括号属于PrimaryExpr,所以这里不需要考虑怎么特殊处理(c+d)，因为会被ParsePrimary自动处理。// parse//   lhs [binop primary] [binop primary] ...// 如遇到优先级小于min_precedence的操作符，则停止std::unique_ptr ParseBinOpRhs(int min_precedence,                                       std::unique_ptr lhs) {  while (true) {    int current_precedence = GetTokenPrecedence();    if (current_precedence (binop, std::move(lhs), std::move(rhs));    // 继续循环  }}// expression//   ::= primary [binop primary] [binop primary] ...std::unique_ptr ParseExpression() {  auto lhs = ParsePrimary();  return ParseBinOpRhs(0, std::move(lhs));}最复杂的部分完成后，按部就班把function写完：// prototype//   ::= id ( id id ... id)std::unique_ptr  ParsePrototype() {  std::string function_name = g_identifier_str;  GetNextToken();  std::vector arg_names;  while (GetNextToken() == TOKEN_IDENTIFIER) {    arg_names.push_back(g_identifier_str);  }  GetNextToken();  // eat )  return std::make_unique (function_name, std::move(arg_names));}// definition ::= def prototype expressionstd::unique_ptr ParseDefinition() {  GetNextToken();  // eat def  auto proto = ParsePrototype();  auto expr = ParseExpression();  return std::make_unique(std::move(proto), std::move(expr));}// external ::= extern prototypestd::unique_ptr  ParseExtern() {  GetNextToken();  // eat extern  return ParsePrototype();}最后，我们为顶层的代码实现匿名function：// toplevelexpr ::= expressionstd::unique_ptr ParseTopLevelExpr() {  auto expr = ParseExpression();  auto proto = std::make_unique ("", std::vector());  return std::make_unique(std::move(proto), std::move(expr));}顶层代码的意思是放在全局而不放在function内定义的一些执行语句比如变量赋值，函数调用等。编写一个main函数：int main() {  GetNextToken();  while (true) {    switch (g_current_token) {      case TOKEN_EOF: return 0;      case TOKEN_DEF: {        ParseDefinition();        std::cout << "parsed a function definition" << std::endl;        break;      }      case TOKEN_EXTERN: {        ParseExtern();        std::cout << "parsed a extern" << std::endl;        break;      }      default: {        ParseTopLevelExpr();        std::cout << "parsed a top level expr" << std::endl;        break;      }    }  }  return 0;}编译：clang++ main.cpp `llvm-config --cxxflags --ldflags --libs`输入如下代码进行测试：def foo(x y)    x + foo(y, 4)def foo(x y)    x + yyextern sin(a)得到输出：parsed a function definitionparsed a function definitionparsed a top level exprparsed a extern至此成功将 Lexer 输出的 tokens 转为 AST。4. Code Generation to LLVM IR终于开始 codegen 了，首先我们 include 一些 LLVM 头文件，定义一些全局变量：#include "llvm/ADT/APFloat.h"#include "llvm/ADT/STLExtras.h"#include "llvm/IR/BasicBlock.h"#include "llvm/IR/Constants.h"#include "llvm/IR/DerivedTypes.h"#include "llvm/IR/Function.h"#include "llvm/IR/IRBuilder.h"#include "llvm/IR/LLVMContext.h"#include "llvm/IR/LegacyPassManager.h"#include "llvm/IR/Module.h"#include "llvm/IR/Type.h"#include "llvm/IR/Verifier.h"#include "llvm/Support/TargetSelect.h"#include "llvm/Target/TargetMachine.h"#include "llvm/Transforms/InstCombine/InstCombine.h"#include "llvm/Transforms/Scalar.h"#include "llvm/Transforms/Scalar/GVN.h"// 记录了LLVM的核心数据结构，比如类型和常量表，不过我们不太需要关心它的内部llvm:LVMContext g_llvm_context;// 用于创建LLVM指令llvm::IRBuilder<> g_ir_builder(g_llvm_context);// 用于管理函数和全局变量，可以粗浅地理解为类c++的编译单元(单个cpp文件)llvm::Module g_module("my cool jit", g_llvm_context);// 用于记录函数的变量参数std::map g_named_values;然后给每个ASTClass增加一个CodeGen接口：// 所有 `表达式` 节点的基类class ExprAST { public:  virtual ~ExprAST() {}  virtual llvm::Value* CodeGen() = 0;};// 字面值表达式class NumberExprAST : public ExprAST { public:  NumberExprAST(double val) : val_(val) {}  llvm::Value* CodeGen() override; private:  double val_;};首先实现NumberExprAST的CodeGen：llvm::Value* NumberExprAST::CodeGen() {  return llvm::ConstantFP::get(g_llvm_context, llvm::APFloat(val_));}由于Kaleidoscope只有一种数据类型FP64,所以直接调用ConstantFP传入即可，APFloat是llvm内部的数据结构，用于存储ArbitraryPrecisionFloat.在LLVMIR中，所有常量是唯一且共享的，所以这里使用的get而不是new/create。然后实现VariableExprAST的CodeGen：llvm::Value* VariableExprAST::CodeGen() {  return g_named_values.at(name_);}由于Kaleidoscope的VariableExpr只存在于函数内对函数参数的引用，我们假定函数参数已经被注册到g_name_values中，所以VariableExpr直接查表返回即可。接着实现BinaryExprAST,分别codegenlhs,rhs然后创建指令处理lhs,rhs即可：llvm::Value* BinaryExprAST::CodeGen() {  llvm::Value* lhs = lhs_->CodeGen();  llvm::Value* rhs = rhs_->CodeGen();  switch (op_) {    case ' args;  for (std::unique_ptr& arg_expr : args_) {    args.push_back(arg_expr->CodeGen());  }  return g_ir_builder.CreateCall(callee, args, "calltmp");}实现ProtoTypeAST：llvm::Value* PrototypeAST::CodeGen() {  // 创建kaleidoscope的函数类型 double (doube, double, ..., double)  std::vector doubles(args_.size(),                                   llvm::Type::getDoubleTy(g_llvm_context));  // 函数类型是唯一的，所以使用get而不是new/create  llvm::FunctionType* function_type = llvm::FunctionType::get(      llvm::Type::getDoubleTy(g_llvm_context), doubles, false);  // 创建函数, ExternalLinkage意味着函数可能不在当前module中定义，在当前module  // 即g_module中注册名字为name_, 后面可以使用这个名字在g_module中查询  llvm::Function* func = llvm::Function::Create(      function_type, llvm::Function::ExternalLinkage, name_, &g_module);  // 增加IR可读性，设置function的argument name  int index = 0;  for (auto& arg : func->args()) {    arg.setName(args_[index++]);  }  return func;}实现FunctionAST：llvm::Value* FunctionAST::CodeGen() {  // 检查函数声明是否已完成codegen(比如之前的extern声明), 如果没有则执行codegen  llvm::Function* func = g_module.getFunction(proto_->name());  if (func == nullptr) {    func = proto_->CodeGen();  }  // 创建一个Block并且设置为指令插入位置。  // llvm block用于定义control flow graph, 由于我们暂不实现control flow, 创建  // 一个单独的block即可  llvm::BasicBlock* block =      llvm::BasicBlock::Create(g_llvm_context, "entry", func);  g_ir_builder.SetInsertPoint(block);  // 将函数参数注册到g_named_values中，让VariableExprAST可以codegen  g_named_values.clear();  for (llvm::Value& arg : func->args()) {    g_named_values[arg.getName()] = &arg;  }  // codegen body然后return  llvm::Value* ret_val = body_->CodeGen();  g_ir_builder.CreateRet(ret_val);  llvm::verifyFunction(*func);  return func;}至此，所有codegen都已完成，修改main：int main() {  GetNextToken();  while (true) {    switch (g_current_token) {      case TOKEN_EOF: return 0;      case TOKEN_DEF: {        auto ast = ParseDefinition();        std::cout << "parsed a function definition" << std::endl;        ast->CodeGen()->print(llvm::errs());        std::cerr << std::endl;        break;      }      case TOKEN_EXTERN: {        auto ast = ParseExtern();        std::cout << "parsed a extern" << std::endl;        ast->CodeGen()->print(llvm::errs());        std::cerr << std::endl;        break;      }      default: {        auto ast = ParseTopLevelExpr();        std::cout << "parsed a top level expr" << std::endl;        ast->CodeGen()->print(llvm::errs());        std::cerr << std::endl;        break;      }    }  }  return 0;}输入测试：4 + 5def foo(a b)    a*a + 2*a*b + b*bfoo(2, 3)def bar(a)    foo(a, 4) + bar(31337)extern cos(x)cos(1.234)得到输出：parsed a top level exprdefine double @0() {entry:  ret double 9.000000e+00}parsed a function definitiondefine 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}parsed a top level exprdefine double @1() {entry:  %calltmp = call double @foo(double 2.000000e+00, double 3.000000e+00)  ret double %calltmp}parsed a function definitiondefine 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}parsed a externdeclare double @cos(double)parsed a top level exprdefine double @2() {entry:  %calltmp = call double @cos(double 1.234000e+00)  ret double %calltmp}至此，我们已成功将>CodeGen();  g_ir_builder.CreateRet(ret_val);  llvm::verifyFunction(*func);  g_fpm.run(*func); // 增加这句  return func;即启动了对每个function的优化，接下来测试之前的代码：parsed a function definitiondefine double @test(double %x) {entry:  %addtmp = fadd double %x, 3.000000e+00  %multmp = fmul double %addtmp, %addtmp  ret double %multmp}可以看到，和我们期望的一样，加法指令减少到一个。6.AddingaJITCompiler由于JIT模式中我们需要反复创建新的module,所以我们将全局变量g_module改为unique_ptr。// 用于管理函数和全局变量，可以粗浅地理解为类c++的编译单元(单个cpp文件)std::unique_ptr g_module =    std::make_unique("my cool jit", g_llvm_context);为了专注于JIT，我们可以把优化的passes删掉。修改ParseTopLevelExpr，给PrototypeAST命名为__anon_expr,让我们后面可以通过这个名字找到它。// toplevelexpr ::= expressionstd::unique_ptr ParseTopLevelExpr() {  auto expr = ParseExpression();  auto proto =      std::make_unique ("__anon_expr", std::vector());  return std::make_unique(std::move(proto), std::move(expr));}然后我们从llvm-project中拷贝一份代码llvm/examples/Kaleidoscope/include/KaleidoscopeJIT.h到本地再include,其定义了KaleidoscopeJIT类，关于这个类，在后面会做解读，这里先不管。定义全局变量g_jit,并使用InitializeNativeTarget*函数初始化环境。#include "KaleidoscopeJIT.h"std::unique_ptr g_jit;int main() {  llvm::InitializeNativeTarget();  llvm::InitializeNativeTargetAsmPrinter();  llvm::InitializeNativeTargetAsmParser();  g_jit.reset(new llvm:rc::KaleidoscopeJIT);  g_module->setDataLayout(g_jit->getTargetMachine().createDataLayout());  ...}修改main处理toplevelexpr的代码为：        auto ast = ParseTopLevelExpr();        std::cout << "parsed a top level expr" << std::endl;        ast->CodeGen()->print(llvm::errs());        std::cout << std::endl;        auto h = g_jit->addModule(std::move(g_module));        // 重新创建g_module在下次使用        g_module =            std::make_unique("my cool jit", g_llvm_context);        g_module->setDataLayout(g_jit->getTargetMachine().createDataLayout());        // 通过名字找到编译的函数符号        auto symbol = g_jit->findSymbol("__anon_expr");        // 强转为C函数指针        double (*fp)() = (double (*)())(symbol.getAddress().get());        // 执行输出        std::cout << fp() << std::endl;        g_jit->removeModule(h);        break;输入：4 + 5def foo(a b)    a*a + 2*a*b + b*bfoo(2, 3)得到输出：parsed a top level exprdefine double @__anon_expr() {entry:  ret double 9.000000e+00}9parsed a function definitiondefine 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}parsed a top level exprdefine double @__anon_expr() {entry:  %calltmp = call double @foo(double 2.000000e+00, double 3.000000e+00)  ret double %calltmp}25可以看到代码已经顺利执行，但现在的实现仍然是有问题的，比如上面的输入，foo函数的定义和调用是被归在同一个module中，当第一次调用完成后，由于我们removeModule,第二次调用foo会失败。在解决这个问题之前，我们先把main函数内对不同TOKEN的处理拆成多个函数，如下：void ReCreateModule() {  g_module = std::make_unique("my cool jit", g_llvm_context);  g_module->setDataLayout(g_jit->getTargetMachine().createDataLayout());}void ParseDefinitionToken() {  auto ast = ParseDefinition();  std::cout << "parsed a function definition" << std::endl;  ast->CodeGen()->print(llvm::errs());  std::cerr << std::endl;}void ParseExternToken() {  auto ast = ParseExtern();  std::cout << "parsed a extern" << std::endl;  ast->CodeGen()->print(llvm::errs());  std::cerr << std::endl;}void ParseTopLevel() {  auto ast = ParseTopLevelExpr();  std::cout << "parsed a top level expr" << std::endl;  ast->CodeGen()->print(llvm::errs());  std::cout << std::endl;  auto h = g_jit->addModule(std::move(g_module));  // 重新创建g_module在下次使用  ReCreateModule();  // 通过名字找到编译的函数符号  auto symbol = g_jit->findSymbol("__anon_expr");  // 强转为C函数指针  double (*fp)() = (double (*)())(symbol.getAddress().get());  // 执行输出  std::cout << fp() << std::endl;  g_jit->removeModule(h);}int main() {  llvm::InitializeNativeTarget();  llvm::InitializeNativeTargetAsmPrinter();  llvm::InitializeNativeTargetAsmParser();  g_jit.reset(new llvm:rc::KaleidoscopeJIT);  g_module->setDataLayout(g_jit->getTargetMachine().createDataLayout());  GetNextToken();  while (true) {    switch (g_current_token) {      case TOKEN_EOF: return 0;      case TOKEN_DEF: ParseDefinitionToken(); break;      case TOKEN_EXTERN: ParseExternToken(); break;      default: ParseTopLevel(); break;    }  }  return 0;}为了解决第二次调用foo失败的问题，我们需要让function和toplevelexpr处于不同的Module,而处于不同Module的话，CallExprAST的CodeGen在当前module会找不到function,所以需要自动在CallExprAST做CodeGen时在当前Module声明这个函数，即自动地增加extern,也就是在当前Module自动做对应PrototypeAST的CodeGen.首先，增加一个全局变量存储从函数名到函数接口的映射，并增加一个查询函数。std::map> name2proto_ast;llvm::Function* GetFunction(const std::string& name) {  llvm::Function* callee = g_module->getFunction(name);  if (callee != nullptr) {  // 当前module存在函数定义    return callee;  } else {    // 声明函数    return name2proto_ast.at(name)->CodeGen();  }}更改CallExprAST的CodeGen,让其使用上面定义的GetFuntion：llvm::Value* CallExprAST::CodeGen() {  llvm::Function* callee = GetFunction(callee_);  std::vector args;  for (std::unique_ptr& arg_expr : args_) {    args.push_back(arg_expr->CodeGen());  }  return g_ir_builder.CreateCall(callee, args, "calltmp");}更改FunctionAST的CodeGen,让其将结果写入name2proto_ast：llvm::Value* FunctionAST::CodeGen() {  PrototypeAST& proto = *proto_;  name2proto_ast[proto.name()] = std::move(proto_);  // transfer ownership  llvm::Function* func = GetFunction(proto.name());  // 创建一个Block并且设置为指令插入位置。  // llvm block用于定义control flow graph, 由于我们暂不实现control flow, 创建  // 一个单独的block即可  llvm::BasicBlock* block =      llvm::BasicBlock::Create(g_llvm_context, "entry", func);  g_ir_builder.SetInsertPoint(block);  // 将函数参数注册到g_named_values中，让VariableExprAST可以codegen  g_named_values.clear();  for (llvm::Value& arg : func->args()) {    g_named_values[arg.getName()] = &arg;  }  // codegen body然后return  llvm::Value* ret_val = body_->CodeGen();  g_ir_builder.CreateRet(ret_val);  llvm::verifyFunction(*func);  return func;}修改ParseExternToken将结果写入name2proto_ast：void ParseExternToken() {  auto ast = ParseExtern();  std::cout << "parsed a extern" << std::endl;  ast->CodeGen()->print(llvm::errs());  std::cerr << std::endl;  name2proto_ast[ast->name()] = std::move(ast);}修改ParseDefinitionToken让其使用独立Module：void ParseDefinitionToken() {  auto ast = ParseDefinition();  std::cout << "parsed a function definition" << std::endl;  ast->CodeGen()->print(llvm::errs());  std::cerr << std::endl;  g_jit->addModule(std::move(g_module));  ReCreateModule();}修改完毕，输入测试：def foo(x)    x + 1foo(2)def foo(x)    x + 2foo(2)extern sin(x)extern cos(x)sin(1.0)def foo(x)    sin(x) * sin(x) + cos(x) * cos(x)foo(4)foo(3)得到输出：parsed a function definitiondefine double @foo(double %x) {entry:  %addtmp = fadd double %x, 1.000000e+00  ret double %addtmp}parsed a top level exprdefine double @__anon_expr() {entry:  %calltmp = call double @foo(double 2.000000e+00)  ret double %calltmp}3parsed a function definitiondefine double @foo(double %x) {entry:  %addtmp = fadd double %x, 2.000000e+00  ret double %addtmp}parsed a top level exprdefine double @__anon_expr() {entry:  %calltmp = call double @foo(double 2.000000e+00)  ret double %calltmp}4parsed a externdeclare double @sin(double)parsed a externdeclare double @cos(double)parsed a top level exprdefine double @__anon_expr() {entry:  %calltmp = call double @sin(double 1.000000e+00)  ret double %calltmp}0.841471parsed a function definitiondefine double @foo(double %x) {entry:  %calltmp = call double @sin(double %x)  %calltmp1 = call double @sin(double %x)  %multmp = fmul double %calltmp, %calltmp1  %calltmp2 = call double @cos(double %x)  %calltmp3 = call double @cos(double %x)  %multmp4 = fmul double %calltmp2, %calltmp3  %addtmp = fadd double %multmp, %multmp4  ret double %addtmp}parsed a top level exprdefine double @__anon_expr() {entry:  %calltmp = call double @foo(double 4.000000e+00)  ret double %calltmp}1parsed a top level exprdefine double @__anon_expr() {entry:  %calltmp = call double @foo(double 3.000000e+00)  ret double %calltmp}1成功运行，执行正确！代码可以正确解析sin,cos的原因在KaleidoscopeJIT.h中，截取其寻找符号的代码。  JITSymbol findMangledSymbol(const std::string &Name) {#ifdef _WIN32    // The symbol lookup of ObjectLinkingLayer uses the SymbolRef::SF_Exported    // flag to decide whether a symbol will be visible or not, when we call    // IRCompileLayer::findSymbolIn with ExportedSymbolsOnly set to true.    //    // But for Windows COFF objects, this flag is currently never set.    // For a potential solution see: https://reviews.llvm.org/rL258665    // For now, we allow non-exported symbols on Windows as a workaround.    const bool ExportedSymbolsOnly = false;#else    const bool ExportedSymbolsOnly = true;#endif    // Search modules in reverse order: from last added to first added.    // This is the opposite of the usual search order for dlsym, but makes more    // sense in a REPL where we want to bind to the newest available definition.    for (auto H : make_range(ModuleKeys.rbegin(), ModuleKeys.rend()))      if (auto Sym = CompileLayer.findSymbolIn(H, Name, ExportedSymbolsOnly))        return Sym;    // If we can't find the symbol in the JIT, try looking in the host process.    if (auto SymAddr = RTDyldMemoryManager::getSymbolAddressInProcess(Name))      return JITSymbol(SymAddr, JITSymbolFlags::Exported);#ifdef _WIN32    // For Windows retry without "_" at beginning, as RTDyldMemoryManager uses    // GetProcAddress and standard libraries like msvcrt.dll use names    // with and without "_" (for example "_itoa" but "sin").    if (Name.length() > 2 && Name[0] == '_')      if (auto SymAddr =              RTDyldMemoryManager::getSymbolAddressInProcess(Name.substr(1)))        return JITSymbol(SymAddr, JITSymbolFlags::Exported);#endif    return null可以看到，在之前定义的Module找不到后会在hostprocess中寻找这个符号。7.SSA继续给我们的Kaleidoscope添加功能之前，需要先介绍SSA,StaticSingleAssignment，考虑下面代码：y := 1y := 2x := y我们可以发现第一个赋值是不必须的，而且第三行使用的y来自第二行的赋值，改成SSA格式为y_1 = 1y_2 = 2x_1 = y_2改完可以方便编译器进行优化，比如把第一个赋值删去，于是我们可以给出SSA的定义：每个变量仅且必须被赋值一次，原本代码中的多次变量赋值会被赋予版本号然后视为不同变量；每个变量在被使用之前必须被定义。考虑如下ControlFlowGraph：加上版本号：可以看到，这里遇到一个问题，最下面的block里面的y应该使用y1还是y2,为了解决这个问题，插入一个特殊语句称为phifunction,其会根据controlflow从y1和y2中选择一个值作为y3,如下：可以看到，对于x不需要phifunction,因为两个分支到最后的都是x2。8.ControlFlow我们现在实现的Kaleidoscope还不够完善，缺少ifelse控制流，比如不支持如下代码：def fib(x)    if x  cond, std::unique_ptr then_expr,            std::unique_ptr else_expr)      : cond_(std::move(cond)),        then_expr_(std::move(then_expr)),        else_expr_(std::move(else_expr)) {}  llvm::Value* CodeGen() override; private:  std::unique_ptr cond_;  std::unique_ptr then_expr_;  std::unique_ptr else_expr_;};增加对IfExprAST的解析：std::unique_ptr ParseIfExpr() {  GetNextToken();  // eat if  std::unique_ptr cond = ParseExpression();  GetNextToken();  // eat then  std::unique_ptr then_expr = ParseExpression();  GetNextToken();  // eat else  std::unique_ptr else_expr = ParseExpression();  return std::make_unique(std::move(cond), std::move(then_expr),                                     std::move(else_expr));}增加到ParsePrimary中：// primary//   ::= identifierexpr//   ::= numberexpr//   ::= parenexprstd::unique_ptr ParsePrimary() {  switch (g_current_token) {    case TOKEN_IDENTIFIER: return ParseIdentifierExpr();    case TOKEN_NUMBER: return ParseNumberExpr();    case '(': return ParseParenExpr();    case TOKEN_IF: return ParseIfExpr();    default: return nullptr;  }}完成了lex和parse，接下来是最有意思的codegen：llvm::Value* IfExprAST::CodeGen() {  llvm::Value* cond_value = cond_->CodeGen();  // 创建fcmp one指令, cond_value = (cond_value != 0.0)  // 转为1bit (bool)类型  cond_value = g_ir_builder.CreateFCmpONE(      cond_value, llvm::ConstantFP::get(g_llvm_context, llvm::APFloat(0.0)),      "ifcond");  // 在每个function内我们会创建一个block, 这里一定在这个block内，根据block得到  // 对应的上层function  llvm::Function* func = g_ir_builder.GetInsertBlock()->getParent();  // 为then else以及最后的final创建block  llvm::BasicBlock* then_block =      llvm::BasicBlock::Create(g_llvm_context, "then", func);  llvm::BasicBlock* else_block =      llvm::BasicBlock::Create(g_llvm_context, "else");  llvm::BasicBlock* final_block =      llvm::BasicBlock::Create(g_llvm_context, "ifcont");  // 创建跳转指令，根据cond_value选择then_block/else_block  g_ir_builder.CreateCondBr(cond_value, then_block, else_block);  // codegen then_block, 增加跳转final_block指令  g_ir_builder.SetInsertPoint(then_block);  llvm::Value* then_value = then_expr_->CodeGen();  g_ir_builder.CreateBr(final_block);  // then语句内可能会有嵌套的if/then/else, 在嵌套的codegen时，会改变当前的  // InsertBlock, 我们需要有最终结果的那个block作为这里的then_block  then_block = g_ir_builder.GetInsertBlock();  // 在这里才加入是为了让这个block位于上面的then里嵌套block的后面  func->getBasicBlockList().push_back(else_block);  // 与then类似  g_ir_builder.SetInsertPoint(else_block);  llvm::Value* else_value = else_expr_->CodeGen();  g_ir_builder.CreateBr(final_block);  else_block = g_ir_builder.GetInsertBlock();  // codegen final  func->getBasicBlockList().push_back(final_block);  g_ir_builder.SetInsertPoint(final_block);  llvm:HINode* pn = g_ir_builder.CreatePHI(      llvm::Type::getDoubleTy(g_llvm_context), 2, "iftmp");  pn->addIncoming(then_value, then_block);  pn->addIncoming(else_value, else_block);  return pn;}这里使用了上一节SSA中提到的phifunction，输入：def foo(x)    if x  start_expr,             std::unique_ptr end_expr,             std::unique_ptr step_expr,             std::unique_ptr body_expr)      : var_name_(var_name),        start_expr_(std::move(start_expr)),        end_expr_(std::move(end_expr)),        step_expr_(std::move(step_expr)),        body_expr_(std::move(body_expr)) {}  llvm::Value* CodeGen() override; private:  std::string var_name_;  std::unique_ptr start_expr_;  std::unique_ptr end_expr_;  std::unique_ptr step_expr_;  std::unique_ptr body_expr_;};添加到Primary的解析中：// forexpr ::= for var_name = start_expr, end_expr, step_expr in body_exprstd::unique_ptr ParseForExpr() {  GetNextToken();  // eat for  std::string var_name = g_identifier_str;  GetNextToken();  // eat var_name  GetNextToken();  // eat =  std::unique_ptr start_expr = ParseExpression();  GetNextToken();  // eat ,  std::unique_ptr end_expr = ParseExpression();  GetNextToken();  // eat ,  std::unique_ptr step_expr = ParseExpression();  GetNextToken();  // eat in  std::unique_ptr body_expr = ParseExpression();  return std::make_unique(var_name, std::move(start_expr),                                      std::move(end_expr), std::move(step_expr),                                      std::move(body_expr));}// primary//   ::= identifierexpr//   ::= numberexpr//   ::= parenexprstd::unique_ptr ParsePrimary() {  switch (g_current_token) {    case TOKEN_IDENTIFIER: return ParseIdentifierExpr();    case TOKEN_NUMBER: return ParseNumberExpr();    case '(': return ParseParenExpr();    case TOKEN_IF: return ParseIfExpr();    case TOKEN_FOR: return ParseForExpr();    default: return nullptr;  }}开始codegen：llvm::Value* ForExprAST::CodeGen() {  // codegen start  llvm::Value* start_val = start_expr_->CodeGen();  // 获取当前function  llvm::Function* func = g_ir_builder.GetInsertBlock()->getParent();  // 保存当前的block  llvm::BasicBlock* pre_block = g_ir_builder.GetInsertBlock();  // 新增一个loop block到当前function  llvm::BasicBlock* loop_block =      llvm::BasicBlock::Create(g_llvm_context, "loop", func);  // 为当前block增加到loop_block的跳转指令  g_ir_builder.CreateBr(loop_block);  // 开始在loop_block内增加指令  g_ir_builder.SetInsertPoint(loop_block);  llvm:HINode* var = g_ir_builder.CreatePHI(      llvm::Type::getDoubleTy(g_llvm_context), 2, var_name_.c_str());  // 如果来自pre_block的跳转，则取start_val的值  var->addIncoming(start_val, pre_block);  // 现在我们新增了一个变量var，因为可能会被后面的代码引用，所以要注册到  // g_named_values中，其可能会和函数参数重名，但我们这里为了方便不管  // 这个特殊情况，直接注册到g_named_values中，  g_named_values[var_name_] = var;  // 在loop_block中增加body的指令  body_expr_->CodeGen();  // codegen step_expr  llvm::Value* step_value = step_expr_->CodeGen();  // next_var = var + step_value  llvm::Value* next_value = g_ir_builder.CreateFAdd(var, step_value, "nextvar");  // codegen end_expr  llvm::Value* end_value = end_expr_->CodeGen();  // end_value = (end_value != 0.0)  end_value = g_ir_builder.CreateFCmpONE(      end_value, llvm::ConstantFP::get(g_llvm_context, llvm::APFloat(0.0)),      "loopcond");  // 和if/then/else一样，这里的block可能会发生变化，保存当前的block  llvm::BasicBlock* loop_end_block = g_ir_builder.GetInsertBlock();  // 创建循环结束后的block  llvm::BasicBlock* after_block =      llvm::BasicBlock::Create(g_llvm_context, "afterloop", func);  // 根据end_value选择是再来一次loop_block还是进入after_block  g_ir_builder.CreateCondBr(end_value, loop_block, after_block);  // 给after_block增加指令  g_ir_builder.SetInsertPoint(after_block);  // 如果是再次循环，取新的值  var->addIncoming(next_value, loop_end_block);  // 循环结束，避免被再次引用  g_named_values.erase(var_name_);  // return 0  return llvm::Constant::getNullValue(llvm::Type::getDoubleTy(g_llvm_context));}输入：extern printd(x)def foo(x)    if x `, 优先级等于内置的 ` 10 (LHS RHS)  RHS  RHS)增加TOKEN的类型：enum Token {  ...  TOKEN_BINARY = -11,     // binary};增加TOKEN的识别：// 从标准输入解析一个Token并返回int GetToken() {  ...  // 识别字符串  if (isalpha(last_char)) {    ...    if (g_identifier_str == "def") {      return TOKEN_DEF;    } else if (g_identifier_str == "extern") {      return TOKEN_EXTERN;    } else if (g_identifier_str == "if") {      return TOKEN_IF;    } else if (g_identifier_str == "then") {      return TOKEN_THEN;    } else if (g_identifier_str == "else") {      return TOKEN_ELSE;    } else if (g_identifier_str == "for") {      return TOKEN_FOR;    } else if (g_identifier_str == "in") {      return TOKEN_IN;    } else if (g_identifier_str == "binary") {      return TOKEN_BINARY;    } else {      return TOKEN_IDENTIFIER;    }  }  ...}我们把新增的二元操作符视为一个函数，所以不需要新增AST，但是需要修改PrototypeAST。// 函数接口class PrototypeAST { public:  PrototypeAST(const std::string& name, std::vector args,               bool is_operator = false, int op_precedence = 0)      : name_(name),        args_(std::move(args)),        is_operator_(is_operator),        op_precedence_(op_precedence) {}  llvm::Function* CodeGen();  const std::string& name() const { return name_; }  int op_precedence() const { return op_precedence_; }  bool IsUnaryOp() const { return is_operator_ && args_.size() == 1; }  bool IsBinaryOp() const { return is_operator_ && args_.size() == 2; }  // like `|` in `binary|`  char GetOpName() { return name_[name_.size() - 1]; } private:  std::string name_;  std::vector args_;  bool is_operator_;  int op_precedence_;};修改parse部分：// prototype//   ::= id ( id id ... id)//   ::= binary binop precedence (id id)std::unique_ptr  ParsePrototype() {  std::string function_name;  bool is_operator = false;  int precedence = 0;  switch (g_current_token) {    case TOKEN_IDENTIFIER: {      function_name = g_identifier_str;      is_operator = false;      GetNextToken();  // eat id      break;    }    case TOKEN_BINARY: {      GetNextToken();  // eat binary      function_name = "binary";      function_name += (char)(g_current_token);      is_operator = true;      GetNextToken();  // eat binop      precedence = g_number_val;      GetNextToken();  // eat precedence      break;    }  }  std::vector arg_names;  while (GetNextToken() == TOKEN_IDENTIFIER) {    arg_names.push_back(g_identifier_str);  }  GetNextToken();  // eat )  return std::make_unique (function_name, arg_names, is_operator,                                        precedence);}修改BinaryExprAST的CodeGen处理自定义Operator,增加函数调用指令：llvm::Value* BinaryExprAST::CodeGen() {  llvm::Value* lhs = lhs_->CodeGen();  llvm::Value* rhs = rhs_->CodeGen();  switch (op_) {    case 'args()) {    g_named_values[arg.getName()] = &arg;  }  // codegen body然后return  llvm::Value* ret_val = body_->CodeGen();  g_ir_builder.CreateRet(ret_val);  llvm::verifyFunction(*func);  return func;}输入：# 新增二元操作符 `>`, 优先级等于内置的 ` 10 (LHS RHS)  RHS  22 > 1# 新增二元操作符 `|`, 优先级为5def binary| 5 (LHS RHS)  if LHS then    1  else if RHS then    1  else    01 | 00 | 10 | 01 | 1得到输出：parsed a function definitiondefine double @"binary>"(double %LHS, double %RHS) {entry:  %cmptmp = fcmp ult double %RHS, %LHS  %booltmp = uitofp i1 %cmptmp to double  ret double %booltmp}parsed a top level exprdefine double @__anon_expr() {entry:  %binop = call double @"binary>"(double 1.000000e+00, double 2.000000e+00)  ret double %binop}0parsed a top level exprdefine double @__anon_expr() {entry:  %binop = call double @"binary>"(double 2.000000e+00, double 1.000000e+00)  ret double %binop}1parsed a function definitiondefine double @"binary|"(double %LHS, double %RHS) {entry:  %ifcond = fcmp one double %LHS, 0.000000e+00  br i1 %ifcond, label %then, label %elsethen:                                             ; preds = %entry  br label %ifcont4else:                                             ; preds = %entry  %ifcond1 = fcmp one double %RHS, 0.000000e+00  br i1 %ifcond1, label %then2, label %else3then2:                                            ; preds = %else  br label %ifcontelse3:                                            ; preds = %else  br label %ifcontifcont:                                           ; preds = %else3, %then2  %iftmp = phi double [ 1.000000e+00, %then2 ], [ 0.000000e+00, %else3 ]  br label %ifcont4ifcont4:                                          ; preds = %ifcont, %then  %iftmp5 = phi double [ 1.000000e+00, %then ], [ %iftmp, %ifcont ]  ret double %iftmp5}parsed a top level exprdefine double @__anon_expr() {entry:  %binop = call double @"binary|"(double 1.000000e+00, double 0.000000e+00)  ret double %binop}1parsed a top level exprdefine double @__anon_expr() {entry:  %binop = call double @"binary|"(double 0.000000e+00, double 1.000000e+00)  ret double %binop}1parsed a top level exprdefine double @__anon_expr() {entry:  %binop = call double @"binary|"(double 0.000000e+00, double 0.000000e+00)  ret double %binop}0parsed a top level exprdefine double @__anon_expr() {entry:  %binop = call double @"binary|"(double 1.000000e+00, double 1.000000e+00)  ret double %binop}110.MutableVariables本节我们将让Kaleidoscope支持可变变量，首先我们看如下C代码：int G, H;int test(_Bool Condition) {  int X;  if (Condition)    X = G;  else    X = H;  return X;}由于变量X的值依赖于程序的执行路径，会加入一个phinode来选取分支结果。上面代码的LLVMIR如下：@G = weak global i32 0   ; type of @G is i32*@H = weak global i32 0   ; type of @H is i32*define i32 @test(i1 %Condition) {entry:  br i1 %Condition, label %cond_true, label %cond_falsecond_true:  %X.0 = load i32* @G  br label %cond_nextcond_false:  %X.1 = load i32* @H  br label %cond_nextcond_next:  %X.2 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]  ret i32 %X.2}上面的X是符合SSA格式的，但是这里真正的难题是给可变变量赋值时怎么自动添加phinode。我们先了解一些信息，LLVM要求寄存器变量是SSA格式，但却不允许内存对象是SSA格式。比如上面的例子中，G和H就没有版本号。在LLVM中，所有内存访问都是显示的load/store指令，并且不存在取内存地址的操作。注意上面的例子中，即使@G/@H全局变量定义时用的i32,但其类型仍然是i32*,表示在全局数据区存放i32的空间地址。现在假设我们想创建一个类似@G但是在栈上的内存变量，基本指令如下：define i32 @example() {entry:  %X = alloca i32           ; type of %X is i32*.  ...  %tmp = load i32* %X       ; load the stack value %X from the stack.  %tmp2 = add i32 %tmp, 1   ; increment it  store i32 %tmp2, i32* %X  ; store it back  ...于是我们可以把上面使用phinode的LLVMIR改写为使用栈上变量：@G = weak global i32 0   ; type of @G is i32*@H = weak global i32 0   ; type of @H is i32*define i32 @test(i1 %Condition) {entry:  %X = alloca i32           ; type of %X is i32*.  br i1 %Condition, label %cond_true, label %cond_falsecond_true:  %X.0 = load i32* @G  store i32 %X.0, i32* %X   ; Update X  br label %cond_nextcond_false:  %X.1 = load i32* @H  store i32 %X.1, i32* %X   ; Update X  br label %cond_nextcond_next:  %X.2 = load i32* %X       ; Read X  ret i32 %X.2}于是我们找到了一个处理任意可变变量而且不需要创建phinode的办法：每个可变变量在栈上创建变量读取变为loadfromstack变量更新变为storetostack使用栈上地址作为变量地址但是这会带来一个新的问题，因为内存速度不如寄存器，大量使用栈会有性能问题。不过，LLVM优化器有一个pass称为"mem2reg",专门将stack的使用自动地尽可能转为使用phinode,下面为自动优化的结果：@G = weak global i32 0@H = weak global i32 0define i32 @test(i1 %Condition) {entry:  br i1 %Condition, label %cond_true, label %cond_falsecond_true:  %X.0 = load i32* @G  br label %cond_nextcond_false:  %X.1 = load i32* @H  br label %cond_nextcond_next:  %X.01 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]  ret i32 %X.01}mem2reg实现了一个称为"iterateddominancefrontier"的标准算法来自动创建SSA格式。对mem2reg的使用需要注意：mem2reg只能优化栈上变量，不会优化全局变量和堆上变量；mem2reg只优化entryblock中的栈上变量创建,因为在entryblock中就意味着只创建一次；如果对栈上变量有load和store之外的操作,mem2reg也不会优化；mem2reg只能优化基本类型的栈上变量，比如指针，数值和数组。其中数组的大小必须为1.对于结构体和数组等的优化需要另一个称为"sroa"的pass。因为我们后面需要启用mem2reg，我们先把优化器加回来，修改全局定义：std::unique_ptr g_module;std::unique_ptr g_fpm;修改ReCreateModule：void ReCreateModule() {  g_module = std::make_unique("my cool jit", g_llvm_context);  g_module->setDataLayout(g_jit->getTargetMachine().createDataLayout());  g_fpm = std::make_unique(g_module.get());  g_fpm->add(llvm::createInstructionCombiningPass());  g_fpm->add(llvm::createReassociatePass());  g_fpm->add(llvm::createGVNPass());  g_fpm->add(llvm::createCFGSimplificationPass());  g_fpm->doInitialization();}在FunctionAST::CodeGen中执行优化器：g_ir_builder.CreateRet(ret_val);llvm::verifyFunction(*func);g_fpm->run(*func);修改main：int main() {  llvm::InitializeNativeTarget();  llvm::InitializeNativeTargetAsmPrinter();  llvm::InitializeNativeTargetAsmParser();  g_jit.reset(new llvm:rc::KaleidoscopeJIT);  ReCreateModule();  ...}我们有两种类型的变量，分别是函数参数以及for循环的变量，这里我们将这两种变量也修改为使用内存，再让mem2reg进行优化。因为所有的变量都会使用内存，修改g_named_value存储的类型为AllocaInst*：std::map g_named_values;编写一个函数CreateEntryBlockAlloca，简化后续工作，其功能是往函数的EntryBlock的最开始的地方添加分配内存指令：llvm::AllocaInst* CreateEntryBlockAlloca(llvm::Function* func,                                         const std::string& var_name) {  llvm::IRBuilder ir_builder(&(func->getEntryBlock()),                               func->getEntryBlock().begin());  return ir_builder.CreateAlloca(llvm::Type::getDoubleTy(g_llvm_context), 0,                                 var_name.c_str());}修改VariableExprAST::CodeGen,由于我们所有变量都放在内存你上，所以增加load指令：llvm::Value* VariableExprAST::CodeGen() {  llvm::AllocaInst* val = g_named_values.at(name_);  return g_ir_builder.CreateLoad(val, name_.c_str());}接下来我们修改for循环里变量的CodeGen：llvm::Value* ForExprAST::CodeGen() {  // 获取当前function  llvm::Function* func = g_ir_builder.GetInsertBlock()->getParent();  // 将变量创建为栈上变量，不再是phi node  llvm::AllocaInst* var = CreateEntryBlockAlloca(func, var_name_);  // codegen start  llvm::Value* start_val = start_expr_->CodeGen();  // 将初始值赋给var  g_ir_builder.CreateStore(start_val, var);  // 新增一个loop block到当前function  llvm::BasicBlock* loop_block =      llvm::BasicBlock::Create(g_llvm_context, "loop", func);  // 为当前block增加到loop_block的跳转指令  g_ir_builder.CreateBr(loop_block);  // 开始在loop_block内增加指令  g_ir_builder.SetInsertPoint(loop_block);  // 现在我们新增了一个变量var，因为可能会被后面的代码引用，所以要注册到  // g_named_values中，其可能会和函数参数重名，但我们这里为了方便不管  // 这个特殊情况，直接注册到g_named_values中，  g_named_values[var_name_] = var;  // 在loop_block中增加body的指令  body_expr_->CodeGen();  // codegen step_expr  llvm::Value* step_value = step_expr_->CodeGen();  // var = var + step_value  llvm::Value* cur_value = g_ir_builder.CreateLoad(var);  llvm::Value* next_value =      g_ir_builder.CreateFAdd(cur_value, step_value, "nextvar");  g_ir_builder.CreateStore(next_value, var);  // codegen end_expr  llvm::Value* end_value = end_expr_->CodeGen();  // end_value = (end_value != 0.0)  end_value = g_ir_builder.CreateFCmpONE(      end_value, llvm::ConstantFP::get(g_llvm_context, llvm::APFloat(0.0)),      "loopcond");  // 和if/then/else一样，这里的block可能会发生变化，保存当前的block  llvm::BasicBlock* loop_end_block = g_ir_builder.GetInsertBlock();  // 创建循环结束后的block  llvm::BasicBlock* after_block =      llvm::BasicBlock::Create(g_llvm_context, "afterloop", func);  // 根据end_value选择是再来一次loop_block还是进入after_block  g_ir_builder.CreateCondBr(end_value, loop_block, after_block);  // 给after_block增加指令  g_ir_builder.SetInsertPoint(after_block);  // 循环结束，避免被再次引用  g_named_values.erase(var_name_);  // return 0  return llvm::Constant::getNullValue(llvm::Type::getDoubleTy(g_llvm_context));}修改FunctionAST::codegen()使得参数可变：llvm::Value* FunctionAST::CodeGen() {  PrototypeAST& proto = *proto_;  name2proto_ast[proto.name()] = std::move(proto_);  // transfer ownership  llvm::Function* func = GetFunction(proto.name());  if (proto.IsBinaryOp()) {    g_binop_precedence[proto.GetOpName()] = proto.op_precedence();  }  // 创建一个Block并且设置为指令插入位置。  // llvm block用于定义control flow graph, 由于我们暂不实现control flow, 创建  // 一个单独的block即可  llvm::BasicBlock* block =      llvm::BasicBlock::Create(g_llvm_context, "entry", func);  g_ir_builder.SetInsertPoint(block);  // 将函数参数注册到g_named_values中，让VariableExprAST可以codegen  g_named_values.clear();  for (llvm::Value& arg : func->args()) {    // 为每个参数创建一个栈上变量，并赋初值，修改g_named_values使得后面的引用    // 会引用这个栈上变量    llvm::AllocaInst* var = CreateEntryBlockAlloca(func, arg.getName());    g_ir_builder.CreateStore(&arg, var);    g_named_values[arg.getName()] = var;  }  // codegen body然后return  llvm::Value* ret_val = body_->CodeGen();  g_ir_builder.CreateRet(ret_val);  llvm::verifyFunction(*func);  g_fpm->run(*func);  return func;}输入：extern printd(x)def foo(x)    if x add(llvm::createPromoteMemoryToRegisterPass());  g_fpm->add(llvm::createInstructionCombiningPass());  g_fpm->add(llvm::createReassociatePass());再次得到输出：parsed a externdeclare double @printd(double)parsed a function definitiondefine double @foo(double %x) {entry:  %cmptmp = fcmp ult double %x, 3.000000e+00  br i1 %cmptmp, label %ifcont, label %elseelse:                                             ; preds = %entry  %subtmp = fadd double %x, -1.000000e+00  %calltmp = call double @foo(double %subtmp)  %subtmp5 = fadd double %x, -2.000000e+00  %calltmp6 = call double @foo(double %subtmp5)  %addtmp = fadd double %calltmp, %calltmp6  br label %ifcontifcont:                                           ; preds = %entry, %else  %iftmp = phi double [ %addtmp, %else ], [ 1.000000e+00, %entry ]  ret double %iftmp}parsed a top level exprdefine double @__anon_expr() {entry:  br label %looploop:                                             ; preds = %loop, %entry  %i1 = phi double [ %nextvar, %loop ], [ 1.000000e+00, %entry ]  %calltmp = call double @foo(double %i1)  %calltmp2 = call double @printd(double %calltmp)  %nextvar = fadd double %i1, 1.000000e+00  %cmptmp = fcmp ult double %nextvar, 1.000000e+01  br i1 %cmptmp, label %loop, label %afterloopafterloop:                                        ; preds = %loop  ret double 0.000000e+00}1.0000001.0000002.0000003.0000005.0000008.00000013.00000021.00000034.0000000可以看到，栈上变量自动地变为寄存器变量，且phinode自动地被添加。11.完整代码与参考资料完整代码见：https://zhuanlan.zhihu.com/p/336929719参考：https://en.wikipedia.org/wiki/Static_single_assignment_formhttps://llvm.org/docs/tutorial/MyFirstLanguageFrontend/index.html欢迎大家多多交流，共同进步。