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