examples/Kaleidoscope/Chapter5/toy.cpp

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