llvm/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 = std::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 std::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 std::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 std::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 std::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         std::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 std::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 std::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 = std::make_unique<PrototypeAST>("__anon_expr",
 523                                                  std::vector<std::string>());
 524     return std::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 std::unique_ptr<LLVMContext> TheContext;
 540 static std::unique_ptr<Module> TheModule;
 541 static std::unique_ptr<IRBuilder<>> Builder;
 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 static ExitOnError ExitOnErr;
 547
 548 Value *LogErrorV(const char *Str) {
 549   LogError(Str);
 550   return nullptr;
 551 }
 552
 553 Function *getFunction(std::string Name) {
 554   // First, see if the function has already been added to the current module.
 555   if (auto *F = TheModule->getFunction(Name))
 556     return F;
 557
 558   // If not, check whether we can codegen the declaration from some existing
 559   // prototype.
 560   auto FI = FunctionProtos.find(Name);
 561   if (FI != FunctionProtos.end())
 562     return FI->second->codegen();
 563
 564   // If no existing prototype exists, return null.
 565   return nullptr;
 566 }
 567
 568 Value *NumberExprAST::codegen() {
 569   return ConstantFP::get(*TheContext, APFloat(Val));
 570 }
 571
 572 Value *VariableExprAST::codegen() {
 573   // Look this variable up in the function.
 574   Value *V = NamedValues[Name];
 575   if (!V)
 576     return LogErrorV("Unknown variable name");
 577   return V;
 578 }
 579
 580 Value *BinaryExprAST::codegen() {
 581   Value *L = LHS->codegen();
 582   Value *R = RHS->codegen();
 583   if (!L || !R)
 584     return nullptr;
 585
 586   switch (Op) {
 587   case '+':
 588     return Builder->CreateFAdd(L, R, "addtmp");
 589   case '-':
 590     return Builder->CreateFSub(L, R, "subtmp");
 591   case '*':
 592     return Builder->CreateFMul(L, R, "multmp");
 593   case '<':
 594     L = Builder->CreateFCmpULT(L, R, "cmptmp");
 595     // Convert bool 0/1 to double 0.0 or 1.0
 596     return Builder->CreateUIToFP(L, Type::getDoubleTy(*TheContext), "booltmp");
 597   default:
 598     return LogErrorV("invalid binary operator");
 599   }
 600 }
 601
 602 Value *CallExprAST::codegen() {
 603   // Look up the name in the global module table.
 604   Function *CalleeF = getFunction(Callee);
 605   if (!CalleeF)
 606     return LogErrorV("Unknown function referenced");
 607
 608   // If argument mismatch error.
 609   if (CalleeF->arg_size() != Args.size())
 610     return LogErrorV("Incorrect # arguments passed");
 611
 612   std::vector<Value *> ArgsV;
 613   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 614     ArgsV.push_back(Args[i]->codegen());
 615     if (!ArgsV.back())
 616       return nullptr;
 617   }
 618
 619   return Builder->CreateCall(CalleeF, ArgsV, "calltmp");
 620 }
 621
 622 Value *IfExprAST::codegen() {
 623   Value *CondV = Cond->codegen();
 624   if (!CondV)
 625     return nullptr;
 626
 627   // Convert condition to a bool by comparing non-equal to 0.0.
 628   CondV = Builder->CreateFCmpONE(
 629       CondV, ConstantFP::get(*TheContext, APFloat(0.0)), "ifcond");
 630
 631   Function *TheFunction = Builder->GetInsertBlock()->getParent();
 632
 633   // Create blocks for the then and else cases.  Insert the 'then' block at the
 634   // end of the function.
 635   BasicBlock *ThenBB = BasicBlock::Create(*TheContext, "then", TheFunction);
 636   BasicBlock *ElseBB = BasicBlock::Create(*TheContext, "else");
 637   BasicBlock *MergeBB = BasicBlock::Create(*TheContext, "ifcont");
 638
 639   Builder->CreateCondBr(CondV, ThenBB, ElseBB);
 640
 641   // Emit then value.
 642   Builder->SetInsertPoint(ThenBB);
 643
 644   Value *ThenV = Then->codegen();
 645   if (!ThenV)
 646     return nullptr;
 647
 648   Builder->CreateBr(MergeBB);
 649   // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
 650   ThenBB = Builder->GetInsertBlock();
 651
 652   // Emit else block.
 653   TheFunction->getBasicBlockList().push_back(ElseBB);
 654   Builder->SetInsertPoint(ElseBB);
 655
 656   Value *ElseV = Else->codegen();
 657   if (!ElseV)
 658     return nullptr;
 659
 660   Builder->CreateBr(MergeBB);
 661   // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
 662   ElseBB = Builder->GetInsertBlock();
 663
 664   // Emit merge block.
 665   TheFunction->getBasicBlockList().push_back(MergeBB);
 666   Builder->SetInsertPoint(MergeBB);
 667   PHINode *PN = Builder->CreatePHI(Type::getDoubleTy(*TheContext), 2, "iftmp");
 668
 669   PN->addIncoming(ThenV, ThenBB);
 670   PN->addIncoming(ElseV, ElseBB);
 671   return PN;
 672 }
 673
 674 // Output for-loop as:
 675 //   ...
 676 //   start = startexpr
 677 //   goto loop
 678 // loop:
 679 //   variable = phi [start, loopheader], [nextvariable, loopend]
 680 //   ...
 681 //   bodyexpr
 682 //   ...
 683 // loopend:
 684 //   step = stepexpr
 685 //   nextvariable = variable + step
 686 //   endcond = endexpr
 687 //   br endcond, loop, endloop
 688 // outloop:
 689 Value *ForExprAST::codegen() {
 690   // Emit the start code first, without 'variable' in scope.
 691   Value *StartVal = Start->codegen();
 692   if (!StartVal)
 693     return nullptr;
 694
 695   // Make the new basic block for the loop header, inserting after current
 696   // block.
 697   Function *TheFunction = Builder->GetInsertBlock()->getParent();
 698   BasicBlock *PreheaderBB = Builder->GetInsertBlock();
 699   BasicBlock *LoopBB = BasicBlock::Create(*TheContext, "loop", TheFunction);
 700
 701   // Insert an explicit fall through from the current block to the LoopBB.
 702   Builder->CreateBr(LoopBB);
 703
 704   // Start insertion in LoopBB.
 705   Builder->SetInsertPoint(LoopBB);
 706
 707   // Start the PHI node with an entry for Start.
 708   PHINode *Variable =
 709       Builder->CreatePHI(Type::getDoubleTy(*TheContext), 2, VarName);
 710   Variable->addIncoming(StartVal, PreheaderBB);
 711
 712   // Within the loop, the variable is defined equal to the PHI node.  If it
 713   // shadows an existing variable, we have to restore it, so save it now.
 714   Value *OldVal = NamedValues[VarName];
 715   NamedValues[VarName] = Variable;
 716
 717   // Emit the body of the loop.  This, like any other expr, can change the
 718   // current BB.  Note that we ignore the value computed by the body, but don't
 719   // allow an error.
 720   if (!Body->codegen())
 721     return nullptr;
 722
 723   // Emit the step value.
 724   Value *StepVal = nullptr;
 725   if (Step) {
 726     StepVal = Step->codegen();
 727     if (!StepVal)
 728       return nullptr;
 729   } else {
 730     // If not specified, use 1.0.
 731     StepVal = ConstantFP::get(*TheContext, APFloat(1.0));
 732   }
 733
 734   Value *NextVar = Builder->CreateFAdd(Variable, StepVal, "nextvar");
 735
 736   // Compute the end condition.
 737   Value *EndCond = End->codegen();
 738   if (!EndCond)
 739     return nullptr;
 740
 741   // Convert condition to a bool by comparing non-equal to 0.0.
 742   EndCond = Builder->CreateFCmpONE(
 743       EndCond, ConstantFP::get(*TheContext, APFloat(0.0)), "loopcond");
 744
 745   // Create the "after loop" block and insert it.
 746   BasicBlock *LoopEndBB = Builder->GetInsertBlock();
 747   BasicBlock *AfterBB =
 748       BasicBlock::Create(*TheContext, "afterloop", TheFunction);
 749
 750   // Insert the conditional branch into the end of LoopEndBB.
 751   Builder->CreateCondBr(EndCond, LoopBB, AfterBB);
 752
 753   // Any new code will be inserted in AfterBB.
 754   Builder->SetInsertPoint(AfterBB);
 755
 756   // Add a new entry to the PHI node for the backedge.
 757   Variable->addIncoming(NextVar, LoopEndBB);
 758
 759   // Restore the unshadowed variable.
 760   if (OldVal)
 761     NamedValues[VarName] = OldVal;
 762   else
 763     NamedValues.erase(VarName);
 764
 765   // for expr always returns 0.0.
 766   return Constant::getNullValue(Type::getDoubleTy(*TheContext));
 767 }
 768
 769 Function *PrototypeAST::codegen() {
 770   // Make the function type:  double(double,double) etc.
 771   std::vector<Type *> Doubles(Args.size(), Type::getDoubleTy(*TheContext));
 772   FunctionType *FT =
 773       FunctionType::get(Type::getDoubleTy(*TheContext), Doubles, false);
 774
 775   Function *F =
 776       Function::Create(FT, Function::ExternalLinkage, Name, TheModule.get());
 777
 778   // Set names for all arguments.
 779   unsigned Idx = 0;
 780   for (auto &Arg : F->args())
 781     Arg.setName(Args[Idx++]);
 782
 783   return F;
 784 }
 785
 786 Function *FunctionAST::codegen() {
 787   // Transfer ownership of the prototype to the FunctionProtos map, but keep a
 788   // reference to it for use below.
 789   auto &P = *Proto;
 790   FunctionProtos[Proto->getName()] = std::move(Proto);
 791   Function *TheFunction = getFunction(P.getName());
 792   if (!TheFunction)
 793     return nullptr;
 794
 795   // Create a new basic block to start insertion into.
 796   BasicBlock *BB = BasicBlock::Create(*TheContext, "entry", TheFunction);
 797   Builder->SetInsertPoint(BB);
 798
 799   // Record the function arguments in the NamedValues map.
 800   NamedValues.clear();
 801   for (auto &Arg : TheFunction->args())
 802     NamedValues[std::string(Arg.getName())] = &Arg;
 803
 804   if (Value *RetVal = Body->codegen()) {
 805     // Finish off the function.
 806     Builder->CreateRet(RetVal);
 807
 808     // Validate the generated code, checking for consistency.
 809     verifyFunction(*TheFunction);
 810
 811     // Run the optimizer on the function.
 812     TheFPM->run(*TheFunction);
 813
 814     return TheFunction;
 815   }
 816
 817   // Error reading body, remove function.
 818   TheFunction->eraseFromParent();
 819   return nullptr;
 820 }
 821
 822 //===----------------------------------------------------------------------===//
 823 // Top-Level parsing and JIT Driver
 824 //===----------------------------------------------------------------------===//
 825
 826 static void InitializeModuleAndPassManager() {
 827   // Open a new module.
 828   TheContext = std::make_unique<LLVMContext>();
 829   TheModule = std::make_unique<Module>("my cool jit", *TheContext);
 830   TheModule->setDataLayout(TheJIT->getDataLayout());
 831
 832   // Create a new builder for the module.
 833   Builder = std::make_unique<IRBuilder<>>(*TheContext);
 834
 835   // Create a new pass manager attached to it.
 836   TheFPM = std::make_unique<legacy::FunctionPassManager>(TheModule.get());
 837
 838   // Do simple "peephole" optimizations and bit-twiddling optzns.
 839   TheFPM->add(createInstructionCombiningPass());
 840   // Reassociate expressions.
 841   TheFPM->add(createReassociatePass());
 842   // Eliminate Common SubExpressions.
 843   TheFPM->add(createGVNPass());
 844   // Simplify the control flow graph (deleting unreachable blocks, etc).
 845   TheFPM->add(createCFGSimplificationPass());
 846
 847   TheFPM->doInitialization();
 848 }
 849
 850 static void HandleDefinition() {
 851   if (auto FnAST = ParseDefinition()) {
 852     if (auto *FnIR = FnAST->codegen()) {
 853       fprintf(stderr, "Read function definition:");
 854       FnIR->print(errs());
 855       fprintf(stderr, "\n");
 856       ExitOnErr(TheJIT->addModule(
 857           ThreadSafeModule(std::move(TheModule), std::move(TheContext))));
 858       InitializeModuleAndPassManager();
 859     }
 860   } else {
 861     // Skip token for error recovery.
 862     getNextToken();
 863   }
 864 }
 865
 866 static void HandleExtern() {
 867   if (auto ProtoAST = ParseExtern()) {
 868     if (auto *FnIR = ProtoAST->codegen()) {
 869       fprintf(stderr, "Read extern: ");
 870       FnIR->print(errs());
 871       fprintf(stderr, "\n");
 872       FunctionProtos[ProtoAST->getName()] = std::move(ProtoAST);
 873     }
 874   } else {
 875     // Skip token for error recovery.
 876     getNextToken();
 877   }
 878 }
 879
 880 static void HandleTopLevelExpression() {
 881   // Evaluate a top-level expression into an anonymous function.
 882   if (auto FnAST = ParseTopLevelExpr()) {
 883     if (FnAST->codegen()) {
 884       // Create a ResourceTracker to track JIT'd memory allocated to our
 885       // anonymous expression -- that way we can free it after executing.
 886       auto RT = TheJIT->getMainJITDylib().createResourceTracker();
 887
 888       auto TSM = ThreadSafeModule(std::move(TheModule), std::move(TheContext));
 889       ExitOnErr(TheJIT->addModule(std::move(TSM), RT));
 890       InitializeModuleAndPassManager();
 891
 892       // Search the JIT for the __anon_expr symbol.
 893       auto ExprSymbol = ExitOnErr(TheJIT->lookup("__anon_expr"));
 894
 895       // Get the symbol's address and cast it to the right type (takes no
 896       // arguments, returns a double) so we can call it as a native function.
 897       double (*FP)() = (double (*)())(intptr_t)ExprSymbol.getAddress();
 898       fprintf(stderr, "Evaluated to %f\n", FP());
 899
 900       // Delete the anonymous expression module from the JIT.
 901       ExitOnErr(RT->remove());
 902     }
 903   } else {
 904     // Skip token for error recovery.
 905     getNextToken();
 906   }
 907 }
 908
 909 /// top ::= definition | external | expression | ';'
 910 static void MainLoop() {
 911   while (true) {
 912     fprintf(stderr, "ready> ");
 913     switch (CurTok) {
 914     case tok_eof:
 915       return;
 916     case ';': // ignore top-level semicolons.
 917       getNextToken();
 918       break;
 919     case tok_def:
 920       HandleDefinition();
 921       break;
 922     case tok_extern:
 923       HandleExtern();
 924       break;
 925     default:
 926       HandleTopLevelExpression();
 927       break;
 928     }
 929   }
 930 }
 931
 932 //===----------------------------------------------------------------------===//
 933 // "Library" functions that can be "extern'd" from user code.
 934 //===----------------------------------------------------------------------===//
 935
 936 #ifdef _WIN32
 937 #define DLLEXPORT __declspec(dllexport)
 938 #else
 939 #define DLLEXPORT
 940 #endif
 941
 942 /// putchard - putchar that takes a double and returns 0.
 943 extern "C" DLLEXPORT double putchard(double X) {
 944   fputc((char)X, stderr);
 945   return 0;
 946 }
 947
 948 /// printd - printf that takes a double prints it as "%f\n", returning 0.
 949 extern "C" DLLEXPORT double printd(double X) {
 950   fprintf(stderr, "%f\n", X);
 951   return 0;
 952 }
 953
 954 //===----------------------------------------------------------------------===//
 955 // Main driver code.
 956 //===----------------------------------------------------------------------===//
 957
 958 int main() {
 959   InitializeNativeTarget();
 960   InitializeNativeTargetAsmPrinter();
 961   InitializeNativeTargetAsmParser();
 962
 963   // Install standard binary operators.
 964   // 1 is lowest precedence.
 965   BinopPrecedence['<'] = 10;
 966   BinopPrecedence['+'] = 20;
 967   BinopPrecedence['-'] = 20;
 968   BinopPrecedence['*'] = 40; // highest.
 969
 970   // Prime the first token.
 971   fprintf(stderr, "ready> ");
 972   getNextToken();
 973
 974   TheJIT = ExitOnErr(KaleidoscopeJIT::Create());
 975
 976   InitializeModuleAndPassManager();
 977
 978   // Run the main "interpreter loop" now.
 979   MainLoop();
 980
 981   return 0;
 982 }