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