examples/Kaleidoscope/Chapter5/toy.cpp

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