1f4a2713aSLionel Sambuc #include "llvm/Analysis/Passes.h"
2f4a2713aSLionel Sambuc #include "llvm/ExecutionEngine/ExecutionEngine.h"
3*0a6a1f1dSLionel Sambuc #include "llvm/ExecutionEngine/MCJIT.h"
4*0a6a1f1dSLionel Sambuc #include "llvm/ExecutionEngine/SectionMemoryManager.h"
5f4a2713aSLionel Sambuc #include "llvm/IR/DataLayout.h"
6f4a2713aSLionel Sambuc #include "llvm/IR/DerivedTypes.h"
7f4a2713aSLionel Sambuc #include "llvm/IR/IRBuilder.h"
8f4a2713aSLionel Sambuc #include "llvm/IR/LLVMContext.h"
9f4a2713aSLionel Sambuc #include "llvm/IR/Module.h"
10*0a6a1f1dSLionel Sambuc #include "llvm/IR/Verifier.h"
11f4a2713aSLionel Sambuc #include "llvm/PassManager.h"
12f4a2713aSLionel Sambuc #include "llvm/Support/TargetSelect.h"
13f4a2713aSLionel Sambuc #include "llvm/Transforms/Scalar.h"
14f4a2713aSLionel Sambuc #include <cctype>
15f4a2713aSLionel Sambuc #include <cstdio>
16f4a2713aSLionel Sambuc #include <map>
17f4a2713aSLionel Sambuc #include <string>
18f4a2713aSLionel Sambuc #include <vector>
19f4a2713aSLionel Sambuc using namespace llvm;
20f4a2713aSLionel Sambuc
21f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
22f4a2713aSLionel Sambuc // Lexer
23f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
24f4a2713aSLionel Sambuc
25f4a2713aSLionel Sambuc // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
26f4a2713aSLionel Sambuc // of these for known things.
27f4a2713aSLionel Sambuc enum Token {
28f4a2713aSLionel Sambuc tok_eof = -1,
29f4a2713aSLionel Sambuc
30f4a2713aSLionel Sambuc // commands
31*0a6a1f1dSLionel Sambuc tok_def = -2,
32*0a6a1f1dSLionel Sambuc tok_extern = -3,
33f4a2713aSLionel Sambuc
34f4a2713aSLionel Sambuc // primary
35*0a6a1f1dSLionel Sambuc tok_identifier = -4,
36*0a6a1f1dSLionel Sambuc tok_number = -5,
37f4a2713aSLionel Sambuc
38f4a2713aSLionel Sambuc // control
39*0a6a1f1dSLionel Sambuc tok_if = -6,
40*0a6a1f1dSLionel Sambuc tok_then = -7,
41*0a6a1f1dSLionel Sambuc tok_else = -8,
42*0a6a1f1dSLionel Sambuc tok_for = -9,
43*0a6a1f1dSLionel Sambuc tok_in = -10,
44f4a2713aSLionel Sambuc
45f4a2713aSLionel Sambuc // operators
46*0a6a1f1dSLionel Sambuc tok_binary = -11,
47*0a6a1f1dSLionel Sambuc tok_unary = -12
48f4a2713aSLionel Sambuc };
49f4a2713aSLionel Sambuc
50f4a2713aSLionel Sambuc static std::string IdentifierStr; // Filled in if tok_identifier
51f4a2713aSLionel Sambuc static double NumVal; // Filled in if tok_number
52f4a2713aSLionel Sambuc
53f4a2713aSLionel Sambuc /// gettok - Return the next token from standard input.
gettok()54f4a2713aSLionel Sambuc static int gettok() {
55f4a2713aSLionel Sambuc static int LastChar = ' ';
56f4a2713aSLionel Sambuc
57f4a2713aSLionel Sambuc // Skip any whitespace.
58f4a2713aSLionel Sambuc while (isspace(LastChar))
59f4a2713aSLionel Sambuc LastChar = getchar();
60f4a2713aSLionel Sambuc
61f4a2713aSLionel Sambuc if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
62f4a2713aSLionel Sambuc IdentifierStr = LastChar;
63f4a2713aSLionel Sambuc while (isalnum((LastChar = getchar())))
64f4a2713aSLionel Sambuc IdentifierStr += LastChar;
65f4a2713aSLionel Sambuc
66*0a6a1f1dSLionel Sambuc if (IdentifierStr == "def")
67*0a6a1f1dSLionel Sambuc return tok_def;
68*0a6a1f1dSLionel Sambuc if (IdentifierStr == "extern")
69*0a6a1f1dSLionel Sambuc return tok_extern;
70*0a6a1f1dSLionel Sambuc if (IdentifierStr == "if")
71*0a6a1f1dSLionel Sambuc return tok_if;
72*0a6a1f1dSLionel Sambuc if (IdentifierStr == "then")
73*0a6a1f1dSLionel Sambuc return tok_then;
74*0a6a1f1dSLionel Sambuc if (IdentifierStr == "else")
75*0a6a1f1dSLionel Sambuc return tok_else;
76*0a6a1f1dSLionel Sambuc if (IdentifierStr == "for")
77*0a6a1f1dSLionel Sambuc return tok_for;
78*0a6a1f1dSLionel Sambuc if (IdentifierStr == "in")
79*0a6a1f1dSLionel Sambuc return tok_in;
80*0a6a1f1dSLionel Sambuc if (IdentifierStr == "binary")
81*0a6a1f1dSLionel Sambuc return tok_binary;
82*0a6a1f1dSLionel Sambuc if (IdentifierStr == "unary")
83*0a6a1f1dSLionel Sambuc return tok_unary;
84f4a2713aSLionel Sambuc return tok_identifier;
85f4a2713aSLionel Sambuc }
86f4a2713aSLionel Sambuc
87f4a2713aSLionel Sambuc if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
88f4a2713aSLionel Sambuc std::string NumStr;
89f4a2713aSLionel Sambuc do {
90f4a2713aSLionel Sambuc NumStr += LastChar;
91f4a2713aSLionel Sambuc LastChar = getchar();
92f4a2713aSLionel Sambuc } while (isdigit(LastChar) || LastChar == '.');
93f4a2713aSLionel Sambuc
94f4a2713aSLionel Sambuc NumVal = strtod(NumStr.c_str(), 0);
95f4a2713aSLionel Sambuc return tok_number;
96f4a2713aSLionel Sambuc }
97f4a2713aSLionel Sambuc
98f4a2713aSLionel Sambuc if (LastChar == '#') {
99f4a2713aSLionel Sambuc // Comment until end of line.
100*0a6a1f1dSLionel Sambuc do
101*0a6a1f1dSLionel Sambuc LastChar = getchar();
102f4a2713aSLionel Sambuc while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
103f4a2713aSLionel Sambuc
104f4a2713aSLionel Sambuc if (LastChar != EOF)
105f4a2713aSLionel Sambuc return gettok();
106f4a2713aSLionel Sambuc }
107f4a2713aSLionel Sambuc
108f4a2713aSLionel Sambuc // Check for end of file. Don't eat the EOF.
109f4a2713aSLionel Sambuc if (LastChar == EOF)
110f4a2713aSLionel Sambuc return tok_eof;
111f4a2713aSLionel Sambuc
112f4a2713aSLionel Sambuc // Otherwise, just return the character as its ascii value.
113f4a2713aSLionel Sambuc int ThisChar = LastChar;
114f4a2713aSLionel Sambuc LastChar = getchar();
115f4a2713aSLionel Sambuc return ThisChar;
116f4a2713aSLionel Sambuc }
117f4a2713aSLionel Sambuc
118f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
119f4a2713aSLionel Sambuc // Abstract Syntax Tree (aka Parse Tree)
120f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
121f4a2713aSLionel Sambuc namespace {
122f4a2713aSLionel Sambuc /// ExprAST - Base class for all expression nodes.
123f4a2713aSLionel Sambuc class ExprAST {
124f4a2713aSLionel Sambuc public:
~ExprAST()125f4a2713aSLionel Sambuc virtual ~ExprAST() {}
126f4a2713aSLionel Sambuc virtual Value *Codegen() = 0;
127f4a2713aSLionel Sambuc };
128f4a2713aSLionel Sambuc
129f4a2713aSLionel Sambuc /// NumberExprAST - Expression class for numeric literals like "1.0".
130f4a2713aSLionel Sambuc class NumberExprAST : public ExprAST {
131f4a2713aSLionel Sambuc double Val;
132*0a6a1f1dSLionel Sambuc
133f4a2713aSLionel Sambuc public:
NumberExprAST(double val)134f4a2713aSLionel Sambuc NumberExprAST(double val) : Val(val) {}
135f4a2713aSLionel Sambuc virtual Value *Codegen();
136f4a2713aSLionel Sambuc };
137f4a2713aSLionel Sambuc
138f4a2713aSLionel Sambuc /// VariableExprAST - Expression class for referencing a variable, like "a".
139f4a2713aSLionel Sambuc class VariableExprAST : public ExprAST {
140f4a2713aSLionel Sambuc std::string Name;
141*0a6a1f1dSLionel Sambuc
142f4a2713aSLionel Sambuc public:
VariableExprAST(const std::string & name)143f4a2713aSLionel Sambuc VariableExprAST(const std::string &name) : Name(name) {}
144f4a2713aSLionel Sambuc virtual Value *Codegen();
145f4a2713aSLionel Sambuc };
146f4a2713aSLionel Sambuc
147f4a2713aSLionel Sambuc /// UnaryExprAST - Expression class for a unary operator.
148f4a2713aSLionel Sambuc class UnaryExprAST : public ExprAST {
149f4a2713aSLionel Sambuc char Opcode;
150f4a2713aSLionel Sambuc ExprAST *Operand;
151*0a6a1f1dSLionel Sambuc
152f4a2713aSLionel Sambuc public:
UnaryExprAST(char opcode,ExprAST * operand)153f4a2713aSLionel Sambuc UnaryExprAST(char opcode, ExprAST *operand)
154f4a2713aSLionel Sambuc : Opcode(opcode), Operand(operand) {}
155f4a2713aSLionel Sambuc virtual Value *Codegen();
156f4a2713aSLionel Sambuc };
157f4a2713aSLionel Sambuc
158f4a2713aSLionel Sambuc /// BinaryExprAST - Expression class for a binary operator.
159f4a2713aSLionel Sambuc class BinaryExprAST : public ExprAST {
160f4a2713aSLionel Sambuc char Op;
161f4a2713aSLionel Sambuc ExprAST *LHS, *RHS;
162*0a6a1f1dSLionel Sambuc
163f4a2713aSLionel Sambuc public:
BinaryExprAST(char op,ExprAST * lhs,ExprAST * rhs)164f4a2713aSLionel Sambuc BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
165f4a2713aSLionel Sambuc : Op(op), LHS(lhs), RHS(rhs) {}
166f4a2713aSLionel Sambuc virtual Value *Codegen();
167f4a2713aSLionel Sambuc };
168f4a2713aSLionel Sambuc
169f4a2713aSLionel Sambuc /// CallExprAST - Expression class for function calls.
170f4a2713aSLionel Sambuc class CallExprAST : public ExprAST {
171f4a2713aSLionel Sambuc std::string Callee;
172f4a2713aSLionel Sambuc std::vector<ExprAST *> Args;
173*0a6a1f1dSLionel Sambuc
174f4a2713aSLionel Sambuc public:
CallExprAST(const std::string & callee,std::vector<ExprAST * > & args)175f4a2713aSLionel Sambuc CallExprAST(const std::string &callee, std::vector<ExprAST *> &args)
176f4a2713aSLionel Sambuc : Callee(callee), Args(args) {}
177f4a2713aSLionel Sambuc virtual Value *Codegen();
178f4a2713aSLionel Sambuc };
179f4a2713aSLionel Sambuc
180f4a2713aSLionel Sambuc /// IfExprAST - Expression class for if/then/else.
181f4a2713aSLionel Sambuc class IfExprAST : public ExprAST {
182f4a2713aSLionel Sambuc ExprAST *Cond, *Then, *Else;
183*0a6a1f1dSLionel Sambuc
184f4a2713aSLionel Sambuc public:
IfExprAST(ExprAST * cond,ExprAST * then,ExprAST * _else)185f4a2713aSLionel Sambuc IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
186f4a2713aSLionel Sambuc : Cond(cond), Then(then), Else(_else) {}
187f4a2713aSLionel Sambuc virtual Value *Codegen();
188f4a2713aSLionel Sambuc };
189f4a2713aSLionel Sambuc
190f4a2713aSLionel Sambuc /// ForExprAST - Expression class for for/in.
191f4a2713aSLionel Sambuc class ForExprAST : public ExprAST {
192f4a2713aSLionel Sambuc std::string VarName;
193f4a2713aSLionel Sambuc ExprAST *Start, *End, *Step, *Body;
194*0a6a1f1dSLionel Sambuc
195f4a2713aSLionel Sambuc public:
ForExprAST(const std::string & varname,ExprAST * start,ExprAST * end,ExprAST * step,ExprAST * body)196f4a2713aSLionel Sambuc ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
197f4a2713aSLionel Sambuc ExprAST *step, ExprAST *body)
198f4a2713aSLionel Sambuc : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
199f4a2713aSLionel Sambuc virtual Value *Codegen();
200f4a2713aSLionel Sambuc };
201f4a2713aSLionel Sambuc
202f4a2713aSLionel Sambuc /// PrototypeAST - This class represents the "prototype" for a function,
203f4a2713aSLionel Sambuc /// which captures its name, and its argument names (thus implicitly the number
204f4a2713aSLionel Sambuc /// of arguments the function takes), as well as if it is an operator.
205f4a2713aSLionel Sambuc class PrototypeAST {
206f4a2713aSLionel Sambuc std::string Name;
207f4a2713aSLionel Sambuc std::vector<std::string> Args;
208f4a2713aSLionel Sambuc bool isOperator;
209f4a2713aSLionel Sambuc unsigned Precedence; // Precedence if a binary op.
210f4a2713aSLionel Sambuc public:
PrototypeAST(const std::string & name,const std::vector<std::string> & args,bool isoperator=false,unsigned prec=0)211f4a2713aSLionel Sambuc PrototypeAST(const std::string &name, const std::vector<std::string> &args,
212f4a2713aSLionel Sambuc bool isoperator = false, unsigned prec = 0)
213f4a2713aSLionel Sambuc : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {}
214f4a2713aSLionel Sambuc
isUnaryOp() const215f4a2713aSLionel Sambuc bool isUnaryOp() const { return isOperator && Args.size() == 1; }
isBinaryOp() const216f4a2713aSLionel Sambuc bool isBinaryOp() const { return isOperator && Args.size() == 2; }
217f4a2713aSLionel Sambuc
getOperatorName() const218f4a2713aSLionel Sambuc char getOperatorName() const {
219f4a2713aSLionel Sambuc assert(isUnaryOp() || isBinaryOp());
220f4a2713aSLionel Sambuc return Name[Name.size() - 1];
221f4a2713aSLionel Sambuc }
222f4a2713aSLionel Sambuc
getBinaryPrecedence() const223f4a2713aSLionel Sambuc unsigned getBinaryPrecedence() const { return Precedence; }
224f4a2713aSLionel Sambuc
225f4a2713aSLionel Sambuc Function *Codegen();
226f4a2713aSLionel Sambuc };
227f4a2713aSLionel Sambuc
228f4a2713aSLionel Sambuc /// FunctionAST - This class represents a function definition itself.
229f4a2713aSLionel Sambuc class FunctionAST {
230f4a2713aSLionel Sambuc PrototypeAST *Proto;
231f4a2713aSLionel Sambuc ExprAST *Body;
232*0a6a1f1dSLionel Sambuc
233f4a2713aSLionel Sambuc public:
FunctionAST(PrototypeAST * proto,ExprAST * body)234*0a6a1f1dSLionel Sambuc FunctionAST(PrototypeAST *proto, ExprAST *body) : Proto(proto), Body(body) {}
235f4a2713aSLionel Sambuc
236f4a2713aSLionel Sambuc Function *Codegen();
237f4a2713aSLionel Sambuc };
238f4a2713aSLionel Sambuc } // end anonymous namespace
239f4a2713aSLionel Sambuc
240f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
241f4a2713aSLionel Sambuc // Parser
242f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
243f4a2713aSLionel Sambuc
244f4a2713aSLionel Sambuc /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
245f4a2713aSLionel Sambuc /// token the parser is looking at. getNextToken reads another token from the
246f4a2713aSLionel Sambuc /// lexer and updates CurTok with its results.
247f4a2713aSLionel Sambuc static int CurTok;
getNextToken()248*0a6a1f1dSLionel Sambuc static int getNextToken() { return CurTok = gettok(); }
249f4a2713aSLionel Sambuc
250f4a2713aSLionel Sambuc /// BinopPrecedence - This holds the precedence for each binary operator that is
251f4a2713aSLionel Sambuc /// defined.
252f4a2713aSLionel Sambuc static std::map<char, int> BinopPrecedence;
253f4a2713aSLionel Sambuc
254f4a2713aSLionel Sambuc /// GetTokPrecedence - Get the precedence of the pending binary operator token.
GetTokPrecedence()255f4a2713aSLionel Sambuc static int GetTokPrecedence() {
256f4a2713aSLionel Sambuc if (!isascii(CurTok))
257f4a2713aSLionel Sambuc return -1;
258f4a2713aSLionel Sambuc
259f4a2713aSLionel Sambuc // Make sure it's a declared binop.
260f4a2713aSLionel Sambuc int TokPrec = BinopPrecedence[CurTok];
261*0a6a1f1dSLionel Sambuc if (TokPrec <= 0)
262*0a6a1f1dSLionel Sambuc return -1;
263f4a2713aSLionel Sambuc return TokPrec;
264f4a2713aSLionel Sambuc }
265f4a2713aSLionel Sambuc
266f4a2713aSLionel Sambuc /// Error* - These are little helper functions for error handling.
Error(const char * Str)267*0a6a1f1dSLionel Sambuc ExprAST *Error(const char *Str) {
268*0a6a1f1dSLionel Sambuc fprintf(stderr, "Error: %s\n", Str);
269*0a6a1f1dSLionel Sambuc return 0;
270*0a6a1f1dSLionel Sambuc }
ErrorP(const char * Str)271*0a6a1f1dSLionel Sambuc PrototypeAST *ErrorP(const char *Str) {
272*0a6a1f1dSLionel Sambuc Error(Str);
273*0a6a1f1dSLionel Sambuc return 0;
274*0a6a1f1dSLionel Sambuc }
ErrorF(const char * Str)275*0a6a1f1dSLionel Sambuc FunctionAST *ErrorF(const char *Str) {
276*0a6a1f1dSLionel Sambuc Error(Str);
277*0a6a1f1dSLionel Sambuc return 0;
278*0a6a1f1dSLionel Sambuc }
279f4a2713aSLionel Sambuc
280f4a2713aSLionel Sambuc static ExprAST *ParseExpression();
281f4a2713aSLionel Sambuc
282f4a2713aSLionel Sambuc /// identifierexpr
283f4a2713aSLionel Sambuc /// ::= identifier
284f4a2713aSLionel Sambuc /// ::= identifier '(' expression* ')'
ParseIdentifierExpr()285f4a2713aSLionel Sambuc static ExprAST *ParseIdentifierExpr() {
286f4a2713aSLionel Sambuc std::string IdName = IdentifierStr;
287f4a2713aSLionel Sambuc
288f4a2713aSLionel Sambuc getNextToken(); // eat identifier.
289f4a2713aSLionel Sambuc
290f4a2713aSLionel Sambuc if (CurTok != '(') // Simple variable ref.
291f4a2713aSLionel Sambuc return new VariableExprAST(IdName);
292f4a2713aSLionel Sambuc
293f4a2713aSLionel Sambuc // Call.
294f4a2713aSLionel Sambuc getNextToken(); // eat (
295f4a2713aSLionel Sambuc std::vector<ExprAST *> Args;
296f4a2713aSLionel Sambuc if (CurTok != ')') {
297f4a2713aSLionel Sambuc while (1) {
298f4a2713aSLionel Sambuc ExprAST *Arg = ParseExpression();
299*0a6a1f1dSLionel Sambuc if (!Arg)
300*0a6a1f1dSLionel Sambuc return 0;
301f4a2713aSLionel Sambuc Args.push_back(Arg);
302f4a2713aSLionel Sambuc
303*0a6a1f1dSLionel Sambuc if (CurTok == ')')
304*0a6a1f1dSLionel Sambuc break;
305f4a2713aSLionel Sambuc
306f4a2713aSLionel Sambuc if (CurTok != ',')
307f4a2713aSLionel Sambuc return Error("Expected ')' or ',' in argument list");
308f4a2713aSLionel Sambuc getNextToken();
309f4a2713aSLionel Sambuc }
310f4a2713aSLionel Sambuc }
311f4a2713aSLionel Sambuc
312f4a2713aSLionel Sambuc // Eat the ')'.
313f4a2713aSLionel Sambuc getNextToken();
314f4a2713aSLionel Sambuc
315f4a2713aSLionel Sambuc return new CallExprAST(IdName, Args);
316f4a2713aSLionel Sambuc }
317f4a2713aSLionel Sambuc
318f4a2713aSLionel Sambuc /// numberexpr ::= number
ParseNumberExpr()319f4a2713aSLionel Sambuc static ExprAST *ParseNumberExpr() {
320f4a2713aSLionel Sambuc ExprAST *Result = new NumberExprAST(NumVal);
321f4a2713aSLionel Sambuc getNextToken(); // consume the number
322f4a2713aSLionel Sambuc return Result;
323f4a2713aSLionel Sambuc }
324f4a2713aSLionel Sambuc
325f4a2713aSLionel Sambuc /// parenexpr ::= '(' expression ')'
ParseParenExpr()326f4a2713aSLionel Sambuc static ExprAST *ParseParenExpr() {
327f4a2713aSLionel Sambuc getNextToken(); // eat (.
328f4a2713aSLionel Sambuc ExprAST *V = ParseExpression();
329*0a6a1f1dSLionel Sambuc if (!V)
330*0a6a1f1dSLionel Sambuc return 0;
331f4a2713aSLionel Sambuc
332f4a2713aSLionel Sambuc if (CurTok != ')')
333f4a2713aSLionel Sambuc return Error("expected ')'");
334f4a2713aSLionel Sambuc getNextToken(); // eat ).
335f4a2713aSLionel Sambuc return V;
336f4a2713aSLionel Sambuc }
337f4a2713aSLionel Sambuc
338f4a2713aSLionel Sambuc /// ifexpr ::= 'if' expression 'then' expression 'else' expression
ParseIfExpr()339f4a2713aSLionel Sambuc static ExprAST *ParseIfExpr() {
340f4a2713aSLionel Sambuc getNextToken(); // eat the if.
341f4a2713aSLionel Sambuc
342f4a2713aSLionel Sambuc // condition.
343f4a2713aSLionel Sambuc ExprAST *Cond = ParseExpression();
344*0a6a1f1dSLionel Sambuc if (!Cond)
345*0a6a1f1dSLionel Sambuc return 0;
346f4a2713aSLionel Sambuc
347f4a2713aSLionel Sambuc if (CurTok != tok_then)
348f4a2713aSLionel Sambuc return Error("expected then");
349f4a2713aSLionel Sambuc getNextToken(); // eat the then
350f4a2713aSLionel Sambuc
351f4a2713aSLionel Sambuc ExprAST *Then = ParseExpression();
352*0a6a1f1dSLionel Sambuc if (Then == 0)
353*0a6a1f1dSLionel Sambuc return 0;
354f4a2713aSLionel Sambuc
355f4a2713aSLionel Sambuc if (CurTok != tok_else)
356f4a2713aSLionel Sambuc return Error("expected else");
357f4a2713aSLionel Sambuc
358f4a2713aSLionel Sambuc getNextToken();
359f4a2713aSLionel Sambuc
360f4a2713aSLionel Sambuc ExprAST *Else = ParseExpression();
361*0a6a1f1dSLionel Sambuc if (!Else)
362*0a6a1f1dSLionel Sambuc return 0;
363f4a2713aSLionel Sambuc
364f4a2713aSLionel Sambuc return new IfExprAST(Cond, Then, Else);
365f4a2713aSLionel Sambuc }
366f4a2713aSLionel Sambuc
367f4a2713aSLionel Sambuc /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
ParseForExpr()368f4a2713aSLionel Sambuc static ExprAST *ParseForExpr() {
369f4a2713aSLionel Sambuc getNextToken(); // eat the for.
370f4a2713aSLionel Sambuc
371f4a2713aSLionel Sambuc if (CurTok != tok_identifier)
372f4a2713aSLionel Sambuc return Error("expected identifier after for");
373f4a2713aSLionel Sambuc
374f4a2713aSLionel Sambuc std::string IdName = IdentifierStr;
375f4a2713aSLionel Sambuc getNextToken(); // eat identifier.
376f4a2713aSLionel Sambuc
377f4a2713aSLionel Sambuc if (CurTok != '=')
378f4a2713aSLionel Sambuc return Error("expected '=' after for");
379f4a2713aSLionel Sambuc getNextToken(); // eat '='.
380f4a2713aSLionel Sambuc
381f4a2713aSLionel Sambuc ExprAST *Start = ParseExpression();
382*0a6a1f1dSLionel Sambuc if (Start == 0)
383*0a6a1f1dSLionel Sambuc return 0;
384f4a2713aSLionel Sambuc if (CurTok != ',')
385f4a2713aSLionel Sambuc return Error("expected ',' after for start value");
386f4a2713aSLionel Sambuc getNextToken();
387f4a2713aSLionel Sambuc
388f4a2713aSLionel Sambuc ExprAST *End = ParseExpression();
389*0a6a1f1dSLionel Sambuc if (End == 0)
390*0a6a1f1dSLionel Sambuc return 0;
391f4a2713aSLionel Sambuc
392f4a2713aSLionel Sambuc // The step value is optional.
393f4a2713aSLionel Sambuc ExprAST *Step = 0;
394f4a2713aSLionel Sambuc if (CurTok == ',') {
395f4a2713aSLionel Sambuc getNextToken();
396f4a2713aSLionel Sambuc Step = ParseExpression();
397*0a6a1f1dSLionel Sambuc if (Step == 0)
398*0a6a1f1dSLionel Sambuc return 0;
399f4a2713aSLionel Sambuc }
400f4a2713aSLionel Sambuc
401f4a2713aSLionel Sambuc if (CurTok != tok_in)
402f4a2713aSLionel Sambuc return Error("expected 'in' after for");
403f4a2713aSLionel Sambuc getNextToken(); // eat 'in'.
404f4a2713aSLionel Sambuc
405f4a2713aSLionel Sambuc ExprAST *Body = ParseExpression();
406*0a6a1f1dSLionel Sambuc if (Body == 0)
407*0a6a1f1dSLionel Sambuc return 0;
408f4a2713aSLionel Sambuc
409f4a2713aSLionel Sambuc return new ForExprAST(IdName, Start, End, Step, Body);
410f4a2713aSLionel Sambuc }
411f4a2713aSLionel Sambuc
412f4a2713aSLionel Sambuc /// primary
413f4a2713aSLionel Sambuc /// ::= identifierexpr
414f4a2713aSLionel Sambuc /// ::= numberexpr
415f4a2713aSLionel Sambuc /// ::= parenexpr
416f4a2713aSLionel Sambuc /// ::= ifexpr
417f4a2713aSLionel Sambuc /// ::= forexpr
ParsePrimary()418f4a2713aSLionel Sambuc static ExprAST *ParsePrimary() {
419f4a2713aSLionel Sambuc switch (CurTok) {
420*0a6a1f1dSLionel Sambuc default:
421*0a6a1f1dSLionel Sambuc return Error("unknown token when expecting an expression");
422*0a6a1f1dSLionel Sambuc case tok_identifier:
423*0a6a1f1dSLionel Sambuc return ParseIdentifierExpr();
424*0a6a1f1dSLionel Sambuc case tok_number:
425*0a6a1f1dSLionel Sambuc return ParseNumberExpr();
426*0a6a1f1dSLionel Sambuc case '(':
427*0a6a1f1dSLionel Sambuc return ParseParenExpr();
428*0a6a1f1dSLionel Sambuc case tok_if:
429*0a6a1f1dSLionel Sambuc return ParseIfExpr();
430*0a6a1f1dSLionel Sambuc case tok_for:
431*0a6a1f1dSLionel Sambuc return ParseForExpr();
432f4a2713aSLionel Sambuc }
433f4a2713aSLionel Sambuc }
434f4a2713aSLionel Sambuc
435f4a2713aSLionel Sambuc /// unary
436f4a2713aSLionel Sambuc /// ::= primary
437f4a2713aSLionel Sambuc /// ::= '!' unary
ParseUnary()438f4a2713aSLionel Sambuc static ExprAST *ParseUnary() {
439f4a2713aSLionel Sambuc // If the current token is not an operator, it must be a primary expr.
440f4a2713aSLionel Sambuc if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
441f4a2713aSLionel Sambuc return ParsePrimary();
442f4a2713aSLionel Sambuc
443f4a2713aSLionel Sambuc // If this is a unary operator, read it.
444f4a2713aSLionel Sambuc int Opc = CurTok;
445f4a2713aSLionel Sambuc getNextToken();
446f4a2713aSLionel Sambuc if (ExprAST *Operand = ParseUnary())
447f4a2713aSLionel Sambuc return new UnaryExprAST(Opc, Operand);
448f4a2713aSLionel Sambuc return 0;
449f4a2713aSLionel Sambuc }
450f4a2713aSLionel Sambuc
451f4a2713aSLionel Sambuc /// binoprhs
452f4a2713aSLionel Sambuc /// ::= ('+' unary)*
ParseBinOpRHS(int ExprPrec,ExprAST * LHS)453f4a2713aSLionel Sambuc static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
454f4a2713aSLionel Sambuc // If this is a binop, find its precedence.
455f4a2713aSLionel Sambuc while (1) {
456f4a2713aSLionel Sambuc int TokPrec = GetTokPrecedence();
457f4a2713aSLionel Sambuc
458f4a2713aSLionel Sambuc // If this is a binop that binds at least as tightly as the current binop,
459f4a2713aSLionel Sambuc // consume it, otherwise we are done.
460f4a2713aSLionel Sambuc if (TokPrec < ExprPrec)
461f4a2713aSLionel Sambuc return LHS;
462f4a2713aSLionel Sambuc
463f4a2713aSLionel Sambuc // Okay, we know this is a binop.
464f4a2713aSLionel Sambuc int BinOp = CurTok;
465f4a2713aSLionel Sambuc getNextToken(); // eat binop
466f4a2713aSLionel Sambuc
467f4a2713aSLionel Sambuc // Parse the unary expression after the binary operator.
468f4a2713aSLionel Sambuc ExprAST *RHS = ParseUnary();
469*0a6a1f1dSLionel Sambuc if (!RHS)
470*0a6a1f1dSLionel Sambuc return 0;
471f4a2713aSLionel Sambuc
472f4a2713aSLionel Sambuc // If BinOp binds less tightly with RHS than the operator after RHS, let
473f4a2713aSLionel Sambuc // the pending operator take RHS as its LHS.
474f4a2713aSLionel Sambuc int NextPrec = GetTokPrecedence();
475f4a2713aSLionel Sambuc if (TokPrec < NextPrec) {
476f4a2713aSLionel Sambuc RHS = ParseBinOpRHS(TokPrec + 1, RHS);
477*0a6a1f1dSLionel Sambuc if (RHS == 0)
478*0a6a1f1dSLionel Sambuc return 0;
479f4a2713aSLionel Sambuc }
480f4a2713aSLionel Sambuc
481f4a2713aSLionel Sambuc // Merge LHS/RHS.
482f4a2713aSLionel Sambuc LHS = new BinaryExprAST(BinOp, LHS, RHS);
483f4a2713aSLionel Sambuc }
484f4a2713aSLionel Sambuc }
485f4a2713aSLionel Sambuc
486f4a2713aSLionel Sambuc /// expression
487f4a2713aSLionel Sambuc /// ::= unary binoprhs
488f4a2713aSLionel Sambuc ///
ParseExpression()489f4a2713aSLionel Sambuc static ExprAST *ParseExpression() {
490f4a2713aSLionel Sambuc ExprAST *LHS = ParseUnary();
491*0a6a1f1dSLionel Sambuc if (!LHS)
492*0a6a1f1dSLionel Sambuc return 0;
493f4a2713aSLionel Sambuc
494f4a2713aSLionel Sambuc return ParseBinOpRHS(0, LHS);
495f4a2713aSLionel Sambuc }
496f4a2713aSLionel Sambuc
497f4a2713aSLionel Sambuc /// prototype
498f4a2713aSLionel Sambuc /// ::= id '(' id* ')'
499f4a2713aSLionel Sambuc /// ::= binary LETTER number? (id, id)
500f4a2713aSLionel Sambuc /// ::= unary LETTER (id)
ParsePrototype()501f4a2713aSLionel Sambuc static PrototypeAST *ParsePrototype() {
502f4a2713aSLionel Sambuc std::string FnName;
503f4a2713aSLionel Sambuc
504f4a2713aSLionel Sambuc unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
505f4a2713aSLionel Sambuc unsigned BinaryPrecedence = 30;
506f4a2713aSLionel Sambuc
507f4a2713aSLionel Sambuc switch (CurTok) {
508f4a2713aSLionel Sambuc default:
509f4a2713aSLionel Sambuc return ErrorP("Expected function name in prototype");
510f4a2713aSLionel Sambuc case tok_identifier:
511f4a2713aSLionel Sambuc FnName = IdentifierStr;
512f4a2713aSLionel Sambuc Kind = 0;
513f4a2713aSLionel Sambuc getNextToken();
514f4a2713aSLionel Sambuc break;
515f4a2713aSLionel Sambuc case tok_unary:
516f4a2713aSLionel Sambuc getNextToken();
517f4a2713aSLionel Sambuc if (!isascii(CurTok))
518f4a2713aSLionel Sambuc return ErrorP("Expected unary operator");
519f4a2713aSLionel Sambuc FnName = "unary";
520f4a2713aSLionel Sambuc FnName += (char)CurTok;
521f4a2713aSLionel Sambuc Kind = 1;
522f4a2713aSLionel Sambuc getNextToken();
523f4a2713aSLionel Sambuc break;
524f4a2713aSLionel Sambuc case tok_binary:
525f4a2713aSLionel Sambuc getNextToken();
526f4a2713aSLionel Sambuc if (!isascii(CurTok))
527f4a2713aSLionel Sambuc return ErrorP("Expected binary operator");
528f4a2713aSLionel Sambuc FnName = "binary";
529f4a2713aSLionel Sambuc FnName += (char)CurTok;
530f4a2713aSLionel Sambuc Kind = 2;
531f4a2713aSLionel Sambuc getNextToken();
532f4a2713aSLionel Sambuc
533f4a2713aSLionel Sambuc // Read the precedence if present.
534f4a2713aSLionel Sambuc if (CurTok == tok_number) {
535f4a2713aSLionel Sambuc if (NumVal < 1 || NumVal > 100)
536f4a2713aSLionel Sambuc return ErrorP("Invalid precedecnce: must be 1..100");
537f4a2713aSLionel Sambuc BinaryPrecedence = (unsigned)NumVal;
538f4a2713aSLionel Sambuc getNextToken();
539f4a2713aSLionel Sambuc }
540f4a2713aSLionel Sambuc break;
541f4a2713aSLionel Sambuc }
542f4a2713aSLionel Sambuc
543f4a2713aSLionel Sambuc if (CurTok != '(')
544f4a2713aSLionel Sambuc return ErrorP("Expected '(' in prototype");
545f4a2713aSLionel Sambuc
546f4a2713aSLionel Sambuc std::vector<std::string> ArgNames;
547f4a2713aSLionel Sambuc while (getNextToken() == tok_identifier)
548f4a2713aSLionel Sambuc ArgNames.push_back(IdentifierStr);
549f4a2713aSLionel Sambuc if (CurTok != ')')
550f4a2713aSLionel Sambuc return ErrorP("Expected ')' in prototype");
551f4a2713aSLionel Sambuc
552f4a2713aSLionel Sambuc // success.
553f4a2713aSLionel Sambuc getNextToken(); // eat ')'.
554f4a2713aSLionel Sambuc
555f4a2713aSLionel Sambuc // Verify right number of names for operator.
556f4a2713aSLionel Sambuc if (Kind && ArgNames.size() != Kind)
557f4a2713aSLionel Sambuc return ErrorP("Invalid number of operands for operator");
558f4a2713aSLionel Sambuc
559f4a2713aSLionel Sambuc return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);
560f4a2713aSLionel Sambuc }
561f4a2713aSLionel Sambuc
562f4a2713aSLionel Sambuc /// definition ::= 'def' prototype expression
ParseDefinition()563f4a2713aSLionel Sambuc static FunctionAST *ParseDefinition() {
564f4a2713aSLionel Sambuc getNextToken(); // eat def.
565f4a2713aSLionel Sambuc PrototypeAST *Proto = ParsePrototype();
566*0a6a1f1dSLionel Sambuc if (Proto == 0)
567*0a6a1f1dSLionel Sambuc return 0;
568f4a2713aSLionel Sambuc
569f4a2713aSLionel Sambuc if (ExprAST *E = ParseExpression())
570f4a2713aSLionel Sambuc return new FunctionAST(Proto, E);
571f4a2713aSLionel Sambuc return 0;
572f4a2713aSLionel Sambuc }
573f4a2713aSLionel Sambuc
574f4a2713aSLionel Sambuc /// toplevelexpr ::= expression
ParseTopLevelExpr()575f4a2713aSLionel Sambuc static FunctionAST *ParseTopLevelExpr() {
576f4a2713aSLionel Sambuc if (ExprAST *E = ParseExpression()) {
577f4a2713aSLionel Sambuc // Make an anonymous proto.
578f4a2713aSLionel Sambuc PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
579f4a2713aSLionel Sambuc return new FunctionAST(Proto, E);
580f4a2713aSLionel Sambuc }
581f4a2713aSLionel Sambuc return 0;
582f4a2713aSLionel Sambuc }
583f4a2713aSLionel Sambuc
584f4a2713aSLionel Sambuc /// external ::= 'extern' prototype
ParseExtern()585f4a2713aSLionel Sambuc static PrototypeAST *ParseExtern() {
586f4a2713aSLionel Sambuc getNextToken(); // eat extern.
587f4a2713aSLionel Sambuc return ParsePrototype();
588f4a2713aSLionel Sambuc }
589f4a2713aSLionel Sambuc
590f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
591f4a2713aSLionel Sambuc // Code Generation
592f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
593f4a2713aSLionel Sambuc
594f4a2713aSLionel Sambuc static Module *TheModule;
595f4a2713aSLionel Sambuc static IRBuilder<> Builder(getGlobalContext());
596f4a2713aSLionel Sambuc static std::map<std::string, Value *> NamedValues;
597f4a2713aSLionel Sambuc static FunctionPassManager *TheFPM;
598f4a2713aSLionel Sambuc
ErrorV(const char * Str)599*0a6a1f1dSLionel Sambuc Value *ErrorV(const char *Str) {
600*0a6a1f1dSLionel Sambuc Error(Str);
601*0a6a1f1dSLionel Sambuc return 0;
602*0a6a1f1dSLionel Sambuc }
603f4a2713aSLionel Sambuc
Codegen()604f4a2713aSLionel Sambuc Value *NumberExprAST::Codegen() {
605f4a2713aSLionel Sambuc return ConstantFP::get(getGlobalContext(), APFloat(Val));
606f4a2713aSLionel Sambuc }
607f4a2713aSLionel Sambuc
Codegen()608f4a2713aSLionel Sambuc Value *VariableExprAST::Codegen() {
609f4a2713aSLionel Sambuc // Look this variable up in the function.
610f4a2713aSLionel Sambuc Value *V = NamedValues[Name];
611f4a2713aSLionel Sambuc return V ? V : ErrorV("Unknown variable name");
612f4a2713aSLionel Sambuc }
613f4a2713aSLionel Sambuc
Codegen()614f4a2713aSLionel Sambuc Value *UnaryExprAST::Codegen() {
615f4a2713aSLionel Sambuc Value *OperandV = Operand->Codegen();
616*0a6a1f1dSLionel Sambuc if (OperandV == 0)
617*0a6a1f1dSLionel Sambuc return 0;
618f4a2713aSLionel Sambuc
619f4a2713aSLionel Sambuc Function *F = TheModule->getFunction(std::string("unary") + Opcode);
620f4a2713aSLionel Sambuc if (F == 0)
621f4a2713aSLionel Sambuc return ErrorV("Unknown unary operator");
622f4a2713aSLionel Sambuc
623f4a2713aSLionel Sambuc return Builder.CreateCall(F, OperandV, "unop");
624f4a2713aSLionel Sambuc }
625f4a2713aSLionel Sambuc
Codegen()626f4a2713aSLionel Sambuc Value *BinaryExprAST::Codegen() {
627f4a2713aSLionel Sambuc Value *L = LHS->Codegen();
628f4a2713aSLionel Sambuc Value *R = RHS->Codegen();
629*0a6a1f1dSLionel Sambuc if (L == 0 || R == 0)
630*0a6a1f1dSLionel Sambuc return 0;
631f4a2713aSLionel Sambuc
632f4a2713aSLionel Sambuc switch (Op) {
633*0a6a1f1dSLionel Sambuc case '+':
634*0a6a1f1dSLionel Sambuc return Builder.CreateFAdd(L, R, "addtmp");
635*0a6a1f1dSLionel Sambuc case '-':
636*0a6a1f1dSLionel Sambuc return Builder.CreateFSub(L, R, "subtmp");
637*0a6a1f1dSLionel Sambuc case '*':
638*0a6a1f1dSLionel Sambuc return Builder.CreateFMul(L, R, "multmp");
639f4a2713aSLionel Sambuc case '<':
640f4a2713aSLionel Sambuc L = Builder.CreateFCmpULT(L, R, "cmptmp");
641f4a2713aSLionel Sambuc // Convert bool 0/1 to double 0.0 or 1.0
642f4a2713aSLionel Sambuc return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
643f4a2713aSLionel Sambuc "booltmp");
644*0a6a1f1dSLionel Sambuc default:
645*0a6a1f1dSLionel Sambuc break;
646f4a2713aSLionel Sambuc }
647f4a2713aSLionel Sambuc
648f4a2713aSLionel Sambuc // If it wasn't a builtin binary operator, it must be a user defined one. Emit
649f4a2713aSLionel Sambuc // a call to it.
650f4a2713aSLionel Sambuc Function *F = TheModule->getFunction(std::string("binary") + Op);
651f4a2713aSLionel Sambuc assert(F && "binary operator not found!");
652f4a2713aSLionel Sambuc
653f4a2713aSLionel Sambuc Value *Ops[] = { L, R };
654f4a2713aSLionel Sambuc return Builder.CreateCall(F, Ops, "binop");
655f4a2713aSLionel Sambuc }
656f4a2713aSLionel Sambuc
Codegen()657f4a2713aSLionel Sambuc Value *CallExprAST::Codegen() {
658f4a2713aSLionel Sambuc // Look up the name in the global module table.
659f4a2713aSLionel Sambuc Function *CalleeF = TheModule->getFunction(Callee);
660f4a2713aSLionel Sambuc if (CalleeF == 0)
661f4a2713aSLionel Sambuc return ErrorV("Unknown function referenced");
662f4a2713aSLionel Sambuc
663f4a2713aSLionel Sambuc // If argument mismatch error.
664f4a2713aSLionel Sambuc if (CalleeF->arg_size() != Args.size())
665f4a2713aSLionel Sambuc return ErrorV("Incorrect # arguments passed");
666f4a2713aSLionel Sambuc
667f4a2713aSLionel Sambuc std::vector<Value *> ArgsV;
668f4a2713aSLionel Sambuc for (unsigned i = 0, e = Args.size(); i != e; ++i) {
669f4a2713aSLionel Sambuc ArgsV.push_back(Args[i]->Codegen());
670*0a6a1f1dSLionel Sambuc if (ArgsV.back() == 0)
671*0a6a1f1dSLionel Sambuc return 0;
672f4a2713aSLionel Sambuc }
673f4a2713aSLionel Sambuc
674f4a2713aSLionel Sambuc return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
675f4a2713aSLionel Sambuc }
676f4a2713aSLionel Sambuc
Codegen()677f4a2713aSLionel Sambuc Value *IfExprAST::Codegen() {
678f4a2713aSLionel Sambuc Value *CondV = Cond->Codegen();
679*0a6a1f1dSLionel Sambuc if (CondV == 0)
680*0a6a1f1dSLionel Sambuc return 0;
681f4a2713aSLionel Sambuc
682f4a2713aSLionel Sambuc // Convert condition to a bool by comparing equal to 0.0.
683*0a6a1f1dSLionel Sambuc CondV = Builder.CreateFCmpONE(
684*0a6a1f1dSLionel Sambuc CondV, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "ifcond");
685f4a2713aSLionel Sambuc
686f4a2713aSLionel Sambuc Function *TheFunction = Builder.GetInsertBlock()->getParent();
687f4a2713aSLionel Sambuc
688f4a2713aSLionel Sambuc // Create blocks for the then and else cases. Insert the 'then' block at the
689f4a2713aSLionel Sambuc // end of the function.
690*0a6a1f1dSLionel Sambuc BasicBlock *ThenBB =
691*0a6a1f1dSLionel Sambuc BasicBlock::Create(getGlobalContext(), "then", TheFunction);
692f4a2713aSLionel Sambuc BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
693f4a2713aSLionel Sambuc BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
694f4a2713aSLionel Sambuc
695f4a2713aSLionel Sambuc Builder.CreateCondBr(CondV, ThenBB, ElseBB);
696f4a2713aSLionel Sambuc
697f4a2713aSLionel Sambuc // Emit then value.
698f4a2713aSLionel Sambuc Builder.SetInsertPoint(ThenBB);
699f4a2713aSLionel Sambuc
700f4a2713aSLionel Sambuc Value *ThenV = Then->Codegen();
701*0a6a1f1dSLionel Sambuc if (ThenV == 0)
702*0a6a1f1dSLionel Sambuc return 0;
703f4a2713aSLionel Sambuc
704f4a2713aSLionel Sambuc Builder.CreateBr(MergeBB);
705f4a2713aSLionel Sambuc // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
706f4a2713aSLionel Sambuc ThenBB = Builder.GetInsertBlock();
707f4a2713aSLionel Sambuc
708f4a2713aSLionel Sambuc // Emit else block.
709f4a2713aSLionel Sambuc TheFunction->getBasicBlockList().push_back(ElseBB);
710f4a2713aSLionel Sambuc Builder.SetInsertPoint(ElseBB);
711f4a2713aSLionel Sambuc
712f4a2713aSLionel Sambuc Value *ElseV = Else->Codegen();
713*0a6a1f1dSLionel Sambuc if (ElseV == 0)
714*0a6a1f1dSLionel Sambuc return 0;
715f4a2713aSLionel Sambuc
716f4a2713aSLionel Sambuc Builder.CreateBr(MergeBB);
717f4a2713aSLionel Sambuc // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
718f4a2713aSLionel Sambuc ElseBB = Builder.GetInsertBlock();
719f4a2713aSLionel Sambuc
720f4a2713aSLionel Sambuc // Emit merge block.
721f4a2713aSLionel Sambuc TheFunction->getBasicBlockList().push_back(MergeBB);
722f4a2713aSLionel Sambuc Builder.SetInsertPoint(MergeBB);
723*0a6a1f1dSLionel Sambuc PHINode *PN =
724*0a6a1f1dSLionel Sambuc Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, "iftmp");
725f4a2713aSLionel Sambuc
726f4a2713aSLionel Sambuc PN->addIncoming(ThenV, ThenBB);
727f4a2713aSLionel Sambuc PN->addIncoming(ElseV, ElseBB);
728f4a2713aSLionel Sambuc return PN;
729f4a2713aSLionel Sambuc }
730f4a2713aSLionel Sambuc
Codegen()731f4a2713aSLionel Sambuc Value *ForExprAST::Codegen() {
732f4a2713aSLionel Sambuc // Output this as:
733f4a2713aSLionel Sambuc // ...
734f4a2713aSLionel Sambuc // start = startexpr
735f4a2713aSLionel Sambuc // goto loop
736f4a2713aSLionel Sambuc // loop:
737f4a2713aSLionel Sambuc // variable = phi [start, loopheader], [nextvariable, loopend]
738f4a2713aSLionel Sambuc // ...
739f4a2713aSLionel Sambuc // bodyexpr
740f4a2713aSLionel Sambuc // ...
741f4a2713aSLionel Sambuc // loopend:
742f4a2713aSLionel Sambuc // step = stepexpr
743f4a2713aSLionel Sambuc // nextvariable = variable + step
744f4a2713aSLionel Sambuc // endcond = endexpr
745f4a2713aSLionel Sambuc // br endcond, loop, endloop
746f4a2713aSLionel Sambuc // outloop:
747f4a2713aSLionel Sambuc
748f4a2713aSLionel Sambuc // Emit the start code first, without 'variable' in scope.
749f4a2713aSLionel Sambuc Value *StartVal = Start->Codegen();
750*0a6a1f1dSLionel Sambuc if (StartVal == 0)
751*0a6a1f1dSLionel Sambuc return 0;
752f4a2713aSLionel Sambuc
753f4a2713aSLionel Sambuc // Make the new basic block for the loop header, inserting after current
754f4a2713aSLionel Sambuc // block.
755f4a2713aSLionel Sambuc Function *TheFunction = Builder.GetInsertBlock()->getParent();
756f4a2713aSLionel Sambuc BasicBlock *PreheaderBB = Builder.GetInsertBlock();
757*0a6a1f1dSLionel Sambuc BasicBlock *LoopBB =
758*0a6a1f1dSLionel Sambuc BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
759f4a2713aSLionel Sambuc
760f4a2713aSLionel Sambuc // Insert an explicit fall through from the current block to the LoopBB.
761f4a2713aSLionel Sambuc Builder.CreateBr(LoopBB);
762f4a2713aSLionel Sambuc
763f4a2713aSLionel Sambuc // Start insertion in LoopBB.
764f4a2713aSLionel Sambuc Builder.SetInsertPoint(LoopBB);
765f4a2713aSLionel Sambuc
766f4a2713aSLionel Sambuc // Start the PHI node with an entry for Start.
767*0a6a1f1dSLionel Sambuc PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()),
768*0a6a1f1dSLionel Sambuc 2, VarName.c_str());
769f4a2713aSLionel Sambuc Variable->addIncoming(StartVal, PreheaderBB);
770f4a2713aSLionel Sambuc
771f4a2713aSLionel Sambuc // Within the loop, the variable is defined equal to the PHI node. If it
772f4a2713aSLionel Sambuc // shadows an existing variable, we have to restore it, so save it now.
773f4a2713aSLionel Sambuc Value *OldVal = NamedValues[VarName];
774f4a2713aSLionel Sambuc NamedValues[VarName] = Variable;
775f4a2713aSLionel Sambuc
776f4a2713aSLionel Sambuc // Emit the body of the loop. This, like any other expr, can change the
777f4a2713aSLionel Sambuc // current BB. Note that we ignore the value computed by the body, but don't
778f4a2713aSLionel Sambuc // allow an error.
779f4a2713aSLionel Sambuc if (Body->Codegen() == 0)
780f4a2713aSLionel Sambuc return 0;
781f4a2713aSLionel Sambuc
782f4a2713aSLionel Sambuc // Emit the step value.
783f4a2713aSLionel Sambuc Value *StepVal;
784f4a2713aSLionel Sambuc if (Step) {
785f4a2713aSLionel Sambuc StepVal = Step->Codegen();
786*0a6a1f1dSLionel Sambuc if (StepVal == 0)
787*0a6a1f1dSLionel Sambuc return 0;
788f4a2713aSLionel Sambuc } else {
789f4a2713aSLionel Sambuc // If not specified, use 1.0.
790f4a2713aSLionel Sambuc StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
791f4a2713aSLionel Sambuc }
792f4a2713aSLionel Sambuc
793f4a2713aSLionel Sambuc Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");
794f4a2713aSLionel Sambuc
795f4a2713aSLionel Sambuc // Compute the end condition.
796f4a2713aSLionel Sambuc Value *EndCond = End->Codegen();
797*0a6a1f1dSLionel Sambuc if (EndCond == 0)
798*0a6a1f1dSLionel Sambuc return EndCond;
799f4a2713aSLionel Sambuc
800f4a2713aSLionel Sambuc // Convert condition to a bool by comparing equal to 0.0.
801*0a6a1f1dSLionel Sambuc EndCond = Builder.CreateFCmpONE(
802*0a6a1f1dSLionel Sambuc EndCond, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "loopcond");
803f4a2713aSLionel Sambuc
804f4a2713aSLionel Sambuc // Create the "after loop" block and insert it.
805f4a2713aSLionel Sambuc BasicBlock *LoopEndBB = Builder.GetInsertBlock();
806*0a6a1f1dSLionel Sambuc BasicBlock *AfterBB =
807*0a6a1f1dSLionel Sambuc BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
808f4a2713aSLionel Sambuc
809f4a2713aSLionel Sambuc // Insert the conditional branch into the end of LoopEndBB.
810f4a2713aSLionel Sambuc Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
811f4a2713aSLionel Sambuc
812f4a2713aSLionel Sambuc // Any new code will be inserted in AfterBB.
813f4a2713aSLionel Sambuc Builder.SetInsertPoint(AfterBB);
814f4a2713aSLionel Sambuc
815f4a2713aSLionel Sambuc // Add a new entry to the PHI node for the backedge.
816f4a2713aSLionel Sambuc Variable->addIncoming(NextVar, LoopEndBB);
817f4a2713aSLionel Sambuc
818f4a2713aSLionel Sambuc // Restore the unshadowed variable.
819f4a2713aSLionel Sambuc if (OldVal)
820f4a2713aSLionel Sambuc NamedValues[VarName] = OldVal;
821f4a2713aSLionel Sambuc else
822f4a2713aSLionel Sambuc NamedValues.erase(VarName);
823f4a2713aSLionel Sambuc
824f4a2713aSLionel Sambuc // for expr always returns 0.0.
825f4a2713aSLionel Sambuc return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
826f4a2713aSLionel Sambuc }
827f4a2713aSLionel Sambuc
Codegen()828f4a2713aSLionel Sambuc Function *PrototypeAST::Codegen() {
829f4a2713aSLionel Sambuc // Make the function type: double(double,double) etc.
830f4a2713aSLionel Sambuc std::vector<Type *> Doubles(Args.size(),
831f4a2713aSLionel Sambuc Type::getDoubleTy(getGlobalContext()));
832*0a6a1f1dSLionel Sambuc FunctionType *FT =
833*0a6a1f1dSLionel Sambuc FunctionType::get(Type::getDoubleTy(getGlobalContext()), Doubles, false);
834f4a2713aSLionel Sambuc
835*0a6a1f1dSLionel Sambuc Function *F =
836*0a6a1f1dSLionel Sambuc Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
837f4a2713aSLionel Sambuc
838f4a2713aSLionel Sambuc // If F conflicted, there was already something named 'Name'. If it has a
839f4a2713aSLionel Sambuc // body, don't allow redefinition or reextern.
840f4a2713aSLionel Sambuc if (F->getName() != Name) {
841f4a2713aSLionel Sambuc // Delete the one we just made and get the existing one.
842f4a2713aSLionel Sambuc F->eraseFromParent();
843f4a2713aSLionel Sambuc F = TheModule->getFunction(Name);
844f4a2713aSLionel Sambuc
845f4a2713aSLionel Sambuc // If F already has a body, reject this.
846f4a2713aSLionel Sambuc if (!F->empty()) {
847f4a2713aSLionel Sambuc ErrorF("redefinition of function");
848f4a2713aSLionel Sambuc return 0;
849f4a2713aSLionel Sambuc }
850f4a2713aSLionel Sambuc
851f4a2713aSLionel Sambuc // If F took a different number of args, reject.
852f4a2713aSLionel Sambuc if (F->arg_size() != Args.size()) {
853f4a2713aSLionel Sambuc ErrorF("redefinition of function with different # args");
854f4a2713aSLionel Sambuc return 0;
855f4a2713aSLionel Sambuc }
856f4a2713aSLionel Sambuc }
857f4a2713aSLionel Sambuc
858f4a2713aSLionel Sambuc // Set names for all arguments.
859f4a2713aSLionel Sambuc unsigned Idx = 0;
860f4a2713aSLionel Sambuc for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
861f4a2713aSLionel Sambuc ++AI, ++Idx) {
862f4a2713aSLionel Sambuc AI->setName(Args[Idx]);
863f4a2713aSLionel Sambuc
864f4a2713aSLionel Sambuc // Add arguments to variable symbol table.
865f4a2713aSLionel Sambuc NamedValues[Args[Idx]] = AI;
866f4a2713aSLionel Sambuc }
867f4a2713aSLionel Sambuc
868f4a2713aSLionel Sambuc return F;
869f4a2713aSLionel Sambuc }
870f4a2713aSLionel Sambuc
Codegen()871f4a2713aSLionel Sambuc Function *FunctionAST::Codegen() {
872f4a2713aSLionel Sambuc NamedValues.clear();
873f4a2713aSLionel Sambuc
874f4a2713aSLionel Sambuc Function *TheFunction = Proto->Codegen();
875f4a2713aSLionel Sambuc if (TheFunction == 0)
876f4a2713aSLionel Sambuc return 0;
877f4a2713aSLionel Sambuc
878f4a2713aSLionel Sambuc // If this is an operator, install it.
879f4a2713aSLionel Sambuc if (Proto->isBinaryOp())
880f4a2713aSLionel Sambuc BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence();
881f4a2713aSLionel Sambuc
882f4a2713aSLionel Sambuc // Create a new basic block to start insertion into.
883f4a2713aSLionel Sambuc BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
884f4a2713aSLionel Sambuc Builder.SetInsertPoint(BB);
885f4a2713aSLionel Sambuc
886f4a2713aSLionel Sambuc if (Value *RetVal = Body->Codegen()) {
887f4a2713aSLionel Sambuc // Finish off the function.
888f4a2713aSLionel Sambuc Builder.CreateRet(RetVal);
889f4a2713aSLionel Sambuc
890f4a2713aSLionel Sambuc // Validate the generated code, checking for consistency.
891f4a2713aSLionel Sambuc verifyFunction(*TheFunction);
892f4a2713aSLionel Sambuc
893f4a2713aSLionel Sambuc // Optimize the function.
894f4a2713aSLionel Sambuc TheFPM->run(*TheFunction);
895f4a2713aSLionel Sambuc
896f4a2713aSLionel Sambuc return TheFunction;
897f4a2713aSLionel Sambuc }
898f4a2713aSLionel Sambuc
899f4a2713aSLionel Sambuc // Error reading body, remove function.
900f4a2713aSLionel Sambuc TheFunction->eraseFromParent();
901f4a2713aSLionel Sambuc
902f4a2713aSLionel Sambuc if (Proto->isBinaryOp())
903f4a2713aSLionel Sambuc BinopPrecedence.erase(Proto->getOperatorName());
904f4a2713aSLionel Sambuc return 0;
905f4a2713aSLionel Sambuc }
906f4a2713aSLionel Sambuc
907f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
908f4a2713aSLionel Sambuc // Top-Level parsing and JIT Driver
909f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
910f4a2713aSLionel Sambuc
911f4a2713aSLionel Sambuc static ExecutionEngine *TheExecutionEngine;
912f4a2713aSLionel Sambuc
HandleDefinition()913f4a2713aSLionel Sambuc static void HandleDefinition() {
914f4a2713aSLionel Sambuc if (FunctionAST *F = ParseDefinition()) {
915f4a2713aSLionel Sambuc if (Function *LF = F->Codegen()) {
916f4a2713aSLionel Sambuc fprintf(stderr, "Read function definition:");
917f4a2713aSLionel Sambuc LF->dump();
918f4a2713aSLionel Sambuc }
919f4a2713aSLionel Sambuc } else {
920f4a2713aSLionel Sambuc // Skip token for error recovery.
921f4a2713aSLionel Sambuc getNextToken();
922f4a2713aSLionel Sambuc }
923f4a2713aSLionel Sambuc }
924f4a2713aSLionel Sambuc
HandleExtern()925f4a2713aSLionel Sambuc static void HandleExtern() {
926f4a2713aSLionel Sambuc if (PrototypeAST *P = ParseExtern()) {
927f4a2713aSLionel Sambuc if (Function *F = P->Codegen()) {
928f4a2713aSLionel Sambuc fprintf(stderr, "Read extern: ");
929f4a2713aSLionel Sambuc F->dump();
930f4a2713aSLionel Sambuc }
931f4a2713aSLionel Sambuc } else {
932f4a2713aSLionel Sambuc // Skip token for error recovery.
933f4a2713aSLionel Sambuc getNextToken();
934f4a2713aSLionel Sambuc }
935f4a2713aSLionel Sambuc }
936f4a2713aSLionel Sambuc
HandleTopLevelExpression()937f4a2713aSLionel Sambuc static void HandleTopLevelExpression() {
938f4a2713aSLionel Sambuc // Evaluate a top-level expression into an anonymous function.
939f4a2713aSLionel Sambuc if (FunctionAST *F = ParseTopLevelExpr()) {
940f4a2713aSLionel Sambuc if (Function *LF = F->Codegen()) {
941*0a6a1f1dSLionel Sambuc TheExecutionEngine->finalizeObject();
942f4a2713aSLionel Sambuc // JIT the function, returning a function pointer.
943f4a2713aSLionel Sambuc void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
944f4a2713aSLionel Sambuc
945f4a2713aSLionel Sambuc // Cast it to the right type (takes no arguments, returns a double) so we
946f4a2713aSLionel Sambuc // can call it as a native function.
947f4a2713aSLionel Sambuc double (*FP)() = (double (*)())(intptr_t)FPtr;
948f4a2713aSLionel Sambuc fprintf(stderr, "Evaluated to %f\n", FP());
949f4a2713aSLionel Sambuc }
950f4a2713aSLionel Sambuc } else {
951f4a2713aSLionel Sambuc // Skip token for error recovery.
952f4a2713aSLionel Sambuc getNextToken();
953f4a2713aSLionel Sambuc }
954f4a2713aSLionel Sambuc }
955f4a2713aSLionel Sambuc
956f4a2713aSLionel Sambuc /// top ::= definition | external | expression | ';'
MainLoop()957f4a2713aSLionel Sambuc static void MainLoop() {
958f4a2713aSLionel Sambuc while (1) {
959f4a2713aSLionel Sambuc fprintf(stderr, "ready> ");
960f4a2713aSLionel Sambuc switch (CurTok) {
961*0a6a1f1dSLionel Sambuc case tok_eof:
962*0a6a1f1dSLionel Sambuc return;
963*0a6a1f1dSLionel Sambuc case ';':
964*0a6a1f1dSLionel Sambuc getNextToken();
965*0a6a1f1dSLionel Sambuc break; // ignore top-level semicolons.
966*0a6a1f1dSLionel Sambuc case tok_def:
967*0a6a1f1dSLionel Sambuc HandleDefinition();
968*0a6a1f1dSLionel Sambuc break;
969*0a6a1f1dSLionel Sambuc case tok_extern:
970*0a6a1f1dSLionel Sambuc HandleExtern();
971*0a6a1f1dSLionel Sambuc break;
972*0a6a1f1dSLionel Sambuc default:
973*0a6a1f1dSLionel Sambuc HandleTopLevelExpression();
974*0a6a1f1dSLionel Sambuc break;
975f4a2713aSLionel Sambuc }
976f4a2713aSLionel Sambuc }
977f4a2713aSLionel Sambuc }
978f4a2713aSLionel Sambuc
979f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
980f4a2713aSLionel Sambuc // "Library" functions that can be "extern'd" from user code.
981f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
982f4a2713aSLionel Sambuc
983f4a2713aSLionel Sambuc /// putchard - putchar that takes a double and returns 0.
putchard(double X)984*0a6a1f1dSLionel Sambuc extern "C" double putchard(double X) {
985f4a2713aSLionel Sambuc putchar((char)X);
986f4a2713aSLionel Sambuc return 0;
987f4a2713aSLionel Sambuc }
988f4a2713aSLionel Sambuc
989f4a2713aSLionel Sambuc /// printd - printf that takes a double prints it as "%f\n", returning 0.
printd(double X)990*0a6a1f1dSLionel Sambuc extern "C" double printd(double X) {
991f4a2713aSLionel Sambuc printf("%f\n", X);
992f4a2713aSLionel Sambuc return 0;
993f4a2713aSLionel Sambuc }
994f4a2713aSLionel Sambuc
995f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
996f4a2713aSLionel Sambuc // Main driver code.
997f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
998f4a2713aSLionel Sambuc
main()999f4a2713aSLionel Sambuc int main() {
1000f4a2713aSLionel Sambuc InitializeNativeTarget();
1001*0a6a1f1dSLionel Sambuc InitializeNativeTargetAsmPrinter();
1002*0a6a1f1dSLionel Sambuc InitializeNativeTargetAsmParser();
1003f4a2713aSLionel Sambuc LLVMContext &Context = getGlobalContext();
1004f4a2713aSLionel Sambuc
1005f4a2713aSLionel Sambuc // Install standard binary operators.
1006f4a2713aSLionel Sambuc // 1 is lowest precedence.
1007f4a2713aSLionel Sambuc BinopPrecedence['<'] = 10;
1008f4a2713aSLionel Sambuc BinopPrecedence['+'] = 20;
1009f4a2713aSLionel Sambuc BinopPrecedence['-'] = 20;
1010f4a2713aSLionel Sambuc BinopPrecedence['*'] = 40; // highest.
1011f4a2713aSLionel Sambuc
1012f4a2713aSLionel Sambuc // Prime the first token.
1013f4a2713aSLionel Sambuc fprintf(stderr, "ready> ");
1014f4a2713aSLionel Sambuc getNextToken();
1015f4a2713aSLionel Sambuc
1016f4a2713aSLionel Sambuc // Make the module, which holds all the code.
1017*0a6a1f1dSLionel Sambuc std::unique_ptr<Module> Owner = make_unique<Module>("my cool jit", Context);
1018*0a6a1f1dSLionel Sambuc TheModule = Owner.get();
1019f4a2713aSLionel Sambuc
1020f4a2713aSLionel Sambuc // Create the JIT. This takes ownership of the module.
1021f4a2713aSLionel Sambuc std::string ErrStr;
1022*0a6a1f1dSLionel Sambuc TheExecutionEngine =
1023*0a6a1f1dSLionel Sambuc EngineBuilder(std::move(Owner))
1024*0a6a1f1dSLionel Sambuc .setErrorStr(&ErrStr)
1025*0a6a1f1dSLionel Sambuc .setMCJITMemoryManager(llvm::make_unique<SectionMemoryManager>())
1026*0a6a1f1dSLionel Sambuc .create();
1027f4a2713aSLionel Sambuc if (!TheExecutionEngine) {
1028f4a2713aSLionel Sambuc fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
1029f4a2713aSLionel Sambuc exit(1);
1030f4a2713aSLionel Sambuc }
1031f4a2713aSLionel Sambuc
1032f4a2713aSLionel Sambuc FunctionPassManager OurFPM(TheModule);
1033f4a2713aSLionel Sambuc
1034f4a2713aSLionel Sambuc // Set up the optimizer pipeline. Start with registering info about how the
1035f4a2713aSLionel Sambuc // target lays out data structures.
1036*0a6a1f1dSLionel Sambuc TheModule->setDataLayout(TheExecutionEngine->getDataLayout());
1037*0a6a1f1dSLionel Sambuc OurFPM.add(new DataLayoutPass());
1038f4a2713aSLionel Sambuc // Provide basic AliasAnalysis support for GVN.
1039f4a2713aSLionel Sambuc OurFPM.add(createBasicAliasAnalysisPass());
1040f4a2713aSLionel Sambuc // Do simple "peephole" optimizations and bit-twiddling optzns.
1041f4a2713aSLionel Sambuc OurFPM.add(createInstructionCombiningPass());
1042f4a2713aSLionel Sambuc // Reassociate expressions.
1043f4a2713aSLionel Sambuc OurFPM.add(createReassociatePass());
1044f4a2713aSLionel Sambuc // Eliminate Common SubExpressions.
1045f4a2713aSLionel Sambuc OurFPM.add(createGVNPass());
1046f4a2713aSLionel Sambuc // Simplify the control flow graph (deleting unreachable blocks, etc).
1047f4a2713aSLionel Sambuc OurFPM.add(createCFGSimplificationPass());
1048f4a2713aSLionel Sambuc
1049f4a2713aSLionel Sambuc OurFPM.doInitialization();
1050f4a2713aSLionel Sambuc
1051f4a2713aSLionel Sambuc // Set the global so the code gen can use this.
1052f4a2713aSLionel Sambuc TheFPM = &OurFPM;
1053f4a2713aSLionel Sambuc
1054f4a2713aSLionel Sambuc // Run the main "interpreter loop" now.
1055f4a2713aSLionel Sambuc MainLoop();
1056f4a2713aSLionel Sambuc
1057f4a2713aSLionel Sambuc TheFPM = 0;
1058f4a2713aSLionel Sambuc
1059f4a2713aSLionel Sambuc // Print out all of the generated code.
1060f4a2713aSLionel Sambuc TheModule->dump();
1061f4a2713aSLionel Sambuc
1062f4a2713aSLionel Sambuc return 0;
1063f4a2713aSLionel Sambuc }
1064