1 #include "llvm/ADT/STLExtras.h" 2 #include "llvm/Analysis/Passes.h" 3 #include "llvm/IR/IRBuilder.h" 4 #include "llvm/IR/LLVMContext.h" 5 #include "llvm/IR/LegacyPassManager.h" 6 #include "llvm/IR/Module.h" 7 #include "llvm/IR/Verifier.h" 8 #include "llvm/Support/TargetSelect.h" 9 #include "llvm/Transforms/Scalar.h" 10 #include <cctype> 11 #include <cstdio> 12 #include <map> 13 #include <string> 14 #include <vector> 15 #include "../include/KaleidoscopeJIT.h" 16 17 using namespace llvm; 18 using namespace llvm::orc; 19 20 //===----------------------------------------------------------------------===// 21 // Lexer 22 //===----------------------------------------------------------------------===// 23 24 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one 25 // of these for known things. 26 enum Token { 27 tok_eof = -1, 28 29 // commands 30 tok_def = -2, 31 tok_extern = -3, 32 33 // primary 34 tok_identifier = -4, 35 tok_number = -5, 36 37 // control 38 tok_if = -6, 39 tok_then = -7, 40 tok_else = -8, 41 tok_for = -9, 42 tok_in = -10 43 }; 44 45 static std::string IdentifierStr; // Filled in if tok_identifier 46 static double NumVal; // Filled in if tok_number 47 48 /// gettok - Return the next token from standard input. 49 static int gettok() { 50 static int LastChar = ' '; 51 52 // Skip any whitespace. 53 while (isspace(LastChar)) 54 LastChar = getchar(); 55 56 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]* 57 IdentifierStr = LastChar; 58 while (isalnum((LastChar = getchar()))) 59 IdentifierStr += LastChar; 60 61 if (IdentifierStr == "def") 62 return tok_def; 63 if (IdentifierStr == "extern") 64 return tok_extern; 65 if (IdentifierStr == "if") 66 return tok_if; 67 if (IdentifierStr == "then") 68 return tok_then; 69 if (IdentifierStr == "else") 70 return tok_else; 71 if (IdentifierStr == "for") 72 return tok_for; 73 if (IdentifierStr == "in") 74 return tok_in; 75 return tok_identifier; 76 } 77 78 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+ 79 std::string NumStr; 80 do { 81 NumStr += LastChar; 82 LastChar = getchar(); 83 } while (isdigit(LastChar) || LastChar == '.'); 84 85 NumVal = strtod(NumStr.c_str(), nullptr); 86 return tok_number; 87 } 88 89 if (LastChar == '#') { 90 // Comment until end of line. 91 do 92 LastChar = getchar(); 93 while (LastChar != EOF && LastChar != '\n' && LastChar != '\r'); 94 95 if (LastChar != EOF) 96 return gettok(); 97 } 98 99 // Check for end of file. Don't eat the EOF. 100 if (LastChar == EOF) 101 return tok_eof; 102 103 // Otherwise, just return the character as its ascii value. 104 int ThisChar = LastChar; 105 LastChar = getchar(); 106 return ThisChar; 107 } 108 109 //===----------------------------------------------------------------------===// 110 // Abstract Syntax Tree (aka Parse Tree) 111 //===----------------------------------------------------------------------===// 112 namespace { 113 /// ExprAST - Base class for all expression nodes. 114 class ExprAST { 115 public: 116 virtual ~ExprAST() {} 117 virtual Value *codegen() = 0; 118 }; 119 120 /// NumberExprAST - Expression class for numeric literals like "1.0". 121 class NumberExprAST : public ExprAST { 122 double Val; 123 124 public: 125 NumberExprAST(double Val) : Val(Val) {} 126 Value *codegen() override; 127 }; 128 129 /// VariableExprAST - Expression class for referencing a variable, like "a". 130 class VariableExprAST : public ExprAST { 131 std::string Name; 132 133 public: 134 VariableExprAST(const std::string &Name) : Name(Name) {} 135 Value *codegen() override; 136 }; 137 138 /// BinaryExprAST - Expression class for a binary operator. 139 class BinaryExprAST : public ExprAST { 140 char Op; 141 std::unique_ptr<ExprAST> LHS, RHS; 142 143 public: 144 BinaryExprAST(char Op, std::unique_ptr<ExprAST> LHS, 145 std::unique_ptr<ExprAST> RHS) 146 : Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {} 147 Value *codegen() override; 148 }; 149 150 /// CallExprAST - Expression class for function calls. 151 class CallExprAST : public ExprAST { 152 std::string Callee; 153 std::vector<std::unique_ptr<ExprAST>> Args; 154 155 public: 156 CallExprAST(const std::string &Callee, 157 std::vector<std::unique_ptr<ExprAST>> Args) 158 : Callee(Callee), Args(std::move(Args)) {} 159 Value *codegen() override; 160 }; 161 162 /// IfExprAST - Expression class for if/then/else. 163 class IfExprAST : public ExprAST { 164 std::unique_ptr<ExprAST> Cond, Then, Else; 165 166 public: 167 IfExprAST(std::unique_ptr<ExprAST> Cond, std::unique_ptr<ExprAST> Then, 168 std::unique_ptr<ExprAST> Else) 169 : Cond(std::move(Cond)), Then(std::move(Then)), Else(std::move(Else)) {} 170 Value *codegen() override; 171 }; 172 173 /// ForExprAST - Expression class for for/in. 174 class ForExprAST : public ExprAST { 175 std::string VarName; 176 std::unique_ptr<ExprAST> Start, End, Step, Body; 177 178 public: 179 ForExprAST(const std::string &VarName, std::unique_ptr<ExprAST> Start, 180 std::unique_ptr<ExprAST> End, std::unique_ptr<ExprAST> Step, 181 std::unique_ptr<ExprAST> Body) 182 : VarName(VarName), Start(std::move(Start)), End(std::move(End)), 183 Step(std::move(Step)), Body(std::move(Body)) {} 184 Value *codegen() override; 185 }; 186 187 /// PrototypeAST - This class represents the "prototype" for a function, 188 /// which captures its name, and its argument names (thus implicitly the number 189 /// of arguments the function takes). 190 class PrototypeAST { 191 std::string Name; 192 std::vector<std::string> Args; 193 194 public: 195 PrototypeAST(const std::string &Name, std::vector<std::string> Args) 196 : Name(Name), Args(std::move(Args)) {} 197 Function *codegen(); 198 const std::string &getName() const { return Name; } 199 }; 200 201 /// FunctionAST - This class represents a function definition itself. 202 class FunctionAST { 203 std::unique_ptr<PrototypeAST> Proto; 204 std::unique_ptr<ExprAST> Body; 205 206 public: 207 FunctionAST(std::unique_ptr<PrototypeAST> Proto, 208 std::unique_ptr<ExprAST> Body) 209 : Proto(std::move(Proto)), Body(std::move(Body)) {} 210 Function *codegen(); 211 }; 212 } // end anonymous namespace 213 214 //===----------------------------------------------------------------------===// 215 // Parser 216 //===----------------------------------------------------------------------===// 217 218 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current 219 /// token the parser is looking at. getNextToken reads another token from the 220 /// lexer and updates CurTok with its results. 221 static int CurTok; 222 static int getNextToken() { return CurTok = gettok(); } 223 224 /// BinopPrecedence - This holds the precedence for each binary operator that is 225 /// defined. 226 static std::map<char, int> BinopPrecedence; 227 228 /// GetTokPrecedence - Get the precedence of the pending binary operator token. 229 static int GetTokPrecedence() { 230 if (!isascii(CurTok)) 231 return -1; 232 233 // Make sure it's a declared binop. 234 int TokPrec = BinopPrecedence[CurTok]; 235 if (TokPrec <= 0) 236 return -1; 237 return TokPrec; 238 } 239 240 /// Error* - These are little helper functions for error handling. 241 std::unique_ptr<ExprAST> Error(const char *Str) { 242 fprintf(stderr, "Error: %s\n", Str); 243 return nullptr; 244 } 245 246 std::unique_ptr<PrototypeAST> ErrorP(const char *Str) { 247 Error(Str); 248 return nullptr; 249 } 250 251 static std::unique_ptr<ExprAST> ParseExpression(); 252 253 /// numberexpr ::= number 254 static std::unique_ptr<ExprAST> ParseNumberExpr() { 255 auto Result = llvm::make_unique<NumberExprAST>(NumVal); 256 getNextToken(); // consume the number 257 return std::move(Result); 258 } 259 260 /// parenexpr ::= '(' expression ')' 261 static std::unique_ptr<ExprAST> ParseParenExpr() { 262 getNextToken(); // eat (. 263 auto V = ParseExpression(); 264 if (!V) 265 return nullptr; 266 267 if (CurTok != ')') 268 return Error("expected ')'"); 269 getNextToken(); // eat ). 270 return V; 271 } 272 273 /// identifierexpr 274 /// ::= identifier 275 /// ::= identifier '(' expression* ')' 276 static std::unique_ptr<ExprAST> ParseIdentifierExpr() { 277 std::string IdName = IdentifierStr; 278 279 getNextToken(); // eat identifier. 280 281 if (CurTok != '(') // Simple variable ref. 282 return llvm::make_unique<VariableExprAST>(IdName); 283 284 // Call. 285 getNextToken(); // eat ( 286 std::vector<std::unique_ptr<ExprAST>> Args; 287 if (CurTok != ')') { 288 while (1) { 289 if (auto Arg = ParseExpression()) 290 Args.push_back(std::move(Arg)); 291 else 292 return nullptr; 293 294 if (CurTok == ')') 295 break; 296 297 if (CurTok != ',') 298 return Error("Expected ')' or ',' in argument list"); 299 getNextToken(); 300 } 301 } 302 303 // Eat the ')'. 304 getNextToken(); 305 306 return llvm::make_unique<CallExprAST>(IdName, std::move(Args)); 307 } 308 309 /// ifexpr ::= 'if' expression 'then' expression 'else' expression 310 static std::unique_ptr<ExprAST> ParseIfExpr() { 311 getNextToken(); // eat the if. 312 313 // condition. 314 auto Cond = ParseExpression(); 315 if (!Cond) 316 return nullptr; 317 318 if (CurTok != tok_then) 319 return Error("expected then"); 320 getNextToken(); // eat the then 321 322 auto Then = ParseExpression(); 323 if (!Then) 324 return nullptr; 325 326 if (CurTok != tok_else) 327 return Error("expected else"); 328 329 getNextToken(); 330 331 auto Else = ParseExpression(); 332 if (!Else) 333 return nullptr; 334 335 return llvm::make_unique<IfExprAST>(std::move(Cond), std::move(Then), 336 std::move(Else)); 337 } 338 339 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression 340 static std::unique_ptr<ExprAST> ParseForExpr() { 341 getNextToken(); // eat the for. 342 343 if (CurTok != tok_identifier) 344 return Error("expected identifier after for"); 345 346 std::string IdName = IdentifierStr; 347 getNextToken(); // eat identifier. 348 349 if (CurTok != '=') 350 return Error("expected '=' after for"); 351 getNextToken(); // eat '='. 352 353 auto Start = ParseExpression(); 354 if (!Start) 355 return nullptr; 356 if (CurTok != ',') 357 return Error("expected ',' after for start value"); 358 getNextToken(); 359 360 auto End = ParseExpression(); 361 if (!End) 362 return nullptr; 363 364 // The step value is optional. 365 std::unique_ptr<ExprAST> Step; 366 if (CurTok == ',') { 367 getNextToken(); 368 Step = ParseExpression(); 369 if (!Step) 370 return nullptr; 371 } 372 373 if (CurTok != tok_in) 374 return Error("expected 'in' after for"); 375 getNextToken(); // eat 'in'. 376 377 auto Body = ParseExpression(); 378 if (!Body) 379 return nullptr; 380 381 return llvm::make_unique<ForExprAST>(IdName, std::move(Start), std::move(End), 382 std::move(Step), std::move(Body)); 383 } 384 385 /// primary 386 /// ::= identifierexpr 387 /// ::= numberexpr 388 /// ::= parenexpr 389 /// ::= ifexpr 390 /// ::= forexpr 391 static std::unique_ptr<ExprAST> ParsePrimary() { 392 switch (CurTok) { 393 default: 394 return Error("unknown token when expecting an expression"); 395 case tok_identifier: 396 return ParseIdentifierExpr(); 397 case tok_number: 398 return ParseNumberExpr(); 399 case '(': 400 return ParseParenExpr(); 401 case tok_if: 402 return ParseIfExpr(); 403 case tok_for: 404 return ParseForExpr(); 405 } 406 } 407 408 /// binoprhs 409 /// ::= ('+' primary)* 410 static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec, 411 std::unique_ptr<ExprAST> LHS) { 412 // If this is a binop, find its precedence. 413 while (1) { 414 int TokPrec = GetTokPrecedence(); 415 416 // If this is a binop that binds at least as tightly as the current binop, 417 // consume it, otherwise we are done. 418 if (TokPrec < ExprPrec) 419 return LHS; 420 421 // Okay, we know this is a binop. 422 int BinOp = CurTok; 423 getNextToken(); // eat binop 424 425 // Parse the primary expression after the binary operator. 426 auto RHS = ParsePrimary(); 427 if (!RHS) 428 return nullptr; 429 430 // If BinOp binds less tightly with RHS than the operator after RHS, let 431 // the pending operator take RHS as its LHS. 432 int NextPrec = GetTokPrecedence(); 433 if (TokPrec < NextPrec) { 434 RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS)); 435 if (!RHS) 436 return nullptr; 437 } 438 439 // Merge LHS/RHS. 440 LHS = 441 llvm::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS)); 442 } 443 } 444 445 /// expression 446 /// ::= primary binoprhs 447 /// 448 static std::unique_ptr<ExprAST> ParseExpression() { 449 auto LHS = ParsePrimary(); 450 if (!LHS) 451 return nullptr; 452 453 return ParseBinOpRHS(0, std::move(LHS)); 454 } 455 456 /// prototype 457 /// ::= id '(' id* ')' 458 static std::unique_ptr<PrototypeAST> ParsePrototype() { 459 if (CurTok != tok_identifier) 460 return ErrorP("Expected function name in prototype"); 461 462 std::string FnName = IdentifierStr; 463 getNextToken(); 464 465 if (CurTok != '(') 466 return ErrorP("Expected '(' in prototype"); 467 468 std::vector<std::string> ArgNames; 469 while (getNextToken() == tok_identifier) 470 ArgNames.push_back(IdentifierStr); 471 if (CurTok != ')') 472 return ErrorP("Expected ')' in prototype"); 473 474 // success. 475 getNextToken(); // eat ')'. 476 477 return llvm::make_unique<PrototypeAST>(FnName, std::move(ArgNames)); 478 } 479 480 /// definition ::= 'def' prototype expression 481 static std::unique_ptr<FunctionAST> ParseDefinition() { 482 getNextToken(); // eat def. 483 auto Proto = ParsePrototype(); 484 if (!Proto) 485 return nullptr; 486 487 if (auto E = ParseExpression()) 488 return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E)); 489 return nullptr; 490 } 491 492 /// toplevelexpr ::= expression 493 static std::unique_ptr<FunctionAST> ParseTopLevelExpr() { 494 if (auto E = ParseExpression()) { 495 // Make an anonymous proto. 496 auto Proto = llvm::make_unique<PrototypeAST>("__anon_expr", 497 std::vector<std::string>()); 498 return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E)); 499 } 500 return nullptr; 501 } 502 503 /// external ::= 'extern' prototype 504 static std::unique_ptr<PrototypeAST> ParseExtern() { 505 getNextToken(); // eat extern. 506 return ParsePrototype(); 507 } 508 509 //===----------------------------------------------------------------------===// 510 // Code Generation 511 //===----------------------------------------------------------------------===// 512 513 static std::unique_ptr<Module> TheModule; 514 static IRBuilder<> Builder(getGlobalContext()); 515 static std::map<std::string, Value *> NamedValues; 516 static std::unique_ptr<legacy::FunctionPassManager> TheFPM; 517 static std::unique_ptr<KaleidoscopeJIT> TheJIT; 518 static std::map<std::string, std::unique_ptr<PrototypeAST>> FunctionProtos; 519 520 Value *ErrorV(const char *Str) { 521 Error(Str); 522 return nullptr; 523 } 524 525 Function *getFunction(std::string Name) { 526 // First, see if the function has already been added to the current module. 527 if (auto *F = TheModule->getFunction(Name)) 528 return F; 529 530 // If not, check whether we can codegen the declaration from some existing 531 // prototype. 532 auto FI = FunctionProtos.find(Name); 533 if (FI != FunctionProtos.end()) 534 return FI->second->codegen(); 535 536 // If no existing prototype exists, return null. 537 return nullptr; 538 } 539 540 Value *NumberExprAST::codegen() { 541 return ConstantFP::get(getGlobalContext(), APFloat(Val)); 542 } 543 544 Value *VariableExprAST::codegen() { 545 // Look this variable up in the function. 546 Value *V = NamedValues[Name]; 547 if (!V) 548 return ErrorV("Unknown variable name"); 549 return V; 550 } 551 552 Value *BinaryExprAST::codegen() { 553 Value *L = LHS->codegen(); 554 Value *R = RHS->codegen(); 555 if (!L || !R) 556 return nullptr; 557 558 switch (Op) { 559 case '+': 560 return Builder.CreateFAdd(L, R, "addtmp"); 561 case '-': 562 return Builder.CreateFSub(L, R, "subtmp"); 563 case '*': 564 return Builder.CreateFMul(L, R, "multmp"); 565 case '<': 566 L = Builder.CreateFCmpULT(L, R, "cmptmp"); 567 // Convert bool 0/1 to double 0.0 or 1.0 568 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()), 569 "booltmp"); 570 default: 571 return ErrorV("invalid binary operator"); 572 } 573 } 574 575 Value *CallExprAST::codegen() { 576 // Look up the name in the global module table. 577 Function *CalleeF = getFunction(Callee); 578 if (!CalleeF) 579 return ErrorV("Unknown function referenced"); 580 581 // If argument mismatch error. 582 if (CalleeF->arg_size() != Args.size()) 583 return ErrorV("Incorrect # arguments passed"); 584 585 std::vector<Value *> ArgsV; 586 for (unsigned i = 0, e = Args.size(); i != e; ++i) { 587 ArgsV.push_back(Args[i]->codegen()); 588 if (!ArgsV.back()) 589 return nullptr; 590 } 591 592 return Builder.CreateCall(CalleeF, ArgsV, "calltmp"); 593 } 594 595 Value *IfExprAST::codegen() { 596 Value *CondV = Cond->codegen(); 597 if (!CondV) 598 return nullptr; 599 600 // Convert condition to a bool by comparing equal to 0.0. 601 CondV = Builder.CreateFCmpONE( 602 CondV, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "ifcond"); 603 604 Function *TheFunction = Builder.GetInsertBlock()->getParent(); 605 606 // Create blocks for the then and else cases. Insert the 'then' block at the 607 // end of the function. 608 BasicBlock *ThenBB = 609 BasicBlock::Create(getGlobalContext(), "then", TheFunction); 610 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else"); 611 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont"); 612 613 Builder.CreateCondBr(CondV, ThenBB, ElseBB); 614 615 // Emit then value. 616 Builder.SetInsertPoint(ThenBB); 617 618 Value *ThenV = Then->codegen(); 619 if (!ThenV) 620 return nullptr; 621 622 Builder.CreateBr(MergeBB); 623 // Codegen of 'Then' can change the current block, update ThenBB for the PHI. 624 ThenBB = Builder.GetInsertBlock(); 625 626 // Emit else block. 627 TheFunction->getBasicBlockList().push_back(ElseBB); 628 Builder.SetInsertPoint(ElseBB); 629 630 Value *ElseV = Else->codegen(); 631 if (!ElseV) 632 return nullptr; 633 634 Builder.CreateBr(MergeBB); 635 // Codegen of 'Else' can change the current block, update ElseBB for the PHI. 636 ElseBB = Builder.GetInsertBlock(); 637 638 // Emit merge block. 639 TheFunction->getBasicBlockList().push_back(MergeBB); 640 Builder.SetInsertPoint(MergeBB); 641 PHINode *PN = 642 Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, "iftmp"); 643 644 PN->addIncoming(ThenV, ThenBB); 645 PN->addIncoming(ElseV, ElseBB); 646 return PN; 647 } 648 649 // Output for-loop as: 650 // ... 651 // start = startexpr 652 // goto loop 653 // loop: 654 // variable = phi [start, loopheader], [nextvariable, loopend] 655 // ... 656 // bodyexpr 657 // ... 658 // loopend: 659 // step = stepexpr 660 // nextvariable = variable + step 661 // endcond = endexpr 662 // br endcond, loop, endloop 663 // outloop: 664 Value *ForExprAST::codegen() { 665 // Emit the start code first, without 'variable' in scope. 666 Value *StartVal = Start->codegen(); 667 if (!StartVal) 668 return nullptr; 669 670 // Make the new basic block for the loop header, inserting after current 671 // block. 672 Function *TheFunction = Builder.GetInsertBlock()->getParent(); 673 BasicBlock *PreheaderBB = Builder.GetInsertBlock(); 674 BasicBlock *LoopBB = 675 BasicBlock::Create(getGlobalContext(), "loop", TheFunction); 676 677 // Insert an explicit fall through from the current block to the LoopBB. 678 Builder.CreateBr(LoopBB); 679 680 // Start insertion in LoopBB. 681 Builder.SetInsertPoint(LoopBB); 682 683 // Start the PHI node with an entry for Start. 684 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 685 2, VarName.c_str()); 686 Variable->addIncoming(StartVal, PreheaderBB); 687 688 // Within the loop, the variable is defined equal to the PHI node. If it 689 // shadows an existing variable, we have to restore it, so save it now. 690 Value *OldVal = NamedValues[VarName]; 691 NamedValues[VarName] = Variable; 692 693 // Emit the body of the loop. This, like any other expr, can change the 694 // current BB. Note that we ignore the value computed by the body, but don't 695 // allow an error. 696 if (!Body->codegen()) 697 return nullptr; 698 699 // Emit the step value. 700 Value *StepVal = nullptr; 701 if (Step) { 702 StepVal = Step->codegen(); 703 if (!StepVal) 704 return nullptr; 705 } else { 706 // If not specified, use 1.0. 707 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0)); 708 } 709 710 Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar"); 711 712 // Compute the end condition. 713 Value *EndCond = End->codegen(); 714 if (!EndCond) 715 return nullptr; 716 717 // Convert condition to a bool by comparing equal to 0.0. 718 EndCond = Builder.CreateFCmpONE( 719 EndCond, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "loopcond"); 720 721 // Create the "after loop" block and insert it. 722 BasicBlock *LoopEndBB = Builder.GetInsertBlock(); 723 BasicBlock *AfterBB = 724 BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction); 725 726 // Insert the conditional branch into the end of LoopEndBB. 727 Builder.CreateCondBr(EndCond, LoopBB, AfterBB); 728 729 // Any new code will be inserted in AfterBB. 730 Builder.SetInsertPoint(AfterBB); 731 732 // Add a new entry to the PHI node for the backedge. 733 Variable->addIncoming(NextVar, LoopEndBB); 734 735 // Restore the unshadowed variable. 736 if (OldVal) 737 NamedValues[VarName] = OldVal; 738 else 739 NamedValues.erase(VarName); 740 741 // for expr always returns 0.0. 742 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext())); 743 } 744 745 Function *PrototypeAST::codegen() { 746 // Make the function type: double(double,double) etc. 747 std::vector<Type *> Doubles(Args.size(), 748 Type::getDoubleTy(getGlobalContext())); 749 FunctionType *FT = 750 FunctionType::get(Type::getDoubleTy(getGlobalContext()), Doubles, false); 751 752 Function *F = 753 Function::Create(FT, Function::ExternalLinkage, Name, TheModule.get()); 754 755 // Set names for all arguments. 756 unsigned Idx = 0; 757 for (auto &Arg : F->args()) 758 Arg.setName(Args[Idx++]); 759 760 return F; 761 } 762 763 Function *FunctionAST::codegen() { 764 // Transfer ownership of the prototype to the FunctionProtos map, but keep a 765 // reference to it for use below. 766 auto &P = *Proto; 767 FunctionProtos[Proto->getName()] = std::move(Proto); 768 Function *TheFunction = getFunction(P.getName()); 769 if (!TheFunction) 770 return nullptr; 771 772 // Create a new basic block to start insertion into. 773 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction); 774 Builder.SetInsertPoint(BB); 775 776 // Record the function arguments in the NamedValues map. 777 NamedValues.clear(); 778 for (auto &Arg : TheFunction->args()) 779 NamedValues[Arg.getName()] = &Arg; 780 781 if (Value *RetVal = Body->codegen()) { 782 // Finish off the function. 783 Builder.CreateRet(RetVal); 784 785 // Validate the generated code, checking for consistency. 786 verifyFunction(*TheFunction); 787 788 // Run the optimizer on the function. 789 TheFPM->run(*TheFunction); 790 791 return TheFunction; 792 } 793 794 // Error reading body, remove function. 795 TheFunction->eraseFromParent(); 796 return nullptr; 797 } 798 799 //===----------------------------------------------------------------------===// 800 // Top-Level parsing and JIT Driver 801 //===----------------------------------------------------------------------===// 802 803 static void InitializeModuleAndPassManager() { 804 // Open a new module. 805 TheModule = llvm::make_unique<Module>("my cool jit", getGlobalContext()); 806 TheModule->setDataLayout(TheJIT->getTargetMachine().createDataLayout()); 807 808 // Create a new pass manager attached to it. 809 TheFPM = llvm::make_unique<legacy::FunctionPassManager>(TheModule.get()); 810 811 // Do simple "peephole" optimizations and bit-twiddling optzns. 812 TheFPM->add(createInstructionCombiningPass()); 813 // Reassociate expressions. 814 TheFPM->add(createReassociatePass()); 815 // Eliminate Common SubExpressions. 816 TheFPM->add(createGVNPass()); 817 // Simplify the control flow graph (deleting unreachable blocks, etc). 818 TheFPM->add(createCFGSimplificationPass()); 819 820 TheFPM->doInitialization(); 821 } 822 823 static void HandleDefinition() { 824 if (auto FnAST = ParseDefinition()) { 825 if (auto *FnIR = FnAST->codegen()) { 826 fprintf(stderr, "Read function definition:"); 827 FnIR->dump(); 828 TheJIT->addModule(std::move(TheModule)); 829 InitializeModuleAndPassManager(); 830 } 831 } else { 832 // Skip token for error recovery. 833 getNextToken(); 834 } 835 } 836 837 static void HandleExtern() { 838 if (auto ProtoAST = ParseExtern()) { 839 if (auto *FnIR = ProtoAST->codegen()) { 840 fprintf(stderr, "Read extern: "); 841 FnIR->dump(); 842 FunctionProtos[ProtoAST->getName()] = std::move(ProtoAST); 843 } 844 } else { 845 // Skip token for error recovery. 846 getNextToken(); 847 } 848 } 849 850 static void HandleTopLevelExpression() { 851 // Evaluate a top-level expression into an anonymous function. 852 if (auto FnAST = ParseTopLevelExpr()) { 853 if (FnAST->codegen()) { 854 855 // JIT the module containing the anonymous expression, keeping a handle so 856 // we can free it later. 857 auto H = TheJIT->addModule(std::move(TheModule)); 858 InitializeModuleAndPassManager(); 859 860 // Search the JIT for the __anon_expr symbol. 861 auto ExprSymbol = TheJIT->findSymbol("__anon_expr"); 862 assert(ExprSymbol && "Function not found"); 863 864 // Get the symbol's address and cast it to the right type (takes no 865 // arguments, returns a double) so we can call it as a native function. 866 double (*FP)() = (double (*)())(intptr_t)ExprSymbol.getAddress(); 867 fprintf(stderr, "Evaluated to %f\n", FP()); 868 869 // Delete the anonymous expression module from the JIT. 870 TheJIT->removeModule(H); 871 } 872 } else { 873 // Skip token for error recovery. 874 getNextToken(); 875 } 876 } 877 878 /// top ::= definition | external | expression | ';' 879 static void MainLoop() { 880 while (1) { 881 fprintf(stderr, "ready> "); 882 switch (CurTok) { 883 case tok_eof: 884 return; 885 case ';': // ignore top-level semicolons. 886 getNextToken(); 887 break; 888 case tok_def: 889 HandleDefinition(); 890 break; 891 case tok_extern: 892 HandleExtern(); 893 break; 894 default: 895 HandleTopLevelExpression(); 896 break; 897 } 898 } 899 } 900 901 //===----------------------------------------------------------------------===// 902 // "Library" functions that can be "extern'd" from user code. 903 //===----------------------------------------------------------------------===// 904 905 /// putchard - putchar that takes a double and returns 0. 906 extern "C" double putchard(double X) { 907 fputc((char)X, stderr); 908 return 0; 909 } 910 911 /// printd - printf that takes a double prints it as "%f\n", returning 0. 912 extern "C" double printd(double X) { 913 fprintf(stderr, "%f\n", X); 914 return 0; 915 } 916 917 //===----------------------------------------------------------------------===// 918 // Main driver code. 919 //===----------------------------------------------------------------------===// 920 921 int main() { 922 InitializeNativeTarget(); 923 InitializeNativeTargetAsmPrinter(); 924 InitializeNativeTargetAsmParser(); 925 926 // Install standard binary operators. 927 // 1 is lowest precedence. 928 BinopPrecedence['<'] = 10; 929 BinopPrecedence['+'] = 20; 930 BinopPrecedence['-'] = 20; 931 BinopPrecedence['*'] = 40; // highest. 932 933 // Prime the first token. 934 fprintf(stderr, "ready> "); 935 getNextToken(); 936 937 TheJIT = llvm::make_unique<KaleidoscopeJIT>(); 938 939 InitializeModuleAndPassManager(); 940 941 // Run the main "interpreter loop" now. 942 MainLoop(); 943 944 return 0; 945 } 946