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