examples/Kaleidoscope/Chapter3/toy.cpp

   1 #include "llvm/ADT/STLExtras.h"
   2 #include "llvm/IR/Verifier.h"
   3 #include "llvm/IR/DerivedTypes.h"
   4 #include "llvm/IR/IRBuilder.h"
   5 #include "llvm/IR/LLVMContext.h"
   6 #include "llvm/IR/Module.h"
   7 #include <cctype>
   8 #include <cstdio>
   9 #include <map>
  10 #include <string>
  11 #include <vector>
  12 using namespace llvm;
  13
  14 //===----------------------------------------------------------------------===//
  15 // Lexer
  16 //===----------------------------------------------------------------------===//
  17
  18 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
  19 // of these for known things.
  20 enum Token {
  21   tok_eof = -1,
  22
  23   // commands
  24   tok_def = -2, tok_extern = -3,
  25
  26   // primary
  27   tok_identifier = -4, tok_number = -5
  28 };
  29
  30 static std::string IdentifierStr;  // Filled in if tok_identifier
  31 static double NumVal;              // Filled in if tok_number
  32
  33 /// gettok - Return the next token from standard input.
  34 static int gettok() {
  35   static int LastChar = ' ';
  36
  37   // Skip any whitespace.
  38   while (isspace(LastChar))
  39     LastChar = getchar();
  40
  41   if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
  42     IdentifierStr = LastChar;
  43     while (isalnum((LastChar = getchar())))
  44       IdentifierStr += LastChar;
  45
  46     if (IdentifierStr == "def") return tok_def;
  47     if (IdentifierStr == "extern") return tok_extern;
  48     return tok_identifier;
  49   }
  50
  51   if (isdigit(LastChar) || LastChar == '.') {   // Number: [0-9.]+
  52     std::string NumStr;
  53     do {
  54       NumStr += LastChar;
  55       LastChar = getchar();
  56     } while (isdigit(LastChar) || LastChar == '.');
  57
  58     NumVal = strtod(NumStr.c_str(), 0);
  59     return tok_number;
  60   }
  61
  62   if (LastChar == '#') {
  63     // Comment until end of line.
  64     do LastChar = getchar();
  65     while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
  66
  67     if (LastChar != EOF)
  68       return gettok();
  69   }
  70
  71   // Check for end of file.  Don't eat the EOF.
  72   if (LastChar == EOF)
  73     return tok_eof;
  74
  75   // Otherwise, just return the character as its ascii value.
  76   int ThisChar = LastChar;
  77   LastChar = getchar();
  78   return ThisChar;
  79 }
  80
  81 //===----------------------------------------------------------------------===//
  82 // Abstract Syntax Tree (aka Parse Tree)
  83 //===----------------------------------------------------------------------===//
  84 namespace {
  85 /// ExprAST - Base class for all expression nodes.
  86 class ExprAST {
  87 public:
  88   virtual ~ExprAST() {}
  89   virtual Value *Codegen() = 0;
  90 };
  91
  92 /// NumberExprAST - Expression class for numeric literals like "1.0".
  93 class NumberExprAST : public ExprAST {
  94   double Val;
  95 public:
  96   NumberExprAST(double Val) : Val(Val) {}
  97   Value *Codegen() override;
  98 };
  99
 100 /// VariableExprAST - Expression class for referencing a variable, like "a".
 101 class VariableExprAST : public ExprAST {
 102   std::string Name;
 103 public:
 104   VariableExprAST(const std::string &Name) : Name(Name) {}
 105   Value *Codegen() override;
 106 };
 107
 108 /// BinaryExprAST - Expression class for a binary operator.
 109 class BinaryExprAST : public ExprAST {
 110   char Op;
 111   std::unique_ptr<ExprAST> LHS, RHS;
 112 public:
 113   BinaryExprAST(char Op, std::unique_ptr<ExprAST> LHS,
 114                 std::unique_ptr<ExprAST> RHS)
 115     : Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}
 116   Value *Codegen() override;
 117 };
 118
 119 /// CallExprAST - Expression class for function calls.
 120 class CallExprAST : public ExprAST {
 121   std::string Callee;
 122   std::vector<std::unique_ptr<ExprAST>> Args;
 123 public:
 124   CallExprAST(const std::string &Callee,
 125               std::vector<std::unique_ptr<ExprAST>> Args)
 126     : Callee(Callee), Args(std::move(Args)) {}
 127   Value *Codegen() override;
 128 };
 129
 130 /// PrototypeAST - This class represents the "prototype" for a function,
 131 /// which captures its name, and its argument names (thus implicitly the number
 132 /// of arguments the function takes).
 133 class PrototypeAST {
 134   std::string Name;
 135   std::vector<std::string> Args;
 136 public:
 137   PrototypeAST(const std::string &Name, std::vector<std::string> Args)
 138     : Name(Name), Args(std::move(Args)) {}
 139
 140   Function *Codegen();
 141 };
 142
 143 /// FunctionAST - This class represents a function definition itself.
 144 class FunctionAST {
 145   std::unique_ptr<PrototypeAST> Proto;
 146   std::unique_ptr<ExprAST> Body;
 147 public:
 148   FunctionAST(std::unique_ptr<PrototypeAST> Proto,
 149               std::unique_ptr<ExprAST> Body)
 150     : Proto(std::move(Proto)), Body(std::move(Body)) {}
 151
 152   Function *Codegen();
 153 };
 154 } // end anonymous namespace
 155
 156 //===----------------------------------------------------------------------===//
 157 // Parser
 158 //===----------------------------------------------------------------------===//
 159
 160 /// CurTok/getNextToken - Provide a simple token buffer.  CurTok is the current
 161 /// token the parser is looking at.  getNextToken reads another token from the
 162 /// lexer and updates CurTok with its results.
 163 static int CurTok;
 164 static int getNextToken() {
 165   return CurTok = gettok();
 166 }
 167
 168 /// BinopPrecedence - This holds the precedence for each binary operator that is
 169 /// defined.
 170 static std::map<char, int> BinopPrecedence;
 171
 172 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
 173 static int GetTokPrecedence() {
 174   if (!isascii(CurTok))
 175     return -1;
 176
 177   // Make sure it's a declared binop.
 178   int TokPrec = BinopPrecedence[CurTok];
 179   if (TokPrec <= 0) return -1;
 180   return TokPrec;
 181 }
 182
 183 /// Error* - These are little helper functions for error handling.
 184 std::unique_ptr<ExprAST> Error(const char *Str) {
 185   fprintf(stderr, "Error: %s\n", Str);
 186   return nullptr;
 187 }
 188 std::unique_ptr<PrototypeAST> ErrorP(const char *Str) {
 189   Error(Str);
 190   return nullptr;
 191 }
 192 std::unique_ptr<FunctionAST> ErrorF(const char *Str) {
 193   Error(Str);
 194   return nullptr;
 195 }
 196
 197 static std::unique_ptr<ExprAST> ParseExpression();
 198
 199 /// identifierexpr
 200 ///   ::= identifier
 201 ///   ::= identifier '(' expression* ')'
 202 static std::unique_ptr<ExprAST> ParseIdentifierExpr() {
 203   std::string IdName = IdentifierStr;
 204
 205   getNextToken();  // eat identifier.
 206
 207   if (CurTok != '(') // Simple variable ref.
 208     return llvm::make_unique<VariableExprAST>(IdName);
 209
 210   // Call.
 211   getNextToken();  // eat (
 212   std::vector<std::unique_ptr<ExprAST>> Args;
 213   if (CurTok != ')') {
 214     while (1) {
 215       if (auto Arg = ParseExpression())
 216         Args.push_back(std::move(Arg));
 217       else
 218         return nullptr;
 219
 220       if (CurTok == ')') break;
 221
 222       if (CurTok != ',')
 223         return Error("Expected ')' or ',' in argument list");
 224       getNextToken();
 225     }
 226   }
 227
 228   // Eat the ')'.
 229   getNextToken();
 230
 231   return llvm::make_unique<CallExprAST>(IdName, std::move(Args));
 232 }
 233
 234 /// numberexpr ::= number
 235 static std::unique_ptr<ExprAST> ParseNumberExpr() {
 236   auto Result = llvm::make_unique<NumberExprAST>(NumVal);
 237   getNextToken(); // consume the number
 238   return std::move(Result);
 239 }
 240
 241 /// parenexpr ::= '(' expression ')'
 242 static std::unique_ptr<ExprAST> ParseParenExpr() {
 243   getNextToken();  // eat (.
 244   auto V = ParseExpression();
 245   if (!V)
 246     return nullptr;
 247
 248   if (CurTok != ')')
 249     return Error("expected ')'");
 250   getNextToken();  // eat ).
 251   return V;
 252 }
 253
 254 /// primary
 255 ///   ::= identifierexpr
 256 ///   ::= numberexpr
 257 ///   ::= parenexpr
 258 static std::unique_ptr<ExprAST> ParsePrimary() {
 259   switch (CurTok) {
 260   default: return Error("unknown token when expecting an expression");
 261   case tok_identifier: return ParseIdentifierExpr();
 262   case tok_number:     return ParseNumberExpr();
 263   case '(':            return ParseParenExpr();
 264   }
 265 }
 266
 267 /// binoprhs
 268 ///   ::= ('+' primary)*
 269 static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
 270                                               std::unique_ptr<ExprAST> LHS) {
 271   // If this is a binop, find its precedence.
 272   while (1) {
 273     int TokPrec = GetTokPrecedence();
 274
 275     // If this is a binop that binds at least as tightly as the current binop,
 276     // consume it, otherwise we are done.
 277     if (TokPrec < ExprPrec)
 278       return LHS;
 279
 280     // Okay, we know this is a binop.
 281     int BinOp = CurTok;
 282     getNextToken();  // eat binop
 283
 284     // Parse the primary expression after the binary operator.
 285     auto RHS = ParsePrimary();
 286     if (!RHS) return nullptr;
 287
 288     // If BinOp binds less tightly with RHS than the operator after RHS, let
 289     // the pending operator take RHS as its LHS.
 290     int NextPrec = GetTokPrecedence();
 291     if (TokPrec < NextPrec) {
 292       RHS = ParseBinOpRHS(TokPrec+1, std::move(RHS));
 293       if (!RHS) return nullptr;
 294     }
 295
 296     // Merge LHS/RHS.
 297     LHS = llvm::make_unique<BinaryExprAST>(BinOp, std::move(LHS),
 298                                            std::move(RHS));
 299   }
 300 }
 301
 302 /// expression
 303 ///   ::= primary binoprhs
 304 ///
 305 static std::unique_ptr<ExprAST> ParseExpression() {
 306   auto LHS = ParsePrimary();
 307   if (!LHS) return nullptr;
 308
 309   return ParseBinOpRHS(0, std::move(LHS));
 310 }
 311
 312 /// prototype
 313 ///   ::= id '(' id* ')'
 314 static std::unique_ptr<PrototypeAST> ParsePrototype() {
 315   if (CurTok != tok_identifier)
 316     return ErrorP("Expected function name in prototype");
 317
 318   std::string FnName = IdentifierStr;
 319   getNextToken();
 320
 321   if (CurTok != '(')
 322     return ErrorP("Expected '(' in prototype");
 323
 324   std::vector<std::string> ArgNames;
 325   while (getNextToken() == tok_identifier)
 326     ArgNames.push_back(IdentifierStr);
 327   if (CurTok != ')')
 328     return ErrorP("Expected ')' in prototype");
 329
 330   // success.
 331   getNextToken();  // eat ')'.
 332
 333   return llvm::make_unique<PrototypeAST>(std::move(FnName),
 334                                          std::move(ArgNames));
 335 }
 336
 337 /// definition ::= 'def' prototype expression
 338 static std::unique_ptr<FunctionAST> ParseDefinition() {
 339   getNextToken();  // eat def.
 340   auto Proto = ParsePrototype();
 341   if (!Proto) return nullptr;
 342
 343   if (auto E = ParseExpression())
 344     return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E));
 345   return nullptr;
 346 }
 347
 348 /// toplevelexpr ::= expression
 349 static std::unique_ptr<FunctionAST> ParseTopLevelExpr() {
 350   if (auto E = ParseExpression()) {
 351     // Make an anonymous proto.
 352     auto Proto = llvm::make_unique<PrototypeAST>("",
 353                                                  std::vector<std::string>());
 354     return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E));
 355   }
 356   return nullptr;
 357 }
 358
 359 /// external ::= 'extern' prototype
 360 static std::unique_ptr<PrototypeAST> ParseExtern() {
 361   getNextToken();  // eat extern.
 362   return ParsePrototype();
 363 }
 364
 365 //===----------------------------------------------------------------------===//
 366 // Code Generation
 367 //===----------------------------------------------------------------------===//
 368
 369 static Module *TheModule;
 370 static IRBuilder<> Builder(getGlobalContext());
 371 static std::map<std::string, Value*> NamedValues;
 372
 373 Value *ErrorV(const char *Str) { Error(Str); return nullptr; }
 374
 375 Value *NumberExprAST::Codegen() {
 376   return ConstantFP::get(getGlobalContext(), APFloat(Val));
 377 }
 378
 379 Value *VariableExprAST::Codegen() {
 380   // Look this variable up in the function.
 381   Value *V = NamedValues[Name];
 382   return V ? V : ErrorV("Unknown variable name");
 383 }
 384
 385 Value *BinaryExprAST::Codegen() {
 386   Value *L = LHS->Codegen();
 387   Value *R = RHS->Codegen();
 388   if (!L || !R) return nullptr;
 389
 390   switch (Op) {
 391   case '+': return Builder.CreateFAdd(L, R, "addtmp");
 392   case '-': return Builder.CreateFSub(L, R, "subtmp");
 393   case '*': return Builder.CreateFMul(L, R, "multmp");
 394   case '<':
 395     L = Builder.CreateFCmpULT(L, R, "cmptmp");
 396     // Convert bool 0/1 to double 0.0 or 1.0
 397     return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
 398                                 "booltmp");
 399   default: return ErrorV("invalid binary operator");
 400   }
 401 }
 402
 403 Value *CallExprAST::Codegen() {
 404   // Look up the name in the global module table.
 405   Function *CalleeF = TheModule->getFunction(Callee);
 406   if (!CalleeF)
 407     return ErrorV("Unknown function referenced");
 408
 409   // If argument mismatch error.
 410   if (CalleeF->arg_size() != Args.size())
 411     return ErrorV("Incorrect # arguments passed");
 412
 413   std::vector<Value*> ArgsV;
 414   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 415     ArgsV.push_back(Args[i]->Codegen());
 416     if (!ArgsV.back()) return nullptr;
 417   }
 418
 419   return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
 420 }
 421
 422 Function *PrototypeAST::Codegen() {
 423   // Make the function type:  double(double,double) etc.
 424   std::vector<Type*> Doubles(Args.size(),
 425                              Type::getDoubleTy(getGlobalContext()));
 426   FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
 427                                        Doubles, false);
 428
 429   Function *F = Function::Create(FT, Function::ExternalLinkage, Name,
 430                                  TheModule);
 431
 432   // If F conflicted, there was already something named 'Name'.  If it has a
 433   // body, don't allow redefinition or reextern.
 434   if (F->getName() != Name) {
 435     // Delete the one we just made and get the existing one.
 436     F->eraseFromParent();
 437     F = TheModule->getFunction(Name);
 438
 439     // If F already has a body, reject this.
 440     if (!F->empty()) {
 441       ErrorF("redefinition of function");
 442       return nullptr;
 443     }
 444
 445     // If F took a different number of args, reject.
 446     if (F->arg_size() != Args.size()) {
 447       ErrorF("redefinition of function with different # args");
 448       return nullptr;
 449     }
 450   }
 451
 452   // Set names for all arguments.
 453   unsigned Idx = 0;
 454   for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
 455        ++AI, ++Idx) {
 456     AI->setName(Args[Idx]);
 457
 458     // Add arguments to variable symbol table.
 459     NamedValues[Args[Idx]] = AI;
 460   }
 461
 462   return F;
 463 }
 464
 465 Function *FunctionAST::Codegen() {
 466   NamedValues.clear();
 467
 468   Function *TheFunction = Proto->Codegen();
 469   if (!TheFunction)
 470     return nullptr;
 471
 472   // Create a new basic block to start insertion into.
 473   BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
 474   Builder.SetInsertPoint(BB);
 475
 476   if (Value *RetVal = Body->Codegen()) {
 477     // Finish off the function.
 478     Builder.CreateRet(RetVal);
 479
 480     // Validate the generated code, checking for consistency.
 481     verifyFunction(*TheFunction);
 482
 483     return TheFunction;
 484   }
 485
 486   // Error reading body, remove function.
 487   TheFunction->eraseFromParent();
 488   return nullptr;
 489 }
 490
 491 //===----------------------------------------------------------------------===//
 492 // Top-Level parsing and JIT Driver
 493 //===----------------------------------------------------------------------===//
 494
 495 static void HandleDefinition() {
 496   if (auto FnAST = ParseDefinition()) {
 497     if (auto *FnIR = FnAST->Codegen()) {
 498       fprintf(stderr, "Read function definition:");
 499       FnIR->dump();
 500     }
 501   } else {
 502     // Skip token for error recovery.
 503     getNextToken();
 504   }
 505 }
 506
 507 static void HandleExtern() {
 508   if (auto ProtoAST = ParseExtern()) {
 509     if (auto *FnIR = ProtoAST->Codegen()) {
 510       fprintf(stderr, "Read extern: ");
 511       FnIR->dump();
 512     }
 513   } else {
 514     // Skip token for error recovery.
 515     getNextToken();
 516   }
 517 }
 518
 519 static void HandleTopLevelExpression() {
 520   // Evaluate a top-level expression into an anonymous function.
 521   if (auto FnAST = ParseTopLevelExpr()) {
 522     if (auto *FnIR = FnAST->Codegen()) {
 523       fprintf(stderr, "Read top-level expression:");
 524       FnIR->dump();
 525     }
 526   } else {
 527     // Skip token for error recovery.
 528     getNextToken();
 529   }
 530 }
 531
 532 /// top ::= definition | external | expression | ';'
 533 static void MainLoop() {
 534   while (1) {
 535     fprintf(stderr, "ready> ");
 536     switch (CurTok) {
 537     case tok_eof:    return;
 538     case ';':        getNextToken(); break;  // ignore top-level semicolons.
 539     case tok_def:    HandleDefinition(); break;
 540     case tok_extern: HandleExtern(); break;
 541     default:         HandleTopLevelExpression(); break;
 542     }
 543   }
 544 }
 545
 546 //===----------------------------------------------------------------------===//
 547 // "Library" functions that can be "extern'd" from user code.
 548 //===----------------------------------------------------------------------===//
 549
 550 /// putchard - putchar that takes a double and returns 0.
 551 extern "C"
 552 double putchard(double X) {
 553   putchar((char)X);
 554   return 0;
 555 }
 556
 557 //===----------------------------------------------------------------------===//
 558 // Main driver code.
 559 //===----------------------------------------------------------------------===//
 560
 561 int main() {
 562   LLVMContext &Context = getGlobalContext();
 563
 564   // Install standard binary operators.
 565   // 1 is lowest precedence.
 566   BinopPrecedence['<'] = 10;
 567   BinopPrecedence['+'] = 20;
 568   BinopPrecedence['-'] = 20;
 569   BinopPrecedence['*'] = 40;  // highest.
 570
 571   // Prime the first token.
 572   fprintf(stderr, "ready> ");
 573   getNextToken();
 574
 575   // Make the module, which holds all the code.
 576   std::unique_ptr<Module> Owner = llvm::make_unique<Module>("my cool jit", Context);
 577   TheModule = Owner.get();
 578
 579   // Run the main "interpreter loop" now.
 580   MainLoop();
 581
 582   // Print out all of the generated code.
 583   TheModule->dump();
 584
 585   return 0;
 586 }