109467b48Spatrick #define MINIMAL_STDERR_OUTPUT
209467b48Spatrick
309467b48Spatrick #include "llvm/Analysis/Passes.h"
409467b48Spatrick #include "llvm/ExecutionEngine/ExecutionEngine.h"
509467b48Spatrick #include "llvm/IR/DataLayout.h"
609467b48Spatrick #include "llvm/IR/DerivedTypes.h"
709467b48Spatrick #include "llvm/IR/IRBuilder.h"
809467b48Spatrick #include "llvm/IR/LLVMContext.h"
909467b48Spatrick #include "llvm/IR/LegacyPassManager.h"
1009467b48Spatrick #include "llvm/IR/Module.h"
1109467b48Spatrick #include "llvm/IR/Verifier.h"
1209467b48Spatrick #include "llvm/Support/TargetSelect.h"
1309467b48Spatrick #include "llvm/Transforms/Scalar.h"
1409467b48Spatrick #include <cctype>
1509467b48Spatrick #include <cstdio>
1609467b48Spatrick #include <map>
1709467b48Spatrick #include <string>
1809467b48Spatrick #include <vector>
1909467b48Spatrick
2009467b48Spatrick using namespace llvm;
2109467b48Spatrick
2209467b48Spatrick //===----------------------------------------------------------------------===//
2309467b48Spatrick // Lexer
2409467b48Spatrick //===----------------------------------------------------------------------===//
2509467b48Spatrick
2609467b48Spatrick // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
2709467b48Spatrick // of these for known things.
2809467b48Spatrick enum Token {
2909467b48Spatrick tok_eof = -1,
3009467b48Spatrick
3109467b48Spatrick // commands
3209467b48Spatrick tok_def = -2, tok_extern = -3,
3309467b48Spatrick
3409467b48Spatrick // primary
3509467b48Spatrick tok_identifier = -4, tok_number = -5,
3609467b48Spatrick
3709467b48Spatrick // control
3809467b48Spatrick tok_if = -6, tok_then = -7, tok_else = -8,
3909467b48Spatrick tok_for = -9, tok_in = -10,
4009467b48Spatrick
4109467b48Spatrick // operators
4209467b48Spatrick tok_binary = -11, tok_unary = -12,
4309467b48Spatrick
4409467b48Spatrick // var definition
4509467b48Spatrick tok_var = -13
4609467b48Spatrick };
4709467b48Spatrick
4809467b48Spatrick static std::string IdentifierStr; // Filled in if tok_identifier
4909467b48Spatrick static double NumVal; // Filled in if tok_number
5009467b48Spatrick
5109467b48Spatrick /// gettok - Return the next token from standard input.
gettok()5209467b48Spatrick static int gettok() {
5309467b48Spatrick static int LastChar = ' ';
5409467b48Spatrick
5509467b48Spatrick // Skip any whitespace.
5609467b48Spatrick while (isspace(LastChar))
5709467b48Spatrick LastChar = getchar();
5809467b48Spatrick
5909467b48Spatrick if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
6009467b48Spatrick IdentifierStr = LastChar;
6109467b48Spatrick while (isalnum((LastChar = getchar())))
6209467b48Spatrick IdentifierStr += LastChar;
6309467b48Spatrick
6409467b48Spatrick if (IdentifierStr == "def") return tok_def;
6509467b48Spatrick if (IdentifierStr == "extern") return tok_extern;
6609467b48Spatrick if (IdentifierStr == "if") return tok_if;
6709467b48Spatrick if (IdentifierStr == "then") return tok_then;
6809467b48Spatrick if (IdentifierStr == "else") return tok_else;
6909467b48Spatrick if (IdentifierStr == "for") return tok_for;
7009467b48Spatrick if (IdentifierStr == "in") return tok_in;
7109467b48Spatrick if (IdentifierStr == "binary") return tok_binary;
7209467b48Spatrick if (IdentifierStr == "unary") return tok_unary;
7309467b48Spatrick if (IdentifierStr == "var") return tok_var;
7409467b48Spatrick return tok_identifier;
7509467b48Spatrick }
7609467b48Spatrick
7709467b48Spatrick if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
7809467b48Spatrick std::string NumStr;
7909467b48Spatrick do {
8009467b48Spatrick NumStr += LastChar;
8109467b48Spatrick LastChar = getchar();
8209467b48Spatrick } while (isdigit(LastChar) || LastChar == '.');
8309467b48Spatrick
8409467b48Spatrick NumVal = strtod(NumStr.c_str(), 0);
8509467b48Spatrick return tok_number;
8609467b48Spatrick }
8709467b48Spatrick
8809467b48Spatrick if (LastChar == '#') {
8909467b48Spatrick // Comment until end of line.
9009467b48Spatrick do LastChar = getchar();
9109467b48Spatrick while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
9209467b48Spatrick
9309467b48Spatrick if (LastChar != EOF)
9409467b48Spatrick return gettok();
9509467b48Spatrick }
9609467b48Spatrick
9709467b48Spatrick // Check for end of file. Don't eat the EOF.
9809467b48Spatrick if (LastChar == EOF)
9909467b48Spatrick return tok_eof;
10009467b48Spatrick
10109467b48Spatrick // Otherwise, just return the character as its ascii value.
10209467b48Spatrick int ThisChar = LastChar;
10309467b48Spatrick LastChar = getchar();
10409467b48Spatrick return ThisChar;
10509467b48Spatrick }
10609467b48Spatrick
10709467b48Spatrick //===----------------------------------------------------------------------===//
10809467b48Spatrick // Abstract Syntax Tree (aka Parse Tree)
10909467b48Spatrick //===----------------------------------------------------------------------===//
11009467b48Spatrick
11109467b48Spatrick /// ExprAST - Base class for all expression nodes.
11209467b48Spatrick class ExprAST {
11309467b48Spatrick public:
~ExprAST()11409467b48Spatrick virtual ~ExprAST() {}
11509467b48Spatrick virtual Value *Codegen() = 0;
11609467b48Spatrick };
11709467b48Spatrick
11809467b48Spatrick /// NumberExprAST - Expression class for numeric literals like "1.0".
11909467b48Spatrick class NumberExprAST : public ExprAST {
12009467b48Spatrick double Val;
12109467b48Spatrick public:
NumberExprAST(double val)12209467b48Spatrick NumberExprAST(double val) : Val(val) {}
12309467b48Spatrick virtual Value *Codegen();
12409467b48Spatrick };
12509467b48Spatrick
12609467b48Spatrick /// VariableExprAST - Expression class for referencing a variable, like "a".
12709467b48Spatrick class VariableExprAST : public ExprAST {
12809467b48Spatrick std::string Name;
12909467b48Spatrick public:
VariableExprAST(const std::string & name)13009467b48Spatrick VariableExprAST(const std::string &name) : Name(name) {}
getName() const13109467b48Spatrick const std::string &getName() const { return Name; }
13209467b48Spatrick virtual Value *Codegen();
13309467b48Spatrick };
13409467b48Spatrick
13509467b48Spatrick /// UnaryExprAST - Expression class for a unary operator.
13609467b48Spatrick class UnaryExprAST : public ExprAST {
13709467b48Spatrick char Opcode;
13809467b48Spatrick ExprAST *Operand;
13909467b48Spatrick public:
UnaryExprAST(char opcode,ExprAST * operand)14009467b48Spatrick UnaryExprAST(char opcode, ExprAST *operand)
14109467b48Spatrick : Opcode(opcode), Operand(operand) {}
14209467b48Spatrick virtual Value *Codegen();
14309467b48Spatrick };
14409467b48Spatrick
14509467b48Spatrick /// BinaryExprAST - Expression class for a binary operator.
14609467b48Spatrick class BinaryExprAST : public ExprAST {
14709467b48Spatrick char Op;
14809467b48Spatrick ExprAST *LHS, *RHS;
14909467b48Spatrick public:
BinaryExprAST(char op,ExprAST * lhs,ExprAST * rhs)15009467b48Spatrick BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
15109467b48Spatrick : Op(op), LHS(lhs), RHS(rhs) {}
15209467b48Spatrick virtual Value *Codegen();
15309467b48Spatrick };
15409467b48Spatrick
15509467b48Spatrick /// CallExprAST - Expression class for function calls.
15609467b48Spatrick class CallExprAST : public ExprAST {
15709467b48Spatrick std::string Callee;
15809467b48Spatrick std::vector<ExprAST*> Args;
15909467b48Spatrick public:
CallExprAST(const std::string & callee,std::vector<ExprAST * > & args)16009467b48Spatrick CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
16109467b48Spatrick : Callee(callee), Args(args) {}
16209467b48Spatrick virtual Value *Codegen();
16309467b48Spatrick };
16409467b48Spatrick
16509467b48Spatrick /// IfExprAST - Expression class for if/then/else.
16609467b48Spatrick class IfExprAST : public ExprAST {
16709467b48Spatrick ExprAST *Cond, *Then, *Else;
16809467b48Spatrick public:
IfExprAST(ExprAST * cond,ExprAST * then,ExprAST * _else)16909467b48Spatrick IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
17009467b48Spatrick : Cond(cond), Then(then), Else(_else) {}
17109467b48Spatrick virtual Value *Codegen();
17209467b48Spatrick };
17309467b48Spatrick
17409467b48Spatrick /// ForExprAST - Expression class for for/in.
17509467b48Spatrick class ForExprAST : public ExprAST {
17609467b48Spatrick std::string VarName;
17709467b48Spatrick ExprAST *Start, *End, *Step, *Body;
17809467b48Spatrick public:
ForExprAST(const std::string & varname,ExprAST * start,ExprAST * end,ExprAST * step,ExprAST * body)17909467b48Spatrick ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
18009467b48Spatrick ExprAST *step, ExprAST *body)
18109467b48Spatrick : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
18209467b48Spatrick virtual Value *Codegen();
18309467b48Spatrick };
18409467b48Spatrick
18509467b48Spatrick /// VarExprAST - Expression class for var/in
18609467b48Spatrick class VarExprAST : public ExprAST {
18709467b48Spatrick std::vector<std::pair<std::string, ExprAST*> > VarNames;
18809467b48Spatrick ExprAST *Body;
18909467b48Spatrick public:
VarExprAST(const std::vector<std::pair<std::string,ExprAST * >> & varnames,ExprAST * body)19009467b48Spatrick VarExprAST(const std::vector<std::pair<std::string, ExprAST*> > &varnames,
19109467b48Spatrick ExprAST *body)
19209467b48Spatrick : VarNames(varnames), Body(body) {}
19309467b48Spatrick
19409467b48Spatrick virtual Value *Codegen();
19509467b48Spatrick };
19609467b48Spatrick
19709467b48Spatrick /// PrototypeAST - This class represents the "prototype" for a function,
19809467b48Spatrick /// which captures its argument names as well as if it is an operator.
19909467b48Spatrick class PrototypeAST {
20009467b48Spatrick std::string Name;
20109467b48Spatrick std::vector<std::string> Args;
20209467b48Spatrick bool isOperator;
20309467b48Spatrick unsigned Precedence; // Precedence if a binary op.
20409467b48Spatrick public:
PrototypeAST(const std::string & name,const std::vector<std::string> & args,bool isoperator=false,unsigned prec=0)20509467b48Spatrick PrototypeAST(const std::string &name, const std::vector<std::string> &args,
20609467b48Spatrick bool isoperator = false, unsigned prec = 0)
20709467b48Spatrick : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {}
20809467b48Spatrick
isUnaryOp() const20909467b48Spatrick bool isUnaryOp() const { return isOperator && Args.size() == 1; }
isBinaryOp() const21009467b48Spatrick bool isBinaryOp() const { return isOperator && Args.size() == 2; }
21109467b48Spatrick
getOperatorName() const21209467b48Spatrick char getOperatorName() const {
21309467b48Spatrick assert(isUnaryOp() || isBinaryOp());
21409467b48Spatrick return Name[Name.size()-1];
21509467b48Spatrick }
21609467b48Spatrick
getBinaryPrecedence() const21709467b48Spatrick unsigned getBinaryPrecedence() const { return Precedence; }
21809467b48Spatrick
21909467b48Spatrick Function *Codegen();
22009467b48Spatrick
22109467b48Spatrick void CreateArgumentAllocas(Function *F);
22209467b48Spatrick };
22309467b48Spatrick
22409467b48Spatrick /// FunctionAST - This class represents a function definition itself.
22509467b48Spatrick class FunctionAST {
22609467b48Spatrick PrototypeAST *Proto;
22709467b48Spatrick ExprAST *Body;
22809467b48Spatrick public:
FunctionAST(PrototypeAST * proto,ExprAST * body)22909467b48Spatrick FunctionAST(PrototypeAST *proto, ExprAST *body)
23009467b48Spatrick : Proto(proto), Body(body) {}
23109467b48Spatrick
23209467b48Spatrick Function *Codegen();
23309467b48Spatrick };
23409467b48Spatrick
23509467b48Spatrick //===----------------------------------------------------------------------===//
23609467b48Spatrick // Parser
23709467b48Spatrick //===----------------------------------------------------------------------===//
23809467b48Spatrick
23909467b48Spatrick /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
24009467b48Spatrick /// token the parser is looking at. getNextToken reads another token from the
24109467b48Spatrick /// lexer and updates CurTok with its results.
24209467b48Spatrick static int CurTok;
getNextToken()24309467b48Spatrick static int getNextToken() {
24409467b48Spatrick return CurTok = gettok();
24509467b48Spatrick }
24609467b48Spatrick
24709467b48Spatrick /// BinopPrecedence - This holds the precedence for each binary operator that is
24809467b48Spatrick /// defined.
24909467b48Spatrick static std::map<char, int> BinopPrecedence;
25009467b48Spatrick
25109467b48Spatrick /// GetTokPrecedence - Get the precedence of the pending binary operator token.
GetTokPrecedence()25209467b48Spatrick static int GetTokPrecedence() {
25309467b48Spatrick if (!isascii(CurTok))
25409467b48Spatrick return -1;
25509467b48Spatrick
25609467b48Spatrick // Make sure it's a declared binop.
25709467b48Spatrick int TokPrec = BinopPrecedence[CurTok];
25809467b48Spatrick if (TokPrec <= 0) return -1;
25909467b48Spatrick return TokPrec;
26009467b48Spatrick }
26109467b48Spatrick
26209467b48Spatrick /// Error* - These are little helper functions for error handling.
Error(const char * Str)26309467b48Spatrick ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
ErrorP(const char * Str)26409467b48Spatrick PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
ErrorF(const char * Str)26509467b48Spatrick FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
26609467b48Spatrick
26709467b48Spatrick static ExprAST *ParseExpression();
26809467b48Spatrick
26909467b48Spatrick /// identifierexpr
27009467b48Spatrick /// ::= identifier
27109467b48Spatrick /// ::= identifier '(' expression* ')'
ParseIdentifierExpr()27209467b48Spatrick static ExprAST *ParseIdentifierExpr() {
27309467b48Spatrick std::string IdName = IdentifierStr;
27409467b48Spatrick
27509467b48Spatrick getNextToken(); // eat identifier.
27609467b48Spatrick
27709467b48Spatrick if (CurTok != '(') // Simple variable ref.
27809467b48Spatrick return new VariableExprAST(IdName);
27909467b48Spatrick
28009467b48Spatrick // Call.
28109467b48Spatrick getNextToken(); // eat (
28209467b48Spatrick std::vector<ExprAST*> Args;
28309467b48Spatrick if (CurTok != ')') {
28409467b48Spatrick while (1) {
28509467b48Spatrick ExprAST *Arg = ParseExpression();
28609467b48Spatrick if (!Arg) return 0;
28709467b48Spatrick Args.push_back(Arg);
28809467b48Spatrick
28909467b48Spatrick if (CurTok == ')') break;
29009467b48Spatrick
29109467b48Spatrick if (CurTok != ',')
29209467b48Spatrick return Error("Expected ')' or ',' in argument list");
29309467b48Spatrick getNextToken();
29409467b48Spatrick }
29509467b48Spatrick }
29609467b48Spatrick
29709467b48Spatrick // Eat the ')'.
29809467b48Spatrick getNextToken();
29909467b48Spatrick
30009467b48Spatrick return new CallExprAST(IdName, Args);
30109467b48Spatrick }
30209467b48Spatrick
30309467b48Spatrick /// numberexpr ::= number
ParseNumberExpr()30409467b48Spatrick static ExprAST *ParseNumberExpr() {
30509467b48Spatrick ExprAST *Result = new NumberExprAST(NumVal);
30609467b48Spatrick getNextToken(); // consume the number
30709467b48Spatrick return Result;
30809467b48Spatrick }
30909467b48Spatrick
31009467b48Spatrick /// parenexpr ::= '(' expression ')'
ParseParenExpr()31109467b48Spatrick static ExprAST *ParseParenExpr() {
31209467b48Spatrick getNextToken(); // eat (.
31309467b48Spatrick ExprAST *V = ParseExpression();
31409467b48Spatrick if (!V) return 0;
31509467b48Spatrick
31609467b48Spatrick if (CurTok != ')')
31709467b48Spatrick return Error("expected ')'");
31809467b48Spatrick getNextToken(); // eat ).
31909467b48Spatrick return V;
32009467b48Spatrick }
32109467b48Spatrick
32209467b48Spatrick /// ifexpr ::= 'if' expression 'then' expression 'else' expression
ParseIfExpr()32309467b48Spatrick static ExprAST *ParseIfExpr() {
32409467b48Spatrick getNextToken(); // eat the if.
32509467b48Spatrick
32609467b48Spatrick // condition.
32709467b48Spatrick ExprAST *Cond = ParseExpression();
32809467b48Spatrick if (!Cond) return 0;
32909467b48Spatrick
33009467b48Spatrick if (CurTok != tok_then)
33109467b48Spatrick return Error("expected then");
33209467b48Spatrick getNextToken(); // eat the then
33309467b48Spatrick
33409467b48Spatrick ExprAST *Then = ParseExpression();
33509467b48Spatrick if (Then == 0) return 0;
33609467b48Spatrick
33709467b48Spatrick if (CurTok != tok_else)
33809467b48Spatrick return Error("expected else");
33909467b48Spatrick
34009467b48Spatrick getNextToken();
34109467b48Spatrick
34209467b48Spatrick ExprAST *Else = ParseExpression();
34309467b48Spatrick if (!Else) return 0;
34409467b48Spatrick
34509467b48Spatrick return new IfExprAST(Cond, Then, Else);
34609467b48Spatrick }
34709467b48Spatrick
34809467b48Spatrick /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
ParseForExpr()34909467b48Spatrick static ExprAST *ParseForExpr() {
35009467b48Spatrick getNextToken(); // eat the for.
35109467b48Spatrick
35209467b48Spatrick if (CurTok != tok_identifier)
35309467b48Spatrick return Error("expected identifier after for");
35409467b48Spatrick
35509467b48Spatrick std::string IdName = IdentifierStr;
35609467b48Spatrick getNextToken(); // eat identifier.
35709467b48Spatrick
35809467b48Spatrick if (CurTok != '=')
35909467b48Spatrick return Error("expected '=' after for");
36009467b48Spatrick getNextToken(); // eat '='.
36109467b48Spatrick
36209467b48Spatrick
36309467b48Spatrick ExprAST *Start = ParseExpression();
36409467b48Spatrick if (Start == 0) return 0;
36509467b48Spatrick if (CurTok != ',')
36609467b48Spatrick return Error("expected ',' after for start value");
36709467b48Spatrick getNextToken();
36809467b48Spatrick
36909467b48Spatrick ExprAST *End = ParseExpression();
37009467b48Spatrick if (End == 0) return 0;
37109467b48Spatrick
37209467b48Spatrick // The step value is optional.
37309467b48Spatrick ExprAST *Step = 0;
37409467b48Spatrick if (CurTok == ',') {
37509467b48Spatrick getNextToken();
37609467b48Spatrick Step = ParseExpression();
37709467b48Spatrick if (Step == 0) return 0;
37809467b48Spatrick }
37909467b48Spatrick
38009467b48Spatrick if (CurTok != tok_in)
38109467b48Spatrick return Error("expected 'in' after for");
38209467b48Spatrick getNextToken(); // eat 'in'.
38309467b48Spatrick
38409467b48Spatrick ExprAST *Body = ParseExpression();
38509467b48Spatrick if (Body == 0) return 0;
38609467b48Spatrick
38709467b48Spatrick return new ForExprAST(IdName, Start, End, Step, Body);
38809467b48Spatrick }
38909467b48Spatrick
39009467b48Spatrick /// varexpr ::= 'var' identifier ('=' expression)?
39109467b48Spatrick // (',' identifier ('=' expression)?)* 'in' expression
ParseVarExpr()39209467b48Spatrick static ExprAST *ParseVarExpr() {
39309467b48Spatrick getNextToken(); // eat the var.
39409467b48Spatrick
39509467b48Spatrick std::vector<std::pair<std::string, ExprAST*> > VarNames;
39609467b48Spatrick
39709467b48Spatrick // At least one variable name is required.
39809467b48Spatrick if (CurTok != tok_identifier)
39909467b48Spatrick return Error("expected identifier after var");
40009467b48Spatrick
40109467b48Spatrick while (1) {
40209467b48Spatrick std::string Name = IdentifierStr;
40309467b48Spatrick getNextToken(); // eat identifier.
40409467b48Spatrick
40509467b48Spatrick // Read the optional initializer.
40609467b48Spatrick ExprAST *Init = 0;
40709467b48Spatrick if (CurTok == '=') {
40809467b48Spatrick getNextToken(); // eat the '='.
40909467b48Spatrick
41009467b48Spatrick Init = ParseExpression();
41109467b48Spatrick if (Init == 0) return 0;
41209467b48Spatrick }
41309467b48Spatrick
41409467b48Spatrick VarNames.push_back(std::make_pair(Name, Init));
41509467b48Spatrick
41609467b48Spatrick // End of var list, exit loop.
41709467b48Spatrick if (CurTok != ',') break;
41809467b48Spatrick getNextToken(); // eat the ','.
41909467b48Spatrick
42009467b48Spatrick if (CurTok != tok_identifier)
42109467b48Spatrick return Error("expected identifier list after var");
42209467b48Spatrick }
42309467b48Spatrick
42409467b48Spatrick // At this point, we have to have 'in'.
42509467b48Spatrick if (CurTok != tok_in)
42609467b48Spatrick return Error("expected 'in' keyword after 'var'");
42709467b48Spatrick getNextToken(); // eat 'in'.
42809467b48Spatrick
42909467b48Spatrick ExprAST *Body = ParseExpression();
43009467b48Spatrick if (Body == 0) return 0;
43109467b48Spatrick
43209467b48Spatrick return new VarExprAST(VarNames, Body);
43309467b48Spatrick }
43409467b48Spatrick
43509467b48Spatrick /// primary
43609467b48Spatrick /// ::= identifierexpr
43709467b48Spatrick /// ::= numberexpr
43809467b48Spatrick /// ::= parenexpr
43909467b48Spatrick /// ::= ifexpr
44009467b48Spatrick /// ::= forexpr
44109467b48Spatrick /// ::= varexpr
ParsePrimary()44209467b48Spatrick static ExprAST *ParsePrimary() {
44309467b48Spatrick switch (CurTok) {
44409467b48Spatrick default: return Error("unknown token when expecting an expression");
44509467b48Spatrick case tok_identifier: return ParseIdentifierExpr();
44609467b48Spatrick case tok_number: return ParseNumberExpr();
44709467b48Spatrick case '(': return ParseParenExpr();
44809467b48Spatrick case tok_if: return ParseIfExpr();
44909467b48Spatrick case tok_for: return ParseForExpr();
45009467b48Spatrick case tok_var: return ParseVarExpr();
45109467b48Spatrick }
45209467b48Spatrick }
45309467b48Spatrick
45409467b48Spatrick /// unary
45509467b48Spatrick /// ::= primary
45609467b48Spatrick /// ::= '!' unary
ParseUnary()45709467b48Spatrick static ExprAST *ParseUnary() {
45809467b48Spatrick // If the current token is not an operator, it must be a primary expr.
45909467b48Spatrick if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
46009467b48Spatrick return ParsePrimary();
46109467b48Spatrick
46209467b48Spatrick // If this is a unary operator, read it.
46309467b48Spatrick int Opc = CurTok;
46409467b48Spatrick getNextToken();
46509467b48Spatrick if (ExprAST *Operand = ParseUnary())
46609467b48Spatrick return new UnaryExprAST(Opc, Operand);
46709467b48Spatrick return 0;
46809467b48Spatrick }
46909467b48Spatrick
47009467b48Spatrick /// binoprhs
47109467b48Spatrick /// ::= ('+' unary)*
ParseBinOpRHS(int ExprPrec,ExprAST * LHS)47209467b48Spatrick static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
47309467b48Spatrick // If this is a binop, find its precedence.
47409467b48Spatrick while (1) {
47509467b48Spatrick int TokPrec = GetTokPrecedence();
47609467b48Spatrick
47709467b48Spatrick // If this is a binop that binds at least as tightly as the current binop,
47809467b48Spatrick // consume it, otherwise we are done.
47909467b48Spatrick if (TokPrec < ExprPrec)
48009467b48Spatrick return LHS;
48109467b48Spatrick
48209467b48Spatrick // Okay, we know this is a binop.
48309467b48Spatrick int BinOp = CurTok;
48409467b48Spatrick getNextToken(); // eat binop
48509467b48Spatrick
48609467b48Spatrick // Parse the unary expression after the binary operator.
48709467b48Spatrick ExprAST *RHS = ParseUnary();
48809467b48Spatrick if (!RHS) return 0;
48909467b48Spatrick
49009467b48Spatrick // If BinOp binds less tightly with RHS than the operator after RHS, let
49109467b48Spatrick // the pending operator take RHS as its LHS.
49209467b48Spatrick int NextPrec = GetTokPrecedence();
49309467b48Spatrick if (TokPrec < NextPrec) {
49409467b48Spatrick RHS = ParseBinOpRHS(TokPrec+1, RHS);
49509467b48Spatrick if (RHS == 0) return 0;
49609467b48Spatrick }
49709467b48Spatrick
49809467b48Spatrick // Merge LHS/RHS.
49909467b48Spatrick LHS = new BinaryExprAST(BinOp, LHS, RHS);
50009467b48Spatrick }
50109467b48Spatrick }
50209467b48Spatrick
50309467b48Spatrick /// expression
50409467b48Spatrick /// ::= unary binoprhs
50509467b48Spatrick ///
ParseExpression()50609467b48Spatrick static ExprAST *ParseExpression() {
50709467b48Spatrick ExprAST *LHS = ParseUnary();
50809467b48Spatrick if (!LHS) return 0;
50909467b48Spatrick
51009467b48Spatrick return ParseBinOpRHS(0, LHS);
51109467b48Spatrick }
51209467b48Spatrick
51309467b48Spatrick /// prototype
51409467b48Spatrick /// ::= id '(' id* ')'
51509467b48Spatrick /// ::= binary LETTER number? (id, id)
51609467b48Spatrick /// ::= unary LETTER (id)
ParsePrototype()51709467b48Spatrick static PrototypeAST *ParsePrototype() {
51809467b48Spatrick std::string FnName;
51909467b48Spatrick
52009467b48Spatrick unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
52109467b48Spatrick unsigned BinaryPrecedence = 30;
52209467b48Spatrick
52309467b48Spatrick switch (CurTok) {
52409467b48Spatrick default:
52509467b48Spatrick return ErrorP("Expected function name in prototype");
52609467b48Spatrick case tok_identifier:
52709467b48Spatrick FnName = IdentifierStr;
52809467b48Spatrick Kind = 0;
52909467b48Spatrick getNextToken();
53009467b48Spatrick break;
53109467b48Spatrick case tok_unary:
53209467b48Spatrick getNextToken();
53309467b48Spatrick if (!isascii(CurTok))
53409467b48Spatrick return ErrorP("Expected unary operator");
53509467b48Spatrick FnName = "unary";
53609467b48Spatrick FnName += (char)CurTok;
53709467b48Spatrick Kind = 1;
53809467b48Spatrick getNextToken();
53909467b48Spatrick break;
54009467b48Spatrick case tok_binary:
54109467b48Spatrick getNextToken();
54209467b48Spatrick if (!isascii(CurTok))
54309467b48Spatrick return ErrorP("Expected binary operator");
54409467b48Spatrick FnName = "binary";
54509467b48Spatrick FnName += (char)CurTok;
54609467b48Spatrick Kind = 2;
54709467b48Spatrick getNextToken();
54809467b48Spatrick
54909467b48Spatrick // Read the precedence if present.
55009467b48Spatrick if (CurTok == tok_number) {
55109467b48Spatrick if (NumVal < 1 || NumVal > 100)
55209467b48Spatrick return ErrorP("Invalid precedecnce: must be 1..100");
55309467b48Spatrick BinaryPrecedence = (unsigned)NumVal;
55409467b48Spatrick getNextToken();
55509467b48Spatrick }
55609467b48Spatrick break;
55709467b48Spatrick }
55809467b48Spatrick
55909467b48Spatrick if (CurTok != '(')
56009467b48Spatrick return ErrorP("Expected '(' in prototype");
56109467b48Spatrick
56209467b48Spatrick std::vector<std::string> ArgNames;
56309467b48Spatrick while (getNextToken() == tok_identifier)
56409467b48Spatrick ArgNames.push_back(IdentifierStr);
56509467b48Spatrick if (CurTok != ')')
56609467b48Spatrick return ErrorP("Expected ')' in prototype");
56709467b48Spatrick
56809467b48Spatrick // success.
56909467b48Spatrick getNextToken(); // eat ')'.
57009467b48Spatrick
57109467b48Spatrick // Verify right number of names for operator.
57209467b48Spatrick if (Kind && ArgNames.size() != Kind)
57309467b48Spatrick return ErrorP("Invalid number of operands for operator");
57409467b48Spatrick
57509467b48Spatrick return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);
57609467b48Spatrick }
57709467b48Spatrick
57809467b48Spatrick /// definition ::= 'def' prototype expression
ParseDefinition()57909467b48Spatrick static FunctionAST *ParseDefinition() {
58009467b48Spatrick getNextToken(); // eat def.
58109467b48Spatrick PrototypeAST *Proto = ParsePrototype();
58209467b48Spatrick if (Proto == 0) return 0;
58309467b48Spatrick
58409467b48Spatrick if (ExprAST *E = ParseExpression())
58509467b48Spatrick return new FunctionAST(Proto, E);
58609467b48Spatrick return 0;
58709467b48Spatrick }
58809467b48Spatrick
58909467b48Spatrick /// toplevelexpr ::= expression
ParseTopLevelExpr()59009467b48Spatrick static FunctionAST *ParseTopLevelExpr() {
59109467b48Spatrick if (ExprAST *E = ParseExpression()) {
59209467b48Spatrick // Make an anonymous proto.
59309467b48Spatrick PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
59409467b48Spatrick return new FunctionAST(Proto, E);
59509467b48Spatrick }
59609467b48Spatrick return 0;
59709467b48Spatrick }
59809467b48Spatrick
59909467b48Spatrick /// external ::= 'extern' prototype
ParseExtern()60009467b48Spatrick static PrototypeAST *ParseExtern() {
60109467b48Spatrick getNextToken(); // eat extern.
60209467b48Spatrick return ParsePrototype();
60309467b48Spatrick }
60409467b48Spatrick
60509467b48Spatrick //===----------------------------------------------------------------------===//
60609467b48Spatrick // Code Generation
60709467b48Spatrick //===----------------------------------------------------------------------===//
60809467b48Spatrick
60909467b48Spatrick static Module *TheModule;
61009467b48Spatrick static FunctionPassManager *TheFPM;
61109467b48Spatrick static LLVMContext TheContext;
61209467b48Spatrick static IRBuilder<> Builder(TheContext);
61309467b48Spatrick static std::map<std::string, AllocaInst*> NamedValues;
61409467b48Spatrick
ErrorV(const char * Str)61509467b48Spatrick Value *ErrorV(const char *Str) { Error(Str); return 0; }
61609467b48Spatrick
61709467b48Spatrick /// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
61809467b48Spatrick /// the function. This is used for mutable variables etc.
CreateEntryBlockAlloca(Function * TheFunction,const std::string & VarName)61909467b48Spatrick static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,
62009467b48Spatrick const std::string &VarName) {
62109467b48Spatrick IRBuilder<> TmpB(&TheFunction->getEntryBlock(),
62209467b48Spatrick TheFunction->getEntryBlock().begin());
62309467b48Spatrick return TmpB.CreateAlloca(Type::getDoubleTy(TheContext), 0, VarName.c_str());
62409467b48Spatrick }
62509467b48Spatrick
Codegen()62609467b48Spatrick Value *NumberExprAST::Codegen() {
62709467b48Spatrick return ConstantFP::get(TheContext, APFloat(Val));
62809467b48Spatrick }
62909467b48Spatrick
Codegen()63009467b48Spatrick Value *VariableExprAST::Codegen() {
63109467b48Spatrick // Look this variable up in the function.
63209467b48Spatrick Value *V = NamedValues[Name];
63309467b48Spatrick if (V == 0) return ErrorV("Unknown variable name");
63409467b48Spatrick
63509467b48Spatrick // Load the value.
63609467b48Spatrick return Builder.CreateLoad(V, Name.c_str());
63709467b48Spatrick }
63809467b48Spatrick
Codegen()63909467b48Spatrick Value *UnaryExprAST::Codegen() {
64009467b48Spatrick Value *OperandV = Operand->Codegen();
64109467b48Spatrick if (OperandV == 0) return 0;
64209467b48Spatrick #ifdef USE_MCJIT
64309467b48Spatrick Function *F = TheHelper->getFunction(MakeLegalFunctionName(std::string("unary")+Opcode));
64409467b48Spatrick #else
64509467b48Spatrick Function *F = TheModule->getFunction(std::string("unary")+Opcode);
64609467b48Spatrick #endif
64709467b48Spatrick if (F == 0)
64809467b48Spatrick return ErrorV("Unknown unary operator");
64909467b48Spatrick
65009467b48Spatrick return Builder.CreateCall(F, OperandV, "unop");
65109467b48Spatrick }
65209467b48Spatrick
Codegen()65309467b48Spatrick Value *BinaryExprAST::Codegen() {
65409467b48Spatrick // Special case '=' because we don't want to emit the LHS as an expression.
65509467b48Spatrick if (Op == '=') {
65609467b48Spatrick // Assignment requires the LHS to be an identifier.
65709467b48Spatrick VariableExprAST *LHSE = dynamic_cast<VariableExprAST*>(LHS);
65809467b48Spatrick if (!LHSE)
65909467b48Spatrick return ErrorV("destination of '=' must be a variable");
66009467b48Spatrick // Codegen the RHS.
66109467b48Spatrick Value *Val = RHS->Codegen();
66209467b48Spatrick if (Val == 0) return 0;
66309467b48Spatrick
66409467b48Spatrick // Look up the name.
66509467b48Spatrick Value *Variable = NamedValues[LHSE->getName()];
66609467b48Spatrick if (Variable == 0) return ErrorV("Unknown variable name");
66709467b48Spatrick
66809467b48Spatrick Builder.CreateStore(Val, Variable);
66909467b48Spatrick return Val;
67009467b48Spatrick }
67109467b48Spatrick
67209467b48Spatrick Value *L = LHS->Codegen();
67309467b48Spatrick Value *R = RHS->Codegen();
67409467b48Spatrick if (L == 0 || R == 0) return 0;
67509467b48Spatrick
67609467b48Spatrick switch (Op) {
67709467b48Spatrick case '+': return Builder.CreateFAdd(L, R, "addtmp");
67809467b48Spatrick case '-': return Builder.CreateFSub(L, R, "subtmp");
67909467b48Spatrick case '*': return Builder.CreateFMul(L, R, "multmp");
68009467b48Spatrick case '/': return Builder.CreateFDiv(L, R, "divtmp");
68109467b48Spatrick case '<':
68209467b48Spatrick L = Builder.CreateFCmpULT(L, R, "cmptmp");
68309467b48Spatrick // Convert bool 0/1 to double 0.0 or 1.0
68409467b48Spatrick return Builder.CreateUIToFP(L, Type::getDoubleTy(TheContext), "booltmp");
68509467b48Spatrick default: break;
68609467b48Spatrick }
68709467b48Spatrick
68809467b48Spatrick // If it wasn't a builtin binary operator, it must be a user defined one. Emit
68909467b48Spatrick // a call to it.
69009467b48Spatrick Function *F = TheModule->getFunction(std::string("binary")+Op);
69109467b48Spatrick assert(F && "binary operator not found!");
69209467b48Spatrick
69309467b48Spatrick Value *Ops[] = { L, R };
69409467b48Spatrick return Builder.CreateCall(F, Ops, "binop");
69509467b48Spatrick }
69609467b48Spatrick
Codegen()69709467b48Spatrick Value *CallExprAST::Codegen() {
69809467b48Spatrick // Look up the name in the global module table.
69909467b48Spatrick Function *CalleeF = TheModule->getFunction(Callee);
70009467b48Spatrick if (CalleeF == 0) {
70109467b48Spatrick char error_str[64];
70209467b48Spatrick sprintf(error_str, "Unknown function referenced %s", Callee.c_str());
70309467b48Spatrick return ErrorV(error_str);
70409467b48Spatrick }
70509467b48Spatrick
70609467b48Spatrick // If argument mismatch error.
70709467b48Spatrick if (CalleeF->arg_size() != Args.size())
70809467b48Spatrick return ErrorV("Incorrect # arguments passed");
70909467b48Spatrick
71009467b48Spatrick std::vector<Value*> ArgsV;
71109467b48Spatrick for (unsigned i = 0, e = Args.size(); i != e; ++i) {
71209467b48Spatrick ArgsV.push_back(Args[i]->Codegen());
71309467b48Spatrick if (ArgsV.back() == 0) return 0;
71409467b48Spatrick }
71509467b48Spatrick
71609467b48Spatrick return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
71709467b48Spatrick }
71809467b48Spatrick
Codegen()71909467b48Spatrick Value *IfExprAST::Codegen() {
72009467b48Spatrick Value *CondV = Cond->Codegen();
72109467b48Spatrick if (CondV == 0) return 0;
72209467b48Spatrick
72309467b48Spatrick // Convert condition to a bool by comparing equal to 0.0.
72409467b48Spatrick CondV = Builder.CreateFCmpONE(
72509467b48Spatrick CondV, ConstantFP::get(TheContext, APFloat(0.0)), "ifcond");
72609467b48Spatrick
72709467b48Spatrick Function *TheFunction = Builder.GetInsertBlock()->getParent();
72809467b48Spatrick
72909467b48Spatrick // Create blocks for the then and else cases. Insert the 'then' block at the
73009467b48Spatrick // end of the function.
73109467b48Spatrick BasicBlock *ThenBB = BasicBlock::Create(TheContext, "then", TheFunction);
73209467b48Spatrick BasicBlock *ElseBB = BasicBlock::Create(TheContext, "else");
73309467b48Spatrick BasicBlock *MergeBB = BasicBlock::Create(TheContext, "ifcont");
73409467b48Spatrick
73509467b48Spatrick Builder.CreateCondBr(CondV, ThenBB, ElseBB);
73609467b48Spatrick
73709467b48Spatrick // Emit then value.
73809467b48Spatrick Builder.SetInsertPoint(ThenBB);
73909467b48Spatrick
74009467b48Spatrick Value *ThenV = Then->Codegen();
74109467b48Spatrick if (ThenV == 0) return 0;
74209467b48Spatrick
74309467b48Spatrick Builder.CreateBr(MergeBB);
74409467b48Spatrick // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
74509467b48Spatrick ThenBB = Builder.GetInsertBlock();
74609467b48Spatrick
74709467b48Spatrick // Emit else block.
748*d415bd75Srobert TheFunction->insert(TheFunction->end(), ElseBB);
74909467b48Spatrick Builder.SetInsertPoint(ElseBB);
75009467b48Spatrick
75109467b48Spatrick Value *ElseV = Else->Codegen();
75209467b48Spatrick if (ElseV == 0) return 0;
75309467b48Spatrick
75409467b48Spatrick Builder.CreateBr(MergeBB);
75509467b48Spatrick // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
75609467b48Spatrick ElseBB = Builder.GetInsertBlock();
75709467b48Spatrick
75809467b48Spatrick // Emit merge block.
759*d415bd75Srobert TheFunction->insert(TheFunction->end(), MergeBB);
76009467b48Spatrick Builder.SetInsertPoint(MergeBB);
76109467b48Spatrick PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(TheContext), 2, "iftmp");
76209467b48Spatrick
76309467b48Spatrick PN->addIncoming(ThenV, ThenBB);
76409467b48Spatrick PN->addIncoming(ElseV, ElseBB);
76509467b48Spatrick return PN;
76609467b48Spatrick }
76709467b48Spatrick
Codegen()76809467b48Spatrick Value *ForExprAST::Codegen() {
76909467b48Spatrick // Output this as:
77009467b48Spatrick // var = alloca double
77109467b48Spatrick // ...
77209467b48Spatrick // start = startexpr
77309467b48Spatrick // store start -> var
77409467b48Spatrick // goto loop
77509467b48Spatrick // loop:
77609467b48Spatrick // ...
77709467b48Spatrick // bodyexpr
77809467b48Spatrick // ...
77909467b48Spatrick // loopend:
78009467b48Spatrick // step = stepexpr
78109467b48Spatrick // endcond = endexpr
78209467b48Spatrick //
78309467b48Spatrick // curvar = load var
78409467b48Spatrick // nextvar = curvar + step
78509467b48Spatrick // store nextvar -> var
78609467b48Spatrick // br endcond, loop, endloop
78709467b48Spatrick // outloop:
78809467b48Spatrick
78909467b48Spatrick Function *TheFunction = Builder.GetInsertBlock()->getParent();
79009467b48Spatrick
79109467b48Spatrick // Create an alloca for the variable in the entry block.
79209467b48Spatrick AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
79309467b48Spatrick
79409467b48Spatrick // Emit the start code first, without 'variable' in scope.
79509467b48Spatrick Value *StartVal = Start->Codegen();
79609467b48Spatrick if (StartVal == 0) return 0;
79709467b48Spatrick
79809467b48Spatrick // Store the value into the alloca.
79909467b48Spatrick Builder.CreateStore(StartVal, Alloca);
80009467b48Spatrick
80109467b48Spatrick // Make the new basic block for the loop header, inserting after current
80209467b48Spatrick // block.
80309467b48Spatrick BasicBlock *LoopBB = BasicBlock::Create(TheContext, "loop", TheFunction);
80409467b48Spatrick
80509467b48Spatrick // Insert an explicit fall through from the current block to the LoopBB.
80609467b48Spatrick Builder.CreateBr(LoopBB);
80709467b48Spatrick
80809467b48Spatrick // Start insertion in LoopBB.
80909467b48Spatrick Builder.SetInsertPoint(LoopBB);
81009467b48Spatrick
81109467b48Spatrick // Within the loop, the variable is defined equal to the PHI node. If it
81209467b48Spatrick // shadows an existing variable, we have to restore it, so save it now.
81309467b48Spatrick AllocaInst *OldVal = NamedValues[VarName];
81409467b48Spatrick NamedValues[VarName] = Alloca;
81509467b48Spatrick
81609467b48Spatrick // Emit the body of the loop. This, like any other expr, can change the
81709467b48Spatrick // current BB. Note that we ignore the value computed by the body, but don't
81809467b48Spatrick // allow an error.
81909467b48Spatrick if (Body->Codegen() == 0)
82009467b48Spatrick return 0;
82109467b48Spatrick
82209467b48Spatrick // Emit the step value.
82309467b48Spatrick Value *StepVal;
82409467b48Spatrick if (Step) {
82509467b48Spatrick StepVal = Step->Codegen();
82609467b48Spatrick if (StepVal == 0) return 0;
82709467b48Spatrick } else {
82809467b48Spatrick // If not specified, use 1.0.
82909467b48Spatrick StepVal = ConstantFP::get(TheContext, APFloat(1.0));
83009467b48Spatrick }
83109467b48Spatrick
83209467b48Spatrick // Compute the end condition.
83309467b48Spatrick Value *EndCond = End->Codegen();
83409467b48Spatrick if (EndCond == 0) return EndCond;
83509467b48Spatrick
83609467b48Spatrick // Reload, increment, and restore the alloca. This handles the case where
83709467b48Spatrick // the body of the loop mutates the variable.
83809467b48Spatrick Value *CurVar = Builder.CreateLoad(Alloca, VarName.c_str());
83909467b48Spatrick Value *NextVar = Builder.CreateFAdd(CurVar, StepVal, "nextvar");
84009467b48Spatrick Builder.CreateStore(NextVar, Alloca);
84109467b48Spatrick
84209467b48Spatrick // Convert condition to a bool by comparing equal to 0.0.
84309467b48Spatrick EndCond = Builder.CreateFCmpONE(
84409467b48Spatrick EndCond, ConstantFP::get(TheContext, APFloat(0.0)), "loopcond");
84509467b48Spatrick
84609467b48Spatrick // Create the "after loop" block and insert it.
84709467b48Spatrick BasicBlock *AfterBB =
84809467b48Spatrick BasicBlock::Create(TheContext, "afterloop", TheFunction);
84909467b48Spatrick
85009467b48Spatrick // Insert the conditional branch into the end of LoopEndBB.
85109467b48Spatrick Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
85209467b48Spatrick
85309467b48Spatrick // Any new code will be inserted in AfterBB.
85409467b48Spatrick Builder.SetInsertPoint(AfterBB);
85509467b48Spatrick
85609467b48Spatrick // Restore the unshadowed variable.
85709467b48Spatrick if (OldVal)
85809467b48Spatrick NamedValues[VarName] = OldVal;
85909467b48Spatrick else
86009467b48Spatrick NamedValues.erase(VarName);
86109467b48Spatrick
86209467b48Spatrick
86309467b48Spatrick // for expr always returns 0.0.
86409467b48Spatrick return Constant::getNullValue(Type::getDoubleTy(TheContext));
86509467b48Spatrick }
86609467b48Spatrick
Codegen()86709467b48Spatrick Value *VarExprAST::Codegen() {
86809467b48Spatrick std::vector<AllocaInst *> OldBindings;
86909467b48Spatrick
87009467b48Spatrick Function *TheFunction = Builder.GetInsertBlock()->getParent();
87109467b48Spatrick
87209467b48Spatrick // Register all variables and emit their initializer.
87309467b48Spatrick for (unsigned i = 0, e = VarNames.size(); i != e; ++i) {
87409467b48Spatrick const std::string &VarName = VarNames[i].first;
87509467b48Spatrick ExprAST *Init = VarNames[i].second;
87609467b48Spatrick
87709467b48Spatrick // Emit the initializer before adding the variable to scope, this prevents
87809467b48Spatrick // the initializer from referencing the variable itself, and permits stuff
87909467b48Spatrick // like this:
88009467b48Spatrick // var a = 1 in
88109467b48Spatrick // var a = a in ... # refers to outer 'a'.
88209467b48Spatrick Value *InitVal;
88309467b48Spatrick if (Init) {
88409467b48Spatrick InitVal = Init->Codegen();
88509467b48Spatrick if (InitVal == 0) return 0;
88609467b48Spatrick } else { // If not specified, use 0.0.
88709467b48Spatrick InitVal = ConstantFP::get(TheContext, APFloat(0.0));
88809467b48Spatrick }
88909467b48Spatrick
89009467b48Spatrick AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
89109467b48Spatrick Builder.CreateStore(InitVal, Alloca);
89209467b48Spatrick
89309467b48Spatrick // Remember the old variable binding so that we can restore the binding when
89409467b48Spatrick // we unrecurse.
89509467b48Spatrick OldBindings.push_back(NamedValues[VarName]);
89609467b48Spatrick
89709467b48Spatrick // Remember this binding.
89809467b48Spatrick NamedValues[VarName] = Alloca;
89909467b48Spatrick }
90009467b48Spatrick
90109467b48Spatrick // Codegen the body, now that all vars are in scope.
90209467b48Spatrick Value *BodyVal = Body->Codegen();
90309467b48Spatrick if (BodyVal == 0) return 0;
90409467b48Spatrick
90509467b48Spatrick // Pop all our variables from scope.
90609467b48Spatrick for (unsigned i = 0, e = VarNames.size(); i != e; ++i)
90709467b48Spatrick NamedValues[VarNames[i].first] = OldBindings[i];
90809467b48Spatrick
90909467b48Spatrick // Return the body computation.
91009467b48Spatrick return BodyVal;
91109467b48Spatrick }
91209467b48Spatrick
Codegen()91309467b48Spatrick Function *PrototypeAST::Codegen() {
91409467b48Spatrick // Make the function type: double(double,double) etc.
91509467b48Spatrick std::vector<Type *> Doubles(Args.size(), Type::getDoubleTy(TheContext));
91609467b48Spatrick FunctionType *FT =
91709467b48Spatrick FunctionType::get(Type::getDoubleTy(TheContext), Doubles, false);
91809467b48Spatrick
91909467b48Spatrick Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
92009467b48Spatrick // If F conflicted, there was already something named 'Name'. If it has a
92109467b48Spatrick // body, don't allow redefinition or reextern.
92209467b48Spatrick if (F->getName() != Name) {
92309467b48Spatrick // Delete the one we just made and get the existing one.
92409467b48Spatrick F->eraseFromParent();
92509467b48Spatrick F = TheModule->getFunction(Name);
92609467b48Spatrick // If F already has a body, reject this.
92709467b48Spatrick if (!F->empty()) {
92809467b48Spatrick ErrorF("redefinition of function");
92909467b48Spatrick return 0;
93009467b48Spatrick }
93109467b48Spatrick // If F took a different number of args, reject.
93209467b48Spatrick if (F->arg_size() != Args.size()) {
93309467b48Spatrick ErrorF("redefinition of function with different # args");
93409467b48Spatrick return 0;
93509467b48Spatrick }
93609467b48Spatrick }
93709467b48Spatrick
93809467b48Spatrick // Set names for all arguments.
93909467b48Spatrick unsigned Idx = 0;
94009467b48Spatrick for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
94109467b48Spatrick ++AI, ++Idx)
94209467b48Spatrick AI->setName(Args[Idx]);
94309467b48Spatrick
94409467b48Spatrick return F;
94509467b48Spatrick }
94609467b48Spatrick
94709467b48Spatrick /// CreateArgumentAllocas - Create an alloca for each argument and register the
94809467b48Spatrick /// argument in the symbol table so that references to it will succeed.
CreateArgumentAllocas(Function * F)94909467b48Spatrick void PrototypeAST::CreateArgumentAllocas(Function *F) {
95009467b48Spatrick Function::arg_iterator AI = F->arg_begin();
95109467b48Spatrick for (unsigned Idx = 0, e = Args.size(); Idx != e; ++Idx, ++AI) {
95209467b48Spatrick // Create an alloca for this variable.
95309467b48Spatrick AllocaInst *Alloca = CreateEntryBlockAlloca(F, Args[Idx]);
95409467b48Spatrick
95509467b48Spatrick // Store the initial value into the alloca.
95609467b48Spatrick Builder.CreateStore(AI, Alloca);
95709467b48Spatrick
95809467b48Spatrick // Add arguments to variable symbol table.
95909467b48Spatrick NamedValues[Args[Idx]] = Alloca;
96009467b48Spatrick }
96109467b48Spatrick }
96209467b48Spatrick
Codegen()96309467b48Spatrick Function *FunctionAST::Codegen() {
96409467b48Spatrick NamedValues.clear();
96509467b48Spatrick
96609467b48Spatrick Function *TheFunction = Proto->Codegen();
96709467b48Spatrick if (TheFunction == 0)
96809467b48Spatrick return 0;
96909467b48Spatrick
97009467b48Spatrick // If this is an operator, install it.
97109467b48Spatrick if (Proto->isBinaryOp())
97209467b48Spatrick BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence();
97309467b48Spatrick
97409467b48Spatrick // Create a new basic block to start insertion into.
97509467b48Spatrick BasicBlock *BB = BasicBlock::Create(TheContext, "entry", TheFunction);
97609467b48Spatrick Builder.SetInsertPoint(BB);
97709467b48Spatrick
97809467b48Spatrick // Add all arguments to the symbol table and create their allocas.
97909467b48Spatrick Proto->CreateArgumentAllocas(TheFunction);
98009467b48Spatrick
98109467b48Spatrick if (Value *RetVal = Body->Codegen()) {
98209467b48Spatrick // Finish off the function.
98309467b48Spatrick Builder.CreateRet(RetVal);
98409467b48Spatrick
98509467b48Spatrick // Validate the generated code, checking for consistency.
98609467b48Spatrick verifyFunction(*TheFunction);
98709467b48Spatrick
98809467b48Spatrick // Optimize the function.
98909467b48Spatrick TheFPM->run(*TheFunction);
99009467b48Spatrick
99109467b48Spatrick return TheFunction;
99209467b48Spatrick }
99309467b48Spatrick
99409467b48Spatrick // Error reading body, remove function.
99509467b48Spatrick TheFunction->eraseFromParent();
99609467b48Spatrick
99709467b48Spatrick if (Proto->isBinaryOp())
99809467b48Spatrick BinopPrecedence.erase(Proto->getOperatorName());
99909467b48Spatrick return 0;
100009467b48Spatrick }
100109467b48Spatrick
100209467b48Spatrick //===----------------------------------------------------------------------===//
100309467b48Spatrick // Top-Level parsing and JIT Driver
100409467b48Spatrick //===----------------------------------------------------------------------===//
100509467b48Spatrick
100609467b48Spatrick static ExecutionEngine *TheExecutionEngine;
100709467b48Spatrick
HandleDefinition()100809467b48Spatrick static void HandleDefinition() {
100909467b48Spatrick if (FunctionAST *F = ParseDefinition()) {
101009467b48Spatrick if (Function *LF = F->Codegen()) {
101109467b48Spatrick #ifndef MINIMAL_STDERR_OUTPUT
101209467b48Spatrick fprintf(stderr, "Read function definition:");
101309467b48Spatrick LF->print(errs());
101409467b48Spatrick fprintf(stderr, "\n");
101509467b48Spatrick #endif
101609467b48Spatrick }
101709467b48Spatrick } else {
101809467b48Spatrick // Skip token for error recovery.
101909467b48Spatrick getNextToken();
102009467b48Spatrick }
102109467b48Spatrick }
102209467b48Spatrick
HandleExtern()102309467b48Spatrick static void HandleExtern() {
102409467b48Spatrick if (PrototypeAST *P = ParseExtern()) {
102509467b48Spatrick if (Function *F = P->Codegen()) {
102609467b48Spatrick #ifndef MINIMAL_STDERR_OUTPUT
102709467b48Spatrick fprintf(stderr, "Read extern: ");
102809467b48Spatrick F->print(errs());
102909467b48Spatrick fprintf(stderr, "\n");
103009467b48Spatrick #endif
103109467b48Spatrick }
103209467b48Spatrick } else {
103309467b48Spatrick // Skip token for error recovery.
103409467b48Spatrick getNextToken();
103509467b48Spatrick }
103609467b48Spatrick }
103709467b48Spatrick
HandleTopLevelExpression()103809467b48Spatrick static void HandleTopLevelExpression() {
103909467b48Spatrick // Evaluate a top-level expression into an anonymous function.
104009467b48Spatrick if (FunctionAST *F = ParseTopLevelExpr()) {
104109467b48Spatrick if (Function *LF = F->Codegen()) {
104209467b48Spatrick // JIT the function, returning a function pointer.
104309467b48Spatrick void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
104409467b48Spatrick // Cast it to the right type (takes no arguments, returns a double) so we
104509467b48Spatrick // can call it as a native function.
104609467b48Spatrick double (*FP)() = (double (*)())(intptr_t)FPtr;
104709467b48Spatrick #ifdef MINIMAL_STDERR_OUTPUT
104809467b48Spatrick FP();
104909467b48Spatrick #else
105009467b48Spatrick fprintf(stderr, "Evaluated to %f\n", FP());
105109467b48Spatrick #endif
105209467b48Spatrick }
105309467b48Spatrick } else {
105409467b48Spatrick // Skip token for error recovery.
105509467b48Spatrick getNextToken();
105609467b48Spatrick }
105709467b48Spatrick }
105809467b48Spatrick
105909467b48Spatrick /// top ::= definition | external | expression | ';'
MainLoop()106009467b48Spatrick static void MainLoop() {
106109467b48Spatrick while (1) {
106209467b48Spatrick #ifndef MINIMAL_STDERR_OUTPUT
106309467b48Spatrick fprintf(stderr, "ready> ");
106409467b48Spatrick #endif
106509467b48Spatrick switch (CurTok) {
106609467b48Spatrick case tok_eof: return;
106709467b48Spatrick case ';': getNextToken(); break; // ignore top-level semicolons.
106809467b48Spatrick case tok_def: HandleDefinition(); break;
106909467b48Spatrick case tok_extern: HandleExtern(); break;
107009467b48Spatrick default: HandleTopLevelExpression(); break;
107109467b48Spatrick }
107209467b48Spatrick }
107309467b48Spatrick }
107409467b48Spatrick
107509467b48Spatrick //===----------------------------------------------------------------------===//
107609467b48Spatrick // "Library" functions that can be "extern'd" from user code.
107709467b48Spatrick //===----------------------------------------------------------------------===//
107809467b48Spatrick
107909467b48Spatrick /// putchard - putchar that takes a double and returns 0.
108009467b48Spatrick extern "C"
putchard(double X)108109467b48Spatrick double putchard(double X) {
108209467b48Spatrick putchar((char)X);
108309467b48Spatrick return 0;
108409467b48Spatrick }
108509467b48Spatrick
108609467b48Spatrick /// printd - printf that takes a double prints it as "%f\n", returning 0.
108709467b48Spatrick extern "C"
printd(double X)108809467b48Spatrick double printd(double X) {
108909467b48Spatrick printf("%f", X);
109009467b48Spatrick return 0;
109109467b48Spatrick }
109209467b48Spatrick
109309467b48Spatrick extern "C"
printlf()109409467b48Spatrick double printlf() {
109509467b48Spatrick printf("\n");
109609467b48Spatrick return 0;
109709467b48Spatrick }
109809467b48Spatrick
109909467b48Spatrick //===----------------------------------------------------------------------===//
110009467b48Spatrick // Main driver code.
110109467b48Spatrick //===----------------------------------------------------------------------===//
110209467b48Spatrick
main(int argc,char ** argv)110309467b48Spatrick int main(int argc, char **argv) {
110409467b48Spatrick InitializeNativeTarget();
110509467b48Spatrick LLVMContext &Context = TheContext;
110609467b48Spatrick
110709467b48Spatrick // Install standard binary operators.
110809467b48Spatrick // 1 is lowest precedence.
110909467b48Spatrick BinopPrecedence['='] = 2;
111009467b48Spatrick BinopPrecedence['<'] = 10;
111109467b48Spatrick BinopPrecedence['+'] = 20;
111209467b48Spatrick BinopPrecedence['-'] = 20;
111309467b48Spatrick BinopPrecedence['/'] = 40;
111409467b48Spatrick BinopPrecedence['*'] = 40; // highest.
111509467b48Spatrick
111609467b48Spatrick // Make the module, which holds all the code.
111709467b48Spatrick TheModule = new Module("my cool jit", Context);
111809467b48Spatrick
111909467b48Spatrick // Create the JIT. This takes ownership of the module.
112009467b48Spatrick std::string ErrStr;
112109467b48Spatrick TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create();
112209467b48Spatrick if (!TheExecutionEngine) {
112309467b48Spatrick fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
112409467b48Spatrick exit(1);
112509467b48Spatrick }
112609467b48Spatrick
112709467b48Spatrick FunctionPassManager OurFPM(TheModule);
112809467b48Spatrick
112909467b48Spatrick // Set up the optimizer pipeline. Start with registering info about how the
113009467b48Spatrick // target lays out data structures.
113109467b48Spatrick OurFPM.add(new DataLayout(*TheExecutionEngine->getDataLayout()));
113209467b48Spatrick // Provide basic AliasAnalysis support for GVN.
113309467b48Spatrick OurFPM.add(createBasicAliasAnalysisPass());
113409467b48Spatrick // Promote allocas to registers.
113509467b48Spatrick OurFPM.add(createPromoteMemoryToRegisterPass());
113609467b48Spatrick // Do simple "peephole" optimizations and bit-twiddling optzns.
113709467b48Spatrick OurFPM.add(createInstructionCombiningPass());
113809467b48Spatrick // Reassociate expressions.
113909467b48Spatrick OurFPM.add(createReassociatePass());
114009467b48Spatrick // Eliminate Common SubExpressions.
114109467b48Spatrick OurFPM.add(createGVNPass());
114209467b48Spatrick // Simplify the control flow graph (deleting unreachable blocks, etc).
114309467b48Spatrick OurFPM.add(createCFGSimplificationPass());
114409467b48Spatrick
114509467b48Spatrick OurFPM.doInitialization();
114609467b48Spatrick
114709467b48Spatrick // Set the global so the code gen can use this.
114809467b48Spatrick TheFPM = &OurFPM;
114909467b48Spatrick
115009467b48Spatrick // Prime the first token.
115109467b48Spatrick #ifndef MINIMAL_STDERR_OUTPUT
115209467b48Spatrick fprintf(stderr, "ready> ");
115309467b48Spatrick #endif
115409467b48Spatrick getNextToken();
115509467b48Spatrick
115609467b48Spatrick // Run the main "interpreter loop" now.
115709467b48Spatrick MainLoop();
115809467b48Spatrick
115909467b48Spatrick // Print out all of the generated code.
116009467b48Spatrick TheFPM = 0;
116109467b48Spatrick #ifndef MINIMAL_STDERR_OUTPUT
116209467b48Spatrick TheModule->print(errs(), nullptr);
116309467b48Spatrick #endif
116409467b48Spatrick return 0;
116509467b48Spatrick }
1166