1 #include "llvm/Analysis/Passes.h" 2 #include "llvm/Analysis/Verifier.h" 3 #include "llvm/ExecutionEngine/ExecutionEngine.h" 4 #include "llvm/ExecutionEngine/JIT.h" 5 #include "llvm/ExecutionEngine/MCJIT.h" 6 #include "llvm/ExecutionEngine/ObjectCache.h" 7 #include "llvm/ExecutionEngine/SectionMemoryManager.h" 8 #include "llvm/IR/DataLayout.h" 9 #include "llvm/IR/DerivedTypes.h" 10 #include "llvm/IR/IRBuilder.h" 11 #include "llvm/IR/LLVMContext.h" 12 #include "llvm/IR/Module.h" 13 #include "llvm/IRReader/IRReader.h" 14 #include "llvm/PassManager.h" 15 #include "llvm/Support/CommandLine.h" 16 #include "llvm/Support/FileSystem.h" 17 #include "llvm/Support/Path.h" 18 #include "llvm/Support/raw_ostream.h" 19 #include "llvm/Support/SourceMgr.h" 20 #include "llvm/Support/TargetSelect.h" 21 #include "llvm/Transforms/Scalar.h" 22 #include <cstdio> 23 #include <map> 24 #include <string> 25 #include <vector> 26 27 using namespace llvm; 28 29 //===----------------------------------------------------------------------===// 30 // Command-line options 31 //===----------------------------------------------------------------------===// 32 33 namespace { 34 cl::opt<std::string> 35 InputIR("input-IR", 36 cl::desc("Specify the name of an IR file to load for function definitions"), 37 cl::value_desc("input IR file name")); 38 39 cl::opt<bool> 40 VerboseOutput("verbose", 41 cl::desc("Enable verbose output (results, IR, etc.) to stderr"), 42 cl::init(false)); 43 44 cl::opt<bool> 45 SuppressPrompts("suppress-prompts", 46 cl::desc("Disable printing the 'ready' prompt"), 47 cl::init(false)); 48 49 cl::opt<bool> 50 DumpModulesOnExit("dump-modules", 51 cl::desc("Dump IR from modules to stderr on shutdown"), 52 cl::init(false)); 53 54 cl::opt<bool> UseMCJIT( 55 "use-mcjit", cl::desc("Use the MCJIT execution engine"), 56 cl::init(true)); 57 58 cl::opt<bool> EnableLazyCompilation( 59 "enable-lazy-compilation", cl::desc("Enable lazy compilation when using the MCJIT engine"), 60 cl::init(true)); 61 62 cl::opt<bool> UseObjectCache( 63 "use-object-cache", cl::desc("Enable use of the MCJIT object caching"), 64 cl::init(false)); 65 } // namespace 66 67 //===----------------------------------------------------------------------===// 68 // Lexer 69 //===----------------------------------------------------------------------===// 70 71 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one 72 // of these for known things. 73 enum Token { 74 tok_eof = -1, 75 76 // commands 77 tok_def = -2, tok_extern = -3, 78 79 // primary 80 tok_identifier = -4, tok_number = -5, 81 82 // control 83 tok_if = -6, tok_then = -7, tok_else = -8, 84 tok_for = -9, tok_in = -10, 85 86 // operators 87 tok_binary = -11, tok_unary = -12, 88 89 // var definition 90 tok_var = -13 91 }; 92 93 static std::string IdentifierStr; // Filled in if tok_identifier 94 static double NumVal; // Filled in if tok_number 95 96 /// gettok - Return the next token from standard input. 97 static int gettok() { 98 static int LastChar = ' '; 99 100 // Skip any whitespace. 101 while (isspace(LastChar)) 102 LastChar = getchar(); 103 104 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]* 105 IdentifierStr = LastChar; 106 while (isalnum((LastChar = getchar()))) 107 IdentifierStr += LastChar; 108 109 if (IdentifierStr == "def") return tok_def; 110 if (IdentifierStr == "extern") return tok_extern; 111 if (IdentifierStr == "if") return tok_if; 112 if (IdentifierStr == "then") return tok_then; 113 if (IdentifierStr == "else") return tok_else; 114 if (IdentifierStr == "for") return tok_for; 115 if (IdentifierStr == "in") return tok_in; 116 if (IdentifierStr == "binary") return tok_binary; 117 if (IdentifierStr == "unary") return tok_unary; 118 if (IdentifierStr == "var") return tok_var; 119 return tok_identifier; 120 } 121 122 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+ 123 std::string NumStr; 124 do { 125 NumStr += LastChar; 126 LastChar = getchar(); 127 } while (isdigit(LastChar) || LastChar == '.'); 128 129 NumVal = strtod(NumStr.c_str(), 0); 130 return tok_number; 131 } 132 133 if (LastChar == '#') { 134 // Comment until end of line. 135 do LastChar = getchar(); 136 while (LastChar != EOF && LastChar != '\n' && LastChar != '\r'); 137 138 if (LastChar != EOF) 139 return gettok(); 140 } 141 142 // Check for end of file. Don't eat the EOF. 143 if (LastChar == EOF) 144 return tok_eof; 145 146 // Otherwise, just return the character as its ascii value. 147 int ThisChar = LastChar; 148 LastChar = getchar(); 149 return ThisChar; 150 } 151 152 //===----------------------------------------------------------------------===// 153 // Abstract Syntax Tree (aka Parse Tree) 154 //===----------------------------------------------------------------------===// 155 156 /// ExprAST - Base class for all expression nodes. 157 class ExprAST { 158 public: 159 virtual ~ExprAST() {} 160 virtual Value *Codegen() = 0; 161 }; 162 163 /// NumberExprAST - Expression class for numeric literals like "1.0". 164 class NumberExprAST : public ExprAST { 165 double Val; 166 public: 167 NumberExprAST(double val) : Val(val) {} 168 virtual Value *Codegen(); 169 }; 170 171 /// VariableExprAST - Expression class for referencing a variable, like "a". 172 class VariableExprAST : public ExprAST { 173 std::string Name; 174 public: 175 VariableExprAST(const std::string &name) : Name(name) {} 176 const std::string &getName() const { return Name; } 177 virtual Value *Codegen(); 178 }; 179 180 /// UnaryExprAST - Expression class for a unary operator. 181 class UnaryExprAST : public ExprAST { 182 char Opcode; 183 ExprAST *Operand; 184 public: 185 UnaryExprAST(char opcode, ExprAST *operand) 186 : Opcode(opcode), Operand(operand) {} 187 virtual Value *Codegen(); 188 }; 189 190 /// BinaryExprAST - Expression class for a binary operator. 191 class BinaryExprAST : public ExprAST { 192 char Op; 193 ExprAST *LHS, *RHS; 194 public: 195 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs) 196 : Op(op), LHS(lhs), RHS(rhs) {} 197 virtual Value *Codegen(); 198 }; 199 200 /// CallExprAST - Expression class for function calls. 201 class CallExprAST : public ExprAST { 202 std::string Callee; 203 std::vector<ExprAST*> Args; 204 public: 205 CallExprAST(const std::string &callee, std::vector<ExprAST*> &args) 206 : Callee(callee), Args(args) {} 207 virtual Value *Codegen(); 208 }; 209 210 /// IfExprAST - Expression class for if/then/else. 211 class IfExprAST : public ExprAST { 212 ExprAST *Cond, *Then, *Else; 213 public: 214 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else) 215 : Cond(cond), Then(then), Else(_else) {} 216 virtual Value *Codegen(); 217 }; 218 219 /// ForExprAST - Expression class for for/in. 220 class ForExprAST : public ExprAST { 221 std::string VarName; 222 ExprAST *Start, *End, *Step, *Body; 223 public: 224 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end, 225 ExprAST *step, ExprAST *body) 226 : VarName(varname), Start(start), End(end), Step(step), Body(body) {} 227 virtual Value *Codegen(); 228 }; 229 230 /// VarExprAST - Expression class for var/in 231 class VarExprAST : public ExprAST { 232 std::vector<std::pair<std::string, ExprAST*> > VarNames; 233 ExprAST *Body; 234 public: 235 VarExprAST(const std::vector<std::pair<std::string, ExprAST*> > &varnames, 236 ExprAST *body) 237 : VarNames(varnames), Body(body) {} 238 239 virtual Value *Codegen(); 240 }; 241 242 /// PrototypeAST - This class represents the "prototype" for a function, 243 /// which captures its argument names as well as if it is an operator. 244 class PrototypeAST { 245 std::string Name; 246 std::vector<std::string> Args; 247 bool isOperator; 248 unsigned Precedence; // Precedence if a binary op. 249 public: 250 PrototypeAST(const std::string &name, const std::vector<std::string> &args, 251 bool isoperator = false, unsigned prec = 0) 252 : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {} 253 254 bool isUnaryOp() const { return isOperator && Args.size() == 1; } 255 bool isBinaryOp() const { return isOperator && Args.size() == 2; } 256 257 char getOperatorName() const { 258 assert(isUnaryOp() || isBinaryOp()); 259 return Name[Name.size()-1]; 260 } 261 262 unsigned getBinaryPrecedence() const { return Precedence; } 263 264 Function *Codegen(); 265 266 void CreateArgumentAllocas(Function *F); 267 }; 268 269 /// FunctionAST - This class represents a function definition itself. 270 class FunctionAST { 271 PrototypeAST *Proto; 272 ExprAST *Body; 273 public: 274 FunctionAST(PrototypeAST *proto, ExprAST *body) 275 : Proto(proto), Body(body) {} 276 277 Function *Codegen(); 278 }; 279 280 //===----------------------------------------------------------------------===// 281 // Parser 282 //===----------------------------------------------------------------------===// 283 284 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current 285 /// token the parser is looking at. getNextToken reads another token from the 286 /// lexer and updates CurTok with its results. 287 static int CurTok; 288 static int getNextToken() { 289 return CurTok = gettok(); 290 } 291 292 /// BinopPrecedence - This holds the precedence for each binary operator that is 293 /// defined. 294 static std::map<char, int> BinopPrecedence; 295 296 /// GetTokPrecedence - Get the precedence of the pending binary operator token. 297 static int GetTokPrecedence() { 298 if (!isascii(CurTok)) 299 return -1; 300 301 // Make sure it's a declared binop. 302 int TokPrec = BinopPrecedence[CurTok]; 303 if (TokPrec <= 0) return -1; 304 return TokPrec; 305 } 306 307 /// Error* - These are little helper functions for error handling. 308 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;} 309 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; } 310 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; } 311 312 static ExprAST *ParseExpression(); 313 314 /// identifierexpr 315 /// ::= identifier 316 /// ::= identifier '(' expression* ')' 317 static ExprAST *ParseIdentifierExpr() { 318 std::string IdName = IdentifierStr; 319 320 getNextToken(); // eat identifier. 321 322 if (CurTok != '(') // Simple variable ref. 323 return new VariableExprAST(IdName); 324 325 // Call. 326 getNextToken(); // eat ( 327 std::vector<ExprAST*> Args; 328 if (CurTok != ')') { 329 while (1) { 330 ExprAST *Arg = ParseExpression(); 331 if (!Arg) return 0; 332 Args.push_back(Arg); 333 334 if (CurTok == ')') break; 335 336 if (CurTok != ',') 337 return Error("Expected ')' or ',' in argument list"); 338 getNextToken(); 339 } 340 } 341 342 // Eat the ')'. 343 getNextToken(); 344 345 return new CallExprAST(IdName, Args); 346 } 347 348 /// numberexpr ::= number 349 static ExprAST *ParseNumberExpr() { 350 ExprAST *Result = new NumberExprAST(NumVal); 351 getNextToken(); // consume the number 352 return Result; 353 } 354 355 /// parenexpr ::= '(' expression ')' 356 static ExprAST *ParseParenExpr() { 357 getNextToken(); // eat (. 358 ExprAST *V = ParseExpression(); 359 if (!V) return 0; 360 361 if (CurTok != ')') 362 return Error("expected ')'"); 363 getNextToken(); // eat ). 364 return V; 365 } 366 367 /// ifexpr ::= 'if' expression 'then' expression 'else' expression 368 static ExprAST *ParseIfExpr() { 369 getNextToken(); // eat the if. 370 371 // condition. 372 ExprAST *Cond = ParseExpression(); 373 if (!Cond) return 0; 374 375 if (CurTok != tok_then) 376 return Error("expected then"); 377 getNextToken(); // eat the then 378 379 ExprAST *Then = ParseExpression(); 380 if (Then == 0) return 0; 381 382 if (CurTok != tok_else) 383 return Error("expected else"); 384 385 getNextToken(); 386 387 ExprAST *Else = ParseExpression(); 388 if (!Else) return 0; 389 390 return new IfExprAST(Cond, Then, Else); 391 } 392 393 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression 394 static ExprAST *ParseForExpr() { 395 getNextToken(); // eat the for. 396 397 if (CurTok != tok_identifier) 398 return Error("expected identifier after for"); 399 400 std::string IdName = IdentifierStr; 401 getNextToken(); // eat identifier. 402 403 if (CurTok != '=') 404 return Error("expected '=' after for"); 405 getNextToken(); // eat '='. 406 407 408 ExprAST *Start = ParseExpression(); 409 if (Start == 0) return 0; 410 if (CurTok != ',') 411 return Error("expected ',' after for start value"); 412 getNextToken(); 413 414 ExprAST *End = ParseExpression(); 415 if (End == 0) return 0; 416 417 // The step value is optional. 418 ExprAST *Step = 0; 419 if (CurTok == ',') { 420 getNextToken(); 421 Step = ParseExpression(); 422 if (Step == 0) return 0; 423 } 424 425 if (CurTok != tok_in) 426 return Error("expected 'in' after for"); 427 getNextToken(); // eat 'in'. 428 429 ExprAST *Body = ParseExpression(); 430 if (Body == 0) return 0; 431 432 return new ForExprAST(IdName, Start, End, Step, Body); 433 } 434 435 /// varexpr ::= 'var' identifier ('=' expression)? 436 // (',' identifier ('=' expression)?)* 'in' expression 437 static ExprAST *ParseVarExpr() { 438 getNextToken(); // eat the var. 439 440 std::vector<std::pair<std::string, ExprAST*> > VarNames; 441 442 // At least one variable name is required. 443 if (CurTok != tok_identifier) 444 return Error("expected identifier after var"); 445 446 while (1) { 447 std::string Name = IdentifierStr; 448 getNextToken(); // eat identifier. 449 450 // Read the optional initializer. 451 ExprAST *Init = 0; 452 if (CurTok == '=') { 453 getNextToken(); // eat the '='. 454 455 Init = ParseExpression(); 456 if (Init == 0) return 0; 457 } 458 459 VarNames.push_back(std::make_pair(Name, Init)); 460 461 // End of var list, exit loop. 462 if (CurTok != ',') break; 463 getNextToken(); // eat the ','. 464 465 if (CurTok != tok_identifier) 466 return Error("expected identifier list after var"); 467 } 468 469 // At this point, we have to have 'in'. 470 if (CurTok != tok_in) 471 return Error("expected 'in' keyword after 'var'"); 472 getNextToken(); // eat 'in'. 473 474 ExprAST *Body = ParseExpression(); 475 if (Body == 0) return 0; 476 477 return new VarExprAST(VarNames, Body); 478 } 479 480 /// primary 481 /// ::= identifierexpr 482 /// ::= numberexpr 483 /// ::= parenexpr 484 /// ::= ifexpr 485 /// ::= forexpr 486 /// ::= varexpr 487 static ExprAST *ParsePrimary() { 488 switch (CurTok) { 489 default: return Error("unknown token when expecting an expression"); 490 case tok_identifier: return ParseIdentifierExpr(); 491 case tok_number: return ParseNumberExpr(); 492 case '(': return ParseParenExpr(); 493 case tok_if: return ParseIfExpr(); 494 case tok_for: return ParseForExpr(); 495 case tok_var: return ParseVarExpr(); 496 } 497 } 498 499 /// unary 500 /// ::= primary 501 /// ::= '!' unary 502 static ExprAST *ParseUnary() { 503 // If the current token is not an operator, it must be a primary expr. 504 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',') 505 return ParsePrimary(); 506 507 // If this is a unary operator, read it. 508 int Opc = CurTok; 509 getNextToken(); 510 if (ExprAST *Operand = ParseUnary()) 511 return new UnaryExprAST(Opc, Operand); 512 return 0; 513 } 514 515 /// binoprhs 516 /// ::= ('+' unary)* 517 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) { 518 // If this is a binop, find its precedence. 519 while (1) { 520 int TokPrec = GetTokPrecedence(); 521 522 // If this is a binop that binds at least as tightly as the current binop, 523 // consume it, otherwise we are done. 524 if (TokPrec < ExprPrec) 525 return LHS; 526 527 // Okay, we know this is a binop. 528 int BinOp = CurTok; 529 getNextToken(); // eat binop 530 531 // Parse the unary expression after the binary operator. 532 ExprAST *RHS = ParseUnary(); 533 if (!RHS) return 0; 534 535 // If BinOp binds less tightly with RHS than the operator after RHS, let 536 // the pending operator take RHS as its LHS. 537 int NextPrec = GetTokPrecedence(); 538 if (TokPrec < NextPrec) { 539 RHS = ParseBinOpRHS(TokPrec+1, RHS); 540 if (RHS == 0) return 0; 541 } 542 543 // Merge LHS/RHS. 544 LHS = new BinaryExprAST(BinOp, LHS, RHS); 545 } 546 } 547 548 /// expression 549 /// ::= unary binoprhs 550 /// 551 static ExprAST *ParseExpression() { 552 ExprAST *LHS = ParseUnary(); 553 if (!LHS) return 0; 554 555 return ParseBinOpRHS(0, LHS); 556 } 557 558 /// prototype 559 /// ::= id '(' id* ')' 560 /// ::= binary LETTER number? (id, id) 561 /// ::= unary LETTER (id) 562 static PrototypeAST *ParsePrototype() { 563 std::string FnName; 564 565 unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary. 566 unsigned BinaryPrecedence = 30; 567 568 switch (CurTok) { 569 default: 570 return ErrorP("Expected function name in prototype"); 571 case tok_identifier: 572 FnName = IdentifierStr; 573 Kind = 0; 574 getNextToken(); 575 break; 576 case tok_unary: 577 getNextToken(); 578 if (!isascii(CurTok)) 579 return ErrorP("Expected unary operator"); 580 FnName = "unary"; 581 FnName += (char)CurTok; 582 Kind = 1; 583 getNextToken(); 584 break; 585 case tok_binary: 586 getNextToken(); 587 if (!isascii(CurTok)) 588 return ErrorP("Expected binary operator"); 589 FnName = "binary"; 590 FnName += (char)CurTok; 591 Kind = 2; 592 getNextToken(); 593 594 // Read the precedence if present. 595 if (CurTok == tok_number) { 596 if (NumVal < 1 || NumVal > 100) 597 return ErrorP("Invalid precedecnce: must be 1..100"); 598 BinaryPrecedence = (unsigned)NumVal; 599 getNextToken(); 600 } 601 break; 602 } 603 604 if (CurTok != '(') 605 return ErrorP("Expected '(' in prototype"); 606 607 std::vector<std::string> ArgNames; 608 while (getNextToken() == tok_identifier) 609 ArgNames.push_back(IdentifierStr); 610 if (CurTok != ')') 611 return ErrorP("Expected ')' in prototype"); 612 613 // success. 614 getNextToken(); // eat ')'. 615 616 // Verify right number of names for operator. 617 if (Kind && ArgNames.size() != Kind) 618 return ErrorP("Invalid number of operands for operator"); 619 620 return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence); 621 } 622 623 /// definition ::= 'def' prototype expression 624 static FunctionAST *ParseDefinition() { 625 getNextToken(); // eat def. 626 PrototypeAST *Proto = ParsePrototype(); 627 if (Proto == 0) return 0; 628 629 if (ExprAST *E = ParseExpression()) 630 return new FunctionAST(Proto, E); 631 return 0; 632 } 633 634 /// toplevelexpr ::= expression 635 static FunctionAST *ParseTopLevelExpr() { 636 if (ExprAST *E = ParseExpression()) { 637 // Make an anonymous proto. 638 PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>()); 639 return new FunctionAST(Proto, E); 640 } 641 return 0; 642 } 643 644 /// external ::= 'extern' prototype 645 static PrototypeAST *ParseExtern() { 646 getNextToken(); // eat extern. 647 return ParsePrototype(); 648 } 649 650 //===----------------------------------------------------------------------===// 651 // Quick and dirty hack 652 //===----------------------------------------------------------------------===// 653 654 // FIXME: Obviously we can do better than this 655 std::string GenerateUniqueName(const char *root) 656 { 657 static int i = 0; 658 char s[16]; 659 sprintf(s, "%s%d", root, i++); 660 std::string S = s; 661 return S; 662 } 663 664 std::string MakeLegalFunctionName(std::string Name) 665 { 666 std::string NewName; 667 if (!Name.length()) 668 return GenerateUniqueName("anon_func_"); 669 670 // Start with what we have 671 NewName = Name; 672 673 // Look for a numberic first character 674 if (NewName.find_first_of("0123456789") == 0) { 675 NewName.insert(0, 1, 'n'); 676 } 677 678 // Replace illegal characters with their ASCII equivalent 679 std::string legal_elements = "_abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"; 680 size_t pos; 681 while ((pos = NewName.find_first_not_of(legal_elements)) != std::string::npos) { 682 char old_c = NewName.at(pos); 683 char new_str[16]; 684 sprintf(new_str, "%d", (int)old_c); 685 NewName = NewName.replace(pos, 1, new_str); 686 } 687 688 return NewName; 689 } 690 691 //===----------------------------------------------------------------------===// 692 // MCJIT object cache class 693 //===----------------------------------------------------------------------===// 694 695 class MCJITObjectCache : public ObjectCache { 696 public: 697 MCJITObjectCache() { 698 // Set IR cache directory 699 sys::fs::current_path(CacheDir); 700 sys::path::append(CacheDir, "toy_object_cache"); 701 } 702 703 virtual ~MCJITObjectCache() { 704 } 705 706 virtual void notifyObjectCompiled(const Module *M, const MemoryBuffer *Obj) { 707 // Get the ModuleID 708 const std::string ModuleID = M->getModuleIdentifier(); 709 710 // If we've flagged this as an IR file, cache it 711 if (0 == ModuleID.compare(0, 3, "IR:")) { 712 std::string IRFileName = ModuleID.substr(3); 713 SmallString<128>IRCacheFile = CacheDir; 714 sys::path::append(IRCacheFile, IRFileName); 715 if (!sys::fs::exists(CacheDir.str()) && sys::fs::create_directory(CacheDir.str())) { 716 fprintf(stderr, "Unable to create cache directory\n"); 717 return; 718 } 719 std::string ErrStr; 720 raw_fd_ostream IRObjectFile(IRCacheFile.c_str(), ErrStr, raw_fd_ostream::F_Binary); 721 IRObjectFile << Obj->getBuffer(); 722 } 723 } 724 725 // MCJIT will call this function before compiling any module 726 // MCJIT takes ownership of both the MemoryBuffer object and the memory 727 // to which it refers. 728 virtual MemoryBuffer* getObject(const Module* M) { 729 // Get the ModuleID 730 const std::string ModuleID = M->getModuleIdentifier(); 731 732 // If we've flagged this as an IR file, cache it 733 if (0 == ModuleID.compare(0, 3, "IR:")) { 734 std::string IRFileName = ModuleID.substr(3); 735 SmallString<128> IRCacheFile = CacheDir; 736 sys::path::append(IRCacheFile, IRFileName); 737 if (!sys::fs::exists(IRCacheFile.str())) { 738 // This file isn't in our cache 739 return NULL; 740 } 741 OwningPtr<MemoryBuffer> IRObjectBuffer; 742 MemoryBuffer::getFile(IRCacheFile.c_str(), IRObjectBuffer, -1, false); 743 // MCJIT will want to write into this buffer, and we don't want that 744 // because the file has probably just been mmapped. Instead we make 745 // a copy. The filed-based buffer will be released when it goes 746 // out of scope. 747 return MemoryBuffer::getMemBufferCopy(IRObjectBuffer->getBuffer()); 748 } 749 750 return NULL; 751 } 752 753 private: 754 SmallString<128> CacheDir; 755 }; 756 757 //===----------------------------------------------------------------------===// 758 // IR input file handler 759 //===----------------------------------------------------------------------===// 760 761 Module* parseInputIR(std::string InputFile, LLVMContext &Context) { 762 SMDiagnostic Err; 763 Module *M = ParseIRFile(InputFile, Err, Context); 764 if (!M) { 765 Err.print("IR parsing failed: ", errs()); 766 return NULL; 767 } 768 769 char ModID[256]; 770 sprintf(ModID, "IR:%s", InputFile.c_str()); 771 M->setModuleIdentifier(ModID); 772 return M; 773 } 774 775 //===----------------------------------------------------------------------===// 776 // Helper class for execution engine abstraction 777 //===----------------------------------------------------------------------===// 778 779 class BaseHelper 780 { 781 public: 782 BaseHelper() {} 783 virtual ~BaseHelper() {} 784 785 virtual Function *getFunction(const std::string FnName) = 0; 786 virtual Module *getModuleForNewFunction() = 0; 787 virtual void *getPointerToFunction(Function* F) = 0; 788 virtual void *getPointerToNamedFunction(const std::string &Name) = 0; 789 virtual void closeCurrentModule() = 0; 790 virtual void runFPM(Function &F) = 0; 791 virtual void dump(); 792 }; 793 794 //===----------------------------------------------------------------------===// 795 // Helper class for JIT execution engine 796 //===----------------------------------------------------------------------===// 797 798 class JITHelper : public BaseHelper { 799 public: 800 JITHelper(LLVMContext &Context) { 801 // Make the module, which holds all the code. 802 if (!InputIR.empty()) { 803 TheModule = parseInputIR(InputIR, Context); 804 } else { 805 TheModule = new Module("my cool jit", Context); 806 } 807 808 // Create the JIT. This takes ownership of the module. 809 std::string ErrStr; 810 TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create(); 811 if (!TheExecutionEngine) { 812 fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str()); 813 exit(1); 814 } 815 816 TheFPM = new FunctionPassManager(TheModule); 817 818 // Set up the optimizer pipeline. Start with registering info about how the 819 // target lays out data structures. 820 TheFPM->add(new DataLayout(*TheExecutionEngine->getDataLayout())); 821 // Provide basic AliasAnalysis support for GVN. 822 TheFPM->add(createBasicAliasAnalysisPass()); 823 // Promote allocas to registers. 824 TheFPM->add(createPromoteMemoryToRegisterPass()); 825 // Do simple "peephole" optimizations and bit-twiddling optzns. 826 TheFPM->add(createInstructionCombiningPass()); 827 // Reassociate expressions. 828 TheFPM->add(createReassociatePass()); 829 // Eliminate Common SubExpressions. 830 TheFPM->add(createGVNPass()); 831 // Simplify the control flow graph (deleting unreachable blocks, etc). 832 TheFPM->add(createCFGSimplificationPass()); 833 834 TheFPM->doInitialization(); 835 } 836 837 virtual ~JITHelper() { 838 if (TheFPM) 839 delete TheFPM; 840 if (TheExecutionEngine) 841 delete TheExecutionEngine; 842 } 843 844 virtual Function *getFunction(const std::string FnName) { 845 assert(TheModule); 846 return TheModule->getFunction(FnName); 847 } 848 849 virtual Module *getModuleForNewFunction() { 850 assert(TheModule); 851 return TheModule; 852 } 853 854 virtual void *getPointerToFunction(Function* F) { 855 assert(TheExecutionEngine); 856 return TheExecutionEngine->getPointerToFunction(F); 857 } 858 859 virtual void *getPointerToNamedFunction(const std::string &Name) { 860 return TheExecutionEngine->getPointerToNamedFunction(Name); 861 } 862 863 virtual void runFPM(Function &F) { 864 assert(TheFPM); 865 TheFPM->run(F); 866 } 867 868 virtual void closeCurrentModule() { 869 // This should never be called for JIT 870 assert(false); 871 } 872 873 virtual void dump() { 874 assert(TheModule); 875 TheModule->dump(); 876 } 877 878 private: 879 Module *TheModule; 880 ExecutionEngine *TheExecutionEngine; 881 FunctionPassManager *TheFPM; 882 }; 883 884 //===----------------------------------------------------------------------===// 885 // MCJIT helper class 886 //===----------------------------------------------------------------------===// 887 888 class MCJITHelper : public BaseHelper 889 { 890 public: 891 MCJITHelper(LLVMContext& C) : Context(C), CurrentModule(NULL) { 892 if (!InputIR.empty()) { 893 Module *M = parseInputIR(InputIR, Context); 894 Modules.push_back(M); 895 if (!EnableLazyCompilation) 896 compileModule(M); 897 } 898 } 899 ~MCJITHelper(); 900 901 Function *getFunction(const std::string FnName); 902 Module *getModuleForNewFunction(); 903 void *getPointerToFunction(Function* F); 904 void *getPointerToNamedFunction(const std::string &Name); 905 void closeCurrentModule(); 906 virtual void runFPM(Function &F) {} // Not needed, see compileModule 907 void dump(); 908 909 protected: 910 ExecutionEngine *compileModule(Module *M); 911 912 private: 913 typedef std::vector<Module*> ModuleVector; 914 915 MCJITObjectCache OurObjectCache; 916 917 LLVMContext &Context; 918 ModuleVector Modules; 919 920 std::map<Module *, ExecutionEngine *> EngineMap; 921 922 Module *CurrentModule; 923 }; 924 925 class HelpingMemoryManager : public SectionMemoryManager 926 { 927 HelpingMemoryManager(const HelpingMemoryManager&) LLVM_DELETED_FUNCTION; 928 void operator=(const HelpingMemoryManager&) LLVM_DELETED_FUNCTION; 929 930 public: 931 HelpingMemoryManager(MCJITHelper *Helper) : MasterHelper(Helper) {} 932 virtual ~HelpingMemoryManager() {} 933 934 /// This method returns the address of the specified function. 935 /// Our implementation will attempt to find functions in other 936 /// modules associated with the MCJITHelper to cross link functions 937 /// from one generated module to another. 938 /// 939 /// If \p AbortOnFailure is false and no function with the given name is 940 /// found, this function returns a null pointer. Otherwise, it prints a 941 /// message to stderr and aborts. 942 virtual void *getPointerToNamedFunction(const std::string &Name, 943 bool AbortOnFailure = true); 944 private: 945 MCJITHelper *MasterHelper; 946 }; 947 948 void *HelpingMemoryManager::getPointerToNamedFunction(const std::string &Name, 949 bool AbortOnFailure) 950 { 951 // Try the standard symbol resolution first, but ask it not to abort. 952 void *pfn = RTDyldMemoryManager::getPointerToNamedFunction(Name, false); 953 if (pfn) 954 return pfn; 955 956 pfn = MasterHelper->getPointerToNamedFunction(Name); 957 if (!pfn && AbortOnFailure) 958 report_fatal_error("Program used external function '" + Name + 959 "' which could not be resolved!"); 960 return pfn; 961 } 962 963 MCJITHelper::~MCJITHelper() 964 { 965 // Walk the vector of modules. 966 ModuleVector::iterator it, end; 967 for (it = Modules.begin(), end = Modules.end(); 968 it != end; ++it) { 969 // See if we have an execution engine for this module. 970 std::map<Module*, ExecutionEngine*>::iterator mapIt = EngineMap.find(*it); 971 // If we have an EE, the EE owns the module so just delete the EE. 972 if (mapIt != EngineMap.end()) { 973 delete mapIt->second; 974 } else { 975 // Otherwise, we still own the module. Delete it now. 976 delete *it; 977 } 978 } 979 } 980 981 Function *MCJITHelper::getFunction(const std::string FnName) { 982 ModuleVector::iterator begin = Modules.begin(); 983 ModuleVector::iterator end = Modules.end(); 984 ModuleVector::iterator it; 985 for (it = begin; it != end; ++it) { 986 Function *F = (*it)->getFunction(FnName); 987 if (F) { 988 if (*it == CurrentModule) 989 return F; 990 991 assert(CurrentModule != NULL); 992 993 // This function is in a module that has already been JITed. 994 // We just need a prototype for external linkage. 995 Function *PF = CurrentModule->getFunction(FnName); 996 if (PF && !PF->empty()) { 997 ErrorF("redefinition of function across modules"); 998 return 0; 999 } 1000 1001 // If we don't have a prototype yet, create one. 1002 if (!PF) 1003 PF = Function::Create(F->getFunctionType(), 1004 Function::ExternalLinkage, 1005 FnName, 1006 CurrentModule); 1007 return PF; 1008 } 1009 } 1010 return NULL; 1011 } 1012 1013 Module *MCJITHelper::getModuleForNewFunction() { 1014 // If we have a Module that hasn't been JITed, use that. 1015 if (CurrentModule) 1016 return CurrentModule; 1017 1018 // Otherwise create a new Module. 1019 std::string ModName = GenerateUniqueName("mcjit_module_"); 1020 Module *M = new Module(ModName, Context); 1021 Modules.push_back(M); 1022 CurrentModule = M; 1023 1024 return M; 1025 } 1026 1027 ExecutionEngine *MCJITHelper::compileModule(Module *M) { 1028 assert(EngineMap.find(M) == EngineMap.end()); 1029 1030 if (M == CurrentModule) 1031 closeCurrentModule(); 1032 1033 std::string ErrStr; 1034 ExecutionEngine *EE = EngineBuilder(M) 1035 .setErrorStr(&ErrStr) 1036 .setUseMCJIT(true) 1037 .setMCJITMemoryManager(new HelpingMemoryManager(this)) 1038 .create(); 1039 if (!EE) { 1040 fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str()); 1041 exit(1); 1042 } 1043 1044 if (UseObjectCache) 1045 EE->setObjectCache(&OurObjectCache); 1046 // Get the ModuleID so we can identify IR input files 1047 const std::string ModuleID = M->getModuleIdentifier(); 1048 1049 // If we've flagged this as an IR file, it doesn't need function passes run. 1050 if (0 != ModuleID.compare(0, 3, "IR:")) { 1051 FunctionPassManager *FPM = 0; 1052 1053 // Create a FPM for this module 1054 FPM = new FunctionPassManager(M); 1055 1056 // Set up the optimizer pipeline. Start with registering info about how the 1057 // target lays out data structures. 1058 FPM->add(new DataLayout(*EE->getDataLayout())); 1059 // Provide basic AliasAnalysis support for GVN. 1060 FPM->add(createBasicAliasAnalysisPass()); 1061 // Promote allocas to registers. 1062 FPM->add(createPromoteMemoryToRegisterPass()); 1063 // Do simple "peephole" optimizations and bit-twiddling optzns. 1064 FPM->add(createInstructionCombiningPass()); 1065 // Reassociate expressions. 1066 FPM->add(createReassociatePass()); 1067 // Eliminate Common SubExpressions. 1068 FPM->add(createGVNPass()); 1069 // Simplify the control flow graph (deleting unreachable blocks, etc). 1070 FPM->add(createCFGSimplificationPass()); 1071 1072 FPM->doInitialization(); 1073 1074 // For each function in the module 1075 Module::iterator it; 1076 Module::iterator end = M->end(); 1077 for (it = M->begin(); it != end; ++it) { 1078 // Run the FPM on this function 1079 FPM->run(*it); 1080 } 1081 1082 delete FPM; 1083 } 1084 1085 EE->finalizeObject(); 1086 1087 // Store this engine 1088 EngineMap[M] = EE; 1089 1090 return EE; 1091 } 1092 1093 void *MCJITHelper::getPointerToFunction(Function* F) { 1094 // Look for this function in an existing module 1095 ModuleVector::iterator begin = Modules.begin(); 1096 ModuleVector::iterator end = Modules.end(); 1097 ModuleVector::iterator it; 1098 std::string FnName = F->getName(); 1099 for (it = begin; it != end; ++it) { 1100 Function *MF = (*it)->getFunction(FnName); 1101 if (MF == F) { 1102 std::map<Module*, ExecutionEngine*>::iterator eeIt = EngineMap.find(*it); 1103 if (eeIt != EngineMap.end()) { 1104 void *P = eeIt->second->getPointerToFunction(F); 1105 if (P) 1106 return P; 1107 } else { 1108 ExecutionEngine *EE = compileModule(*it); 1109 void *P = EE->getPointerToFunction(F); 1110 if (P) 1111 return P; 1112 } 1113 } 1114 } 1115 return NULL; 1116 } 1117 1118 void MCJITHelper::closeCurrentModule() { 1119 // If we have an open module (and we should), pack it up 1120 if (CurrentModule) { 1121 CurrentModule = NULL; 1122 } 1123 } 1124 1125 void *MCJITHelper::getPointerToNamedFunction(const std::string &Name) 1126 { 1127 // Look for the functions in our modules, compiling only as necessary 1128 ModuleVector::iterator begin = Modules.begin(); 1129 ModuleVector::iterator end = Modules.end(); 1130 ModuleVector::iterator it; 1131 for (it = begin; it != end; ++it) { 1132 Function *F = (*it)->getFunction(Name); 1133 if (F && !F->empty()) { 1134 std::map<Module*, ExecutionEngine*>::iterator eeIt = EngineMap.find(*it); 1135 if (eeIt != EngineMap.end()) { 1136 void *P = eeIt->second->getPointerToFunction(F); 1137 if (P) 1138 return P; 1139 } else { 1140 ExecutionEngine *EE = compileModule(*it); 1141 void *P = EE->getPointerToFunction(F); 1142 if (P) 1143 return P; 1144 } 1145 } 1146 } 1147 return NULL; 1148 } 1149 1150 void MCJITHelper::dump() 1151 { 1152 ModuleVector::iterator begin = Modules.begin(); 1153 ModuleVector::iterator end = Modules.end(); 1154 ModuleVector::iterator it; 1155 for (it = begin; it != end; ++it) 1156 (*it)->dump(); 1157 } 1158 1159 //===----------------------------------------------------------------------===// 1160 // Code Generation 1161 //===----------------------------------------------------------------------===// 1162 1163 static BaseHelper *TheHelper; 1164 static IRBuilder<> Builder(getGlobalContext()); 1165 static std::map<std::string, AllocaInst*> NamedValues; 1166 1167 Value *ErrorV(const char *Str) { Error(Str); return 0; } 1168 1169 /// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of 1170 /// the function. This is used for mutable variables etc. 1171 static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction, 1172 const std::string &VarName) { 1173 IRBuilder<> TmpB(&TheFunction->getEntryBlock(), 1174 TheFunction->getEntryBlock().begin()); 1175 return TmpB.CreateAlloca(Type::getDoubleTy(getGlobalContext()), 0, 1176 VarName.c_str()); 1177 } 1178 1179 Value *NumberExprAST::Codegen() { 1180 return ConstantFP::get(getGlobalContext(), APFloat(Val)); 1181 } 1182 1183 Value *VariableExprAST::Codegen() { 1184 // Look this variable up in the function. 1185 Value *V = NamedValues[Name]; 1186 if (V == 0) return ErrorV("Unknown variable name"); 1187 1188 // Load the value. 1189 return Builder.CreateLoad(V, Name.c_str()); 1190 } 1191 1192 Value *UnaryExprAST::Codegen() { 1193 Value *OperandV = Operand->Codegen(); 1194 if (OperandV == 0) return 0; 1195 Function *F; 1196 if (UseMCJIT) 1197 F = TheHelper->getFunction(MakeLegalFunctionName(std::string("unary")+Opcode)); 1198 else 1199 F = TheHelper->getFunction(std::string("unary")+Opcode); 1200 if (F == 0) 1201 return ErrorV("Unknown unary operator"); 1202 1203 return Builder.CreateCall(F, OperandV, "unop"); 1204 } 1205 1206 Value *BinaryExprAST::Codegen() { 1207 // Special case '=' because we don't want to emit the LHS as an expression. 1208 if (Op == '=') { 1209 // Assignment requires the LHS to be an identifier. 1210 // This assume we're building without RTTI because LLVM builds that way by 1211 // default. If you build LLVM with RTTI this can be changed to a 1212 // dynamic_cast for automatic error checking. 1213 VariableExprAST *LHSE = reinterpret_cast<VariableExprAST*>(LHS); 1214 if (!LHSE) 1215 return ErrorV("destination of '=' must be a variable"); 1216 // Codegen the RHS. 1217 Value *Val = RHS->Codegen(); 1218 if (Val == 0) return 0; 1219 1220 // Look up the name. 1221 Value *Variable = NamedValues[LHSE->getName()]; 1222 if (Variable == 0) return ErrorV("Unknown variable name"); 1223 1224 Builder.CreateStore(Val, Variable); 1225 return Val; 1226 } 1227 1228 Value *L = LHS->Codegen(); 1229 Value *R = RHS->Codegen(); 1230 if (L == 0 || R == 0) return 0; 1231 1232 switch (Op) { 1233 case '+': return Builder.CreateFAdd(L, R, "addtmp"); 1234 case '-': return Builder.CreateFSub(L, R, "subtmp"); 1235 case '*': return Builder.CreateFMul(L, R, "multmp"); 1236 case '/': return Builder.CreateFDiv(L, R, "divtmp"); 1237 case '<': 1238 L = Builder.CreateFCmpULT(L, R, "cmptmp"); 1239 // Convert bool 0/1 to double 0.0 or 1.0 1240 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()), 1241 "booltmp"); 1242 default: break; 1243 } 1244 1245 // If it wasn't a builtin binary operator, it must be a user defined one. Emit 1246 // a call to it. 1247 Function *F; 1248 if (UseMCJIT) 1249 F = TheHelper->getFunction(MakeLegalFunctionName(std::string("binary")+Op)); 1250 else 1251 F = TheHelper->getFunction(std::string("binary")+Op); 1252 assert(F && "binary operator not found!"); 1253 1254 Value *Ops[] = { L, R }; 1255 return Builder.CreateCall(F, Ops, "binop"); 1256 } 1257 1258 Value *CallExprAST::Codegen() { 1259 // Look up the name in the global module table. 1260 Function *CalleeF = TheHelper->getFunction(Callee); 1261 if (CalleeF == 0) { 1262 char error_str[64]; 1263 sprintf(error_str, "Unknown function referenced %s", Callee.c_str()); 1264 return ErrorV(error_str); 1265 } 1266 1267 // If argument mismatch error. 1268 if (CalleeF->arg_size() != Args.size()) 1269 return ErrorV("Incorrect # arguments passed"); 1270 1271 std::vector<Value*> ArgsV; 1272 for (unsigned i = 0, e = Args.size(); i != e; ++i) { 1273 ArgsV.push_back(Args[i]->Codegen()); 1274 if (ArgsV.back() == 0) return 0; 1275 } 1276 1277 return Builder.CreateCall(CalleeF, ArgsV, "calltmp"); 1278 } 1279 1280 Value *IfExprAST::Codegen() { 1281 Value *CondV = Cond->Codegen(); 1282 if (CondV == 0) return 0; 1283 1284 // Convert condition to a bool by comparing equal to 0.0. 1285 CondV = Builder.CreateFCmpONE(CondV, 1286 ConstantFP::get(getGlobalContext(), APFloat(0.0)), 1287 "ifcond"); 1288 1289 Function *TheFunction = Builder.GetInsertBlock()->getParent(); 1290 1291 // Create blocks for the then and else cases. Insert the 'then' block at the 1292 // end of the function. 1293 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction); 1294 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else"); 1295 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont"); 1296 1297 Builder.CreateCondBr(CondV, ThenBB, ElseBB); 1298 1299 // Emit then value. 1300 Builder.SetInsertPoint(ThenBB); 1301 1302 Value *ThenV = Then->Codegen(); 1303 if (ThenV == 0) return 0; 1304 1305 Builder.CreateBr(MergeBB); 1306 // Codegen of 'Then' can change the current block, update ThenBB for the PHI. 1307 ThenBB = Builder.GetInsertBlock(); 1308 1309 // Emit else block. 1310 TheFunction->getBasicBlockList().push_back(ElseBB); 1311 Builder.SetInsertPoint(ElseBB); 1312 1313 Value *ElseV = Else->Codegen(); 1314 if (ElseV == 0) return 0; 1315 1316 Builder.CreateBr(MergeBB); 1317 // Codegen of 'Else' can change the current block, update ElseBB for the PHI. 1318 ElseBB = Builder.GetInsertBlock(); 1319 1320 // Emit merge block. 1321 TheFunction->getBasicBlockList().push_back(MergeBB); 1322 Builder.SetInsertPoint(MergeBB); 1323 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, 1324 "iftmp"); 1325 1326 PN->addIncoming(ThenV, ThenBB); 1327 PN->addIncoming(ElseV, ElseBB); 1328 return PN; 1329 } 1330 1331 Value *ForExprAST::Codegen() { 1332 // Output this as: 1333 // var = alloca double 1334 // ... 1335 // start = startexpr 1336 // store start -> var 1337 // goto loop 1338 // loop: 1339 // ... 1340 // bodyexpr 1341 // ... 1342 // loopend: 1343 // step = stepexpr 1344 // endcond = endexpr 1345 // 1346 // curvar = load var 1347 // nextvar = curvar + step 1348 // store nextvar -> var 1349 // br endcond, loop, endloop 1350 // outloop: 1351 1352 Function *TheFunction = Builder.GetInsertBlock()->getParent(); 1353 1354 // Create an alloca for the variable in the entry block. 1355 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName); 1356 1357 // Emit the start code first, without 'variable' in scope. 1358 Value *StartVal = Start->Codegen(); 1359 if (StartVal == 0) return 0; 1360 1361 // Store the value into the alloca. 1362 Builder.CreateStore(StartVal, Alloca); 1363 1364 // Make the new basic block for the loop header, inserting after current 1365 // block. 1366 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction); 1367 1368 // Insert an explicit fall through from the current block to the LoopBB. 1369 Builder.CreateBr(LoopBB); 1370 1371 // Start insertion in LoopBB. 1372 Builder.SetInsertPoint(LoopBB); 1373 1374 // Within the loop, the variable is defined equal to the PHI node. If it 1375 // shadows an existing variable, we have to restore it, so save it now. 1376 AllocaInst *OldVal = NamedValues[VarName]; 1377 NamedValues[VarName] = Alloca; 1378 1379 // Emit the body of the loop. This, like any other expr, can change the 1380 // current BB. Note that we ignore the value computed by the body, but don't 1381 // allow an error. 1382 if (Body->Codegen() == 0) 1383 return 0; 1384 1385 // Emit the step value. 1386 Value *StepVal; 1387 if (Step) { 1388 StepVal = Step->Codegen(); 1389 if (StepVal == 0) return 0; 1390 } else { 1391 // If not specified, use 1.0. 1392 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0)); 1393 } 1394 1395 // Compute the end condition. 1396 Value *EndCond = End->Codegen(); 1397 if (EndCond == 0) return EndCond; 1398 1399 // Reload, increment, and restore the alloca. This handles the case where 1400 // the body of the loop mutates the variable. 1401 Value *CurVar = Builder.CreateLoad(Alloca, VarName.c_str()); 1402 Value *NextVar = Builder.CreateFAdd(CurVar, StepVal, "nextvar"); 1403 Builder.CreateStore(NextVar, Alloca); 1404 1405 // Convert condition to a bool by comparing equal to 0.0. 1406 EndCond = Builder.CreateFCmpONE(EndCond, 1407 ConstantFP::get(getGlobalContext(), APFloat(0.0)), 1408 "loopcond"); 1409 1410 // Create the "after loop" block and insert it. 1411 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction); 1412 1413 // Insert the conditional branch into the end of LoopEndBB. 1414 Builder.CreateCondBr(EndCond, LoopBB, AfterBB); 1415 1416 // Any new code will be inserted in AfterBB. 1417 Builder.SetInsertPoint(AfterBB); 1418 1419 // Restore the unshadowed variable. 1420 if (OldVal) 1421 NamedValues[VarName] = OldVal; 1422 else 1423 NamedValues.erase(VarName); 1424 1425 1426 // for expr always returns 0.0. 1427 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext())); 1428 } 1429 1430 Value *VarExprAST::Codegen() { 1431 std::vector<AllocaInst *> OldBindings; 1432 1433 Function *TheFunction = Builder.GetInsertBlock()->getParent(); 1434 1435 // Register all variables and emit their initializer. 1436 for (unsigned i = 0, e = VarNames.size(); i != e; ++i) { 1437 const std::string &VarName = VarNames[i].first; 1438 ExprAST *Init = VarNames[i].second; 1439 1440 // Emit the initializer before adding the variable to scope, this prevents 1441 // the initializer from referencing the variable itself, and permits stuff 1442 // like this: 1443 // var a = 1 in 1444 // var a = a in ... # refers to outer 'a'. 1445 Value *InitVal; 1446 if (Init) { 1447 InitVal = Init->Codegen(); 1448 if (InitVal == 0) return 0; 1449 } else { // If not specified, use 0.0. 1450 InitVal = ConstantFP::get(getGlobalContext(), APFloat(0.0)); 1451 } 1452 1453 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName); 1454 Builder.CreateStore(InitVal, Alloca); 1455 1456 // Remember the old variable binding so that we can restore the binding when 1457 // we unrecurse. 1458 OldBindings.push_back(NamedValues[VarName]); 1459 1460 // Remember this binding. 1461 NamedValues[VarName] = Alloca; 1462 } 1463 1464 // Codegen the body, now that all vars are in scope. 1465 Value *BodyVal = Body->Codegen(); 1466 if (BodyVal == 0) return 0; 1467 1468 // Pop all our variables from scope. 1469 for (unsigned i = 0, e = VarNames.size(); i != e; ++i) 1470 NamedValues[VarNames[i].first] = OldBindings[i]; 1471 1472 // Return the body computation. 1473 return BodyVal; 1474 } 1475 1476 Function *PrototypeAST::Codegen() { 1477 // Make the function type: double(double,double) etc. 1478 std::vector<Type*> Doubles(Args.size(), 1479 Type::getDoubleTy(getGlobalContext())); 1480 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()), 1481 Doubles, false); 1482 1483 std::string FnName; 1484 if (UseMCJIT) 1485 FnName = MakeLegalFunctionName(Name); 1486 else 1487 FnName = Name; 1488 1489 Module* M = TheHelper->getModuleForNewFunction(); 1490 Function *F = Function::Create(FT, Function::ExternalLinkage, FnName, M); 1491 1492 // FIXME: Implement duplicate function detection. 1493 // The check below will only work if the duplicate is in the open module. 1494 // If F conflicted, there was already something named 'Name'. If it has a 1495 // body, don't allow redefinition or reextern. 1496 if (F->getName() != FnName) { 1497 // Delete the one we just made and get the existing one. 1498 F->eraseFromParent(); 1499 F = M->getFunction(FnName); 1500 // If F already has a body, reject this. 1501 if (!F->empty()) { 1502 ErrorF("redefinition of function"); 1503 return 0; 1504 } 1505 // If F took a different number of args, reject. 1506 if (F->arg_size() != Args.size()) { 1507 ErrorF("redefinition of function with different # args"); 1508 return 0; 1509 } 1510 } 1511 1512 // Set names for all arguments. 1513 unsigned Idx = 0; 1514 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size(); 1515 ++AI, ++Idx) 1516 AI->setName(Args[Idx]); 1517 1518 return F; 1519 } 1520 1521 /// CreateArgumentAllocas - Create an alloca for each argument and register the 1522 /// argument in the symbol table so that references to it will succeed. 1523 void PrototypeAST::CreateArgumentAllocas(Function *F) { 1524 Function::arg_iterator AI = F->arg_begin(); 1525 for (unsigned Idx = 0, e = Args.size(); Idx != e; ++Idx, ++AI) { 1526 // Create an alloca for this variable. 1527 AllocaInst *Alloca = CreateEntryBlockAlloca(F, Args[Idx]); 1528 1529 // Store the initial value into the alloca. 1530 Builder.CreateStore(AI, Alloca); 1531 1532 // Add arguments to variable symbol table. 1533 NamedValues[Args[Idx]] = Alloca; 1534 } 1535 } 1536 1537 Function *FunctionAST::Codegen() { 1538 NamedValues.clear(); 1539 1540 Function *TheFunction = Proto->Codegen(); 1541 if (TheFunction == 0) 1542 return 0; 1543 1544 // If this is an operator, install it. 1545 if (Proto->isBinaryOp()) 1546 BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence(); 1547 1548 // Create a new basic block to start insertion into. 1549 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction); 1550 Builder.SetInsertPoint(BB); 1551 1552 // Add all arguments to the symbol table and create their allocas. 1553 Proto->CreateArgumentAllocas(TheFunction); 1554 1555 if (Value *RetVal = Body->Codegen()) { 1556 // Finish off the function. 1557 Builder.CreateRet(RetVal); 1558 1559 // Validate the generated code, checking for consistency. 1560 verifyFunction(*TheFunction); 1561 1562 // Optimize the function. 1563 if (!UseMCJIT) 1564 TheHelper->runFPM(*TheFunction); 1565 1566 return TheFunction; 1567 } 1568 1569 // Error reading body, remove function. 1570 TheFunction->eraseFromParent(); 1571 1572 if (Proto->isBinaryOp()) 1573 BinopPrecedence.erase(Proto->getOperatorName()); 1574 return 0; 1575 } 1576 1577 //===----------------------------------------------------------------------===// 1578 // Top-Level parsing and JIT Driver 1579 //===----------------------------------------------------------------------===// 1580 1581 static void HandleDefinition() { 1582 if (FunctionAST *F = ParseDefinition()) { 1583 if (UseMCJIT && EnableLazyCompilation) 1584 TheHelper->closeCurrentModule(); 1585 Function *LF = F->Codegen(); 1586 if (LF && VerboseOutput) { 1587 fprintf(stderr, "Read function definition:"); 1588 LF->dump(); 1589 } 1590 } else { 1591 // Skip token for error recovery. 1592 getNextToken(); 1593 } 1594 } 1595 1596 static void HandleExtern() { 1597 if (PrototypeAST *P = ParseExtern()) { 1598 Function *F = P->Codegen(); 1599 if (F && VerboseOutput) { 1600 fprintf(stderr, "Read extern: "); 1601 F->dump(); 1602 } 1603 } else { 1604 // Skip token for error recovery. 1605 getNextToken(); 1606 } 1607 } 1608 1609 static void HandleTopLevelExpression() { 1610 // Evaluate a top-level expression into an anonymous function. 1611 if (FunctionAST *F = ParseTopLevelExpr()) { 1612 if (Function *LF = F->Codegen()) { 1613 // JIT the function, returning a function pointer. 1614 void *FPtr = TheHelper->getPointerToFunction(LF); 1615 // Cast it to the right type (takes no arguments, returns a double) so we 1616 // can call it as a native function. 1617 double (*FP)() = (double (*)())(intptr_t)FPtr; 1618 double Result = FP(); 1619 if (VerboseOutput) 1620 fprintf(stderr, "Evaluated to %f\n", Result); 1621 } 1622 } else { 1623 // Skip token for error recovery. 1624 getNextToken(); 1625 } 1626 } 1627 1628 /// top ::= definition | external | expression | ';' 1629 static void MainLoop() { 1630 while (1) { 1631 if (!SuppressPrompts) 1632 fprintf(stderr, "ready> "); 1633 switch (CurTok) { 1634 case tok_eof: return; 1635 case ';': getNextToken(); break; // ignore top-level semicolons. 1636 case tok_def: HandleDefinition(); break; 1637 case tok_extern: HandleExtern(); break; 1638 default: HandleTopLevelExpression(); break; 1639 } 1640 } 1641 } 1642 1643 //===----------------------------------------------------------------------===// 1644 // "Library" functions that can be "extern'd" from user code. 1645 //===----------------------------------------------------------------------===// 1646 1647 /// putchard - putchar that takes a double and returns 0. 1648 extern "C" 1649 double putchard(double X) { 1650 putchar((char)X); 1651 return 0; 1652 } 1653 1654 /// printd - printf that takes a double prints it as "%f\n", returning 0. 1655 extern "C" 1656 double printd(double X) { 1657 printf("%f", X); 1658 return 0; 1659 } 1660 1661 extern "C" 1662 double printlf() { 1663 printf("\n"); 1664 return 0; 1665 } 1666 1667 //===----------------------------------------------------------------------===// 1668 // Main driver code. 1669 //===----------------------------------------------------------------------===// 1670 1671 int main(int argc, char **argv) { 1672 InitializeNativeTarget(); 1673 if (UseMCJIT) { 1674 InitializeNativeTargetAsmPrinter(); 1675 InitializeNativeTargetAsmParser(); 1676 } 1677 LLVMContext &Context = getGlobalContext(); 1678 1679 cl::ParseCommandLineOptions(argc, argv, 1680 "Kaleidoscope example program\n"); 1681 1682 // Install standard binary operators. 1683 // 1 is lowest precedence. 1684 BinopPrecedence['='] = 2; 1685 BinopPrecedence['<'] = 10; 1686 BinopPrecedence['+'] = 20; 1687 BinopPrecedence['-'] = 20; 1688 BinopPrecedence['/'] = 40; 1689 BinopPrecedence['*'] = 40; // highest. 1690 1691 // Make the Helper, which holds all the code. 1692 if (UseMCJIT) 1693 TheHelper = new MCJITHelper(Context); 1694 else 1695 TheHelper = new JITHelper(Context); 1696 1697 // Prime the first token. 1698 if (!SuppressPrompts) 1699 fprintf(stderr, "ready> "); 1700 getNextToken(); 1701 1702 // Run the main "interpreter loop" now. 1703 MainLoop(); 1704 1705 // Print out all of the generated code. 1706 if (DumpModulesOnExit) 1707 TheHelper->dump(); 1708 1709 return 0; 1710 } 1711