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