examples/Kaleidoscope/Chapter5/toy.cpp

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