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