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