examples/Kaleidoscope/BuildingAJIT/Chapter5/toy.cpp

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