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