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 LLVMContext TheContext;
607 static IRBuilder<> Builder(TheContext);
608 static std::map<std::string, Value *> NamedValues;
609 static std::unique_ptr<legacy::FunctionPassManager> TheFPM;
610 static std::unique_ptr<KaleidoscopeJIT> TheJIT;
611 static std::map<std::string, std::unique_ptr<PrototypeAST>> FunctionProtos;
612 
613 Value *LogErrorV(const char *Str) {
614   LogError(Str);
615   return nullptr;
616 }
617 
618 Function *getFunction(std::string Name) {
619   // First, see if the function has already been added to the current module.
620   if (auto *F = TheModule->getFunction(Name))
621     return F;
622 
623   // If not, check whether we can codegen the declaration from some existing
624   // prototype.
625   auto FI = FunctionProtos.find(Name);
626   if (FI != FunctionProtos.end())
627     return FI->second->codegen();
628 
629   // If no existing prototype exists, return null.
630   return nullptr;
631 }
632 
633 Value *NumberExprAST::codegen() {
634   return ConstantFP::get(TheContext, APFloat(Val));
635 }
636 
637 Value *VariableExprAST::codegen() {
638   // Look this variable up in the function.
639   Value *V = NamedValues[Name];
640   if (!V)
641     return LogErrorV("Unknown variable name");
642   return V;
643 }
644 
645 Value *UnaryExprAST::codegen() {
646   Value *OperandV = Operand->codegen();
647   if (!OperandV)
648     return nullptr;
649 
650   Function *F = getFunction(std::string("unary") + Opcode);
651   if (!F)
652     return LogErrorV("Unknown unary operator");
653 
654   return Builder.CreateCall(F, OperandV, "unop");
655 }
656 
657 Value *BinaryExprAST::codegen() {
658   Value *L = LHS->codegen();
659   Value *R = RHS->codegen();
660   if (!L || !R)
661     return nullptr;
662 
663   switch (Op) {
664   case '+':
665     return Builder.CreateFAdd(L, R, "addtmp");
666   case '-':
667     return Builder.CreateFSub(L, R, "subtmp");
668   case '*':
669     return Builder.CreateFMul(L, R, "multmp");
670   case '<':
671     L = Builder.CreateFCmpULT(L, R, "cmptmp");
672     // Convert bool 0/1 to double 0.0 or 1.0
673     return Builder.CreateUIToFP(L, Type::getDoubleTy(TheContext), "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(TheContext, 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 = BasicBlock::Create(TheContext, "then", TheFunction);
721   BasicBlock *ElseBB = BasicBlock::Create(TheContext, "else");
722   BasicBlock *MergeBB = BasicBlock::Create(TheContext, "ifcont");
723 
724   Builder.CreateCondBr(CondV, ThenBB, ElseBB);
725 
726   // Emit then value.
727   Builder.SetInsertPoint(ThenBB);
728 
729   Value *ThenV = Then->codegen();
730   if (!ThenV)
731     return nullptr;
732 
733   Builder.CreateBr(MergeBB);
734   // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
735   ThenBB = Builder.GetInsertBlock();
736 
737   // Emit else block.
738   TheFunction->getBasicBlockList().push_back(ElseBB);
739   Builder.SetInsertPoint(ElseBB);
740 
741   Value *ElseV = Else->codegen();
742   if (!ElseV)
743     return nullptr;
744 
745   Builder.CreateBr(MergeBB);
746   // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
747   ElseBB = Builder.GetInsertBlock();
748 
749   // Emit merge block.
750   TheFunction->getBasicBlockList().push_back(MergeBB);
751   Builder.SetInsertPoint(MergeBB);
752   PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(TheContext), 2, "iftmp");
753 
754   PN->addIncoming(ThenV, ThenBB);
755   PN->addIncoming(ElseV, ElseBB);
756   return PN;
757 }
758 
759 // Output for-loop as:
760 //   ...
761 //   start = startexpr
762 //   goto loop
763 // loop:
764 //   variable = phi [start, loopheader], [nextvariable, loopend]
765 //   ...
766 //   bodyexpr
767 //   ...
768 // loopend:
769 //   step = stepexpr
770 //   nextvariable = variable + step
771 //   endcond = endexpr
772 //   br endcond, loop, endloop
773 // outloop:
774 Value *ForExprAST::codegen() {
775   // Emit the start code first, without 'variable' in scope.
776   Value *StartVal = Start->codegen();
777   if (!StartVal)
778     return nullptr;
779 
780   // Make the new basic block for the loop header, inserting after current
781   // block.
782   Function *TheFunction = Builder.GetInsertBlock()->getParent();
783   BasicBlock *PreheaderBB = Builder.GetInsertBlock();
784   BasicBlock *LoopBB = BasicBlock::Create(TheContext, "loop", TheFunction);
785 
786   // Insert an explicit fall through from the current block to the LoopBB.
787   Builder.CreateBr(LoopBB);
788 
789   // Start insertion in LoopBB.
790   Builder.SetInsertPoint(LoopBB);
791 
792   // Start the PHI node with an entry for Start.
793   PHINode *Variable =
794       Builder.CreatePHI(Type::getDoubleTy(TheContext), 2, VarName.c_str());
795   Variable->addIncoming(StartVal, PreheaderBB);
796 
797   // Within the loop, the variable is defined equal to the PHI node.  If it
798   // shadows an existing variable, we have to restore it, so save it now.
799   Value *OldVal = NamedValues[VarName];
800   NamedValues[VarName] = Variable;
801 
802   // Emit the body of the loop.  This, like any other expr, can change the
803   // current BB.  Note that we ignore the value computed by the body, but don't
804   // allow an error.
805   if (!Body->codegen())
806     return nullptr;
807 
808   // Emit the step value.
809   Value *StepVal = nullptr;
810   if (Step) {
811     StepVal = Step->codegen();
812     if (!StepVal)
813       return nullptr;
814   } else {
815     // If not specified, use 1.0.
816     StepVal = ConstantFP::get(TheContext, APFloat(1.0));
817   }
818 
819   Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");
820 
821   // Compute the end condition.
822   Value *EndCond = End->codegen();
823   if (!EndCond)
824     return nullptr;
825 
826   // Convert condition to a bool by comparing equal to 0.0.
827   EndCond = Builder.CreateFCmpONE(
828       EndCond, ConstantFP::get(TheContext, APFloat(0.0)), "loopcond");
829 
830   // Create the "after loop" block and insert it.
831   BasicBlock *LoopEndBB = Builder.GetInsertBlock();
832   BasicBlock *AfterBB =
833       BasicBlock::Create(TheContext, "afterloop", TheFunction);
834 
835   // Insert the conditional branch into the end of LoopEndBB.
836   Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
837 
838   // Any new code will be inserted in AfterBB.
839   Builder.SetInsertPoint(AfterBB);
840 
841   // Add a new entry to the PHI node for the backedge.
842   Variable->addIncoming(NextVar, LoopEndBB);
843 
844   // Restore the unshadowed variable.
845   if (OldVal)
846     NamedValues[VarName] = OldVal;
847   else
848     NamedValues.erase(VarName);
849 
850   // for expr always returns 0.0.
851   return Constant::getNullValue(Type::getDoubleTy(TheContext));
852 }
853 
854 Function *PrototypeAST::codegen() {
855   // Make the function type:  double(double,double) etc.
856   std::vector<Type *> Doubles(Args.size(), Type::getDoubleTy(TheContext));
857   FunctionType *FT =
858       FunctionType::get(Type::getDoubleTy(TheContext), Doubles, false);
859 
860   Function *F =
861       Function::Create(FT, Function::ExternalLinkage, Name, TheModule.get());
862 
863   // Set names for all arguments.
864   unsigned Idx = 0;
865   for (auto &Arg : F->args())
866     Arg.setName(Args[Idx++]);
867 
868   return F;
869 }
870 
871 Function *FunctionAST::codegen() {
872   // Transfer ownership of the prototype to the FunctionProtos map, but keep a
873   // reference to it for use below.
874   auto &P = *Proto;
875   FunctionProtos[Proto->getName()] = std::move(Proto);
876   Function *TheFunction = getFunction(P.getName());
877   if (!TheFunction)
878     return nullptr;
879 
880   // If this is an operator, install it.
881   if (P.isBinaryOp())
882     BinopPrecedence[P.getOperatorName()] = P.getBinaryPrecedence();
883 
884   // Create a new basic block to start insertion into.
885   BasicBlock *BB = BasicBlock::Create(TheContext, "entry", TheFunction);
886   Builder.SetInsertPoint(BB);
887 
888   // Record the function arguments in the NamedValues map.
889   NamedValues.clear();
890   for (auto &Arg : TheFunction->args())
891     NamedValues[Arg.getName()] = &Arg;
892 
893   if (Value *RetVal = Body->codegen()) {
894     // Finish off the function.
895     Builder.CreateRet(RetVal);
896 
897     // Validate the generated code, checking for consistency.
898     verifyFunction(*TheFunction);
899 
900     // Run the optimizer on the function.
901     TheFPM->run(*TheFunction);
902 
903     return TheFunction;
904   }
905 
906   // Error reading body, remove function.
907   TheFunction->eraseFromParent();
908 
909   if (P.isBinaryOp())
910     BinopPrecedence.erase(Proto->getOperatorName());
911   return nullptr;
912 }
913 
914 //===----------------------------------------------------------------------===//
915 // Top-Level parsing and JIT Driver
916 //===----------------------------------------------------------------------===//
917 
918 static void InitializeModuleAndPassManager() {
919   // Open a new module.
920   TheModule = llvm::make_unique<Module>("my cool jit", TheContext);
921   TheModule->setDataLayout(TheJIT->getTargetMachine().createDataLayout());
922 
923   // Create a new pass manager attached to it.
924   TheFPM = llvm::make_unique<legacy::FunctionPassManager>(TheModule.get());
925 
926   // Do simple "peephole" optimizations and bit-twiddling optzns.
927   TheFPM->add(createInstructionCombiningPass());
928   // Reassociate expressions.
929   TheFPM->add(createReassociatePass());
930   // Eliminate Common SubExpressions.
931   TheFPM->add(createGVNPass());
932   // Simplify the control flow graph (deleting unreachable blocks, etc).
933   TheFPM->add(createCFGSimplificationPass());
934 
935   TheFPM->doInitialization();
936 }
937 
938 static void HandleDefinition() {
939   if (auto FnAST = ParseDefinition()) {
940     if (auto *FnIR = FnAST->codegen()) {
941       fprintf(stderr, "Read function definition:");
942       FnIR->dump();
943       TheJIT->addModule(std::move(TheModule));
944       InitializeModuleAndPassManager();
945     }
946   } else {
947     // Skip token for error recovery.
948     getNextToken();
949   }
950 }
951 
952 static void HandleExtern() {
953   if (auto ProtoAST = ParseExtern()) {
954     if (auto *FnIR = ProtoAST->codegen()) {
955       fprintf(stderr, "Read extern: ");
956       FnIR->dump();
957       FunctionProtos[ProtoAST->getName()] = std::move(ProtoAST);
958     }
959   } else {
960     // Skip token for error recovery.
961     getNextToken();
962   }
963 }
964 
965 static void HandleTopLevelExpression() {
966   // Evaluate a top-level expression into an anonymous function.
967   if (auto FnAST = ParseTopLevelExpr()) {
968     if (FnAST->codegen()) {
969 
970       // JIT the module containing the anonymous expression, keeping a handle so
971       // we can free it later.
972       auto H = TheJIT->addModule(std::move(TheModule));
973       InitializeModuleAndPassManager();
974 
975       // Search the JIT for the __anon_expr symbol.
976       auto ExprSymbol = TheJIT->findSymbol("__anon_expr");
977       assert(ExprSymbol && "Function not found");
978 
979       // Get the symbol's address and cast it to the right type (takes no
980       // arguments, returns a double) so we can call it as a native function.
981       double (*FP)() = (double (*)())(intptr_t)ExprSymbol.getAddress();
982       fprintf(stderr, "Evaluated to %f\n", FP());
983 
984       // Delete the anonymous expression module from the JIT.
985       TheJIT->removeModule(H);
986     }
987   } else {
988     // Skip token for error recovery.
989     getNextToken();
990   }
991 }
992 
993 /// top ::= definition | external | expression | ';'
994 static void MainLoop() {
995   while (1) {
996     fprintf(stderr, "ready> ");
997     switch (CurTok) {
998     case tok_eof:
999       return;
1000     case ';': // ignore top-level semicolons.
1001       getNextToken();
1002       break;
1003     case tok_def:
1004       HandleDefinition();
1005       break;
1006     case tok_extern:
1007       HandleExtern();
1008       break;
1009     default:
1010       HandleTopLevelExpression();
1011       break;
1012     }
1013   }
1014 }
1015 
1016 //===----------------------------------------------------------------------===//
1017 // "Library" functions that can be "extern'd" from user code.
1018 //===----------------------------------------------------------------------===//
1019 
1020 /// putchard - putchar that takes a double and returns 0.
1021 extern "C" double putchard(double X) {
1022   fputc((char)X, stderr);
1023   return 0;
1024 }
1025 
1026 /// printd - printf that takes a double prints it as "%f\n", returning 0.
1027 extern "C" double printd(double X) {
1028   fprintf(stderr, "%f\n", X);
1029   return 0;
1030 }
1031 
1032 //===----------------------------------------------------------------------===//
1033 // Main driver code.
1034 //===----------------------------------------------------------------------===//
1035 
1036 int main() {
1037   InitializeNativeTarget();
1038   InitializeNativeTargetAsmPrinter();
1039   InitializeNativeTargetAsmParser();
1040 
1041   // Install standard binary operators.
1042   // 1 is lowest precedence.
1043   BinopPrecedence['<'] = 10;
1044   BinopPrecedence['+'] = 20;
1045   BinopPrecedence['-'] = 20;
1046   BinopPrecedence['*'] = 40; // highest.
1047 
1048   // Prime the first token.
1049   fprintf(stderr, "ready> ");
1050   getNextToken();
1051 
1052   TheJIT = llvm::make_unique<KaleidoscopeJIT>();
1053 
1054   InitializeModuleAndPassManager();
1055 
1056   // Run the main "interpreter loop" now.
1057   MainLoop();
1058 
1059   return 0;
1060 }
1061