+/// PrototypeAST - This class represents the "prototype" for a function,
+/// which captures its argument names as well as if it is an operator.
+class PrototypeAST {
+ std::string Name;
+ std::vector<std::string> Args;
+public:
+ PrototypeAST(const std::string &name, const std::vector<std::string> &args)
+ : Name(name), Args(args) {}
+
+ Function *Codegen();
+};
+
+/// FunctionAST - This class represents a function definition itself.
+class FunctionAST {
+ PrototypeAST *Proto;
+ ExprAST *Body;
+public:
+ FunctionAST(PrototypeAST *proto, ExprAST *body)
+ : Proto(proto), Body(body) {}
+
+ Function *Codegen();
+};
+
+//===----------------------------------------------------------------------===//
+// Parser
+//===----------------------------------------------------------------------===//
+
+/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
+/// token the parser it 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;
+}
+
+/// 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; }
+
+static ExprAST *ParseExpression();
+
+/// identifierexpr
+/// ::= identifier
+/// ::= identifier '(' expression* ')'
+static ExprAST *ParseIdentifierExpr() {
+ std::string IdName = IdentifierStr;
+
+ getNextToken(); // eat identifier.
+
+ if (CurTok != '(') // Simple variable ref.
+ return new VariableExprAST(IdName);
+
+ // Call.
+ getNextToken(); // eat (
+ std::vector<ExprAST*> Args;
+ if (CurTok != ')') {
+ while (1) {
+ ExprAST *Arg = ParseExpression();
+ if (!Arg) return 0;
+ Args.push_back(Arg);
+
+ if (CurTok == ')') break;
+
+ if (CurTok != ',')
+ return Error("Expected ')' or ',' in argument list");
+ getNextToken();
+ }
+ }
+
+ // 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;
+}
+
+/// primary
+/// ::= identifierexpr
+/// ::= numberexpr
+/// ::= parenexpr
+static ExprAST *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();
+ }
+}
+
+/// binoprhs
+/// ::= ('+' primary)*
+static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *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
+
+ // Parse the primary expression after the binary operator.
+ ExprAST *RHS = ParsePrimary();
+ if (!RHS) return 0;
+
+ // 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;
+ }
+
+ // Merge LHS/RHS.
+ LHS = new BinaryExprAST(BinOp, LHS, RHS);
+ }
+}
+
+/// expression
+/// ::= primary binoprhs
+///
+static ExprAST *ParseExpression() {
+ ExprAST *LHS = ParsePrimary();
+ if (!LHS) return 0;
+
+ return ParseBinOpRHS(0, LHS);
+}
+
+/// prototype
+/// ::= id '(' id* ')'
+static PrototypeAST *ParsePrototype() {
+ if (CurTok != tok_identifier)
+ return ErrorP("Expected function name in prototype");
+
+ std::string FnName = IdentifierStr;
+ getNextToken();
+
+ if (CurTok != '(')
+ return ErrorP("Expected '(' in prototype");
+
+ std::vector<std::string> ArgNames;
+ while (getNextToken() == tok_identifier)
+ ArgNames.push_back(IdentifierStr);
+ if (CurTok != ')')
+ return ErrorP("Expected ')' in prototype");
+
+ // success.
+ getNextToken(); // eat ')'.
+
+ return new PrototypeAST(FnName, ArgNames);
+}
+
+/// 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;
+}
+
+/// toplevelexpr ::= expression
+static FunctionAST *ParseTopLevelExpr() {
+ if (ExprAST *E = ParseExpression()) {
+ // Make an anonymous proto.
+ PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
+ return new FunctionAST(Proto, E);
+ }
+ return 0;
+}
+
+/// external ::= 'extern' prototype
+static PrototypeAST *ParseExtern() {
+ getNextToken(); // eat extern.
+ return ParsePrototype();
+}
+
+//===----------------------------------------------------------------------===//
+// Code Generation
+//===----------------------------------------------------------------------===//
+
+static Module *TheModule;
+static IRBuilder Builder;
+static std::map<std::string, Value*> NamedValues;
+static FunctionPassManager *TheFPM;
+
+Value *ErrorV(const char *Str) { Error(Str); return 0; }
+
+Value *NumberExprAST::Codegen() {
+ return ConstantFP::get(APFloat(Val));
+}
+
+Value *VariableExprAST::Codegen() {
+ // Look this variable up in the function.
+ Value *V = NamedValues[Name];
+ return V ? V : ErrorV("Unknown variable name");
+}
+
+Value *BinaryExprAST::Codegen() {
+ Value *L = LHS->Codegen();
+ Value *R = RHS->Codegen();
+ if (L == 0 || R == 0) return 0;
+
+ switch (Op) {
+ case '+': return Builder.CreateAdd(L, R, "addtmp");
+ case '-': return Builder.CreateSub(L, R, "subtmp");
+ case '*': return Builder.CreateMul(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::DoubleTy, "booltmp");
+ default: return ErrorV("invalid binary operator");
+ }
+}
+
+Value *CallExprAST::Codegen() {
+ // Look up the name in the global module table.
+ Function *CalleeF = TheModule->getFunction(Callee);
+ if (CalleeF == 0)
+ return ErrorV("Unknown function referenced");
+
+ // If argument mismatch error.
+ if (CalleeF->arg_size() != Args.size())
+ return ErrorV("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() == 0) return 0;
+ }
+
+ return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
+}
+
+Function *PrototypeAST::Codegen() {
+ // Make the function type: double(double,double) etc.
+ std::vector<const Type*> Doubles(Args.size(), Type::DoubleTy);
+ FunctionType *FT = FunctionType::get(Type::DoubleTy, 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;
+ }
+ }
+
+ // 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;
+ }
+
+ return F;
+}
+
+Function *FunctionAST::Codegen() {
+ NamedValues.clear();
+
+ Function *TheFunction = Proto->Codegen();
+ if (TheFunction == 0)
+ return 0;
+
+ // Create a new basic block to start insertion into.
+ BasicBlock *BB = BasicBlock::Create("entry", TheFunction);
+ Builder.SetInsertPoint(BB);
+
+ if (Value *RetVal = Body->Codegen()) {
+ // Finish off the function.
+ Builder.CreateRet(RetVal);
+
+ // Validate the generated code, checking for consistency.
+ verifyFunction(*TheFunction);
+
+ // Optimize the function.
+ TheFPM->run(*TheFunction);
+
+ return TheFunction;
+ }
+
+ // Error reading body, remove function.
+ TheFunction->eraseFromParent();
+ return 0;
+}
+
+//===----------------------------------------------------------------------===//
+// Top-Level parsing and JIT Driver
+//===----------------------------------------------------------------------===//
+
+static ExecutionEngine *TheExecutionEngine;
+
+static void HandleDefinition() {
+ if (FunctionAST *F = ParseDefinition()) {
+ if (Function *LF = F->Codegen()) {
+ fprintf(stderr, "Read function definition:");
+ LF->dump();
+ }
+ } else {
+ // Skip token for error recovery.
+ getNextToken();
+ }
+}
+
+static void HandleExtern() {
+ if (PrototypeAST *P = ParseExtern()) {
+ if (Function *F = P->Codegen()) {
+ fprintf(stderr, "Read extern: ");
+ F->dump();
+ }
+ } else {
+ // Skip token for error recovery.
+ getNextToken();
+ }
+}
+
+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 (*)())FPtr;
+ fprintf(stderr, "Evaluated to %f\n", FP());
+ }
+ } else {
+ // Skip token for error recovery.
+ getNextToken();
+ }
+}
+
+/// top ::= definition | external | expression | ';'
+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;
+ }
+ }
+}
+
+
+
+//===----------------------------------------------------------------------===//
+// "Library" functions that can be "extern'd" from user code.
+//===----------------------------------------------------------------------===//
+
+/// putchard - putchar that takes a double and returns 0.
+extern "C"
+double putchard(double X) {
+ putchar((char)X);
+ return 0;
+}
+
+//===----------------------------------------------------------------------===//
+// 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.
+ TheModule = new Module("my cool jit");
+
+ // Create the JIT.
+ TheExecutionEngine = ExecutionEngine::create(TheModule);
+
+ {
+ ExistingModuleProvider OurModuleProvider(TheModule);
+ FunctionPassManager OurFPM(&OurModuleProvider);
+
+ // Set up the optimizer pipeline. Start with registering info about how the
+ // target lays out data structures.
+ OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
+ // 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());
+
+ // Set the global so the code gen can use this.
+ TheFPM = &OurFPM;
+
+ // Run the main "interpreter loop" now.
+ MainLoop();
+
+ TheFPM = 0;
+
+ // Print out all of the generated code.
+ TheModule->dump();
+ } // Free module provider (and thus the module) and pass manager.
+
+ return 0;
+}
+</pre>
+</div>