X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=examples%2FKaleidoscope%2FChapter6%2Ftoy.cpp;h=e1bed45189e0593d36c113036b200757080b7f9f;hp=c5576992c3547e416a03af9f49ebef088092a731;hb=28388315a9e1a4a2c8eaf07e8dc3f3245157df6b;hpb=3ecfc861b4365f341c5c969b40e1afccde676e6f diff --git a/examples/Kaleidoscope/Chapter6/toy.cpp b/examples/Kaleidoscope/Chapter6/toy.cpp index c5576992c35..e1bed45189e 100644 --- a/examples/Kaleidoscope/Chapter6/toy.cpp +++ b/examples/Kaleidoscope/Chapter6/toy.cpp @@ -1,20 +1,22 @@ -#include "llvm/DerivedTypes.h" -#include "llvm/ExecutionEngine/ExecutionEngine.h" -#include "llvm/ExecutionEngine/JIT.h" -#include "llvm/LLVMContext.h" -#include "llvm/Module.h" -#include "llvm/PassManager.h" -#include "llvm/Analysis/Verifier.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/Passes.h" -#include "llvm/Target/TargetData.h" -#include "llvm/Target/TargetSelect.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/LegacyPassManager.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/Verifier.h" +#include "llvm/Support/TargetSelect.h" #include "llvm/Transforms/Scalar.h" -#include "llvm/Support/IRBuilder.h" +#include #include -#include #include +#include #include +#include "../include/KaleidoscopeJIT.h" + using namespace llvm; +using namespace llvm::orc; //===----------------------------------------------------------------------===// // Lexer @@ -26,21 +28,27 @@ enum Token { tok_eof = -1, // commands - tok_def = -2, tok_extern = -3, + tok_def = -2, + tok_extern = -3, // primary - tok_identifier = -4, tok_number = -5, - + tok_identifier = -4, + tok_number = -5, + // control - tok_if = -6, tok_then = -7, tok_else = -8, - tok_for = -9, tok_in = -10, - + tok_if = -6, + tok_then = -7, + tok_else = -8, + tok_for = -9, + tok_in = -10, + // operators - tok_binary = -11, tok_unary = -12 + tok_binary = -11, + tok_unary = -12 }; -static std::string IdentifierStr; // Filled in if tok_identifier -static double NumVal; // Filled in if tok_number +static std::string IdentifierStr; // Filled in if tok_identifier +static double NumVal; // Filled in if tok_number /// gettok - Return the next token from standard input. static int gettok() { @@ -55,19 +63,28 @@ static int gettok() { while (isalnum((LastChar = getchar()))) IdentifierStr += LastChar; - if (IdentifierStr == "def") return tok_def; - if (IdentifierStr == "extern") return tok_extern; - if (IdentifierStr == "if") return tok_if; - if (IdentifierStr == "then") return tok_then; - if (IdentifierStr == "else") return tok_else; - if (IdentifierStr == "for") return tok_for; - if (IdentifierStr == "in") return tok_in; - if (IdentifierStr == "binary") return tok_binary; - if (IdentifierStr == "unary") return tok_unary; + if (IdentifierStr == "def") + return tok_def; + if (IdentifierStr == "extern") + return tok_extern; + if (IdentifierStr == "if") + return tok_if; + if (IdentifierStr == "then") + return tok_then; + if (IdentifierStr == "else") + return tok_else; + if (IdentifierStr == "for") + return tok_for; + if (IdentifierStr == "in") + return tok_in; + if (IdentifierStr == "binary") + return tok_binary; + if (IdentifierStr == "unary") + return tok_unary; return tok_identifier; } - if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+ + if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+ std::string NumStr; do { NumStr += LastChar; @@ -80,13 +97,14 @@ static int gettok() { if (LastChar == '#') { // Comment until end of line. - do LastChar = getchar(); + do + LastChar = 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; @@ -100,78 +118,90 @@ static int gettok() { //===----------------------------------------------------------------------===// // Abstract Syntax Tree (aka Parse Tree) //===----------------------------------------------------------------------===// - +namespace { /// ExprAST - Base class for all expression nodes. class ExprAST { public: virtual ~ExprAST() {} - virtual Value *Codegen() = 0; + 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(); + 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) {} - virtual Value *Codegen(); + VariableExprAST(const std::string &Name) : Name(Name) {} + Value *codegen() override; }; /// UnaryExprAST - Expression class for a unary operator. class UnaryExprAST : public ExprAST { char Opcode; - ExprAST *Operand; + std::unique_ptr Operand; + public: - UnaryExprAST(char opcode, ExprAST *operand) - : Opcode(opcode), Operand(operand) {} - virtual Value *Codegen(); + UnaryExprAST(char Opcode, std::unique_ptr Operand) + : Opcode(Opcode), Operand(std::move(Operand)) {} + Value *codegen() override; }; /// BinaryExprAST - Expression class for a binary operator. class BinaryExprAST : public ExprAST { char Op; - ExprAST *LHS, *RHS; + std::unique_ptr LHS, RHS; + public: - BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs) - : Op(op), LHS(lhs), RHS(rhs) {} - virtual Value *Codegen(); + BinaryExprAST(char Op, std::unique_ptr LHS, + std::unique_ptr 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 Args; + std::vector> Args; + public: - CallExprAST(const std::string &callee, std::vector &args) - : Callee(callee), Args(args) {} - virtual Value *Codegen(); + CallExprAST(const std::string &Callee, + std::vector> Args) + : Callee(Callee), Args(std::move(Args)) {} + Value *codegen() override; }; /// IfExprAST - Expression class for if/then/else. class IfExprAST : public ExprAST { - ExprAST *Cond, *Then, *Else; + std::unique_ptr Cond, Then, Else; + public: - IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else) - : Cond(cond), Then(then), Else(_else) {} - virtual Value *Codegen(); + IfExprAST(std::unique_ptr Cond, std::unique_ptr Then, + std::unique_ptr Else) + : Cond(std::move(Cond)), Then(std::move(Then)), Else(std::move(Else)) {} + Value *codegen() override; }; /// ForExprAST - Expression class for for/in. class ForExprAST : public ExprAST { std::string VarName; - ExprAST *Start, *End, *Step, *Body; + std::unique_ptr Start, End, Step, Body; + public: - ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end, - ExprAST *step, ExprAST *body) - : VarName(varname), Start(start), End(end), Step(step), Body(body) {} - virtual Value *Codegen(); + ForExprAST(const std::string &VarName, std::unique_ptr Start, + std::unique_ptr End, std::unique_ptr Step, + std::unique_ptr Body) + : VarName(VarName), Start(std::move(Start)), End(std::move(End)), + Step(std::move(Step)), Body(std::move(Body)) {} + Value *codegen() override; }; /// PrototypeAST - This class represents the "prototype" for a function, @@ -180,36 +210,40 @@ public: class PrototypeAST { std::string Name; std::vector Args; - bool isOperator; - unsigned Precedence; // Precedence if a binary op. + bool IsOperator; + unsigned Precedence; // Precedence if a binary op. + public: - PrototypeAST(const std::string &name, const std::vector &args, - bool isoperator = false, unsigned prec = 0) - : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {} - - bool isUnaryOp() const { return isOperator && Args.size() == 1; } - bool isBinaryOp() const { return isOperator && Args.size() == 2; } - + PrototypeAST(const std::string &Name, std::vector Args, + bool IsOperator = false, unsigned Prec = 0) + : Name(Name), Args(std::move(Args)), IsOperator(IsOperator), + Precedence(Prec) {} + Function *codegen(); + const std::string &getName() const { return Name; } + + bool isUnaryOp() const { return IsOperator && Args.size() == 1; } + bool isBinaryOp() const { return IsOperator && Args.size() == 2; } + char getOperatorName() const { assert(isUnaryOp() || isBinaryOp()); - return Name[Name.size()-1]; + return Name[Name.size() - 1]; } - + unsigned getBinaryPrecedence() const { return Precedence; } - - Function *Codegen(); }; /// FunctionAST - This class represents a function definition itself. class FunctionAST { - PrototypeAST *Proto; - ExprAST *Body; + std::unique_ptr Proto; + std::unique_ptr Body; + public: - FunctionAST(PrototypeAST *proto, ExprAST *body) - : Proto(proto), Body(body) {} - - Function *Codegen(); + FunctionAST(std::unique_ptr Proto, + std::unique_ptr Body) + : Proto(std::move(Proto)), Body(std::move(Body)) {} + Function *codegen(); }; +} // end anonymous namespace //===----------------------------------------------------------------------===// // Parser @@ -219,9 +253,7 @@ public: /// 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(); -} +static int getNextToken() { return CurTok = gettok(); } /// BinopPrecedence - This holds the precedence for each binary operator that is /// defined. @@ -231,41 +263,69 @@ static std::map BinopPrecedence; static int GetTokPrecedence() { if (!isascii(CurTok)) return -1; - + // Make sure it's a declared binop. int TokPrec = BinopPrecedence[CurTok]; - if (TokPrec <= 0) return -1; + if (TokPrec <= 0) + return -1; return TokPrec; } /// Error* - These are little helper functions for error handling. -ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;} -PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; } -FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; } +std::unique_ptr Error(const char *Str) { + fprintf(stderr, "Error: %s\n", Str); + return nullptr; +} +std::unique_ptr ErrorP(const char *Str) { + Error(Str); + return nullptr; +} + +static std::unique_ptr ParseExpression(); -static ExprAST *ParseExpression(); +/// numberexpr ::= number +static std::unique_ptr ParseNumberExpr() { + auto Result = llvm::make_unique(NumVal); + getNextToken(); // consume the number + return std::move(Result); +} + +/// parenexpr ::= '(' expression ')' +static std::unique_ptr ParseParenExpr() { + getNextToken(); // eat (. + auto V = ParseExpression(); + if (!V) + return nullptr; + + if (CurTok != ')') + return Error("expected ')'"); + getNextToken(); // eat ). + return V; +} /// identifierexpr /// ::= identifier /// ::= identifier '(' expression* ')' -static ExprAST *ParseIdentifierExpr() { +static std::unique_ptr ParseIdentifierExpr() { std::string IdName = IdentifierStr; - - getNextToken(); // eat identifier. - + + getNextToken(); // eat identifier. + if (CurTok != '(') // Simple variable ref. - return new VariableExprAST(IdName); - + return llvm::make_unique(IdName); + // Call. - getNextToken(); // eat ( - std::vector Args; + getNextToken(); // eat ( + std::vector> Args; if (CurTok != ')') { while (1) { - ExprAST *Arg = ParseExpression(); - if (!Arg) return 0; - Args.push_back(Arg); + if (auto Arg = ParseExpression()) + Args.push_back(std::move(Arg)); + else + return nullptr; - if (CurTok == ')') break; + if (CurTok == ')') + break; if (CurTok != ',') return Error("Expected ')' or ',' in argument list"); @@ -275,95 +335,84 @@ static ExprAST *ParseIdentifierExpr() { // Eat the ')'. getNextToken(); - - return new CallExprAST(IdName, Args); -} -/// numberexpr ::= number -static ExprAST *ParseNumberExpr() { - ExprAST *Result = new NumberExprAST(NumVal); - getNextToken(); // consume the number - return Result; -} - -/// parenexpr ::= '(' expression ')' -static ExprAST *ParseParenExpr() { - getNextToken(); // eat (. - ExprAST *V = ParseExpression(); - if (!V) return 0; - - if (CurTok != ')') - return Error("expected ')'"); - getNextToken(); // eat ). - return V; + return llvm::make_unique(IdName, std::move(Args)); } /// ifexpr ::= 'if' expression 'then' expression 'else' expression -static ExprAST *ParseIfExpr() { - getNextToken(); // eat the if. - +static std::unique_ptr ParseIfExpr() { + getNextToken(); // eat the if. + // condition. - ExprAST *Cond = ParseExpression(); - if (!Cond) return 0; - + auto Cond = ParseExpression(); + if (!Cond) + return nullptr; + if (CurTok != tok_then) return Error("expected then"); - getNextToken(); // eat the then - - ExprAST *Then = ParseExpression(); - if (Then == 0) return 0; - + getNextToken(); // eat the then + + auto Then = ParseExpression(); + if (!Then) + return nullptr; + if (CurTok != tok_else) return Error("expected else"); - + getNextToken(); - - ExprAST *Else = ParseExpression(); - if (!Else) return 0; - - return new IfExprAST(Cond, Then, Else); + + auto Else = ParseExpression(); + if (!Else) + return nullptr; + + return llvm::make_unique(std::move(Cond), std::move(Then), + std::move(Else)); } /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression -static ExprAST *ParseForExpr() { - getNextToken(); // eat the for. +static std::unique_ptr ParseForExpr() { + getNextToken(); // eat the for. if (CurTok != tok_identifier) return Error("expected identifier after for"); - + std::string IdName = IdentifierStr; - getNextToken(); // eat identifier. - + getNextToken(); // eat identifier. + if (CurTok != '=') return Error("expected '=' after for"); - getNextToken(); // eat '='. - - - ExprAST *Start = ParseExpression(); - if (Start == 0) return 0; + getNextToken(); // eat '='. + + auto Start = ParseExpression(); + if (!Start) + return nullptr; if (CurTok != ',') return Error("expected ',' after for start value"); getNextToken(); - - ExprAST *End = ParseExpression(); - if (End == 0) return 0; - + + auto End = ParseExpression(); + if (!End) + return nullptr; + // The step value is optional. - ExprAST *Step = 0; + std::unique_ptr Step; if (CurTok == ',') { getNextToken(); Step = ParseExpression(); - if (Step == 0) return 0; + if (!Step) + return nullptr; } - + if (CurTok != tok_in) return Error("expected 'in' after for"); - getNextToken(); // eat 'in'. - - ExprAST *Body = ParseExpression(); - if (Body == 0) return 0; + getNextToken(); // eat 'in'. + + auto Body = ParseExpression(); + if (!Body) + return nullptr; - return new ForExprAST(IdName, Start, End, Step, Body); + return llvm::make_unique(IdName, std::move(Start), std::move(End), + std::move(Step), std::move(Body)); } /// primary @@ -372,86 +421,97 @@ static ExprAST *ParseForExpr() { /// ::= parenexpr /// ::= ifexpr /// ::= forexpr -static ExprAST *ParsePrimary() { +static std::unique_ptr ParsePrimary() { switch (CurTok) { - default: return Error("unknown token when expecting an expression"); - case tok_identifier: return ParseIdentifierExpr(); - case tok_number: return ParseNumberExpr(); - case '(': return ParseParenExpr(); - case tok_if: return ParseIfExpr(); - case tok_for: return ParseForExpr(); + default: + return Error("unknown token when expecting an expression"); + case tok_identifier: + return ParseIdentifierExpr(); + case tok_number: + return ParseNumberExpr(); + case '(': + return ParseParenExpr(); + case tok_if: + return ParseIfExpr(); + case tok_for: + return ParseForExpr(); } } /// unary /// ::= primary /// ::= '!' unary -static ExprAST *ParseUnary() { +static std::unique_ptr ParseUnary() { // If the current token is not an operator, it must be a primary expr. if (!isascii(CurTok) || CurTok == '(' || CurTok == ',') return ParsePrimary(); - + // If this is a unary operator, read it. int Opc = CurTok; getNextToken(); - if (ExprAST *Operand = ParseUnary()) - return new UnaryExprAST(Opc, Operand); - return 0; + if (auto Operand = ParseUnary()) + return llvm::make_unique(Opc, std::move(Operand)); + return nullptr; } /// binoprhs /// ::= ('+' unary)* -static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) { +static std::unique_ptr ParseBinOpRHS(int ExprPrec, + std::unique_ptr LHS) { // If this is a binop, find its precedence. while (1) { 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 - + getNextToken(); // eat binop + // Parse the unary expression after the binary operator. - ExprAST *RHS = ParseUnary(); - if (!RHS) return 0; - + auto RHS = ParseUnary(); + 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, RHS); - if (RHS == 0) return 0; + RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS)); + if (!RHS) + return nullptr; } - + // Merge LHS/RHS. - LHS = new BinaryExprAST(BinOp, LHS, RHS); + LHS = + llvm::make_unique(BinOp, std::move(LHS), std::move(RHS)); } } /// expression /// ::= unary binoprhs /// -static ExprAST *ParseExpression() { - ExprAST *LHS = ParseUnary(); - if (!LHS) return 0; - - return ParseBinOpRHS(0, LHS); +static std::unique_ptr ParseExpression() { + auto LHS = ParseUnary(); + if (!LHS) + return nullptr; + + return ParseBinOpRHS(0, std::move(LHS)); } /// prototype /// ::= id '(' id* ')' /// ::= binary LETTER number? (id, id) /// ::= unary LETTER (id) -static PrototypeAST *ParsePrototype() { +static std::unique_ptr ParsePrototype() { std::string FnName; - + unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary. unsigned BinaryPrecedence = 30; - + switch (CurTok) { default: return ErrorP("Expected function name in prototype"); @@ -477,7 +537,7 @@ static PrototypeAST *ParsePrototype() { FnName += (char)CurTok; Kind = 2; getNextToken(); - + // Read the precedence if present. if (CurTok == tok_number) { if (NumVal < 1 || NumVal > 100) @@ -487,50 +547,53 @@ static PrototypeAST *ParsePrototype() { } break; } - + if (CurTok != '(') return ErrorP("Expected '(' in prototype"); - + std::vector ArgNames; while (getNextToken() == tok_identifier) ArgNames.push_back(IdentifierStr); if (CurTok != ')') return ErrorP("Expected ')' in prototype"); - + // success. - getNextToken(); // eat ')'. - + getNextToken(); // eat ')'. + // Verify right number of names for operator. if (Kind && ArgNames.size() != Kind) return ErrorP("Invalid number of operands for operator"); - - return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence); + + return llvm::make_unique(FnName, ArgNames, Kind != 0, + BinaryPrecedence); } /// definition ::= 'def' prototype expression -static FunctionAST *ParseDefinition() { - getNextToken(); // eat def. - PrototypeAST *Proto = ParsePrototype(); - if (Proto == 0) return 0; - - if (ExprAST *E = ParseExpression()) - return new FunctionAST(Proto, E); - return 0; +static std::unique_ptr ParseDefinition() { + getNextToken(); // eat def. + auto Proto = ParsePrototype(); + if (!Proto) + return nullptr; + + if (auto E = ParseExpression()) + return llvm::make_unique(std::move(Proto), std::move(E)); + return nullptr; } /// toplevelexpr ::= expression -static FunctionAST *ParseTopLevelExpr() { - if (ExprAST *E = ParseExpression()) { +static std::unique_ptr ParseTopLevelExpr() { + if (auto E = ParseExpression()) { // Make an anonymous proto. - PrototypeAST *Proto = new PrototypeAST("", std::vector()); - return new FunctionAST(Proto, E); + auto Proto = llvm::make_unique("__anon_expr", + std::vector()); + return llvm::make_unique(std::move(Proto), std::move(E)); } - return 0; + return nullptr; } /// external ::= 'extern' prototype -static PrototypeAST *ParseExtern() { - getNextToken(); // eat extern. +static std::unique_ptr ParseExtern() { + getNextToken(); // eat extern. return ParsePrototype(); } @@ -538,312 +601,352 @@ static PrototypeAST *ParseExtern() { // Code Generation //===----------------------------------------------------------------------===// -static Module *TheModule; +static std::unique_ptr TheModule; static IRBuilder<> Builder(getGlobalContext()); -static std::map NamedValues; -static FunctionPassManager *TheFPM; +static std::map NamedValues; +static std::unique_ptr TheFPM; +static std::unique_ptr TheJIT; +static std::map> FunctionProtos; + +Value *ErrorV(const char *Str) { + Error(Str); + return nullptr; +} + +Function *getFunction(std::string Name) { + // First, see if the function has already been added to the current module. + if (auto *F = TheModule->getFunction(Name)) + return F; -Value *ErrorV(const char *Str) { Error(Str); return 0; } + // If not, check whether we can codegen the declaration from some existing + // prototype. + auto FI = FunctionProtos.find(Name); + if (FI != FunctionProtos.end()) + return FI->second->codegen(); -Value *NumberExprAST::Codegen() { + // If no existing prototype exists, return null. + return nullptr; +} + +Value *NumberExprAST::codegen() { return ConstantFP::get(getGlobalContext(), APFloat(Val)); } -Value *VariableExprAST::Codegen() { +Value *VariableExprAST::codegen() { // Look this variable up in the function. Value *V = NamedValues[Name]; - return V ? V : ErrorV("Unknown variable name"); + if (!V) + return ErrorV("Unknown variable name"); + return V; } -Value *UnaryExprAST::Codegen() { - Value *OperandV = Operand->Codegen(); - if (OperandV == 0) return 0; - - Function *F = TheModule->getFunction(std::string("unary")+Opcode); - if (F == 0) +Value *UnaryExprAST::codegen() { + Value *OperandV = Operand->codegen(); + if (!OperandV) + return nullptr; + + Function *F = getFunction(std::string("unary") + Opcode); + if (!F) return ErrorV("Unknown unary operator"); - + return Builder.CreateCall(F, OperandV, "unop"); } -Value *BinaryExprAST::Codegen() { - Value *L = LHS->Codegen(); - Value *R = RHS->Codegen(); - if (L == 0 || R == 0) return 0; - +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 '+': + 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(getGlobalContext()), "booltmp"); - default: break; + default: + break; } - + // If it wasn't a builtin binary operator, it must be a user defined one. Emit // a call to it. - Function *F = TheModule->getFunction(std::string("binary")+Op); + Function *F = getFunction(std::string("binary") + Op); assert(F && "binary operator not found!"); - - Value *Ops[] = { L, R }; - return Builder.CreateCall(F, Ops, Ops+2, "binop"); + + Value *Ops[] = {L, R}; + return Builder.CreateCall(F, Ops, "binop"); } -Value *CallExprAST::Codegen() { +Value *CallExprAST::codegen() { // Look up the name in the global module table. - Function *CalleeF = TheModule->getFunction(Callee); - if (CalleeF == 0) + Function *CalleeF = getFunction(Callee); + if (!CalleeF) return ErrorV("Unknown function referenced"); - + // If argument mismatch error. if (CalleeF->arg_size() != Args.size()) return ErrorV("Incorrect # arguments passed"); - std::vector ArgsV; + std::vector ArgsV; for (unsigned i = 0, e = Args.size(); i != e; ++i) { - ArgsV.push_back(Args[i]->Codegen()); - if (ArgsV.back() == 0) return 0; + ArgsV.push_back(Args[i]->codegen()); + if (!ArgsV.back()) + return nullptr; } - - return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp"); + + return Builder.CreateCall(CalleeF, ArgsV, "calltmp"); } -Value *IfExprAST::Codegen() { - Value *CondV = Cond->Codegen(); - if (CondV == 0) return 0; - +Value *IfExprAST::codegen() { + Value *CondV = Cond->codegen(); + if (!CondV) + return nullptr; + // Convert condition to a bool by comparing equal to 0.0. - CondV = Builder.CreateFCmpONE(CondV, - ConstantFP::get(getGlobalContext(), APFloat(0.0)), - "ifcond"); - + CondV = Builder.CreateFCmpONE( + CondV, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "ifcond"); + Function *TheFunction = Builder.GetInsertBlock()->getParent(); - + // Create blocks for the then and else cases. Insert the 'then' block at the // end of the function. - BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction); + BasicBlock *ThenBB = + BasicBlock::Create(getGlobalContext(), "then", TheFunction); BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else"); BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont"); - + Builder.CreateCondBr(CondV, ThenBB, ElseBB); - + // Emit then value. Builder.SetInsertPoint(ThenBB); - - Value *ThenV = Then->Codegen(); - if (ThenV == 0) return 0; - + + Value *ThenV = Then->codegen(); + if (!ThenV) + return nullptr; + Builder.CreateBr(MergeBB); // Codegen of 'Then' can change the current block, update ThenBB for the PHI. ThenBB = Builder.GetInsertBlock(); - + // Emit else block. TheFunction->getBasicBlockList().push_back(ElseBB); Builder.SetInsertPoint(ElseBB); - - Value *ElseV = Else->Codegen(); - if (ElseV == 0) return 0; - + + Value *ElseV = Else->codegen(); + if (!ElseV) + return nullptr; + Builder.CreateBr(MergeBB); // Codegen of 'Else' can change the current block, update ElseBB for the PHI. ElseBB = Builder.GetInsertBlock(); - + // Emit merge block. TheFunction->getBasicBlockList().push_back(MergeBB); Builder.SetInsertPoint(MergeBB); - PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, - "iftmp"); - + PHINode *PN = + Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, "iftmp"); + PN->addIncoming(ThenV, ThenBB); PN->addIncoming(ElseV, ElseBB); return PN; } -Value *ForExprAST::Codegen() { - // Output this as: - // ... - // start = startexpr - // goto loop - // loop: - // variable = phi [start, loopheader], [nextvariable, loopend] - // ... - // bodyexpr - // ... - // loopend: - // step = stepexpr - // nextvariable = variable + step - // endcond = endexpr - // br endcond, loop, endloop - // outloop: - +// Output for-loop as: +// ... +// start = startexpr +// goto loop +// loop: +// variable = phi [start, loopheader], [nextvariable, loopend] +// ... +// bodyexpr +// ... +// loopend: +// step = stepexpr +// nextvariable = variable + step +// endcond = endexpr +// br endcond, loop, endloop +// outloop: +Value *ForExprAST::codegen() { // Emit the start code first, without 'variable' in scope. - Value *StartVal = Start->Codegen(); - if (StartVal == 0) return 0; - + Value *StartVal = Start->codegen(); + if (!StartVal) + return nullptr; + // Make the new basic block for the loop header, inserting after current // block. Function *TheFunction = Builder.GetInsertBlock()->getParent(); BasicBlock *PreheaderBB = Builder.GetInsertBlock(); - BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction); - + BasicBlock *LoopBB = + BasicBlock::Create(getGlobalContext(), "loop", TheFunction); + // Insert an explicit fall through from the current block to the LoopBB. Builder.CreateBr(LoopBB); // Start insertion in LoopBB. Builder.SetInsertPoint(LoopBB); - + // Start the PHI node with an entry for Start. - PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str()); + PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), + 2, VarName.c_str()); Variable->addIncoming(StartVal, PreheaderBB); - + // 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. Value *OldVal = NamedValues[VarName]; NamedValues[VarName] = 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. - if (Body->Codegen() == 0) - return 0; - + if (!Body->codegen()) + return nullptr; + // Emit the step value. - Value *StepVal; + Value *StepVal = nullptr; if (Step) { - StepVal = Step->Codegen(); - if (StepVal == 0) return 0; + StepVal = Step->codegen(); + if (!StepVal) + return nullptr; } else { // If not specified, use 1.0. StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0)); } - + Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar"); // Compute the end condition. - Value *EndCond = End->Codegen(); - if (EndCond == 0) return EndCond; - + Value *EndCond = End->codegen(); + if (!EndCond) + return nullptr; + // Convert condition to a bool by comparing equal to 0.0. - EndCond = Builder.CreateFCmpONE(EndCond, - ConstantFP::get(getGlobalContext(), APFloat(0.0)), - "loopcond"); - + EndCond = Builder.CreateFCmpONE( + EndCond, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "loopcond"); + // Create the "after loop" block and insert it. BasicBlock *LoopEndBB = Builder.GetInsertBlock(); - BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction); - + BasicBlock *AfterBB = + BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction); + // Insert the conditional branch into the end of LoopEndBB. Builder.CreateCondBr(EndCond, LoopBB, AfterBB); - + // Any new code will be inserted in AfterBB. Builder.SetInsertPoint(AfterBB); - + // Add a new entry to the PHI node for the backedge. Variable->addIncoming(NextVar, LoopEndBB); - + // Restore the unshadowed variable. if (OldVal) NamedValues[VarName] = OldVal; else NamedValues.erase(VarName); - // for expr always returns 0.0. return Constant::getNullValue(Type::getDoubleTy(getGlobalContext())); } -Function *PrototypeAST::Codegen() { +Function *PrototypeAST::codegen() { // Make the function type: double(double,double) etc. - std::vector Doubles(Args.size(), - Type::getDoubleTy(getGlobalContext())); - FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()), - Doubles, false); - - Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule); - - // If F conflicted, there was already something named 'Name'. If it has a - // body, don't allow redefinition or reextern. - if (F->getName() != Name) { - // Delete the one we just made and get the existing one. - F->eraseFromParent(); - F = TheModule->getFunction(Name); - - // If F already has a body, reject this. - if (!F->empty()) { - ErrorF("redefinition of function"); - return 0; - } - - // If F took a different number of args, reject. - if (F->arg_size() != Args.size()) { - ErrorF("redefinition of function with different # args"); - return 0; - } - } - + std::vector Doubles(Args.size(), + Type::getDoubleTy(getGlobalContext())); + FunctionType *FT = + FunctionType::get(Type::getDoubleTy(getGlobalContext()), Doubles, false); + + Function *F = + Function::Create(FT, Function::ExternalLinkage, Name, TheModule.get()); + // Set names for all arguments. unsigned Idx = 0; - for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size(); - ++AI, ++Idx) { - AI->setName(Args[Idx]); - - // Add arguments to variable symbol table. - NamedValues[Args[Idx]] = AI; - } - + for (auto &Arg : F->args()) + Arg.setName(Args[Idx++]); + return F; } -Function *FunctionAST::Codegen() { - NamedValues.clear(); - - Function *TheFunction = Proto->Codegen(); - if (TheFunction == 0) - return 0; - +Function *FunctionAST::codegen() { + // Transfer ownership of the prototype to the FunctionProtos map, but keep a + // reference to it for use below. + auto &P = *Proto; + FunctionProtos[Proto->getName()] = std::move(Proto); + Function *TheFunction = getFunction(P.getName()); + if (!TheFunction) + return nullptr; + // If this is an operator, install it. - if (Proto->isBinaryOp()) - BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence(); - + if (P.isBinaryOp()) + BinopPrecedence[P.getOperatorName()] = P.getBinaryPrecedence(); + // Create a new basic block to start insertion into. BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction); Builder.SetInsertPoint(BB); - - if (Value *RetVal = Body->Codegen()) { + + // Record the function arguments in the NamedValues map. + NamedValues.clear(); + for (auto &Arg : TheFunction->args()) + NamedValues[Arg.getName()] = &Arg; + + if (Value *RetVal = Body->codegen()) { // Finish off the function. Builder.CreateRet(RetVal); // Validate the generated code, checking for consistency. verifyFunction(*TheFunction); - // Optimize the function. + // Run the optimizer on the function. TheFPM->run(*TheFunction); - + return TheFunction; } - + // Error reading body, remove function. TheFunction->eraseFromParent(); - if (Proto->isBinaryOp()) + if (P.isBinaryOp()) BinopPrecedence.erase(Proto->getOperatorName()); - return 0; + return nullptr; } //===----------------------------------------------------------------------===// // Top-Level parsing and JIT Driver //===----------------------------------------------------------------------===// -static ExecutionEngine *TheExecutionEngine; +static void InitializeModuleAndPassManager() { + // Open a new module. + TheModule = llvm::make_unique("my cool jit", getGlobalContext()); + TheModule->setDataLayout(TheJIT->getTargetMachine().createDataLayout()); + + // Create a new pass manager attached to it. + TheFPM = llvm::make_unique(TheModule.get()); + + // Provide basic AliasAnalysis support for GVN. + TheFPM->add(createBasicAliasAnalysisPass()); + // 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(); +} static void HandleDefinition() { - if (FunctionAST *F = ParseDefinition()) { - if (Function *LF = F->Codegen()) { + if (auto FnAST = ParseDefinition()) { + if (auto *FnIR = FnAST->codegen()) { fprintf(stderr, "Read function definition:"); - LF->dump(); + FnIR->dump(); + TheJIT->addModule(std::move(TheModule)); + InitializeModuleAndPassManager(); } } else { // Skip token for error recovery. @@ -852,10 +955,11 @@ static void HandleDefinition() { } static void HandleExtern() { - if (PrototypeAST *P = ParseExtern()) { - if (Function *F = P->Codegen()) { + if (auto ProtoAST = ParseExtern()) { + if (auto *FnIR = ProtoAST->codegen()) { fprintf(stderr, "Read extern: "); - F->dump(); + FnIR->dump(); + FunctionProtos[ProtoAST->getName()] = std::move(ProtoAST); } } else { // Skip token for error recovery. @@ -865,15 +969,25 @@ static void HandleExtern() { static void HandleTopLevelExpression() { // Evaluate a top-level expression into an anonymous function. - if (FunctionAST *F = ParseTopLevelExpr()) { - if (Function *LF = F->Codegen()) { - // JIT the function, returning a function pointer. - void *FPtr = TheExecutionEngine->getPointerToFunction(LF); - - // Cast it to the right type (takes no arguments, returns a double) so we - // can call it as a native function. - double (*FP)() = (double (*)())(intptr_t)FPtr; + if (auto FnAST = ParseTopLevelExpr()) { + if (FnAST->codegen()) { + + // JIT the module containing the anonymous expression, keeping a handle so + // we can free it later. + auto H = TheJIT->addModule(std::move(TheModule)); + InitializeModuleAndPassManager(); + + // Search the JIT for the __anon_expr symbol. + auto ExprSymbol = TheJIT->findSymbol("__anon_expr"); + assert(ExprSymbol && "Function not found"); + + // Get the symbol's address and cast it to the right type (takes no + // arguments, returns a double) so we can call it as a native function. + double (*FP)() = (double (*)())(intptr_t)ExprSymbol.getAddress(); fprintf(stderr, "Evaluated to %f\n", FP()); + + // Delete the anonymous expression module from the JIT. + TheJIT->removeModule(H); } } else { // Skip token for error recovery. @@ -886,11 +1000,20 @@ static void MainLoop() { while (1) { fprintf(stderr, "ready> "); switch (CurTok) { - case tok_eof: return; - case ';': getNextToken(); break; // ignore top-level semicolons. - case tok_def: HandleDefinition(); break; - case tok_extern: HandleExtern(); break; - default: HandleTopLevelExpression(); break; + case tok_eof: + return; + case ';': // ignore top-level semicolons. + getNextToken(); + break; + case tok_def: + HandleDefinition(); + break; + case tok_extern: + HandleExtern(); + break; + default: + HandleTopLevelExpression(); + break; } } } @@ -900,15 +1023,13 @@ static void MainLoop() { //===----------------------------------------------------------------------===// /// putchard - putchar that takes a double and returns 0. -extern "C" -double putchard(double X) { +extern "C" double putchard(double X) { putchar((char)X); return 0; } /// printd - printf that takes a double prints it as "%f\n", returning 0. -extern "C" -double printd(double X) { +extern "C" double printd(double X) { printf("%f\n", X); return 0; } @@ -919,58 +1040,26 @@ double printd(double X) { int main() { InitializeNativeTarget(); - LLVMContext &Context = getGlobalContext(); + InitializeNativeTargetAsmPrinter(); + InitializeNativeTargetAsmParser(); // Install standard binary operators. // 1 is lowest precedence. BinopPrecedence['<'] = 10; BinopPrecedence['+'] = 20; BinopPrecedence['-'] = 20; - BinopPrecedence['*'] = 40; // highest. + BinopPrecedence['*'] = 40; // highest. // Prime the first token. fprintf(stderr, "ready> "); getNextToken(); - // Make the module, which holds all the code. - TheModule = new Module("my cool jit", Context); - - // Create the JIT. This takes ownership of the module. - std::string ErrStr; - TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create(); - if (!TheExecutionEngine) { - fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str()); - exit(1); - } - - FunctionPassManager OurFPM(TheModule); - - // Set up the optimizer pipeline. Start with registering info about how the - // target lays out data structures. - OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData())); - // Provide basic AliasAnalysis support for GVN. - OurFPM.add(createBasicAliasAnalysisPass()); - // Do simple "peephole" optimizations and bit-twiddling optzns. - OurFPM.add(createInstructionCombiningPass()); - // Reassociate expressions. - OurFPM.add(createReassociatePass()); - // Eliminate Common SubExpressions. - OurFPM.add(createGVNPass()); - // Simplify the control flow graph (deleting unreachable blocks, etc). - OurFPM.add(createCFGSimplificationPass()); - - OurFPM.doInitialization(); + TheJIT = llvm::make_unique(); - // Set the global so the code gen can use this. - TheFPM = &OurFPM; + InitializeModuleAndPassManager(); // Run the main "interpreter loop" now. MainLoop(); - TheFPM = 0; - - // Print out all of the generated code. - TheModule->dump(); - return 0; }