llvm/examples/Kaleidoscope/Chapter8/toy.cpp

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