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