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