1 #include "llvm/ADT/STLExtras.h"
2 #include "llvm/ADT/Triple.h"
3 #include "llvm/Analysis/Passes.h"
4 #include "llvm/ExecutionEngine/ExecutionEngine.h"
5 #include "llvm/ExecutionEngine/MCJIT.h"
6 #include "llvm/ExecutionEngine/SectionMemoryManager.h"
7 #include "llvm/IR/DIBuilder.h"
8 #include "llvm/IR/DataLayout.h"
9 #include "llvm/IR/DerivedTypes.h"
10 #include "llvm/IR/IRBuilder.h"
11 #include "llvm/IR/LLVMContext.h"
12 #include "llvm/IR/LegacyPassManager.h"
13 #include "llvm/IR/Module.h"
14 #include "llvm/IR/Verifier.h"
15 #include "llvm/Support/Host.h"
16 #include "llvm/Support/TargetSelect.h"
17 #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 raw_ostream &indent(raw_ostream &O, int size) {
199 return O << std::string(size, ' ');
202 /// ExprAST - Base class for all expression nodes.
207 ExprAST(SourceLocation Loc = CurLoc) : Loc(Loc) {}
208 virtual ~ExprAST() {}
209 virtual Value *Codegen() = 0;
210 int getLine() const { return Loc.Line; }
211 int getCol() const { return Loc.Col; }
212 virtual raw_ostream &dump(raw_ostream &out, int ind) {
213 return out << ':' << getLine() << ':' << getCol() << '\n';
217 /// NumberExprAST - Expression class for numeric literals like "1.0".
218 class NumberExprAST : public ExprAST {
222 NumberExprAST(double Val) : Val(Val) {}
223 raw_ostream &dump(raw_ostream &out, int ind) override {
224 return ExprAST::dump(out << Val, ind);
226 Value *Codegen() override;
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 raw_ostream &dump(raw_ostream &out, int ind) override {
238 return ExprAST::dump(out << Name, ind);
240 Value *Codegen() override;
243 /// UnaryExprAST - Expression class for a unary operator.
244 class UnaryExprAST : public ExprAST {
246 std::unique_ptr<ExprAST> Operand;
249 UnaryExprAST(char Opcode, std::unique_ptr<ExprAST> Operand)
250 : Opcode(Opcode), Operand(std::move(Operand)) {}
251 raw_ostream &dump(raw_ostream &out, int ind) override {
252 ExprAST::dump(out << "unary" << Opcode, ind);
253 Operand->dump(out, ind + 1);
256 Value *Codegen() override;
259 /// BinaryExprAST - Expression class for a binary operator.
260 class BinaryExprAST : public ExprAST {
262 std::unique_ptr<ExprAST> LHS, RHS;
265 BinaryExprAST(SourceLocation Loc, char Op, std::unique_ptr<ExprAST> LHS,
266 std::unique_ptr<ExprAST> RHS)
267 : ExprAST(Loc), Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}
268 raw_ostream &dump(raw_ostream &out, int ind) override {
269 ExprAST::dump(out << "binary" << Op, ind);
270 LHS->dump(indent(out, ind) << "LHS:", ind + 1);
271 RHS->dump(indent(out, ind) << "RHS:", ind + 1);
274 Value *Codegen() override;
277 /// CallExprAST - Expression class for function calls.
278 class CallExprAST : public ExprAST {
280 std::vector<std::unique_ptr<ExprAST>> Args;
283 CallExprAST(SourceLocation Loc, const std::string &Callee,
284 std::vector<std::unique_ptr<ExprAST>> Args)
285 : ExprAST(Loc), Callee(Callee), Args(std::move(Args)) {}
286 raw_ostream &dump(raw_ostream &out, int ind) override {
287 ExprAST::dump(out << "call " << Callee, ind);
288 for (const auto &Arg : Args)
289 Arg->dump(indent(out, ind + 1), ind + 1);
292 Value *Codegen() override;
295 /// IfExprAST - Expression class for if/then/else.
296 class IfExprAST : public ExprAST {
297 std::unique_ptr<ExprAST> Cond, Then, Else;
300 IfExprAST(SourceLocation Loc, std::unique_ptr<ExprAST> Cond,
301 std::unique_ptr<ExprAST> Then, std::unique_ptr<ExprAST> Else)
302 : ExprAST(Loc), Cond(std::move(Cond)), Then(std::move(Then)),
303 Else(std::move(Else)) {}
304 raw_ostream &dump(raw_ostream &out, int ind) override {
305 ExprAST::dump(out << "if", ind);
306 Cond->dump(indent(out, ind) << "Cond:", ind + 1);
307 Then->dump(indent(out, ind) << "Then:", ind + 1);
308 Else->dump(indent(out, ind) << "Else:", ind + 1);
311 Value *Codegen() override;
314 /// ForExprAST - Expression class for for/in.
315 class ForExprAST : public ExprAST {
317 std::unique_ptr<ExprAST> Start, End, Step, Body;
320 ForExprAST(const std::string &VarName, std::unique_ptr<ExprAST> Start,
321 std::unique_ptr<ExprAST> End, std::unique_ptr<ExprAST> Step,
322 std::unique_ptr<ExprAST> Body)
323 : VarName(VarName), Start(std::move(Start)), End(std::move(End)),
324 Step(std::move(Step)), Body(std::move(Body)) {}
325 raw_ostream &dump(raw_ostream &out, int ind) override {
326 ExprAST::dump(out << "for", ind);
327 Start->dump(indent(out, ind) << "Cond:", ind + 1);
328 End->dump(indent(out, ind) << "End:", ind + 1);
329 Step->dump(indent(out, ind) << "Step:", ind + 1);
330 Body->dump(indent(out, ind) << "Body:", ind + 1);
333 Value *Codegen() override;
336 /// VarExprAST - Expression class for var/in
337 class VarExprAST : public ExprAST {
338 std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames;
339 std::unique_ptr<ExprAST> Body;
343 std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames,
344 std::unique_ptr<ExprAST> Body)
345 : VarNames(std::move(VarNames)), Body(std::move(Body)) {}
346 raw_ostream &dump(raw_ostream &out, int ind) override {
347 ExprAST::dump(out << "var", ind);
348 for (const auto &NamedVar : VarNames)
349 NamedVar.second->dump(indent(out, ind) << NamedVar.first << ':', ind + 1);
350 Body->dump(indent(out, ind) << "Body:", ind + 1);
353 Value *Codegen() override;
356 /// PrototypeAST - This class represents the "prototype" for a function,
357 /// which captures its name, and its argument names (thus implicitly the number
358 /// of arguments the function takes), as well as if it is an operator.
361 std::vector<std::string> Args;
363 unsigned Precedence; // Precedence if a binary op.
367 PrototypeAST(SourceLocation Loc, const std::string &Name,
368 std::vector<std::string> Args, bool IsOperator = false,
370 : Name(Name), Args(std::move(Args)), IsOperator(IsOperator),
371 Precedence(Prec), Line(Loc.Line) {}
373 bool isUnaryOp() const { return IsOperator && Args.size() == 1; }
374 bool isBinaryOp() const { return IsOperator && Args.size() == 2; }
376 char getOperatorName() const {
377 assert(isUnaryOp() || isBinaryOp());
378 return Name[Name.size() - 1];
381 unsigned getBinaryPrecedence() const { return Precedence; }
385 void CreateArgumentAllocas(Function *F);
386 const std::vector<std::string> &getArgs() const { return Args; }
389 /// FunctionAST - This class represents a function definition itself.
391 std::unique_ptr<PrototypeAST> Proto;
392 std::unique_ptr<ExprAST> Body;
395 FunctionAST(std::unique_ptr<PrototypeAST> Proto,
396 std::unique_ptr<ExprAST> Body)
397 : Proto(std::move(Proto)), Body(std::move(Body)) {}
399 raw_ostream &dump(raw_ostream &out, int ind) {
400 indent(out, ind) << "FunctionAST\n";
402 indent(out, ind) << "Body:";
403 return Body ? Body->dump(out, ind) : out << "null\n";
408 } // end anonymous namespace
410 //===----------------------------------------------------------------------===//
412 //===----------------------------------------------------------------------===//
414 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
415 /// token the parser is looking at. getNextToken reads another token from the
416 /// lexer and updates CurTok with its results.
418 static int getNextToken() { return CurTok = gettok(); }
420 /// BinopPrecedence - This holds the precedence for each binary operator that is
422 static std::map<char, int> BinopPrecedence;
424 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
425 static int GetTokPrecedence() {
426 if (!isascii(CurTok))
429 // Make sure it's a declared binop.
430 int TokPrec = BinopPrecedence[CurTok];
436 /// Error* - These are little helper functions for error handling.
437 std::unique_ptr<ExprAST> Error(const char *Str) {
438 fprintf(stderr, "Error: %s\n", Str);
441 std::unique_ptr<PrototypeAST> ErrorP(const char *Str) {
445 std::unique_ptr<FunctionAST> ErrorF(const char *Str) {
450 static std::unique_ptr<ExprAST> ParseExpression();
452 /// numberexpr ::= number
453 static std::unique_ptr<ExprAST> ParseNumberExpr() {
454 auto Result = llvm::make_unique<NumberExprAST>(NumVal);
455 getNextToken(); // consume the number
456 return std::move(Result);
459 /// parenexpr ::= '(' expression ')'
460 static std::unique_ptr<ExprAST> ParseParenExpr() {
461 getNextToken(); // eat (.
462 auto V = ParseExpression();
467 return Error("expected ')'");
468 getNextToken(); // eat ).
474 /// ::= identifier '(' expression* ')'
475 static std::unique_ptr<ExprAST> ParseIdentifierExpr() {
476 std::string IdName = IdentifierStr;
478 SourceLocation LitLoc = CurLoc;
480 getNextToken(); // eat identifier.
482 if (CurTok != '(') // Simple variable ref.
483 return llvm::make_unique<VariableExprAST>(LitLoc, IdName);
486 getNextToken(); // eat (
487 std::vector<std::unique_ptr<ExprAST>> Args;
490 if (auto Arg = ParseExpression())
491 Args.push_back(std::move(Arg));
499 return Error("Expected ')' or ',' in argument list");
507 return llvm::make_unique<CallExprAST>(LitLoc, IdName, std::move(Args));
510 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
511 static std::unique_ptr<ExprAST> ParseIfExpr() {
512 SourceLocation IfLoc = CurLoc;
514 getNextToken(); // eat the if.
517 auto Cond = ParseExpression();
521 if (CurTok != tok_then)
522 return Error("expected then");
523 getNextToken(); // eat the then
525 auto Then = ParseExpression();
529 if (CurTok != tok_else)
530 return Error("expected else");
534 auto Else = ParseExpression();
538 return llvm::make_unique<IfExprAST>(IfLoc, std::move(Cond), std::move(Then),
542 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
543 static std::unique_ptr<ExprAST> ParseForExpr() {
544 getNextToken(); // eat the for.
546 if (CurTok != tok_identifier)
547 return Error("expected identifier after for");
549 std::string IdName = IdentifierStr;
550 getNextToken(); // eat identifier.
553 return Error("expected '=' after for");
554 getNextToken(); // eat '='.
556 auto Start = ParseExpression();
560 return Error("expected ',' after for start value");
563 auto End = ParseExpression();
567 // The step value is optional.
568 std::unique_ptr<ExprAST> Step;
571 Step = ParseExpression();
576 if (CurTok != tok_in)
577 return Error("expected 'in' after for");
578 getNextToken(); // eat 'in'.
580 auto Body = ParseExpression();
584 return llvm::make_unique<ForExprAST>(IdName, std::move(Start), std::move(End),
585 std::move(Step), std::move(Body));
588 /// varexpr ::= 'var' identifier ('=' expression)?
589 // (',' identifier ('=' expression)?)* 'in' expression
590 static std::unique_ptr<ExprAST> ParseVarExpr() {
591 getNextToken(); // eat the var.
593 std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames;
595 // At least one variable name is required.
596 if (CurTok != tok_identifier)
597 return Error("expected identifier after var");
600 std::string Name = IdentifierStr;
601 getNextToken(); // eat identifier.
603 // Read the optional initializer.
604 std::unique_ptr<ExprAST> Init = nullptr;
606 getNextToken(); // eat the '='.
608 Init = ParseExpression();
613 VarNames.push_back(std::make_pair(Name, std::move(Init)));
615 // End of var list, exit loop.
618 getNextToken(); // eat the ','.
620 if (CurTok != tok_identifier)
621 return Error("expected identifier list after var");
624 // At this point, we have to have 'in'.
625 if (CurTok != tok_in)
626 return Error("expected 'in' keyword after 'var'");
627 getNextToken(); // eat 'in'.
629 auto Body = ParseExpression();
633 return llvm::make_unique<VarExprAST>(std::move(VarNames), std::move(Body));
637 /// ::= identifierexpr
643 static std::unique_ptr<ExprAST> ParsePrimary() {
646 return Error("unknown token when expecting an expression");
648 return ParseIdentifierExpr();
650 return ParseNumberExpr();
652 return ParseParenExpr();
654 return ParseIfExpr();
656 return ParseForExpr();
658 return ParseVarExpr();
665 static std::unique_ptr<ExprAST> ParseUnary() {
666 // If the current token is not an operator, it must be a primary expr.
667 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
668 return ParsePrimary();
670 // If this is a unary operator, read it.
673 if (auto Operand = ParseUnary())
674 return llvm::make_unique<UnaryExprAST>(Opc, std::move(Operand));
680 static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
681 std::unique_ptr<ExprAST> LHS) {
682 // If this is a binop, find its precedence.
684 int TokPrec = GetTokPrecedence();
686 // If this is a binop that binds at least as tightly as the current binop,
687 // consume it, otherwise we are done.
688 if (TokPrec < ExprPrec)
691 // Okay, we know this is a binop.
693 SourceLocation BinLoc = CurLoc;
694 getNextToken(); // eat binop
696 // Parse the unary expression after the binary operator.
697 auto RHS = ParseUnary();
701 // If BinOp binds less tightly with RHS than the operator after RHS, let
702 // the pending operator take RHS as its LHS.
703 int NextPrec = GetTokPrecedence();
704 if (TokPrec < NextPrec) {
705 RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS));
711 LHS = llvm::make_unique<BinaryExprAST>(BinLoc, BinOp, std::move(LHS),
717 /// ::= unary binoprhs
719 static std::unique_ptr<ExprAST> ParseExpression() {
720 auto LHS = ParseUnary();
724 return ParseBinOpRHS(0, std::move(LHS));
728 /// ::= id '(' id* ')'
729 /// ::= binary LETTER number? (id, id)
730 /// ::= unary LETTER (id)
731 static std::unique_ptr<PrototypeAST> ParsePrototype() {
734 SourceLocation FnLoc = CurLoc;
736 unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
737 unsigned BinaryPrecedence = 30;
741 return ErrorP("Expected function name in prototype");
743 FnName = IdentifierStr;
749 if (!isascii(CurTok))
750 return ErrorP("Expected unary operator");
752 FnName += (char)CurTok;
758 if (!isascii(CurTok))
759 return ErrorP("Expected binary operator");
761 FnName += (char)CurTok;
765 // Read the precedence if present.
766 if (CurTok == tok_number) {
767 if (NumVal < 1 || NumVal > 100)
768 return ErrorP("Invalid precedecnce: must be 1..100");
769 BinaryPrecedence = (unsigned)NumVal;
776 return ErrorP("Expected '(' in prototype");
778 std::vector<std::string> ArgNames;
779 while (getNextToken() == tok_identifier)
780 ArgNames.push_back(IdentifierStr);
782 return ErrorP("Expected ')' in prototype");
785 getNextToken(); // eat ')'.
787 // Verify right number of names for operator.
788 if (Kind && ArgNames.size() != Kind)
789 return ErrorP("Invalid number of operands for operator");
791 return llvm::make_unique<PrototypeAST>(FnLoc, FnName, ArgNames, Kind != 0,
795 /// definition ::= 'def' prototype expression
796 static std::unique_ptr<FunctionAST> ParseDefinition() {
797 getNextToken(); // eat def.
798 auto Proto = ParsePrototype();
802 if (auto E = ParseExpression())
803 return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E));
807 /// toplevelexpr ::= expression
808 static std::unique_ptr<FunctionAST> ParseTopLevelExpr() {
809 SourceLocation FnLoc = CurLoc;
810 if (auto E = ParseExpression()) {
811 // Make an anonymous proto.
812 auto Proto = llvm::make_unique<PrototypeAST>(FnLoc, "main",
813 std::vector<std::string>());
814 return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E));
819 /// external ::= 'extern' prototype
820 static std::unique_ptr<PrototypeAST> ParseExtern() {
821 getNextToken(); // eat extern.
822 return ParsePrototype();
825 //===----------------------------------------------------------------------===//
826 // Debug Info Support
827 //===----------------------------------------------------------------------===//
829 static DIBuilder *DBuilder;
831 DIType *DebugInfo::getDoubleTy() {
835 DblTy = DBuilder->createBasicType("double", 64, 64, dwarf::DW_ATE_float);
839 void DebugInfo::emitLocation(ExprAST *AST) {
841 return Builder.SetCurrentDebugLocation(DebugLoc());
843 if (LexicalBlocks.empty())
846 Scope = LexicalBlocks.back();
847 Builder.SetCurrentDebugLocation(
848 DebugLoc::get(AST->getLine(), AST->getCol(), Scope));
851 static DISubroutineType *CreateFunctionType(unsigned NumArgs, DIFile *Unit) {
852 SmallVector<Metadata *, 8> EltTys;
853 DIType *DblTy = KSDbgInfo.getDoubleTy();
855 // Add the result type.
856 EltTys.push_back(DblTy);
858 for (unsigned i = 0, e = NumArgs; i != e; ++i)
859 EltTys.push_back(DblTy);
861 return DBuilder->createSubroutineType(Unit,
862 DBuilder->getOrCreateTypeArray(EltTys));
865 //===----------------------------------------------------------------------===//
867 //===----------------------------------------------------------------------===//
869 static Module *TheModule;
870 static std::map<std::string, AllocaInst *> NamedValues;
871 static legacy::FunctionPassManager *TheFPM;
873 Value *ErrorV(const char *Str) {
878 /// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
879 /// the function. This is used for mutable variables etc.
880 static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,
881 const std::string &VarName) {
882 IRBuilder<> TmpB(&TheFunction->getEntryBlock(),
883 TheFunction->getEntryBlock().begin());
884 return TmpB.CreateAlloca(Type::getDoubleTy(getGlobalContext()), 0,
888 Value *NumberExprAST::Codegen() {
889 KSDbgInfo.emitLocation(this);
890 return ConstantFP::get(getGlobalContext(), APFloat(Val));
893 Value *VariableExprAST::Codegen() {
894 // Look this variable up in the function.
895 Value *V = NamedValues[Name];
897 return ErrorV("Unknown variable name");
899 KSDbgInfo.emitLocation(this);
901 return Builder.CreateLoad(V, Name.c_str());
904 Value *UnaryExprAST::Codegen() {
905 Value *OperandV = Operand->Codegen();
909 Function *F = TheModule->getFunction(std::string("unary") + Opcode);
911 return ErrorV("Unknown unary operator");
913 KSDbgInfo.emitLocation(this);
914 return Builder.CreateCall(F, OperandV, "unop");
917 Value *BinaryExprAST::Codegen() {
918 KSDbgInfo.emitLocation(this);
920 // Special case '=' because we don't want to emit the LHS as an expression.
922 // Assignment requires the LHS to be an identifier.
923 // This assume we're building without RTTI because LLVM builds that way by
924 // default. If you build LLVM with RTTI this can be changed to a
925 // dynamic_cast for automatic error checking.
926 VariableExprAST *LHSE = static_cast<VariableExprAST *>(LHS.get());
928 return ErrorV("destination of '=' must be a variable");
930 Value *Val = RHS->Codegen();
935 Value *Variable = NamedValues[LHSE->getName()];
937 return ErrorV("Unknown variable name");
939 Builder.CreateStore(Val, Variable);
943 Value *L = LHS->Codegen();
944 Value *R = RHS->Codegen();
950 return Builder.CreateFAdd(L, R, "addtmp");
952 return Builder.CreateFSub(L, R, "subtmp");
954 return Builder.CreateFMul(L, R, "multmp");
956 L = Builder.CreateFCmpULT(L, R, "cmptmp");
957 // Convert bool 0/1 to double 0.0 or 1.0
958 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
964 // If it wasn't a builtin binary operator, it must be a user defined one. Emit
966 Function *F = TheModule->getFunction(std::string("binary") + Op);
967 assert(F && "binary operator not found!");
969 Value *Ops[] = {L, R};
970 return Builder.CreateCall(F, Ops, "binop");
973 Value *CallExprAST::Codegen() {
974 KSDbgInfo.emitLocation(this);
976 // Look up the name in the global module table.
977 Function *CalleeF = TheModule->getFunction(Callee);
979 return ErrorV("Unknown function referenced");
981 // If argument mismatch error.
982 if (CalleeF->arg_size() != Args.size())
983 return ErrorV("Incorrect # arguments passed");
985 std::vector<Value *> ArgsV;
986 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
987 ArgsV.push_back(Args[i]->Codegen());
992 return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
995 Value *IfExprAST::Codegen() {
996 KSDbgInfo.emitLocation(this);
998 Value *CondV = Cond->Codegen();
1002 // Convert condition to a bool by comparing equal to 0.0.
1003 CondV = Builder.CreateFCmpONE(
1004 CondV, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "ifcond");
1006 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1008 // Create blocks for the then and else cases. Insert the 'then' block at the
1009 // end of the function.
1010 BasicBlock *ThenBB =
1011 BasicBlock::Create(getGlobalContext(), "then", TheFunction);
1012 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
1013 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
1015 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1018 Builder.SetInsertPoint(ThenBB);
1020 Value *ThenV = Then->Codegen();
1024 Builder.CreateBr(MergeBB);
1025 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1026 ThenBB = Builder.GetInsertBlock();
1029 TheFunction->getBasicBlockList().push_back(ElseBB);
1030 Builder.SetInsertPoint(ElseBB);
1032 Value *ElseV = Else->Codegen();
1036 Builder.CreateBr(MergeBB);
1037 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1038 ElseBB = Builder.GetInsertBlock();
1040 // Emit merge block.
1041 TheFunction->getBasicBlockList().push_back(MergeBB);
1042 Builder.SetInsertPoint(MergeBB);
1044 Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, "iftmp");
1046 PN->addIncoming(ThenV, ThenBB);
1047 PN->addIncoming(ElseV, ElseBB);
1051 // Output for-loop as:
1052 // var = alloca double
1054 // start = startexpr
1055 // store start -> var
1063 // endcond = endexpr
1065 // curvar = load var
1066 // nextvar = curvar + step
1067 // store nextvar -> var
1068 // br endcond, loop, endloop
1070 Value *ForExprAST::Codegen() {
1071 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1073 // Create an alloca for the variable in the entry block.
1074 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
1076 KSDbgInfo.emitLocation(this);
1078 // Emit the start code first, without 'variable' in scope.
1079 Value *StartVal = Start->Codegen();
1083 // Store the value into the alloca.
1084 Builder.CreateStore(StartVal, Alloca);
1086 // Make the new basic block for the loop header, inserting after current
1088 BasicBlock *LoopBB =
1089 BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
1091 // Insert an explicit fall through from the current block to the LoopBB.
1092 Builder.CreateBr(LoopBB);
1094 // Start insertion in LoopBB.
1095 Builder.SetInsertPoint(LoopBB);
1097 // Within the loop, the variable is defined equal to the PHI node. If it
1098 // shadows an existing variable, we have to restore it, so save it now.
1099 AllocaInst *OldVal = NamedValues[VarName];
1100 NamedValues[VarName] = Alloca;
1102 // Emit the body of the loop. This, like any other expr, can change the
1103 // current BB. Note that we ignore the value computed by the body, but don't
1105 if (!Body->Codegen())
1108 // Emit the step value.
1109 Value *StepVal = nullptr;
1111 StepVal = Step->Codegen();
1115 // If not specified, use 1.0.
1116 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
1119 // Compute the end condition.
1120 Value *EndCond = End->Codegen();
1124 // Reload, increment, and restore the alloca. This handles the case where
1125 // the body of the loop mutates the variable.
1126 Value *CurVar = Builder.CreateLoad(Alloca, VarName.c_str());
1127 Value *NextVar = Builder.CreateFAdd(CurVar, StepVal, "nextvar");
1128 Builder.CreateStore(NextVar, Alloca);
1130 // Convert condition to a bool by comparing equal to 0.0.
1131 EndCond = Builder.CreateFCmpONE(
1132 EndCond, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "loopcond");
1134 // Create the "after loop" block and insert it.
1135 BasicBlock *AfterBB =
1136 BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
1138 // Insert the conditional branch into the end of LoopEndBB.
1139 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1141 // Any new code will be inserted in AfterBB.
1142 Builder.SetInsertPoint(AfterBB);
1144 // Restore the unshadowed variable.
1146 NamedValues[VarName] = OldVal;
1148 NamedValues.erase(VarName);
1150 // for expr always returns 0.0.
1151 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
1154 Value *VarExprAST::Codegen() {
1155 std::vector<AllocaInst *> OldBindings;
1157 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1159 // Register all variables and emit their initializer.
1160 for (unsigned i = 0, e = VarNames.size(); i != e; ++i) {
1161 const std::string &VarName = VarNames[i].first;
1162 ExprAST *Init = VarNames[i].second.get();
1164 // Emit the initializer before adding the variable to scope, this prevents
1165 // the initializer from referencing the variable itself, and permits stuff
1168 // var a = a in ... # refers to outer 'a'.
1171 InitVal = Init->Codegen();
1174 } else { // If not specified, use 0.0.
1175 InitVal = ConstantFP::get(getGlobalContext(), APFloat(0.0));
1178 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
1179 Builder.CreateStore(InitVal, Alloca);
1181 // Remember the old variable binding so that we can restore the binding when
1183 OldBindings.push_back(NamedValues[VarName]);
1185 // Remember this binding.
1186 NamedValues[VarName] = Alloca;
1189 KSDbgInfo.emitLocation(this);
1191 // Codegen the body, now that all vars are in scope.
1192 Value *BodyVal = Body->Codegen();
1196 // Pop all our variables from scope.
1197 for (unsigned i = 0, e = VarNames.size(); i != e; ++i)
1198 NamedValues[VarNames[i].first] = OldBindings[i];
1200 // Return the body computation.
1204 Function *PrototypeAST::Codegen() {
1205 // Make the function type: double(double,double) etc.
1206 std::vector<Type *> Doubles(Args.size(),
1207 Type::getDoubleTy(getGlobalContext()));
1209 FunctionType::get(Type::getDoubleTy(getGlobalContext()), Doubles, false);
1212 Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
1214 // If F conflicted, there was already something named 'Name'. If it has a
1215 // body, don't allow redefinition or reextern.
1216 if (F->getName() != Name) {
1217 // Delete the one we just made and get the existing one.
1218 F->eraseFromParent();
1219 F = TheModule->getFunction(Name);
1221 // If F already has a body, reject this.
1223 ErrorF("redefinition of function");
1227 // If F took a different number of args, reject.
1228 if (F->arg_size() != Args.size()) {
1229 ErrorF("redefinition of function with different # args");
1234 // Set names for all arguments.
1236 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1238 AI->setName(Args[Idx]);
1240 // Create a subprogram DIE for this function.
1241 DIFile *Unit = DBuilder->createFile(KSDbgInfo.TheCU->getFilename(),
1242 KSDbgInfo.TheCU->getDirectory());
1243 DIScope *FContext = Unit;
1244 unsigned LineNo = Line;
1245 unsigned ScopeLine = Line;
1246 DISubprogram *SP = DBuilder->createFunction(
1247 FContext, Name, StringRef(), Unit, LineNo,
1248 CreateFunctionType(Args.size(), Unit), false /* internal linkage */,
1249 true /* definition */, ScopeLine, DINode::FlagPrototyped, false, F);
1251 KSDbgInfo.FnScopeMap[this] = SP;
1255 /// CreateArgumentAllocas - Create an alloca for each argument and register the
1256 /// argument in the symbol table so that references to it will succeed.
1257 void PrototypeAST::CreateArgumentAllocas(Function *F) {
1258 Function::arg_iterator AI = F->arg_begin();
1259 for (unsigned Idx = 0, e = Args.size(); Idx != e; ++Idx, ++AI) {
1260 // Create an alloca for this variable.
1261 AllocaInst *Alloca = CreateEntryBlockAlloca(F, Args[Idx]);
1263 // Create a debug descriptor for the variable.
1264 DIScope *Scope = KSDbgInfo.LexicalBlocks.back();
1265 DIFile *Unit = DBuilder->createFile(KSDbgInfo.TheCU->getFilename(),
1266 KSDbgInfo.TheCU->getDirectory());
1267 DILocalVariable *D = DBuilder->createParameterVariable(
1268 Scope, Args[Idx], Idx + 1, Unit, Line, KSDbgInfo.getDoubleTy(), true);
1270 DBuilder->insertDeclare(Alloca, D, DBuilder->createExpression(),
1271 DebugLoc::get(Line, 0, Scope),
1272 Builder.GetInsertBlock());
1274 // Store the initial value into the alloca.
1275 Builder.CreateStore(AI, Alloca);
1277 // Add arguments to variable symbol table.
1278 NamedValues[Args[Idx]] = Alloca;
1282 Function *FunctionAST::Codegen() {
1283 NamedValues.clear();
1285 Function *TheFunction = Proto->Codegen();
1289 // Push the current scope.
1290 KSDbgInfo.LexicalBlocks.push_back(KSDbgInfo.FnScopeMap[Proto.get()]);
1292 // Unset the location for the prologue emission (leading instructions with no
1293 // location in a function are considered part of the prologue and the debugger
1294 // will run past them when breaking on a function)
1295 KSDbgInfo.emitLocation(nullptr);
1297 // If this is an operator, install it.
1298 if (Proto->isBinaryOp())
1299 BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence();
1301 // Create a new basic block to start insertion into.
1302 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1303 Builder.SetInsertPoint(BB);
1305 // Add all arguments to the symbol table and create their allocas.
1306 Proto->CreateArgumentAllocas(TheFunction);
1308 KSDbgInfo.emitLocation(Body.get());
1310 if (Value *RetVal = Body->Codegen()) {
1311 // Finish off the function.
1312 Builder.CreateRet(RetVal);
1314 // Pop off the lexical block for the function.
1315 KSDbgInfo.LexicalBlocks.pop_back();
1317 // Validate the generated code, checking for consistency.
1318 verifyFunction(*TheFunction);
1320 // Optimize the function.
1321 TheFPM->run(*TheFunction);
1326 // Error reading body, remove function.
1327 TheFunction->eraseFromParent();
1329 if (Proto->isBinaryOp())
1330 BinopPrecedence.erase(Proto->getOperatorName());
1332 // Pop off the lexical block for the function since we added it
1334 KSDbgInfo.LexicalBlocks.pop_back();
1339 //===----------------------------------------------------------------------===//
1340 // Top-Level parsing and JIT Driver
1341 //===----------------------------------------------------------------------===//
1343 static ExecutionEngine *TheExecutionEngine;
1345 static void HandleDefinition() {
1346 if (auto FnAST = ParseDefinition()) {
1347 if (!FnAST->Codegen()) {
1348 fprintf(stderr, "Error reading function definition:");
1351 // Skip token for error recovery.
1356 static void HandleExtern() {
1357 if (auto ProtoAST = ParseExtern()) {
1358 if (!ProtoAST->Codegen()) {
1359 fprintf(stderr, "Error reading extern");
1362 // Skip token for error recovery.
1367 static void HandleTopLevelExpression() {
1368 // Evaluate a top-level expression into an anonymous function.
1369 if (auto FnAST = ParseTopLevelExpr()) {
1370 if (!FnAST->Codegen()) {
1371 fprintf(stderr, "Error generating code for top level expr");
1374 // Skip token for error recovery.
1379 /// top ::= definition | external | expression | ';'
1380 static void MainLoop() {
1385 case ';': // ignore top-level semicolons.
1395 HandleTopLevelExpression();
1401 //===----------------------------------------------------------------------===//
1402 // "Library" functions that can be "extern'd" from user code.
1403 //===----------------------------------------------------------------------===//
1405 /// putchard - putchar that takes a double and returns 0.
1406 extern "C" double putchard(double X) {
1411 /// printd - printf that takes a double prints it as "%f\n", returning 0.
1412 extern "C" double printd(double X) {
1417 //===----------------------------------------------------------------------===//
1418 // Main driver code.
1419 //===----------------------------------------------------------------------===//
1422 InitializeNativeTarget();
1423 InitializeNativeTargetAsmPrinter();
1424 InitializeNativeTargetAsmParser();
1425 LLVMContext &Context = getGlobalContext();
1427 // Install standard binary operators.
1428 // 1 is lowest precedence.
1429 BinopPrecedence['='] = 2;
1430 BinopPrecedence['<'] = 10;
1431 BinopPrecedence['+'] = 20;
1432 BinopPrecedence['-'] = 20;
1433 BinopPrecedence['*'] = 40; // highest.
1435 // Prime the first token.
1438 // Make the module, which holds all the code.
1439 std::unique_ptr<Module> Owner = make_unique<Module>("my cool jit", Context);
1440 TheModule = Owner.get();
1442 // Add the current debug info version into the module.
1443 TheModule->addModuleFlag(Module::Warning, "Debug Info Version",
1444 DEBUG_METADATA_VERSION);
1446 // Darwin only supports dwarf2.
1447 if (Triple(sys::getProcessTriple()).isOSDarwin())
1448 TheModule->addModuleFlag(llvm::Module::Warning, "Dwarf Version", 2);
1450 // Construct the DIBuilder, we do this here because we need the module.
1451 DBuilder = new DIBuilder(*TheModule);
1453 // Create the compile unit for the module.
1454 // Currently down as "fib.ks" as a filename since we're redirecting stdin
1455 // but we'd like actual source locations.
1456 KSDbgInfo.TheCU = DBuilder->createCompileUnit(
1457 dwarf::DW_LANG_C, "fib.ks", ".", "Kaleidoscope Compiler", 0, "", 0);
1459 // Create the JIT. This takes ownership of the module.
1461 TheExecutionEngine =
1462 EngineBuilder(std::move(Owner))
1463 .setErrorStr(&ErrStr)
1464 .setMCJITMemoryManager(llvm::make_unique<SectionMemoryManager>())
1466 if (!TheExecutionEngine) {
1467 fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
1471 legacy::FunctionPassManager OurFPM(TheModule);
1473 // Set up the optimizer pipeline. Start with registering info about how the
1474 // target lays out data structures.
1475 TheModule->setDataLayout(TheExecutionEngine->getDataLayout());
1477 // Provide basic AliasAnalysis support for GVN.
1478 OurFPM.add(createBasicAliasAnalysisPass());
1479 // Promote allocas to registers.
1480 OurFPM.add(createPromoteMemoryToRegisterPass());
1481 // Do simple "peephole" optimizations and bit-twiddling optzns.
1482 OurFPM.add(createInstructionCombiningPass());
1483 // Reassociate expressions.
1484 OurFPM.add(createReassociatePass());
1485 // Eliminate Common SubExpressions.
1486 OurFPM.add(createGVNPass());
1487 // Simplify the control flow graph (deleting unreachable blocks, etc).
1488 OurFPM.add(createCFGSimplificationPass());
1490 OurFPM.doInitialization();
1492 // Set the global so the code gen can use this.
1495 // Run the main "interpreter loop" now.
1500 // Finalize the debug info.
1501 DBuilder->finalize();
1503 // Print out all of the generated code.