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