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