examples/Kaleidoscope/Chapter6/toy.cpp

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