note：

1. 需要LLVM3.7及以上版本
2. 你会发现这些教程是自底向上描述的，可能初读有些费解，唯一的方法就是多读几遍。

设置

首先进行一些设置，主要是为所有抽象语法树中添加codegen()函数

/// ExprAST - 所有表达式结点由此继承
/// Base class for all expression nodes.
class ExprAST {
public:
  virtual ~ExprAST() {}
  virtual Value *codegen() = 0;
};

/// NumberExprAST - 数值型表达式，比如“1.0”
/// Expression class for numeric literals like "1.0".
class NumberExprAST : public ExprAST {
  double Val;

public:
  NumberExprAST(double Val) : Val(Val) {}
  virtual Value *codegen();
};
...

codegen()方法会生成所有语法树节点的中间表示，返回一个LLVM的Value对象。

Value对象是LLVM中用来表达SSA值的类型

第二步是添加一个LogErrorV函数用于代码生成过程中的错误信息提示。

Value *LogErrorV(const char *Str) {
  LogError(Str);
  return nullptr;
}

还需要一些LLVM中的数据结构

• TheContext中包含很多LLVM的核心数据结构，比如类型表和常量值表
• Builder对象用来追踪在何处生成代码
• TheModule包含了函数和全局变量，他是LLVM IR用来包含代码的顶级结构，拥有所生成的IR的全部内存
• NamedValues用来追踪在当前作用域中定义了哪些变量，目前来说，它只对函数参数起作用，在生成函数体的代码时，NamedValues中保存的就是所有参数

static std::unique_ptr TheContext;
static std::unique_ptr> Builder(*TheContext);
static std::unique_ptr TheModule;
static std::map NamedValues;

3.3 表达式的代码生成

1. 数值

   在LLVM中，在 LLVM IR 中，数值常量用 ConstantFP 类表示，该类在内部APFloat 中保存数值(APFloat具有保存任意精度的浮点常量的能力)。这段代码基本上只是创建并返回一个 ConstantFP。注意，在 LLVM IR 中，常量都是唯一的，并且是共享的。因此，API使用了foo::get(...)习惯用法，而不是new foo()。或者foo::Create()

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

2. 变量

   如上文所说，在我们目前的设计中变量的代码生成只会在函数的形参中出现，而此时变量都保存在NamedValues这个map中，因此我们只需要根据对应的变量名找到其Value对象即可，在下文中会提及NamedValues表的处理，及这些变量是如何添加到表中的。

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

   ---

3. 二元表达式

   根据前面的Parse过程，二元表达式包含了LHS，RHS和操作符Op。LHS和RHS的类型有自己的codegen()方法，直接调用就可以，重点即是在处理Op的过程。

   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类开始工作。IRBuilder知道在哪里插入新创建的指令，我们所要做的就是指定要创建什么指令(例如使用CreateFAdd) ，要使用哪个操作数(比如代码中的L和R)，并有选择地为生成的指令提供一个名称。

   注意刚刚所说的名称，即代码中的addtmp，subtmp等，只是一个提示，如果出现多个同名，LLVM自动为每个名称添加一个递增的后缀

   LLVM指令有严格的规则约束:例如，添加指令的左操作符和右操作符必须具有相同的类型，并且添加的结果类型必须与操作数类型匹配。因为万花筒中的所有值都是双精度的，这使得add、sub和mul的代码非常简单。

   另一方面，LLVM指定fcmp指令总是返回一个'i1'值(一个1位整数)。问题在于Kaleidoscope希望值是0.0或1.0。为了得到这些语义，我们将fcmp指令与uitofp指令结合起来。该指令将输入的整数作为无符号值处理，从而将其转换为浮点值。相反，如果我们使用sitofp指令，Kaleidoscope的'<'操作符将返回0.0和-1.0，这取决于输入值。

4. 函数调用

   使用 LLVM 生成函数调用的代码非常简单。上面的代码首先在 LLVM 的Module的符号表中查找函数名。回想一下，LLVM Module是容纳我们要JIT的函数的容器。通过赋予每个函数与用户指定的函数相同的名称，我们可以使用 LLVM 符号表为我们解析函数名。

   Value *CallExprAST::codegen() {
     // Look up the name in the global module table.
   	// 在Mudole中查找函数名
     Function *CalleeF = TheModule->getFunction(this->Callee);
     if (!CalleeF)
       return LogErrorV("Unknown function referenced");
   
     // If argument mismatch error.
   	// 如果参数对应不上
     if (CalleeF->arg_size() != this->Args.size())
       return LogErrorV("Incorrect # arguments passed");
   
     std::vector ArgsV;
     for (unsigned i = 0, e = this->Args.size(); i != e; ++i) {
   		// 这里的Args[i]的类型基类是ExprAST
       ArgsV.push_back(this->Args[i]->codegen());
       if (!ArgsV.back())
         return nullptr;
     }
   
     return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
   }
   

5. END

   到目前为止，我们在《万花筒》中对四个基本表达式的处理就到此结束了。请随意进入并添加更多内容。例如，通过浏览LLVM语言参考，你会发现其他几个有趣的指令，它们非常容易插入我们的基本框架。

函数代码的生成

原型和函数的代码生成必须处理大量的细节，这使得它们的代码没有上文那些表达式的代码生成那么优美。首先，让我们讨论一下原型ProtoType的代码生成:它们既用于函数体，也用于外部函数声明。代码的开头是:

Function *PrototypeAST::codegen() {
  // Make the function type:  double(double,double) etc.

	// hint: 这里的this->Args的类型是vector
  std::vector Doubles(this->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函数是有意义的。

上面这段代码一共有3行：

1. 第一行：

   因为Kaleidoscope中的所有函数参数都是double类型的，所以第一行创建了一个大小为N的LLVM double类型的向量，这表示所有参数的类型。

2. 第二行

   然后，它使用Functiontype::get方法创建一个函数类型，该函数类型以N个double类型作为参数类型，一个double作为返回值类型。false参数表示该函数的参数不可变长。

   注意，LLVM 中的类型是uniqued的，就像常量一样，所以不需要new一个类型，而是get。

3. 第三行

   上面的最后一行实际上创建了与Prototype对应的一个IR Function。

   IR Function指示了要使用的类型（double→返回值 (N个Double→参数)）、链接和函数名称，以及要插入到哪个模块。

   ”Function::ExternalLinkage”意味着该函数可以在当前模块之外定义，并且/或者可以由模块之外的函数调用。

   传入的 Name 是用户指定的名称: 因为指定了“TheModule”，所以这个名称注册在“ TheModule”的符号表中。

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

return F;

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

现在，我们有了一个没有主体的函数原型。这就是LLVM IR表示函数声明的方式。

对于Kaleidoscope中的extern语句而言，到这一步就可以完全处理掉一个extern语句了。但是，对于自定义的有主体的函数，我们需还要codegen并附加一个函数体。

Function *FunctionAST::codegen() {
    // First, check for an existing function from a previous 'extern' declaration.
	// 前文中我们通过：Function::Create(..., Name, TheModule.get())将Name添加到Module中了
  Function *TheFunction = TheModule->getFunction(this->Proto->getName());

  if (!TheFunction)
    TheFunction = this->Proto->codegen();

  if (!TheFunction)
    return nullptr;

  if (!TheFunction->empty())
    return (Function*)LogErrorV("Function cannot be redefined.");

对于函数定义，我们首先在模块的符号表中查找这个函数的现有版本，以防已经使用'extern'语句创建了一个函数。如果Module::getFunction返回null，那么之前的版本不存在，所以我们将从原型中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”,在接之后的运行过程中我们会看到这个entry的位置)，并将其插入到TheFunction中。

然后，第二行告诉builder，新的指令应该插入到新的基本块的末尾。

LLVM 中的基本块是定义控制流程图的函数的一个重要部分。因为我们没有任何控制流，所以我们的函数此时只包含一个块。我们将在第5章解决这个问题:)。

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

// 这里的Body是一个expression，递归调用它自身的codegen()方法
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()方法。如果没有错误发生，则发出代码以计算条目块中的表达式，并返回计算得到的值。假设没有错误，然后我们创建一个 LLVM ret instruction，完成这个函数。构建函数后，我们调用由 LLVM 提供的 verifyFunction。这个函数对生成的代码进行各种一致性检查，以确定我们的编译器是否一切正常。使用这一点很重要: 它可以捕捉到很多 bug。一旦完成并验证了函数，我们就返回它。

这里剩下的唯一部分是处理错误情况。为了简单起见，我们仅仅通过删除 eraseFromParent 方法生成的函数来处理这个问题。这允许用户重新定义他们之前输入的错误的函数: 如果我们没有删除它，它将与一个主体一起存在于符号表中，防止将来重新定义。

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