]>
git.proxmox.com Git - rustc.git/blob - src/llvm/examples/Kaleidoscope/Chapter8/toy.cpp
1 #include "llvm/ADT/Triple.h"
2 #include "llvm/Analysis/Passes.h"
3 #include "llvm/ExecutionEngine/ExecutionEngine.h"
4 #include "llvm/ExecutionEngine/MCJIT.h"
5 #include "llvm/ExecutionEngine/SectionMemoryManager.h"
6 #include "llvm/IR/DataLayout.h"
7 #include "llvm/IR/DerivedTypes.h"
8 #include "llvm/IR/DIBuilder.h"
9 #include "llvm/IR/IRBuilder.h"
10 #include "llvm/IR/LLVMContext.h"
11 #include "llvm/IR/Module.h"
12 #include "llvm/IR/Verifier.h"
13 #include "llvm/PassManager.h"
14 #include "llvm/Support/Host.h"
15 #include "llvm/Support/TargetSelect.h"
16 #include "llvm/Transforms/Scalar.h"
25 //===----------------------------------------------------------------------===//
27 //===----------------------------------------------------------------------===//
29 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
30 // of these for known things.
57 std::string
getTokName(int Tok
) {
86 return std::string(1, (char)Tok
);
93 static IRBuilder
<> Builder(getGlobalContext());
97 std::vector
<DIScope
*> LexicalBlocks
;
98 std::map
<const PrototypeAST
*, DIScope
> FnScopeMap
;
100 void emitLocation(ExprAST
*AST
);
101 DIType
getDoubleTy();
104 static std::string IdentifierStr
; // Filled in if tok_identifier
105 static double NumVal
; // Filled in if tok_number
106 struct SourceLocation
{
110 static SourceLocation CurLoc
;
111 static SourceLocation LexLoc
= { 1, 0 };
113 static int advance() {
114 int LastChar
= getchar();
116 if (LastChar
== '\n' || LastChar
== '\r') {
124 /// gettok - Return the next token from standard input.
125 static int gettok() {
126 static int LastChar
= ' ';
128 // Skip any whitespace.
129 while (isspace(LastChar
))
130 LastChar
= advance();
134 if (isalpha(LastChar
)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
135 IdentifierStr
= LastChar
;
136 while (isalnum((LastChar
= advance())))
137 IdentifierStr
+= LastChar
;
139 if (IdentifierStr
== "def")
141 if (IdentifierStr
== "extern")
143 if (IdentifierStr
== "if")
145 if (IdentifierStr
== "then")
147 if (IdentifierStr
== "else")
149 if (IdentifierStr
== "for")
151 if (IdentifierStr
== "in")
153 if (IdentifierStr
== "binary")
155 if (IdentifierStr
== "unary")
157 if (IdentifierStr
== "var")
159 return tok_identifier
;
162 if (isdigit(LastChar
) || LastChar
== '.') { // Number: [0-9.]+
166 LastChar
= advance();
167 } while (isdigit(LastChar
) || LastChar
== '.');
169 NumVal
= strtod(NumStr
.c_str(), 0);
173 if (LastChar
== '#') {
174 // Comment until end of line.
176 LastChar
= advance();
177 while (LastChar
!= EOF
&& LastChar
!= '\n' && LastChar
!= '\r');
183 // Check for end of file. Don't eat the EOF.
187 // Otherwise, just return the character as its ascii value.
188 int ThisChar
= LastChar
;
189 LastChar
= advance();
193 //===----------------------------------------------------------------------===//
194 // Abstract Syntax Tree (aka Parse Tree)
195 //===----------------------------------------------------------------------===//
198 std::ostream
&indent(std::ostream
&O
, int size
) {
199 return O
<< std::string(size
, ' ');
202 /// ExprAST - Base class for all expression nodes.
207 int getLine() const { return Loc
.Line
; }
208 int getCol() const { return Loc
.Col
; }
209 ExprAST(SourceLocation Loc
= CurLoc
) : Loc(Loc
) {}
210 virtual std::ostream
&dump(std::ostream
&out
, int ind
) {
211 return out
<< ':' << getLine() << ':' << getCol() << '\n';
213 virtual ~ExprAST() {}
214 virtual Value
*Codegen() = 0;
217 /// NumberExprAST - Expression class for numeric literals like "1.0".
218 class NumberExprAST
: public ExprAST
{
222 NumberExprAST(double val
) : Val(val
) {}
223 virtual std::ostream
&dump(std::ostream
&out
, int ind
) {
224 return ExprAST::dump(out
<< Val
, ind
);
226 virtual Value
*Codegen();
229 /// VariableExprAST - Expression class for referencing a variable, like "a".
230 class VariableExprAST
: public ExprAST
{
234 VariableExprAST(SourceLocation Loc
, const std::string
&name
)
235 : ExprAST(Loc
), Name(name
) {}
236 const std::string
&getName() const { return Name
; }
237 virtual std::ostream
&dump(std::ostream
&out
, int ind
) {
238 return ExprAST::dump(out
<< Name
, ind
);
240 virtual Value
*Codegen();
243 /// UnaryExprAST - Expression class for a unary operator.
244 class UnaryExprAST
: public ExprAST
{
249 UnaryExprAST(char opcode
, ExprAST
*operand
)
250 : Opcode(opcode
), Operand(operand
) {}
251 virtual std::ostream
&dump(std::ostream
&out
, int ind
) {
252 ExprAST::dump(out
<< "unary" << Opcode
, ind
);
253 Operand
->dump(out
, ind
+ 1);
256 virtual Value
*Codegen();
259 /// BinaryExprAST - Expression class for a binary operator.
260 class BinaryExprAST
: public ExprAST
{
265 BinaryExprAST(SourceLocation Loc
, char op
, ExprAST
*lhs
, ExprAST
*rhs
)
266 : ExprAST(Loc
), Op(op
), LHS(lhs
), RHS(rhs
) {}
267 virtual std::ostream
&dump(std::ostream
&out
, int ind
) {
268 ExprAST::dump(out
<< "binary" << Op
, ind
);
269 LHS
->dump(indent(out
, ind
) << "LHS:", ind
+ 1);
270 RHS
->dump(indent(out
, ind
) << "RHS:", ind
+ 1);
273 virtual Value
*Codegen();
276 /// CallExprAST - Expression class for function calls.
277 class CallExprAST
: public ExprAST
{
279 std::vector
<ExprAST
*> Args
;
282 CallExprAST(SourceLocation Loc
, const std::string
&callee
,
283 std::vector
<ExprAST
*> &args
)
284 : ExprAST(Loc
), Callee(callee
), Args(args
) {}
285 virtual std::ostream
&dump(std::ostream
&out
, int ind
) {
286 ExprAST::dump(out
<< "call " << Callee
, ind
);
287 for (ExprAST
*Arg
: Args
)
288 Arg
->dump(indent(out
, ind
+ 1), ind
+ 1);
291 virtual Value
*Codegen();
294 /// IfExprAST - Expression class for if/then/else.
295 class IfExprAST
: public ExprAST
{
296 ExprAST
*Cond
, *Then
, *Else
;
299 IfExprAST(SourceLocation Loc
, ExprAST
*cond
, ExprAST
*then
, ExprAST
*_else
)
300 : ExprAST(Loc
), Cond(cond
), Then(then
), Else(_else
) {}
301 virtual std::ostream
&dump(std::ostream
&out
, int ind
) {
302 ExprAST::dump(out
<< "if", ind
);
303 Cond
->dump(indent(out
, ind
) << "Cond:", ind
+ 1);
304 Then
->dump(indent(out
, ind
) << "Then:", ind
+ 1);
305 Else
->dump(indent(out
, ind
) << "Else:", ind
+ 1);
308 virtual Value
*Codegen();
311 /// ForExprAST - Expression class for for/in.
312 class ForExprAST
: public ExprAST
{
314 ExprAST
*Start
, *End
, *Step
, *Body
;
317 ForExprAST(const std::string
&varname
, ExprAST
*start
, ExprAST
*end
,
318 ExprAST
*step
, ExprAST
*body
)
319 : VarName(varname
), Start(start
), End(end
), Step(step
), Body(body
) {}
320 virtual std::ostream
&dump(std::ostream
&out
, int ind
) {
321 ExprAST::dump(out
<< "for", ind
);
322 Start
->dump(indent(out
, ind
) << "Cond:", ind
+ 1);
323 End
->dump(indent(out
, ind
) << "End:", ind
+ 1);
324 Step
->dump(indent(out
, ind
) << "Step:", ind
+ 1);
325 Body
->dump(indent(out
, ind
) << "Body:", ind
+ 1);
328 virtual Value
*Codegen();
331 /// VarExprAST - Expression class for var/in
332 class VarExprAST
: public ExprAST
{
333 std::vector
<std::pair
<std::string
, ExprAST
*> > VarNames
;
337 VarExprAST(const std::vector
<std::pair
<std::string
, ExprAST
*> > &varnames
,
339 : VarNames(varnames
), Body(body
) {}
341 virtual std::ostream
&dump(std::ostream
&out
, int ind
) {
342 ExprAST::dump(out
<< "var", ind
);
343 for (const auto &NamedVar
: VarNames
)
344 NamedVar
.second
->dump(indent(out
, ind
) << NamedVar
.first
<< ':', ind
+ 1);
345 Body
->dump(indent(out
, ind
) << "Body:", ind
+ 1);
348 virtual Value
*Codegen();
351 /// PrototypeAST - This class represents the "prototype" for a function,
352 /// which captures its argument names as well as if it is an operator.
355 std::vector
<std::string
> Args
;
357 unsigned Precedence
; // Precedence if a binary op.
361 PrototypeAST(SourceLocation Loc
, const std::string
&name
,
362 const std::vector
<std::string
> &args
, bool isoperator
= false,
364 : Name(name
), Args(args
), isOperator(isoperator
), Precedence(prec
),
367 bool isUnaryOp() const { return isOperator
&& Args
.size() == 1; }
368 bool isBinaryOp() const { return isOperator
&& Args
.size() == 2; }
370 char getOperatorName() const {
371 assert(isUnaryOp() || isBinaryOp());
372 return Name
[Name
.size() - 1];
375 unsigned getBinaryPrecedence() const { return Precedence
; }
379 void CreateArgumentAllocas(Function
*F
);
380 const std::vector
<std::string
> &getArgs() const { return Args
; }
383 /// FunctionAST - This class represents a function definition itself.
389 FunctionAST(PrototypeAST
*proto
, ExprAST
*body
) : Proto(proto
), Body(body
) {}
391 std::ostream
&dump(std::ostream
&out
, int ind
) {
392 indent(out
, ind
) << "FunctionAST\n";
394 indent(out
, ind
) << "Body:";
395 return Body
? Body
->dump(out
, ind
) : out
<< "null\n";
400 } // end anonymous namespace
402 //===----------------------------------------------------------------------===//
404 //===----------------------------------------------------------------------===//
406 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
407 /// token the parser is looking at. getNextToken reads another token from the
408 /// lexer and updates CurTok with its results.
410 static int getNextToken() { return CurTok
= gettok(); }
412 /// BinopPrecedence - This holds the precedence for each binary operator that is
414 static std::map
<char, int> BinopPrecedence
;
416 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
417 static int GetTokPrecedence() {
418 if (!isascii(CurTok
))
421 // Make sure it's a declared binop.
422 int TokPrec
= BinopPrecedence
[CurTok
];
428 /// Error* - These are little helper functions for error handling.
429 ExprAST
*Error(const char *Str
) {
430 fprintf(stderr
, "Error: %s\n", Str
);
433 PrototypeAST
*ErrorP(const char *Str
) {
437 FunctionAST
*ErrorF(const char *Str
) {
442 static ExprAST
*ParseExpression();
446 /// ::= identifier '(' expression* ')'
447 static ExprAST
*ParseIdentifierExpr() {
448 std::string IdName
= IdentifierStr
;
450 SourceLocation LitLoc
= CurLoc
;
452 getNextToken(); // eat identifier.
454 if (CurTok
!= '(') // Simple variable ref.
455 return new VariableExprAST(LitLoc
, IdName
);
458 getNextToken(); // eat (
459 std::vector
<ExprAST
*> Args
;
462 ExprAST
*Arg
= ParseExpression();
471 return Error("Expected ')' or ',' in argument list");
479 return new CallExprAST(LitLoc
, IdName
, Args
);
482 /// numberexpr ::= number
483 static ExprAST
*ParseNumberExpr() {
484 ExprAST
*Result
= new NumberExprAST(NumVal
);
485 getNextToken(); // consume the number
489 /// parenexpr ::= '(' expression ')'
490 static ExprAST
*ParseParenExpr() {
491 getNextToken(); // eat (.
492 ExprAST
*V
= ParseExpression();
497 return Error("expected ')'");
498 getNextToken(); // eat ).
502 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
503 static ExprAST
*ParseIfExpr() {
504 SourceLocation IfLoc
= CurLoc
;
506 getNextToken(); // eat the if.
509 ExprAST
*Cond
= ParseExpression();
513 if (CurTok
!= tok_then
)
514 return Error("expected then");
515 getNextToken(); // eat the then
517 ExprAST
*Then
= ParseExpression();
521 if (CurTok
!= tok_else
)
522 return Error("expected else");
526 ExprAST
*Else
= ParseExpression();
530 return new IfExprAST(IfLoc
, Cond
, Then
, Else
);
533 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
534 static ExprAST
*ParseForExpr() {
535 getNextToken(); // eat the for.
537 if (CurTok
!= tok_identifier
)
538 return Error("expected identifier after for");
540 std::string IdName
= IdentifierStr
;
541 getNextToken(); // eat identifier.
544 return Error("expected '=' after for");
545 getNextToken(); // eat '='.
547 ExprAST
*Start
= ParseExpression();
551 return Error("expected ',' after for start value");
554 ExprAST
*End
= ParseExpression();
558 // The step value is optional.
562 Step
= ParseExpression();
567 if (CurTok
!= tok_in
)
568 return Error("expected 'in' after for");
569 getNextToken(); // eat 'in'.
571 ExprAST
*Body
= ParseExpression();
575 return new ForExprAST(IdName
, Start
, End
, Step
, Body
);
578 /// varexpr ::= 'var' identifier ('=' expression)?
579 // (',' identifier ('=' expression)?)* 'in' expression
580 static ExprAST
*ParseVarExpr() {
581 getNextToken(); // eat the var.
583 std::vector
<std::pair
<std::string
, ExprAST
*> > VarNames
;
585 // At least one variable name is required.
586 if (CurTok
!= tok_identifier
)
587 return Error("expected identifier after var");
590 std::string Name
= IdentifierStr
;
591 getNextToken(); // eat identifier.
593 // Read the optional initializer.
596 getNextToken(); // eat the '='.
598 Init
= ParseExpression();
603 VarNames
.push_back(std::make_pair(Name
, Init
));
605 // End of var list, exit loop.
608 getNextToken(); // eat the ','.
610 if (CurTok
!= tok_identifier
)
611 return Error("expected identifier list after var");
614 // At this point, we have to have 'in'.
615 if (CurTok
!= tok_in
)
616 return Error("expected 'in' keyword after 'var'");
617 getNextToken(); // eat 'in'.
619 ExprAST
*Body
= ParseExpression();
623 return new VarExprAST(VarNames
, Body
);
627 /// ::= identifierexpr
633 static ExprAST
*ParsePrimary() {
636 return Error("unknown token when expecting an expression");
638 return ParseIdentifierExpr();
640 return ParseNumberExpr();
642 return ParseParenExpr();
644 return ParseIfExpr();
646 return ParseForExpr();
648 return ParseVarExpr();
655 static ExprAST
*ParseUnary() {
656 // If the current token is not an operator, it must be a primary expr.
657 if (!isascii(CurTok
) || CurTok
== '(' || CurTok
== ',')
658 return ParsePrimary();
660 // If this is a unary operator, read it.
663 if (ExprAST
*Operand
= ParseUnary())
664 return new UnaryExprAST(Opc
, Operand
);
670 static ExprAST
*ParseBinOpRHS(int ExprPrec
, ExprAST
*LHS
) {
671 // If this is a binop, find its precedence.
673 int TokPrec
= GetTokPrecedence();
675 // If this is a binop that binds at least as tightly as the current binop,
676 // consume it, otherwise we are done.
677 if (TokPrec
< ExprPrec
)
680 // Okay, we know this is a binop.
682 SourceLocation BinLoc
= CurLoc
;
683 getNextToken(); // eat binop
685 // Parse the unary expression after the binary operator.
686 ExprAST
*RHS
= ParseUnary();
690 // If BinOp binds less tightly with RHS than the operator after RHS, let
691 // the pending operator take RHS as its LHS.
692 int NextPrec
= GetTokPrecedence();
693 if (TokPrec
< NextPrec
) {
694 RHS
= ParseBinOpRHS(TokPrec
+ 1, RHS
);
700 LHS
= new BinaryExprAST(BinLoc
, BinOp
, LHS
, RHS
);
705 /// ::= unary binoprhs
707 static ExprAST
*ParseExpression() {
708 ExprAST
*LHS
= ParseUnary();
712 return ParseBinOpRHS(0, LHS
);
716 /// ::= id '(' id* ')'
717 /// ::= binary LETTER number? (id, id)
718 /// ::= unary LETTER (id)
719 static PrototypeAST
*ParsePrototype() {
722 SourceLocation FnLoc
= CurLoc
;
724 unsigned Kind
= 0; // 0 = identifier, 1 = unary, 2 = binary.
725 unsigned BinaryPrecedence
= 30;
729 return ErrorP("Expected function name in prototype");
731 FnName
= IdentifierStr
;
737 if (!isascii(CurTok
))
738 return ErrorP("Expected unary operator");
740 FnName
+= (char)CurTok
;
746 if (!isascii(CurTok
))
747 return ErrorP("Expected binary operator");
749 FnName
+= (char)CurTok
;
753 // Read the precedence if present.
754 if (CurTok
== tok_number
) {
755 if (NumVal
< 1 || NumVal
> 100)
756 return ErrorP("Invalid precedecnce: must be 1..100");
757 BinaryPrecedence
= (unsigned)NumVal
;
764 return ErrorP("Expected '(' in prototype");
766 std::vector
<std::string
> ArgNames
;
767 while (getNextToken() == tok_identifier
)
768 ArgNames
.push_back(IdentifierStr
);
770 return ErrorP("Expected ')' in prototype");
773 getNextToken(); // eat ')'.
775 // Verify right number of names for operator.
776 if (Kind
&& ArgNames
.size() != Kind
)
777 return ErrorP("Invalid number of operands for operator");
779 return new PrototypeAST(FnLoc
, FnName
, ArgNames
, Kind
!= 0, BinaryPrecedence
);
782 /// definition ::= 'def' prototype expression
783 static FunctionAST
*ParseDefinition() {
784 getNextToken(); // eat def.
785 PrototypeAST
*Proto
= ParsePrototype();
789 if (ExprAST
*E
= ParseExpression())
790 return new FunctionAST(Proto
, E
);
794 /// toplevelexpr ::= expression
795 static FunctionAST
*ParseTopLevelExpr() {
796 SourceLocation FnLoc
= CurLoc
;
797 if (ExprAST
*E
= ParseExpression()) {
798 // Make an anonymous proto.
799 PrototypeAST
*Proto
=
800 new PrototypeAST(FnLoc
, "main", std::vector
<std::string
>());
801 return new FunctionAST(Proto
, E
);
806 /// external ::= 'extern' prototype
807 static PrototypeAST
*ParseExtern() {
808 getNextToken(); // eat extern.
809 return ParsePrototype();
812 //===----------------------------------------------------------------------===//
813 // Debug Info Support
814 //===----------------------------------------------------------------------===//
816 static DIBuilder
*DBuilder
;
818 DIType
DebugInfo::getDoubleTy() {
822 DblTy
= DBuilder
->createBasicType("double", 64, 64, dwarf::DW_ATE_float
);
826 void DebugInfo::emitLocation(ExprAST
*AST
) {
828 return Builder
.SetCurrentDebugLocation(DebugLoc());
830 if (LexicalBlocks
.empty())
833 Scope
= LexicalBlocks
.back();
834 Builder
.SetCurrentDebugLocation(
835 DebugLoc::get(AST
->getLine(), AST
->getCol(), DIScope(*Scope
)));
838 static DICompositeType
CreateFunctionType(unsigned NumArgs
, DIFile Unit
) {
839 SmallVector
<Metadata
*, 8> EltTys
;
840 DIType DblTy
= KSDbgInfo
.getDoubleTy();
842 // Add the result type.
843 EltTys
.push_back(DblTy
);
845 for (unsigned i
= 0, e
= NumArgs
; i
!= e
; ++i
)
846 EltTys
.push_back(DblTy
);
848 DITypeArray EltTypeArray
= DBuilder
->getOrCreateTypeArray(EltTys
);
849 return DBuilder
->createSubroutineType(Unit
, EltTypeArray
);
852 //===----------------------------------------------------------------------===//
854 //===----------------------------------------------------------------------===//
856 static Module
*TheModule
;
857 static std::map
<std::string
, AllocaInst
*> NamedValues
;
858 static FunctionPassManager
*TheFPM
;
860 Value
*ErrorV(const char *Str
) {
865 /// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
866 /// the function. This is used for mutable variables etc.
867 static AllocaInst
*CreateEntryBlockAlloca(Function
*TheFunction
,
868 const std::string
&VarName
) {
869 IRBuilder
<> TmpB(&TheFunction
->getEntryBlock(),
870 TheFunction
->getEntryBlock().begin());
871 return TmpB
.CreateAlloca(Type::getDoubleTy(getGlobalContext()), 0,
875 Value
*NumberExprAST::Codegen() {
876 KSDbgInfo
.emitLocation(this);
877 return ConstantFP::get(getGlobalContext(), APFloat(Val
));
880 Value
*VariableExprAST::Codegen() {
881 // Look this variable up in the function.
882 Value
*V
= NamedValues
[Name
];
884 return ErrorV("Unknown variable name");
886 KSDbgInfo
.emitLocation(this);
888 return Builder
.CreateLoad(V
, Name
.c_str());
891 Value
*UnaryExprAST::Codegen() {
892 Value
*OperandV
= Operand
->Codegen();
896 Function
*F
= TheModule
->getFunction(std::string("unary") + Opcode
);
898 return ErrorV("Unknown unary operator");
900 KSDbgInfo
.emitLocation(this);
901 return Builder
.CreateCall(F
, OperandV
, "unop");
904 Value
*BinaryExprAST::Codegen() {
905 KSDbgInfo
.emitLocation(this);
907 // Special case '=' because we don't want to emit the LHS as an expression.
909 // Assignment requires the LHS to be an identifier.
910 VariableExprAST
*LHSE
= dynamic_cast<VariableExprAST
*>(LHS
);
912 return ErrorV("destination of '=' must be a variable");
914 Value
*Val
= RHS
->Codegen();
919 Value
*Variable
= NamedValues
[LHSE
->getName()];
921 return ErrorV("Unknown variable name");
923 Builder
.CreateStore(Val
, Variable
);
927 Value
*L
= LHS
->Codegen();
928 Value
*R
= RHS
->Codegen();
929 if (L
== 0 || R
== 0)
934 return Builder
.CreateFAdd(L
, R
, "addtmp");
936 return Builder
.CreateFSub(L
, R
, "subtmp");
938 return Builder
.CreateFMul(L
, R
, "multmp");
940 L
= Builder
.CreateFCmpULT(L
, R
, "cmptmp");
941 // Convert bool 0/1 to double 0.0 or 1.0
942 return Builder
.CreateUIToFP(L
, Type::getDoubleTy(getGlobalContext()),
948 // If it wasn't a builtin binary operator, it must be a user defined one. Emit
950 Function
*F
= TheModule
->getFunction(std::string("binary") + Op
);
951 assert(F
&& "binary operator not found!");
953 Value
*Ops
[] = { L
, R
};
954 return Builder
.CreateCall(F
, Ops
, "binop");
957 Value
*CallExprAST::Codegen() {
958 KSDbgInfo
.emitLocation(this);
960 // Look up the name in the global module table.
961 Function
*CalleeF
= TheModule
->getFunction(Callee
);
963 return ErrorV("Unknown function referenced");
965 // If argument mismatch error.
966 if (CalleeF
->arg_size() != Args
.size())
967 return ErrorV("Incorrect # arguments passed");
969 std::vector
<Value
*> ArgsV
;
970 for (unsigned i
= 0, e
= Args
.size(); i
!= e
; ++i
) {
971 ArgsV
.push_back(Args
[i
]->Codegen());
972 if (ArgsV
.back() == 0)
976 return Builder
.CreateCall(CalleeF
, ArgsV
, "calltmp");
979 Value
*IfExprAST::Codegen() {
980 KSDbgInfo
.emitLocation(this);
982 Value
*CondV
= Cond
->Codegen();
986 // Convert condition to a bool by comparing equal to 0.0.
987 CondV
= Builder
.CreateFCmpONE(
988 CondV
, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "ifcond");
990 Function
*TheFunction
= Builder
.GetInsertBlock()->getParent();
992 // Create blocks for the then and else cases. Insert the 'then' block at the
993 // end of the function.
995 BasicBlock::Create(getGlobalContext(), "then", TheFunction
);
996 BasicBlock
*ElseBB
= BasicBlock::Create(getGlobalContext(), "else");
997 BasicBlock
*MergeBB
= BasicBlock::Create(getGlobalContext(), "ifcont");
999 Builder
.CreateCondBr(CondV
, ThenBB
, ElseBB
);
1002 Builder
.SetInsertPoint(ThenBB
);
1004 Value
*ThenV
= Then
->Codegen();
1008 Builder
.CreateBr(MergeBB
);
1009 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1010 ThenBB
= Builder
.GetInsertBlock();
1013 TheFunction
->getBasicBlockList().push_back(ElseBB
);
1014 Builder
.SetInsertPoint(ElseBB
);
1016 Value
*ElseV
= Else
->Codegen();
1020 Builder
.CreateBr(MergeBB
);
1021 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1022 ElseBB
= Builder
.GetInsertBlock();
1024 // Emit merge block.
1025 TheFunction
->getBasicBlockList().push_back(MergeBB
);
1026 Builder
.SetInsertPoint(MergeBB
);
1028 Builder
.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, "iftmp");
1030 PN
->addIncoming(ThenV
, ThenBB
);
1031 PN
->addIncoming(ElseV
, ElseBB
);
1035 Value
*ForExprAST::Codegen() {
1037 // var = alloca double
1039 // start = startexpr
1040 // store start -> var
1048 // endcond = endexpr
1050 // curvar = load var
1051 // nextvar = curvar + step
1052 // store nextvar -> var
1053 // br endcond, loop, endloop
1056 Function
*TheFunction
= Builder
.GetInsertBlock()->getParent();
1058 // Create an alloca for the variable in the entry block.
1059 AllocaInst
*Alloca
= CreateEntryBlockAlloca(TheFunction
, VarName
);
1061 KSDbgInfo
.emitLocation(this);
1063 // Emit the start code first, without 'variable' in scope.
1064 Value
*StartVal
= Start
->Codegen();
1068 // Store the value into the alloca.
1069 Builder
.CreateStore(StartVal
, Alloca
);
1071 // Make the new basic block for the loop header, inserting after current
1073 BasicBlock
*LoopBB
=
1074 BasicBlock::Create(getGlobalContext(), "loop", TheFunction
);
1076 // Insert an explicit fall through from the current block to the LoopBB.
1077 Builder
.CreateBr(LoopBB
);
1079 // Start insertion in LoopBB.
1080 Builder
.SetInsertPoint(LoopBB
);
1082 // Within the loop, the variable is defined equal to the PHI node. If it
1083 // shadows an existing variable, we have to restore it, so save it now.
1084 AllocaInst
*OldVal
= NamedValues
[VarName
];
1085 NamedValues
[VarName
] = Alloca
;
1087 // Emit the body of the loop. This, like any other expr, can change the
1088 // current BB. Note that we ignore the value computed by the body, but don't
1090 if (Body
->Codegen() == 0)
1093 // Emit the step value.
1096 StepVal
= Step
->Codegen();
1100 // If not specified, use 1.0.
1101 StepVal
= ConstantFP::get(getGlobalContext(), APFloat(1.0));
1104 // Compute the end condition.
1105 Value
*EndCond
= End
->Codegen();
1109 // Reload, increment, and restore the alloca. This handles the case where
1110 // the body of the loop mutates the variable.
1111 Value
*CurVar
= Builder
.CreateLoad(Alloca
, VarName
.c_str());
1112 Value
*NextVar
= Builder
.CreateFAdd(CurVar
, StepVal
, "nextvar");
1113 Builder
.CreateStore(NextVar
, Alloca
);
1115 // Convert condition to a bool by comparing equal to 0.0.
1116 EndCond
= Builder
.CreateFCmpONE(
1117 EndCond
, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "loopcond");
1119 // Create the "after loop" block and insert it.
1120 BasicBlock
*AfterBB
=
1121 BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction
);
1123 // Insert the conditional branch into the end of LoopEndBB.
1124 Builder
.CreateCondBr(EndCond
, LoopBB
, AfterBB
);
1126 // Any new code will be inserted in AfterBB.
1127 Builder
.SetInsertPoint(AfterBB
);
1129 // Restore the unshadowed variable.
1131 NamedValues
[VarName
] = OldVal
;
1133 NamedValues
.erase(VarName
);
1135 // for expr always returns 0.0.
1136 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
1139 Value
*VarExprAST::Codegen() {
1140 std::vector
<AllocaInst
*> OldBindings
;
1142 Function
*TheFunction
= Builder
.GetInsertBlock()->getParent();
1144 // Register all variables and emit their initializer.
1145 for (unsigned i
= 0, e
= VarNames
.size(); i
!= e
; ++i
) {
1146 const std::string
&VarName
= VarNames
[i
].first
;
1147 ExprAST
*Init
= VarNames
[i
].second
;
1149 // Emit the initializer before adding the variable to scope, this prevents
1150 // the initializer from referencing the variable itself, and permits stuff
1153 // var a = a in ... # refers to outer 'a'.
1156 InitVal
= Init
->Codegen();
1159 } else { // If not specified, use 0.0.
1160 InitVal
= ConstantFP::get(getGlobalContext(), APFloat(0.0));
1163 AllocaInst
*Alloca
= CreateEntryBlockAlloca(TheFunction
, VarName
);
1164 Builder
.CreateStore(InitVal
, Alloca
);
1166 // Remember the old variable binding so that we can restore the binding when
1168 OldBindings
.push_back(NamedValues
[VarName
]);
1170 // Remember this binding.
1171 NamedValues
[VarName
] = Alloca
;
1174 KSDbgInfo
.emitLocation(this);
1176 // Codegen the body, now that all vars are in scope.
1177 Value
*BodyVal
= Body
->Codegen();
1181 // Pop all our variables from scope.
1182 for (unsigned i
= 0, e
= VarNames
.size(); i
!= e
; ++i
)
1183 NamedValues
[VarNames
[i
].first
] = OldBindings
[i
];
1185 // Return the body computation.
1189 Function
*PrototypeAST::Codegen() {
1190 // Make the function type: double(double,double) etc.
1191 std::vector
<Type
*> Doubles(Args
.size(),
1192 Type::getDoubleTy(getGlobalContext()));
1194 FunctionType::get(Type::getDoubleTy(getGlobalContext()), Doubles
, false);
1197 Function::Create(FT
, Function::ExternalLinkage
, Name
, TheModule
);
1199 // If F conflicted, there was already something named 'Name'. If it has a
1200 // body, don't allow redefinition or reextern.
1201 if (F
->getName() != Name
) {
1202 // Delete the one we just made and get the existing one.
1203 F
->eraseFromParent();
1204 F
= TheModule
->getFunction(Name
);
1206 // If F already has a body, reject this.
1208 ErrorF("redefinition of function");
1212 // If F took a different number of args, reject.
1213 if (F
->arg_size() != Args
.size()) {
1214 ErrorF("redefinition of function with different # args");
1219 // Set names for all arguments.
1221 for (Function::arg_iterator AI
= F
->arg_begin(); Idx
!= Args
.size();
1223 AI
->setName(Args
[Idx
]);
1225 // Create a subprogram DIE for this function.
1226 DIFile Unit
= DBuilder
->createFile(KSDbgInfo
.TheCU
.getFilename(),
1227 KSDbgInfo
.TheCU
.getDirectory());
1228 DIDescriptor
FContext(Unit
);
1229 unsigned LineNo
= Line
;
1230 unsigned ScopeLine
= Line
;
1231 DISubprogram SP
= DBuilder
->createFunction(
1232 FContext
, Name
, StringRef(), Unit
, LineNo
,
1233 CreateFunctionType(Args
.size(), Unit
), false /* internal linkage */,
1234 true /* definition */, ScopeLine
, DIDescriptor::FlagPrototyped
, false, F
);
1236 KSDbgInfo
.FnScopeMap
[this] = SP
;
1240 /// CreateArgumentAllocas - Create an alloca for each argument and register the
1241 /// argument in the symbol table so that references to it will succeed.
1242 void PrototypeAST::CreateArgumentAllocas(Function
*F
) {
1243 Function::arg_iterator AI
= F
->arg_begin();
1244 for (unsigned Idx
= 0, e
= Args
.size(); Idx
!= e
; ++Idx
, ++AI
) {
1245 // Create an alloca for this variable.
1246 AllocaInst
*Alloca
= CreateEntryBlockAlloca(F
, Args
[Idx
]);
1248 // Create a debug descriptor for the variable.
1249 DIScope
*Scope
= KSDbgInfo
.LexicalBlocks
.back();
1250 DIFile Unit
= DBuilder
->createFile(KSDbgInfo
.TheCU
.getFilename(),
1251 KSDbgInfo
.TheCU
.getDirectory());
1252 DIVariable D
= DBuilder
->createLocalVariable(dwarf::DW_TAG_arg_variable
,
1253 *Scope
, Args
[Idx
], Unit
, Line
,
1254 KSDbgInfo
.getDoubleTy(), Idx
);
1256 Instruction
*Call
= DBuilder
->insertDeclare(
1257 Alloca
, D
, DBuilder
->createExpression(), Builder
.GetInsertBlock());
1258 Call
->setDebugLoc(DebugLoc::get(Line
, 0, *Scope
));
1260 // Store the initial value into the alloca.
1261 Builder
.CreateStore(AI
, Alloca
);
1263 // Add arguments to variable symbol table.
1264 NamedValues
[Args
[Idx
]] = Alloca
;
1268 Function
*FunctionAST::Codegen() {
1269 NamedValues
.clear();
1271 Function
*TheFunction
= Proto
->Codegen();
1272 if (TheFunction
== 0)
1275 // Push the current scope.
1276 KSDbgInfo
.LexicalBlocks
.push_back(&KSDbgInfo
.FnScopeMap
[Proto
]);
1278 // Unset the location for the prologue emission (leading instructions with no
1279 // location in a function are considered part of the prologue and the debugger
1280 // will run past them when breaking on a function)
1281 KSDbgInfo
.emitLocation(nullptr);
1283 // If this is an operator, install it.
1284 if (Proto
->isBinaryOp())
1285 BinopPrecedence
[Proto
->getOperatorName()] = Proto
->getBinaryPrecedence();
1287 // Create a new basic block to start insertion into.
1288 BasicBlock
*BB
= BasicBlock::Create(getGlobalContext(), "entry", TheFunction
);
1289 Builder
.SetInsertPoint(BB
);
1291 // Add all arguments to the symbol table and create their allocas.
1292 Proto
->CreateArgumentAllocas(TheFunction
);
1294 KSDbgInfo
.emitLocation(Body
);
1296 if (Value
*RetVal
= Body
->Codegen()) {
1297 // Finish off the function.
1298 Builder
.CreateRet(RetVal
);
1300 // Pop off the lexical block for the function.
1301 KSDbgInfo
.LexicalBlocks
.pop_back();
1303 // Validate the generated code, checking for consistency.
1304 verifyFunction(*TheFunction
);
1306 // Optimize the function.
1307 TheFPM
->run(*TheFunction
);
1312 // Error reading body, remove function.
1313 TheFunction
->eraseFromParent();
1315 if (Proto
->isBinaryOp())
1316 BinopPrecedence
.erase(Proto
->getOperatorName());
1318 // Pop off the lexical block for the function since we added it
1320 KSDbgInfo
.LexicalBlocks
.pop_back();
1325 //===----------------------------------------------------------------------===//
1326 // Top-Level parsing and JIT Driver
1327 //===----------------------------------------------------------------------===//
1329 static ExecutionEngine
*TheExecutionEngine
;
1331 static void HandleDefinition() {
1332 if (FunctionAST
*F
= ParseDefinition()) {
1333 if (!F
->Codegen()) {
1334 fprintf(stderr
, "Error reading function definition:");
1337 // Skip token for error recovery.
1342 static void HandleExtern() {
1343 if (PrototypeAST
*P
= ParseExtern()) {
1344 if (!P
->Codegen()) {
1345 fprintf(stderr
, "Error reading extern");
1348 // Skip token for error recovery.
1353 static void HandleTopLevelExpression() {
1354 // Evaluate a top-level expression into an anonymous function.
1355 if (FunctionAST
*F
= ParseTopLevelExpr()) {
1356 if (!F
->Codegen()) {
1357 fprintf(stderr
, "Error generating code for top level expr");
1360 // Skip token for error recovery.
1365 /// top ::= definition | external | expression | ';'
1366 static void MainLoop() {
1373 break; // ignore top-level semicolons.
1381 HandleTopLevelExpression();
1387 //===----------------------------------------------------------------------===//
1388 // "Library" functions that can be "extern'd" from user code.
1389 //===----------------------------------------------------------------------===//
1391 /// putchard - putchar that takes a double and returns 0.
1392 extern "C" double putchard(double X
) {
1397 /// printd - printf that takes a double prints it as "%f\n", returning 0.
1398 extern "C" double printd(double X
) {
1403 //===----------------------------------------------------------------------===//
1404 // Main driver code.
1405 //===----------------------------------------------------------------------===//
1408 InitializeNativeTarget();
1409 InitializeNativeTargetAsmPrinter();
1410 InitializeNativeTargetAsmParser();
1411 LLVMContext
&Context
= getGlobalContext();
1413 // Install standard binary operators.
1414 // 1 is lowest precedence.
1415 BinopPrecedence
['='] = 2;
1416 BinopPrecedence
['<'] = 10;
1417 BinopPrecedence
['+'] = 20;
1418 BinopPrecedence
['-'] = 20;
1419 BinopPrecedence
['*'] = 40; // highest.
1421 // Prime the first token.
1424 // Make the module, which holds all the code.
1425 std::unique_ptr
<Module
> Owner
= make_unique
<Module
>("my cool jit", Context
);
1426 TheModule
= Owner
.get();
1428 // Add the current debug info version into the module.
1429 TheModule
->addModuleFlag(Module::Warning
, "Debug Info Version",
1430 DEBUG_METADATA_VERSION
);
1432 // Darwin only supports dwarf2.
1433 if (Triple(sys::getProcessTriple()).isOSDarwin())
1434 TheModule
->addModuleFlag(llvm::Module::Warning
, "Dwarf Version", 2);
1436 // Construct the DIBuilder, we do this here because we need the module.
1437 DBuilder
= new DIBuilder(*TheModule
);
1439 // Create the compile unit for the module.
1440 // Currently down as "fib.ks" as a filename since we're redirecting stdin
1441 // but we'd like actual source locations.
1442 KSDbgInfo
.TheCU
= DBuilder
->createCompileUnit(
1443 dwarf::DW_LANG_C
, "fib.ks", ".", "Kaleidoscope Compiler", 0, "", 0);
1445 // Create the JIT. This takes ownership of the module.
1447 TheExecutionEngine
=
1448 EngineBuilder(std::move(Owner
))
1449 .setErrorStr(&ErrStr
)
1450 .setMCJITMemoryManager(llvm::make_unique
<SectionMemoryManager
>())
1452 if (!TheExecutionEngine
) {
1453 fprintf(stderr
, "Could not create ExecutionEngine: %s\n", ErrStr
.c_str());
1457 FunctionPassManager
OurFPM(TheModule
);
1459 // Set up the optimizer pipeline. Start with registering info about how the
1460 // target lays out data structures.
1461 TheModule
->setDataLayout(TheExecutionEngine
->getDataLayout());
1462 OurFPM
.add(new DataLayoutPass());
1464 // Provide basic AliasAnalysis support for GVN.
1465 OurFPM
.add(createBasicAliasAnalysisPass());
1466 // Promote allocas to registers.
1467 OurFPM
.add(createPromoteMemoryToRegisterPass());
1468 // Do simple "peephole" optimizations and bit-twiddling optzns.
1469 OurFPM
.add(createInstructionCombiningPass());
1470 // Reassociate expressions.
1471 OurFPM
.add(createReassociatePass());
1472 // Eliminate Common SubExpressions.
1473 OurFPM
.add(createGVNPass());
1474 // Simplify the control flow graph (deleting unreachable blocks, etc).
1475 OurFPM
.add(createCFGSimplificationPass());
1477 OurFPM
.doInitialization();
1479 // Set the global so the code gen can use this.
1482 // Run the main "interpreter loop" now.
1487 // Finalize the debug info.
1488 DBuilder
->finalize();
1490 // Print out all of the generated code.