1 #include "llvm/Analysis/Passes.h"
2 #include "llvm/ExecutionEngine/ExecutionEngine.h"
3 #include "llvm/ExecutionEngine/MCJIT.h"
4 #include "llvm/ExecutionEngine/SectionMemoryManager.h"
5 #include "llvm/IR/DataLayout.h"
6 #include "llvm/IR/DerivedTypes.h"
7 #include "llvm/IR/IRBuilder.h"
8 #include "llvm/IR/LLVMContext.h"
9 #include "llvm/IR/Module.h"
10 #include "llvm/IR/Verifier.h"
11 #include "llvm/PassManager.h"
12 #include "llvm/Support/TargetSelect.h"
13 #include "llvm/Transforms/Scalar.h"
21 //===----------------------------------------------------------------------===//
23 //===----------------------------------------------------------------------===//
25 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
26 // of these for known things.
46 static std::string IdentifierStr; // Filled in if tok_identifier
47 static double NumVal; // Filled in if tok_number
49 /// gettok - Return the next token from standard input.
51 static int LastChar = ' ';
53 // Skip any whitespace.
54 while (isspace(LastChar))
57 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
58 IdentifierStr = LastChar;
59 while (isalnum((LastChar = getchar())))
60 IdentifierStr += LastChar;
62 if (IdentifierStr == "def")
64 if (IdentifierStr == "extern")
66 if (IdentifierStr == "if")
68 if (IdentifierStr == "then")
70 if (IdentifierStr == "else")
72 if (IdentifierStr == "for")
74 if (IdentifierStr == "in")
76 return tok_identifier;
79 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
84 } while (isdigit(LastChar) || LastChar == '.');
86 NumVal = strtod(NumStr.c_str(), 0);
90 if (LastChar == '#') {
91 // Comment until end of line.
94 while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
100 // Check for end of file. Don't eat the EOF.
104 // Otherwise, just return the character as its ascii value.
105 int ThisChar = LastChar;
106 LastChar = getchar();
110 //===----------------------------------------------------------------------===//
111 // Abstract Syntax Tree (aka Parse Tree)
112 //===----------------------------------------------------------------------===//
114 /// ExprAST - Base class for all expression nodes.
117 virtual ~ExprAST() {}
118 virtual Value *Codegen() = 0;
121 /// NumberExprAST - Expression class for numeric literals like "1.0".
122 class NumberExprAST : public ExprAST {
126 NumberExprAST(double val) : Val(val) {}
127 virtual Value *Codegen();
130 /// VariableExprAST - Expression class for referencing a variable, like "a".
131 class VariableExprAST : public ExprAST {
135 VariableExprAST(const std::string &name) : Name(name) {}
136 virtual Value *Codegen();
139 /// BinaryExprAST - Expression class for a binary operator.
140 class BinaryExprAST : public ExprAST {
145 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
146 : Op(op), LHS(lhs), RHS(rhs) {}
147 virtual Value *Codegen();
150 /// CallExprAST - Expression class for function calls.
151 class CallExprAST : public ExprAST {
153 std::vector<ExprAST *> Args;
156 CallExprAST(const std::string &callee, std::vector<ExprAST *> &args)
157 : Callee(callee), Args(args) {}
158 virtual Value *Codegen();
161 /// IfExprAST - Expression class for if/then/else.
162 class IfExprAST : public ExprAST {
163 ExprAST *Cond, *Then, *Else;
166 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
167 : Cond(cond), Then(then), Else(_else) {}
168 virtual Value *Codegen();
171 /// ForExprAST - Expression class for for/in.
172 class ForExprAST : public ExprAST {
174 ExprAST *Start, *End, *Step, *Body;
177 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
178 ExprAST *step, ExprAST *body)
179 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
180 virtual Value *Codegen();
183 /// PrototypeAST - This class represents the "prototype" for a function,
184 /// which captures its name, and its argument names (thus implicitly the number
185 /// of arguments the function takes).
188 std::vector<std::string> Args;
191 PrototypeAST(const std::string &name, const std::vector<std::string> &args)
192 : Name(name), Args(args) {}
197 /// FunctionAST - This class represents a function definition itself.
203 FunctionAST(PrototypeAST *proto, ExprAST *body) : Proto(proto), Body(body) {}
207 } // end anonymous namespace
209 //===----------------------------------------------------------------------===//
211 //===----------------------------------------------------------------------===//
213 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
214 /// token the parser is looking at. getNextToken reads another token from the
215 /// lexer and updates CurTok with its results.
217 static int getNextToken() { return CurTok = gettok(); }
219 /// BinopPrecedence - This holds the precedence for each binary operator that is
221 static std::map<char, int> BinopPrecedence;
223 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
224 static int GetTokPrecedence() {
225 if (!isascii(CurTok))
228 // Make sure it's a declared binop.
229 int TokPrec = BinopPrecedence[CurTok];
235 /// Error* - These are little helper functions for error handling.
236 ExprAST *Error(const char *Str) {
237 fprintf(stderr, "Error: %s\n", Str);
240 PrototypeAST *ErrorP(const char *Str) {
244 FunctionAST *ErrorF(const char *Str) {
249 static ExprAST *ParseExpression();
253 /// ::= identifier '(' expression* ')'
254 static ExprAST *ParseIdentifierExpr() {
255 std::string IdName = IdentifierStr;
257 getNextToken(); // eat identifier.
259 if (CurTok != '(') // Simple variable ref.
260 return new VariableExprAST(IdName);
263 getNextToken(); // eat (
264 std::vector<ExprAST *> Args;
267 ExprAST *Arg = ParseExpression();
276 return Error("Expected ')' or ',' in argument list");
284 return new CallExprAST(IdName, Args);
287 /// numberexpr ::= number
288 static ExprAST *ParseNumberExpr() {
289 ExprAST *Result = new NumberExprAST(NumVal);
290 getNextToken(); // consume the number
294 /// parenexpr ::= '(' expression ')'
295 static ExprAST *ParseParenExpr() {
296 getNextToken(); // eat (.
297 ExprAST *V = ParseExpression();
302 return Error("expected ')'");
303 getNextToken(); // eat ).
307 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
308 static ExprAST *ParseIfExpr() {
309 getNextToken(); // eat the if.
312 ExprAST *Cond = ParseExpression();
316 if (CurTok != tok_then)
317 return Error("expected then");
318 getNextToken(); // eat the then
320 ExprAST *Then = ParseExpression();
324 if (CurTok != tok_else)
325 return Error("expected else");
329 ExprAST *Else = ParseExpression();
333 return new IfExprAST(Cond, Then, Else);
336 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
337 static ExprAST *ParseForExpr() {
338 getNextToken(); // eat the for.
340 if (CurTok != tok_identifier)
341 return Error("expected identifier after for");
343 std::string IdName = IdentifierStr;
344 getNextToken(); // eat identifier.
347 return Error("expected '=' after for");
348 getNextToken(); // eat '='.
350 ExprAST *Start = ParseExpression();
354 return Error("expected ',' after for start value");
357 ExprAST *End = ParseExpression();
361 // The step value is optional.
365 Step = ParseExpression();
370 if (CurTok != tok_in)
371 return Error("expected 'in' after for");
372 getNextToken(); // eat 'in'.
374 ExprAST *Body = ParseExpression();
378 return new ForExprAST(IdName, Start, End, Step, Body);
382 /// ::= identifierexpr
387 static ExprAST *ParsePrimary() {
390 return Error("unknown token when expecting an expression");
392 return ParseIdentifierExpr();
394 return ParseNumberExpr();
396 return ParseParenExpr();
398 return ParseIfExpr();
400 return ParseForExpr();
405 /// ::= ('+' primary)*
406 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
407 // If this is a binop, find its precedence.
409 int TokPrec = GetTokPrecedence();
411 // If this is a binop that binds at least as tightly as the current binop,
412 // consume it, otherwise we are done.
413 if (TokPrec < ExprPrec)
416 // Okay, we know this is a binop.
418 getNextToken(); // eat binop
420 // Parse the primary expression after the binary operator.
421 ExprAST *RHS = ParsePrimary();
425 // If BinOp binds less tightly with RHS than the operator after RHS, let
426 // the pending operator take RHS as its LHS.
427 int NextPrec = GetTokPrecedence();
428 if (TokPrec < NextPrec) {
429 RHS = ParseBinOpRHS(TokPrec + 1, RHS);
435 LHS = new BinaryExprAST(BinOp, LHS, RHS);
440 /// ::= primary binoprhs
442 static ExprAST *ParseExpression() {
443 ExprAST *LHS = ParsePrimary();
447 return ParseBinOpRHS(0, LHS);
451 /// ::= id '(' id* ')'
452 static PrototypeAST *ParsePrototype() {
453 if (CurTok != tok_identifier)
454 return ErrorP("Expected function name in prototype");
456 std::string FnName = IdentifierStr;
460 return ErrorP("Expected '(' in prototype");
462 std::vector<std::string> ArgNames;
463 while (getNextToken() == tok_identifier)
464 ArgNames.push_back(IdentifierStr);
466 return ErrorP("Expected ')' in prototype");
469 getNextToken(); // eat ')'.
471 return new PrototypeAST(FnName, ArgNames);
474 /// definition ::= 'def' prototype expression
475 static FunctionAST *ParseDefinition() {
476 getNextToken(); // eat def.
477 PrototypeAST *Proto = ParsePrototype();
481 if (ExprAST *E = ParseExpression())
482 return new FunctionAST(Proto, E);
486 /// toplevelexpr ::= expression
487 static FunctionAST *ParseTopLevelExpr() {
488 if (ExprAST *E = ParseExpression()) {
489 // Make an anonymous proto.
490 PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
491 return new FunctionAST(Proto, E);
496 /// external ::= 'extern' prototype
497 static PrototypeAST *ParseExtern() {
498 getNextToken(); // eat extern.
499 return ParsePrototype();
502 //===----------------------------------------------------------------------===//
504 //===----------------------------------------------------------------------===//
506 static Module *TheModule;
507 static IRBuilder<> Builder(getGlobalContext());
508 static std::map<std::string, Value *> NamedValues;
509 static FunctionPassManager *TheFPM;
511 Value *ErrorV(const char *Str) {
516 Value *NumberExprAST::Codegen() {
517 return ConstantFP::get(getGlobalContext(), APFloat(Val));
520 Value *VariableExprAST::Codegen() {
521 // Look this variable up in the function.
522 Value *V = NamedValues[Name];
523 return V ? V : ErrorV("Unknown variable name");
526 Value *BinaryExprAST::Codegen() {
527 Value *L = LHS->Codegen();
528 Value *R = RHS->Codegen();
529 if (L == 0 || R == 0)
534 return Builder.CreateFAdd(L, R, "addtmp");
536 return Builder.CreateFSub(L, R, "subtmp");
538 return Builder.CreateFMul(L, R, "multmp");
540 L = Builder.CreateFCmpULT(L, R, "cmptmp");
541 // Convert bool 0/1 to double 0.0 or 1.0
542 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
545 return ErrorV("invalid binary operator");
549 Value *CallExprAST::Codegen() {
550 // Look up the name in the global module table.
551 Function *CalleeF = TheModule->getFunction(Callee);
553 return ErrorV("Unknown function referenced");
555 // If argument mismatch error.
556 if (CalleeF->arg_size() != Args.size())
557 return ErrorV("Incorrect # arguments passed");
559 std::vector<Value *> ArgsV;
560 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
561 ArgsV.push_back(Args[i]->Codegen());
562 if (ArgsV.back() == 0)
566 return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
569 Value *IfExprAST::Codegen() {
570 Value *CondV = Cond->Codegen();
574 // Convert condition to a bool by comparing equal to 0.0.
575 CondV = Builder.CreateFCmpONE(
576 CondV, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "ifcond");
578 Function *TheFunction = Builder.GetInsertBlock()->getParent();
580 // Create blocks for the then and else cases. Insert the 'then' block at the
581 // end of the function.
583 BasicBlock::Create(getGlobalContext(), "then", TheFunction);
584 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
585 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
587 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
590 Builder.SetInsertPoint(ThenBB);
592 Value *ThenV = Then->Codegen();
596 Builder.CreateBr(MergeBB);
597 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
598 ThenBB = Builder.GetInsertBlock();
601 TheFunction->getBasicBlockList().push_back(ElseBB);
602 Builder.SetInsertPoint(ElseBB);
604 Value *ElseV = Else->Codegen();
608 Builder.CreateBr(MergeBB);
609 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
610 ElseBB = Builder.GetInsertBlock();
613 TheFunction->getBasicBlockList().push_back(MergeBB);
614 Builder.SetInsertPoint(MergeBB);
616 Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, "iftmp");
618 PN->addIncoming(ThenV, ThenBB);
619 PN->addIncoming(ElseV, ElseBB);
623 Value *ForExprAST::Codegen() {
629 // variable = phi [start, loopheader], [nextvariable, loopend]
635 // nextvariable = variable + step
637 // br endcond, loop, endloop
640 // Emit the start code first, without 'variable' in scope.
641 Value *StartVal = Start->Codegen();
645 // Make the new basic block for the loop header, inserting after current
647 Function *TheFunction = Builder.GetInsertBlock()->getParent();
648 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
650 BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
652 // Insert an explicit fall through from the current block to the LoopBB.
653 Builder.CreateBr(LoopBB);
655 // Start insertion in LoopBB.
656 Builder.SetInsertPoint(LoopBB);
658 // Start the PHI node with an entry for Start.
659 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()),
661 Variable->addIncoming(StartVal, PreheaderBB);
663 // Within the loop, the variable is defined equal to the PHI node. If it
664 // shadows an existing variable, we have to restore it, so save it now.
665 Value *OldVal = NamedValues[VarName];
666 NamedValues[VarName] = Variable;
668 // Emit the body of the loop. This, like any other expr, can change the
669 // current BB. Note that we ignore the value computed by the body, but don't
671 if (Body->Codegen() == 0)
674 // Emit the step value.
677 StepVal = Step->Codegen();
681 // If not specified, use 1.0.
682 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
685 Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");
687 // Compute the end condition.
688 Value *EndCond = End->Codegen();
692 // Convert condition to a bool by comparing equal to 0.0.
693 EndCond = Builder.CreateFCmpONE(
694 EndCond, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "loopcond");
696 // Create the "after loop" block and insert it.
697 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
698 BasicBlock *AfterBB =
699 BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
701 // Insert the conditional branch into the end of LoopEndBB.
702 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
704 // Any new code will be inserted in AfterBB.
705 Builder.SetInsertPoint(AfterBB);
707 // Add a new entry to the PHI node for the backedge.
708 Variable->addIncoming(NextVar, LoopEndBB);
710 // Restore the unshadowed variable.
712 NamedValues[VarName] = OldVal;
714 NamedValues.erase(VarName);
716 // for expr always returns 0.0.
717 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
720 Function *PrototypeAST::Codegen() {
721 // Make the function type: double(double,double) etc.
722 std::vector<Type *> Doubles(Args.size(),
723 Type::getDoubleTy(getGlobalContext()));
725 FunctionType::get(Type::getDoubleTy(getGlobalContext()), Doubles, false);
728 Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
730 // If F conflicted, there was already something named 'Name'. If it has a
731 // body, don't allow redefinition or reextern.
732 if (F->getName() != Name) {
733 // Delete the one we just made and get the existing one.
734 F->eraseFromParent();
735 F = TheModule->getFunction(Name);
737 // If F already has a body, reject this.
739 ErrorF("redefinition of function");
743 // If F took a different number of args, reject.
744 if (F->arg_size() != Args.size()) {
745 ErrorF("redefinition of function with different # args");
750 // Set names for all arguments.
752 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
754 AI->setName(Args[Idx]);
756 // Add arguments to variable symbol table.
757 NamedValues[Args[Idx]] = AI;
763 Function *FunctionAST::Codegen() {
766 Function *TheFunction = Proto->Codegen();
767 if (TheFunction == 0)
770 // Create a new basic block to start insertion into.
771 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
772 Builder.SetInsertPoint(BB);
774 if (Value *RetVal = Body->Codegen()) {
775 // Finish off the function.
776 Builder.CreateRet(RetVal);
778 // Validate the generated code, checking for consistency.
779 verifyFunction(*TheFunction);
781 // Optimize the function.
782 TheFPM->run(*TheFunction);
787 // Error reading body, remove function.
788 TheFunction->eraseFromParent();
792 //===----------------------------------------------------------------------===//
793 // Top-Level parsing and JIT Driver
794 //===----------------------------------------------------------------------===//
796 static ExecutionEngine *TheExecutionEngine;
798 static void HandleDefinition() {
799 if (FunctionAST *F = ParseDefinition()) {
800 if (Function *LF = F->Codegen()) {
801 fprintf(stderr, "Read function definition:");
805 // Skip token for error recovery.
810 static void HandleExtern() {
811 if (PrototypeAST *P = ParseExtern()) {
812 if (Function *F = P->Codegen()) {
813 fprintf(stderr, "Read extern: ");
817 // Skip token for error recovery.
822 static void HandleTopLevelExpression() {
823 // Evaluate a top-level expression into an anonymous function.
824 if (FunctionAST *F = ParseTopLevelExpr()) {
825 if (Function *LF = F->Codegen()) {
826 TheExecutionEngine->finalizeObject();
827 // JIT the function, returning a function pointer.
828 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
830 // Cast it to the right type (takes no arguments, returns a double) so we
831 // can call it as a native function.
832 double (*FP)() = (double (*)())(intptr_t)FPtr;
833 fprintf(stderr, "Evaluated to %f\n", FP());
836 // Skip token for error recovery.
841 /// top ::= definition | external | expression | ';'
842 static void MainLoop() {
844 fprintf(stderr, "ready> ");
850 break; // ignore top-level semicolons.
858 HandleTopLevelExpression();
864 //===----------------------------------------------------------------------===//
865 // "Library" functions that can be "extern'd" from user code.
866 //===----------------------------------------------------------------------===//
868 /// putchard - putchar that takes a double and returns 0.
869 extern "C" double putchard(double X) {
874 //===----------------------------------------------------------------------===//
876 //===----------------------------------------------------------------------===//
879 InitializeNativeTarget();
880 InitializeNativeTargetAsmPrinter();
881 InitializeNativeTargetAsmParser();
882 LLVMContext &Context = getGlobalContext();
884 // Install standard binary operators.
885 // 1 is lowest precedence.
886 BinopPrecedence['<'] = 10;
887 BinopPrecedence['+'] = 20;
888 BinopPrecedence['-'] = 20;
889 BinopPrecedence['*'] = 40; // highest.
891 // Prime the first token.
892 fprintf(stderr, "ready> ");
895 // Make the module, which holds all the code.
896 std::unique_ptr<Module> Owner = make_unique<Module>("my cool jit", Context);
897 TheModule = Owner.get();
899 // Create the JIT. This takes ownership of the module.
902 EngineBuilder(std::move(Owner))
903 .setErrorStr(&ErrStr)
904 .setMCJITMemoryManager(llvm::make_unique<SectionMemoryManager>())
906 if (!TheExecutionEngine) {
907 fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
911 FunctionPassManager OurFPM(TheModule);
913 // Set up the optimizer pipeline. Start with registering info about how the
914 // target lays out data structures.
915 TheModule->setDataLayout(TheExecutionEngine->getDataLayout());
916 OurFPM.add(new DataLayoutPass());
917 // Provide basic AliasAnalysis support for GVN.
918 OurFPM.add(createBasicAliasAnalysisPass());
919 // Do simple "peephole" optimizations and bit-twiddling optzns.
920 OurFPM.add(createInstructionCombiningPass());
921 // Reassociate expressions.
922 OurFPM.add(createReassociatePass());
923 // Eliminate Common SubExpressions.
924 OurFPM.add(createGVNPass());
925 // Simplify the control flow graph (deleting unreachable blocks, etc).
926 OurFPM.add(createCFGSimplificationPass());
928 OurFPM.doInitialization();
930 // Set the global so the code gen can use this.
933 // Run the main "interpreter loop" now.
938 // Print out all of the generated code.