examples/Kaleidoscope/Chapter6/toy.cpp

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