examples/Kaleidoscope/Chapter8/toy.cpp

   1 #include "llvm/ADT/STLExtras.h"
   2 #include "llvm/ADT/Triple.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/DIBuilder.h"
   8 #include "llvm/IR/DataLayout.h"
   9 #include "llvm/IR/DerivedTypes.h"
  10 #include "llvm/IR/IRBuilder.h"
  11 #include "llvm/IR/LLVMContext.h"
  12 #include "llvm/IR/LegacyPassManager.h"
  13 #include "llvm/IR/Module.h"
  14 #include "llvm/IR/Verifier.h"
  15 #include "llvm/Support/Host.h"
  16 #include "llvm/Support/TargetSelect.h"
  17 #include "llvm/Transforms/Scalar.h"
  18 #include <cctype>
  19 #include <cstdio>
  20 #include <map>
  21 #include <string>
  22 #include <vector>
  23 using namespace llvm;
  24
  25 //===----------------------------------------------------------------------===//
  26 // Lexer
  27 //===----------------------------------------------------------------------===//
  28
  29 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
  30 // of these for known things.
  31 enum Token {
  32   tok_eof = -1,
  33
  34   // commands
  35   tok_def = -2,
  36   tok_extern = -3,
  37
  38   // primary
  39   tok_identifier = -4,
  40   tok_number = -5,
  41
  42   // control
  43   tok_if = -6,
  44   tok_then = -7,
  45   tok_else = -8,
  46   tok_for = -9,
  47   tok_in = -10,
  48
  49   // operators
  50   tok_binary = -11,
  51   tok_unary = -12,
  52
  53   // var definition
  54   tok_var = -13
  55 };
  56
  57 std::string getTokName(int Tok) {
  58   switch (Tok) {
  59   case tok_eof:
  60     return "eof";
  61   case tok_def:
  62     return "def";
  63   case tok_extern:
  64     return "extern";
  65   case tok_identifier:
  66     return "identifier";
  67   case tok_number:
  68     return "number";
  69   case tok_if:
  70     return "if";
  71   case tok_then:
  72     return "then";
  73   case tok_else:
  74     return "else";
  75   case tok_for:
  76     return "for";
  77   case tok_in:
  78     return "in";
  79   case tok_binary:
  80     return "binary";
  81   case tok_unary:
  82     return "unary";
  83   case tok_var:
  84     return "var";
  85   }
  86   return std::string(1, (char)Tok);
  87 }
  88
  89 namespace {
  90 class PrototypeAST;
  91 class ExprAST;
  92 }
  93 static IRBuilder<> Builder(getGlobalContext());
  94 struct DebugInfo {
  95   DICompileUnit *TheCU;
  96   DIType *DblTy;
  97   std::vector<DIScope *> LexicalBlocks;
  98   std::map<const PrototypeAST *, DIScope *> FnScopeMap;
  99
 100   void emitLocation(ExprAST *AST);
 101   DIType *getDoubleTy();
 102 } KSDbgInfo;
 103
 104 static std::string IdentifierStr; // Filled in if tok_identifier
 105 static double NumVal;             // Filled in if tok_number
 106 struct SourceLocation {
 107   int Line;
 108   int Col;
 109 };
 110 static SourceLocation CurLoc;
 111 static SourceLocation LexLoc = {1, 0};
 112
 113 static int advance() {
 114   int LastChar = getchar();
 115
 116   if (LastChar == '\n' || LastChar == '\r') {
 117     LexLoc.Line++;
 118     LexLoc.Col = 0;
 119   } else
 120     LexLoc.Col++;
 121   return LastChar;
 122 }
 123
 124 /// gettok - Return the next token from standard input.
 125 static int gettok() {
 126   static int LastChar = ' ';
 127
 128   // Skip any whitespace.
 129   while (isspace(LastChar))
 130     LastChar = advance();
 131
 132   CurLoc = LexLoc;
 133
 134   if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
 135     IdentifierStr = LastChar;
 136     while (isalnum((LastChar = advance())))
 137       IdentifierStr += LastChar;
 138
 139     if (IdentifierStr == "def")
 140       return tok_def;
 141     if (IdentifierStr == "extern")
 142       return tok_extern;
 143     if (IdentifierStr == "if")
 144       return tok_if;
 145     if (IdentifierStr == "then")
 146       return tok_then;
 147     if (IdentifierStr == "else")
 148       return tok_else;
 149     if (IdentifierStr == "for")
 150       return tok_for;
 151     if (IdentifierStr == "in")
 152       return tok_in;
 153     if (IdentifierStr == "binary")
 154       return tok_binary;
 155     if (IdentifierStr == "unary")
 156       return tok_unary;
 157     if (IdentifierStr == "var")
 158       return tok_var;
 159     return tok_identifier;
 160   }
 161
 162   if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
 163     std::string NumStr;
 164     do {
 165       NumStr += LastChar;
 166       LastChar = advance();
 167     } while (isdigit(LastChar) || LastChar == '.');
 168
 169     NumVal = strtod(NumStr.c_str(), 0);
 170     return tok_number;
 171   }
 172
 173   if (LastChar == '#') {
 174     // Comment until end of line.
 175     do
 176       LastChar = advance();
 177     while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
 178
 179     if (LastChar != EOF)
 180       return gettok();
 181   }
 182
 183   // Check for end of file.  Don't eat the EOF.
 184   if (LastChar == EOF)
 185     return tok_eof;
 186
 187   // Otherwise, just return the character as its ascii value.
 188   int ThisChar = LastChar;
 189   LastChar = advance();
 190   return ThisChar;
 191 }
 192
 193 //===----------------------------------------------------------------------===//
 194 // Abstract Syntax Tree (aka Parse Tree)
 195 //===----------------------------------------------------------------------===//
 196 namespace {
 197
 198 raw_ostream &indent(raw_ostream &O, int size) {
 199   return O << std::string(size, ' ');
 200 }
 201
 202 /// ExprAST - Base class for all expression nodes.
 203 class ExprAST {
 204   SourceLocation Loc;
 205
 206 public:
 207   ExprAST(SourceLocation Loc = CurLoc) : Loc(Loc) {}
 208   virtual ~ExprAST() {}
 209   virtual Value *Codegen() = 0;
 210   int getLine() const { return Loc.Line; }
 211   int getCol() const { return Loc.Col; }
 212   virtual raw_ostream &dump(raw_ostream &out, int ind) {
 213     return out << ':' << getLine() << ':' << getCol() << '\n';
 214   }
 215 };
 216
 217 /// NumberExprAST - Expression class for numeric literals like "1.0".
 218 class NumberExprAST : public ExprAST {
 219   double Val;
 220
 221 public:
 222   NumberExprAST(double Val) : Val(Val) {}
 223   raw_ostream &dump(raw_ostream &out, int ind) override {
 224     return ExprAST::dump(out << Val, ind);
 225   }
 226   Value *Codegen() override;
 227 };
 228
 229 /// VariableExprAST - Expression class for referencing a variable, like "a".
 230 class VariableExprAST : public ExprAST {
 231   std::string Name;
 232
 233 public:
 234   VariableExprAST(SourceLocation Loc, const std::string &Name)
 235       : ExprAST(Loc), Name(Name) {}
 236   const std::string &getName() const { return Name; }
 237   raw_ostream &dump(raw_ostream &out, int ind) override {
 238     return ExprAST::dump(out << Name, ind);
 239   }
 240   Value *Codegen() override;
 241 };
 242
 243 /// UnaryExprAST - Expression class for a unary operator.
 244 class UnaryExprAST : public ExprAST {
 245   char Opcode;
 246   std::unique_ptr<ExprAST> Operand;
 247
 248 public:
 249   UnaryExprAST(char Opcode, std::unique_ptr<ExprAST> Operand)
 250       : Opcode(Opcode), Operand(std::move(Operand)) {}
 251   raw_ostream &dump(raw_ostream &out, int ind) override {
 252     ExprAST::dump(out << "unary" << Opcode, ind);
 253     Operand->dump(out, ind + 1);
 254     return out;
 255   }
 256   Value *Codegen() override;
 257 };
 258
 259 /// BinaryExprAST - Expression class for a binary operator.
 260 class BinaryExprAST : public ExprAST {
 261   char Op;
 262   std::unique_ptr<ExprAST> LHS, RHS;
 263
 264 public:
 265   BinaryExprAST(SourceLocation Loc, char Op, std::unique_ptr<ExprAST> LHS,
 266                 std::unique_ptr<ExprAST> RHS)
 267       : ExprAST(Loc), Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}
 268   raw_ostream &dump(raw_ostream &out, int ind) override {
 269     ExprAST::dump(out << "binary" << Op, ind);
 270     LHS->dump(indent(out, ind) << "LHS:", ind + 1);
 271     RHS->dump(indent(out, ind) << "RHS:", ind + 1);
 272     return out;
 273   }
 274   Value *Codegen() override;
 275 };
 276
 277 /// CallExprAST - Expression class for function calls.
 278 class CallExprAST : public ExprAST {
 279   std::string Callee;
 280   std::vector<std::unique_ptr<ExprAST>> Args;
 281
 282 public:
 283   CallExprAST(SourceLocation Loc, const std::string &Callee,
 284               std::vector<std::unique_ptr<ExprAST>> Args)
 285       : ExprAST(Loc), Callee(Callee), Args(std::move(Args)) {}
 286   raw_ostream &dump(raw_ostream &out, int ind) override {
 287     ExprAST::dump(out << "call " << Callee, ind);
 288     for (const auto &Arg : Args)
 289       Arg->dump(indent(out, ind + 1), ind + 1);
 290     return out;
 291   }
 292   Value *Codegen() override;
 293 };
 294
 295 /// IfExprAST - Expression class for if/then/else.
 296 class IfExprAST : public ExprAST {
 297   std::unique_ptr<ExprAST> Cond, Then, Else;
 298
 299 public:
 300   IfExprAST(SourceLocation Loc, std::unique_ptr<ExprAST> Cond,
 301             std::unique_ptr<ExprAST> Then, std::unique_ptr<ExprAST> Else)
 302       : ExprAST(Loc), Cond(std::move(Cond)), Then(std::move(Then)),
 303         Else(std::move(Else)) {}
 304   raw_ostream &dump(raw_ostream &out, int ind) override {
 305     ExprAST::dump(out << "if", ind);
 306     Cond->dump(indent(out, ind) << "Cond:", ind + 1);
 307     Then->dump(indent(out, ind) << "Then:", ind + 1);
 308     Else->dump(indent(out, ind) << "Else:", ind + 1);
 309     return out;
 310   }
 311   Value *Codegen() override;
 312 };
 313
 314 /// ForExprAST - Expression class for for/in.
 315 class ForExprAST : public ExprAST {
 316   std::string VarName;
 317   std::unique_ptr<ExprAST> Start, End, Step, Body;
 318
 319 public:
 320   ForExprAST(const std::string &VarName, std::unique_ptr<ExprAST> Start,
 321              std::unique_ptr<ExprAST> End, std::unique_ptr<ExprAST> Step,
 322              std::unique_ptr<ExprAST> Body)
 323       : VarName(VarName), Start(std::move(Start)), End(std::move(End)),
 324         Step(std::move(Step)), Body(std::move(Body)) {}
 325   raw_ostream &dump(raw_ostream &out, int ind) override {
 326     ExprAST::dump(out << "for", ind);
 327     Start->dump(indent(out, ind) << "Cond:", ind + 1);
 328     End->dump(indent(out, ind) << "End:", ind + 1);
 329     Step->dump(indent(out, ind) << "Step:", ind + 1);
 330     Body->dump(indent(out, ind) << "Body:", ind + 1);
 331     return out;
 332   }
 333   Value *Codegen() override;
 334 };
 335
 336 /// VarExprAST - Expression class for var/in
 337 class VarExprAST : public ExprAST {
 338   std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames;
 339   std::unique_ptr<ExprAST> Body;
 340
 341 public:
 342   VarExprAST(
 343       std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames,
 344       std::unique_ptr<ExprAST> Body)
 345       : VarNames(std::move(VarNames)), Body(std::move(Body)) {}
 346   raw_ostream &dump(raw_ostream &out, int ind) override {
 347     ExprAST::dump(out << "var", ind);
 348     for (const auto &NamedVar : VarNames)
 349       NamedVar.second->dump(indent(out, ind) << NamedVar.first << ':', ind + 1);
 350     Body->dump(indent(out, ind) << "Body:", ind + 1);
 351     return out;
 352   }
 353   Value *Codegen() override;
 354 };
 355
 356 /// PrototypeAST - This class represents the "prototype" for a function,
 357 /// which captures its name, and its argument names (thus implicitly the number
 358 /// of arguments the function takes), as well as if it is an operator.
 359 class PrototypeAST {
 360   std::string Name;
 361   std::vector<std::string> Args;
 362   bool IsOperator;
 363   unsigned Precedence; // Precedence if a binary op.
 364   int Line;
 365
 366 public:
 367   PrototypeAST(SourceLocation Loc, const std::string &Name,
 368                std::vector<std::string> Args, bool IsOperator = false,
 369                unsigned Prec = 0)
 370       : Name(Name), Args(std::move(Args)), IsOperator(IsOperator),
 371         Precedence(Prec), Line(Loc.Line) {}
 372
 373   bool isUnaryOp() const { return IsOperator && Args.size() == 1; }
 374   bool isBinaryOp() const { return IsOperator && Args.size() == 2; }
 375
 376   char getOperatorName() const {
 377     assert(isUnaryOp() || isBinaryOp());
 378     return Name[Name.size() - 1];
 379   }
 380
 381   unsigned getBinaryPrecedence() const { return Precedence; }
 382
 383   Function *Codegen();
 384
 385   void CreateArgumentAllocas(Function *F);
 386   const std::vector<std::string> &getArgs() const { return Args; }
 387 };
 388
 389 /// FunctionAST - This class represents a function definition itself.
 390 class FunctionAST {
 391   std::unique_ptr<PrototypeAST> Proto;
 392   std::unique_ptr<ExprAST> Body;
 393
 394 public:
 395   FunctionAST(std::unique_ptr<PrototypeAST> Proto,
 396               std::unique_ptr<ExprAST> Body)
 397       : Proto(std::move(Proto)), Body(std::move(Body)) {}
 398
 399   raw_ostream &dump(raw_ostream &out, int ind) {
 400     indent(out, ind) << "FunctionAST\n";
 401     ++ind;
 402     indent(out, ind) << "Body:";
 403     return Body ? Body->dump(out, ind) : out << "null\n";
 404   }
 405
 406   Function *Codegen();
 407 };
 408 } // end anonymous namespace
 409
 410 //===----------------------------------------------------------------------===//
 411 // Parser
 412 //===----------------------------------------------------------------------===//
 413
 414 /// CurTok/getNextToken - Provide a simple token buffer.  CurTok is the current
 415 /// token the parser is looking at.  getNextToken reads another token from the
 416 /// lexer and updates CurTok with its results.
 417 static int CurTok;
 418 static int getNextToken() { return CurTok = gettok(); }
 419
 420 /// BinopPrecedence - This holds the precedence for each binary operator that is
 421 /// defined.
 422 static std::map<char, int> BinopPrecedence;
 423
 424 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
 425 static int GetTokPrecedence() {
 426   if (!isascii(CurTok))
 427     return -1;
 428
 429   // Make sure it's a declared binop.
 430   int TokPrec = BinopPrecedence[CurTok];
 431   if (TokPrec <= 0)
 432     return -1;
 433   return TokPrec;
 434 }
 435
 436 /// Error* - These are little helper functions for error handling.
 437 std::unique_ptr<ExprAST> Error(const char *Str) {
 438   fprintf(stderr, "Error: %s\n", Str);
 439   return nullptr;
 440 }
 441 std::unique_ptr<PrototypeAST> ErrorP(const char *Str) {
 442   Error(Str);
 443   return nullptr;
 444 }
 445 std::unique_ptr<FunctionAST> ErrorF(const char *Str) {
 446   Error(Str);
 447   return nullptr;
 448 }
 449
 450 static std::unique_ptr<ExprAST> ParseExpression();
 451
 452 /// numberexpr ::= number
 453 static std::unique_ptr<ExprAST> ParseNumberExpr() {
 454   auto Result = llvm::make_unique<NumberExprAST>(NumVal);
 455   getNextToken(); // consume the number
 456   return std::move(Result);
 457 }
 458
 459 /// parenexpr ::= '(' expression ')'
 460 static std::unique_ptr<ExprAST> ParseParenExpr() {
 461   getNextToken(); // eat (.
 462   auto V = ParseExpression();
 463   if (!V)
 464     return nullptr;
 465
 466   if (CurTok != ')')
 467     return Error("expected ')'");
 468   getNextToken(); // eat ).
 469   return V;
 470 }
 471
 472 /// identifierexpr
 473 ///   ::= identifier
 474 ///   ::= identifier '(' expression* ')'
 475 static std::unique_ptr<ExprAST> ParseIdentifierExpr() {
 476   std::string IdName = IdentifierStr;
 477
 478   SourceLocation LitLoc = CurLoc;
 479
 480   getNextToken(); // eat identifier.
 481
 482   if (CurTok != '(') // Simple variable ref.
 483     return llvm::make_unique<VariableExprAST>(LitLoc, IdName);
 484
 485   // Call.
 486   getNextToken(); // eat (
 487   std::vector<std::unique_ptr<ExprAST>> Args;
 488   if (CurTok != ')') {
 489     while (1) {
 490       if (auto Arg = ParseExpression())
 491         Args.push_back(std::move(Arg));
 492       else
 493         return nullptr;
 494
 495       if (CurTok == ')')
 496         break;
 497
 498       if (CurTok != ',')
 499         return Error("Expected ')' or ',' in argument list");
 500       getNextToken();
 501     }
 502   }
 503
 504   // Eat the ')'.
 505   getNextToken();
 506
 507   return llvm::make_unique<CallExprAST>(LitLoc, IdName, std::move(Args));
 508 }
 509
 510 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
 511 static std::unique_ptr<ExprAST> ParseIfExpr() {
 512   SourceLocation IfLoc = CurLoc;
 513
 514   getNextToken(); // eat the if.
 515
 516   // condition.
 517   auto Cond = ParseExpression();
 518   if (!Cond)
 519     return nullptr;
 520
 521   if (CurTok != tok_then)
 522     return Error("expected then");
 523   getNextToken(); // eat the then
 524
 525   auto Then = ParseExpression();
 526   if (!Then)
 527     return nullptr;
 528
 529   if (CurTok != tok_else)
 530     return Error("expected else");
 531
 532   getNextToken();
 533
 534   auto Else = ParseExpression();
 535   if (!Else)
 536     return nullptr;
 537
 538   return llvm::make_unique<IfExprAST>(IfLoc, std::move(Cond), std::move(Then),
 539                                       std::move(Else));
 540 }
 541
 542 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
 543 static std::unique_ptr<ExprAST> ParseForExpr() {
 544   getNextToken(); // eat the for.
 545
 546   if (CurTok != tok_identifier)
 547     return Error("expected identifier after for");
 548
 549   std::string IdName = IdentifierStr;
 550   getNextToken(); // eat identifier.
 551
 552   if (CurTok != '=')
 553     return Error("expected '=' after for");
 554   getNextToken(); // eat '='.
 555
 556   auto Start = ParseExpression();
 557   if (!Start)
 558     return nullptr;
 559   if (CurTok != ',')
 560     return Error("expected ',' after for start value");
 561   getNextToken();
 562
 563   auto End = ParseExpression();
 564   if (!End)
 565     return nullptr;
 566
 567   // The step value is optional.
 568   std::unique_ptr<ExprAST> Step;
 569   if (CurTok == ',') {
 570     getNextToken();
 571     Step = ParseExpression();
 572     if (!Step)
 573       return nullptr;
 574   }
 575
 576   if (CurTok != tok_in)
 577     return Error("expected 'in' after for");
 578   getNextToken(); // eat 'in'.
 579
 580   auto Body = ParseExpression();
 581   if (!Body)
 582     return nullptr;
 583
 584   return llvm::make_unique<ForExprAST>(IdName, std::move(Start), std::move(End),
 585                                        std::move(Step), std::move(Body));
 586 }
 587
 588 /// varexpr ::= 'var' identifier ('=' expression)?
 589 //                    (',' identifier ('=' expression)?)* 'in' expression
 590 static std::unique_ptr<ExprAST> ParseVarExpr() {
 591   getNextToken(); // eat the var.
 592
 593   std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames;
 594
 595   // At least one variable name is required.
 596   if (CurTok != tok_identifier)
 597     return Error("expected identifier after var");
 598
 599   while (1) {
 600     std::string Name = IdentifierStr;
 601     getNextToken(); // eat identifier.
 602
 603     // Read the optional initializer.
 604     std::unique_ptr<ExprAST> Init = nullptr;
 605     if (CurTok == '=') {
 606       getNextToken(); // eat the '='.
 607
 608       Init = ParseExpression();
 609       if (!Init)
 610         return nullptr;
 611     }
 612
 613     VarNames.push_back(std::make_pair(Name, std::move(Init)));
 614
 615     // End of var list, exit loop.
 616     if (CurTok != ',')
 617       break;
 618     getNextToken(); // eat the ','.
 619
 620     if (CurTok != tok_identifier)
 621       return Error("expected identifier list after var");
 622   }
 623
 624   // At this point, we have to have 'in'.
 625   if (CurTok != tok_in)
 626     return Error("expected 'in' keyword after 'var'");
 627   getNextToken(); // eat 'in'.
 628
 629   auto Body = ParseExpression();
 630   if (!Body)
 631     return nullptr;
 632
 633   return llvm::make_unique<VarExprAST>(std::move(VarNames), std::move(Body));
 634 }
 635
 636 /// primary
 637 ///   ::= identifierexpr
 638 ///   ::= numberexpr
 639 ///   ::= parenexpr
 640 ///   ::= ifexpr
 641 ///   ::= forexpr
 642 ///   ::= varexpr
 643 static std::unique_ptr<ExprAST> ParsePrimary() {
 644   switch (CurTok) {
 645   default:
 646     return Error("unknown token when expecting an expression");
 647   case tok_identifier:
 648     return ParseIdentifierExpr();
 649   case tok_number:
 650     return ParseNumberExpr();
 651   case '(':
 652     return ParseParenExpr();
 653   case tok_if:
 654     return ParseIfExpr();
 655   case tok_for:
 656     return ParseForExpr();
 657   case tok_var:
 658     return ParseVarExpr();
 659   }
 660 }
 661
 662 /// unary
 663 ///   ::= primary
 664 ///   ::= '!' unary
 665 static std::unique_ptr<ExprAST> ParseUnary() {
 666   // If the current token is not an operator, it must be a primary expr.
 667   if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
 668     return ParsePrimary();
 669
 670   // If this is a unary operator, read it.
 671   int Opc = CurTok;
 672   getNextToken();
 673   if (auto Operand = ParseUnary())
 674     return llvm::make_unique<UnaryExprAST>(Opc, std::move(Operand));
 675   return nullptr;
 676 }
 677
 678 /// binoprhs
 679 ///   ::= ('+' unary)*
 680 static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
 681                                               std::unique_ptr<ExprAST> LHS) {
 682   // If this is a binop, find its precedence.
 683   while (1) {
 684     int TokPrec = GetTokPrecedence();
 685
 686     // If this is a binop that binds at least as tightly as the current binop,
 687     // consume it, otherwise we are done.
 688     if (TokPrec < ExprPrec)
 689       return LHS;
 690
 691     // Okay, we know this is a binop.
 692     int BinOp = CurTok;
 693     SourceLocation BinLoc = CurLoc;
 694     getNextToken(); // eat binop
 695
 696     // Parse the unary expression after the binary operator.
 697     auto RHS = ParseUnary();
 698     if (!RHS)
 699       return nullptr;
 700
 701     // If BinOp binds less tightly with RHS than the operator after RHS, let
 702     // the pending operator take RHS as its LHS.
 703     int NextPrec = GetTokPrecedence();
 704     if (TokPrec < NextPrec) {
 705       RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS));
 706       if (!RHS)
 707         return nullptr;
 708     }
 709
 710     // Merge LHS/RHS.
 711     LHS = llvm::make_unique<BinaryExprAST>(BinLoc, BinOp, std::move(LHS),
 712                                            std::move(RHS));
 713   }
 714 }
 715
 716 /// expression
 717 ///   ::= unary binoprhs
 718 ///
 719 static std::unique_ptr<ExprAST> ParseExpression() {
 720   auto LHS = ParseUnary();
 721   if (!LHS)
 722     return nullptr;
 723
 724   return ParseBinOpRHS(0, std::move(LHS));
 725 }
 726
 727 /// prototype
 728 ///   ::= id '(' id* ')'
 729 ///   ::= binary LETTER number? (id, id)
 730 ///   ::= unary LETTER (id)
 731 static std::unique_ptr<PrototypeAST> ParsePrototype() {
 732   std::string FnName;
 733
 734   SourceLocation FnLoc = CurLoc;
 735
 736   unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
 737   unsigned BinaryPrecedence = 30;
 738
 739   switch (CurTok) {
 740   default:
 741     return ErrorP("Expected function name in prototype");
 742   case tok_identifier:
 743     FnName = IdentifierStr;
 744     Kind = 0;
 745     getNextToken();
 746     break;
 747   case tok_unary:
 748     getNextToken();
 749     if (!isascii(CurTok))
 750       return ErrorP("Expected unary operator");
 751     FnName = "unary";
 752     FnName += (char)CurTok;
 753     Kind = 1;
 754     getNextToken();
 755     break;
 756   case tok_binary:
 757     getNextToken();
 758     if (!isascii(CurTok))
 759       return ErrorP("Expected binary operator");
 760     FnName = "binary";
 761     FnName += (char)CurTok;
 762     Kind = 2;
 763     getNextToken();
 764
 765     // Read the precedence if present.
 766     if (CurTok == tok_number) {
 767       if (NumVal < 1 || NumVal > 100)
 768         return ErrorP("Invalid precedecnce: must be 1..100");
 769       BinaryPrecedence = (unsigned)NumVal;
 770       getNextToken();
 771     }
 772     break;
 773   }
 774
 775   if (CurTok != '(')
 776     return ErrorP("Expected '(' in prototype");
 777
 778   std::vector<std::string> ArgNames;
 779   while (getNextToken() == tok_identifier)
 780     ArgNames.push_back(IdentifierStr);
 781   if (CurTok != ')')
 782     return ErrorP("Expected ')' in prototype");
 783
 784   // success.
 785   getNextToken(); // eat ')'.
 786
 787   // Verify right number of names for operator.
 788   if (Kind && ArgNames.size() != Kind)
 789     return ErrorP("Invalid number of operands for operator");
 790
 791   return llvm::make_unique<PrototypeAST>(FnLoc, FnName, ArgNames, Kind != 0,
 792                                          BinaryPrecedence);
 793 }
 794
 795 /// definition ::= 'def' prototype expression
 796 static std::unique_ptr<FunctionAST> ParseDefinition() {
 797   getNextToken(); // eat def.
 798   auto Proto = ParsePrototype();
 799   if (!Proto)
 800     return nullptr;
 801
 802   if (auto E = ParseExpression())
 803     return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E));
 804   return nullptr;
 805 }
 806
 807 /// toplevelexpr ::= expression
 808 static std::unique_ptr<FunctionAST> ParseTopLevelExpr() {
 809   SourceLocation FnLoc = CurLoc;
 810   if (auto E = ParseExpression()) {
 811     // Make an anonymous proto.
 812     auto Proto = llvm::make_unique<PrototypeAST>(FnLoc, "main",
 813                                                  std::vector<std::string>());
 814     return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E));
 815   }
 816   return nullptr;
 817 }
 818
 819 /// external ::= 'extern' prototype
 820 static std::unique_ptr<PrototypeAST> ParseExtern() {
 821   getNextToken(); // eat extern.
 822   return ParsePrototype();
 823 }
 824
 825 //===----------------------------------------------------------------------===//
 826 // Debug Info Support
 827 //===----------------------------------------------------------------------===//
 828
 829 static DIBuilder *DBuilder;
 830
 831 DIType *DebugInfo::getDoubleTy() {
 832   if (DblTy)
 833     return DblTy;
 834
 835   DblTy = DBuilder->createBasicType("double", 64, 64, dwarf::DW_ATE_float);
 836   return DblTy;
 837 }
 838
 839 void DebugInfo::emitLocation(ExprAST *AST) {
 840   if (!AST)
 841     return Builder.SetCurrentDebugLocation(DebugLoc());
 842   DIScope *Scope;
 843   if (LexicalBlocks.empty())
 844     Scope = TheCU;
 845   else
 846     Scope = LexicalBlocks.back();
 847   Builder.SetCurrentDebugLocation(
 848       DebugLoc::get(AST->getLine(), AST->getCol(), Scope));
 849 }
 850
 851 static DISubroutineType *CreateFunctionType(unsigned NumArgs, DIFile *Unit) {
 852   SmallVector<Metadata *, 8> EltTys;
 853   DIType *DblTy = KSDbgInfo.getDoubleTy();
 854
 855   // Add the result type.
 856   EltTys.push_back(DblTy);
 857
 858   for (unsigned i = 0, e = NumArgs; i != e; ++i)
 859     EltTys.push_back(DblTy);
 860
 861   return DBuilder->createSubroutineType(Unit,
 862                                         DBuilder->getOrCreateTypeArray(EltTys));
 863 }
 864
 865 //===----------------------------------------------------------------------===//
 866 // Code Generation
 867 //===----------------------------------------------------------------------===//
 868
 869 static Module *TheModule;
 870 static std::map<std::string, AllocaInst *> NamedValues;
 871 static legacy::FunctionPassManager *TheFPM;
 872
 873 Value *ErrorV(const char *Str) {
 874   Error(Str);
 875   return nullptr;
 876 }
 877
 878 /// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
 879 /// the function.  This is used for mutable variables etc.
 880 static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,
 881                                           const std::string &VarName) {
 882   IRBuilder<> TmpB(&TheFunction->getEntryBlock(),
 883                    TheFunction->getEntryBlock().begin());
 884   return TmpB.CreateAlloca(Type::getDoubleTy(getGlobalContext()), 0,
 885                            VarName.c_str());
 886 }
 887
 888 Value *NumberExprAST::Codegen() {
 889   KSDbgInfo.emitLocation(this);
 890   return ConstantFP::get(getGlobalContext(), APFloat(Val));
 891 }
 892
 893 Value *VariableExprAST::Codegen() {
 894   // Look this variable up in the function.
 895   Value *V = NamedValues[Name];
 896   if (!V)
 897     return ErrorV("Unknown variable name");
 898
 899   KSDbgInfo.emitLocation(this);
 900   // Load the value.
 901   return Builder.CreateLoad(V, Name.c_str());
 902 }
 903
 904 Value *UnaryExprAST::Codegen() {
 905   Value *OperandV = Operand->Codegen();
 906   if (!OperandV)
 907     return nullptr;
 908
 909   Function *F = TheModule->getFunction(std::string("unary") + Opcode);
 910   if (!F)
 911     return ErrorV("Unknown unary operator");
 912
 913   KSDbgInfo.emitLocation(this);
 914   return Builder.CreateCall(F, OperandV, "unop");
 915 }
 916
 917 Value *BinaryExprAST::Codegen() {
 918   KSDbgInfo.emitLocation(this);
 919
 920   // Special case '=' because we don't want to emit the LHS as an expression.
 921   if (Op == '=') {
 922     // Assignment requires the LHS to be an identifier.
 923     // This assume we're building without RTTI because LLVM builds that way by
 924     // default.  If you build LLVM with RTTI this can be changed to a
 925     // dynamic_cast for automatic error checking.
 926     VariableExprAST *LHSE = static_cast<VariableExprAST *>(LHS.get());
 927     if (!LHSE)
 928       return ErrorV("destination of '=' must be a variable");
 929     // Codegen the RHS.
 930     Value *Val = RHS->Codegen();
 931     if (!Val)
 932       return nullptr;
 933
 934     // Look up the name.
 935     Value *Variable = NamedValues[LHSE->getName()];
 936     if (!Variable)
 937       return ErrorV("Unknown variable name");
 938
 939     Builder.CreateStore(Val, Variable);
 940     return Val;
 941   }
 942
 943   Value *L = LHS->Codegen();
 944   Value *R = RHS->Codegen();
 945   if (!L || !R)
 946     return nullptr;
 947
 948   switch (Op) {
 949   case '+':
 950     return Builder.CreateFAdd(L, R, "addtmp");
 951   case '-':
 952     return Builder.CreateFSub(L, R, "subtmp");
 953   case '*':
 954     return Builder.CreateFMul(L, R, "multmp");
 955   case '<':
 956     L = Builder.CreateFCmpULT(L, R, "cmptmp");
 957     // Convert bool 0/1 to double 0.0 or 1.0
 958     return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
 959                                 "booltmp");
 960   default:
 961     break;
 962   }
 963
 964   // If it wasn't a builtin binary operator, it must be a user defined one. Emit
 965   // a call to it.
 966   Function *F = TheModule->getFunction(std::string("binary") + Op);
 967   assert(F && "binary operator not found!");
 968
 969   Value *Ops[] = {L, R};
 970   return Builder.CreateCall(F, Ops, "binop");
 971 }
 972
 973 Value *CallExprAST::Codegen() {
 974   KSDbgInfo.emitLocation(this);
 975
 976   // Look up the name in the global module table.
 977   Function *CalleeF = TheModule->getFunction(Callee);
 978   if (!CalleeF)
 979     return ErrorV("Unknown function referenced");
 980
 981   // If argument mismatch error.
 982   if (CalleeF->arg_size() != Args.size())
 983     return ErrorV("Incorrect # arguments passed");
 984
 985   std::vector<Value *> ArgsV;
 986   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 987     ArgsV.push_back(Args[i]->Codegen());
 988     if (!ArgsV.back())
 989       return nullptr;
 990   }
 991
 992   return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
 993 }
 994
 995 Value *IfExprAST::Codegen() {
 996   KSDbgInfo.emitLocation(this);
 997
 998   Value *CondV = Cond->Codegen();
 999   if (!CondV)
1000     return nullptr;
1001
1002   // Convert condition to a bool by comparing equal to 0.0.
1003   CondV = Builder.CreateFCmpONE(
1004       CondV, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "ifcond");
1005
1006   Function *TheFunction = Builder.GetInsertBlock()->getParent();
1007
1008   // Create blocks for the then and else cases.  Insert the 'then' block at the
1009   // end of the function.
1010   BasicBlock *ThenBB =
1011       BasicBlock::Create(getGlobalContext(), "then", TheFunction);
1012   BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
1013   BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
1014
1015   Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1016
1017   // Emit then value.
1018   Builder.SetInsertPoint(ThenBB);
1019
1020   Value *ThenV = Then->Codegen();
1021   if (!ThenV)
1022     return nullptr;
1023
1024   Builder.CreateBr(MergeBB);
1025   // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1026   ThenBB = Builder.GetInsertBlock();
1027
1028   // Emit else block.
1029   TheFunction->getBasicBlockList().push_back(ElseBB);
1030   Builder.SetInsertPoint(ElseBB);
1031
1032   Value *ElseV = Else->Codegen();
1033   if (!ElseV)
1034     return nullptr;
1035
1036   Builder.CreateBr(MergeBB);
1037   // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1038   ElseBB = Builder.GetInsertBlock();
1039
1040   // Emit merge block.
1041   TheFunction->getBasicBlockList().push_back(MergeBB);
1042   Builder.SetInsertPoint(MergeBB);
1043   PHINode *PN =
1044       Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, "iftmp");
1045
1046   PN->addIncoming(ThenV, ThenBB);
1047   PN->addIncoming(ElseV, ElseBB);
1048   return PN;
1049 }
1050
1051 // Output for-loop as:
1052 //   var = alloca double
1053 //   ...
1054 //   start = startexpr
1055 //   store start -> var
1056 //   goto loop
1057 // loop:
1058 //   ...
1059 //   bodyexpr
1060 //   ...
1061 // loopend:
1062 //   step = stepexpr
1063 //   endcond = endexpr
1064 //
1065 //   curvar = load var
1066 //   nextvar = curvar + step
1067 //   store nextvar -> var
1068 //   br endcond, loop, endloop
1069 // outloop:
1070 Value *ForExprAST::Codegen() {
1071   Function *TheFunction = Builder.GetInsertBlock()->getParent();
1072
1073   // Create an alloca for the variable in the entry block.
1074   AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
1075
1076   KSDbgInfo.emitLocation(this);
1077
1078   // Emit the start code first, without 'variable' in scope.
1079   Value *StartVal = Start->Codegen();
1080   if (!StartVal)
1081     return nullptr;
1082
1083   // Store the value into the alloca.
1084   Builder.CreateStore(StartVal, Alloca);
1085
1086   // Make the new basic block for the loop header, inserting after current
1087   // block.
1088   BasicBlock *LoopBB =
1089       BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
1090
1091   // Insert an explicit fall through from the current block to the LoopBB.
1092   Builder.CreateBr(LoopBB);
1093
1094   // Start insertion in LoopBB.
1095   Builder.SetInsertPoint(LoopBB);
1096
1097   // Within the loop, the variable is defined equal to the PHI node.  If it
1098   // shadows an existing variable, we have to restore it, so save it now.
1099   AllocaInst *OldVal = NamedValues[VarName];
1100   NamedValues[VarName] = Alloca;
1101
1102   // Emit the body of the loop.  This, like any other expr, can change the
1103   // current BB.  Note that we ignore the value computed by the body, but don't
1104   // allow an error.
1105   if (!Body->Codegen())
1106     return nullptr;
1107
1108   // Emit the step value.
1109   Value *StepVal = nullptr;
1110   if (Step) {
1111     StepVal = Step->Codegen();
1112     if (!StepVal)
1113       return nullptr;
1114   } else {
1115     // If not specified, use 1.0.
1116     StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
1117   }
1118
1119   // Compute the end condition.
1120   Value *EndCond = End->Codegen();
1121   if (!EndCond)
1122     return nullptr;
1123
1124   // Reload, increment, and restore the alloca.  This handles the case where
1125   // the body of the loop mutates the variable.
1126   Value *CurVar = Builder.CreateLoad(Alloca, VarName.c_str());
1127   Value *NextVar = Builder.CreateFAdd(CurVar, StepVal, "nextvar");
1128   Builder.CreateStore(NextVar, Alloca);
1129
1130   // Convert condition to a bool by comparing equal to 0.0.
1131   EndCond = Builder.CreateFCmpONE(
1132       EndCond, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "loopcond");
1133
1134   // Create the "after loop" block and insert it.
1135   BasicBlock *AfterBB =
1136       BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
1137
1138   // Insert the conditional branch into the end of LoopEndBB.
1139   Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1140
1141   // Any new code will be inserted in AfterBB.
1142   Builder.SetInsertPoint(AfterBB);
1143
1144   // Restore the unshadowed variable.
1145   if (OldVal)
1146     NamedValues[VarName] = OldVal;
1147   else
1148     NamedValues.erase(VarName);
1149
1150   // for expr always returns 0.0.
1151   return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
1152 }
1153
1154 Value *VarExprAST::Codegen() {
1155   std::vector<AllocaInst *> OldBindings;
1156
1157   Function *TheFunction = Builder.GetInsertBlock()->getParent();
1158
1159   // Register all variables and emit their initializer.
1160   for (unsigned i = 0, e = VarNames.size(); i != e; ++i) {
1161     const std::string &VarName = VarNames[i].first;
1162     ExprAST *Init = VarNames[i].second.get();
1163
1164     // Emit the initializer before adding the variable to scope, this prevents
1165     // the initializer from referencing the variable itself, and permits stuff
1166     // like this:
1167     //  var a = 1 in
1168     //    var a = a in ...   # refers to outer 'a'.
1169     Value *InitVal;
1170     if (Init) {
1171       InitVal = Init->Codegen();
1172       if (!InitVal)
1173         return nullptr;
1174     } else { // If not specified, use 0.0.
1175       InitVal = ConstantFP::get(getGlobalContext(), APFloat(0.0));
1176     }
1177
1178     AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
1179     Builder.CreateStore(InitVal, Alloca);
1180
1181     // Remember the old variable binding so that we can restore the binding when
1182     // we unrecurse.
1183     OldBindings.push_back(NamedValues[VarName]);
1184
1185     // Remember this binding.
1186     NamedValues[VarName] = Alloca;
1187   }
1188
1189   KSDbgInfo.emitLocation(this);
1190
1191   // Codegen the body, now that all vars are in scope.
1192   Value *BodyVal = Body->Codegen();
1193   if (!BodyVal)
1194     return nullptr;
1195
1196   // Pop all our variables from scope.
1197   for (unsigned i = 0, e = VarNames.size(); i != e; ++i)
1198     NamedValues[VarNames[i].first] = OldBindings[i];
1199
1200   // Return the body computation.
1201   return BodyVal;
1202 }
1203
1204 Function *PrototypeAST::Codegen() {
1205   // Make the function type:  double(double,double) etc.
1206   std::vector<Type *> Doubles(Args.size(),
1207                               Type::getDoubleTy(getGlobalContext()));
1208   FunctionType *FT =
1209       FunctionType::get(Type::getDoubleTy(getGlobalContext()), Doubles, false);
1210
1211   Function *F =
1212       Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
1213
1214   // If F conflicted, there was already something named 'Name'.  If it has a
1215   // body, don't allow redefinition or reextern.
1216   if (F->getName() != Name) {
1217     // Delete the one we just made and get the existing one.
1218     F->eraseFromParent();
1219     F = TheModule->getFunction(Name);
1220
1221     // If F already has a body, reject this.
1222     if (!F->empty()) {
1223       ErrorF("redefinition of function");
1224       return nullptr;
1225     }
1226
1227     // If F took a different number of args, reject.
1228     if (F->arg_size() != Args.size()) {
1229       ErrorF("redefinition of function with different # args");
1230       return nullptr;
1231     }
1232   }
1233
1234   // Set names for all arguments.
1235   unsigned Idx = 0;
1236   for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1237        ++AI, ++Idx)
1238     AI->setName(Args[Idx]);
1239
1240   // Create a subprogram DIE for this function.
1241   DIFile *Unit = DBuilder->createFile(KSDbgInfo.TheCU->getFilename(),
1242                                       KSDbgInfo.TheCU->getDirectory());
1243   DIScope *FContext = Unit;
1244   unsigned LineNo = Line;
1245   unsigned ScopeLine = Line;
1246   DISubprogram *SP = DBuilder->createFunction(
1247       FContext, Name, StringRef(), Unit, LineNo,
1248       CreateFunctionType(Args.size(), Unit), false /* internal linkage */,
1249       true /* definition */, ScopeLine, DINode::FlagPrototyped, false, F);
1250
1251   KSDbgInfo.FnScopeMap[this] = SP;
1252   return F;
1253 }
1254
1255 /// CreateArgumentAllocas - Create an alloca for each argument and register the
1256 /// argument in the symbol table so that references to it will succeed.
1257 void PrototypeAST::CreateArgumentAllocas(Function *F) {
1258   Function::arg_iterator AI = F->arg_begin();
1259   for (unsigned Idx = 0, e = Args.size(); Idx != e; ++Idx, ++AI) {
1260     // Create an alloca for this variable.
1261     AllocaInst *Alloca = CreateEntryBlockAlloca(F, Args[Idx]);
1262
1263     // Create a debug descriptor for the variable.
1264     DIScope *Scope = KSDbgInfo.LexicalBlocks.back();
1265     DIFile *Unit = DBuilder->createFile(KSDbgInfo.TheCU->getFilename(),
1266                                         KSDbgInfo.TheCU->getDirectory());
1267     DILocalVariable *D = DBuilder->createParameterVariable(
1268         Scope, Args[Idx], Idx + 1, Unit, Line, KSDbgInfo.getDoubleTy(), true);
1269
1270     DBuilder->insertDeclare(Alloca, D, DBuilder->createExpression(),
1271                             DebugLoc::get(Line, 0, Scope),
1272                             Builder.GetInsertBlock());
1273
1274     // Store the initial value into the alloca.
1275     Builder.CreateStore(AI, Alloca);
1276
1277     // Add arguments to variable symbol table.
1278     NamedValues[Args[Idx]] = Alloca;
1279   }
1280 }
1281
1282 Function *FunctionAST::Codegen() {
1283   NamedValues.clear();
1284
1285   Function *TheFunction = Proto->Codegen();
1286   if (!TheFunction)
1287     return nullptr;
1288
1289   // Push the current scope.
1290   KSDbgInfo.LexicalBlocks.push_back(KSDbgInfo.FnScopeMap[Proto.get()]);
1291
1292   // Unset the location for the prologue emission (leading instructions with no
1293   // location in a function are considered part of the prologue and the debugger
1294   // will run past them when breaking on a function)
1295   KSDbgInfo.emitLocation(nullptr);
1296
1297   // If this is an operator, install it.
1298   if (Proto->isBinaryOp())
1299     BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence();
1300
1301   // Create a new basic block to start insertion into.
1302   BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1303   Builder.SetInsertPoint(BB);
1304
1305   // Add all arguments to the symbol table and create their allocas.
1306   Proto->CreateArgumentAllocas(TheFunction);
1307
1308   KSDbgInfo.emitLocation(Body.get());
1309
1310   if (Value *RetVal = Body->Codegen()) {
1311     // Finish off the function.
1312     Builder.CreateRet(RetVal);
1313
1314     // Pop off the lexical block for the function.
1315     KSDbgInfo.LexicalBlocks.pop_back();
1316
1317     // Validate the generated code, checking for consistency.
1318     verifyFunction(*TheFunction);
1319
1320     // Optimize the function.
1321     TheFPM->run(*TheFunction);
1322
1323     return TheFunction;
1324   }
1325
1326   // Error reading body, remove function.
1327   TheFunction->eraseFromParent();
1328
1329   if (Proto->isBinaryOp())
1330     BinopPrecedence.erase(Proto->getOperatorName());
1331
1332   // Pop off the lexical block for the function since we added it
1333   // unconditionally.
1334   KSDbgInfo.LexicalBlocks.pop_back();
1335
1336   return nullptr;
1337 }
1338
1339 //===----------------------------------------------------------------------===//
1340 // Top-Level parsing and JIT Driver
1341 //===----------------------------------------------------------------------===//
1342
1343 static ExecutionEngine *TheExecutionEngine;
1344
1345 static void HandleDefinition() {
1346   if (auto FnAST = ParseDefinition()) {
1347     if (!FnAST->Codegen()) {
1348       fprintf(stderr, "Error reading function definition:");
1349     }
1350   } else {
1351     // Skip token for error recovery.
1352     getNextToken();
1353   }
1354 }
1355
1356 static void HandleExtern() {
1357   if (auto ProtoAST = ParseExtern()) {
1358     if (!ProtoAST->Codegen()) {
1359       fprintf(stderr, "Error reading extern");
1360     }
1361   } else {
1362     // Skip token for error recovery.
1363     getNextToken();
1364   }
1365 }
1366
1367 static void HandleTopLevelExpression() {
1368   // Evaluate a top-level expression into an anonymous function.
1369   if (auto FnAST = ParseTopLevelExpr()) {
1370     if (!FnAST->Codegen()) {
1371       fprintf(stderr, "Error generating code for top level expr");
1372     }
1373   } else {
1374     // Skip token for error recovery.
1375     getNextToken();
1376   }
1377 }
1378
1379 /// top ::= definition | external | expression | ';'
1380 static void MainLoop() {
1381   while (1) {
1382     switch (CurTok) {
1383     case tok_eof:
1384       return;
1385     case ';': // ignore top-level semicolons.
1386       getNextToken();
1387       break;
1388     case tok_def:
1389       HandleDefinition();
1390       break;
1391     case tok_extern:
1392       HandleExtern();
1393       break;
1394     default:
1395       HandleTopLevelExpression();
1396       break;
1397     }
1398   }
1399 }
1400
1401 //===----------------------------------------------------------------------===//
1402 // "Library" functions that can be "extern'd" from user code.
1403 //===----------------------------------------------------------------------===//
1404
1405 /// putchard - putchar that takes a double and returns 0.
1406 extern "C" double putchard(double X) {
1407   putchar((char)X);
1408   return 0;
1409 }
1410
1411 /// printd - printf that takes a double prints it as "%f\n", returning 0.
1412 extern "C" double printd(double X) {
1413   printf("%f\n", X);
1414   return 0;
1415 }
1416
1417 //===----------------------------------------------------------------------===//
1418 // Main driver code.
1419 //===----------------------------------------------------------------------===//
1420
1421 int main() {
1422   InitializeNativeTarget();
1423   InitializeNativeTargetAsmPrinter();
1424   InitializeNativeTargetAsmParser();
1425   LLVMContext &Context = getGlobalContext();
1426
1427   // Install standard binary operators.
1428   // 1 is lowest precedence.
1429   BinopPrecedence['='] = 2;
1430   BinopPrecedence['<'] = 10;
1431   BinopPrecedence['+'] = 20;
1432   BinopPrecedence['-'] = 20;
1433   BinopPrecedence['*'] = 40; // highest.
1434
1435   // Prime the first token.
1436   getNextToken();
1437
1438   // Make the module, which holds all the code.
1439   std::unique_ptr<Module> Owner = make_unique<Module>("my cool jit", Context);
1440   TheModule = Owner.get();
1441
1442   // Add the current debug info version into the module.
1443   TheModule->addModuleFlag(Module::Warning, "Debug Info Version",
1444                            DEBUG_METADATA_VERSION);
1445
1446   // Darwin only supports dwarf2.
1447   if (Triple(sys::getProcessTriple()).isOSDarwin())
1448     TheModule->addModuleFlag(llvm::Module::Warning, "Dwarf Version", 2);
1449
1450   // Construct the DIBuilder, we do this here because we need the module.
1451   DBuilder = new DIBuilder(*TheModule);
1452
1453   // Create the compile unit for the module.
1454   // Currently down as "fib.ks" as a filename since we're redirecting stdin
1455   // but we'd like actual source locations.
1456   KSDbgInfo.TheCU = DBuilder->createCompileUnit(
1457       dwarf::DW_LANG_C, "fib.ks", ".", "Kaleidoscope Compiler", 0, "", 0);
1458
1459   // Create the JIT.  This takes ownership of the module.
1460   std::string ErrStr;
1461   TheExecutionEngine =
1462       EngineBuilder(std::move(Owner))
1463           .setErrorStr(&ErrStr)
1464           .setMCJITMemoryManager(llvm::make_unique<SectionMemoryManager>())
1465           .create();
1466   if (!TheExecutionEngine) {
1467     fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
1468     exit(1);
1469   }
1470
1471   legacy::FunctionPassManager OurFPM(TheModule);
1472
1473   // Set up the optimizer pipeline.  Start with registering info about how the
1474   // target lays out data structures.
1475   TheModule->setDataLayout(TheExecutionEngine->getDataLayout());
1476 #if 0
1477   // Provide basic AliasAnalysis support for GVN.
1478   OurFPM.add(createBasicAliasAnalysisPass());
1479   // Promote allocas to registers.
1480   OurFPM.add(createPromoteMemoryToRegisterPass());
1481   // Do simple "peephole" optimizations and bit-twiddling optzns.
1482   OurFPM.add(createInstructionCombiningPass());
1483   // Reassociate expressions.
1484   OurFPM.add(createReassociatePass());
1485   // Eliminate Common SubExpressions.
1486   OurFPM.add(createGVNPass());
1487   // Simplify the control flow graph (deleting unreachable blocks, etc).
1488   OurFPM.add(createCFGSimplificationPass());
1489 #endif
1490   OurFPM.doInitialization();
1491
1492   // Set the global so the code gen can use this.
1493   TheFPM = &OurFPM;
1494
1495   // Run the main "interpreter loop" now.
1496   MainLoop();
1497
1498   TheFPM = 0;
1499
1500   // Finalize the debug info.
1501   DBuilder->finalize();
1502
1503   // Print out all of the generated code.
1504   TheModule->dump();
1505
1506   return 0;
1507 }