官方教程地址: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的样子:
函数定义示例
表达式示例
有了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 ConstantFP::get(TheContext, APFloat(Val)); Value *V = NamedValues[Name]; Function *CalleeF = TheModule->getFunction(Callee); 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 ; } Builder.CreateCall(CalleeF, ArgsV, "calltmp" ); Value *L = LHS->codegen(); Value *R = RHS->codegen(); 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" ); return Builder.CreateUIToFP(L, Type::getDoubleTy(TheContext), "booltmp" ); } 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()); Function *TheFunction = Proto->codegen(); NamedValues.clear(); for (auto &Arg : TheFunction->args()) { NamedValues[Arg.getName()] = &Arg; } 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 { unsigned idx = 0 ; for (auto &Arg : TheFunction->args()) { 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()); TheFPM->add(createInstructionCombiningPass()); TheFPM->add(createReassociatePass()); TheFPM->add(createGVNPass()); 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()) { auto H = TheJIT->addModule(std ::move(TheModule)); InitializeModuleAndPassManager(); 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); Builder.SetInsertPoint(ThenBB); Value *ThenV = Then->codegen(); Builder.CreateBr(MergeBB); ThenBB = Builder.GetInsertBlock(); TheFunction->getBasicBlockList().push_back(ElseBB); Builder.SetInsertPoint(ElseBB); Value *ElseV = Else->codegen(); Builder.CreateBr(MergeBB); ElseBB = Builder.GetInsertBlock(); 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); Builder.SetInsertPoint(LoopBB); PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(TheContext), 2 , VarName.c_str()); Variable->addIncoming(StartVal, PreheaderBB); NamedValues[VarName] = Variable; 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(); 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中的栈变量,然后调用mem2reg
Pass进行转化即可。
这里说下大致的代码逻辑。在根据函数定义和变量声明的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(); std ::string Error;auto Target = TargetRegistry::lookupTarget(TargetTriple, Error);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
最后提到了两个避坑指令:
遇到的问题
第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