14c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/ADT/STLExtras.h" 24ca7e09b7c1e41535f2a1bd86915375d023daf27Chandler Carruth#include "llvm/Analysis/Passes.h" 30a08460599eed603e469e3e16d0cf6aa33b8ba93Chandler Carruth#include "llvm/IR/IRBuilder.h" 40a08460599eed603e469e3e16d0cf6aa33b8ba93Chandler Carruth#include "llvm/IR/LLVMContext.h" 5ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/IR/LegacyPassManager.h" 60a08460599eed603e469e3e16d0cf6aa33b8ba93Chandler Carruth#include "llvm/IR/Module.h" 736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Verifier.h" 83e74d6fdd248e20a280f1dff3da9a6c689c2c4c3Evan Cheng#include "llvm/Support/TargetSelect.h" 94ca7e09b7c1e41535f2a1bd86915375d023daf27Chandler Carruth#include "llvm/Transforms/Scalar.h" 10e3ba15c794839abe076e3e2bdf6c626396a19d4dWill Dietz#include <cctype> 119f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky#include <cstdio> 129f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky#include <map> 134ca7e09b7c1e41535f2a1bd86915375d023daf27Chandler Carruth#include <string> 149f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky#include <vector> 15cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar#include "../include/KaleidoscopeJIT.h" 16cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 179f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckyusing namespace llvm; 18cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarusing namespace llvm::orc; 199f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 209f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky//===----------------------------------------------------------------------===// 219f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky// Lexer 229f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky//===----------------------------------------------------------------------===// 239f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 249f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky// The lexer returns tokens [0-255] if it is an unknown character, otherwise one 259f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky// of these for known things. 269f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckyenum Token { 279f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky tok_eof = -1, 289f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 299f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // commands 30ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines tok_def = -2, 31ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines tok_extern = -3, 329f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 339f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // primary 34ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines tok_identifier = -4, 35ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines tok_number = -5, 36ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 379f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // control 38ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines tok_if = -6, 39ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines tok_then = -7, 40ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines tok_else = -8, 41ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines tok_for = -9, 42ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines tok_in = -10, 43ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 449f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // operators 45ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines tok_binary = -11, 46ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines tok_unary = -12, 47ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 489f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // var definition 499f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky tok_var = -13 509f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky}; 519f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 52ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstatic std::string IdentifierStr; // Filled in if tok_identifier 53ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstatic double NumVal; // Filled in if tok_number 549f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 559f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// gettok - Return the next token from standard input. 569f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckystatic int gettok() { 579f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky static int LastChar = ' '; 589f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 599f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Skip any whitespace. 609f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky while (isspace(LastChar)) 619f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky LastChar = getchar(); 629f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 639f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]* 649f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky IdentifierStr = LastChar; 659f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky while (isalnum((LastChar = getchar()))) 669f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky IdentifierStr += LastChar; 679f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 68ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (IdentifierStr == "def") 69ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return tok_def; 70ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (IdentifierStr == "extern") 71ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return tok_extern; 72ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (IdentifierStr == "if") 73ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return tok_if; 74ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (IdentifierStr == "then") 75ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return tok_then; 76ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (IdentifierStr == "else") 77ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return tok_else; 78ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (IdentifierStr == "for") 79ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return tok_for; 80ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (IdentifierStr == "in") 81ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return tok_in; 82ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (IdentifierStr == "binary") 83ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return tok_binary; 84ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (IdentifierStr == "unary") 85ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return tok_unary; 86ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (IdentifierStr == "var") 87ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return tok_var; 889f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return tok_identifier; 899f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 909f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 91ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+ 929f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky std::string NumStr; 939f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky do { 949f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky NumStr += LastChar; 959f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky LastChar = getchar(); 969f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } while (isdigit(LastChar) || LastChar == '.'); 979f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 98cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar NumVal = strtod(NumStr.c_str(), nullptr); 999f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return tok_number; 1009f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 1019f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 1029f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (LastChar == '#') { 1039f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Comment until end of line. 104ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines do 105ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LastChar = getchar(); 1069f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky while (LastChar != EOF && LastChar != '\n' && LastChar != '\r'); 107ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1089f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (LastChar != EOF) 1099f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return gettok(); 1109f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 111ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1129f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Check for end of file. Don't eat the EOF. 1139f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (LastChar == EOF) 1149f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return tok_eof; 1159f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 1169f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Otherwise, just return the character as its ascii value. 1179f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky int ThisChar = LastChar; 1189f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky LastChar = getchar(); 1199f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return ThisChar; 1209f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 1219f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 1229f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky//===----------------------------------------------------------------------===// 1239f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky// Abstract Syntax Tree (aka Parse Tree) 1249f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky//===----------------------------------------------------------------------===// 1259d7c776d32c8a4d64b37a91c2d627629cf1498efBill Wendlingnamespace { 1269f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// ExprAST - Base class for all expression nodes. 1279f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckyclass ExprAST { 1289f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckypublic: 1299d7c776d32c8a4d64b37a91c2d627629cf1498efBill Wendling virtual ~ExprAST() {} 130cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar virtual Value *codegen() = 0; 1319f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky}; 1329f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 1339f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// NumberExprAST - Expression class for numeric literals like "1.0". 1349f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckyclass NumberExprAST : public ExprAST { 1359f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky double Val; 136ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1379f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckypublic: 138cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar NumberExprAST(double Val) : Val(Val) {} 139cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *codegen() override; 1409f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky}; 1419f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 1429f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// VariableExprAST - Expression class for referencing a variable, like "a". 1439f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckyclass VariableExprAST : public ExprAST { 1449f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky std::string Name; 145ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1469f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckypublic: 147cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar VariableExprAST(const std::string &Name) : Name(Name) {} 1489f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky const std::string &getName() const { return Name; } 149cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *codegen() override; 1509f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky}; 1519f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 1529f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// UnaryExprAST - Expression class for a unary operator. 1539f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckyclass UnaryExprAST : public ExprAST { 1549f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky char Opcode; 155cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::unique_ptr<ExprAST> Operand; 156ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1579f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckypublic: 158cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar UnaryExprAST(char Opcode, std::unique_ptr<ExprAST> Operand) 159cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar : Opcode(Opcode), Operand(std::move(Operand)) {} 160cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *codegen() override; 1619f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky}; 1629f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 1639f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// BinaryExprAST - Expression class for a binary operator. 1649f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckyclass BinaryExprAST : public ExprAST { 1659f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky char Op; 166cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::unique_ptr<ExprAST> LHS, RHS; 167ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1689f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckypublic: 169cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar BinaryExprAST(char Op, std::unique_ptr<ExprAST> LHS, 170cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::unique_ptr<ExprAST> RHS) 171cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar : Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {} 172cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *codegen() override; 1739f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky}; 1749f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 1759f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// CallExprAST - Expression class for function calls. 1769f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckyclass CallExprAST : public ExprAST { 1779f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky std::string Callee; 178cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::vector<std::unique_ptr<ExprAST>> Args; 179ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1809f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckypublic: 181cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar CallExprAST(const std::string &Callee, 182cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::vector<std::unique_ptr<ExprAST>> Args) 183cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar : Callee(Callee), Args(std::move(Args)) {} 184cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *codegen() override; 1859f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky}; 1869f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 1879f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// IfExprAST - Expression class for if/then/else. 1889f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckyclass IfExprAST : public ExprAST { 189cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::unique_ptr<ExprAST> Cond, Then, Else; 190ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1919f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckypublic: 192cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar IfExprAST(std::unique_ptr<ExprAST> Cond, std::unique_ptr<ExprAST> Then, 193cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::unique_ptr<ExprAST> Else) 194cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar : Cond(std::move(Cond)), Then(std::move(Then)), Else(std::move(Else)) {} 195cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *codegen() override; 1969f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky}; 1979f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 1989f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// ForExprAST - Expression class for for/in. 1999f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckyclass ForExprAST : public ExprAST { 2009f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky std::string VarName; 201cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::unique_ptr<ExprAST> Start, End, Step, Body; 202ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 2039f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckypublic: 204cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar ForExprAST(const std::string &VarName, std::unique_ptr<ExprAST> Start, 205cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::unique_ptr<ExprAST> End, std::unique_ptr<ExprAST> Step, 206cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::unique_ptr<ExprAST> Body) 207cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar : VarName(VarName), Start(std::move(Start)), End(std::move(End)), 208cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Step(std::move(Step)), Body(std::move(Body)) {} 209cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *codegen() override; 2109f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky}; 2119f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 2129f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// VarExprAST - Expression class for var/in 2139f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckyclass VarExprAST : public ExprAST { 214cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames; 215cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::unique_ptr<ExprAST> Body; 216ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 2179f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckypublic: 218cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar VarExprAST( 219cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames, 220cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::unique_ptr<ExprAST> Body) 221cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar : VarNames(std::move(VarNames)), Body(std::move(Body)) {} 222cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *codegen() override; 2239f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky}; 2249f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 2259f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// PrototypeAST - This class represents the "prototype" for a function, 226cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar/// which captures its name, and its argument names (thus implicitly the number 227cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar/// of arguments the function takes), as well as if it is an operator. 2289f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckyclass PrototypeAST { 2299f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky std::string Name; 2309f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky std::vector<std::string> Args; 231cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar bool IsOperator; 232ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines unsigned Precedence; // Precedence if a binary op. 233cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 2349f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckypublic: 235cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar PrototypeAST(const std::string &Name, std::vector<std::string> Args, 236cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar bool IsOperator = false, unsigned Prec = 0) 237cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar : Name(Name), Args(std::move(Args)), IsOperator(IsOperator), 238cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Precedence(Prec) {} 239cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Function *codegen(); 240cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar const std::string &getName() const { return Name; } 241ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 242cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar bool isUnaryOp() const { return IsOperator && Args.size() == 1; } 243cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar bool isBinaryOp() const { return IsOperator && Args.size() == 2; } 244ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 2459f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky char getOperatorName() const { 2469f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky assert(isUnaryOp() || isBinaryOp()); 247ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return Name[Name.size() - 1]; 2489f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 249ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 2509f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky unsigned getBinaryPrecedence() const { return Precedence; } 2519f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky}; 2529f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 2539f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// FunctionAST - This class represents a function definition itself. 2549f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckyclass FunctionAST { 255cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::unique_ptr<PrototypeAST> Proto; 256cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::unique_ptr<ExprAST> Body; 257ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 2589f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckypublic: 259cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar FunctionAST(std::unique_ptr<PrototypeAST> Proto, 260cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::unique_ptr<ExprAST> Body) 261cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar : Proto(std::move(Proto)), Body(std::move(Body)) {} 262cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Function *codegen(); 2639f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky}; 2649d7c776d32c8a4d64b37a91c2d627629cf1498efBill Wendling} // end anonymous namespace 2659f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 2669f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky//===----------------------------------------------------------------------===// 2679f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky// Parser 2689f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky//===----------------------------------------------------------------------===// 2699f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 2709f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current 271fd1ec5e68b593a4f4d5497b150e677ebef36c231Erick Tryzelaar/// token the parser is looking at. getNextToken reads another token from the 2729f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// lexer and updates CurTok with its results. 2739f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckystatic int CurTok; 274ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstatic int getNextToken() { return CurTok = gettok(); } 2759f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 2769f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// BinopPrecedence - This holds the precedence for each binary operator that is 2779f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// defined. 2789f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckystatic std::map<char, int> BinopPrecedence; 2799f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 2809f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// GetTokPrecedence - Get the precedence of the pending binary operator token. 2819f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckystatic int GetTokPrecedence() { 2829f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (!isascii(CurTok)) 2839f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return -1; 284ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 2859f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Make sure it's a declared binop. 2869f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky int TokPrec = BinopPrecedence[CurTok]; 287ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (TokPrec <= 0) 288ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return -1; 2899f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return TokPrec; 2909f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 2919f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 2929f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// Error* - These are little helper functions for error handling. 293cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstd::unique_ptr<ExprAST> Error(const char *Str) { 294ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines fprintf(stderr, "Error: %s\n", Str); 295cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 296ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 297cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 298cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstd::unique_ptr<PrototypeAST> ErrorP(const char *Str) { 299ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Error(Str); 300cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 301ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 302cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 303cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::unique_ptr<ExprAST> ParseExpression(); 304cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 305cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar/// numberexpr ::= number 306cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::unique_ptr<ExprAST> ParseNumberExpr() { 307cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar auto Result = llvm::make_unique<NumberExprAST>(NumVal); 308cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar getNextToken(); // consume the number 309cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return std::move(Result); 310ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 3119f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 312cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar/// parenexpr ::= '(' expression ')' 313cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::unique_ptr<ExprAST> ParseParenExpr() { 314cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar getNextToken(); // eat (. 315cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar auto V = ParseExpression(); 316cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!V) 317cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 318cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 319cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (CurTok != ')') 320cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return Error("expected ')'"); 321cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar getNextToken(); // eat ). 322cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return V; 323cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar} 3249f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 3259f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// identifierexpr 3269f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// ::= identifier 3279f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// ::= identifier '(' expression* ')' 328cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::unique_ptr<ExprAST> ParseIdentifierExpr() { 3299f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky std::string IdName = IdentifierStr; 330ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 331ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines getNextToken(); // eat identifier. 332ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3339f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (CurTok != '(') // Simple variable ref. 334cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return llvm::make_unique<VariableExprAST>(IdName); 335ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3369f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Call. 337ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines getNextToken(); // eat ( 338cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::vector<std::unique_ptr<ExprAST>> Args; 3399f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (CurTok != ')') { 3409f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky while (1) { 341cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (auto Arg = ParseExpression()) 342cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Args.push_back(std::move(Arg)); 343cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar else 344cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 345fd1ec5e68b593a4f4d5497b150e677ebef36c231Erick Tryzelaar 346ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (CurTok == ')') 347ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines break; 348fd1ec5e68b593a4f4d5497b150e677ebef36c231Erick Tryzelaar 3499f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (CurTok != ',') 3509f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return Error("Expected ')' or ',' in argument list"); 3519f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky getNextToken(); 3529f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 3539f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 3549f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 3559f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Eat the ')'. 3569f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky getNextToken(); 357ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 358cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return llvm::make_unique<CallExprAST>(IdName, std::move(Args)); 3599f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 3609f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 3619f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// ifexpr ::= 'if' expression 'then' expression 'else' expression 362cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::unique_ptr<ExprAST> ParseIfExpr() { 363ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines getNextToken(); // eat the if. 364ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3659f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // condition. 366cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar auto Cond = ParseExpression(); 367ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!Cond) 368cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 369ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3709f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (CurTok != tok_then) 3719f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return Error("expected then"); 372ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines getNextToken(); // eat the then 373ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 374cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar auto Then = ParseExpression(); 375cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!Then) 376cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 377ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3789f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (CurTok != tok_else) 3799f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return Error("expected else"); 380ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3819f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky getNextToken(); 382ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 383cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar auto Else = ParseExpression(); 384ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!Else) 385cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 386ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 387cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return llvm::make_unique<IfExprAST>(std::move(Cond), std::move(Then), 388cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::move(Else)); 3899f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 3909f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 3919f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression 392cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::unique_ptr<ExprAST> ParseForExpr() { 393ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines getNextToken(); // eat the for. 3949f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 3959f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (CurTok != tok_identifier) 3969f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return Error("expected identifier after for"); 397ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3989f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky std::string IdName = IdentifierStr; 399ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines getNextToken(); // eat identifier. 400ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 4019f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (CurTok != '=') 4029f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return Error("expected '=' after for"); 403ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines getNextToken(); // eat '='. 404ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 405cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar auto Start = ParseExpression(); 406cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!Start) 407cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 4089f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (CurTok != ',') 4099f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return Error("expected ',' after for start value"); 4109f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky getNextToken(); 411ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 412cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar auto End = ParseExpression(); 413cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!End) 414cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 415ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 4169f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // The step value is optional. 417cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::unique_ptr<ExprAST> Step; 4189f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (CurTok == ',') { 4199f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky getNextToken(); 4209f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Step = ParseExpression(); 421cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!Step) 422cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 4239f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 424ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 4259f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (CurTok != tok_in) 4269f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return Error("expected 'in' after for"); 427ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines getNextToken(); // eat 'in'. 428ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 429cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar auto Body = ParseExpression(); 430cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!Body) 431cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 4329f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 433cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return llvm::make_unique<ForExprAST>(IdName, std::move(Start), std::move(End), 434cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::move(Step), std::move(Body)); 4359f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 4369f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 437ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// varexpr ::= 'var' identifier ('=' expression)? 4389f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky// (',' identifier ('=' expression)?)* 'in' expression 439cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::unique_ptr<ExprAST> ParseVarExpr() { 440ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines getNextToken(); // eat the var. 4419f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 442cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames; 4439f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 4449f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // At least one variable name is required. 4459f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (CurTok != tok_identifier) 4469f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return Error("expected identifier after var"); 447ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 4489f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky while (1) { 4499f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky std::string Name = IdentifierStr; 450ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines getNextToken(); // eat identifier. 4519f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 4529f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Read the optional initializer. 453cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::unique_ptr<ExprAST> Init = nullptr; 4549f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (CurTok == '=') { 4559f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky getNextToken(); // eat the '='. 456ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 4579f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Init = ParseExpression(); 458cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!Init) 459cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 4609f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 461ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 462cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar VarNames.push_back(std::make_pair(Name, std::move(Init))); 463ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 4649f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // End of var list, exit loop. 465ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (CurTok != ',') 466ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines break; 4679f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky getNextToken(); // eat the ','. 468ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 4699f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (CurTok != tok_identifier) 4709f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return Error("expected identifier list after var"); 4719f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 472ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 4739f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // At this point, we have to have 'in'. 4749f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (CurTok != tok_in) 4759f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return Error("expected 'in' keyword after 'var'"); 476ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines getNextToken(); // eat 'in'. 477ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 478cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar auto Body = ParseExpression(); 479cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!Body) 480cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 481ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 482cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return llvm::make_unique<VarExprAST>(std::move(VarNames), std::move(Body)); 4839f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 4849f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 4859f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// primary 4869f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// ::= identifierexpr 4879f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// ::= numberexpr 4889f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// ::= parenexpr 4899f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// ::= ifexpr 4909f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// ::= forexpr 4919f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// ::= varexpr 492cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::unique_ptr<ExprAST> ParsePrimary() { 4939f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky switch (CurTok) { 494ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines default: 495ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return Error("unknown token when expecting an expression"); 496ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case tok_identifier: 497ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return ParseIdentifierExpr(); 498ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case tok_number: 499ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return ParseNumberExpr(); 500ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case '(': 501ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return ParseParenExpr(); 502ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case tok_if: 503ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return ParseIfExpr(); 504ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case tok_for: 505ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return ParseForExpr(); 506ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case tok_var: 507ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return ParseVarExpr(); 5089f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 5099f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 5109f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 5119f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// unary 5129f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// ::= primary 5139f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// ::= '!' unary 514cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::unique_ptr<ExprAST> ParseUnary() { 5159f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // If the current token is not an operator, it must be a primary expr. 5169f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (!isascii(CurTok) || CurTok == '(' || CurTok == ',') 5179f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return ParsePrimary(); 518ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 5199f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // If this is a unary operator, read it. 5209f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky int Opc = CurTok; 5219f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky getNextToken(); 522cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (auto Operand = ParseUnary()) 523cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return llvm::make_unique<UnaryExprAST>(Opc, std::move(Operand)); 524cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 5259f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 5269f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 5279f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// binoprhs 5289f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// ::= ('+' unary)* 529cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec, 530cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::unique_ptr<ExprAST> LHS) { 5319f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // If this is a binop, find its precedence. 5329f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky while (1) { 5339f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky int TokPrec = GetTokPrecedence(); 534ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 5359f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // If this is a binop that binds at least as tightly as the current binop, 5369f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // consume it, otherwise we are done. 5379f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (TokPrec < ExprPrec) 5389f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return LHS; 539ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 5409f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Okay, we know this is a binop. 5419f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky int BinOp = CurTok; 542ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines getNextToken(); // eat binop 543ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 5449f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Parse the unary expression after the binary operator. 545cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar auto RHS = ParseUnary(); 546ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!RHS) 547cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 548ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 5499f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // If BinOp binds less tightly with RHS than the operator after RHS, let 5509f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // the pending operator take RHS as its LHS. 5519f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky int NextPrec = GetTokPrecedence(); 5529f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (TokPrec < NextPrec) { 553cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS)); 554cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!RHS) 555cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 5569f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 557ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 5589f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Merge LHS/RHS. 559cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar LHS = 560cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar llvm::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS)); 5619f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 5629f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 5639f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 5649f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// expression 5659f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// ::= unary binoprhs 5669f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// 567cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::unique_ptr<ExprAST> ParseExpression() { 568cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar auto LHS = ParseUnary(); 569ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!LHS) 570cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 571ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 572cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return ParseBinOpRHS(0, std::move(LHS)); 5739f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 5749f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 5759f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// prototype 5769f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// ::= id '(' id* ')' 5779f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// ::= binary LETTER number? (id, id) 5789f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// ::= unary LETTER (id) 579cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::unique_ptr<PrototypeAST> ParsePrototype() { 5809f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky std::string FnName; 581ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 582fd1ec5e68b593a4f4d5497b150e677ebef36c231Erick Tryzelaar unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary. 5839f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky unsigned BinaryPrecedence = 30; 584ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 5859f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky switch (CurTok) { 5869f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky default: 5879f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return ErrorP("Expected function name in prototype"); 5889f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky case tok_identifier: 5899f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky FnName = IdentifierStr; 5909f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Kind = 0; 5919f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky getNextToken(); 5929f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky break; 5939f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky case tok_unary: 5949f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky getNextToken(); 5959f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (!isascii(CurTok)) 5969f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return ErrorP("Expected unary operator"); 5979f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky FnName = "unary"; 5989f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky FnName += (char)CurTok; 5999f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Kind = 1; 6009f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky getNextToken(); 6019f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky break; 6029f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky case tok_binary: 6039f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky getNextToken(); 6049f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (!isascii(CurTok)) 6059f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return ErrorP("Expected binary operator"); 6069f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky FnName = "binary"; 6079f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky FnName += (char)CurTok; 6089f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Kind = 2; 6099f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky getNextToken(); 610ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 6119f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Read the precedence if present. 6129f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (CurTok == tok_number) { 6139f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (NumVal < 1 || NumVal > 100) 6149f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return ErrorP("Invalid precedecnce: must be 1..100"); 6159f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky BinaryPrecedence = (unsigned)NumVal; 6169f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky getNextToken(); 6179f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 6189f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky break; 6199f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 620ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 6219f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (CurTok != '(') 6229f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return ErrorP("Expected '(' in prototype"); 623ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 6249f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky std::vector<std::string> ArgNames; 6259f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky while (getNextToken() == tok_identifier) 6269f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky ArgNames.push_back(IdentifierStr); 6279f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (CurTok != ')') 6289f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return ErrorP("Expected ')' in prototype"); 629ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 6309f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // success. 631ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines getNextToken(); // eat ')'. 632ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 6339f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Verify right number of names for operator. 6349f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (Kind && ArgNames.size() != Kind) 6359f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return ErrorP("Invalid number of operands for operator"); 636ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 637cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return llvm::make_unique<PrototypeAST>(FnName, ArgNames, Kind != 0, 638cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar BinaryPrecedence); 6399f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 6409f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 6419f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// definition ::= 'def' prototype expression 642cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::unique_ptr<FunctionAST> ParseDefinition() { 643ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines getNextToken(); // eat def. 644cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar auto Proto = ParsePrototype(); 645cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!Proto) 646cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 6479f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 648cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (auto E = ParseExpression()) 649cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E)); 650cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 6519f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 6529f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 6539f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// toplevelexpr ::= expression 654cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::unique_ptr<FunctionAST> ParseTopLevelExpr() { 655cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (auto E = ParseExpression()) { 6569f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Make an anonymous proto. 657cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar auto Proto = llvm::make_unique<PrototypeAST>("__anon_expr", 658cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar std::vector<std::string>()); 659cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E)); 6609f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 661cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 6629f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 6639f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 6649f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// external ::= 'extern' prototype 665cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::unique_ptr<PrototypeAST> ParseExtern() { 666ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines getNextToken(); // eat extern. 6679f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return ParsePrototype(); 6689f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 6699f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 6709f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky//===----------------------------------------------------------------------===// 6719f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky// Code Generation 6729f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky//===----------------------------------------------------------------------===// 6739f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 674cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::unique_ptr<Module> TheModule; 675d1fbd142945f5ef0c273c3d756431f8cb9d25dedOwen Andersonstatic IRBuilder<> Builder(getGlobalContext()); 676ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstatic std::map<std::string, AllocaInst *> NamedValues; 677cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::unique_ptr<legacy::FunctionPassManager> TheFPM; 678cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::unique_ptr<KaleidoscopeJIT> TheJIT; 679cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic std::map<std::string, std::unique_ptr<PrototypeAST>> FunctionProtos; 6809f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 681ebe69fe11e48d322045d5949c83283927a0d790bStephen HinesValue *ErrorV(const char *Str) { 682ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Error(Str); 683cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 684cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar} 685cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 686cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga NainarFunction *getFunction(std::string Name) { 687cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // First, see if the function has already been added to the current module. 688cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (auto *F = TheModule->getFunction(Name)) 689cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return F; 690cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 691cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // If not, check whether we can codegen the declaration from some existing 692cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // prototype. 693cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar auto FI = FunctionProtos.find(Name); 694cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (FI != FunctionProtos.end()) 695cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return FI->second->codegen(); 696cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 697cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // If no existing prototype exists, return null. 698cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 699ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 7009f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 7019f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of 7029f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// the function. This is used for mutable variables etc. 7039f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckystatic AllocaInst *CreateEntryBlockAlloca(Function *TheFunction, 7049f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky const std::string &VarName) { 7059f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky IRBuilder<> TmpB(&TheFunction->getEntryBlock(), 706ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines TheFunction->getEntryBlock().begin()); 707cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return TmpB.CreateAlloca(Type::getDoubleTy(getGlobalContext()), nullptr, 7081d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson VarName.c_str()); 7099f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 7109f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 711cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga NainarValue *NumberExprAST::codegen() { 7126f83c9c6ef0e7f79825a0a8f22941815e4b684c7Owen Anderson return ConstantFP::get(getGlobalContext(), APFloat(Val)); 7139f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 7149f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 715cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga NainarValue *VariableExprAST::codegen() { 7169f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Look this variable up in the function. 7179f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Value *V = NamedValues[Name]; 718cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!V) 719ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return ErrorV("Unknown variable name"); 7209f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 7219f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Load the value. 7229f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return Builder.CreateLoad(V, Name.c_str()); 7239f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 7249f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 725cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga NainarValue *UnaryExprAST::codegen() { 726cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *OperandV = Operand->codegen(); 727cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!OperandV) 728cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 729ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 730cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Function *F = getFunction(std::string("unary") + Opcode); 731cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!F) 7329f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return ErrorV("Unknown unary operator"); 733ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 7349f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return Builder.CreateCall(F, OperandV, "unop"); 7359f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 7369f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 737cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga NainarValue *BinaryExprAST::codegen() { 7389f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Special case '=' because we don't want to emit the LHS as an expression. 7399f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (Op == '=') { 7409f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Assignment requires the LHS to be an identifier. 7416948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // This assume we're building without RTTI because LLVM builds that way by 7426948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // default. If you build LLVM with RTTI this can be changed to a 7436948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // dynamic_cast for automatic error checking. 744cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar VariableExprAST *LHSE = static_cast<VariableExprAST *>(LHS.get()); 7459f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (!LHSE) 7469f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return ErrorV("destination of '=' must be a variable"); 7479f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Codegen the RHS. 748cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *Val = RHS->codegen(); 749cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!Val) 750cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 7519f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 7529f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Look up the name. 7539f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Value *Variable = NamedValues[LHSE->getName()]; 754cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!Variable) 755ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return ErrorV("Unknown variable name"); 7569f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 7579f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Builder.CreateStore(Val, Variable); 7589f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return Val; 7599f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 760ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 761cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *L = LHS->codegen(); 762cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *R = RHS->codegen(); 763cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!L || !R) 764cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 765ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 7669f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky switch (Op) { 767ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case '+': 768ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return Builder.CreateFAdd(L, R, "addtmp"); 769ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case '-': 770ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return Builder.CreateFSub(L, R, "subtmp"); 771ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case '*': 772ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return Builder.CreateFMul(L, R, "multmp"); 7739f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky case '<': 7749f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky L = Builder.CreateFCmpULT(L, R, "cmptmp"); 7759f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Convert bool 0/1 to double 0.0 or 1.0 7761d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()), 7771d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson "booltmp"); 778ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines default: 779ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines break; 7809f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 781ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 7829f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // If it wasn't a builtin binary operator, it must be a user defined one. Emit 7839f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // a call to it. 784cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Function *F = getFunction(std::string("binary") + Op); 7859f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky assert(F && "binary operator not found!"); 786ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 787cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *Ops[] = {L, R}; 7880bd9d3af54b62152355525bea7914bdef4600371Francois Pichet return Builder.CreateCall(F, Ops, "binop"); 7899f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 7909f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 791cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga NainarValue *CallExprAST::codegen() { 7929f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Look up the name in the global module table. 793cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Function *CalleeF = getFunction(Callee); 794cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!CalleeF) 7959f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return ErrorV("Unknown function referenced"); 796ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 7979f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // If argument mismatch error. 7989f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (CalleeF->arg_size() != Args.size()) 7999f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return ErrorV("Incorrect # arguments passed"); 8009f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 801ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::vector<Value *> ArgsV; 8029f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky for (unsigned i = 0, e = Args.size(); i != e; ++i) { 803cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar ArgsV.push_back(Args[i]->codegen()); 804cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!ArgsV.back()) 805cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 8069f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 807ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 8080bd9d3af54b62152355525bea7914bdef4600371Francois Pichet return Builder.CreateCall(CalleeF, ArgsV, "calltmp"); 8099f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 8109f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 811cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga NainarValue *IfExprAST::codegen() { 812cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *CondV = Cond->codegen(); 813cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!CondV) 814cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 815ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 8169f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Convert condition to a bool by comparing equal to 0.0. 817ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines CondV = Builder.CreateFCmpONE( 818ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines CondV, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "ifcond"); 819ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 8209f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Function *TheFunction = Builder.GetInsertBlock()->getParent(); 821ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 8229f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Create blocks for the then and else cases. Insert the 'then' block at the 8239f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // end of the function. 824ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *ThenBB = 825ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock::Create(getGlobalContext(), "then", TheFunction); 8261d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else"); 8271d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont"); 828ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 8299f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Builder.CreateCondBr(CondV, ThenBB, ElseBB); 830ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 8319f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Emit then value. 8329f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Builder.SetInsertPoint(ThenBB); 833ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 834cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *ThenV = Then->codegen(); 835cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!ThenV) 836cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 837ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 8389f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Builder.CreateBr(MergeBB); 8399f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Codegen of 'Then' can change the current block, update ThenBB for the PHI. 8409f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky ThenBB = Builder.GetInsertBlock(); 841ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 8429f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Emit else block. 8439f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky TheFunction->getBasicBlockList().push_back(ElseBB); 8449f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Builder.SetInsertPoint(ElseBB); 845ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 846cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *ElseV = Else->codegen(); 847cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!ElseV) 848cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 849ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 8509f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Builder.CreateBr(MergeBB); 8519f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Codegen of 'Else' can change the current block, update ElseBB for the PHI. 8529f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky ElseBB = Builder.GetInsertBlock(); 853ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 8549f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Emit merge block. 8559f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky TheFunction->getBasicBlockList().push_back(MergeBB); 8569f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Builder.SetInsertPoint(MergeBB); 857ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PHINode *PN = 858ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, "iftmp"); 859ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 8609f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky PN->addIncoming(ThenV, ThenBB); 8619f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky PN->addIncoming(ElseV, ElseBB); 8629f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return PN; 8639f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 8649f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 865cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// Output for-loop as: 866cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// var = alloca double 867cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// ... 868cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// start = startexpr 869cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// store start -> var 870cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// goto loop 871cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// loop: 872cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// ... 873cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// bodyexpr 874cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// ... 875cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// loopend: 876cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// step = stepexpr 877cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// endcond = endexpr 878cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// 879cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// curvar = load var 880cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// nextvar = curvar + step 881cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// store nextvar -> var 882cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// br endcond, loop, endloop 883cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar// outloop: 884cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga NainarValue *ForExprAST::codegen() { 8859f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Function *TheFunction = Builder.GetInsertBlock()->getParent(); 8869f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 8879f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Create an alloca for the variable in the entry block. 8889f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName); 889ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 8909f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Emit the start code first, without 'variable' in scope. 891cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *StartVal = Start->codegen(); 892cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!StartVal) 893cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 894ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 8959f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Store the value into the alloca. 8969f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Builder.CreateStore(StartVal, Alloca); 897ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 8989f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Make the new basic block for the loop header, inserting after current 8999f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // block. 900ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *LoopBB = 901ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock::Create(getGlobalContext(), "loop", TheFunction); 902ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 9039f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Insert an explicit fall through from the current block to the LoopBB. 9049f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Builder.CreateBr(LoopBB); 9059f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 9069f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Start insertion in LoopBB. 9079f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Builder.SetInsertPoint(LoopBB); 908ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 9099f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Within the loop, the variable is defined equal to the PHI node. If it 9109f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // shadows an existing variable, we have to restore it, so save it now. 9119f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky AllocaInst *OldVal = NamedValues[VarName]; 9129f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky NamedValues[VarName] = Alloca; 913ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 9149f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Emit the body of the loop. This, like any other expr, can change the 9159f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // current BB. Note that we ignore the value computed by the body, but don't 9169f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // allow an error. 917cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!Body->codegen()) 918cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 919ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 9209f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Emit the step value. 921cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *StepVal = nullptr; 9229f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (Step) { 923cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar StepVal = Step->codegen(); 924cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!StepVal) 925cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 9269f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } else { 9279f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // If not specified, use 1.0. 9286f83c9c6ef0e7f79825a0a8f22941815e4b684c7Owen Anderson StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0)); 9299f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 930ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 9319f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Compute the end condition. 932cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *EndCond = End->codegen(); 933cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!EndCond) 934cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 935ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 9369f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Reload, increment, and restore the alloca. This handles the case where 9379f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // the body of the loop mutates the variable. 9389f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Value *CurVar = Builder.CreateLoad(Alloca, VarName.c_str()); 939b0e9eada32faf9218352f0893841e6839e1c586cChris Lattner Value *NextVar = Builder.CreateFAdd(CurVar, StepVal, "nextvar"); 9409f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Builder.CreateStore(NextVar, Alloca); 941ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 9429f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Convert condition to a bool by comparing equal to 0.0. 943ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines EndCond = Builder.CreateFCmpONE( 944ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines EndCond, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "loopcond"); 945ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 9469f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Create the "after loop" block and insert it. 947ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *AfterBB = 948ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction); 949ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 9509f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Insert the conditional branch into the end of LoopEndBB. 9519f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Builder.CreateCondBr(EndCond, LoopBB, AfterBB); 952ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 9539f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Any new code will be inserted in AfterBB. 9549f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Builder.SetInsertPoint(AfterBB); 955ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 9569f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Restore the unshadowed variable. 9579f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (OldVal) 9589f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky NamedValues[VarName] = OldVal; 9599f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky else 9609f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky NamedValues.erase(VarName); 9619f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 9629f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // for expr always returns 0.0. 9631d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson return Constant::getNullValue(Type::getDoubleTy(getGlobalContext())); 9649f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 9659f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 966cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga NainarValue *VarExprAST::codegen() { 9679f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky std::vector<AllocaInst *> OldBindings; 968ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 9699f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Function *TheFunction = Builder.GetInsertBlock()->getParent(); 9709f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 9719f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Register all variables and emit their initializer. 9729f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky for (unsigned i = 0, e = VarNames.size(); i != e; ++i) { 9739f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky const std::string &VarName = VarNames[i].first; 974cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar ExprAST *Init = VarNames[i].second.get(); 975ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 9769f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Emit the initializer before adding the variable to scope, this prevents 9779f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // the initializer from referencing the variable itself, and permits stuff 9789f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // like this: 9799f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // var a = 1 in 9809f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // var a = a in ... # refers to outer 'a'. 9819f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Value *InitVal; 9829f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky if (Init) { 983cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar InitVal = Init->codegen(); 984cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!InitVal) 985cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 9869f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } else { // If not specified, use 0.0. 9876f83c9c6ef0e7f79825a0a8f22941815e4b684c7Owen Anderson InitVal = ConstantFP::get(getGlobalContext(), APFloat(0.0)); 9889f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 989ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 9909f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName); 9919f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Builder.CreateStore(InitVal, Alloca); 9929f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 9939f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Remember the old variable binding so that we can restore the binding when 9949f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // we unrecurse. 9959f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky OldBindings.push_back(NamedValues[VarName]); 996ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 9979f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Remember this binding. 9989f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky NamedValues[VarName] = Alloca; 9999f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 1000ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 10019f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Codegen the body, now that all vars are in scope. 1002cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Value *BodyVal = Body->codegen(); 1003cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!BodyVal) 1004cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 1005ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 10069f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Pop all our variables from scope. 10079f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky for (unsigned i = 0, e = VarNames.size(); i != e; ++i) 10089f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky NamedValues[VarNames[i].first] = OldBindings[i]; 10099f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 10109f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Return the body computation. 10119f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return BodyVal; 10129f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 10139f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 1014cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga NainarFunction *PrototypeAST::codegen() { 10159f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Make the function type: double(double,double) etc. 1016ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::vector<Type *> Doubles(Args.size(), 1017ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Type::getDoubleTy(getGlobalContext())); 1018ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines FunctionType *FT = 1019ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines FunctionType::get(Type::getDoubleTy(getGlobalContext()), Doubles, false); 1020ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1021ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Function *F = 1022cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Function::Create(FT, Function::ExternalLinkage, Name, TheModule.get()); 1023ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 10249f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Set names for all arguments. 10259f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky unsigned Idx = 0; 1026cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar for (auto &Arg : F->args()) 1027cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Arg.setName(Args[Idx++]); 1028ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 10299f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return F; 10309f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 10319f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 1032cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga NainarFunction *FunctionAST::codegen() { 1033cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // Transfer ownership of the prototype to the FunctionProtos map, but keep a 1034cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // reference to it for use below. 1035cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar auto &P = *Proto; 1036cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar FunctionProtos[Proto->getName()] = std::move(Proto); 1037cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Function *TheFunction = getFunction(P.getName()); 1038cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (!TheFunction) 1039cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 1040ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 10419f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // If this is an operator, install it. 1042cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (P.isBinaryOp()) 1043cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar BinopPrecedence[P.getOperatorName()] = P.getBinaryPrecedence(); 1044ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 10459f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Create a new basic block to start insertion into. 10461d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction); 10479f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Builder.SetInsertPoint(BB); 1048ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1049cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // Record the function arguments in the NamedValues map. 1050cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar NamedValues.clear(); 1051cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar for (auto &Arg : TheFunction->args()) { 1052cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // Create an alloca for this variable. 1053cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, Arg.getName()); 1054cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 1055cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // Store the initial value into the alloca. 1056cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Builder.CreateStore(&Arg, Alloca); 1057cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 1058cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // Add arguments to variable symbol table. 1059cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar NamedValues[Arg.getName()] = Alloca; 1060cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar } 1061fd1ec5e68b593a4f4d5497b150e677ebef36c231Erick Tryzelaar 1062cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (Value *RetVal = Body->codegen()) { 10639f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Finish off the function. 10649f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky Builder.CreateRet(RetVal); 10659f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 10669f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Validate the generated code, checking for consistency. 10679f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky verifyFunction(*TheFunction); 10689f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 1069cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // Run the optimizer on the function. 10709f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky TheFPM->run(*TheFunction); 1071ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 10729f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return TheFunction; 10739f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 1074ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 10759f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Error reading body, remove function. 10769f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky TheFunction->eraseFromParent(); 10779f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 1078cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (P.isBinaryOp()) 10799f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky BinopPrecedence.erase(Proto->getOperatorName()); 1080cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 10819f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 10829f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 10839f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky//===----------------------------------------------------------------------===// 10849f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky// Top-Level parsing and JIT Driver 10859f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky//===----------------------------------------------------------------------===// 10869f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 1087cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainarstatic void InitializeModuleAndPassManager() { 1088cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // Open a new module. 1089cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar TheModule = llvm::make_unique<Module>("my cool jit", getGlobalContext()); 1090cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar TheModule->setDataLayout(TheJIT->getTargetMachine().createDataLayout()); 1091cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 1092cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // Create a new pass manager attached to it. 1093cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar TheFPM = llvm::make_unique<legacy::FunctionPassManager>(TheModule.get()); 1094cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 1095cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // Do simple "peephole" optimizations and bit-twiddling optzns. 1096cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar TheFPM->add(createInstructionCombiningPass()); 1097cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // Reassociate expressions. 1098cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar TheFPM->add(createReassociatePass()); 1099cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // Eliminate Common SubExpressions. 1100cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar TheFPM->add(createGVNPass()); 1101cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // Simplify the control flow graph (deleting unreachable blocks, etc). 1102cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar TheFPM->add(createCFGSimplificationPass()); 1103cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 1104cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar TheFPM->doInitialization(); 1105cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar} 11069f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 11079f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckystatic void HandleDefinition() { 1108cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (auto FnAST = ParseDefinition()) { 1109cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (auto *FnIR = FnAST->codegen()) { 11109f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky fprintf(stderr, "Read function definition:"); 1111cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar FnIR->dump(); 1112cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar TheJIT->addModule(std::move(TheModule)); 1113cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar InitializeModuleAndPassManager(); 11149f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 11159f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } else { 11169f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Skip token for error recovery. 11179f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky getNextToken(); 11189f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 11199f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 11209f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 11219f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckystatic void HandleExtern() { 1122cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (auto ProtoAST = ParseExtern()) { 1123cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (auto *FnIR = ProtoAST->codegen()) { 11249f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky fprintf(stderr, "Read extern: "); 1125cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar FnIR->dump(); 1126cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar FunctionProtos[ProtoAST->getName()] = std::move(ProtoAST); 11279f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 11289f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } else { 11299f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Skip token for error recovery. 11309f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky getNextToken(); 11319f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 11329f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 11339f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 11349f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckystatic void HandleTopLevelExpression() { 1135fd1ec5e68b593a4f4d5497b150e677ebef36c231Erick Tryzelaar // Evaluate a top-level expression into an anonymous function. 1136cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (auto FnAST = ParseTopLevelExpr()) { 1137cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (FnAST->codegen()) { 1138cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 1139cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // JIT the module containing the anonymous expression, keeping a handle so 1140cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // we can free it later. 1141cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar auto H = TheJIT->addModule(std::move(TheModule)); 1142cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar InitializeModuleAndPassManager(); 1143cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 1144cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // Search the JIT for the __anon_expr symbol. 1145cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar auto ExprSymbol = TheJIT->findSymbol("__anon_expr"); 1146cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar assert(ExprSymbol && "Function not found"); 1147cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 1148cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // Get the symbol's address and cast it to the right type (takes no 1149cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // arguments, returns a double) so we can call it as a native function. 1150cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar double (*FP)() = (double (*)())(intptr_t)ExprSymbol.getAddress(); 11519f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky fprintf(stderr, "Evaluated to %f\n", FP()); 1152cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 1153cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar // Delete the anonymous expression module from the JIT. 1154cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar TheJIT->removeModule(H); 11559f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 11569f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } else { 11579f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Skip token for error recovery. 11589f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky getNextToken(); 11599f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 11609f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 11619f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 11629f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// top ::= definition | external | expression | ';' 11639f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckystatic void MainLoop() { 11649f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky while (1) { 11659f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky fprintf(stderr, "ready> "); 11669f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky switch (CurTok) { 1167ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case tok_eof: 1168ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return; 1169cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar case ';': // ignore top-level semicolons. 1170ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines getNextToken(); 1171cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar break; 1172ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case tok_def: 1173ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines HandleDefinition(); 1174ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines break; 1175ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case tok_extern: 1176ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines HandleExtern(); 1177ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines break; 1178ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines default: 1179ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines HandleTopLevelExpression(); 1180ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines break; 11819f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 11829f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky } 11839f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 11849f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 11859f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky//===----------------------------------------------------------------------===// 11869f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky// "Library" functions that can be "extern'd" from user code. 11879f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky//===----------------------------------------------------------------------===// 11889f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 11899f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// putchard - putchar that takes a double and returns 0. 1190ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesextern "C" double putchard(double X) { 1191cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar fputc((char)X, stderr); 11929f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return 0; 11939f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 11949f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 11959f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky/// printd - printf that takes a double prints it as "%f\n", returning 0. 1196ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesextern "C" double printd(double X) { 1197cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar fprintf(stderr, "%f\n", X); 11989f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return 0; 11999f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 12009f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 12019f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky//===----------------------------------------------------------------------===// 12029f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky// Main driver code. 12039f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky//===----------------------------------------------------------------------===// 12049f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 12059f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewyckyint main() { 1206da06288aeb28393b937e17dcd180658c3737a6e5Chris Lattner InitializeNativeTarget(); 1207ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines InitializeNativeTargetAsmPrinter(); 1208ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines InitializeNativeTargetAsmParser(); 1209fd1ec5e68b593a4f4d5497b150e677ebef36c231Erick Tryzelaar 12109f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Install standard binary operators. 12119f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // 1 is lowest precedence. 12129f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky BinopPrecedence['='] = 2; 12139f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky BinopPrecedence['<'] = 10; 12149f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky BinopPrecedence['+'] = 20; 12159f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky BinopPrecedence['-'] = 20; 1216ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BinopPrecedence['*'] = 40; // highest. 12179f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 12189f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky // Prime the first token. 12199f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky fprintf(stderr, "ready> "); 12209f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky getNextToken(); 12219f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky 1222cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar TheJIT = llvm::make_unique<KaleidoscopeJIT>(); 12239e6f3f2f14d46cfd12e01221a6f3229852001e40Reid Kleckner 1224cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar InitializeModuleAndPassManager(); 122560130f0e90d69dc3022878bfe4508dae81f911ebReid Kleckner 122660130f0e90d69dc3022878bfe4508dae81f911ebReid Kleckner // Run the main "interpreter loop" now. 122760130f0e90d69dc3022878bfe4508dae81f911ebReid Kleckner MainLoop(); 122860130f0e90d69dc3022878bfe4508dae81f911ebReid Kleckner 12299f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky return 0; 12309f85634bd2fccd2f366b7ce9048f6c9f95ebba18Nick Lewycky} 1231