⊙3.1第三章简介
⊙3.2代码生成设置
⊙3.3表达式代码生成
⊙3.4功能代码生成
⊙3.5程序的结束
3.1 第三章 简介
欢迎来到使用llvm实现语言的第三章，本章将展示使用第二章构建的抽象语法树转换为LLVM IR。
3.2 代码生成设置
为了生成LLVM IR，我们需要在每个AST中定义codegen方法
/// ExprAST - Base class for all expression nodes.class ExprAST {public:virtual ~ExprAST() = default;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) {}Value *codegen() override;};
codegen方法的作用是为该ast节点及其所有的依赖项，生成IR，并且他们都返回一个LLVM Value对象。
其中Value是用于表示LLVM中SSA(SSA 形式意味着每个变量（在 LLVM IR 中通常表示为“值”或“寄存器”）在被定义（赋值）之后，其值就固定不变，直到程序结束或者该变量再次被“定义”。)
首先我们要定义四个全局变量：
//llvm管理着LLVM中间表示IR的各种数据结构包括Type,Constant Global Variables,提供了一个统一环境，确保这些数据的唯一性和一致性。static std::unique_ptr<LLVMContext> TheContext;//IRBuilder：提供了一组丰富的接口，允许开发者以一种更直观、更高级的方式来生成和操作 IR 代码，而无需直接处理底层的 LLVM IR 指令和数据结构static std::unique_ptr<IRBuilder<>> Builder(TheContext);//这个变量作为生成的所有函数和全局变量的容器，代表了整个程序或其中的一部分。static std::unique_ptr<Module> TheModule;//从字符串（变量名）到 Value *（变量值的指针）的映射static std::map<std::string, Value *> NamedValues;
然后需要定义一个LogError方法，勇于报告代码生成期间的错误：
Value *LogErrorV(const char *Str) {LogError(Str);return nullptr;}
3.3表达式代码生成
Value *NumberExprAST::codegen() {return ConstantFP::get(*TheContext, APFloat(Val));}
在LLVM IR中，数值常量通常用使用ConstantFP类表示，这段代码基本上只是创建并返回一个ConstantFP，在LLVM IR中，所有常量都是唯一且共享，因此api使用foo::get(...)习惯用法，而不是new foo(...)或foo::Create(...)。
Value *VariableExprAST::codegen() {// Look this variable up in the function.Value *V = NamedValues[Name];if (!V)LogErrorV("Unknown variable name");return V;}
使用llvm对变量的引用，也非常简单，我们假设变量已经在某处发出，并且其值可用，此代码检查指定的名称是否在映射中，并返回它的值，这个在后面FunctionAST中会被用到，给其添加值。
Value *BinaryExprAST::codegen() {Value *L = LHS->codegen();Value *R = RHS->codegen();if (!L || !R)return nullptr;switch (Op) {case '+':return Builder->CreateFAdd(L, R, "addtmp");case '-':return Builder->CreateFSub(L, R, "subtmp");case '*':return Builder->CreateFMul(L, R, "multmp");case '<':L = Builder->CreateFCmpULT(L, R, "cmptmp");// Convert bool 0/1 to double 0.0 or 1.0return Builder->CreateUIToFP(L, Type::getDoubleTy(TheContext),"booltmp");default:return LogErrorV("invalid binary operator");}}
二元运算符，这里的基本思想是，递归地处理左侧和右侧的表达式，然后计算二进制表达式的结果，然后创建正确的LLVM指令。
在上面LLVM builder开始发力，IRBuilder知道在哪里插入新创建的指令，你所要的就是创建什么指令，要使用哪些操作数，并可选择为生成的指令提供名称。
LLVM的指令对类型的校验非常严格，例如加法指令的左操作和右操作数必须有相同的类型，如果是加法的情况下，加法的结果类型必须与操作数类型匹配。
Value *CallExprAST::codegen() {// Look up the name in the global module table.Function *CalleeF = TheModule->getFunction(Callee);if (!CalleeF)return LogErrorV("Unknown function referenced");// If argument mismatch error.if (CalleeF->arg_size() != Args.size())return LogErrorV("Incorrect # arguments passed");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;}return Builder->CreateCall(CalleeF, ArgsV, "calltmp");}
使用LLVM生成函数的调用代码非常简单，在LLVM的模块的符号表中进行函数名称查找，通过为每个
函数指定与用户指定的名称相同的名称，我们可以使用LLVM符号来解析函数名称。
3.4 功能代码生成
原型和函数的代码生成必须处理许多细节，这使它们的代码不如表达式代码生成漂亮，我们看一下原型的代码生成，它们既用于函数体，也用于外部函数声明。
Function *PrototypeAST::codegen() {// Make the function type: double(double,double) etc.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 *"而不是Value*，因为原型实际上讨论的是函数的外部接口，而不是表达式计算的值，所以它在代码生成时返回对应的LLVM函数是有意义的。
上面的最后一行实际上创建了与原型对应的IR函数，这指示要使用的类型、链接和名称，以及要插入到那个模块。
// Set names for all arguments.unsigned Idx = 0;for (auto &Arg : F->args())Arg.setName(Args[Idx++]);return F;
最后，我们根据原型中给出的名称设置函数每个参数的名称，此步骤不是必须的，但保持名称的一致可以使IR更具可读性，并循序后续代码直接饮用参数的名称，不必在AST中查找它们。
上面的代码经过处理后就有了一个没有主体的函数原型，这就是LLVM IR表示函数声明的方式，对于万花筒语言的extern语句，这就是我们需要做的，但是对于有函数体定义的函数，我们需要进行生成函数体：
Function *FunctionAST::codegen() {// First, check for an existing function from a previous 'extern' declaration.Function *TheFunction = TheModule->getFunction(Proto->getName());if (!TheFunction)TheFunction = Proto->codegen();if (!TheFunction)return nullptr;if (!TheFunction->empty())return (Function*)LogErrorV("Function cannot be redefined.");
对于函数体定义，我们首先在TheModule的函数表中搜索该函数的现有版本，以防已经使extern语句创建了该函数，如果Module::getFunction返回null，则不存在以前的版本，因此我们将从Prototype中生成一个版本。
// Create a new basic block to start insertion into.BasicBlock *BB = BasicBlock::Create(*TheContext, "entry", TheFunction);Builder->SetInsertPoint(BB);// Record the function arguments in the NamedValues map.NamedValues.clear();for (auto &Arg : TheFunction->args())NamedValues[std::string(Arg.getName())] = &Arg;
现在我们到了构建器的设置阶段，第一行创建一个新的基本快，entry，然后插入到function中，然后第二行告诉构建器应将新指令插入到新基本快的末尾，LLVM中的基本块是定义控制流图的函数的重要组成部分，由于我们没有控制流，因此我们的函数只有一个块，在第五章解决好这个问题。
接下来，我们将函数参数添加到 NamedValues 映射（首先将其清除之后），以便 VariableExprAST 节点可以访问它们。
if (Value *RetVal = Body->codegen()) {// Finish off the function.Builder->CreateRet(RetVal);// Validate the generated code, checking for consistency.verifyFunction(*TheFunction);return TheFunction;}
一旦设置了插入点并填充了 NamedValues 映射，我们就为函数的根表达式调用 codegen() 方法。如果没有发生错误，则会发出代码来计算入口块中的表达式并返回计算出的值。假设没有错误，我们然后创建一条 LLVM ret 指令，该指令完成了该功能。函数构建完成后，我们调用 LLVM 提供的 verifyFunction。该函数对生成的代码进行各种一致性检查，以确定我们的编译器是否正确执行了所有操作。使用它很重要：它可以捕获很多错误。一旦函数完成并验证，我们就会返回它。
// Error reading body, remove function.TheFunction->eraseFromParent();return nullptr;}
这里剩下的唯一部分是处理错误情况。为简单起见，我们仅通过删除使用eraseFromParent 方法生成的函数来处理此问题。这允许用户重新定义他们之前错误输入的函数：如果我们不删除它，它将与主体一起存在于符号表中，防止将来重新定义。
不过，这段代码确实有一个错误：如果 FunctionAST::codegen() 方法找到现有的 IR 函数，它不会根据定义自己的原型验证其签名。这意味着早期的“extern”声明将优先于函数定义的签名，这可能会导致 codegen 失败，例如，如果函数参数的命名不同。有多种方法可以修复此错误，看看您能想出什么！这是一个测试用例：
extern foo(a);def foo(b) b; # Error: Unknown variable name. (decl using 'a' takes precedence).
3.5 程序的办法和结束的想法
LLVM的代码生成并没有给我们带来很大帮助，在下方我们展示了，我们进行输入一些代码，然后转换成IR的结果。
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, %multmp3ret double %addtmp4}
3.6 完整代码清单
using namespace llvm;//===----------------------------------------------------------------------===//// Lexer//===----------------------------------------------------------------------===//// The lexer returns tokens [0-255] if it is an unknown character, otherwise one// of these for known things.enum Token {tok_eof = -1,// commandstok_def = -2,tok_extern = -3,// primarytok_identifier = -4,tok_number = -5};static std::string IdentifierStr; // Filled in if tok_identifierstatic double NumVal; // Filled in if tok_number/// gettok - Return the next token from standard input.static int gettok() {static int LastChar = ' ';// Skip any whitespace.while (isspace(LastChar))LastChar = getchar();if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*IdentifierStr = LastChar;while (isalnum((LastChar = getchar())))IdentifierStr += LastChar;if (IdentifierStr == "def")return tok_def;if (IdentifierStr == "extern")return tok_extern;return tok_identifier;}if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+std::string NumStr;do {NumStr += LastChar;LastChar = getchar();} while (isdigit(LastChar) || LastChar == '.');NumVal = strtod(NumStr.c_str(), nullptr);return tok_number;}if (LastChar == '#') {// Comment until end of line.doLastChar = getchar();while (LastChar != EOF && LastChar != 'n' && LastChar != 'r');if (LastChar != EOF)return gettok();}// Check for end of file. Don't eat the EOF.if (LastChar == EOF)return tok_eof;// Otherwise, just return the character as its ascii value.int ThisChar = LastChar;LastChar = getchar();return ThisChar;}//===----------------------------------------------------------------------===//// Abstract Syntax Tree (aka Parse Tree)//===----------------------------------------------------------------------===//namespace {/// ExprAST - Base class for all expression nodes.class ExprAST {public:virtual ~ExprAST() = default;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) {}Value *codegen() override;};/// VariableExprAST - Expression class for referencing a variable, like "a".class VariableExprAST : public ExprAST {std::string Name;public:VariableExprAST(const std::string &Name) : Name(Name) {}Value *codegen() override;};/// BinaryExprAST - Expression class for a binary operator.class BinaryExprAST : public ExprAST {char Op;std::unique_ptr<ExprAST> LHS, RHS;public:BinaryExprAST(char Op, std::unique_ptr<ExprAST> LHS,std::unique_ptr<ExprAST> RHS): Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}Value *codegen() override;};/// CallExprAST - Expression class for function calls.class CallExprAST : public ExprAST {std::string Callee;std::vector<std::unique_ptr<ExprAST>> Args;public:CallExprAST(const std::string &Callee,std::vector<std::unique_ptr<ExprAST>> Args): Callee(Callee), Args(std::move(Args)) {}Value *codegen() override;};/// PrototypeAST - This class represents the "prototype" for a function,/// which captures its name, and its argument names (thus implicitly the number/// of arguments the function takes).class PrototypeAST {std::string Name;std::vector<std::string> Args;public:PrototypeAST(const std::string &Name, std::vector<std::string> Args): Name(Name), Args(std::move(Args)) {}Function *codegen();const std::string &getName() const { return Name; }};/// FunctionAST - This class represents a function definition itself.class FunctionAST {std::unique_ptr<PrototypeAST> Proto;std::unique_ptr<ExprAST> Body;public:FunctionAST(std::unique_ptr<PrototypeAST> Proto,std::unique_ptr<ExprAST> Body): Proto(std::move(Proto)), Body(std::move(Body)) {}Function *codegen();};} // end anonymous namespace//===----------------------------------------------------------------------===//// Parser//===----------------------------------------------------------------------===///// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current/// token the parser is looking at. getNextToken reads another token from the/// lexer and updates CurTok with its results.static int CurTok;static int getNextToken() { return CurTok = gettok(); }/// BinopPrecedence - This holds the precedence for each binary operator that is/// defined.static std::map<char, int> BinopPrecedence;/// GetTokPrecedence - Get the precedence of the pending binary operator token.static int GetTokPrecedence() {if (!isascii(CurTok))return -1;// Make sure it's a declared binop.int TokPrec = BinopPrecedence[CurTok];if (TokPrec <= 0)return -1;return TokPrec;}/// LogError* - These are little helper functions for error handling.std::unique_ptr<ExprAST> LogError(const char *Str) {fprintf(stderr, "Error: %sn", Str);return nullptr;}std::unique_ptr<PrototypeAST> LogErrorP(const char *Str) {LogError(Str);return nullptr;}static std::unique_ptr<ExprAST> ParseExpression();/// numberexpr ::= numberstatic std::unique_ptr<ExprAST> ParseNumberExpr() {auto Result = std::make_unique<NumberExprAST>(NumVal);getNextToken(); // consume the numberreturn std::move(Result);}/// parenexpr ::= '(' expression ')'static std::unique_ptr<ExprAST> ParseParenExpr() {getNextToken(); // eat (.auto V = ParseExpression();if (!V)return nullptr;if (CurTok != ')')return LogError("expected ')'");getNextToken(); // eat ).return V;}/// identifierexpr/// ::= identifier/// ::= identifier '(' expression* ')'static std::unique_ptr<ExprAST> ParseIdentifierExpr() {std::string IdName = IdentifierStr;getNextToken(); // eat identifier.if (CurTok != '(') // Simple variable ref.return std::make_unique<VariableExprAST>(IdName);// Call.getNextToken(); // eat (std::vector<std::unique_ptr<ExprAST>> Args;if (CurTok != ')') {while (true) {if (auto Arg = ParseExpression())Args.push_back(std::move(Arg));elsereturn nullptr;if (CurTok == ')')break;if (CurTok != ',')return LogError("Expected ')' or ',' in argument list");getNextToken();}}// Eat the ')'.getNextToken();return std::make_unique<CallExprAST>(IdName, std::move(Args));}/// primary/// ::= identifierexpr/// ::= numberexpr/// ::= parenexprstatic std::unique_ptr<ExprAST> ParsePrimary() {switch (CurTok) {default:return LogError("unknown token when expecting an expression");case tok_identifier:return ParseIdentifierExpr();case tok_number:return ParseNumberExpr();case '(':return ParseParenExpr();}}/// binoprhs/// ::= ('+' primary)*static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,std::unique_ptr<ExprAST> LHS) {// If this is a binop, find its precedence.while (true) {int TokPrec = GetTokPrecedence();// If this is a binop that binds at least as tightly as the current binop,// consume it, otherwise we are done.if (TokPrec < ExprPrec)return LHS;// Okay, we know this is a binop.int BinOp = CurTok;getNextToken(); // eat binop// Parse the primary expression after the binary operator.auto RHS = ParsePrimary();if (!RHS)return nullptr;// If BinOp binds less tightly with RHS than the operator after RHS, let// the pending operator take RHS as its LHS.int NextPrec = GetTokPrecedence();if (TokPrec < NextPrec) {RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS));if (!RHS)return nullptr;}// Merge LHS/RHS.LHS =std::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS));}}/// expression/// ::= primary binoprhs///static std::unique_ptr<ExprAST> ParseExpression() {auto LHS = ParsePrimary();if (!LHS)return nullptr;return ParseBinOpRHS(0, std::move(LHS));}/// prototype/// ::= id '(' id* ')'static std::unique_ptr<PrototypeAST> ParsePrototype() {if (CurTok != tok_identifier)return LogErrorP("Expected function name in prototype");std::string FnName = IdentifierStr;getNextToken();if (CurTok != '(')return LogErrorP("Expected '(' in prototype");std::vector<std::string> ArgNames;while (getNextToken() == tok_identifier)ArgNames.push_back(IdentifierStr);if (CurTok != ')')return LogErrorP("Expected ')' in prototype");// success.getNextToken(); // eat ')'.return std::make_unique<PrototypeAST>(FnName, std::move(ArgNames));}/// definition ::= 'def' prototype expressionstatic std::unique_ptr<FunctionAST> ParseDefinition() {getNextToken(); // eat def.auto Proto = ParsePrototype();if (!Proto)return nullptr;if (auto E = ParseExpression())return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));return nullptr;}/// toplevelexpr ::= expressionstatic std::unique_ptr<FunctionAST> ParseTopLevelExpr() {if (auto E = ParseExpression()) {// Make an anonymous proto.auto Proto = std::make_unique<PrototypeAST>("__anon_expr",std::vector<std::string>());return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));}return nullptr;}/// external ::= 'extern' prototypestatic std::unique_ptr<PrototypeAST> ParseExtern() {getNextToken(); // eat extern.return ParsePrototype();}//===----------------------------------------------------------------------===//// Code Generation//===----------------------------------------------------------------------===//static std::unique_ptr<LLVMContext> TheContext;static std::unique_ptr<Module> TheModule;static std::unique_ptr<IRBuilder<>> Builder;static std::map<std::string, Value *> NamedValues;Value *LogErrorV(const char *Str) {LogError(Str);return nullptr;}Value *NumberExprAST::codegen() {return ConstantFP::get(*TheContext, APFloat(Val));}Value *VariableExprAST::codegen() {// Look this variable up in the function.Value *V = NamedValues[Name];if (!V)return LogErrorV("Unknown variable name");return V;}Value *BinaryExprAST::codegen() {Value *L = LHS->codegen();Value *R = RHS->codegen();if (!L || !R)return nullptr;switch (Op) {case '+':return Builder->CreateFAdd(L, R, "addtmp");case '-':return Builder->CreateFSub(L, R, "subtmp");case '*':return Builder->CreateFMul(L, R, "multmp");case '<':L = Builder->CreateFCmpULT(L, R, "cmptmp");// Convert bool 0/1 to double 0.0 or 1.0return Builder->CreateUIToFP(L, Type::getDoubleTy(*TheContext), "booltmp");default:return LogErrorV("invalid binary operator");}}Value *CallExprAST::codegen() {// Look up the name in the global module table.Function *CalleeF = TheModule->getFunction(Callee);if (!CalleeF)return LogErrorV("Unknown function referenced");// If argument mismatch error.if (CalleeF->arg_size() != Args.size())return LogErrorV("Incorrect # arguments passed");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;}return Builder->CreateCall(CalleeF, ArgsV, "calltmp");}Function *PrototypeAST::codegen() {// Make the function type: double(double,double) etc.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());// Set names for all arguments.unsigned Idx = 0;for (auto &Arg : F->args())Arg.setName(Args[Idx++]);return F;}Function *FunctionAST::codegen() {// First, check for an existing function from a previous 'extern' declaration.Function *TheFunction = TheModule->getFunction(Proto->getName());if (!TheFunction)TheFunction = Proto->codegen();if (!TheFunction)return nullptr;// Create a new basic block to start insertion into.BasicBlock *BB = BasicBlock::Create(*TheContext, "entry", TheFunction);Builder->SetInsertPoint(BB);// Record the function arguments in the NamedValues map.NamedValues.clear();for (auto &Arg : TheFunction->args())NamedValues[std::string(Arg.getName())] = &Arg;if (Value *RetVal = Body->codegen()) {// Finish off the function.Builder->CreateRet(RetVal);// Validate the generated code, checking for consistency.verifyFunction(*TheFunction);return TheFunction;}// Error reading body, remove function.TheFunction->eraseFromParent();return nullptr;}//===----------------------------------------------------------------------===//// Top-Level parsing and JIT Driver//===----------------------------------------------------------------------===//static void InitializeModule() {// Open a new context and module.TheContext = std::make_unique<LLVMContext>();TheModule = std::make_unique<Module>("my cool jit", *TheContext);// Create a new builder for the module.Builder = std::make_unique<IRBuilder<>>(*TheContext);}static void HandleDefinition() {if (auto FnAST = ParseDefinition()) {if (auto *FnIR = FnAST->codegen()) {fprintf(stderr, "Read function definition:");FnIR->print(errs());fprintf(stderr, "n");}} else {// Skip token for error recovery.getNextToken();}}static void HandleExtern() {if (auto ProtoAST = ParseExtern()) {if (auto *FnIR = ProtoAST->codegen()) {fprintf(stderr, "Read extern: ");FnIR->print(errs());fprintf(stderr, "n");}} else {// Skip token for error recovery.getNextToken();}}static void HandleTopLevelExpression() {// Evaluate a top-level expression into an anonymous function.if (auto FnAST = ParseTopLevelExpr()) {if (auto *FnIR = FnAST->codegen()) {fprintf(stderr, "Read top-level expression:");FnIR->print(errs());fprintf(stderr, "n");// Remove the anonymous expression.FnIR->eraseFromParent();}} else {// Skip token for error recovery.getNextToken();}}/// top ::= definition | external | expression | ';'static void MainLoop() {while (true) {fprintf(stderr, "ready> ");switch (CurTok) {case tok_eof:return;case ';': // ignore top-level semicolons.getNextToken();break;case tok_def:HandleDefinition();break;case tok_extern:HandleExtern();break;default:HandleTopLevelExpression();break;}}}//===----------------------------------------------------------------------===//// Main driver code.//===----------------------------------------------------------------------===//int main() {// Install standard binary operators.// 1 is lowest precedence.BinopPrecedence['<'] = 10;BinopPrecedence['+'] = 20;BinopPrecedence['-'] = 20;BinopPrecedence['*'] = 40; // highest.// Prime the first token.fprintf(stderr, "ready> ");getNextToken();// Make the module, which holds all the code.InitializeModule();// Run the main "interpreter loop" now.MainLoop();// Print out all of the generated code.TheModule->print(errs(), nullptr);return 0;}
学习逆向和爬虫可以关注我朋友：
我是BestToYou,分享工作或日常学习中关于Android、iOS逆向及安全防护的一些思路和一些自己闲暇时刻调试的一些程序,文中若有错误或者不足的地方,恳请大家联系我批评指正。
扫码加我为好友
原文始发于微信公众号（二进制科学）：第三章：Kaleidoscope LLVM IR的生成
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论