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
 630   return V;
 631 }
 632
 633 Value *UnaryExprAST::Codegen() {
 634   Value *OperandV = Operand->Codegen();
 635   if (!OperandV)
 636     return nullptr;
 637
 638   Function *F = TheModule->getFunction(std::string("unary") + Opcode);
 639   if (!F)
 640     return ErrorV("Unknown unary operator");
 641
 642   return Builder.CreateCall(F, OperandV, "unop");
 643 }
 644
 645 Value *BinaryExprAST::Codegen() {
 646   Value *L = LHS->Codegen();
 647   Value *R = RHS->Codegen();
 648   if (!L || !R)
 649     return nullptr;
 650
 651   switch (Op) {
 652   case '+':
 653     return Builder.CreateFAdd(L, R, "addtmp");
 654   case '-':
 655     return Builder.CreateFSub(L, R, "subtmp");
 656   case '*':
 657     return Builder.CreateFMul(L, R, "multmp");
 658   case '<':
 659     L = Builder.CreateFCmpULT(L, R, "cmptmp");
 660     // Convert bool 0/1 to double 0.0 or 1.0
 661     return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
 662                                 "booltmp");
 663   default:
 664     break;
 665   }
 666
 667   // If it wasn't a builtin binary operator, it must be a user defined one. Emit
 668   // a call to it.
 669   Function *F = TheModule->getFunction(std::string("binary") + Op);
 670   assert(F && "binary operator not found!");
 671
 672   Value *Ops[] = {L, R};
 673   return Builder.CreateCall(F, Ops, "binop");
 674 }
 675
 676 Value *CallExprAST::Codegen() {
 677   // Look up the name in the global module table.
 678   Function *CalleeF = TheModule->getFunction(Callee);
 679   if (!CalleeF)
 680     return ErrorV("Unknown function referenced");
 681
 682   // If argument mismatch error.
 683   if (CalleeF->arg_size() != Args.size())
 684     return ErrorV("Incorrect # arguments passed");
 685
 686   std::vector<Value *> ArgsV;
 687   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 688     ArgsV.push_back(Args[i]->Codegen());
 689     if (!ArgsV.back())
 690       return nullptr;
 691   }
 692
 693   return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
 694 }
 695
 696 Value *IfExprAST::Codegen() {
 697   Value *CondV = Cond->Codegen();
 698   if (!CondV)
 699     return nullptr;
 700
 701   // Convert condition to a bool by comparing equal to 0.0.
 702   CondV = Builder.CreateFCmpONE(
 703       CondV, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "ifcond");
 704
 705   Function *TheFunction = Builder.GetInsertBlock()->getParent();
 706
 707   // Create blocks for the then and else cases.  Insert the 'then' block at the
 708   // end of the function.
 709   BasicBlock *ThenBB =
 710       BasicBlock::Create(getGlobalContext(), "then", TheFunction);
 711   BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
 712   BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
 713
 714   Builder.CreateCondBr(CondV, ThenBB, ElseBB);
 715
 716   // Emit then value.
 717   Builder.SetInsertPoint(ThenBB);
 718
 719   Value *ThenV = Then->Codegen();
 720   if (!ThenV)
 721     return nullptr;
 722
 723   Builder.CreateBr(MergeBB);
 724   // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
 725   ThenBB = Builder.GetInsertBlock();
 726
 727   // Emit else block.
 728   TheFunction->getBasicBlockList().push_back(ElseBB);
 729   Builder.SetInsertPoint(ElseBB);
 730
 731   Value *ElseV = Else->Codegen();
 732   if (!ElseV)
 733     return nullptr;
 734
 735   Builder.CreateBr(MergeBB);
 736   // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
 737   ElseBB = Builder.GetInsertBlock();
 738
 739   // Emit merge block.
 740   TheFunction->getBasicBlockList().push_back(MergeBB);
 741   Builder.SetInsertPoint(MergeBB);
 742   PHINode *PN =
 743       Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, "iftmp");
 744
 745   PN->addIncoming(ThenV, ThenBB);
 746   PN->addIncoming(ElseV, ElseBB);
 747   return PN;
 748 }
 749
 750 // Output for-loop as:
 751 //   ...
 752 //   start = startexpr
 753 //   goto loop
 754 // loop:
 755 //   variable = phi [start, loopheader], [nextvariable, loopend]
 756 //   ...
 757 //   bodyexpr
 758 //   ...
 759 // loopend:
 760 //   step = stepexpr
 761 //   nextvariable = variable + step
 762 //   endcond = endexpr
 763 //   br endcond, loop, endloop
 764 // outloop:
 765 Value *ForExprAST::Codegen() {
 766   // Emit the start code first, without 'variable' in scope.
 767   Value *StartVal = Start->Codegen();
 768   if (!StartVal)
 769     return nullptr;
 770
 771   // Make the new basic block for the loop header, inserting after current
 772   // block.
 773   Function *TheFunction = Builder.GetInsertBlock()->getParent();
 774   BasicBlock *PreheaderBB = Builder.GetInsertBlock();
 775   BasicBlock *LoopBB =
 776       BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
 777
 778   // Insert an explicit fall through from the current block to the LoopBB.
 779   Builder.CreateBr(LoopBB);
 780
 781   // Start insertion in LoopBB.
 782   Builder.SetInsertPoint(LoopBB);
 783
 784   // Start the PHI node with an entry for Start.
 785   PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()),
 786                                         2, VarName.c_str());
 787   Variable->addIncoming(StartVal, PreheaderBB);
 788
 789   // Within the loop, the variable is defined equal to the PHI node.  If it
 790   // shadows an existing variable, we have to restore it, so save it now.
 791   Value *OldVal = NamedValues[VarName];
 792   NamedValues[VarName] = Variable;
 793
 794   // Emit the body of the loop.  This, like any other expr, can change the
 795   // current BB.  Note that we ignore the value computed by the body, but don't
 796   // allow an error.
 797   if (!Body->Codegen())
 798     return nullptr;
 799
 800   // Emit the step value.
 801   Value *StepVal = nullptr;
 802   if (Step) {
 803     StepVal = Step->Codegen();
 804     if (!StepVal)
 805       return nullptr;
 806   } else {
 807     // If not specified, use 1.0.
 808     StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
 809   }
 810
 811   Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");
 812
 813   // Compute the end condition.
 814   Value *EndCond = End->Codegen();
 815   if (!EndCond)
 816     return nullptr;
 817
 818   // Convert condition to a bool by comparing equal to 0.0.
 819   EndCond = Builder.CreateFCmpONE(
 820       EndCond, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "loopcond");
 821
 822   // Create the "after loop" block and insert it.
 823   BasicBlock *LoopEndBB = Builder.GetInsertBlock();
 824   BasicBlock *AfterBB =
 825       BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
 826
 827   // Insert the conditional branch into the end of LoopEndBB.
 828   Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
 829
 830   // Any new code will be inserted in AfterBB.
 831   Builder.SetInsertPoint(AfterBB);
 832
 833   // Add a new entry to the PHI node for the backedge.
 834   Variable->addIncoming(NextVar, LoopEndBB);
 835
 836   // Restore the unshadowed variable.
 837   if (OldVal)
 838     NamedValues[VarName] = OldVal;
 839   else
 840     NamedValues.erase(VarName);
 841
 842   // for expr always returns 0.0.
 843   return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
 844 }
 845
 846 Function *PrototypeAST::Codegen() {
 847   // Make the function type:  double(double,double) etc.
 848   std::vector<Type *> Doubles(Args.size(),
 849                               Type::getDoubleTy(getGlobalContext()));
 850   FunctionType *FT =
 851       FunctionType::get(Type::getDoubleTy(getGlobalContext()), Doubles, false);
 852
 853   Function *F =
 854       Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
 855
 856   // If F conflicted, there was already something named 'Name'.  If it has a
 857   // body, don't allow redefinition or reextern.
 858   if (F->getName() != Name) {
 859     // Delete the one we just made and get the existing one.
 860     F->eraseFromParent();
 861     F = TheModule->getFunction(Name);
 862
 863     // If F already has a body, reject this.
 864     if (!F->empty()) {
 865       ErrorF("redefinition of function");
 866       return nullptr;
 867     }
 868
 869     // If F took a different number of args, reject.
 870     if (F->arg_size() != Args.size()) {
 871       ErrorF("redefinition of function with different # args");
 872       return nullptr;
 873     }
 874   }
 875
 876   // Set names for all arguments.
 877   unsigned Idx = 0;
 878   for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
 879        ++AI, ++Idx) {
 880     AI->setName(Args[Idx]);
 881
 882     // Add arguments to variable symbol table.
 883     NamedValues[Args[Idx]] = AI;
 884   }
 885
 886   return F;
 887 }
 888
 889 Function *FunctionAST::Codegen() {
 890   NamedValues.clear();
 891
 892   Function *TheFunction = Proto->Codegen();
 893   if (!TheFunction)
 894     return nullptr;
 895
 896   // If this is an operator, install it.
 897   if (Proto->isBinaryOp())
 898     BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence();
 899
 900   // Create a new basic block to start insertion into.
 901   BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
 902   Builder.SetInsertPoint(BB);
 903
 904   if (Value *RetVal = Body->Codegen()) {
 905     // Finish off the function.
 906     Builder.CreateRet(RetVal);
 907
 908     // Validate the generated code, checking for consistency.
 909     verifyFunction(*TheFunction);
 910
 911     // Optimize the function.
 912     TheFPM->run(*TheFunction);
 913
 914     return TheFunction;
 915   }
 916
 917   // Error reading body, remove function.
 918   TheFunction->eraseFromParent();
 919
 920   if (Proto->isBinaryOp())
 921     BinopPrecedence.erase(Proto->getOperatorName());
 922   return nullptr;
 923 }
 924
 925 //===----------------------------------------------------------------------===//
 926 // Top-Level parsing and JIT Driver
 927 //===----------------------------------------------------------------------===//
 928
 929 static ExecutionEngine *TheExecutionEngine;
 930
 931 static void HandleDefinition() {
 932   if (auto FnAST = ParseDefinition()) {
 933     if (auto *FnIR = FnAST->Codegen()) {
 934       fprintf(stderr, "Read function definition:");
 935       FnIR->dump();
 936     }
 937   } else {
 938     // Skip token for error recovery.
 939     getNextToken();
 940   }
 941 }
 942
 943 static void HandleExtern() {
 944   if (auto ProtoAST = ParseExtern()) {
 945     if (auto *FnIR = ProtoAST->Codegen()) {
 946       fprintf(stderr, "Read extern: ");
 947       FnIR->dump();
 948     }
 949   } else {
 950     // Skip token for error recovery.
 951     getNextToken();
 952   }
 953 }
 954
 955 static void HandleTopLevelExpression() {
 956   // Evaluate a top-level expression into an anonymous function.
 957   if (auto FnAST = ParseTopLevelExpr()) {
 958     if (auto *FnIR = FnAST->Codegen()) {
 959       TheExecutionEngine->finalizeObject();
 960       // JIT the function, returning a function pointer.
 961       void *FPtr = TheExecutionEngine->getPointerToFunction(FnIR);
 962
 963       // Cast it to the right type (takes no arguments, returns a double) so we
 964       // can call it as a native function.
 965       double (*FP)() = (double (*)())(intptr_t)FPtr;
 966       fprintf(stderr, "Evaluated to %f\n", FP());
 967     }
 968   } else {
 969     // Skip token for error recovery.
 970     getNextToken();
 971   }
 972 }
 973
 974 /// top ::= definition | external | expression | ';'
 975 static void MainLoop() {
 976   while (1) {
 977     fprintf(stderr, "ready> ");
 978     switch (CurTok) {
 979     case tok_eof:
 980       return;
 981     case ';': // ignore top-level semicolons.
 982       getNextToken();
 983       break;
 984     case tok_def:
 985       HandleDefinition();
 986       break;
 987     case tok_extern:
 988       HandleExtern();
 989       break;
 990     default:
 991       HandleTopLevelExpression();
 992       break;
 993     }
 994   }
 995 }
 996
 997 //===----------------------------------------------------------------------===//
 998 // "Library" functions that can be "extern'd" from user code.
 999 //===----------------------------------------------------------------------===//
1000
1001 /// putchard - putchar that takes a double and returns 0.
1002 extern "C" double putchard(double X) {
1003   putchar((char)X);
1004   return 0;
1005 }
1006
1007 /// printd - printf that takes a double prints it as "%f\n", returning 0.
1008 extern "C" double printd(double X) {
1009   printf("%f\n", X);
1010   return 0;
1011 }
1012
1013 //===----------------------------------------------------------------------===//
1014 // Main driver code.
1015 //===----------------------------------------------------------------------===//
1016
1017 int main() {
1018   InitializeNativeTarget();
1019   InitializeNativeTargetAsmPrinter();
1020   InitializeNativeTargetAsmParser();
1021   LLVMContext &Context = getGlobalContext();
1022
1023   // Install standard binary operators.
1024   // 1 is lowest precedence.
1025   BinopPrecedence['<'] = 10;
1026   BinopPrecedence['+'] = 20;
1027   BinopPrecedence['-'] = 20;
1028   BinopPrecedence['*'] = 40; // highest.
1029
1030   // Prime the first token.
1031   fprintf(stderr, "ready> ");
1032   getNextToken();
1033
1034   // Make the module, which holds all the code.
1035   std::unique_ptr<Module> Owner = make_unique<Module>("my cool jit", Context);
1036   TheModule = Owner.get();
1037
1038   // Create the JIT.  This takes ownership of the module.
1039   std::string ErrStr;
1040   TheExecutionEngine =
1041       EngineBuilder(std::move(Owner))
1042           .setErrorStr(&ErrStr)
1043           .setMCJITMemoryManager(llvm::make_unique<SectionMemoryManager>())
1044           .create();
1045   if (!TheExecutionEngine) {
1046     fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
1047     exit(1);
1048   }
1049
1050   legacy::FunctionPassManager OurFPM(TheModule);
1051
1052   // Set up the optimizer pipeline.  Start with registering info about how the
1053   // target lays out data structures.
1054   TheModule->setDataLayout(TheExecutionEngine->getDataLayout());
1055   // Provide basic AliasAnalysis support for GVN.
1056   OurFPM.add(createBasicAliasAnalysisPass());
1057   // Do simple "peephole" optimizations and bit-twiddling optzns.
1058   OurFPM.add(createInstructionCombiningPass());
1059   // Reassociate expressions.
1060   OurFPM.add(createReassociatePass());
1061   // Eliminate Common SubExpressions.
1062   OurFPM.add(createGVNPass());
1063   // Simplify the control flow graph (deleting unreachable blocks, etc).
1064   OurFPM.add(createCFGSimplificationPass());
1065
1066   OurFPM.doInitialization();
1067
1068   // Set the global so the code gen can use this.
1069   TheFPM = &OurFPM;
1070
1071   // Run the main "interpreter loop" now.
1072   MainLoop();
1073
1074   TheFPM = 0;
1075
1076   // Print out all of the generated code.
1077   TheModule->dump();
1078
1079   return 0;
1080 }