2024LLVM中文版编程手册

LLVMCookbook中文版LLVMCookbook交叉编译将LLVMIR转换为将LLVMbitcode将LLVMbitcode转回为LLVM转换LLVM链接LLVM执行LLVM使用第2第4自定义LLVM实现一个分析实现一个别名分析使用其他分析第5编写无用代码消除编写内联转换编写内存优化合并LLVM其他优化第6LLVMIR使用GraphViz可视化LLVMIR合法化优化第7实现栈帧多指令使用将LLVMIR转换为使用使用第1LLVM交叉编译将LLVMIR转换为将LLVMbitcode将LLVMbitcode转回为LLVM转换LLVM链接LLVM执行LLVM使用言代码编译为LLVMIR（IntermediateRepresentation——中间码）以及如何把它转为其他与其他编译器（例如GNUCompilerCollection——GCC）不同，LLVM的设计目标是成为在我们开始本节之前，我们需要知道一点关于汇编码的知识。的代码有3种表示形式：内存编译器中的、存于磁盘的bod，以及用户可读的汇编码。MR是基于静态单赋值1（cngegnn——）的，并且提供了类型安全性、底层操作性、灵活性，因此能够清楚表达绝大多数高级语言。这种表示形式贯穿的各个阶段。事实上，M致力于成为一种足够底层的通用，只有这样，高级语言的诸多特性才能够得以实现。同样，M组织良好，也具备不错的可读性。如果你对理解本节提到的汇编码有任何疑问，请参考本节结尾的另请参阅一节。$catdefinei32@test1(i32%A)%B=addi32%A,0reti32%Bdefineinternali32@test(i32%X,i32%dead){reti32%Xdefinei32@caller()%A=calli32@test(i32123,i32456)reti32%A$opt–S–instcombinetestfile.ll–o$cat;ModuleID=definei32@test1(i32%A){reti32%Adefineinternali32@test(i32%X,i32%dead){reti32%Xdefinei32@caller()%A=calli32@test(i32123,i32456)reti32%A$opt–S–deadargelimtestfile.ll–o$cat;ModuleID=definei32@test1(i32%A)%B=addi32%A,0reti32%Bdefineinternali32@test(i32%X){reti32%Xdefinei32@caller()%A=calli32@test(i32123)reti32%A在前面的代码中，我们可以看到，第1个命令运行instcombinePass，会将指令合并，因此%Baddi32%A0;reti32%B被优化为reti32%A，并且没有改变原来的代码，而是产在第2个样例中，运行deadargelimpass，对第一个函数没有任何影响，但优化对第2个函数小，而Pass之间的依赖信息由LLVMPass管理器（PassManager）来统一管理，在Pass运行件。图中，PassA中PassA.o引用了LLVMPasses.a，而自定义的Pass中MyPass.oObject文件与优化器相似，LLVM代码生成器（codegenerator）也采用了模块的设计理念，它将代码交叉编译所谓交叉编译，指的是我们能够在一个平台（例如x86）编译并构建二进制文件，而在另一个平台（例如）运行。编译二进制文件的机器称为主机（ho），进制文件的平台我们称为目标平台（g）。为相同平台（主机与目标机器相同）编译代码我们称为本机编译（nveb），而当主机与目标机器为不同平台时编译代码则称为交叉编译（oop）。在此之前你需要为系统（主机平台）安装以下包（程序installllvmonyourhost--DCMAKE_INSTALL_PREFIX=<工具链安装目录（可选-DLLVM_TABLEGEN=<已安装的LLVM工具链目录>/llvm--DCLANG_TABLEGEN=<已安装的LLVM工具链目录>/clang--DLLVM_DEFAULT_TARGET_TRIPLE=arm-linux----DCMAKE_CXX_FLAGS='-targetarmv7a-linux-gnueabihf-mcpu=cortex-a9-I/usr/arm-$cmake-GNinja<LLVM源码目录><上面的选项$CC='clang'CXX='clang++'cmake-GNinja<源码目录><上面的选项$$ninjasysroot[1]关代码（position-independentcode——PIC）生成过程中的绝对地址重定向，这时候可以[1]sysroot：通常指的是系统的根目录，例如Linux系统的根目录为。有时我们可以通过将C源码转换为LLVM本节将使用C语言前端——Clang，把C语言源码转换为LLVMIR$catmultiply.cintmult(){inta=5;intb=3;intc=a*b;returnc;使用以下命令来将C语言代码转换成LLVM$clang-emit-llvm-Smultiply.c-o生成如下的LLVM$cat;ModuleID=targetdatalayout="e-m:e-i64:64-f80:128-n8:16:32:64-S128"targettriple="x86_64-unknown-linux-gnu";FunctionAttrs:nounwinduwtabledefinei32@mult()#0{%a=allocai32,align%b=allocai32,align%c=allocai32,align4storei325,i32*%a,align4storei323,i32*%b,align%1=loadi32*%a,align%2=loadi32*%b,align%3=mulnswi32%1,storei32%3,i32*%c,align%4=loadi32*%c,align4reti32%4$clang-cc1-emit-llvmtestfile.c-o将C语言代码编译为LLVMIR的过程从词法分析开始——将C语言源码分解成token流，每在语言的CFG（ContextFreeGrammar，上下文无关文法）的指导下将token流组织成在第2章中，我们将会看到词法分析、语法分析和代码生成的工作原理。关于LLVM将LLVMIR转换为本节将介绍如何从LLVMIR来生成bitcode。LLVMbitcode（也称为字节码——bytecode）由两部分组成：位流（bitstream，可类比字节流），以及将LLVMIR编码成位流的编码格首先创建LLVMIR代码作为llvm-as$catdefinei32@mult(i32%a,i32%b)#0%1=mulnswi32%a,%breti32%1llvm-astest.ll–ollvm-as即是LLVM的汇编器。它会将LLVMIR转为bitcode（就像把普通的汇编码转成可执为了把M转为bod，我们引入了区块（bok）和记录（od）的概念。区块表示位流的区域，例如一个函数体、符号表等。每个区块的内容都对应一个特定的，例如M中函数体的是12。记录由一个记录码和一个整数值组成，它们描述了在指令、全局变量描述符、类型描述中的实体。LLVMIR的bitcode文件由一个简单的封装结构封装。结构包括一个描述文件段落偏移量将LLVMbitcode本节介绍如何将LLVMbitcode前一节创建的test.bcbitcode文件可作为llc的输入，通过以下命令可把LLVMbitcode转换$llctest.bc–o$cat.file.globl.align16,.type ##BB#0:Pushq.cfi_def_cfa_offset.cfi_offset%rbp,-16movq%rsp,%rbp.cfi_def_cfa_register%rbpimull%esi,%edimovl%edi,%eaxpopq%rbp.sizemult,.Ltmp3-$clang-Stest.bc-otest.s–fomit-frame- #使用Clangmcpu=cpu参数则可以指定其CPU，而-regallocbasicgreedy/fast/pbqp则可以指定寄存器将LLVMbitcode转回为LLVM本节介绍如何通过反汇编工具llvm-dis把LLVMbitcode转回为LLVMIR$llvm-distest.bc–o查看其生成的LLVM|$cat;ModuleID=definei32@mult(i32%a,i32%b)#0%1=mulnswi32%a,%breti32%1llvm-dis命令即是LLVM反汇编器，它使用LLVMbitcode文件作为输入，输出LLVMIR。转换LLVM$opt–passnameinput.ll–o为输入，创建等价的LLVMIR：$catmultiply.cintmult(){inta=5;intb=3;intc=a*b;returnc;$clang-emit-llvm-Smultiply.c-o$cat;ModuleID=targetdatalayout="e-m:e-i64:64-f80:128-n8:16:32:64-S128"targettriple="x86_64-unknown-linux-gnu";FunctionAttrs:nounwinduwtabledefinei32@mult()#0{%a=allocai32,align%b=allocai32,align%c=allocai32,align4storei325,i32*%a,align4storei323,i32*%b,align%1=loadi32*%a,align%2=loadi32*%b,align%3=mulnswi32%1,storei32%3,i32*%c,align%4=loadi32*%c,align4reti32%4$opt-mem2reg-Smultiply.ll-o$cat;ModuleID=targetdatalayout="e-m:e-i64:64-f80:128-n8:16:32:64-S128"targettriple="x86_64-unknown-linux-gnu";FunctionAttrs:nounwinduwtabledefinei32@mult(i32%a,i32%b)#0{%1=mulnswi32%a,%breti32%1gvn为了弄明白C语言代码是如何映射到LLVMIR的，你可以在将C代码转换为IR之后（在“将C源码转换为LLVM汇编码”一节提到），运行mem2regPass，它会帮助你明白C指令是如链接LLVM$cattest1.cintfunc(inta){a=a*2;return$cattest2.cexternintfunc(inta);intmain(){intnum=5;num=func(num);printf("numberis%d\n",num);returnnum;$clang-emit-llvm-Stest1.c-o$clang-emit-llvm-Stest2.c-o$llvm-astest1.ll-o$llvm-astest2.ll-o通过如下方式使用llvm-link命令链接两个LLVMbitcode$llvm-linktest1.bctest2.bc–o执行LLVM本节介绍如何执行之前得到的LLVMbitcode你需要先安装lli工具，用它来执行LLVMbitcode|$llioutput.bcnumberis10这个样例中输出结果是“numberis10”，这就是由之前章节中的test1.c和test2.c链接得到的lli工具命令执行LLVMbitcode格式程序，它使用LLVMbitcode格式作为输入并且使用即时使用C语言前端——创建一个C语言的helloworld，文件名是$cattest.cintmain(){printf("helloworld\n");return0;}$clang$./a.outhelloworld$cattest.c#defineMAX100voidfunc(){inta[MAX];$clangtest.c-E#1"test.c"#1"<built-in>"#1"<built-in>"#308"<built-in>"#1"<commandline>"#1"<built-in>"#1"test.c"2voidfunc(){inta[100];|$clang-cc1test.c-ast-TranslationUnitDecl0x3f72c50<<invalidsloc>><invalid|-TypedefDecl0x3f73148<<invalidsloc>><invalidsloc>int128_t'|-TypedefDecl0x3f731a8<<invalidsloc>><invalidsloc>uint128_t'unsigned|-TypedefDecl0x3f73518<<invalidsloc>><invalidsloc>builtin_va_list'va_list_tag`-FunctionDecl0x3f735b8<test.c:3:1,line:5:1>line:3:6func'void()'`-CompoundStmt0x3f73790<col:13,`-DeclStmt0x3f73778<line:4:1,`-VarDecl0x3f73718<col:1,col:10>col:5a'int|$clangtest.c-S-emit-llvm-o|;ModuleID=|targetdatalayout="e-m:e-i64:64-f80:128-n8:16:32:64-|targettriple="x86_64-unknown-linux-|;FunctionAttrs:nounwind|definevoid@func()#0|%a=alloca[100xi32],align|ret为了得到用于相同test.c测试码的机器码，需要给Clang传递-S参数。如果你使用了-o参|$clang-Stest.c-o .file .globl .align16, .type # |# pushq .cfi_def_cfa_offset .cfi_offset%rbp,- %rsp, .cfi_def_cfa_register func,.Ltmp3- 在只使用-S参数的情况下，编译器会在代码生成的过程中产生机器码。这里使用了-o参使用GO|$cat|package|import|funcmain()|fmt.Println("Test$llgo-dump;ModuleID=targetdatalayout="e-p:64:64:64..."targettriple="x86_64-unknown-linux"%0=type{i8*,i8*llgo编译器是Go语言的前端，它用test.go程序作为输入，输出LLVMIR关于llgo的源码下载及安装步骤，请参见/go-llvmllgo使用你需要GCC4.5及以上版本，目标机器为x86-32/x86-64以及ARM处理器。当然，也需要下创建一个简单的helloworld$cattestprog.cintmain(){printf("hello$gcctestprog.c-S-O1-o.file".string"Hello.globl.typemain,@functionsubq$8,%rspmovl$.LC0,%edicallputsmovl$0,%eaxaddq$8,%rsp.sizemain,.-$gcctestprog.c-S-O1-o--.file"#Startoffilescopeinline.ident"GCC:(GNU)4.5.020090928(experimental)LLVM:#Endoffilescopeinline.align.globl.typemain,@functionsubq$8,%rspmovl$.L.str,%edicallputsxorl%eax,%eaxaddq$8,%rsp.sizemain,.-.type.asciz“Hello.size.L.str,.section.note.GNU-第2词法分析器和语法分析器，以及使用前端从AST（AbstractSyntaxTree）生成IR代码。定义TOYHandSide——LHS），终结符号[2]（terminal-symbol）和非终结符的组合在右边（RightHandSide——RHS）；当遇到一个LHS，就会根据推导规则生成与之对应的RHS。numeric_expr:=paran_expr:='('expression:=:=identifier'('expr_list:=:=expression(','primary:=expression:=primarybinoprhs:=(binoperatorprimary)*binoperators:='+'/'-'/'*'/'/'func_decl:=identifier'('identifier_list')'identifier_list:=(empty):=function_defn:='def'func_decltoplevel_expr:=deffoo(x,y)x+y*16词法分析往往是编译程序的第一步。词法分析器把程序代码的输入流切分成okn，而语法分析器则接受这些okn并把okn流构建成（抽象语法树）。通常来说，被解析成okn的语言是基于上下文无关语法1的。一个okn可以是一个字符串，由一个或多个同一范畴的字符组成。对输入字符流构建成okn的过程称为符号化（oknon）。为了把输入的字符分组成okn，还需要有特定的定界符。对于词法分析来说，有自动化的词法分析工具来完成这个工作，比如。而我们接下来展示的语言来手动实现的。$vim$vimenumToken_Type{EOF_TOKEN=0,staticintstaticstd::stringstaticintget_token(){staticintLastChar='';LastChar=fgetc(file);if(isalpha(LastChar)){Identifier_string=LastChar;while(isalnum((LastChar=fgetc(file))))Identifier_string+=LastChar;if(Identifier_string=="def")returnDEF_TOKEN;returnif(isdigit(LastChar)){std::stringNumStr;do{NumStr+=LastChar;LastChar=}Numeric_Val=strtod(NumStr.c_str(),0);returnNUMERIC_TOKEN;if(LastChar=='#')doLastChar=fgetc(file);while(LastChar!=EOF&&LastChar!='\n'&&LastChar!='\r');if(LastChar!=EOF)returnif(LastChar==EOF)returnintThisChar=LastChar;LastChar=fgetc(file);returnThisChar;deffoo(x,y)x+y*16上下文无关语法：Context-FreeGrammar（CFG），X>=Y，X可以被Y替换，而无须考虑X的上下文，在这里X是一个非终结符。与之对应的是上下文相关语法，aXYbXZ，在不同的推导规则中X具有不同的语义，因此称之为上下文相关语法。——在生成之时，我们需要运行词法分析器来得到okn。我们即将要解析的语言由表达达式等。$vimclassBaseAST{public:virtualclassVariableAST:publicBaseAST{std::stringVar_Name;//定义stringVariableAST(std::string&name):Var_Name(name)//变量ASTclassNumericAST:publicBaseAST{intnumeric_val;publicNumericAST(intval):numeric_val(val)ClassBinaryAST:publicBaseASTstd::stringBin_Operator;//用于存储二元运算符的stringBaseAST*LHS,*RHS;//用于存储一个二元表达式的LHS和RHS//由于LHS和RHS二元操作可以是任何类型，因此用BaseASTBinaryAST(std::stringop,BaseAST*lhs,BaseAST*rhs):Bin_Operator(op),LHS(lhs),RHS(rhs){}//初始化二元运算符、二元表达式的LHS和classFunctionDeclAST{std::stringFunc_Name;std::vector<std::string>Arguments;FunctionDeclAST(conststd::string&name,conststd::vector<std::string>&args):Func_Name(name),Arguments(args)classFunctionDefnAST{FunctionDeclAST*Func_Decl;BaseAST*Body;FunctionDefnAST(FunctionDeclAST*proto,BaseAST*body):Func_Decl(proto),Body(body){}classFunctionCallAST:publicBaseAST{std::stringFunction_Callee;std::vector<BaseAST*>Function_Arguments;FunctionCallAST(conststd::string&callee,std::vector<BaseAST*>Function_Callee(callee),Function_Arguments(args)分析器的样例。关于Clang使用的C++AST结构的详细信息，请参见语法分析器（p）根据语言的语法规则来解析代码，解析阶段决定了输入的代码是否能够根据既定的语法组成okn流1。在此阶段会构造出一棵解析树，而语法分析器则会定义一些函数来把代码组织成一种被称为下降的解析技术自顶向下解析，并用相互递归的函数构建。$vimstaticintstaticvoidnext_token(){Current_token=get_token();staticBaseAST*Base_Parser(){switch(Current_token){default:returncaseIDENTIFIER_TOKEN:returnidentifier_parser();caseNUMERIC_TOKEN:returnnumeric_parser();case'(':return[1]原文为astringoftokens，译者认为原文可能存在错误，应为astreamoftokens，故根据$vistaticBaseAST*numeric_parser()BaseAST*Result=newNumericAST(Numeric_Val);returnstaticBaseAST*identifier_parser(){std::stringIdName=Identifier_string;if(Current_token!='(')returnnewVariableAST(IdName);std::vector<BaseAST*>Args;if(Current_token!=')'){while(1)BaseAST*Arg=expression_parser();if(!Arg)return0;if(Current_token==')')if(Current_token!=',')return0;returnnewFunctionCallAST(IdName,staticFunctionDeclAST*func_decl_parser(){if(Current_token!=IDENTIFIER_TOKEN)return0;std::stringFnName=Identifier_string;if(Current_token!='(')return0;std::vector<std::string>Function_Argument_Names;while(next_token()==IDENTIFIER_TOKEN)if(Current_token!=')')return0;returnnewFunctionDeclAST(FnName,staticFunctionDefnAST*func_defn_parser(){FunctionDeclAST*Decl=func_decl_parser();if(Decl==0)return0;if(BaseAST*Body=expression_parser())returnnewFunctionDefnAST(Decl,Body);return0;staticBaseAST*expression_parser(){BaseAST*LHS=Base_Parser();if(!LHS)return0;returnbinary_op_parser(0,$vistaticstd::map<char,-<+</<staticvoidinit_precedence(){Operator_Precedence['-']=Operator_Precedence['+']=Operator_Precedence['/']=Operator_Precedence['*']=staticintgetBinOpPrecedence(){return-intTokPrec=Operator_Precedence[Current_token];if(TokPrec<=0)return-1;returnstaticBaseAST*binary_op_parser(intOld_Prec,BaseAST*LHS)while(1)intOperator_Prec=getBinOpPrecedence();if(Operator_Prec<Old_Prec)returnintBinOp=Current_token;BaseAST*RHS=Base_Parser();if(!RHS)return0;intNext_Prec=getBinOpPrecedence();if(Operator_Prec<Next_Prec){RHS=binary_op_parser(Operator_Prec+1,RHS);if(RHS==0)return0;LHS=newBinaryAST(std::to_string(BinOp),LHS,staticBaseAST*paran_parser(){BaseAST*V=expression_parser();if(!V)return0;if(Current_token!=')')return0;returnstaticvoidHandleDefn()if(FunctionDefnAST*F=func_defn_parser()){if(Function*LF=F->Codegen()){elsestaticvoidHandleTopExpression(){if(FunctionDefnAST*F=top_level_parser()){if(Function*LF=F->Codegen())else见/doxygen/classclang_1_1Parser.html。$vistaticvoidDriver(){while(1){switch(Current_token){caseEOF_TOKEN:return;case';':next_token();caseDEF_TOKEN:HandleDefn();break;default:HandleTopExpression();break;intmain(intargc,char*argv[]){LLVMContext&Context=getGlobalContext();file=fopen(argv[1],"r");if(file==0){printf("CouldnotopenModule_Ob=newModule("mycompiler",Context);return0;对TOY$clang++toy.cpp-O3-o$catexampledeffoo(x,y)x+y*16$./toy编译器会以读模式打开xp文件，并且将单词组织成okn流。如果遇到d关键字即返回_，然后调用ndn函数，它会存储函数名和参数。程序会递归地检查okn的类型，然后调用特定的okn处理函数，把信息存储在各自的中。理，请参见/docs/tutorial/LangImpl2.html#parser-basics。为每个AST类定义IR现在所有必要信息都存储于AST这一数据结构中，下一阶段即是从AST生成LLVMIR。在的LLVMIR。为了生成LLVMIR，我们需要在每个AST类定义一个CodeGen虚函数（AST类在前面的$viclassBaseASTvirtualValue*Codegen()=classNumericAST:publicBaseASTvirtualValue*classVariableAST:publicBaseASTvirtualValue*这一函数返回值是LLVMValue对象，它表示了静态单赋值（SSA）对象。在Codegen过程staticModulestaticIRBuilder<>Builder(getGlobalContext());staticstd::map<std::string,Value*>Named_Values;Builder对象帮助生成LLVMIR并且记录程序的当前点，以插入LLVMNamed_Valuesmap对象记录当前作用域中的所有已定义值，充当符号表的功能。对我们为表达式生成IR为了实现TOY语言的LLVMIR$viValue*NumericAST::Codegen()returnConstantInt::get(Type::getInt32Ty(getGlobalContext()),Value*VariableAST::Codegen(){Value*V=Named_Values[Var_Name];returnV?V:0;Value*BinaryAST::Codegen(){Value*L=LHS->Codegen();Value*R=RHS->Codegen();if(L==0||R==0)return0;switch(atoi(Bin_Operator.c_str()))case'+':returnBuilder.CreateAdd(L,R,"addtmp");case'-':returnBuilder.CreateSub(L,R,"subtmp");case'*':returnBuilder.CreateMul(L,R,"multmp");case'/':returnBuilder.CreateUDiv(L,R,"divtmp");default:return0;为函数生成IRValue*FunctionCallAST::Codegen(){Function*CalleeF=for(unsignedi=0,e=Function_Arguments.size();i!=e;++i){if(ArgsV.back()==0)return0;returnBuilder.CreateCall(CalleeF,ArgsV,Function*FunctionDeclAST::Codegen(){std::vector<Type*>Integers(Arguments.size(),Type::getInt32Ty(geFunctionType*FT=FunctionType::get(Type::getInt32Ty(getGlobalContext()),Integers,false);Function*F=Function::Create(FT,Function::ExternalLinkage,Func_Name,Module_Ob);if(F->getName()!=Func_Name){F=Module_Ob-if(!F->empty())returnif(F->arg_size()!=Arguments.size())returnunsignedIdx=for(Function::arg_iteratorArg_It=F->arg_begin();Idx!=Arguments.size();++Arg_It,++Idx){Named_Values[Arguments[Idx]]=Arg_It;returnFunction*FunctionDefnAST::Codegen(){Function*TheFunction=Func_Decl->Codegen();if(TheFunction==0)return0;BasicBlock*BB=BasicBlock::Create(getGlobalContext(),"entry",if(Value*RetVal=Body->Codegen()){returnTheFunction;return0;好了，LLVMIR已经准备好了！这些Codegen()函数会被解析顶层表达式的包装函数调staticvoidHandleDefn()if(FunctionDefnAST*F=func_defn_parser()){if(Function*LF=F->Codegen()){elsestaticvoidHandleTopExpression(){if(FunctionDefnAST*F=top_level_parser()){if(Function*LF=F->Codegen())else所以，在成功解析之后，相应的Codegen()函数会被调用以生成LLVMIR。而dump()函数llvm-config--cxxflags--ldflags--system-libs--libs$clang++-O3toy.cpp`llvm-config--cxxflags--ldflags--system-libs--libs当toy编译器在example程序上运行的时候，它会生成如下的LLVM$./toydefinei32@foo(i32%x,i32%y){%multmp=muli32%y,%addtmp=addi32%x,%multmpreti32%addtmp$catexample2foo(5,6);会得到如下的LLVM$./toyexample2definei32@1(){%calltmp=calli32@foo(i325,i326)reti32%calltmp增加IRstaticFunctionPassManagerFunctionPassManagerGlobal_FP=&My_FP;Function*FunctionDefnAST::Codegen(){Function*TheFunction=Func_Decl->Codegen();if(!TheFunction)return0;BasicBlock*BB=BasicBlock::Create(getGlobalContext(),"entry",if(Value*Return_Value=Body->Codegen()){return0;第3扩展前端并增加JITAST，实现了语法分析器，并且为语言生成了LLVMIR代码。另外，我们也展示了如何在处理条件控制结构——if/then/elseifx<2thenx+yx-ystaticvoidinit_precedence(){Operator_Precedence['<']=Value*BinaryAST::Codegen()case'<'L=Builder.CreateICmpULT(L,R,returnBuilder.CreateZExt(L,现在，LLVMIR将生成一个比较指令及布尔指令作为比较结果，而比较结果则会决定程enumstaticintget_token()if(Identifier_string=="def")returnDEF_TOKEN;if(Identifier_string=="if")returnIF_TOKEN;if(Identifier_string=="then")returnTHEN_TOKEN;if(Identifier_string=="else")returnclassExprIfAST:publicBaseAST{BaseAST*Cond,*Then,*Else;ExprIfAST(BaseAST*cond,BaseAST*then,BaseAST*:Cond(cond),Then(then),Else(else_st){}Value*Codegen()override;staticBaseAST*If_parser(){BaseAST*Cond=expression_parser();if(!Cond)returnif(Current_token!=THEN_TOKEN)return0;BaseAST*Then=expression_parser();if(Then==0)returnIf(Current_token!=ELSE_TOKEN)return0;BaseAST*Else=expression_parser();if(!Else)returnreturnnewExprIfAST(Cond,Then,解析逻辑倒是很简单：首先查找iftoken，以及解析紧随其后的条件表达式。之后是标识thentoken，以及解析true条件表达式；最后是查找elsetoken和解析false条件表达式。staticBaseAST*Base_Parser(){switch(Current_token){caseIF_TOKEN:returnLLVMIR了，让我们来定义Codegen()Value*ExprIfAST::Codegen(){Value*Condtn=Cond->Codegen();if(Condtn==0)returnCondtn=Condtn,Builder.getInt32(0),Function*TheFunc=Builder.GetInsertBlock()-BasicBlock*ThenBBBasicBlock::Create(getGlobalContext(),"then",TheFunc);BasicBlock*ElseBB=BasicBlock::Create(getGlobalContext(),BasicBlock*MergeBB=BasicBlock::Create(getGlobalContext(),Builder.CreateCondBr(Condtn,ThenBB,ElseBB);Value*ThenVal=Then->Codegen();if(ThenVal==0)returnThenBB=Value*ElseVal=Else->Codegen();if(ElseVal==0)returnElseBB=TheFunc-PHINode*Phi=Builder.CreatePHI(Type::getInt32Ty(getGlobalContext()),2,"iftmp");Phi->addIncoming(ThenVal,ThenBB);Phi->addIncoming(ElseVal,ElseBB);returnPhi;$g++-gtoy.cpp`llvm-config--cxxflags--ldflags--system-libs--libscore`-O3-otoy$videfifx<3thenfib(x-1)+fib(x-$./toy;ModuleID='mytargetdatalayout="e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-definei32@fib(i32%x){%cmptmp=icmpulti32%x,bri1%cmptmp,label%ifcont,label ;preds=%subtmp=addi32%x,-%calltmp=calli32@fib(i32%subtmp1=addi32%x,-%calltmp2=calli32@fib(i32%addtmp=addi32%calltmp2,%calltmpbrlabel%ifcont ;preds=%iftmp=phii32[%addtmp,%else],[1,%entry]reti32%iftmp解析器会识别hn结构以及根据条件真假执行的相应语句，将数据存储于中，以构建。之后代码生成器会把转成M，条件语句随之生成。无论条件为真还是假，都会生成关于Clang如何处理C++语言的ifelse语句的一些具体样例，请参见fori=1,i<n,1inx+y;初始化表达式是i1，终止条件是in，第1行代码表示i以1的东西叫PHI节点，它会选择来自不同分支的i，因为我们的IR是SSA（singlestatic基本块（两条不同的路径），为了在SSA形式的LLVMIR中表达这种分支情况，需要用%i=phii32[1,%entry],[%nextvar,%loop有循环变量的AST数据结构，以及定义语法分析器和Codegen()函数来生成LLVMIR：enumToken_Typestaticintget_token()if(Identifier_string==returnif(Identifier_string=="for")returnFOR_TOKEN;if(Identifier_string=="in")returnIN_TOKEN;classExprForAST:publicBaseAST{std::stringVar_Name;BaseAST*Start,*End,*Step,ExprForAST(conststd::string&varname,BaseAST*start,BaseAST*step,BaseAST:Var_Name(varname),Start(start),End(end),Step(step),Body(body){}Value*Codegen()staticBaseAST*For_parser(){if(Current_token!=IDENTIFIER_TOKEN)return0;std::stringIdName=Identifier_string;if(Current_token!='=')return0;BaseAST*Start=expression_parser();if(Start==0)returnif(Current_token!=',')return0;BaseAST*End=expression_parser();if(End==0)returnBaseAST*Step=if(Current_token==','){Step=expression_parser();if(Step==0)returnif(Current_token!=IN_TOKEN)return0;BaseAST*Body=expression_parser();if(Body==0)returnreturnnewExprForAST(IdName,Start,End,Step,再定义Codegen()函数生成LLVMValue*ExprForAST::Codegen()Value*StartVal=Start->Codegen();if(StartVal==0)returnFunction*TheFunction=Builder.GetInsertBlock()->getParent();BasicBlock*PreheaderBB=Builder.GetInsertBlock();BasicBlock*LoopBB=BasicBlock::Create(getGlobalContext(),"loop",TheFunction);PHINode*Variable=Builder.CreatePHI(Type::getInt32Ty(getGlobalContext()),2,Var_Name.c_str());Variable->addIncoming(StartVal,Value*OldVal=Named_Values[Var_Name];Named_Values[Var_Name]=Variable;if(Body->Codegen()==0)return0;Value*StepVal;if(Step){StepVal=Step->Codegen();if(StepVal==0)return}elseStepVal=ConstantInt::get(Type::getInt32Ty(getGlobalContext()),1);Value*NextVar=Builder.CreateAdd(Variable,StepVal,Value*EndCond=End->Codegen();if(EndCond==0)returnEndCond=EndCond,ConstantInt::get(Type::getInt32Ty(getGlobalContext()),0),"loopcond");BasicBlock*LoopEndBB=Builder.GetInsertBlock();BasicBlock*AfterBB=BasicBlock::Create(getGlobalContext(),Builder.CreateCondBr(EndCond,LoopBB,AfterBB);Variable->addIncoming(NextVar,if(OldVal)Named_Values[Var_Name]=OldVal;returnConstant::getNullValue(Type::getInt32Ty(getGlobalConte$g++-gtoy.cpp`llvm-config--cxxflags--ldflags--system-libs--libscore`-O3-otoy$videfprintstar(nfori=1,i<n,1.0inx+1$./toy前面的for循环代码会生成以下的LLVM;ModuleID=‘mytargetdatalayout=“e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-definei32@printstar(i32%n,i32%x){brlabel%i=phii32[1,%entry],[%nextvar,%nextvar=addi32%i,%cmptmp=icmpulti32%i,bri1%cmptmp,label%loop,labelReti320体。然后它会像之前做的那样，把块转成LLVMIR。|（逻辑或运算符）TOY|defbinary|(LHSRHS)ifLHSthenelseifRHSthenenumToken_Typestaticintget_token()if(Identifier_string=="in")returnif(Identifier_string=="binary")returnclassFunctionDeclAST{std::stringFunc_Name;std::vector<std::string>Arguments;boolisOperator;unsignedPrecedence;FunctionDeclAST(conststd::string&name,conststd::vector<std::string>&args,boolisoperator=false,unsignedprec=:Func_Name(name),Arguments(args),isOperator(isoperator),Precedence(prec){}boolisUnaryOp()const{returnisOperator&&==1;boolisBinaryOp()const{returnisOperator&&==2;chargetOperatorName()const{assert(isUnaryOp()||isBinaryOp());returnFunc_Name[Func_Name.size()-1];unsignedgetBinaryPrecedence()const{returnFunctionstaticFunctionDeclAST*func_decl_parser(){std::stringFnName;unsignedKind=unsignedBinaryPrecedence=switch(Current_token){returncaseFnName=Identifier_string;Kind=0;caseUNARY_TOKEN:if(!isascii(Current_token))return0;FnName=FnName+=(char)Current_token;Kind=1;caseif(!isascii(Current_token))return0;FnName=FnName+=(char)Current_token;Kind=2;if(Current_token==NUMERIC_TOKEN)if(Numeric_Val<1||Numeric_Val>100)return0;BinaryPrecedence=(unsigned)Numeric_Val;if(Current_token!='(')return0;std::vector<std::string>Function_Argument_Names;while(next_token()==IDENTIFIER_TOKEN)if(Current_token!=')')return0;if(Kind&&Function_Argument_Names.size()!=Kind)return0;returnnewFunctionDeclAST(FnName,Function_Argument_Names,Kind!=0,BinaryPrecedence);Value*BinaryAST::Codegen(){Value*L=LHS->Codegen();Value*R=RHS->Codegen();switch(Bin_Operator){case'+':returnBuilder.CreateAdd(L,R,"addtmp");case'-':returnBuilder.CreateSub(L,R,"subtmp");case'*':returnBuilder.CreateMul(L,R,"multmp");case'/':returnBuilder.CreateUDiv(L,R,"divtmp");case'<':L=Builder.CreateICmpULT(L,R,returnBuilder.CreateUIToFP(L,Type::getIntTy(getGlobalContext()),defaultFunction*F=TheModule->getFunction(std::string("binary")+Op);Value*Ops[2]={L,R};returnBuilder.CreateCall(F,Ops,Function*FunctionDefnAST::Codegen(){Function*TheFunction=Func_Decl->Codegen();if(!TheFunction)return0;if(Func_Decl-Operator_Precedence[Func_Decl->getOperatorName()]=Func_BasicBlock*BB=BasicBlock::Create(getGlobalContext(),"entry",if(Value*Return_Value=Body->Codegen()){$g++-gtoy.cpp`llvm-config--cxxflags--ldflags--system-libs--libscore`-O3-otoy$videfbinary|5(LHSRHS)ifLHSthenelseifRHSthen$./toyexampleoutput:;ModuleID='mytargetdatalayout="e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"definei32@"binary|"(i32%LHS,i32%RHS){%ifcond=icmpeqi32%LHS,%ifcond1=icmpeqi32%RHS,%.=selecti1%ifcond1,i320,i32%iftmp5=selecti1%ifcond,i32%.,i321reti32%iftmp5defunary!(v)ifvthen如果变量v的值是真，则返回0，否则返回1首先在toy.cpp文件中为一元运算符定义enumenumToken_Type然后识别一元运算符字符串，返回staticintget_token()if(Identifier_string=="in")returnif(Identifier_string=="binary")returnBINARY_TOKEN;if(Identifier_string=="unary")returnUNARY_TOKEN;接着为一元运算符定义classExprUnaryAST:publicBaseAST{charOpcode;BaseAST*Operand;ExprUnaryAST(charopcode,BaseAST:Opcode(opcode),Operand(operand)virtualValuestaticBaseAST*unary_parser()if(!isascii(Current_token)||Current_token=='('||Current_token==',')returnBase_Parser();intOp=Current_token;if(ExprAST*Operand=unary_parser())returnnewExprUnaryAST(Opc,Operand);returnstaticBaseAST*binary_op_parser(intOld_Prec,BaseAST*LHS)while(1)intOperator_Prec=if(Operator_Prec<Old_Prec)returnLHS;intBinOp=Current_token;BaseAST*RHS=unary_parser();if(!RHS)returnintNext_Prec=getBinOpPrecedence();if(Operator_Prec<Next_Prec){RHS=binary_op_parser(Operator_Prec+1,RHS);if(RHS==0)returnLHS=newBinaryAST(std::to_string(BinOp),LHS,staticBaseAST*expression_parser(){BaseAST*LHS=unary_parser();ifreturnreturnbinary_op_parser(0,staticFunctionDeclAST*func_decl_parser(){std::stringFunction_Name=Identifier_string;unsignedKind=0;unsignedBinaryPrecedence=30;switch(Current_token){return0;caseFunction_Name=Identifier_string;Kind=0;caseUNARY_TOKEN:if(!isascii(Current_token))Function_Name="unary";Function_Name+=(char)Current_token;Kind=1;caseif(!isascii(Current_token))return0;Function_Name="binary";Function_Name+=(char)Current_token;Kind=2;if(Current_token==NUMERIC_TOKEN)if(Numeric_Val<1||Numeric_Val>100)return0;BinaryPrecedence=(unsigned)Numeric_Val;if(Current_token!='('){printf("errorinfunctiondeclaration");return0;std::vector<std::string>Function_Argument_Names;while(next_token()==IDENTIFIE