xref: /openbsd-src/gnu/llvm/llvm/examples/Kaleidoscope/MCJIT/lazy/toy-jit.cpp (revision d415bd752c734aee168c4ee86ff32e8cc249eb16)
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