1 #include "llvm/Analysis/Passes.h"
2 #include "llvm/ExecutionEngine/ExecutionEngine.h"
3 #include "llvm/IR/DataLayout.h"
4 #include "llvm/IR/DerivedTypes.h"
5 #include "llvm/IR/IRBuilder.h"
6 #include "llvm/IR/LLVMContext.h"
7 #include "llvm/IR/Module.h"
8 #include "llvm/IR/Verifier.h"
9 #include "llvm/PassManager.h"
10 #include "llvm/Support/TargetSelect.h"
11 #include "llvm/Transforms/Scalar.h"
19 //===----------------------------------------------------------------------===//
21 //===----------------------------------------------------------------------===//
23 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
24 // of these for known things.
29 tok_def = -2, tok_extern = -3,
32 tok_identifier = -4, tok_number = -5,
35 tok_if = -6, tok_then = -7, tok_else = -8,
36 tok_for = -9, tok_in = -10,
39 tok_binary = -11, tok_unary = -12,
45 static std::string IdentifierStr; // Filled in if tok_identifier
46 static double NumVal; // Filled in if tok_number
48 /// gettok - Return the next token from standard input.
50 static int LastChar = ' ';
52 // Skip any whitespace.
53 while (isspace(LastChar))
56 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
57 IdentifierStr = LastChar;
58 while (isalnum((LastChar = getchar())))
59 IdentifierStr += LastChar;
61 if (IdentifierStr == "def") return tok_def;
62 if (IdentifierStr == "extern") return tok_extern;
63 if (IdentifierStr == "if") return tok_if;
64 if (IdentifierStr == "then") return tok_then;
65 if (IdentifierStr == "else") return tok_else;
66 if (IdentifierStr == "for") return tok_for;
67 if (IdentifierStr == "in") return tok_in;
68 if (IdentifierStr == "binary") return tok_binary;
69 if (IdentifierStr == "unary") return tok_unary;
70 if (IdentifierStr == "var") return tok_var;
71 return tok_identifier;
74 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
79 } while (isdigit(LastChar) || LastChar == '.');
81 NumVal = strtod(NumStr.c_str(), 0);
85 if (LastChar == '#') {
86 // Comment until end of line.
87 do LastChar = getchar();
88 while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
94 // Check for end of file. Don't eat the EOF.
98 // Otherwise, just return the character as its ascii value.
99 int ThisChar = LastChar;
100 LastChar = getchar();
104 //===----------------------------------------------------------------------===//
105 // Abstract Syntax Tree (aka Parse Tree)
106 //===----------------------------------------------------------------------===//
108 /// ExprAST - Base class for all expression nodes.
111 virtual ~ExprAST() {}
112 virtual Value *Codegen() = 0;
115 /// NumberExprAST - Expression class for numeric literals like "1.0".
116 class NumberExprAST : public ExprAST {
119 NumberExprAST(double val) : Val(val) {}
120 virtual Value *Codegen();
123 /// VariableExprAST - Expression class for referencing a variable, like "a".
124 class VariableExprAST : public ExprAST {
127 VariableExprAST(const std::string &name) : Name(name) {}
128 const std::string &getName() const { return Name; }
129 virtual Value *Codegen();
132 /// UnaryExprAST - Expression class for a unary operator.
133 class UnaryExprAST : public ExprAST {
137 UnaryExprAST(char opcode, ExprAST *operand)
138 : Opcode(opcode), Operand(operand) {}
139 virtual Value *Codegen();
142 /// BinaryExprAST - Expression class for a binary operator.
143 class BinaryExprAST : public ExprAST {
147 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
148 : Op(op), LHS(lhs), RHS(rhs) {}
149 virtual Value *Codegen();
152 /// CallExprAST - Expression class for function calls.
153 class CallExprAST : public ExprAST {
155 std::vector<ExprAST*> Args;
157 CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
158 : Callee(callee), Args(args) {}
159 virtual Value *Codegen();
162 /// IfExprAST - Expression class for if/then/else.
163 class IfExprAST : public ExprAST {
164 ExprAST *Cond, *Then, *Else;
166 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
167 : Cond(cond), Then(then), Else(_else) {}
168 virtual Value *Codegen();
171 /// ForExprAST - Expression class for for/in.
172 class ForExprAST : public ExprAST {
174 ExprAST *Start, *End, *Step, *Body;
176 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
177 ExprAST *step, ExprAST *body)
178 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
179 virtual Value *Codegen();
182 /// VarExprAST - Expression class for var/in
183 class VarExprAST : public ExprAST {
184 std::vector<std::pair<std::string, ExprAST*> > VarNames;
187 VarExprAST(const std::vector<std::pair<std::string, ExprAST*> > &varnames,
189 : VarNames(varnames), Body(body) {}
191 virtual Value *Codegen();
194 /// PrototypeAST - This class represents the "prototype" for a function,
195 /// which captures its argument names as well as if it is an operator.
198 std::vector<std::string> Args;
200 unsigned Precedence; // Precedence if a binary op.
202 PrototypeAST(const std::string &name, const std::vector<std::string> &args,
203 bool isoperator = false, unsigned prec = 0)
204 : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {}
206 bool isUnaryOp() const { return isOperator && Args.size() == 1; }
207 bool isBinaryOp() const { return isOperator && Args.size() == 2; }
209 char getOperatorName() const {
210 assert(isUnaryOp() || isBinaryOp());
211 return Name[Name.size()-1];
214 unsigned getBinaryPrecedence() const { return Precedence; }
218 void CreateArgumentAllocas(Function *F);
221 /// FunctionAST - This class represents a function definition itself.
226 FunctionAST(PrototypeAST *proto, ExprAST *body)
227 : Proto(proto), Body(body) {}
231 } // end anonymous namespace
233 //===----------------------------------------------------------------------===//
235 //===----------------------------------------------------------------------===//
237 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
238 /// token the parser is looking at. getNextToken reads another token from the
239 /// lexer and updates CurTok with its results.
241 static int getNextToken() {
242 return CurTok = gettok();
245 /// BinopPrecedence - This holds the precedence for each binary operator that is
247 static std::map<char, int> BinopPrecedence;
249 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
250 static int GetTokPrecedence() {
251 if (!isascii(CurTok))
254 // Make sure it's a declared binop.
255 int TokPrec = BinopPrecedence[CurTok];
256 if (TokPrec <= 0) return -1;
260 /// Error* - These are little helper functions for error handling.
261 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
262 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
263 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
265 static ExprAST *ParseExpression();
269 /// ::= identifier '(' expression* ')'
270 static ExprAST *ParseIdentifierExpr() {
271 std::string IdName = IdentifierStr;
273 getNextToken(); // eat identifier.
275 if (CurTok != '(') // Simple variable ref.
276 return new VariableExprAST(IdName);
279 getNextToken(); // eat (
280 std::vector<ExprAST*> Args;
283 ExprAST *Arg = ParseExpression();
287 if (CurTok == ')') break;
290 return Error("Expected ')' or ',' in argument list");
298 return new CallExprAST(IdName, Args);
301 /// numberexpr ::= number
302 static ExprAST *ParseNumberExpr() {
303 ExprAST *Result = new NumberExprAST(NumVal);
304 getNextToken(); // consume the number
308 /// parenexpr ::= '(' expression ')'
309 static ExprAST *ParseParenExpr() {
310 getNextToken(); // eat (.
311 ExprAST *V = ParseExpression();
315 return Error("expected ')'");
316 getNextToken(); // eat ).
320 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
321 static ExprAST *ParseIfExpr() {
322 getNextToken(); // eat the if.
325 ExprAST *Cond = ParseExpression();
328 if (CurTok != tok_then)
329 return Error("expected then");
330 getNextToken(); // eat the then
332 ExprAST *Then = ParseExpression();
333 if (Then == 0) return 0;
335 if (CurTok != tok_else)
336 return Error("expected else");
340 ExprAST *Else = ParseExpression();
343 return new IfExprAST(Cond, Then, Else);
346 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
347 static ExprAST *ParseForExpr() {
348 getNextToken(); // eat the for.
350 if (CurTok != tok_identifier)
351 return Error("expected identifier after for");
353 std::string IdName = IdentifierStr;
354 getNextToken(); // eat identifier.
357 return Error("expected '=' after for");
358 getNextToken(); // eat '='.
361 ExprAST *Start = ParseExpression();
362 if (Start == 0) return 0;
364 return Error("expected ',' after for start value");
367 ExprAST *End = ParseExpression();
368 if (End == 0) return 0;
370 // The step value is optional.
374 Step = ParseExpression();
375 if (Step == 0) return 0;
378 if (CurTok != tok_in)
379 return Error("expected 'in' after for");
380 getNextToken(); // eat 'in'.
382 ExprAST *Body = ParseExpression();
383 if (Body == 0) return 0;
385 return new ForExprAST(IdName, Start, End, Step, Body);
388 /// varexpr ::= 'var' identifier ('=' expression)?
389 // (',' identifier ('=' expression)?)* 'in' expression
390 static ExprAST *ParseVarExpr() {
391 getNextToken(); // eat the var.
393 std::vector<std::pair<std::string, ExprAST*> > VarNames;
395 // At least one variable name is required.
396 if (CurTok != tok_identifier)
397 return Error("expected identifier after var");
400 std::string Name = IdentifierStr;
401 getNextToken(); // eat identifier.
403 // Read the optional initializer.
406 getNextToken(); // eat the '='.
408 Init = ParseExpression();
409 if (Init == 0) return 0;
412 VarNames.push_back(std::make_pair(Name, Init));
414 // End of var list, exit loop.
415 if (CurTok != ',') break;
416 getNextToken(); // eat the ','.
418 if (CurTok != tok_identifier)
419 return Error("expected identifier list after var");
422 // At this point, we have to have 'in'.
423 if (CurTok != tok_in)
424 return Error("expected 'in' keyword after 'var'");
425 getNextToken(); // eat 'in'.
427 ExprAST *Body = ParseExpression();
428 if (Body == 0) return 0;
430 return new VarExprAST(VarNames, Body);
434 /// ::= identifierexpr
440 static ExprAST *ParsePrimary() {
442 default: return Error("unknown token when expecting an expression");
443 case tok_identifier: return ParseIdentifierExpr();
444 case tok_number: return ParseNumberExpr();
445 case '(': return ParseParenExpr();
446 case tok_if: return ParseIfExpr();
447 case tok_for: return ParseForExpr();
448 case tok_var: return ParseVarExpr();
455 static ExprAST *ParseUnary() {
456 // If the current token is not an operator, it must be a primary expr.
457 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
458 return ParsePrimary();
460 // If this is a unary operator, read it.
463 if (ExprAST *Operand = ParseUnary())
464 return new UnaryExprAST(Opc, Operand);
470 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
471 // If this is a binop, find its precedence.
473 int TokPrec = GetTokPrecedence();
475 // If this is a binop that binds at least as tightly as the current binop,
476 // consume it, otherwise we are done.
477 if (TokPrec < ExprPrec)
480 // Okay, we know this is a binop.
482 getNextToken(); // eat binop
484 // Parse the unary expression after the binary operator.
485 ExprAST *RHS = ParseUnary();
488 // If BinOp binds less tightly with RHS than the operator after RHS, let
489 // the pending operator take RHS as its LHS.
490 int NextPrec = GetTokPrecedence();
491 if (TokPrec < NextPrec) {
492 RHS = ParseBinOpRHS(TokPrec+1, RHS);
493 if (RHS == 0) return 0;
497 LHS = new BinaryExprAST(BinOp, LHS, RHS);
502 /// ::= unary binoprhs
504 static ExprAST *ParseExpression() {
505 ExprAST *LHS = ParseUnary();
508 return ParseBinOpRHS(0, LHS);
512 /// ::= id '(' id* ')'
513 /// ::= binary LETTER number? (id, id)
514 /// ::= unary LETTER (id)
515 static PrototypeAST *ParsePrototype() {
518 unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
519 unsigned BinaryPrecedence = 30;
523 return ErrorP("Expected function name in prototype");
525 FnName = IdentifierStr;
531 if (!isascii(CurTok))
532 return ErrorP("Expected unary operator");
534 FnName += (char)CurTok;
540 if (!isascii(CurTok))
541 return ErrorP("Expected binary operator");
543 FnName += (char)CurTok;
547 // Read the precedence if present.
548 if (CurTok == tok_number) {
549 if (NumVal < 1 || NumVal > 100)
550 return ErrorP("Invalid precedecnce: must be 1..100");
551 BinaryPrecedence = (unsigned)NumVal;
558 return ErrorP("Expected '(' in prototype");
560 std::vector<std::string> ArgNames;
561 while (getNextToken() == tok_identifier)
562 ArgNames.push_back(IdentifierStr);
564 return ErrorP("Expected ')' in prototype");
567 getNextToken(); // eat ')'.
569 // Verify right number of names for operator.
570 if (Kind && ArgNames.size() != Kind)
571 return ErrorP("Invalid number of operands for operator");
573 return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);
576 /// definition ::= 'def' prototype expression
577 static FunctionAST *ParseDefinition() {
578 getNextToken(); // eat def.
579 PrototypeAST *Proto = ParsePrototype();
580 if (Proto == 0) return 0;
582 if (ExprAST *E = ParseExpression())
583 return new FunctionAST(Proto, E);
587 /// toplevelexpr ::= expression
588 static FunctionAST *ParseTopLevelExpr() {
589 if (ExprAST *E = ParseExpression()) {
590 // Make an anonymous proto.
591 PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
592 return new FunctionAST(Proto, E);
597 /// external ::= 'extern' prototype
598 static PrototypeAST *ParseExtern() {
599 getNextToken(); // eat extern.
600 return ParsePrototype();
603 //===----------------------------------------------------------------------===//
605 //===----------------------------------------------------------------------===//
607 static Module *TheModule;
608 static IRBuilder<> Builder(getGlobalContext());
609 static std::map<std::string, AllocaInst*> NamedValues;
610 static FunctionPassManager *TheFPM;
612 Value *ErrorV(const char *Str) { Error(Str); return 0; }
614 /// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
615 /// the function. This is used for mutable variables etc.
616 static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,
617 const std::string &VarName) {
618 IRBuilder<> TmpB(&TheFunction->getEntryBlock(),
619 TheFunction->getEntryBlock().begin());
620 return TmpB.CreateAlloca(Type::getDoubleTy(getGlobalContext()), 0,
624 Value *NumberExprAST::Codegen() {
625 return ConstantFP::get(getGlobalContext(), APFloat(Val));
628 Value *VariableExprAST::Codegen() {
629 // Look this variable up in the function.
630 Value *V = NamedValues[Name];
631 if (V == 0) return ErrorV("Unknown variable name");
634 return Builder.CreateLoad(V, Name.c_str());
637 Value *UnaryExprAST::Codegen() {
638 Value *OperandV = Operand->Codegen();
639 if (OperandV == 0) return 0;
641 Function *F = TheModule->getFunction(std::string("unary")+Opcode);
643 return ErrorV("Unknown unary operator");
645 return Builder.CreateCall(F, OperandV, "unop");
648 Value *BinaryExprAST::Codegen() {
649 // Special case '=' because we don't want to emit the LHS as an expression.
651 // Assignment requires the LHS to be an identifier.
652 VariableExprAST *LHSE = dynamic_cast<VariableExprAST*>(LHS);
654 return ErrorV("destination of '=' must be a variable");
656 Value *Val = RHS->Codegen();
657 if (Val == 0) return 0;
660 Value *Variable = NamedValues[LHSE->getName()];
661 if (Variable == 0) return ErrorV("Unknown variable name");
663 Builder.CreateStore(Val, Variable);
667 Value *L = LHS->Codegen();
668 Value *R = RHS->Codegen();
669 if (L == 0 || R == 0) return 0;
672 case '+': return Builder.CreateFAdd(L, R, "addtmp");
673 case '-': return Builder.CreateFSub(L, R, "subtmp");
674 case '*': return Builder.CreateFMul(L, R, "multmp");
676 L = Builder.CreateFCmpULT(L, R, "cmptmp");
677 // Convert bool 0/1 to double 0.0 or 1.0
678 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
683 // If it wasn't a builtin binary operator, it must be a user defined one. Emit
685 Function *F = TheModule->getFunction(std::string("binary")+Op);
686 assert(F && "binary operator not found!");
688 Value *Ops[] = { L, R };
689 return Builder.CreateCall(F, Ops, "binop");
692 Value *CallExprAST::Codegen() {
693 // Look up the name in the global module table.
694 Function *CalleeF = TheModule->getFunction(Callee);
696 return ErrorV("Unknown function referenced");
698 // If argument mismatch error.
699 if (CalleeF->arg_size() != Args.size())
700 return ErrorV("Incorrect # arguments passed");
702 std::vector<Value*> ArgsV;
703 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
704 ArgsV.push_back(Args[i]->Codegen());
705 if (ArgsV.back() == 0) return 0;
708 return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
711 Value *IfExprAST::Codegen() {
712 Value *CondV = Cond->Codegen();
713 if (CondV == 0) return 0;
715 // Convert condition to a bool by comparing equal to 0.0.
716 CondV = Builder.CreateFCmpONE(CondV,
717 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
720 Function *TheFunction = Builder.GetInsertBlock()->getParent();
722 // Create blocks for the then and else cases. Insert the 'then' block at the
723 // end of the function.
724 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
725 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
726 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
728 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
731 Builder.SetInsertPoint(ThenBB);
733 Value *ThenV = Then->Codegen();
734 if (ThenV == 0) return 0;
736 Builder.CreateBr(MergeBB);
737 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
738 ThenBB = Builder.GetInsertBlock();
741 TheFunction->getBasicBlockList().push_back(ElseBB);
742 Builder.SetInsertPoint(ElseBB);
744 Value *ElseV = Else->Codegen();
745 if (ElseV == 0) return 0;
747 Builder.CreateBr(MergeBB);
748 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
749 ElseBB = Builder.GetInsertBlock();
752 TheFunction->getBasicBlockList().push_back(MergeBB);
753 Builder.SetInsertPoint(MergeBB);
754 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2,
757 PN->addIncoming(ThenV, ThenBB);
758 PN->addIncoming(ElseV, ElseBB);
762 Value *ForExprAST::Codegen() {
764 // var = alloca double
767 // store start -> var
778 // nextvar = curvar + step
779 // store nextvar -> var
780 // br endcond, loop, endloop
783 Function *TheFunction = Builder.GetInsertBlock()->getParent();
785 // Create an alloca for the variable in the entry block.
786 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
788 // Emit the start code first, without 'variable' in scope.
789 Value *StartVal = Start->Codegen();
790 if (StartVal == 0) return 0;
792 // Store the value into the alloca.
793 Builder.CreateStore(StartVal, Alloca);
795 // Make the new basic block for the loop header, inserting after current
797 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
799 // Insert an explicit fall through from the current block to the LoopBB.
800 Builder.CreateBr(LoopBB);
802 // Start insertion in LoopBB.
803 Builder.SetInsertPoint(LoopBB);
805 // Within the loop, the variable is defined equal to the PHI node. If it
806 // shadows an existing variable, we have to restore it, so save it now.
807 AllocaInst *OldVal = NamedValues[VarName];
808 NamedValues[VarName] = Alloca;
810 // Emit the body of the loop. This, like any other expr, can change the
811 // current BB. Note that we ignore the value computed by the body, but don't
813 if (Body->Codegen() == 0)
816 // Emit the step value.
819 StepVal = Step->Codegen();
820 if (StepVal == 0) return 0;
822 // If not specified, use 1.0.
823 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
826 // Compute the end condition.
827 Value *EndCond = End->Codegen();
828 if (EndCond == 0) return EndCond;
830 // Reload, increment, and restore the alloca. This handles the case where
831 // the body of the loop mutates the variable.
832 Value *CurVar = Builder.CreateLoad(Alloca, VarName.c_str());
833 Value *NextVar = Builder.CreateFAdd(CurVar, StepVal, "nextvar");
834 Builder.CreateStore(NextVar, Alloca);
836 // Convert condition to a bool by comparing equal to 0.0.
837 EndCond = Builder.CreateFCmpONE(EndCond,
838 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
841 // Create the "after loop" block and insert it.
842 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
844 // Insert the conditional branch into the end of LoopEndBB.
845 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
847 // Any new code will be inserted in AfterBB.
848 Builder.SetInsertPoint(AfterBB);
850 // Restore the unshadowed variable.
852 NamedValues[VarName] = OldVal;
854 NamedValues.erase(VarName);
857 // for expr always returns 0.0.
858 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
861 Value *VarExprAST::Codegen() {
862 std::vector<AllocaInst *> OldBindings;
864 Function *TheFunction = Builder.GetInsertBlock()->getParent();
866 // Register all variables and emit their initializer.
867 for (unsigned i = 0, e = VarNames.size(); i != e; ++i) {
868 const std::string &VarName = VarNames[i].first;
869 ExprAST *Init = VarNames[i].second;
871 // Emit the initializer before adding the variable to scope, this prevents
872 // the initializer from referencing the variable itself, and permits stuff
875 // var a = a in ... # refers to outer 'a'.
878 InitVal = Init->Codegen();
879 if (InitVal == 0) return 0;
880 } else { // If not specified, use 0.0.
881 InitVal = ConstantFP::get(getGlobalContext(), APFloat(0.0));
884 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
885 Builder.CreateStore(InitVal, Alloca);
887 // Remember the old variable binding so that we can restore the binding when
889 OldBindings.push_back(NamedValues[VarName]);
891 // Remember this binding.
892 NamedValues[VarName] = Alloca;
895 // Codegen the body, now that all vars are in scope.
896 Value *BodyVal = Body->Codegen();
897 if (BodyVal == 0) return 0;
899 // Pop all our variables from scope.
900 for (unsigned i = 0, e = VarNames.size(); i != e; ++i)
901 NamedValues[VarNames[i].first] = OldBindings[i];
903 // Return the body computation.
907 Function *PrototypeAST::Codegen() {
908 // Make the function type: double(double,double) etc.
909 std::vector<Type*> Doubles(Args.size(),
910 Type::getDoubleTy(getGlobalContext()));
911 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
914 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
916 // If F conflicted, there was already something named 'Name'. If it has a
917 // body, don't allow redefinition or reextern.
918 if (F->getName() != Name) {
919 // Delete the one we just made and get the existing one.
920 F->eraseFromParent();
921 F = TheModule->getFunction(Name);
923 // If F already has a body, reject this.
925 ErrorF("redefinition of function");
929 // If F took a different number of args, reject.
930 if (F->arg_size() != Args.size()) {
931 ErrorF("redefinition of function with different # args");
936 // Set names for all arguments.
938 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
940 AI->setName(Args[Idx]);
945 /// CreateArgumentAllocas - Create an alloca for each argument and register the
946 /// argument in the symbol table so that references to it will succeed.
947 void PrototypeAST::CreateArgumentAllocas(Function *F) {
948 Function::arg_iterator AI = F->arg_begin();
949 for (unsigned Idx = 0, e = Args.size(); Idx != e; ++Idx, ++AI) {
950 // Create an alloca for this variable.
951 AllocaInst *Alloca = CreateEntryBlockAlloca(F, Args[Idx]);
953 // Store the initial value into the alloca.
954 Builder.CreateStore(AI, Alloca);
956 // Add arguments to variable symbol table.
957 NamedValues[Args[Idx]] = Alloca;
961 Function *FunctionAST::Codegen() {
964 Function *TheFunction = Proto->Codegen();
965 if (TheFunction == 0)
968 // If this is an operator, install it.
969 if (Proto->isBinaryOp())
970 BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence();
972 // Create a new basic block to start insertion into.
973 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
974 Builder.SetInsertPoint(BB);
976 // Add all arguments to the symbol table and create their allocas.
977 Proto->CreateArgumentAllocas(TheFunction);
979 if (Value *RetVal = Body->Codegen()) {
980 // Finish off the function.
981 Builder.CreateRet(RetVal);
983 // Validate the generated code, checking for consistency.
984 verifyFunction(*TheFunction);
986 // Optimize the function.
987 TheFPM->run(*TheFunction);
992 // Error reading body, remove function.
993 TheFunction->eraseFromParent();
995 if (Proto->isBinaryOp())
996 BinopPrecedence.erase(Proto->getOperatorName());
1000 //===----------------------------------------------------------------------===//
1001 // Top-Level parsing and JIT Driver
1002 //===----------------------------------------------------------------------===//
1004 static ExecutionEngine *TheExecutionEngine;
1006 static void HandleDefinition() {
1007 if (FunctionAST *F = ParseDefinition()) {
1008 if (Function *LF = F->Codegen()) {
1009 fprintf(stderr, "Read function definition:");
1013 // Skip token for error recovery.
1018 static void HandleExtern() {
1019 if (PrototypeAST *P = ParseExtern()) {
1020 if (Function *F = P->Codegen()) {
1021 fprintf(stderr, "Read extern: ");
1025 // Skip token for error recovery.
1030 static void HandleTopLevelExpression() {
1031 // Evaluate a top-level expression into an anonymous function.
1032 if (FunctionAST *F = ParseTopLevelExpr()) {
1033 if (Function *LF = F->Codegen()) {
1034 // JIT the function, returning a function pointer.
1035 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
1037 // Cast it to the right type (takes no arguments, returns a double) so we
1038 // can call it as a native function.
1039 double (*FP)() = (double (*)())(intptr_t)FPtr;
1040 fprintf(stderr, "Evaluated to %f\n", FP());
1043 // Skip token for error recovery.
1048 /// top ::= definition | external | expression | ';'
1049 static void MainLoop() {
1051 fprintf(stderr, "ready> ");
1053 case tok_eof: return;
1054 case ';': getNextToken(); break; // ignore top-level semicolons.
1055 case tok_def: HandleDefinition(); break;
1056 case tok_extern: HandleExtern(); break;
1057 default: HandleTopLevelExpression(); break;
1062 //===----------------------------------------------------------------------===//
1063 // "Library" functions that can be "extern'd" from user code.
1064 //===----------------------------------------------------------------------===//
1066 /// putchard - putchar that takes a double and returns 0.
1068 double putchard(double X) {
1073 /// printd - printf that takes a double prints it as "%f\n", returning 0.
1075 double printd(double X) {
1080 //===----------------------------------------------------------------------===//
1081 // Main driver code.
1082 //===----------------------------------------------------------------------===//
1085 InitializeNativeTarget();
1086 LLVMContext &Context = getGlobalContext();
1088 // Install standard binary operators.
1089 // 1 is lowest precedence.
1090 BinopPrecedence['='] = 2;
1091 BinopPrecedence['<'] = 10;
1092 BinopPrecedence['+'] = 20;
1093 BinopPrecedence['-'] = 20;
1094 BinopPrecedence['*'] = 40; // highest.
1096 // Prime the first token.
1097 fprintf(stderr, "ready> ");
1100 // Make the module, which holds all the code.
1101 TheModule = new Module("my cool jit", Context);
1103 // Create the JIT. This takes ownership of the module.
1105 TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create();
1106 if (!TheExecutionEngine) {
1107 fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
1111 FunctionPassManager OurFPM(TheModule);
1113 // Set up the optimizer pipeline. Start with registering info about how the
1114 // target lays out data structures.
1115 TheModule->setDataLayout(TheExecutionEngine->getDataLayout());
1116 OurFPM.add(new DataLayoutPass(TheModule));
1117 // Provide basic AliasAnalysis support for GVN.
1118 OurFPM.add(createBasicAliasAnalysisPass());
1119 // Promote allocas to registers.
1120 OurFPM.add(createPromoteMemoryToRegisterPass());
1121 // Do simple "peephole" optimizations and bit-twiddling optzns.
1122 OurFPM.add(createInstructionCombiningPass());
1123 // Reassociate expressions.
1124 OurFPM.add(createReassociatePass());
1125 // Eliminate Common SubExpressions.
1126 OurFPM.add(createGVNPass());
1127 // Simplify the control flow graph (deleting unreachable blocks, etc).
1128 OurFPM.add(createCFGSimplificationPass());
1130 OurFPM.doInitialization();
1132 // Set the global so the code gen can use this.
1135 // Run the main "interpreter loop" now.
1140 // Print out all of the generated code.