1 #define MINIMAL_STDERR_OUTPUT
3 #include "llvm/Analysis/Passes.h"
4 #include "llvm/ExecutionEngine/ExecutionEngine.h"
5 #include "llvm/IR/DataLayout.h"
6 #include "llvm/IR/DerivedTypes.h"
7 #include "llvm/IR/IRBuilder.h"
8 #include "llvm/IR/LLVMContext.h"
9 #include "llvm/IR/LegacyPassManager.h"
10 #include "llvm/IR/Module.h"
11 #include "llvm/IR/Verifier.h"
12 #include "llvm/Support/TargetSelect.h"
13 #include "llvm/Transforms/Scalar.h"
22 //===----------------------------------------------------------------------===//
24 //===----------------------------------------------------------------------===//
26 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
27 // of these for known things.
32 tok_def
= -2, tok_extern
= -3,
35 tok_identifier
= -4, tok_number
= -5,
38 tok_if
= -6, tok_then
= -7, tok_else
= -8,
39 tok_for
= -9, tok_in
= -10,
42 tok_binary
= -11, tok_unary
= -12,
48 static std::string IdentifierStr
; // Filled in if tok_identifier
49 static double NumVal
; // Filled in if tok_number
51 /// gettok - Return the next token from standard input.
53 static int LastChar
= ' ';
55 // Skip any whitespace.
56 while (isspace(LastChar
))
59 if (isalpha(LastChar
)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
60 IdentifierStr
= LastChar
;
61 while (isalnum((LastChar
= getchar())))
62 IdentifierStr
+= LastChar
;
64 if (IdentifierStr
== "def") return tok_def
;
65 if (IdentifierStr
== "extern") return tok_extern
;
66 if (IdentifierStr
== "if") return tok_if
;
67 if (IdentifierStr
== "then") return tok_then
;
68 if (IdentifierStr
== "else") return tok_else
;
69 if (IdentifierStr
== "for") return tok_for
;
70 if (IdentifierStr
== "in") return tok_in
;
71 if (IdentifierStr
== "binary") return tok_binary
;
72 if (IdentifierStr
== "unary") return tok_unary
;
73 if (IdentifierStr
== "var") return tok_var
;
74 return tok_identifier
;
77 if (isdigit(LastChar
) || LastChar
== '.') { // Number: [0-9.]+
82 } while (isdigit(LastChar
) || LastChar
== '.');
84 NumVal
= strtod(NumStr
.c_str(), 0);
88 if (LastChar
== '#') {
89 // Comment until end of line.
90 do LastChar
= getchar();
91 while (LastChar
!= EOF
&& LastChar
!= '\n' && LastChar
!= '\r');
97 // Check for end of file. Don't eat the EOF.
101 // Otherwise, just return the character as its ascii value.
102 int ThisChar
= LastChar
;
103 LastChar
= getchar();
107 //===----------------------------------------------------------------------===//
108 // Abstract Syntax Tree (aka Parse Tree)
109 //===----------------------------------------------------------------------===//
111 /// ExprAST - Base class for all expression nodes.
114 virtual ~ExprAST() {}
115 virtual Value
*Codegen() = 0;
118 /// NumberExprAST - Expression class for numeric literals like "1.0".
119 class NumberExprAST
: public ExprAST
{
122 NumberExprAST(double val
) : Val(val
) {}
123 virtual Value
*Codegen();
126 /// VariableExprAST - Expression class for referencing a variable, like "a".
127 class VariableExprAST
: public ExprAST
{
130 VariableExprAST(const std::string
&name
) : Name(name
) {}
131 const std::string
&getName() const { return Name
; }
132 virtual Value
*Codegen();
135 /// UnaryExprAST - Expression class for a unary operator.
136 class UnaryExprAST
: public ExprAST
{
140 UnaryExprAST(char opcode
, ExprAST
*operand
)
141 : Opcode(opcode
), Operand(operand
) {}
142 virtual Value
*Codegen();
145 /// BinaryExprAST - Expression class for a binary operator.
146 class BinaryExprAST
: public ExprAST
{
150 BinaryExprAST(char op
, ExprAST
*lhs
, ExprAST
*rhs
)
151 : Op(op
), LHS(lhs
), RHS(rhs
) {}
152 virtual Value
*Codegen();
155 /// CallExprAST - Expression class for function calls.
156 class CallExprAST
: public ExprAST
{
158 std::vector
<ExprAST
*> Args
;
160 CallExprAST(const std::string
&callee
, std::vector
<ExprAST
*> &args
)
161 : Callee(callee
), Args(args
) {}
162 virtual Value
*Codegen();
165 /// IfExprAST - Expression class for if/then/else.
166 class IfExprAST
: public ExprAST
{
167 ExprAST
*Cond
, *Then
, *Else
;
169 IfExprAST(ExprAST
*cond
, ExprAST
*then
, ExprAST
*_else
)
170 : Cond(cond
), Then(then
), Else(_else
) {}
171 virtual Value
*Codegen();
174 /// ForExprAST - Expression class for for/in.
175 class ForExprAST
: public ExprAST
{
177 ExprAST
*Start
, *End
, *Step
, *Body
;
179 ForExprAST(const std::string
&varname
, ExprAST
*start
, ExprAST
*end
,
180 ExprAST
*step
, ExprAST
*body
)
181 : VarName(varname
), Start(start
), End(end
), Step(step
), Body(body
) {}
182 virtual Value
*Codegen();
185 /// VarExprAST - Expression class for var/in
186 class VarExprAST
: public ExprAST
{
187 std::vector
<std::pair
<std::string
, ExprAST
*> > VarNames
;
190 VarExprAST(const std::vector
<std::pair
<std::string
, ExprAST
*> > &varnames
,
192 : VarNames(varnames
), Body(body
) {}
194 virtual Value
*Codegen();
197 /// PrototypeAST - This class represents the "prototype" for a function,
198 /// which captures its argument names as well as if it is an operator.
201 std::vector
<std::string
> Args
;
203 unsigned Precedence
; // Precedence if a binary op.
205 PrototypeAST(const std::string
&name
, const std::vector
<std::string
> &args
,
206 bool isoperator
= false, unsigned prec
= 0)
207 : Name(name
), Args(args
), isOperator(isoperator
), Precedence(prec
) {}
209 bool isUnaryOp() const { return isOperator
&& Args
.size() == 1; }
210 bool isBinaryOp() const { return isOperator
&& Args
.size() == 2; }
212 char getOperatorName() const {
213 assert(isUnaryOp() || isBinaryOp());
214 return Name
[Name
.size()-1];
217 unsigned getBinaryPrecedence() const { return Precedence
; }
221 void CreateArgumentAllocas(Function
*F
);
224 /// FunctionAST - This class represents a function definition itself.
229 FunctionAST(PrototypeAST
*proto
, ExprAST
*body
)
230 : Proto(proto
), Body(body
) {}
235 //===----------------------------------------------------------------------===//
237 //===----------------------------------------------------------------------===//
239 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
240 /// token the parser is looking at. getNextToken reads another token from the
241 /// lexer and updates CurTok with its results.
243 static int getNextToken() {
244 return CurTok
= gettok();
247 /// BinopPrecedence - This holds the precedence for each binary operator that is
249 static std::map
<char, int> BinopPrecedence
;
251 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
252 static int GetTokPrecedence() {
253 if (!isascii(CurTok
))
256 // Make sure it's a declared binop.
257 int TokPrec
= BinopPrecedence
[CurTok
];
258 if (TokPrec
<= 0) return -1;
262 /// Error* - These are little helper functions for error handling.
263 ExprAST
*Error(const char *Str
) { fprintf(stderr
, "Error: %s\n", Str
);return 0;}
264 PrototypeAST
*ErrorP(const char *Str
) { Error(Str
); return 0; }
265 FunctionAST
*ErrorF(const char *Str
) { Error(Str
); return 0; }
267 static ExprAST
*ParseExpression();
271 /// ::= identifier '(' expression* ')'
272 static ExprAST
*ParseIdentifierExpr() {
273 std::string IdName
= IdentifierStr
;
275 getNextToken(); // eat identifier.
277 if (CurTok
!= '(') // Simple variable ref.
278 return new VariableExprAST(IdName
);
281 getNextToken(); // eat (
282 std::vector
<ExprAST
*> Args
;
285 ExprAST
*Arg
= ParseExpression();
289 if (CurTok
== ')') break;
292 return Error("Expected ')' or ',' in argument list");
300 return new CallExprAST(IdName
, Args
);
303 /// numberexpr ::= number
304 static ExprAST
*ParseNumberExpr() {
305 ExprAST
*Result
= new NumberExprAST(NumVal
);
306 getNextToken(); // consume the number
310 /// parenexpr ::= '(' expression ')'
311 static ExprAST
*ParseParenExpr() {
312 getNextToken(); // eat (.
313 ExprAST
*V
= ParseExpression();
317 return Error("expected ')'");
318 getNextToken(); // eat ).
322 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
323 static ExprAST
*ParseIfExpr() {
324 getNextToken(); // eat the if.
327 ExprAST
*Cond
= ParseExpression();
330 if (CurTok
!= tok_then
)
331 return Error("expected then");
332 getNextToken(); // eat the then
334 ExprAST
*Then
= ParseExpression();
335 if (Then
== 0) return 0;
337 if (CurTok
!= tok_else
)
338 return Error("expected else");
342 ExprAST
*Else
= ParseExpression();
345 return new IfExprAST(Cond
, Then
, Else
);
348 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
349 static ExprAST
*ParseForExpr() {
350 getNextToken(); // eat the for.
352 if (CurTok
!= tok_identifier
)
353 return Error("expected identifier after for");
355 std::string IdName
= IdentifierStr
;
356 getNextToken(); // eat identifier.
359 return Error("expected '=' after for");
360 getNextToken(); // eat '='.
363 ExprAST
*Start
= ParseExpression();
364 if (Start
== 0) return 0;
366 return Error("expected ',' after for start value");
369 ExprAST
*End
= ParseExpression();
370 if (End
== 0) return 0;
372 // The step value is optional.
376 Step
= ParseExpression();
377 if (Step
== 0) return 0;
380 if (CurTok
!= tok_in
)
381 return Error("expected 'in' after for");
382 getNextToken(); // eat 'in'.
384 ExprAST
*Body
= ParseExpression();
385 if (Body
== 0) return 0;
387 return new ForExprAST(IdName
, Start
, End
, Step
, Body
);
390 /// varexpr ::= 'var' identifier ('=' expression)?
391 // (',' identifier ('=' expression)?)* 'in' expression
392 static ExprAST
*ParseVarExpr() {
393 getNextToken(); // eat the var.
395 std::vector
<std::pair
<std::string
, ExprAST
*> > VarNames
;
397 // At least one variable name is required.
398 if (CurTok
!= tok_identifier
)
399 return Error("expected identifier after var");
402 std::string Name
= IdentifierStr
;
403 getNextToken(); // eat identifier.
405 // Read the optional initializer.
408 getNextToken(); // eat the '='.
410 Init
= ParseExpression();
411 if (Init
== 0) return 0;
414 VarNames
.push_back(std::make_pair(Name
, Init
));
416 // End of var list, exit loop.
417 if (CurTok
!= ',') break;
418 getNextToken(); // eat the ','.
420 if (CurTok
!= tok_identifier
)
421 return Error("expected identifier list after var");
424 // At this point, we have to have 'in'.
425 if (CurTok
!= tok_in
)
426 return Error("expected 'in' keyword after 'var'");
427 getNextToken(); // eat 'in'.
429 ExprAST
*Body
= ParseExpression();
430 if (Body
== 0) return 0;
432 return new VarExprAST(VarNames
, Body
);
436 /// ::= identifierexpr
442 static ExprAST
*ParsePrimary() {
444 default: return Error("unknown token when expecting an expression");
445 case tok_identifier
: return ParseIdentifierExpr();
446 case tok_number
: return ParseNumberExpr();
447 case '(': return ParseParenExpr();
448 case tok_if
: return ParseIfExpr();
449 case tok_for
: return ParseForExpr();
450 case tok_var
: return ParseVarExpr();
457 static ExprAST
*ParseUnary() {
458 // If the current token is not an operator, it must be a primary expr.
459 if (!isascii(CurTok
) || CurTok
== '(' || CurTok
== ',')
460 return ParsePrimary();
462 // If this is a unary operator, read it.
465 if (ExprAST
*Operand
= ParseUnary())
466 return new UnaryExprAST(Opc
, Operand
);
472 static ExprAST
*ParseBinOpRHS(int ExprPrec
, ExprAST
*LHS
) {
473 // If this is a binop, find its precedence.
475 int TokPrec
= GetTokPrecedence();
477 // If this is a binop that binds at least as tightly as the current binop,
478 // consume it, otherwise we are done.
479 if (TokPrec
< ExprPrec
)
482 // Okay, we know this is a binop.
484 getNextToken(); // eat binop
486 // Parse the unary expression after the binary operator.
487 ExprAST
*RHS
= ParseUnary();
490 // If BinOp binds less tightly with RHS than the operator after RHS, let
491 // the pending operator take RHS as its LHS.
492 int NextPrec
= GetTokPrecedence();
493 if (TokPrec
< NextPrec
) {
494 RHS
= ParseBinOpRHS(TokPrec
+1, RHS
);
495 if (RHS
== 0) return 0;
499 LHS
= new BinaryExprAST(BinOp
, LHS
, RHS
);
504 /// ::= unary binoprhs
506 static ExprAST
*ParseExpression() {
507 ExprAST
*LHS
= ParseUnary();
510 return ParseBinOpRHS(0, LHS
);
514 /// ::= id '(' id* ')'
515 /// ::= binary LETTER number? (id, id)
516 /// ::= unary LETTER (id)
517 static PrototypeAST
*ParsePrototype() {
520 unsigned Kind
= 0; // 0 = identifier, 1 = unary, 2 = binary.
521 unsigned BinaryPrecedence
= 30;
525 return ErrorP("Expected function name in prototype");
527 FnName
= IdentifierStr
;
533 if (!isascii(CurTok
))
534 return ErrorP("Expected unary operator");
536 FnName
+= (char)CurTok
;
542 if (!isascii(CurTok
))
543 return ErrorP("Expected binary operator");
545 FnName
+= (char)CurTok
;
549 // Read the precedence if present.
550 if (CurTok
== tok_number
) {
551 if (NumVal
< 1 || NumVal
> 100)
552 return ErrorP("Invalid precedecnce: must be 1..100");
553 BinaryPrecedence
= (unsigned)NumVal
;
560 return ErrorP("Expected '(' in prototype");
562 std::vector
<std::string
> ArgNames
;
563 while (getNextToken() == tok_identifier
)
564 ArgNames
.push_back(IdentifierStr
);
566 return ErrorP("Expected ')' in prototype");
569 getNextToken(); // eat ')'.
571 // Verify right number of names for operator.
572 if (Kind
&& ArgNames
.size() != Kind
)
573 return ErrorP("Invalid number of operands for operator");
575 return new PrototypeAST(FnName
, ArgNames
, Kind
!= 0, BinaryPrecedence
);
578 /// definition ::= 'def' prototype expression
579 static FunctionAST
*ParseDefinition() {
580 getNextToken(); // eat def.
581 PrototypeAST
*Proto
= ParsePrototype();
582 if (Proto
== 0) return 0;
584 if (ExprAST
*E
= ParseExpression())
585 return new FunctionAST(Proto
, E
);
589 /// toplevelexpr ::= expression
590 static FunctionAST
*ParseTopLevelExpr() {
591 if (ExprAST
*E
= ParseExpression()) {
592 // Make an anonymous proto.
593 PrototypeAST
*Proto
= new PrototypeAST("", std::vector
<std::string
>());
594 return new FunctionAST(Proto
, E
);
599 /// external ::= 'extern' prototype
600 static PrototypeAST
*ParseExtern() {
601 getNextToken(); // eat extern.
602 return ParsePrototype();
605 //===----------------------------------------------------------------------===//
607 //===----------------------------------------------------------------------===//
609 static Module
*TheModule
;
610 static FunctionPassManager
*TheFPM
;
611 static LLVMContext TheContext
;
612 static IRBuilder
<> Builder(TheContext
);
613 static std::map
<std::string
, AllocaInst
*> NamedValues
;
615 Value
*ErrorV(const char *Str
) { Error(Str
); return 0; }
617 /// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
618 /// the function. This is used for mutable variables etc.
619 static AllocaInst
*CreateEntryBlockAlloca(Function
*TheFunction
,
620 const std::string
&VarName
) {
621 IRBuilder
<> TmpB(&TheFunction
->getEntryBlock(),
622 TheFunction
->getEntryBlock().begin());
623 return TmpB
.CreateAlloca(Type::getDoubleTy(TheContext
), 0, VarName
.c_str());
626 Value
*NumberExprAST::Codegen() {
627 return ConstantFP::get(TheContext
, APFloat(Val
));
630 Value
*VariableExprAST::Codegen() {
631 // Look this variable up in the function.
632 Value
*V
= NamedValues
[Name
];
633 if (V
== 0) return ErrorV("Unknown variable name");
636 return Builder
.CreateLoad(V
, Name
.c_str());
639 Value
*UnaryExprAST::Codegen() {
640 Value
*OperandV
= Operand
->Codegen();
641 if (OperandV
== 0) return 0;
643 Function
*F
= TheHelper
->getFunction(MakeLegalFunctionName(std::string("unary")+Opcode
));
645 Function
*F
= TheModule
->getFunction(std::string("unary")+Opcode
);
648 return ErrorV("Unknown unary operator");
650 return Builder
.CreateCall(F
, OperandV
, "unop");
653 Value
*BinaryExprAST::Codegen() {
654 // Special case '=' because we don't want to emit the LHS as an expression.
656 // Assignment requires the LHS to be an identifier.
657 VariableExprAST
*LHSE
= dynamic_cast<VariableExprAST
*>(LHS
);
659 return ErrorV("destination of '=' must be a variable");
661 Value
*Val
= RHS
->Codegen();
662 if (Val
== 0) return 0;
665 Value
*Variable
= NamedValues
[LHSE
->getName()];
666 if (Variable
== 0) return ErrorV("Unknown variable name");
668 Builder
.CreateStore(Val
, Variable
);
672 Value
*L
= LHS
->Codegen();
673 Value
*R
= RHS
->Codegen();
674 if (L
== 0 || R
== 0) return 0;
677 case '+': return Builder
.CreateFAdd(L
, R
, "addtmp");
678 case '-': return Builder
.CreateFSub(L
, R
, "subtmp");
679 case '*': return Builder
.CreateFMul(L
, R
, "multmp");
680 case '/': return Builder
.CreateFDiv(L
, R
, "divtmp");
682 L
= Builder
.CreateFCmpULT(L
, R
, "cmptmp");
683 // Convert bool 0/1 to double 0.0 or 1.0
684 return Builder
.CreateUIToFP(L
, Type::getDoubleTy(TheContext
), "booltmp");
688 // If it wasn't a builtin binary operator, it must be a user defined one. Emit
690 Function
*F
= TheModule
->getFunction(std::string("binary")+Op
);
691 assert(F
&& "binary operator not found!");
693 Value
*Ops
[] = { L
, R
};
694 return Builder
.CreateCall(F
, Ops
, "binop");
697 Value
*CallExprAST::Codegen() {
698 // Look up the name in the global module table.
699 Function
*CalleeF
= TheModule
->getFunction(Callee
);
702 sprintf(error_str
, "Unknown function referenced %s", Callee
.c_str());
703 return ErrorV(error_str
);
706 // If argument mismatch error.
707 if (CalleeF
->arg_size() != Args
.size())
708 return ErrorV("Incorrect # arguments passed");
710 std::vector
<Value
*> ArgsV
;
711 for (unsigned i
= 0, e
= Args
.size(); i
!= e
; ++i
) {
712 ArgsV
.push_back(Args
[i
]->Codegen());
713 if (ArgsV
.back() == 0) return 0;
716 return Builder
.CreateCall(CalleeF
, ArgsV
, "calltmp");
719 Value
*IfExprAST::Codegen() {
720 Value
*CondV
= Cond
->Codegen();
721 if (CondV
== 0) return 0;
723 // Convert condition to a bool by comparing equal to 0.0.
724 CondV
= Builder
.CreateFCmpONE(
725 CondV
, ConstantFP::get(TheContext
, APFloat(0.0)), "ifcond");
727 Function
*TheFunction
= Builder
.GetInsertBlock()->getParent();
729 // Create blocks for the then and else cases. Insert the 'then' block at the
730 // end of the function.
731 BasicBlock
*ThenBB
= BasicBlock::Create(TheContext
, "then", TheFunction
);
732 BasicBlock
*ElseBB
= BasicBlock::Create(TheContext
, "else");
733 BasicBlock
*MergeBB
= BasicBlock::Create(TheContext
, "ifcont");
735 Builder
.CreateCondBr(CondV
, ThenBB
, ElseBB
);
738 Builder
.SetInsertPoint(ThenBB
);
740 Value
*ThenV
= Then
->Codegen();
741 if (ThenV
== 0) return 0;
743 Builder
.CreateBr(MergeBB
);
744 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
745 ThenBB
= Builder
.GetInsertBlock();
748 TheFunction
->getBasicBlockList().push_back(ElseBB
);
749 Builder
.SetInsertPoint(ElseBB
);
751 Value
*ElseV
= Else
->Codegen();
752 if (ElseV
== 0) return 0;
754 Builder
.CreateBr(MergeBB
);
755 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
756 ElseBB
= Builder
.GetInsertBlock();
759 TheFunction
->getBasicBlockList().push_back(MergeBB
);
760 Builder
.SetInsertPoint(MergeBB
);
761 PHINode
*PN
= Builder
.CreatePHI(Type::getDoubleTy(TheContext
), 2, "iftmp");
763 PN
->addIncoming(ThenV
, ThenBB
);
764 PN
->addIncoming(ElseV
, ElseBB
);
768 Value
*ForExprAST::Codegen() {
770 // var = alloca double
773 // store start -> var
784 // nextvar = curvar + step
785 // store nextvar -> var
786 // br endcond, loop, endloop
789 Function
*TheFunction
= Builder
.GetInsertBlock()->getParent();
791 // Create an alloca for the variable in the entry block.
792 AllocaInst
*Alloca
= CreateEntryBlockAlloca(TheFunction
, VarName
);
794 // Emit the start code first, without 'variable' in scope.
795 Value
*StartVal
= Start
->Codegen();
796 if (StartVal
== 0) return 0;
798 // Store the value into the alloca.
799 Builder
.CreateStore(StartVal
, Alloca
);
801 // Make the new basic block for the loop header, inserting after current
803 BasicBlock
*LoopBB
= BasicBlock::Create(TheContext
, "loop", TheFunction
);
805 // Insert an explicit fall through from the current block to the LoopBB.
806 Builder
.CreateBr(LoopBB
);
808 // Start insertion in LoopBB.
809 Builder
.SetInsertPoint(LoopBB
);
811 // Within the loop, the variable is defined equal to the PHI node. If it
812 // shadows an existing variable, we have to restore it, so save it now.
813 AllocaInst
*OldVal
= NamedValues
[VarName
];
814 NamedValues
[VarName
] = Alloca
;
816 // Emit the body of the loop. This, like any other expr, can change the
817 // current BB. Note that we ignore the value computed by the body, but don't
819 if (Body
->Codegen() == 0)
822 // Emit the step value.
825 StepVal
= Step
->Codegen();
826 if (StepVal
== 0) return 0;
828 // If not specified, use 1.0.
829 StepVal
= ConstantFP::get(TheContext
, APFloat(1.0));
832 // Compute the end condition.
833 Value
*EndCond
= End
->Codegen();
834 if (EndCond
== 0) return EndCond
;
836 // Reload, increment, and restore the alloca. This handles the case where
837 // the body of the loop mutates the variable.
838 Value
*CurVar
= Builder
.CreateLoad(Alloca
, VarName
.c_str());
839 Value
*NextVar
= Builder
.CreateFAdd(CurVar
, StepVal
, "nextvar");
840 Builder
.CreateStore(NextVar
, Alloca
);
842 // Convert condition to a bool by comparing equal to 0.0.
843 EndCond
= Builder
.CreateFCmpONE(
844 EndCond
, ConstantFP::get(TheContext
, APFloat(0.0)), "loopcond");
846 // Create the "after loop" block and insert it.
847 BasicBlock
*AfterBB
=
848 BasicBlock::Create(TheContext
, "afterloop", TheFunction
);
850 // Insert the conditional branch into the end of LoopEndBB.
851 Builder
.CreateCondBr(EndCond
, LoopBB
, AfterBB
);
853 // Any new code will be inserted in AfterBB.
854 Builder
.SetInsertPoint(AfterBB
);
856 // Restore the unshadowed variable.
858 NamedValues
[VarName
] = OldVal
;
860 NamedValues
.erase(VarName
);
863 // for expr always returns 0.0.
864 return Constant::getNullValue(Type::getDoubleTy(TheContext
));
867 Value
*VarExprAST::Codegen() {
868 std::vector
<AllocaInst
*> OldBindings
;
870 Function
*TheFunction
= Builder
.GetInsertBlock()->getParent();
872 // Register all variables and emit their initializer.
873 for (unsigned i
= 0, e
= VarNames
.size(); i
!= e
; ++i
) {
874 const std::string
&VarName
= VarNames
[i
].first
;
875 ExprAST
*Init
= VarNames
[i
].second
;
877 // Emit the initializer before adding the variable to scope, this prevents
878 // the initializer from referencing the variable itself, and permits stuff
881 // var a = a in ... # refers to outer 'a'.
884 InitVal
= Init
->Codegen();
885 if (InitVal
== 0) return 0;
886 } else { // If not specified, use 0.0.
887 InitVal
= ConstantFP::get(TheContext
, APFloat(0.0));
890 AllocaInst
*Alloca
= CreateEntryBlockAlloca(TheFunction
, VarName
);
891 Builder
.CreateStore(InitVal
, Alloca
);
893 // Remember the old variable binding so that we can restore the binding when
895 OldBindings
.push_back(NamedValues
[VarName
]);
897 // Remember this binding.
898 NamedValues
[VarName
] = Alloca
;
901 // Codegen the body, now that all vars are in scope.
902 Value
*BodyVal
= Body
->Codegen();
903 if (BodyVal
== 0) return 0;
905 // Pop all our variables from scope.
906 for (unsigned i
= 0, e
= VarNames
.size(); i
!= e
; ++i
)
907 NamedValues
[VarNames
[i
].first
] = OldBindings
[i
];
909 // Return the body computation.
913 Function
*PrototypeAST::Codegen() {
914 // Make the function type: double(double,double) etc.
915 std::vector
<Type
*> Doubles(Args
.size(), Type::getDoubleTy(TheContext
));
917 FunctionType::get(Type::getDoubleTy(TheContext
), Doubles
, false);
919 Function
*F
= Function::Create(FT
, Function::ExternalLinkage
, Name
, TheModule
);
920 // If F conflicted, there was already something named 'Name'. If it has a
921 // body, don't allow redefinition or reextern.
922 if (F
->getName() != Name
) {
923 // Delete the one we just made and get the existing one.
924 F
->eraseFromParent();
925 F
= TheModule
->getFunction(Name
);
926 // If F already has a body, reject this.
928 ErrorF("redefinition of function");
931 // If F took a different number of args, reject.
932 if (F
->arg_size() != Args
.size()) {
933 ErrorF("redefinition of function with different # args");
938 // Set names for all arguments.
940 for (Function::arg_iterator AI
= F
->arg_begin(); Idx
!= Args
.size();
942 AI
->setName(Args
[Idx
]);
947 /// CreateArgumentAllocas - Create an alloca for each argument and register the
948 /// argument in the symbol table so that references to it will succeed.
949 void PrototypeAST::CreateArgumentAllocas(Function
*F
) {
950 Function::arg_iterator AI
= F
->arg_begin();
951 for (unsigned Idx
= 0, e
= Args
.size(); Idx
!= e
; ++Idx
, ++AI
) {
952 // Create an alloca for this variable.
953 AllocaInst
*Alloca
= CreateEntryBlockAlloca(F
, Args
[Idx
]);
955 // Store the initial value into the alloca.
956 Builder
.CreateStore(AI
, Alloca
);
958 // Add arguments to variable symbol table.
959 NamedValues
[Args
[Idx
]] = Alloca
;
963 Function
*FunctionAST::Codegen() {
966 Function
*TheFunction
= Proto
->Codegen();
967 if (TheFunction
== 0)
970 // If this is an operator, install it.
971 if (Proto
->isBinaryOp())
972 BinopPrecedence
[Proto
->getOperatorName()] = Proto
->getBinaryPrecedence();
974 // Create a new basic block to start insertion into.
975 BasicBlock
*BB
= BasicBlock::Create(TheContext
, "entry", TheFunction
);
976 Builder
.SetInsertPoint(BB
);
978 // Add all arguments to the symbol table and create their allocas.
979 Proto
->CreateArgumentAllocas(TheFunction
);
981 if (Value
*RetVal
= Body
->Codegen()) {
982 // Finish off the function.
983 Builder
.CreateRet(RetVal
);
985 // Validate the generated code, checking for consistency.
986 verifyFunction(*TheFunction
);
988 // Optimize the function.
989 TheFPM
->run(*TheFunction
);
994 // Error reading body, remove function.
995 TheFunction
->eraseFromParent();
997 if (Proto
->isBinaryOp())
998 BinopPrecedence
.erase(Proto
->getOperatorName());
1002 //===----------------------------------------------------------------------===//
1003 // Top-Level parsing and JIT Driver
1004 //===----------------------------------------------------------------------===//
1006 static ExecutionEngine
*TheExecutionEngine
;
1008 static void HandleDefinition() {
1009 if (FunctionAST
*F
= ParseDefinition()) {
1010 if (Function
*LF
= F
->Codegen()) {
1011 #ifndef MINIMAL_STDERR_OUTPUT
1012 fprintf(stderr
, "Read function definition:");
1014 fprintf(stderr
, "\n");
1018 // Skip token for error recovery.
1023 static void HandleExtern() {
1024 if (PrototypeAST
*P
= ParseExtern()) {
1025 if (Function
*F
= P
->Codegen()) {
1026 #ifndef MINIMAL_STDERR_OUTPUT
1027 fprintf(stderr
, "Read extern: ");
1029 fprintf(stderr
, "\n");
1033 // Skip token for error recovery.
1038 static void HandleTopLevelExpression() {
1039 // Evaluate a top-level expression into an anonymous function.
1040 if (FunctionAST
*F
= ParseTopLevelExpr()) {
1041 if (Function
*LF
= F
->Codegen()) {
1042 // JIT the function, returning a function pointer.
1043 void *FPtr
= TheExecutionEngine
->getPointerToFunction(LF
);
1044 // Cast it to the right type (takes no arguments, returns a double) so we
1045 // can call it as a native function.
1046 double (*FP
)() = (double (*)())(intptr_t)FPtr
;
1047 #ifdef MINIMAL_STDERR_OUTPUT
1050 fprintf(stderr
, "Evaluated to %f\n", FP());
1054 // Skip token for error recovery.
1059 /// top ::= definition | external | expression | ';'
1060 static void MainLoop() {
1062 #ifndef MINIMAL_STDERR_OUTPUT
1063 fprintf(stderr
, "ready> ");
1066 case tok_eof
: return;
1067 case ';': getNextToken(); break; // ignore top-level semicolons.
1068 case tok_def
: HandleDefinition(); break;
1069 case tok_extern
: HandleExtern(); break;
1070 default: HandleTopLevelExpression(); break;
1075 //===----------------------------------------------------------------------===//
1076 // "Library" functions that can be "extern'd" from user code.
1077 //===----------------------------------------------------------------------===//
1079 /// putchard - putchar that takes a double and returns 0.
1081 double putchard(double X
) {
1086 /// printd - printf that takes a double prints it as "%f\n", returning 0.
1088 double printd(double X
) {
1099 //===----------------------------------------------------------------------===//
1100 // Main driver code.
1101 //===----------------------------------------------------------------------===//
1103 int main(int argc
, char **argv
) {
1104 InitializeNativeTarget();
1105 LLVMContext
&Context
= TheContext
;
1107 // Install standard binary operators.
1108 // 1 is lowest precedence.
1109 BinopPrecedence
['='] = 2;
1110 BinopPrecedence
['<'] = 10;
1111 BinopPrecedence
['+'] = 20;
1112 BinopPrecedence
['-'] = 20;
1113 BinopPrecedence
['/'] = 40;
1114 BinopPrecedence
['*'] = 40; // highest.
1116 // Make the module, which holds all the code.
1117 TheModule
= new Module("my cool jit", Context
);
1119 // Create the JIT. This takes ownership of the module.
1121 TheExecutionEngine
= EngineBuilder(TheModule
).setErrorStr(&ErrStr
).create();
1122 if (!TheExecutionEngine
) {
1123 fprintf(stderr
, "Could not create ExecutionEngine: %s\n", ErrStr
.c_str());
1127 FunctionPassManager
OurFPM(TheModule
);
1129 // Set up the optimizer pipeline. Start with registering info about how the
1130 // target lays out data structures.
1131 OurFPM
.add(new DataLayout(*TheExecutionEngine
->getDataLayout()));
1132 // Provide basic AliasAnalysis support for GVN.
1133 OurFPM
.add(createBasicAliasAnalysisPass());
1134 // Promote allocas to registers.
1135 OurFPM
.add(createPromoteMemoryToRegisterPass());
1136 // Do simple "peephole" optimizations and bit-twiddling optzns.
1137 OurFPM
.add(createInstructionCombiningPass());
1138 // Reassociate expressions.
1139 OurFPM
.add(createReassociatePass());
1140 // Eliminate Common SubExpressions.
1141 OurFPM
.add(createGVNPass());
1142 // Simplify the control flow graph (deleting unreachable blocks, etc).
1143 OurFPM
.add(createCFGSimplificationPass());
1145 OurFPM
.doInitialization();
1147 // Set the global so the code gen can use this.
1150 // Prime the first token.
1151 #ifndef MINIMAL_STDERR_OUTPUT
1152 fprintf(stderr
, "ready> ");
1156 // Run the main "interpreter loop" now.
1159 // Print out all of the generated code.
1161 #ifndef MINIMAL_STDERR_OUTPUT
1162 TheModule
->print(errs(), nullptr);