14ca7e09b7c1e41535f2a1bd86915375d023daf27Chandler Carruth#include "llvm/Analysis/Passes.h" 231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar#include "llvm/ExecutionEngine/ExecutionEngine.h" 331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar#include "llvm/ExecutionEngine/JIT.h" 40a08460599eed603e469e3e16d0cf6aa33b8ba93Chandler Carruth#include "llvm/IR/DataLayout.h" 50a08460599eed603e469e3e16d0cf6aa33b8ba93Chandler Carruth#include "llvm/IR/DerivedTypes.h" 60a08460599eed603e469e3e16d0cf6aa33b8ba93Chandler Carruth#include "llvm/IR/IRBuilder.h" 70a08460599eed603e469e3e16d0cf6aa33b8ba93Chandler Carruth#include "llvm/IR/LLVMContext.h" 80a08460599eed603e469e3e16d0cf6aa33b8ba93Chandler Carruth#include "llvm/IR/Module.h" 936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Verifier.h" 1031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar#include "llvm/PassManager.h" 113e74d6fdd248e20a280f1dff3da9a6c689c2c4c3Evan Cheng#include "llvm/Support/TargetSelect.h" 124ca7e09b7c1e41535f2a1bd86915375d023daf27Chandler Carruth#include "llvm/Transforms/Scalar.h" 13e3ba15c794839abe076e3e2bdf6c626396a19d4dWill Dietz#include <cctype> 1431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar#include <cstdio> 1531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar#include <map> 164ca7e09b7c1e41535f2a1bd86915375d023daf27Chandler Carruth#include <string> 1731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar#include <vector> 1831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarusing namespace llvm; 1931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 2031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 2131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar// Lexer 2231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 2331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 2431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar// The lexer returns tokens [0-255] if it is an unknown character, otherwise one 2531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar// of these for known things. 2631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarenum Token { 2731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar tok_eof = -1, 2831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 2931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // commands 3031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar tok_def = -2, tok_extern = -3, 3131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 3231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // primary 3331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar tok_identifier = -4, tok_number = -5, 3431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 3531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // control 3631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar tok_if = -6, tok_then = -7, tok_else = -8, 3731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar tok_for = -9, tok_in = -10, 3831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 3931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // operators 4031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar tok_binary = -11, tok_unary = -12 4131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 4231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 4331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic std::string IdentifierStr; // Filled in if tok_identifier 4431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic double NumVal; // Filled in if tok_number 4531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 4631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// gettok - Return the next token from standard input. 4731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic int gettok() { 4831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar static int LastChar = ' '; 4931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 5031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Skip any whitespace. 5131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar while (isspace(LastChar)) 5231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar LastChar = getchar(); 5331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 5431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]* 5531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar IdentifierStr = LastChar; 5631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar while (isalnum((LastChar = getchar()))) 5731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar IdentifierStr += LastChar; 5831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 5931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (IdentifierStr == "def") return tok_def; 6031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (IdentifierStr == "extern") return tok_extern; 6131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (IdentifierStr == "if") return tok_if; 6231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (IdentifierStr == "then") return tok_then; 6331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (IdentifierStr == "else") return tok_else; 6431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (IdentifierStr == "for") return tok_for; 6531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (IdentifierStr == "in") return tok_in; 6631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (IdentifierStr == "binary") return tok_binary; 6731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (IdentifierStr == "unary") return tok_unary; 6831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return tok_identifier; 6931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 7031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 7131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+ 7231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::string NumStr; 7331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar do { 7431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar NumStr += LastChar; 7531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar LastChar = getchar(); 7631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } while (isdigit(LastChar) || LastChar == '.'); 7731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 7831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar NumVal = strtod(NumStr.c_str(), 0); 7931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return tok_number; 8031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 8131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 8231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (LastChar == '#') { 8331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Comment until end of line. 8431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar do LastChar = getchar(); 8531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar while (LastChar != EOF && LastChar != '\n' && LastChar != '\r'); 8631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 8731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (LastChar != EOF) 8831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return gettok(); 8931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 9031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 9131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Check for end of file. Don't eat the EOF. 9231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (LastChar == EOF) 9331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return tok_eof; 9431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 9531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Otherwise, just return the character as its ascii value. 9631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar int ThisChar = LastChar; 9731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar LastChar = getchar(); 9831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ThisChar; 9931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 10031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 10131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 10231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar// Abstract Syntax Tree (aka Parse Tree) 10331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 1049d7c776d32c8a4d64b37a91c2d627629cf1498efBill Wendlingnamespace { 10531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ExprAST - Base class for all expression nodes. 10631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarclass ExprAST { 10731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarpublic: 1089d7c776d32c8a4d64b37a91c2d627629cf1498efBill Wendling virtual ~ExprAST() {} 10931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar virtual Value *Codegen() = 0; 11031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 11131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 11231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// NumberExprAST - Expression class for numeric literals like "1.0". 11331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarclass NumberExprAST : public ExprAST { 11431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar double Val; 11531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarpublic: 11631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar NumberExprAST(double val) : Val(val) {} 11731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar virtual Value *Codegen(); 11831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 11931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 12031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// VariableExprAST - Expression class for referencing a variable, like "a". 12131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarclass VariableExprAST : public ExprAST { 12231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::string Name; 12331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarpublic: 12431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar VariableExprAST(const std::string &name) : Name(name) {} 12531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar virtual Value *Codegen(); 12631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 12731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 12831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// UnaryExprAST - Expression class for a unary operator. 12931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarclass UnaryExprAST : public ExprAST { 13031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar char Opcode; 13131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *Operand; 13231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarpublic: 13331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar UnaryExprAST(char opcode, ExprAST *operand) 13431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar : Opcode(opcode), Operand(operand) {} 13531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar virtual Value *Codegen(); 13631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 13731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 13831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// BinaryExprAST - Expression class for a binary operator. 13931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarclass BinaryExprAST : public ExprAST { 14031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar char Op; 14131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *LHS, *RHS; 14231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarpublic: 14331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs) 14431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar : Op(op), LHS(lhs), RHS(rhs) {} 14531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar virtual Value *Codegen(); 14631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 14731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 14831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// CallExprAST - Expression class for function calls. 14931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarclass CallExprAST : public ExprAST { 15031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::string Callee; 15131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::vector<ExprAST*> Args; 15231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarpublic: 15331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar CallExprAST(const std::string &callee, std::vector<ExprAST*> &args) 15431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar : Callee(callee), Args(args) {} 15531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar virtual Value *Codegen(); 15631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 15731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 15831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// IfExprAST - Expression class for if/then/else. 15931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarclass IfExprAST : public ExprAST { 16031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *Cond, *Then, *Else; 16131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarpublic: 16231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else) 16331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar : Cond(cond), Then(then), Else(_else) {} 16431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar virtual Value *Codegen(); 16531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 16631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 16731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ForExprAST - Expression class for for/in. 16831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarclass ForExprAST : public ExprAST { 16931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::string VarName; 17031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *Start, *End, *Step, *Body; 17131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarpublic: 17231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end, 17331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *step, ExprAST *body) 17431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar : VarName(varname), Start(start), End(end), Step(step), Body(body) {} 17531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar virtual Value *Codegen(); 17631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 17731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 17831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// PrototypeAST - This class represents the "prototype" for a function, 17931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// which captures its name, and its argument names (thus implicitly the number 18031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// of arguments the function takes), as well as if it is an operator. 18131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarclass PrototypeAST { 18231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::string Name; 18331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::vector<std::string> Args; 18431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar bool isOperator; 18531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar unsigned Precedence; // Precedence if a binary op. 18631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarpublic: 18731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar PrototypeAST(const std::string &name, const std::vector<std::string> &args, 18831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar bool isoperator = false, unsigned prec = 0) 18931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {} 19031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 19131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar bool isUnaryOp() const { return isOperator && Args.size() == 1; } 19231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar bool isBinaryOp() const { return isOperator && Args.size() == 2; } 19331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 19431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar char getOperatorName() const { 19531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar assert(isUnaryOp() || isBinaryOp()); 19631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return Name[Name.size()-1]; 19731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 19831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 19931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar unsigned getBinaryPrecedence() const { return Precedence; } 20031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 20131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Function *Codegen(); 20231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 20331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 20431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// FunctionAST - This class represents a function definition itself. 20531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarclass FunctionAST { 20631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar PrototypeAST *Proto; 20731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *Body; 20831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarpublic: 20931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar FunctionAST(PrototypeAST *proto, ExprAST *body) 21031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar : Proto(proto), Body(body) {} 21131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 21231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Function *Codegen(); 21331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 2149d7c776d32c8a4d64b37a91c2d627629cf1498efBill Wendling} // end anonymous namespace 21531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 21631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 21731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar// Parser 21831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 21931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 22031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current 22131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// token the parser is looking at. getNextToken reads another token from the 22231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// lexer and updates CurTok with its results. 22331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic int CurTok; 22431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic int getNextToken() { 22531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return CurTok = gettok(); 22631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 22731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 22831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// BinopPrecedence - This holds the precedence for each binary operator that is 22931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// defined. 23031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic std::map<char, int> BinopPrecedence; 23131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 23231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// GetTokPrecedence - Get the precedence of the pending binary operator token. 23331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic int GetTokPrecedence() { 23431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (!isascii(CurTok)) 23531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return -1; 23631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 23731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Make sure it's a declared binop. 23831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar int TokPrec = BinopPrecedence[CurTok]; 23931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (TokPrec <= 0) return -1; 24031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return TokPrec; 24131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 24231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 24331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// Error* - These are little helper functions for error handling. 24431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick TryzelaarExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;} 24531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick TryzelaarPrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; } 24631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick TryzelaarFunctionAST *ErrorF(const char *Str) { Error(Str); return 0; } 24731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 24831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic ExprAST *ParseExpression(); 24931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 25031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// identifierexpr 25131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= identifier 25231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= identifier '(' expression* ')' 25331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic ExprAST *ParseIdentifierExpr() { 25431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::string IdName = IdentifierStr; 25531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 25631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat identifier. 25731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 25831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != '(') // Simple variable ref. 25931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return new VariableExprAST(IdName); 26031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 26131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Call. 26231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat ( 26331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::vector<ExprAST*> Args; 26431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != ')') { 26531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar while (1) { 26631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *Arg = ParseExpression(); 26731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (!Arg) return 0; 26831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Args.push_back(Arg); 26931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 27031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok == ')') break; 27131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 27231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != ',') 27331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return Error("Expected ')' or ',' in argument list"); 27431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 27531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 27631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 27731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 27831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Eat the ')'. 27931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 28031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 28131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return new CallExprAST(IdName, Args); 28231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 28331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 28431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// numberexpr ::= number 28531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic ExprAST *ParseNumberExpr() { 28631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *Result = new NumberExprAST(NumVal); 28731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // consume the number 28831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return Result; 28931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 29031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 29131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// parenexpr ::= '(' expression ')' 29231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic ExprAST *ParseParenExpr() { 29331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat (. 29431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *V = ParseExpression(); 29531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (!V) return 0; 29631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 29731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != ')') 29831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return Error("expected ')'"); 29931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat ). 30031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return V; 30131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 30231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 30331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ifexpr ::= 'if' expression 'then' expression 'else' expression 30431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic ExprAST *ParseIfExpr() { 30531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat the if. 30631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 30731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // condition. 30831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *Cond = ParseExpression(); 30931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (!Cond) return 0; 31031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 31131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != tok_then) 31231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return Error("expected then"); 31331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat the then 31431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 31531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *Then = ParseExpression(); 31631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (Then == 0) return 0; 31731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 31831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != tok_else) 31931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return Error("expected else"); 32031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 32131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 32231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 32331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *Else = ParseExpression(); 32431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (!Else) return 0; 32531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 32631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return new IfExprAST(Cond, Then, Else); 32731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 32831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 32931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression 33031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic ExprAST *ParseForExpr() { 33131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat the for. 33231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 33331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != tok_identifier) 33431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return Error("expected identifier after for"); 33531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 33631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::string IdName = IdentifierStr; 33731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat identifier. 33831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 33931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != '=') 34031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return Error("expected '=' after for"); 34131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat '='. 34231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 34331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 34431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *Start = ParseExpression(); 34531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (Start == 0) return 0; 34631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != ',') 34731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return Error("expected ',' after for start value"); 34831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 34931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 35031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *End = ParseExpression(); 35131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (End == 0) return 0; 35231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 35331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // The step value is optional. 35431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *Step = 0; 35531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok == ',') { 35631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 35731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Step = ParseExpression(); 35831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (Step == 0) return 0; 35931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 36031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 36131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != tok_in) 36231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return Error("expected 'in' after for"); 36331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat 'in'. 36431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 36531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *Body = ParseExpression(); 36631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (Body == 0) return 0; 36731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 36831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return new ForExprAST(IdName, Start, End, Step, Body); 36931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 37031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 37131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// primary 37231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= identifierexpr 37331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= numberexpr 37431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= parenexpr 37531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= ifexpr 37631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= forexpr 37731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic ExprAST *ParsePrimary() { 37831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar switch (CurTok) { 37931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar default: return Error("unknown token when expecting an expression"); 38031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case tok_identifier: return ParseIdentifierExpr(); 38131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case tok_number: return ParseNumberExpr(); 38231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case '(': return ParseParenExpr(); 38331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case tok_if: return ParseIfExpr(); 38431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case tok_for: return ParseForExpr(); 38531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 38631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 38731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 38831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// unary 38931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= primary 39031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= '!' unary 39131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic ExprAST *ParseUnary() { 39231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // If the current token is not an operator, it must be a primary expr. 39331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (!isascii(CurTok) || CurTok == '(' || CurTok == ',') 39431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ParsePrimary(); 39531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 39631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // If this is a unary operator, read it. 39731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar int Opc = CurTok; 39831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 39931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (ExprAST *Operand = ParseUnary()) 40031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return new UnaryExprAST(Opc, Operand); 40131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return 0; 40231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 40331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 40431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// binoprhs 40531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= ('+' unary)* 40631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) { 40731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // If this is a binop, find its precedence. 40831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar while (1) { 40931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar int TokPrec = GetTokPrecedence(); 41031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 41131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // If this is a binop that binds at least as tightly as the current binop, 41231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // consume it, otherwise we are done. 41331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (TokPrec < ExprPrec) 41431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return LHS; 41531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 41631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Okay, we know this is a binop. 41731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar int BinOp = CurTok; 41831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat binop 41931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 42031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Parse the unary expression after the binary operator. 42131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *RHS = ParseUnary(); 42231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (!RHS) return 0; 42331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 42431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // If BinOp binds less tightly with RHS than the operator after RHS, let 42531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // the pending operator take RHS as its LHS. 42631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar int NextPrec = GetTokPrecedence(); 42731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (TokPrec < NextPrec) { 42831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar RHS = ParseBinOpRHS(TokPrec+1, RHS); 42931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (RHS == 0) return 0; 43031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 43131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 43231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Merge LHS/RHS. 43331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar LHS = new BinaryExprAST(BinOp, LHS, RHS); 43431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 43531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 43631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 43731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// expression 43831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= unary binoprhs 43931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// 44031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic ExprAST *ParseExpression() { 44131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *LHS = ParseUnary(); 44231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (!LHS) return 0; 44331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 44431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ParseBinOpRHS(0, LHS); 44531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 44631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 44731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// prototype 44831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= id '(' id* ')' 44931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= binary LETTER number? (id, id) 45031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= unary LETTER (id) 45131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic PrototypeAST *ParsePrototype() { 45231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::string FnName; 45331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 45431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary. 45531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar unsigned BinaryPrecedence = 30; 45631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 45731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar switch (CurTok) { 45831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar default: 45931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ErrorP("Expected function name in prototype"); 46031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case tok_identifier: 46131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar FnName = IdentifierStr; 46231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Kind = 0; 46331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 46431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar break; 46531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case tok_unary: 46631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 46731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (!isascii(CurTok)) 46831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ErrorP("Expected unary operator"); 46931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar FnName = "unary"; 47031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar FnName += (char)CurTok; 47131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Kind = 1; 47231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 47331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar break; 47431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case tok_binary: 47531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 47631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (!isascii(CurTok)) 47731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ErrorP("Expected binary operator"); 47831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar FnName = "binary"; 47931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar FnName += (char)CurTok; 48031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Kind = 2; 48131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 48231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 48331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Read the precedence if present. 48431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok == tok_number) { 48531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (NumVal < 1 || NumVal > 100) 48631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ErrorP("Invalid precedecnce: must be 1..100"); 48731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BinaryPrecedence = (unsigned)NumVal; 48831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 48931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 49031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar break; 49131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 49231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 49331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != '(') 49431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ErrorP("Expected '(' in prototype"); 49531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 49631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::vector<std::string> ArgNames; 49731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar while (getNextToken() == tok_identifier) 49831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ArgNames.push_back(IdentifierStr); 49931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != ')') 50031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ErrorP("Expected ')' in prototype"); 50131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 50231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // success. 50331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat ')'. 50431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 50531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Verify right number of names for operator. 50631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (Kind && ArgNames.size() != Kind) 50731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ErrorP("Invalid number of operands for operator"); 50831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 50931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence); 51031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 51131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 51231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// definition ::= 'def' prototype expression 51331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic FunctionAST *ParseDefinition() { 51431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat def. 51531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar PrototypeAST *Proto = ParsePrototype(); 51631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (Proto == 0) return 0; 51731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 51831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (ExprAST *E = ParseExpression()) 51931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return new FunctionAST(Proto, E); 52031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return 0; 52131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 52231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 52331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// toplevelexpr ::= expression 52431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic FunctionAST *ParseTopLevelExpr() { 52531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (ExprAST *E = ParseExpression()) { 52631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Make an anonymous proto. 52731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>()); 52831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return new FunctionAST(Proto, E); 52931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 53031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return 0; 53131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 53231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 53331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// external ::= 'extern' prototype 53431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic PrototypeAST *ParseExtern() { 53531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat extern. 53631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ParsePrototype(); 53731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 53831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 53931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 54031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar// Code Generation 54131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 54231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 54331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic Module *TheModule; 54431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic IRBuilder<> Builder(getGlobalContext()); 54531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic std::map<std::string, Value*> NamedValues; 54631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic FunctionPassManager *TheFPM; 54731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 54831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick TryzelaarValue *ErrorV(const char *Str) { Error(Str); return 0; } 54931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 55031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick TryzelaarValue *NumberExprAST::Codegen() { 55131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ConstantFP::get(getGlobalContext(), APFloat(Val)); 55231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 55331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 55431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick TryzelaarValue *VariableExprAST::Codegen() { 55531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Look this variable up in the function. 55631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Value *V = NamedValues[Name]; 55731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return V ? V : ErrorV("Unknown variable name"); 55831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 55931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 56031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick TryzelaarValue *UnaryExprAST::Codegen() { 56131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Value *OperandV = Operand->Codegen(); 56231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (OperandV == 0) return 0; 56331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 56431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Function *F = TheModule->getFunction(std::string("unary")+Opcode); 56531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (F == 0) 56631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ErrorV("Unknown unary operator"); 56731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 56831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return Builder.CreateCall(F, OperandV, "unop"); 56931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 57031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 57131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick TryzelaarValue *BinaryExprAST::Codegen() { 57231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Value *L = LHS->Codegen(); 57331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Value *R = RHS->Codegen(); 57431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (L == 0 || R == 0) return 0; 57531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 57631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar switch (Op) { 5772632bbf0de4637e02f333952991263d526976fafEric Christopher case '+': return Builder.CreateFAdd(L, R, "addtmp"); 5782632bbf0de4637e02f333952991263d526976fafEric Christopher case '-': return Builder.CreateFSub(L, R, "subtmp"); 5792632bbf0de4637e02f333952991263d526976fafEric Christopher case '*': return Builder.CreateFMul(L, R, "multmp"); 58031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case '<': 58131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar L = Builder.CreateFCmpULT(L, R, "cmptmp"); 58231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Convert bool 0/1 to double 0.0 or 1.0 58331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()), 58431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar "booltmp"); 58531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar default: break; 58631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 58731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 58831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // If it wasn't a builtin binary operator, it must be a user defined one. Emit 58931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // a call to it. 59031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Function *F = TheModule->getFunction(std::string("binary")+Op); 59131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar assert(F && "binary operator not found!"); 59231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 59331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Value *Ops[] = { L, R }; 5940bd9d3af54b62152355525bea7914bdef4600371Francois Pichet return Builder.CreateCall(F, Ops, "binop"); 59531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 59631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 59731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick TryzelaarValue *CallExprAST::Codegen() { 59831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Look up the name in the global module table. 59931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Function *CalleeF = TheModule->getFunction(Callee); 60031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CalleeF == 0) 60131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ErrorV("Unknown function referenced"); 60231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 60331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // If argument mismatch error. 60431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CalleeF->arg_size() != Args.size()) 60531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ErrorV("Incorrect # arguments passed"); 60631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 60731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::vector<Value*> ArgsV; 60831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar for (unsigned i = 0, e = Args.size(); i != e; ++i) { 60931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ArgsV.push_back(Args[i]->Codegen()); 61031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (ArgsV.back() == 0) return 0; 61131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 61231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 6130bd9d3af54b62152355525bea7914bdef4600371Francois Pichet return Builder.CreateCall(CalleeF, ArgsV, "calltmp"); 61431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 61531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 61631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick TryzelaarValue *IfExprAST::Codegen() { 61731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Value *CondV = Cond->Codegen(); 61831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CondV == 0) return 0; 61931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 62031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Convert condition to a bool by comparing equal to 0.0. 62131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar CondV = Builder.CreateFCmpONE(CondV, 62231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ConstantFP::get(getGlobalContext(), APFloat(0.0)), 62331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar "ifcond"); 62431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 62531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Function *TheFunction = Builder.GetInsertBlock()->getParent(); 62631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 62731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Create blocks for the then and else cases. Insert the 'then' block at the 62831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // end of the function. 62931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction); 63031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else"); 63131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont"); 63231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 63331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Builder.CreateCondBr(CondV, ThenBB, ElseBB); 63431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 63531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Emit then value. 63631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Builder.SetInsertPoint(ThenBB); 63731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 63831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Value *ThenV = Then->Codegen(); 63931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (ThenV == 0) return 0; 64031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 64131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Builder.CreateBr(MergeBB); 64231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Codegen of 'Then' can change the current block, update ThenBB for the PHI. 64331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ThenBB = Builder.GetInsertBlock(); 64431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 64531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Emit else block. 64631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar TheFunction->getBasicBlockList().push_back(ElseBB); 64731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Builder.SetInsertPoint(ElseBB); 64831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 64931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Value *ElseV = Else->Codegen(); 65031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (ElseV == 0) return 0; 65131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 65231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Builder.CreateBr(MergeBB); 65331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Codegen of 'Else' can change the current block, update ElseBB for the PHI. 65431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ElseBB = Builder.GetInsertBlock(); 65531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 65631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Emit merge block. 65731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar TheFunction->getBasicBlockList().push_back(MergeBB); 65831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Builder.SetInsertPoint(MergeBB); 6593ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, 66031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar "iftmp"); 66131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 66231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar PN->addIncoming(ThenV, ThenBB); 66331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar PN->addIncoming(ElseV, ElseBB); 66431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return PN; 66531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 66631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 66731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick TryzelaarValue *ForExprAST::Codegen() { 66831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Output this as: 66931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // ... 67031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // start = startexpr 67131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // goto loop 67231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // loop: 67331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // variable = phi [start, loopheader], [nextvariable, loopend] 67431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // ... 67531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // bodyexpr 67631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // ... 67731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // loopend: 67831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // step = stepexpr 67931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // nextvariable = variable + step 68031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // endcond = endexpr 68131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // br endcond, loop, endloop 68231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // outloop: 68331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 68431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Emit the start code first, without 'variable' in scope. 68531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Value *StartVal = Start->Codegen(); 68631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (StartVal == 0) return 0; 68731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 68831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Make the new basic block for the loop header, inserting after current 68931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // block. 69031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Function *TheFunction = Builder.GetInsertBlock()->getParent(); 69131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BasicBlock *PreheaderBB = Builder.GetInsertBlock(); 69231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction); 69331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 69431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Insert an explicit fall through from the current block to the LoopBB. 69531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Builder.CreateBr(LoopBB); 69631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 69731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Start insertion in LoopBB. 69831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Builder.SetInsertPoint(LoopBB); 69931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 70031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Start the PHI node with an entry for Start. 7013ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str()); 70231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Variable->addIncoming(StartVal, PreheaderBB); 70331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 70431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Within the loop, the variable is defined equal to the PHI node. If it 70531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // shadows an existing variable, we have to restore it, so save it now. 70631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Value *OldVal = NamedValues[VarName]; 70731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar NamedValues[VarName] = Variable; 70831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 70931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Emit the body of the loop. This, like any other expr, can change the 71031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // current BB. Note that we ignore the value computed by the body, but don't 71131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // allow an error. 71231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (Body->Codegen() == 0) 71331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return 0; 71431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 71531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Emit the step value. 71631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Value *StepVal; 71731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (Step) { 71831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar StepVal = Step->Codegen(); 71931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (StepVal == 0) return 0; 72031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } else { 72131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // If not specified, use 1.0. 72231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0)); 72331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 72431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 725b0e9eada32faf9218352f0893841e6839e1c586cChris Lattner Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar"); 72631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 72731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Compute the end condition. 72831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Value *EndCond = End->Codegen(); 72931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (EndCond == 0) return EndCond; 73031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 73131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Convert condition to a bool by comparing equal to 0.0. 73231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar EndCond = Builder.CreateFCmpONE(EndCond, 73331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ConstantFP::get(getGlobalContext(), APFloat(0.0)), 73431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar "loopcond"); 73531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 73631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Create the "after loop" block and insert it. 73731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BasicBlock *LoopEndBB = Builder.GetInsertBlock(); 73831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction); 73931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 74031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Insert the conditional branch into the end of LoopEndBB. 74131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Builder.CreateCondBr(EndCond, LoopBB, AfterBB); 74231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 74331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Any new code will be inserted in AfterBB. 74431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Builder.SetInsertPoint(AfterBB); 74531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 74631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Add a new entry to the PHI node for the backedge. 74731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Variable->addIncoming(NextVar, LoopEndBB); 74831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 74931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Restore the unshadowed variable. 75031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (OldVal) 75131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar NamedValues[VarName] = OldVal; 75231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar else 75331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar NamedValues.erase(VarName); 75431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 75531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 75631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // for expr always returns 0.0. 75731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return Constant::getNullValue(Type::getDoubleTy(getGlobalContext())); 75831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 75931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 76031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick TryzelaarFunction *PrototypeAST::Codegen() { 76131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Make the function type: double(double,double) etc. 762d1c2bd8e6e37e08393f7c4980efc5bcb66b6f0d0John Wiegley std::vector<Type*> Doubles(Args.size(), 763d1c2bd8e6e37e08393f7c4980efc5bcb66b6f0d0John Wiegley Type::getDoubleTy(getGlobalContext())); 76431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()), 76531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Doubles, false); 76631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 76731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule); 76831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 76931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // If F conflicted, there was already something named 'Name'. If it has a 77031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // body, don't allow redefinition or reextern. 77131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (F->getName() != Name) { 77231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Delete the one we just made and get the existing one. 77331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar F->eraseFromParent(); 77431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar F = TheModule->getFunction(Name); 77531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 77631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // If F already has a body, reject this. 77731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (!F->empty()) { 77831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ErrorF("redefinition of function"); 77931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return 0; 78031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 78131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 78231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // If F took a different number of args, reject. 78331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (F->arg_size() != Args.size()) { 78431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ErrorF("redefinition of function with different # args"); 78531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return 0; 78631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 78731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 78831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 78931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Set names for all arguments. 79031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar unsigned Idx = 0; 79131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size(); 79231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ++AI, ++Idx) { 79331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar AI->setName(Args[Idx]); 79431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 79531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Add arguments to variable symbol table. 79631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar NamedValues[Args[Idx]] = AI; 79731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 79831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 79931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return F; 80031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 80131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 80231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick TryzelaarFunction *FunctionAST::Codegen() { 80331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar NamedValues.clear(); 80431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 80531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Function *TheFunction = Proto->Codegen(); 80631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (TheFunction == 0) 80731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return 0; 80831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 80931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // If this is an operator, install it. 81031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (Proto->isBinaryOp()) 81131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence(); 81231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 81331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Create a new basic block to start insertion into. 81431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction); 81531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Builder.SetInsertPoint(BB); 81631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 81731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (Value *RetVal = Body->Codegen()) { 81831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Finish off the function. 81931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Builder.CreateRet(RetVal); 82031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 82131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Validate the generated code, checking for consistency. 82231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar verifyFunction(*TheFunction); 82331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 82431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Optimize the function. 82531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar TheFPM->run(*TheFunction); 82631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 82731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return TheFunction; 82831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 82931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 83031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Error reading body, remove function. 83131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar TheFunction->eraseFromParent(); 83231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 83331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (Proto->isBinaryOp()) 83431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BinopPrecedence.erase(Proto->getOperatorName()); 83531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return 0; 83631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 83731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 83831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 83931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar// Top-Level parsing and JIT Driver 84031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 84131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 84231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic ExecutionEngine *TheExecutionEngine; 84331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 84431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic void HandleDefinition() { 84531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (FunctionAST *F = ParseDefinition()) { 84631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (Function *LF = F->Codegen()) { 84731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar fprintf(stderr, "Read function definition:"); 84831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar LF->dump(); 84931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 85031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } else { 85131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Skip token for error recovery. 85231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 85331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 85431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 85531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 85631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic void HandleExtern() { 85731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (PrototypeAST *P = ParseExtern()) { 85831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (Function *F = P->Codegen()) { 85931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar fprintf(stderr, "Read extern: "); 86031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar F->dump(); 86131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 86231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } else { 86331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Skip token for error recovery. 86431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 86531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 86631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 86731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 86831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic void HandleTopLevelExpression() { 86931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Evaluate a top-level expression into an anonymous function. 87031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (FunctionAST *F = ParseTopLevelExpr()) { 87131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (Function *LF = F->Codegen()) { 87231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // JIT the function, returning a function pointer. 87331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar void *FPtr = TheExecutionEngine->getPointerToFunction(LF); 87431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 87531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Cast it to the right type (takes no arguments, returns a double) so we 87631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // can call it as a native function. 87731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar double (*FP)() = (double (*)())(intptr_t)FPtr; 87831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar fprintf(stderr, "Evaluated to %f\n", FP()); 87931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 88031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } else { 88131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Skip token for error recovery. 88231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 88331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 88431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 88531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 88631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// top ::= definition | external | expression | ';' 88731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic void MainLoop() { 88831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar while (1) { 88931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar fprintf(stderr, "ready> "); 89031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar switch (CurTok) { 89131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case tok_eof: return; 89231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case ';': getNextToken(); break; // ignore top-level semicolons. 89331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case tok_def: HandleDefinition(); break; 89431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case tok_extern: HandleExtern(); break; 89531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar default: HandleTopLevelExpression(); break; 89631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 89731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 89831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 89931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 90031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 90131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar// "Library" functions that can be "extern'd" from user code. 90231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 90331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 90431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// putchard - putchar that takes a double and returns 0. 90531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarextern "C" 90631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaardouble putchard(double X) { 90731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar putchar((char)X); 90831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return 0; 90931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 91031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 91131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// printd - printf that takes a double prints it as "%f\n", returning 0. 91231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarextern "C" 91331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaardouble printd(double X) { 91431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar printf("%f\n", X); 91531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return 0; 91631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 91731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 91831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 91931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar// Main driver code. 92031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 92131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 92231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarint main() { 92331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar InitializeNativeTarget(); 92431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar LLVMContext &Context = getGlobalContext(); 92531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 92631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Install standard binary operators. 92731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // 1 is lowest precedence. 92831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BinopPrecedence['<'] = 10; 92931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BinopPrecedence['+'] = 20; 93031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BinopPrecedence['-'] = 20; 93131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BinopPrecedence['*'] = 40; // highest. 93231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 93331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Prime the first token. 93431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar fprintf(stderr, "ready> "); 93531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 93631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 93731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Make the module, which holds all the code. 93831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar TheModule = new Module("my cool jit", Context); 93931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 940f0356fe140af1a30587b9a86bcfb1b2c51b8ce20Jeffrey Yasskin // Create the JIT. This takes ownership of the module. 94142fc5586241ddc5948ffff67eefe8cb2690534a8Jeffrey Yasskin std::string ErrStr; 94242fc5586241ddc5948ffff67eefe8cb2690534a8Jeffrey Yasskin TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create(); 94342fc5586241ddc5948ffff67eefe8cb2690534a8Jeffrey Yasskin if (!TheExecutionEngine) { 94442fc5586241ddc5948ffff67eefe8cb2690534a8Jeffrey Yasskin fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str()); 94542fc5586241ddc5948ffff67eefe8cb2690534a8Jeffrey Yasskin exit(1); 94642fc5586241ddc5948ffff67eefe8cb2690534a8Jeffrey Yasskin } 94731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 948f0356fe140af1a30587b9a86bcfb1b2c51b8ce20Jeffrey Yasskin FunctionPassManager OurFPM(TheModule); 94931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 95031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Set up the optimizer pipeline. Start with registering info about how the 95131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // target lays out data structures. 95236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines TheModule->setDataLayout(TheExecutionEngine->getDataLayout()); 95336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines OurFPM.add(new DataLayoutPass(TheModule)); 954dfa1a79b0c2f09349b6cd451198781a3ced48cb8Dan Gohman // Provide basic AliasAnalysis support for GVN. 955dfa1a79b0c2f09349b6cd451198781a3ced48cb8Dan Gohman OurFPM.add(createBasicAliasAnalysisPass()); 95631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Do simple "peephole" optimizations and bit-twiddling optzns. 95731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar OurFPM.add(createInstructionCombiningPass()); 95831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Reassociate expressions. 95931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar OurFPM.add(createReassociatePass()); 96031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Eliminate Common SubExpressions. 96131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar OurFPM.add(createGVNPass()); 96231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Simplify the control flow graph (deleting unreachable blocks, etc). 96331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar OurFPM.add(createCFGSimplificationPass()); 96431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 96531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar OurFPM.doInitialization(); 96631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 96731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Set the global so the code gen can use this. 96831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar TheFPM = &OurFPM; 96931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 97031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Run the main "interpreter loop" now. 97131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar MainLoop(); 97231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 97331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar TheFPM = 0; 97431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 97531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Print out all of the generated code. 97631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar TheModule->dump(); 97731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 97831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return 0; 97931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 980