[2] 使用 LLVM 实现一门简单的语言

原创

谛听

修改于 2023-06-13 08:04:39

2.3K0

修改于 2023-06-13 08:04:39

文章被收录于专栏：随意记录

5 生成 LLVM IR

IR 指中间表达方式，介于高级语言和汇编语言之间。与高级语言相比，丢弃了语法和语义特征，比如作用域、面向对象等；与汇编语言相比，不会有硬件相关的细节，比如目标机器架构、操作系统等。

先 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"

// 记录一些全局数据，比如各模块中用到的类型和常量
static std::unique_ptr<LLVMContext> g_llvm_context;

// 一个文件就是一个模块
// 模块中包含函数、全局变量
static std::unique_ptr<Module> g_llvm_module;

// 用于创建 LLVM 指令
static std::unique_ptr<IRBuilder<>> g_ir_builder;

// 用于记录函数的变量参数
static std::map<std::string, Value *> g_named_values;

5.1 添加 Codegen()

在每个 AST 类中添加 Codegen()，用于生成 LLVM IR。

/// 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();
};
...

也可以通过 visitor 模式生成 LLVM IR，本文并非工程最佳实践，添加 Codegen() 会更简单一些。Codegen() 会返回 LLVM Value，Value 用来表示 SSA（Static Single Assignment）值，一个变量只能被定义一次，然后多次使用，便于代码优化。

5.2 实现 Codegen()

实现 NumberExprAST 的 Codegen()：

Value *NumberExprAST::Codegen() {
  return ConstantFP::get(g_llvm_context, APFloat(val_));
}

在 LLVM IR 中，所有常量都是唯一且共享的，所以使用 get 而不是 new/create。

实现 VariableExprAST 的 Codegen()：

Value *VariableExprAST::Codegen() {
  // Look this variable up in the function.
  Value *v = g_named_values[name_];
  if (!v)
    LogErrorV("Unknown variable name");
  return v;
}

目前 g_named_values 中仅保存函数参数，在生成的函数的 IR 时，会生成参数的 IR，并存放到 g_named_values 中，所以这里仅仅是获取。后面 g_named_values 中会保存循环中的变量和本地变量。

实现 BinaryExprAST 的 Codegen()：

Value *BinaryExprAST::Codegen() {
  Value *l = lhs_->Codegen();
  Value *r = rhs_->Codegen();
  if (!l || !r)
    return nullptr;

  switch (opcode_) {
  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::GetDoubleTypepe(*g_llvm_context),
                                "booltmp");
  default:
    return LogErrorV("invalid binary operator");
  }
}

递归地生成左边表达式是 IR 和右边表达式的 IR，然后计算结果。Builder.CreateFAdd() 用来插入加法的 IR 指令，第三个参数表示名称，使得生成的 IR 便于阅读。

LLVM 指令要求比较严格，比如，加法指令的 L 和 R 的数据类型必须相同，结果类型必须和操作数类型匹配。

另外，CreateFCmpULT() 返回 bool 型，但 Kaleidoscope 中的数据类型都为 float64，所以需要通过 CreateUIToFP() 转换一下。

实现 CallExprAST 的 Codegen()：

Value *CallExprAST::Codegen() {
  // Look up the name in the global module table.
  // LLVM Module 中存放了所有的函数
  Function *callee = g_llvm_module->getFunction(callee_);
  if (!callee)
    return LogErrorV("Unknown function referenced");

  // If argument mismatch error.
  if (callee->arg_size() != args.size())
    return LogErrorV("Incorrect # arguments passed");

  std::vector<Value *> args_v;
  for (unsigned i = 0, e = args_.size(); i != e; ++i) {
    args_v.push_back(args_[i]->Codegen());
    if (!args_v.back())
      return nullptr;
  }

  return g_ir_builder.CreateCall(callee, args_v, "calltmp");
}

实现 PrototypeAST 的 Codegen()：

// 返回的是 Function* 而非 Value*
Function *PrototypeAST::Codegen() {
  // Make the function type:  double(double, double) etc.
  std::vector<Type*> doubles(args_.size(),
                             Type::GetDoubleTypepe(*g_llvm_context));
                             
  // 在 LLVM 中，Types 是唯一的，所以使用 get 而非 new
  // false 表示参数个数是固定的
  FunctionType *f_type =
    FunctionType::get(Type::GetDoubleTypepe(*g_llvm_context), doubles, false);

	// 生成 IR
	// 第 2 个参数表明函数可能定义在当前模块外，或者本函数可被其它模块调用
	// 第 4 个参数表明了要插入到哪个模块
  Function *fun =
    Function::Create(f_type, Function::ExternalLinkage, name_, g_llvm_module.get());
    
  // Set names for all arguments.
  // 本步骤不是必须的，可以使得生成的 IR 更具可读性
  // 也使得后续的代码可以直接通过参数名称引用参数，而避免遍历 PrototypeAST
  unsigned idx = 0;
  for (auto &arg : fun->args())
    arg.setName(args[Idx++]);

  return fun;
}

实现 FunctionAST 的 Codegen()：会加上函数体

Function *FunctionAST::Codegen() {
  // First, check for an existing function from a previous 'extern' declaration.
  // 可能会有 extern 声明
  Function *function = g_llvm_module->getFunction(proto_->name());

  if (!function)
    function = proto_->Codegen();

  if (!function)
    return nullptr;

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

  // Create a new basic block to start insertion into.
  // 创建一个名称为 entry 的基本块，会被插入到 function 
  // llvm block 用于定义control flow graph, 但我们暂不实现 control flow，创建一个单独的 block 即可
  BasicBlock *bb = BasicBlock::Create(g_llvm_context, "entry", function);
  
  // 设置指令插入点，即后面的指令会被插入到 bb
  Builder.SetInsertPoint(bb);

  // Record the function arguments in the g_named_values map.
  // g_named_values 会被 VariableExprAST 访问
  g_named_values.clear();
  for (auto &arg : function->args())
    g_named_values[arg.getName()] = &arg;

  // 会将计算表达式的 IR 发送到 entry block 中，并返回计算结果
  if (Value *ret_val = body_->Codegen()) {
    // Finish off the function.
    // 利用计算结果创建返回值
    g_ir_builder.CreateRet(ret_val);

    // Validate the generated code, checking for consistency.
    verifyFunction(*function);

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

该代码目前还存在一个问题，如果 FunctionAST::Codegen() 发现了一个已经存在的 IR，并不会检查其签名。

5.3 运行

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

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
}

6 优化

IRBuilder 生成的 IR 如下：

ready> def test(x) 1+2+x;
Read function definition:
define double @test(double %x) {
entry:
        %addtmp = fadd double 3.000000e+00, %x
        ret double %addtmp
}

可以看到，自动进行了常量折叠。

但是如果想对如下 IR 优化，还需要引入 LLVM 中的 pass。

ready> def test(x) (1+2+x)*(x+(1+2));
ready> Read function definition:
define double @test(double %x) {
entry:
        %addtmp = fadd double 3.000000e+00, %x
        %addtmp1 = fadd double %x, 3.000000e+00
        %multmp = fmul double %addtmp, %addtmp1
        ret double %multmp
}

可以选择是否启用 pass，并调整 pass 的顺序。

LLVM 既提供针对整个 Module 的 pass，也提供针对单个函数的 pass。

本文中，对每个函数单独优化，初始化 pass 管理器：

static std::unique_ptr<legacy::FunctionPassManager> g_fpm;

void InitializeModuleAndPassManager(void) {
  // Open a new module.
  g_llvm_module = std::make_unique<Module>("my cool jit", g_llvm_context);

  // Create a new pass manager attached to it.
  g_fpm = std::make_unique<legacy::FunctionPassManager>(g_llvm_module.get());

  // Do simple "peephole" optimizations and bit-twiddling optzns.
  g_fpm->add(createInstructionCombiningPass());
  // Reassociate expressions.
  g_fpm->add(createReassociatePass());
  // Eliminate Common SubExpressions.
  g_fpm->add(createGVNPass());
  // Simplify the control flow graph (deleting unreachable blocks, etc).
  g_fpm->add(createCFGSimplificationPass());

  g_fpm->doInitialization();
}

在 FunctionAST::Codegen() 中添加如下代码：

if (Value *ret_val = body_->Codegen()) {
  // Finish off the function.
  g_ir_builder.CreateRet(ret_val);

  // Validate the generated code, checking for consistency.
  verifyFunction(*function);

  // Optimize the function.
  g_fpm->run(*function);

  return function;
}

测试并查看效果：

ready> def test(x) (1+2+x)*(x+(1+2));
ready> Read function definition:
define double @test(double %x) {
entry:
        %addtmp = fadd double %x, 3.000000e+00
        %multmp = fmul double %addtmp, %addtmp
        ret double %multmp
}

7 添加 JIT

提前编译（AOT）：编译成可执行文件后，再执行。

即时编译（JIT）：在需要运行某段代码的时候，再编译。Java、JavaScript 等语言都是通过即时编译提高性能的

JIT 原理：动态申请内存，加载目标代码到内存，并赋予内存可执行权限。

定义 JIT 的全局变量，并通过 InitializeNativeTarget* 函数初始化环境。

#include "KaleidoscopeJIT.h"

static std::unique_ptr<KaleidoscopeJIT> g_jit;
...
int main() {
  InitializeNativeTarget();
  InitializeNativeTargetAsmPrinter();
  InitializeNativeTargetAsmParser();
	g_jit = std::make_unique<KaleidoscopeJIT>();
  ...
  return 0;
}

其中，KaleidoscopeJIT.h 是从 LLVM 的源码 llvm-src/examples/Kaleidoscope/include/KaleidoscopeJIT.h 中拷贝过来的。

为 JIT 设置数据布局：

void InitializeModuleAndPassManager(void) {
  // Open a new module.
  g_llvm_module = std::make_unique<Module>("my cool jit", g_llvm_context);
  g_llvm_module->setDataLayout(g_jit->getTargetMachine().createDataLayout());

  // Create a new pass manager attached to it.
  g_fpm = std::make_unique<legacy::FunctionPassManager>(g_llvm_module.get());
  ...

修改顶层解析函数：

static void HandleTopLevelExpression() {
  // Evaluate a top-level expression into an anonymous function.
  if (auto fn_ast = ParseTopLevelExpr()) {
    if (fn_ast->Codegen()) {
    
			// 顶层函数 Codegen 后，将包含顶层函数的模块添加到 JIT
      // addModule 会触发模块中所有函数的 Codegen，并返回一个句柄 handle
      // 后续可以通过 handle 删除该模块
      auto handle = g_jit->addModule(std::move(g_llvm_module));
     
      // 一旦模块被添加到JIT中，就不能再对其进行修改
      // 因此我们还通过调用InitializeModuleAndPassManager（）打开一个新模块来保存后续代码。
      InitializeModuleAndPassManager();

			// 通过顶层函数的名称搜索其符号
      auto expr_symbol = g_jit->findSymbol("__anon_expr");
      assert(expr_symbol && "Function not found");

      // 获取符号地址，强制转换为函数指针 (double (*)())（无参数，并返回一个 double）
      double (*fp)() = (double (*)())(intptr_t)expr_symbol.getAddress();
      fprintf(stderr, "Evaluated to %f\n", fp());

      // Delete the anonymous expression module from the JIT.
      g_jit->removeModule(handle);
    }

运行：

ready> def testfunc(x y) x + y*2;
Read function definition:
define double @testfunc(double %x, double %y) {
entry:
  %multmp = fmul double %y, 2.000000e+00
  %addtmp = fadd double %multmp, %x
  ret double %addtmp
}

ready> testfunc(4, 10);
Read top-level expression:
define double @1() {
entry:
  %calltmp = call double @testfunc(double 4.000000e+00, double 1.000000e+01)
  ret double %calltmp
}

Evaluated to 24.000000

ready> testfunc(5, 10);
ready> LLVM ERROR: Program used external function 'testfunc' which could not be resolved!

可以看到存在一个问题，所有函数都在同一个模块中，当模块被删除并释放后，函数定义也随之被删除。

最简单的解决方式是将顶层函数和其它函数定义分别放在不同的模块中，这样即时顶层函数所在模块被删掉，也不会影响到其它函数。

我们也可以更进一步，将每个函数都放在自己的模块中，这样函数就可以被多次添加到 JIT 中了。当我们在 JIT 中查找函数符号时，总是会返回被最新定义的：

ready> def foo(x) x + 1;
Read function definition:
define double @foo(double %x) {
entry:
  %addtmp = fadd double %x, 1.000000e+00
  ret double %addtmp
}

ready> foo(2);
Evaluated to 3.000000

ready> def foo(x) x + 2;
define double @foo(double %x) {
entry:
  %addtmp = fadd double %x, 2.000000e+00
  ret double %addtmp
}

ready> foo(2);
Evaluated to 4.000000

在每个新打开的模块中重新生成函数定义：

static std::unique_ptr<KaleidoscopeJIT> g_jit;
// 存放函数的最新定义
static std::map<std::string, std::unique_ptr<PrototypeAST>> g_function_protos;
...

Function *GetFunction(std::string Name) {
  // 首先，在模块中搜寻函数定义
  if (auto *f = g_llvm_module->getFunction(Name))
    return f;

  // 如果没有找到，就根据 g_function_protos 新生成定义
  auto fn = g_function_protos.find(Name);
  if (fn != g_function_protos.end())
    return fn->second->Codegen();

  // If no existing prototype exists, return null.
  return nullptr;
}

...

Value *CallExprAST::Codegen() {
  // Look up the name in the global module table.
  // 替换 g_llvm_module->getFunction()
  Function *callee = GetFunction(Callee);

...

Function *FunctionAST::Codegen() {
  // Transfer ownership of the prototype to the g_function_protos map, but keep a
  // reference to it for use below.
  auto &proto = *proto_;
  // 先更新 g_function_protos，然后再调用 getFunction
  g_function_protos[proto_->name()] = std::move(proto_);
  Function *function = GetFunction(proto.name());
  if (!function)
    return nullptr;

还需要更新 HandleDefinition 和 HandleExtern：

static void HandleDefinition() {
  if (auto fn_ast = ParseDefinition()) {
    if (auto *fn_ir = fn_ast->Codegen()) {
      fprintf(stderr, "Read function definition:");
      fn_ir->print(errs());
      fprintf(stderr, "\n");
      // 将最新定义的函数添加到 JIT
      g_jit->addModule(std::move(g_llvm_module));
      // 打开新模块
      InitializeModuleAndPassManager();
    }
  } else {
    // Skip token for error recovery.
     NextToken();
  }
}

static void HandleExtern() {
  if (auto proto_ast = ParseExtern()) {
    if (auto *fn_ir = proto_ast->Codegen()) {
      fprintf(stderr, "Read extern: ");
      fn_ir->print(errs());
      fprintf(stderr, "\n");
      // 更新 g_function_protos
      g_function_protos[proto_ast->name()] = std::move(proto_ast);
    }
  } else {
    // Skip token for error recovery.
    NextToken();
  }
}

再次运行：

ready> def foo(x) x + 1;
ready> foo(2);
Evaluated to 3.000000

ready> def foo(x) x + 2;
ready> foo(2);
Evaluated to 4.000000

8 控制流

8.1 支持 If/Then/Else

在 lexer 中支持新的 token：

// control
TOKEN_IF = -6,
TOKEN_then_ = -7,
TOKEN_else_ = -8,

识别新 token：

...
if (g_identifier_str == "if")
	return TOKEN_IF;
if (g_identifier_str == "then")
	return TOKEN_THEN;
if (g_identifier_str == "else")
	return TOKEN_ELSE;

添加新的 AST 节点：

/// IfExprAST - Expression class for if/then/else.
class IfExprAST : public ExprAST {
  std::unique_ptr<ExprAST> cond_, then_, else_;

public:
  IfExprAST(std::unique_ptr<ExprAST> cond, std::unique_ptr<ExprAST> then,
            std::unique_ptr<ExprAST> else)
    : cond_(std::move(cond)), then_(std::move(then)), else_(std::move(else)) {}

  Value *Codegen() override;
};

定义新的解析函数：

/// ifexpr ::= 'if' expression 'then' expression 'else' expression
static std::unique_ptr<ExprAST> ParseIfExpr() {
  NextToken();  // eat the if.

  // condition.
  auto cond = ParseExpression();
  if (!cond)
    return nullptr;

  if (g_cur_token != TOKEN_THEN)
    return LogError("expected then");
  NextToken(); // eat the then

  auto then_expr = ParseExpression();
  if (!then_expr)
    return nullptr;

  if (g_cur_token != TOKEN_ELSE)
    return LogError("expected else");

  NextToken();

  auto else_expr = ParseExpression();
  if (!else)
    return nullptr;

  return std::make_unique<IfExprAST>(std::move(cond), std::move(then_expr),
                                     std::move(else_expr));
}

修改基本表达式的解析：

static std::unique_ptr<ExprAST> ParsePrimary() {
  switch (g_cur_token) {
  default:
    return LogError("unknown token when expecting an expression");
  case TOKEN_IDENTIFIER:
    return ParseIdentifierExpr();
  case TOKEN_NUMBER:
    return ParseNumberExpr();
  case '(':
    return ParseParenExpr();
  case TOKEN_IF:
    return ParseIfExpr();
  }
}

生成 IR：

Value *IfExprAST::Codegen() {
  Value *cond_v = cond_->Codegen();
  if (!cond_v)
    return nullptr;

  // Convert condition to a bool by comparing non-equal to 0.0.
  // 创建fcmp one指令, cond_value = (cond_value != 0.0)
  cond_v = g_ir_builder.CreateFCmpONE(
      cond_v, ConstantFP::get(g_llvm_context, APFloat(0.0)), "ifcond");
      
  // 获取要插入指令的函数
  Function *function = g_ir_builder.GetInsertBlock()->getParent();

  // Create blocks for the then and else cases.  Insert the 'then' block at the
  // end of the function.
  // 创建 3 个 block，并将 then block 插入到函数中
  // 另外两个 block 还没有被插入到函数中，因为后面要先为 then_bb 生成指令
  BasicBlock *then_bb = BasicBlock::Create(*g_llvm_context, "then", function);
  BasicBlock *else_bb = BasicBlock::Create(*g_llvm_context, "else");
  BasicBlock *merge_bb = BasicBlock::Create(*g_llvm_context, "ifcond");

	// 创建条件跳转指令，cond_v 是 1 的时候跳转到 then_bb，0 的时候跳转到 else_bb
  Builder.CreateCondBr(cond_v, then_bb, else_bb);
  
  // ---------------------- Emit then value.
  // 将指令插入点移到 then_bb
  g_ir_builder.SetInsertPoint(then_bb);

  Value *then_v = then_->Codegen();
  if (!then_v)
    return nullptr;

	// 为了结束 then_bb，创建了一个到 merge_bb 的无条件跳转指令
  g_ir_builder.CreateBr(merge_bb);
  
  // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
  // 更新 ThenBB，因为 ThenBB 可能已经改变了 Builder 要插入指令的 block
  // 比如内部可能会有 if/then/else，而我们需要获取最终有结果的 block
  then_bb = g_ir_builder.GetInsertBlock();
  
  // ----------------------- Emit else block.
  // 将 ElseBB 添加到函数中
  function->getBasicBlockList().push_back(else_bb);
  g_ir_builder.SetInsertPoint(else_bb);

  Value *else_v = else_->Codegen();
  if (!else_v)
    return nullptr;

  g_ir_builder.CreateBr(MergeBB);
  // Codegen of 'else_' can change the current block, update else_bb for the PHI.
  else_bb = g_ir_builder.GetInsertBlock();
  
  // ------------------------ Emit merge block.
  function->getBasicBlockList().push_back(merge_bb);
  g_ir_builder.SetInsertPoint(merge_bb);
  
  // 创建 PHI 指令：浮点型，2 个候选值
  PHINode *pn =
    Builder.CreatePHI(Type::GetDoubleTypepe(g_llvm_context), 2, "iftmp");

  pn->addIncoming(then_v, then_bb);  // 如果是来自 then_bb 的跳转，采用 then_v
  pn->addIncoming(else_v, else_bb);  // 如果是来自 else_bb 的跳转，采用 else_v
  return pn;
}

8.2 支持 for 循环表达式

接下来支持 for 表达式：

extern putchard(char);
def printstar(n)
  for i = 1, i < n, 1.0 in
    putchard(42);  # ascii 42 = '*'

# print 100 '*' characters
printstar(100);

扩展 lexer：

... in enum Token ...
TOKEN_FOR = -9,
TOKEN_IN = -10,

... in GetToken ...
if (g_identifier_str == "for")
	return TOKEN_FOR;
if (g_identifier_str == "in")
	return TOKEN_IN;
return TOKEN_IDENTIFIER;

扩展 AST：

/// ForExprAST - Expression class for for/in.
class ForExprAST : public ExprAST {
  std::string var_name_;
  std::unique_ptr<ExprAST> start_, end_, step_, body_;

public:
  ForExprAST(const std::string &var_name, std::unique_ptr<ExprAST> start,
             std::unique_ptr<ExprAST> end, std::unique_ptr<ExprAST> step,
             std::unique_ptr<ExprAST> body;)
      : var_name_(var_name), start_(std::move(start)), end_(std::move(end)),
        step_(std::move(step)), body_(std::move(body)) {}

  Value *Codegen() override;
};

扩展 Parser：

/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
static std::unique_ptr<ExprAST> ParseForExpr() {
  NextToken();  // eat the for.

  if (g_cur_token != TOKEN_IDENTIFIER)
    return LogError("expected identifier after for");

  std::string identifier_name = g_identifier_str;
  NextToken(); // eat identifier.

  if (g_cur_token != '=')
    return LogError("expected '=' after for");
  NextToken(); // eat '='.

  auto start = ParseExpression();
  if (!start)
    return nullptr;
  if (g_cur_token != ',')
    return LogError("expected ',' after for start_ value");
  NextToken();

  auto end = ParseExpression();
  if (!end)
    return nullptr;

  // The step value is optional.
  std::unique_ptr<ExprAST> step;
  if (g_cur_token == ',') {
    NextToken();
    step = ParseExpression();
    if (!step)
      return nullptr;
  }

  if (g_cur_token != TOKEN_IN)
    return LogError("expected 'in' after for");
  NextToken(); // eat 'in'.

  auto body = ParseExpression();
  if (!body)
    return nullptr;

  return std::make_unique<ForExprAST>(identifier_name, std::move(start), std::move(end),
                                      std::move(step), std::move(body));
}

再次更新对基本表达式的解析：

static std::unique_ptr<ExprAST> ParsePrimary() {
  switch (g_cur_token) {
  ...
  case TOKEN_FOR:
    return ParseForExpr();
  }
}

生成 IR：

// Output for-loop as:
//   var = alloca double
//   ...
//   start = startexpr
//   store start -> var
//   goto loop
// loop:
//   ...
//   bodyexpr
//   ...
// loopend:
//   step = stepexpr
//   endcond = endexpr
//
//   curvar = load var
//   nextvar = curvar + step
//   store nextvar -> var
//   br endcond, loop, endloop
// outloop:
Value *ForExprAST::Codegen() {
  // Emit the start code first, without 'variable' in scope.
  Value *start_val = start_->Codegen();
  if (!start_val)
    return nullptr;
    
  // Make the new basic block for the loop header, inserting after current
  // block.
  Function *function = g_ir_builder->GetInsertBlock()->getParent();
  // 获得当前 block
  BasicBlock *preheader_bb = g_ir_builder->GetInsertBlock();
  // 新增 loop_bb
  BasicBlock *loop_bb =
      BasicBlock::Create(g_llvm_context, "loop", function);

  // Insert an explicit fall through from the current block to the LoopBB.
  // 添加从当前 block 到 loop_bb 的跳转指令
  g_ir_builder.CreateBr(loop_bb);
  
  // Start insertion in loop_bb.
  // 开始在 loop_bb 内增加指令
  g_ir_builder.SetInsertPoint(loop_bb);

  // Start the PHI node with an entry for Start.
  // 新增 PHI 指令
  PHINode *variable = Builder.CreatePHI(Type::GetDoubleTypepe(g_llvm_context),
                                        2, var_name_.c_str())
  // 如果是来自 preheader_bb 的跳转，则取 start_val 的值
  variable->addIncoming(start_val, preheader_bb); 
  
  // Within the loop, the variable is defined equal to the PHI node.  If it
  // shadows an existing variable, we have to restore it, so save it now.
  // 防止 loop 中的变量覆盖已有的同名变量
  Value *old_val = g_named_values[var_name_];
  g_named_values[var_name_] = variable;

  // Emit the body of the loop.  
  // This, like any other expr, can change the
  // current BB.  Note that we ignore the value computed by the body, but don't
  // allow an error.
  // body 可能会用到刚刚更新到 g_named_values 中的 loop 变量
  if (!body_->Codegen())
    return nullptr;
    
  // Emit the step value.
  Value *step_val = nullptr;
  if (step_) {
    step_val = step_->Codegen();
    if (!step_val)
      return nullptr;
  } else {
    // If not specified, use 1.0.
    step_val = ConstantFP::get(g_llvm_context, APFloat(1.0));
  }

	// 生成 body 后，需要计算下次循环中的变量值
  Value *next_var = g_ir_builder.CreateFAdd(variable, step_val, "nextvar");
  
  // Compute the end condition.
  Value *end_cond = end_->Codegen();
  if (!end_ond)
    return nullptr;

  // Convert condition to a bool by comparing non-equal to 0.0.
  end_cond = g_ir_builder.CreateFCmpONE(
      end_cond, ConstantFP::get(g_llvm_context, APFloat(0.0)), "loopcond");

  // Create the "after loop" block and insert it.
  BasicBlock *loop_end_bb = g_ir_builder.GetInsertBlock();
  BasicBlock *after_bb =
      BasicBlock::Create(g_llvm_context, "afterloop", function);

  // Insert the conditional branch into the end of loop_end_bb.
  // 创建条件跳转指令，决定是否要退出循环
  g_ir_builder.CreateCondBr(end_cond, loop_bb, after_bb);

  // Any new code will be inserted in after_bb.
  // 后续的指令会插入到 after_bb 中
  g_ir_builder.SetInsertPoint(after_bb);
  
  // Add a new entry to the PHI node for the backedge.
  // 如果是再次循环，则取 next_var 值
  variable->addIncoming(next_var, loop_end_bb);

  // Restore the unshadowed variable.
  // loop 中的变量只能在 loop 作用域内使用
  if (old_val)
    g_g_named_values[var_name_] = old_val;
  else
    g_named_values.erase(var_name_);

  // for expr always returns 0.0.
  return Constant::getNullValue(Type::GetDoubleTypepe(g_llvm_context));
}

可以看到，loop 中也用到了 PHI 指令，如果是第一次循环，则循环变量取 StartVal 值；否则，取 NextVal 值。

编译运行：

# Compile
clang++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core orcjit native` -O3 -o toy
# Run
./toy

9 用户自定义运算符

我们将允许用户新增不存在的运算符，比如：

# 定义一元运算符 !
def unary!(v)
  if v then
    0
  else
    1;

# 定义二元运算符 >，优先级为 10
def binary> 10 (LHS RHS)
  RHS < LHS;

# Binary "logical or", (note that it does not "short circuit")
# 定义二元运算符 |，优先级为 5
def binary| 5 (LHS RHS)
  if LHS then
    1
  else if RHS then
    1
  else
    0;

# Define = with slightly lower precedence than relationals.
# 定义二元运算符 =，优先级为 9
def binary= 9 (LHS RHS)
  !(LHS < RHS | LHS > RHS);

9.1 自定义二元运算符

扩展 Lexer：

enum Token {
  ...
  // operators
  TOKEN_BINARY = -11,
  TOKEN_UNARY = -12,
};
...
static int GetToken() {
...
  if (g_identifier_str == "binary")
  	return TOKEN_BINARY;
  if (g_identifier_str == "unary")
  	return TOKEN_UNARY;
  return TOKEN_IDENTIFIER;
}

新增的二元操作符会被视为一个函数，所以不需要新增 AST 节点，只需扩展 PrototypeAST 节点即可：

/// PrototypeAST - This class represents the "prototype" for a function,
/// which captures its argument names as well as if it is an operator.
class PrototypeAST {
  std::string name_;
  std::vector<std::string> args_;
  bool is_operator_;  // 是否为操作符
  unsigned precedence_;  // 二元操作符的优先级

public:
  PrototypeAST(const std::string &name,
               std::vector<std::string> args_, bool is_operator = false,
               unsigned prec = 0)
      : name_(name), args_(std::move(args)), is_operator_(is_operator),
        precedence_(prec) {}

  Function *Codegen();
  const std::string &name() const { return name_; }

  bool IsUnaryOpcode() const { return is_operator_ && args_.size() == 1; }
  bool IsBinaryOpcode() const { return is_operator_ && args_.size() == 2; }

  char operator_name() const {
    assert(IsUnaryOpcode() || IsBinaryOpcode());
    return name_[name_.size() - 1];
  }
 
  unsigned binary_precedence() const { return precedence_; }
};

修改 Parser：

/// prototype
///   ::= id '(' id* ')'
///   ::= binary LETTER number? (id, id)
static std::unique_ptr<PrototypeAST> ParsePrototype() {
  std::string fn_name;

  unsigned kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
  unsigned binary_precedence = 30;

  switch (g_cur_token) {
  default:
    return LogErrorP("Expected function name in prototype");
  case TOKEN_IDENTIFIER:
    fn_name = g_identifier_str;
    kind = 0;
    NextToken();
    break;
  // 解析二元操作符名称和优先级
  case TOKEN_BINARY:
    NextToken();
    if (!isascii(g_cur_token))
      return LogErrorP("Expected binary operator");
    fn_name = "binary";
    fn_name += (char)g_cur_token;
    kind = 2;
    NextToken();
    
    // Read the precedence if present.
    if (g_cur_token == TOKEN_NUMBER) {
      if (g_num_val < 1 || g_num_val > 100)
        return LogErrorP("Invalid precedence: must be 1..100");
      binary_precedence = (unsigned)g_num_val;
      NextToken();
    }
    break;
  }

  if (g_cur_token != '(')
    return LogErrorP("Expected '(' in prototype");

  std::vector<std::string> arg_names;
  while (NextToken() == TOKEN_IDENTIFIER)
    arg_names.push_back(g_identifier_str);
  if (g_cur_token != ')')
    return LogErrorP("Expected ')' in proto_type");

  // success.
  NextToken();  // eat ')'.

  // Verify right number of names for operator.
  if (kind && arg_names.size() != kind)
    return LogErrorP("Invalid number of oprand_s for operator");

  return std::make_unique<PrototypeAST>(fn_name, arg_names, kind != 0,
                                        binary_precedence);
}

生成 IR：

Value *BinaryExprAST::Codegen() {
  Value *l = lhs_->Codegen();
  Value *r = rhs_->Codegen();
  if (!l || !r)
    return nullptr;

  switch (opcode_) {
  case '+':
    return g_ir_builder->CreateFAdd(l, r, "addtmp");
  case '-':
    return g_ir_builder->CreateFSub(l, r, "subtmp");
  case '*':
    return g_ir_builder->CreateFMul(l, r, "multmp");
  case '<':
    l = g_ir_builder->CreateFCmpULT(l, r, "cmptmp");
    // Convert bool 0/1 to double 0.0 or 1.0
    return g_ir_builder->CreateUIToFP(l, Type::GetDoubleTypepe(*g_llvm_context), "booltmp");
  default:
    break;
  }

  // If it wasn't a builtin binary operator, it must be a user defined one. Emit
  // a call to it.
  Function *f = GetFunction(std::string("binary") + opcode_);
  assert(f && "binary operator not found!");

  Value *opcodes[] = {l, r};
  return g_ir_builder->CreateCall(f, opcodes, "binopcode");
}

顶层函数的 IR：

Function *FunctionAST::Codegen() {
  // Transfer ownership of the prototype to the g_function_protos map, but keep a
  // reference to it for use below.
  auto &proto = *proto_;
  g_function_protos[proto_->name()] = std::move(proto_);
  Function *function = GetFunction(proto.name());
  if (!function)
    return nullptr;

  // If this is an operator, install it.
  if (P.IsBinaryOp())
  	// 注册优先级，为后续 Codegen 作准备
    g_binopcode_precedence[proto.operator_name()] = proto.binary_precedence();

  // Create a new basic block to start insertion into.
  BasicBlock *bb = BasicBlock::Create(*g_llvm_context, "entry", function);
  ...

9.2 自定义一元运算符

支持自定义二元操作符只是扩展了已有框架，而支持一元操作符会更具挑战。

添加 AST 节点：

/// UnaryExprAST - Expression class for a unary operator.
class UnaryExprAST : public ExprAST {
  char opcode_;
  std::unique_ptr<ExprAST> operand_;

public:
  UnaryExprAST(char opcode, std::unique_ptr<ExprAST> oprand)
      : opcode_(opcode), oprand_(std::move(oprand)) {}

  Value *Codegen() override;
};

添加 Parser：

/// unary
///   ::= primary
///   ::= '!' unary
static std::unique_ptr<ExprAST> ParseUnary() {
  // If the current token is not an operator, it must be a primary expr.
  if (!isascii(g_cur_token) || g_cur_token == '(' || g_cur_token == ',')
    return ParsePrimary();

  // If this is a unary operator, read it.
  int opcode = g_cur_token;
  NextToken();
  if (auto operand = ParseUnary())
    return std::make_unique<UnaryExprAST>(opcode, std::move(operand));
  return nullptr;
}

以上代码先处理一元运算符，然后将剩余部分看作另外一个一元运算表达式，这样的话就能处理有多个一元运算符的情况了，比如 !!x。

接下来，需要想办法让 ParseUnary 被调用到。可以将调用 ParsePrimary 的地方替换为调用 ParseUnary：

/// binoprhs
///   ::= ('+' unary)*
static std::unique_ptr<ExprAST> ParseBinOpRHS(int min_expr_prec,
                                              std::unique_ptr<ExprAST> lhs) {
  ...
    // Parse the unary expression after the binary operator.
    auto rhs = ParseUnary();
    if (!rhs)
      return nullptr;
  ...
}

/// expression
///   ::= unary binoprhs
static std::unique_ptr<ExprAST> ParseExpression() {
  auto lhs = ParseUnary();
  if (!lhs)
    return nullptr;

  return ParseBinOpRHS(0, std::move(lhs));
}

扩展对 Prototype 的解析：

/// prototype
///   ::= id '(' id* ')'
///   ::= binary LETTER number? (id, id)
///   ::= unary LETTER (id)
static std::unique_ptr<PrototypeAST> ParsePrototype() {
  std::string fn_name;

  unsigned kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
  unsigned binary_precedence = 30;

  switch (g_cur_token) {
  default:
    return LogErrorP("Expected function name in prototype");
  case TOKEN_IDENTIFIER:
    fn_name = g_identifier_str;
    kind = 0;
    NextToken();
    break;
  case TOKEN_UNARY:
    NextToken();
    if (!isascii(g_cur_token))
      return LogErrorP("Expected unary operator");
    fn_name = "unary";
    fn_name += (char)g_cur_token;
    kind = 1;
    NextToken();
    break;
  case TOKEN_BINARY:
    ...

生成 IR：

Value *UnaryExprAST::Codegen() {
  Value *oprand_v = oprand_->Codegen();
  if (!oprand_v)
    return nullptr;

  Function *f = GetFunction(std::string("unary") + opcode_);
  if (!f)
    return LogErrorV("Unknown unary operator");

  g_ir_builder->CreateCall(f, oprand_v, "unopcode");
}

10 可变变量

接下来将支持如下两个功能：

通过等号给变量赋值。
定义新变量。

比如支持如下示例：

# Define ':' for sequencing: as a low-precedence operator that ignores operands
# and just returns the RHS.
def binary : 1 (x y) y;

# Recursive fib, we could do this before.
def fib(x)
  if (x < 3) then
    1
  else
    fib(x-1)+fib(x-2);

# Iterative fib.
def fibi(x)
  var a = 1, b = 1, c in
  (for i = 3, i < x in
     c = a + b :
     a = b :
     b = c) :
  b;

# Call it.
fibi(10);

为了改变变量，需要改变变量申请方式，并添加新的操作符。

10.1 修改已有变量

g_named_values 中存放对应符号名称的 LLVM Value*，为了支持变量，需要改为存放符号的”内存地址“。

首先，将 g_named_values 改为映射 AllocaInst*，而不再映射 Value*：

static std::map<std::string, AllocaInst*> g_named_values;

需要一个 helper 函数确保在函数的入口块中创建 alloca：

/// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
/// the function.  This is used for mutable variables etc.
static AllocaInst *CreateEntryBlockAlloca(Function *function,
                                          const std::string &var_name) {
  // 创建 IRBuilder，指向了入口块的第一条指令
  IRBuilder<> tmp_b(&function->getEntryBlock(),
                    function->getEntryBlock().begin());
  // 创建 alloca
  return tmp_b.CreateAlloca(Type::GetDoubleTypepe(g_llvm_context), 0,
                            var_name.c_str());
}

在新模式中，变量位于栈中，所以要使用它们的话，需要从栈中加载：

Value *VariableExprAST::Codegen() {
  // Look this variable up in the function.
  Value *v = g_named_values[name_];
  if (!v)
    return LogErrorV("Unknown variable name");

  // Load the value.
  g_ir_builder->CreateLoad(Type::GetDoubleTypepe(*g_llvm_context), v, name_.c_str());
}

接下来需要更新定义变量的地方以使用 alloca，先从 ForExprAST::Codegen() 开始：

Function *function = Builder.GetInsertBlock()->getParent();

// Create an alloca for the variable in the entry block.
AllocaInst *alloca = CreateEntryBlockAlloca(function, var_name_);

// Emit the start code first, without 'variable' in scope.
Value *start_val = start_->Codegen();
  if (!start_val)
    return nullptr;

// Store the value into the alloca.
g_ir_builder->CreateStore(start_val, alloca);
...

// Compute the end condition.
Value *end_condition = end_->Codegen();
if (!end_condition)
	return nullptr;

// Reload, increment, and restore the alloca.  This handles the case where
// the body of the loop mutates the variable.
Value *cur_var = g_ir_builder->CreateLoad(Type::GetDoubleTypepe(*g_llvm_context), alloca,
                                          var_name_.c_str());
Value *next_var = g_ir_builder->CreateFAdd(cur_var, step_val, "nextvar");
g_ir_builder->CreateStore(next_var, alloca);
...

可以看到，使用了变量后，便不需要再创建 PHI 节点了，而是通过 load/store 访问所需的变量。

支持函数参数变量：

Function *FunctionAST::Codegen() {
  ...
  g_ir_builder->SetInsertPoint(bb);

  // Record the function arguments in the g_named_values map.
  g_named_values.clear();
  for (auto &arg : function->args()) {
    // Create an alloca for this variable.
    AllocaInst *alloca = CreateEntryBlockAlloca(function, arg.name());

    // Store the initial value into the alloca.
    g_ir_builder->CreateStore(&arg, alloca);

    // Add arguments to variable symbol table.
    g_named_values[std::string(arg.name())] = alloca;
  }

  if (Value *ret_val = body_->Codegen()) {
    ...

为每个参数创建一个 alloca，即在栈上申请内存，然后将参数值保存进去，最后将 alloca 更新到 g_named_values 中。

使用内存保存临时变量的性能比较低，可以使用 mem2reg 优化，使用寄存器存放变量：

// Promote allocas to registers.
g_fpm->add(createPromoteMemoryToRegisterPass());
// Do simple "peephole" optimizations and bit-twiddling optzns.
g_fpm->add(createInstructionCombiningPass());
// Reassociate expressions.
g_fpm->add(createReassociatePass());
...

10.2 新的赋值符号

设置优先级：

int main() {
  // Install standard binary operators.
  // 1 is lowest precedence.
  g_binopcode_precedence['='] = 2;
  g_binopcode_precedence['<'] = 10;
  g_binopcode_precedence['+'] = 20;
  g_binopcode_precedence['-'] = 20;

生成 IR：

Value *BinaryExprAST::Codegen() {
  // Special case '=' because we don't want to emit the LHS as an expression.
  if (opcode_ == '=') {
    // Assignment requires the LHS to be an identifier.
    // 左值必须是个变量
    VariableExprAST *lhs = static_cast<VariableExprAST *>(lhs_.get());
    if (!lhs)
      return LogErrorV("destination of '=' must be a variable");
      
    // Codegen the RHS.
    // 生成右值
    Value *val = rhs_->Codegen();
    if (!val)
      return nullptr;

    // Look up the name.
    Value *variable = g_named_values[lhs->name()];
    if (!variable)
      return LogErrorV("Unknown variable name");

		// 赋值
    g_ir_builder->CreateStore(val, variable);
    return val;
  }
  ...

因为有了赋值符号和变量，所以可运行如下代码：

# Function to print a double.
extern printd(x);

# Define ':' for sequencing: as a low-precedence operator that ignores operands
# and just returns the RHS.
def binary : 1 (x y) y;

def test(x)
  printd(x) :
  x = 4 :
  printd(x);

test(123);

10.3 自定义本地变量

添加 var/in，和之前一样，扩展 Kaleidoscope 一般需要扩展：Lexer、Parser、AST 和生成 IR。

扩展 Lexer：

enum Token {
  ...
  // var definition
  TOKEN_VAR = -13
...
}
...
static int GetToken() {
...
    if (g_identifier_str == "var")
      return TOKEN_VAR;
    return TOKEN_IDENTIFIER;
...

定义 AST 节点：

/// VarExprAST - Expression class for var/in
// 可以一次性定义多个变量
class VarExprAST : public ExprAST {
	std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> var_names_;
  std::unique_ptr<ExprAST> body_; // 对变量要执行的操作

public:
  VarExprAST(
  		std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> var_names_,
      std::unique_ptr<ExprAST> body)
      : var_names_(std::move(var_names_)), body_(std::move(body)) {}

  Value *Codegen() override;
};

扩展 Parser。

先添加到基本表达式中：

/// primary
///   ::= identifierexpr
///   ::= numberexpr
///   ::= parenexpr
///   ::= ifexpr
///   ::= forexpr
///   ::= varexpr
static std::unique_ptr<ExprAST> ParsePrimary() {
  switch (g_cur_token) {
  ...
  case TOKEN_VAR:
    return ParseVarExpr();
  }
}

然后定义 ParseVarExpr：

/// varexpr ::= 'var' identifier ('=' expression)?
//                    (',' identifier ('=' expression)?)* 'in' expression
static std::unique_ptr<ExprAST> ParseVarExpr() {
  NextToken();  // eat the var.

  std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> var_names;

  // At least one variable name is required.
  if (g_cur_token != TOKEN_IDENTIFIER)
    return LogError("expected identifier after var");
    
  // 解析所有变量
  while (1) {
    std::string name = g_identifier_str;
    NextToken(); // eat identifier.

    // Read the opcodetional initializer.
    std::unique_ptr<ExprAST> init = nullptr;
    if (g_cur_token == '=') {
      NextToken(); // eat the '='.

      init = ParseExpression();
      if (!init)
        return nullptr;
    }

    var_names.push_back(std::make_pair(name, std::move(init)));

    // End of var list, exit loop.
    if (g_cur_token != ',')
      break;
    NextToken(); // eat the ','.

    if (g_cur_token != TOKEN_IDENTIFIER)
      return LogError("expected identifier list after var");
  }
  
  // At this point, we have to have 'in'.
  if (g_cur_token != TOKEN_IN)
    return LogError("expected 'in' keyword after 'var'");
  NextToken(); // eat 'in'.

	// 针对变量要执行的操作
  auto body = ParseExpression();
  if (!body)
    return nullptr;

  return std::make_unique<VarExprAST>(std::move(var_names), std::move(body));
}

生成 IR：

Value *VarExprAST::Codegen() {
  std::vector<AllocaInst *> old_bindings;

  Function *function = Builder.GetInsertBlock()->getParent();

  // Register all variables and emit their initializer.
  // 初始化每个变量，并注册到符号表中
  for (unsigned i = 0, e = var_names_.size(); i != e; ++i) {
    const std::string &var_name = var_names_[i].first;
    ExprAST *init = var_names[i].second.get();
    
    // Emit the initializer before adding the variable to scope, this prevents
    // the initializer from referencing the variable itself, and permits stuff
    // like this:
    //  var a = 1 in
    //    var a = a in ...   # refers to outer 'a'.
    Value *init_val;
    if (init) {
      init_val = init->Codegen();
      if (!init_val)
        return nullptr;
    } else { // If not specified, use 0.0.
      init_val = ConstantFP::get(*g_llvm_context, APFloat(0.0));
    }

    AllocaInst *alloca = CreateEntryBlockAlloca(function, var_name);
    g_ir_builder->CreateStore(init_val, alloca);

    // Remember the old variable binding so that we can restore the binding when
    // we unrecurse.
    old_bindings.push_back(g_named_values[var_name]);

    // Remember this binding.
    g_named_values[var_name] = alloca;
  }
  
  // Codegen the body, now that all vars are in scope.
  // body 可以访问到所有的自定义变量
  Value *body_val = body_->Codegen();
  if (!body_val)
    return nullptr;
    
  // Pop all our variables from scope.
  for (unsigned i = 0, e = var_names_.size(); i != e; ++i)
    g_named_values[var_names_[i].first] = old_bindings[i];

  // Return the body computation.
  return body_val;
}

现在可以支持如下示例了：

extern printd(x)

def foo(x)
    if x < 3 then
        1
    else
        foo(x - 1) + foo(x - 2)

for i = 1, i < 10, 1.0 in
    printd(foo(i))

编译运行：

# Compile
clang++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core orcjit native` -O3 -o toy
# Run
./toy

11 编译生成目标文件

LLVM 支持跨平台编译，可使用“target triple”的字符串指定体系结构，其形式为<arch><sub>-<vendor>-<sys>-<abi>。例如，clang 认为我们的体系结构为：

$ clang --version | grep Target
Target: x86_64-unknown-linux-gnu

我们并不需要硬编码体系结构，LLVM 的 sys::getDefaultTargetTriple 会返回当前机器的体系结构：

auto target_triple = sys::getDefaultTargetTriple();

TargetMachine 类提供了对机器的完整描述，可以帮助我们配置特定的 feature 或特定的 CPU。比如，我们可以查看支持哪些 feature 和 CPU：

$ llvm-as < /dev/null | llc -march=x86 -mattr=help
Available CPUs for this target:

  amdfam10      - Select the amdfam10 processor.
  athlon        - Select the athlon processor.
  athlon-4      - Select the athlon-4 processor.
  ...

Available features for this target:

  16bit-mode            - 16-bit mode (i8086).
  32bit-mode            - 32-bit mode (80386).
  3dnow                 - Enable 3DNow! instructions.
  3dnowa                - Enable 3DNow! Athlon instructions.
  ...

比如，我们可以使用不包含任何附加 feature 的通用 CPU：

auto cpu = "generic";
auto features = "";

TargetOptions opt;
auto rm = Optional<Reloc::Model>();
auto target_machine = target->createTargetMachine(target_triple, cpu, features, opt, rm);

完整代码如下：

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

  // Initialize the target registry etc.
	// 初始化生成 IR 的所有 target
	// LLVM 并不要求我们链接所有的 target，如果我们只是使用 JIT，可以不组装打印机
  InitializeAllTargetInfos();
  InitializeAllTargets();
  InitializeAllTargetMCs();
  InitializeAllAsmParsers();
  InitializeAllAsmPrinters();

	// 返回当前机器的体系结构
  auto target_triple = sys::getDefaultTargetTriple();
  
  g_llvm_module->setTargetTriple(target_triple);

  // 获取 Target
  std::string error;
  auto target = TargetRegistry::lookupTarget(target_triple, error);

  // Print an error and exit if we couldn't find the requested target.
  // This generally occurs if we've forgotten to initialise the
  // TargetRegistry or we have a bogus target triple.
  if (!target) {
    errs() << error;
    return 1;
  }

	// 使用不包含任何附加 feature 的通用 CPU
  auto cpu = "generic";
  auto features = "";

  TargetOptions opt;
  auto rm = Optional<Reloc::Model>();
  // TargetMachine 类提供对机器的完整描述
  auto target_machine =
      target->createTargetMachine(target_triple, cpu, features, opt, rm);

  // 配置 Module，这一步不是必须的，但是有助于优化
  g_llvm_module->setDataLayout(target_machine->createDataLayout());
  g_llvm_module->setTargetTriple(target_triple);

	// 目标文件
  auto filename = "output.o";
  std::error_code err_code;
  raw_fd_ostream dest(filename, err_code, sys::fs::OF_None);

  if (err_code) {
    errs() << "Could not open file: " << err_code.message();
    return 1;
  }

  // 定义一个生成目标的 pass
  legacy::PassManager pass;
  auto file_type = CGFT_ObjectFile;

  if (target_machine->addPassesToEmitFile(pass, dest, nullptr, file_type)) {
    errs() << "TheTargetMachine can't emit a file of this type";
    return 1;
  }

  // 运行 pass
  pass.run(*g_llvm_module);
  dest.flush();

  outs() << "Wrote " << filename << "\n";

  return 0;
}

编译运行：

$ clang++ -g -O3 toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs all` -o toy
$ ./toy
ready> def average(x y) (x + y) * 0.5;
^D
Wrote output.o

12 添加 Debug 信息

12.1 提前编译模式

我们无法在 JIT 模式下 debug，而是需要进行提前编译（AOT），为此需要一个源码文件。

优化会将多条指令合并成一个，还可能会去掉一些变量，所以为了 debug，我们先去掉优化。

首先，我们将包含顶级语句的匿名函数设为“main”：

auto proto = std::make_unique<PrototypeAST>("main", std::vector<std::string>());

然后去掉命令行代码：

@@ -1129,7 +1129,6 @@ static void HandleTopLevelExpression() {
 /// top ::= definition | external | expression | ';'
 static void MainLoop() {
   while (1) {
-    fprintf(stderr, "ready> ");
     switch (g_cur_token) {
     case TOKEN_EOF:
       return;
@@ -1184,7 +1183,6 @@ int main() {
   g_binop_precedence['*'] = 40; // highest.

   // Prime the first token.
-  fprintf(stderr, "ready> ");
   NextToken();

最后，关掉所有的优化和 JIT：

static void HandleTopLevelExpression() {
  // Evaluate a top-level expression into an anonymous function.
  if (auto fn_ast = ParseTopLevelExpr()) {
    if (!fn_ast->codegen()) {
      fprintf(stderr, "Error generating code for top level expr");
    }
  } else {
    // Skip token for error recovery.
    NextToken();
  }
}

通过以上改动，我们便可通过如下命令将 Kaleidoscope 编译为一个可执行程序 a.out/a.exe：

Kaleidoscope-Ch9 < fib.ks | & clang -x ir -

12.2 DWARF 设置

源码级调试需要使用格式化的数据，以便调试器将二进制文件和机器码转换回源代码。LLVM 中，通常使用 DWARF 格式，一种表示类型、源位置和变量位置的紧凑编码。

与 IRBuilder 类似，DIBuilder 可以为 LLVM IR 文件构建 debug 元数据。我们将使用 DIBuilder 来构建所有 IR 级别的描述。

static std::unique_ptr<DIBuilder> g_di_builder;

struct DebugInfo {
  DICompileUnit *compile_unit_;  // 编译单元，可以理解为是一个源码文件
  DIType *di_type_;

  DIType *GetDoubleTypepe();
} g_dbg_info;

// 只需要考虑 double 类型就好了
DIType *DebugInfo::GetDoubleType() {
  if (di_type_)
    return di_type_;

  di_type_ = g_di_builder->createBasicType("double", 64, dwarf::DW_ATE_float);
  return di_type_;
}

在 main 中构建 module 时：

g_di_builder = new DIBuilder(*g_llvm_module);

g_dbg_info.compile_unit_ = g_di_builder->createCompileUnit(
		// 使用了 C 中的常量，
		// 因为调试器不一定理解它不识别的语言的调用约定或默认 ABI，
		// 所以在 LLVM 代码生成中遵循 C ABI 是最准确的。
		// 这确保了我们可以从调试器中调用函数并让它们执行
    dwarf::DW_LANG_C, 
    // 硬编码了文件名
    g_di_builder->createFile("fib.ks", "."),
    "Kaleidoscope Compiler", 0, "", 0);

在 main 的末尾处添加：

g_di_builder->finalize();

12.3 函数

接下来需要将一些函数定义添加到 debug 信息中。在 PrototypeAST::Codegen() 中添加几行代码来描述程序的上下文。本例中是“文件”和函数本身的定义。

上下文：

DIFile *unit = DBuilder->createFile(g_dbg_info.compile_unit_.getFilename(),
                                    g_dbg_info.compile_unit_.getDirectory());

使用源位置 0（因为 AST 还没有源码位置信息）并构建函数定义：

DIScope *f_context = unit;
unsigned line_no = p.line();
unsigned scope_line = line_no;
  
// DISubprogram 中包含了函数的所有元数据
DISubprogram *sp = g_di_builder->createFunction(
  f_context, p.name(), StringRef(), unit, line_no,
  CreateFunctionType(function->arg_size(), unit), scope_line,
  DINode::Flagprototyped, DISubprogram::SPFlagDefinition);
function->setSubprogram(sp);

12.4 源位置

debug 最重要的就是精确的源位置。

在 Lexer 中添加源位置信息，跟踪行号和列号：

struct SourceLocation {
  int line_;
  int col_;
};
static SourceLocation g_cur_loc;
static SourceLocation g_lex_loc = {1, 0};

static int Advance() {
  int last_char = getchar();

  if (last_char == '\n' || last_char == '\r') {
    g_lex_loc.line_++;
    g_lex_loc.col_ = 0;
  } else
    g_lex_loc.col_++;
  return last_char;
}

在 AST 中添加源位置信息：

class ExprAST {
  SourceLocation loc_;

public:
  ExprAST(SourceLocation loc = g_cur_loc) : loc_(loc) {}
  virtual ~ExprAST() {}
  virtual Value *Codegen() = 0;
  int line() const { return loc_.line_; }
  int col() const { return loc_.col_; }
  virtual raw_ostream &Dump(raw_ostream &out, int ind) {
    return out << ':' << line() << ':' << col() << '\n';
  }
};

创建 AST 的时候将源位置信息传进去：

lhs = std::make_unique<BinaryExprAST>(bin_loc, binopcode, std::move(lhs),
                                      std::move(rhs));

为了确保每条指令都能获得正确的源位置，每到达一个新位置时都需要告诉 Builder。使用一个 helper 函数来实现此功能：

void DebugInfo::EmitLocation(ExprAST *ast) {
  DIScope *scope;
  if (lexical_blocks_.empty())
    scope = compile_unit_;
  else
    scope = lexical_blocks_.back();
  g_ir_builder->SetCurrentDebugLocation(DILocation::get(
      scope->getContext(), ast->line(), ast->col(), scope));
}

这既告诉了 main IRBuilder 我们在哪里，也告诉了我们在什么作用域内。在 DebugInfo 创建了一个栈作用域：

std::vector<DIScope *> lexical_blocks_;

每当为一个函数生成 code 时，便将该函数的作用域入栈：

// Push the current scope.
g_dbg_info.lexical_blocks_.push_back(sp);

结束生成 code 时，将该函数的作用域出栈：

// Pop off the lexical block for the function since we added it
// unconditionally.
g_dbg_info.lexical_blocks_.pop_back();

每当为一个新的 AST 生成 code 时，都需要发射位置：

g_dbg_info.EmitLocation(this);

12.5 变量

现在有了函数，我们需要能够打印出作用域内的变量。

// Record the function arguments in the g_named_values map.
g_named_values.clear();
unsigned arg_idx = 0;
for (auto &arg : function->args()) {
  // Create an alloca for this variable.
  AllocaInst *alloca = CreateEntryBlockAlloca(function, arg.name());

  // Create a debug descriptor for the variable.
  // 给变量一个作用域（sp），源码位置，类型和参数下标
  DILocalVariable *des = g_di_builder->createParameterVariable(
        sp, arg.name(), ++arg_idx, unit, line_no, g_dbg_info.GetDoubleType(),
        true);

	// 告诉 IR 我们在 alloca 中获取到一个变量（给出了变量的位置）
	// 并在 declare 上为作用域的起始位置设置源位置
  g_di_builder->insertDeclare(alloca, des, g_di_builder->createExpression(),
                              DILocation::get(SP->getContext(), line_no, 0, sp),
                              g_ir_builder->GetInsertBlock());

  // Store the initial value into the alloca.
  g_ir_builder.CreateStore(&arg, alloca);

  // Add arguments to variable symbol table.
  g_named_values[arg.name()] = alloca;
}

在 FunctionST::Codegen中，添加了几行，避免为函数序言生成行信息，以便调试器知道在设置断点时跳过这些指令：

// Unset the location for the prologue emission (leading instructions with no
// location in a function are considered part of the prologue and the debugger
// will run past them when breaking on a function)
g_dbg_info.EmitLocation(nullptr);

当真正开始为函数体生成 code 时发射位置：

g_dbg_info.EmitLocation(body_.get());

有了这些，我们就有了足够的调试信息，可以在函数中设置断点、打印参数变量和调用函数。

编译运行：

# Compile
clang++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core orcjit native` -O3 -o toy
# Run
./toy

参考

https://llvm.org/docs/tutorial/index.html

宫文学. 编译原理之美.

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

llvm-ir

llvm

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

llvm-ir

llvm

#LLVM