examples/Kaleidoscope/Chapter7/toy.cpp

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