学习LLVM第1篇：官方入门教程笔记

by tintin @

官方教程地址：https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/index.html

简介

这个教程介绍了如何使用LLVM来开发一门新的语言，主要包括手写的Lexer、Parser、以及如何将AST转化为LLVM IR、如何对转化后的IR进行JIT编译并执行、如何将IR编译为目标文件。

教程的第1～7章是一步步扩充Kaleidoscope语言的，从基本的功能，到JIT，再新增IF和FOR语句，再到用户可自定义的操作符，再到可重新赋值的变量。第8章讲解如何将IR编译为目标文件，并且跟其他语言的目标文件（比如C/C++）进行链接。第9章讲解了如何生存调试信息（主要就是源代码中各语句的位置信息），从而可以方便的进行调试。第10章做了总结，并且提出了很多可以继续开发的扩展点。

如果想直接看代码的话，可以只看第7、8、9三个章节的代码。1～6章节是一个迭代过程，在第7章都可以看到。

每个章节详解

下面对每一个章节进行细讲，主要是讲每个章节所做的事情，以及一些原理的重点介绍。

第1、2章

实现第一版不带控制流的Kaleidoscope语言的词法和语法解析部分，输出抽象语法树AST。

词法分析部分比较简单，直接一个个字符进行判断，生成对应的token。

语法解析部分使用了自顶向下的递归下降语法分析方法（Recursive Descent Parsing），通过最多往前判断一个token进行语法的确认，简称LL(1)。这种方法一般会给每个产生式定义一个处理函数，通过判断当前的token所属类型确定属于哪一种语法，进而调用对应的处理函数。

不过在解析表达式语法的时候，因为要处理二元操作符的优先级，使用了自底向上的操作符优先级判断的语法分析方法（Operator-Precedence Parsing）。具体的原理大概是这样子的，比如对于a + b * c表达式，+的优先级为10，*的优先级为20。在解析到+号时，会再去判断是否后面还有操作符及优先级，如果后面的优先级更高，则会先让后面的表达式先解析，然后再回来解析+号。具体到这个例子，*号的优先级比+号的高，所以在解析到a + b的时候，并不是先解析成表达式之后再继续解析后面的，而是继续判断后面的*号是否优先级更高。因为*号的优先级较高，所以会让a +先等着，先解析b * c。得到一个表达式后作为一个完整的操作数（作为+号的第二个操作数），并回来解析a +。

语言BNF定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
Program       -> FunDef | ExternFun | TopLevelExpr
FunDef        -> "def" ident "(" FormalArgs ")" Expr ";"
ExternFun     -> "extern" ident "(" FormalArgs ")" ";"
FormalArgs    -> ε | ident | ident FormalArgs
TopLevelExpr  -> Expr ";"
Expr          -> num | ident | ident "(" ActualArgs ")" 
              |  Expr Op Expr | "(" Expr ")"
Op            -> "<" | "-" | "+" | "*"
ActualArgs    -> ε | ident | ident "," ActualArgs
ident         -> [a-zA-Z][a-zA-Z0-9]*
num           -> [0-9.]+
comment       -> "#" [^\n\r]*

示例代码：

1
2
3
4
5
6
extern sin(arg); # 外部函数
sin(1);

def f(a b c)
  a + (b * c);
f(1, 2, 3);

第3章

这一章介绍如何将前面生成的抽象语法树，转化为LLVM IR的表示。主要做的事情就是根据AST的语义，等价调用LLVM IR的API，创建module。首先来看下Kaleidoscope语言的AST表示：

接下来我们来看两个示例，看下他们对应的AST的样子：

  1. 函数定义示例

    1
    2
    def add (a b)
      a + b;

  2. 表达式示例

    1
    add(1, 2);

有了AST之后，转换成LLVM IR就比较直接了。针对不同的AST节点，做对应的事情，最终将其转化为一个LLVM中的Value实例。比如针对NumExpr，调用ConstantFP::get(TheContext, APFloat(Val))即可。不熟悉的话可以去查看下LLVM IR的API文档。下面列下每种AST节点对应的创建LLVM IR的代码（来源于教程）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// NumExpr:
ConstantFP::get(TheContext, APFloat(Val));

// VariableExpr:
// 根据名称从NamedValues Map中获取对应的Value
Value *V = NamedValues[Name];

// CallExpr:
// 1. 根据函数名称获取前面定义了的函数实例
Function *CalleeF = TheModule->getFunction(Callee);
// 2. 确定每个参数的Value
std::vector<Value *> ArgsV;
for (unsigned i = 0, e = Args.size(); i != e; ++i) {
  ArgsV.push_back(Args[i]->codegen());
  if (!ArgsV.back())
    return nullptr;
}
// 3. 创建Call指令
Builder.CreateCall(CalleeF, ArgsV, "calltmp");

// BinaryExpr:
// 1. 确定左右操作数的Value
Value *L = LHS->codegen();
Value *R = RHS->codegen();
// 2. 根据操作符，创建对应的操作
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");
}

// FuncProto:
// 创建参数列表的类型
std::vector<Type *> Doubles(Args.size(), Type::getDoubleTy(TheContext));
// 函数原型
FunctionType *FT = FunctionType::get(Type::getDoubleTy(TheContext), Doubles, false);
// 生成函数实例
Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule.get());

// FuncDef:
Function *TheFunction = Proto->codegen();
// 收集参数变量，用于body中的访问
NamedValues.clear();
for (auto &Arg : TheFunction->args()) {
  NamedValues[Arg.getName()] = &Arg;
}
// 创建函数的body BB，并设置指令插入的位置为底部
BasicBlock *BB = BasicBlock::Create(TheContext, "entry", TheFunction);
Builder.SetInsertPoint(BB);
Value *RetVal = Body->codegen();
// 设置返回指定，指定返回的内容
Builder.CreateRet(RetVal);

在讲到FuncDef的LLVM IR的生成代码时，教程提到有一个bug，无法处理下面的代码：

1
2
extern foo(a);
def foo(b) b; // 两个函数原型的参数名称不一样

下面给出我的解决方法：

1
2
3
4
5
6
7
8
9
10
11
Function *TheFunction = TheModule->getFunction(Proto->getName());
if (!TheFunction) {
  TheFunction = Proto->codegen();
} else {
  // 如果TheFunction之前就创建过了，则更新参数的名称，这样之后就可以找到了
  unsigned idx = 0;
  for (auto &Arg : TheFunction->args()) {
    // getArgName是新增的根据idx获取参数名称的方法
    Arg.setName(Proto->getArgName(idx++));
  }
}

第4章

讲了两件事情，一是如何增加函数级别的优化，二是增加JIT编译功能，通过JIT编译之后为本地代码之后，可以在C++中直接调用Kaleidoscope中的函数进行执行。

关于增加函数级别的优化，只需要在初始化Module的时候，同时根据创建的module创建FunctionPassManager，有了FunctionPassManager之后，就可以给他添加你想要的优化Pass了。比如教程中就添加了四个：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void InitializeModuleAndPassManager(void) {
  TheModule = std::make_unique<Module>("my cool jit", TheContext);
  TheFPM = std::make_unique<FunctionPassManager>(TheModule.get());

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

  TheFPM->doInitialization();
}

对于JIT编译，本章并没有分享JIT模块的原理，而是假设已经写好了一个KaleidoscopeJIT模块，如何去使用它。通过创建一个JIT实例，然后将用户输入的代码转化为LLVM Module，然后将Module添加给JIT实例，就会对添加进去的模块进行编译。编译了之后，可以通过函数名称找到函数的内存地址，进而直接调用。核心代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if (auto FnAST = ParseTopLevelExpr()) {
  if (FnAST->codegen()) {
    // 将TopLevelExpr所在的模块添加到JIT实例中
    auto H = TheJIT->addModule(std::move(TheModule));
    InitializeModuleAndPassManager();

    // 编译万之后找到__anon_expr的内存地址
    auto ExprSymbol = TheJIT->findSymbol("__anon_expr");
    // 转化为函数指针后进行调用
    double (*FP)() = (double (*)())(intptr_t)ExprSymbol.getAddress();
    fprintf(stderr, "Evaluated to %f\n", FP());
    // 执行完之后删除
    TheJIT->removeModule(H);
  }

另外需要注意，为了让用户输入的函数定义，在后面一直都可以被调用。需要将函数定义存放的模块跟TopLevelExpr所处的模块分开，这样在执行完之后进行删除时，不会同时把函数定义给删除了。

第5章

本章给Kaleidoscope添加了流程控制语句If/Then/Else和循环语句For/In。

扩展后语言的BNF定义如下：

1
2
3
4
5
6
7
...
Expr          -> num | ident | ident "(" ActualArgs ")" 
              |  Expr Op Expr | "(" Expr ")"
              |  "if" Expr "then" Expr "else" Expr
              |  "for" ident "=" Expr "," Expr "," Expr "in"
              |  "for" ident "=" Expr "," Expr "in"
...

示例代码：

1
2
3
4
5
6
7
8
# If语句
if 1 < 2 
then 3
else f(1, 2, 3);

# For语句，1.00增长步伐可以省略
for i = 0, i < 100, 1.00 in
  f(1, 2, i);

IR的生成，主要需要注意分支有哪些，以及分支汇集的地方PHI节点的创建。下面将教程中的核心代码加上注释展示出来。

生成条件语句的LLVM IR：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Value *CondV = Cond->codegen();
CondV = Builder.CreateFCmpONE(CondV, ConstantFP::get(TheContext, APFloat(0.0)), "ifcond");
Function *TheFunction = Builder.GetInsertBlock()->getParent();
BasicBlock *ThenBB = BasicBlock::Create(TheContext, "then", TheFunction); // 自动加到函数中
BasicBlock *ElseBB = BasicBlock::Create(TheContext, "else");
BasicBlock *MergeBB = BasicBlock::Create(TheContext, "ifcont");

Builder.CreateCondBr(CondV, ThenBB, ElseBB); // 插入条件分支语句的指令

// Then语句处理
Builder.SetInsertPoint(ThenBB);
Value *ThenV = Then->codegen();
Builder.CreateBr(MergeBB); // 插入跳转到Merge分支的指令
ThenBB = Builder.GetInsertBlock(); // 获取Then语句的出口

// Else语句处理
TheFunction->getBasicBlockList().push_back(ElseBB); // 添加到函数中去
Builder.SetInsertPoint(ElseBB);
Value *ElseV = Else->codegen();
Builder.CreateBr(MergeBB); // 插入跳转到Merge分支的指令
ElseBB = Builder.GetInsertBlock(); // 获取Else语句的出口

// PHI指令的生成
TheFunction->getBasicBlockList().push_back(MergeBB);
Builder.SetInsertPoint(MergeBB);
PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(TheContext), 2, "iftmp");
PN->addIncoming(ThenV, ThenBB);
PN->addIncoming(ElseV, ElseBB);

生成For语句的LLVM IR：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Value *StartVal = Start->codegen();
Function *TheFunction = Builder.GetInsertBlock()->getParent();
BasicBlock *PreheaderBB = Builder.GetInsertBlock();
BasicBlock *LoopBB = BasicBlock::Create(TheContext, "loop", TheFunction);
Builder.CreateBr(LoopBB); // 跳转到Loop分支

Builder.SetInsertPoint(LoopBB);
// 创建PHI节点
PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(TheContext), 2, VarName.c_str());
Variable->addIncoming(StartVal, PreheaderBB);
NamedValues[VarName] = Variable; // 将for定义的变量添加到作用域中
Body->codegen();
Value *StepVal = Step->codegen();
Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");
Value *EndCond = End->codegen();
EndCond = Builder.CreateFCmpONE(EndCond, ConstantFP::get(TheContext, APFloat(0.0)), "loopcond");
BasicBlock *LoopEndBB = Builder.GetInsertBlock(); // 为啥不可以直接使用LoopBB，而是还要获取一次呢？
BasicBlock *AfterBB = BasicBlock::Create(TheContext, "afterloop", TheFunction);
Builder.CreateCondBr(EndCond, LoopBB, AfterBB);

Builder.SetInsertPoint(AfterBB);
Variable->addIncoming(NextVar, LoopEndBB);

第6章

本章讲解自定义操作符功能，主要的方式是通过新增特定的函数定义来实现，BNF表示如下：

1
2
3
4
5
6
...
FunDef        -> "def" ident "(" FormalArgs ")" Expr ";"
              |  "def" "unary" CustomOp "(" Expr ")" Expr ";"
              |  "def" "binary" CustomOp num "(" Expr Expr ")" Expr ";"
CustomOp      -> [.]+
...

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
# 取反
def unary ! (v)
  if v then 0 else 1;

# 或运算，5为二元操作符的优先级
def binary | 5 (LHS RHS)
  if LHS then
    1
  else 
    if RHS then
      1
    else
      0;

这章主要是新增了一些语法糖，并没有新增实质性的内容，并且也没有涉及新的LLVM的内容，所以就不细说了。

第7章

本章给Kaleidoscope语言引入了变量可赋值的功能。需要注意的是，LLVM IR是一种SSA（Static Single Assignment），也就是说每个变量只能被赋值一次。而变量可赋值意味着变量可以被赋值多次，所以需要有一个转化过程，将其转化为SSA格式。但是如果每个地方都需要这样手工处理的话，会相当的繁琐，你需要手工创建很多的PHI节点。幸运的是，LLVM提供了mem2reg的转化Pass，可以将栈变量（可以被修复多次）转化为寄存器变量（只可以被赋值一次）。因此，当我们遇到变量赋值时，我们只需要将其转化为IR中的栈变量，然后调用mem2regPass进行转化即可。

这里说下大致的代码逻辑。在根据函数定义和变量声明的AST生成IR时，首先在EntryBlock（因为mem2reg只会处理放在EntryBlock中的变量）的给每个变量创建一个栈变量，然后再对应的修改的地方创建Store指令，在需要获取的地方创建Load指令。同时因为可以定义新的变量，需要处理同名变量互相覆盖的问题。

语言最新的BNF表示（因为后面的章节没有再对语法有改动了，所以这里给出完整的语法，方便查看）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Program       -> FunDef | ExternFun | TopLevelExpr
FunDef        -> "def" ident "(" FormalArgs ")" Expr ";"
              |  "def" "unary" CustomOp "(" Expr ")" Expr ";"
              |  "def" "binary" CustomOp num "(" Expr Expr ")" Expr ";"
CustomOp      -> [.]+
ExternFun     -> "extern" ident "(" FormalArgs ")" ";"
FormalArgs    -> ε | ident | ident FormalArgs
TopLevelExpr  -> Expr ";"
Expr          -> num | ident | ident "(" ActualArgs ")" 
              |  Expr Op Expr | "(" Expr ")"
              |  "if" Expr "then" Expr "else" Expr
              |  "for" ident "=" Expr "," Expr "," Expr "in"
              |  "for" ident "=" Expr "," Expr "in"
              |  ident "=" Expr
              |  "var" VarDef [ "," VarDef ] "in" Expr
VarDef        -> ident | ident "=" Expr
Op            -> "<" | "-" | "+" | "*"
ActualArgs    -> ε | ident | ident "," ActualArgs
ident         -> [a-zA-Z][a-zA-Z0-9]*
num           -> [0-9.]+
comment       -> "#" [^\n\r]*

新增语法对应的示例代码：

1
2
3
4
5
6
7
8
9
10
11
def binary : 1 (x y) y; # 取两个表达式中的后一个表达式

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

fib(10);

第8章

本章讲解如何将LLVM IR转化为目标文件。这章内容不多，主要包括如何设置和获取Target，如何创建TargetMachine，以及如何通过PassManager触发运行，生成目标文件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
auto TargetTriple = sys::getDefaultTargetTriple();
InitializeAllTargetInfos();
InitializeAllTargets();
InitializeAllTargetMCs();
InitializeAllAsmParsers();
InitializeAllAsmPrinters();
// 获取当前平台相关的Target
std::string Error;
auto Target = TargetRegistry::lookupTarget(TargetTriple, Error);
// 生成TargetMatchine
auto CPU = "generic";
auto Features = "";
TargetOptions opt;
auto RM = Optional<Reloc::Model>();
auto TargetMachine = Target->createTargetMachine(TargetTriple, CPU, Features, opt, RM);
// 生成目标代码
auto Filename = "output.o";
std::error_code EC;
raw_fd_ostream dest(Filename, EC, sys::fs::OF_None);
legacy::PassManager pass;
auto FileType = CGFT_ObjectFile;
TargetMachine->addPassesToEmitFile(pass, dest, nullptr, FileType)
pass.run(*TheModule);
dest.flush(); // 更新到磁盘

第9章

本章讲解如何添加Debug信息到IR中，用于后面的程序调试。大概的原理是这样子的，LLVM提供了DIBuilder，类似IRBuilder。然后在生成IR指令前，需要调用IRBuilder的SetCurrentDebugLocation方法，设置接下来的IR指令的代码行数和列数等信息。关于调试信息的作用域，分为了模块和函数两种，在设置调试信息时，需要确定好是处在模块层还是函数层。LLVM生成的是DWARF标准格式的调试信息。

具体的代码可以直接看对应的章节。

第10章

本章是最后的总结。

首先提到可以对Kaleidoscope做的一些扩展，比如全局变量、含类型的变量、数组等结构体、内存管理、异常管理等各种功能。

然后是讲了下LLVM的一些属性：

  • LLVM IR是目标架构无关的语言，你可以将它编译成任何支持的平台。
  • LLVM IR本身并不是安全的语言，IR支持不安全的指针转换。可以在LLVM之上做一层安全的校验。
  • 编程语言相关的优化。在将源码转成LLVM IR的时候，会丢失一些信息。不过你可以扩展LLVM来添加一些专门针对某一种语言的优化Pass

最后提到了两个避坑指令：

  • 关于offset/sizeof的移植性问题，LLVM中的指针大小是平台相关的，不过有些方式可以避免这个问题。具体可以参考这里。

  • 关于控制栈帧的方法（比如用于实现闭包），LLVM是提供了支持的，不过这需要前端先将代码转成CPS风格的尾递归调用才行。具体可以参考这里

遇到的问题

  • 第4章节（其实还包括后面所有需要用到JIT功能的章节），编译时需要给--libs增加orcjit参数
    • 原来：llvm-config --cxxflags --ldflags --system-libs --libs core mcjit native
    • 需改为：llvm-config --cxxflags --ldflags --system-libs --libs core mcjit native orcjit
    • 或者直接改为all：llvm-config --cxxflags --ldflags --system-libs --libs all