examples/Kaleidoscope/Chapter5/toy.cpp

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