Fix PR25372 - teach replaceCongruentPHIs to handle cases where SE evaluates a PHI...
[oota-llvm.git] / examples / Kaleidoscope / Orc / fully_lazy / toy.cpp
1 #include "llvm/Analysis/Passes.h"
2 #include "llvm/ExecutionEngine/Orc/CompileUtils.h"
3 #include "llvm/ExecutionEngine/Orc/IRCompileLayer.h"
4 #include "llvm/ExecutionEngine/Orc/LambdaResolver.h"
5 #include "llvm/ExecutionEngine/Orc/LazyEmittingLayer.h"
6 #include "llvm/ExecutionEngine/Orc/ObjectLinkingLayer.h"
7 #include "llvm/ExecutionEngine/Orc/OrcTargetSupport.h"
8 #include "llvm/IR/DataLayout.h"
9 #include "llvm/IR/DerivedTypes.h"
10 #include "llvm/IR/IRBuilder.h"
11 #include "llvm/IR/LegacyPassManager.h"
12 #include "llvm/IR/LLVMContext.h"
13 #include "llvm/IR/Module.h"
14 #include "llvm/IR/Verifier.h"
15 #include "llvm/Support/TargetSelect.h"
16 #include "llvm/Transforms/Scalar.h"
17 #include <cctype>
18 #include <iomanip>
19 #include <iostream>
20 #include <map>
21 #include <sstream>
22 #include <string>
23 #include <vector>
24
25 using namespace llvm;
26 using namespace llvm::orc;
27
28 //===----------------------------------------------------------------------===//
29 // Lexer
30 //===----------------------------------------------------------------------===//
31
32 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
33 // of these for known things.
34 enum Token {
35   tok_eof = -1,
36
37   // commands
38   tok_def = -2, tok_extern = -3,
39
40   // primary
41   tok_identifier = -4, tok_number = -5,
42
43   // control
44   tok_if = -6, tok_then = -7, tok_else = -8,
45   tok_for = -9, tok_in = -10,
46
47   // operators
48   tok_binary = -11, tok_unary = -12,
49
50   // var definition
51   tok_var = -13
52 };
53
54 static std::string IdentifierStr;  // Filled in if tok_identifier
55 static double NumVal;              // Filled in if tok_number
56
57 /// gettok - Return the next token from standard input.
58 static int gettok() {
59   static int LastChar = ' ';
60
61   // Skip any whitespace.
62   while (isspace(LastChar))
63     LastChar = getchar();
64
65   if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
66     IdentifierStr = LastChar;
67     while (isalnum((LastChar = getchar())))
68       IdentifierStr += LastChar;
69
70     if (IdentifierStr == "def") return tok_def;
71     if (IdentifierStr == "extern") return tok_extern;
72     if (IdentifierStr == "if") return tok_if;
73     if (IdentifierStr == "then") return tok_then;
74     if (IdentifierStr == "else") return tok_else;
75     if (IdentifierStr == "for") return tok_for;
76     if (IdentifierStr == "in") return tok_in;
77     if (IdentifierStr == "binary") return tok_binary;
78     if (IdentifierStr == "unary") return tok_unary;
79     if (IdentifierStr == "var") return tok_var;
80     return tok_identifier;
81   }
82
83   if (isdigit(LastChar) || LastChar == '.') {   // Number: [0-9.]+
84     std::string NumStr;
85     do {
86       NumStr += LastChar;
87       LastChar = getchar();
88     } while (isdigit(LastChar) || LastChar == '.');
89
90     NumVal = strtod(NumStr.c_str(), nullptr);
91     return tok_number;
92   }
93
94   if (LastChar == '#') {
95     // Comment until end of line.
96     do LastChar = getchar();
97     while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
98
99     if (LastChar != EOF)
100       return gettok();
101   }
102
103   // Check for end of file.  Don't eat the EOF.
104   if (LastChar == EOF)
105     return tok_eof;
106
107   // Otherwise, just return the character as its ascii value.
108   int ThisChar = LastChar;
109   LastChar = getchar();
110   return ThisChar;
111 }
112
113 //===----------------------------------------------------------------------===//
114 // Abstract Syntax Tree (aka Parse Tree)
115 //===----------------------------------------------------------------------===//
116
117 class IRGenContext;
118
119 /// ExprAST - Base class for all expression nodes.
120 struct ExprAST {
121   virtual ~ExprAST() {}
122   virtual Value *IRGen(IRGenContext &C) const = 0;
123 };
124
125 /// NumberExprAST - Expression class for numeric literals like "1.0".
126 struct NumberExprAST : public ExprAST {
127   NumberExprAST(double Val) : Val(Val) {}
128   Value *IRGen(IRGenContext &C) const override;
129
130   double Val;
131 };
132
133 /// VariableExprAST - Expression class for referencing a variable, like "a".
134 struct VariableExprAST : public ExprAST {
135   VariableExprAST(std::string Name) : Name(std::move(Name)) {}
136   Value *IRGen(IRGenContext &C) const override;
137
138   std::string Name;
139 };
140
141 /// UnaryExprAST - Expression class for a unary operator.
142 struct UnaryExprAST : public ExprAST {
143   UnaryExprAST(char Opcode, std::unique_ptr<ExprAST> Operand)
144     : Opcode(std::move(Opcode)), Operand(std::move(Operand)) {}
145
146   Value *IRGen(IRGenContext &C) const override;
147
148   char Opcode;
149   std::unique_ptr<ExprAST> Operand;
150 };
151
152 /// BinaryExprAST - Expression class for a binary operator.
153 struct BinaryExprAST : public ExprAST {
154   BinaryExprAST(char Op, std::unique_ptr<ExprAST> LHS,
155                 std::unique_ptr<ExprAST> RHS)
156     : Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}
157
158   Value *IRGen(IRGenContext &C) const override;
159
160   char Op;
161   std::unique_ptr<ExprAST> LHS, RHS;
162 };
163
164 /// CallExprAST - Expression class for function calls.
165 struct CallExprAST : public ExprAST {
166   CallExprAST(std::string CalleeName,
167               std::vector<std::unique_ptr<ExprAST>> Args)
168     : CalleeName(std::move(CalleeName)), Args(std::move(Args)) {}
169
170   Value *IRGen(IRGenContext &C) const override;
171
172   std::string CalleeName;
173   std::vector<std::unique_ptr<ExprAST>> Args;
174 };
175
176 /// IfExprAST - Expression class for if/then/else.
177 struct IfExprAST : public ExprAST {
178   IfExprAST(std::unique_ptr<ExprAST> Cond, std::unique_ptr<ExprAST> Then,
179             std::unique_ptr<ExprAST> Else)
180     : Cond(std::move(Cond)), Then(std::move(Then)), Else(std::move(Else)) {}
181   Value *IRGen(IRGenContext &C) const override;
182
183   std::unique_ptr<ExprAST> Cond, Then, Else;
184 };
185
186 /// ForExprAST - Expression class for for/in.
187 struct ForExprAST : public ExprAST {
188   ForExprAST(std::string VarName, std::unique_ptr<ExprAST> Start,
189              std::unique_ptr<ExprAST> End, std::unique_ptr<ExprAST> Step,
190              std::unique_ptr<ExprAST> Body)
191     : VarName(std::move(VarName)), Start(std::move(Start)), End(std::move(End)),
192       Step(std::move(Step)), Body(std::move(Body)) {}
193
194   Value *IRGen(IRGenContext &C) const override;
195
196   std::string VarName;
197   std::unique_ptr<ExprAST> Start, End, Step, Body;
198 };
199
200 /// VarExprAST - Expression class for var/in
201 struct VarExprAST : public ExprAST {
202   typedef std::pair<std::string, std::unique_ptr<ExprAST>> Binding;
203   typedef std::vector<Binding> BindingList;
204
205   VarExprAST(BindingList VarBindings, std::unique_ptr<ExprAST> Body)
206     : VarBindings(std::move(VarBindings)), Body(std::move(Body)) {}
207
208   Value *IRGen(IRGenContext &C) const override;
209
210   BindingList VarBindings;
211   std::unique_ptr<ExprAST> Body;
212 };
213
214 /// PrototypeAST - This class represents the "prototype" for a function,
215 /// which captures its argument names as well as if it is an operator.
216 struct PrototypeAST {
217   PrototypeAST(std::string Name, std::vector<std::string> Args,
218                bool IsOperator = false, unsigned Precedence = 0)
219     : Name(std::move(Name)), Args(std::move(Args)), IsOperator(IsOperator),
220       Precedence(Precedence) {}
221
222   Function *IRGen(IRGenContext &C) const;
223   void CreateArgumentAllocas(Function *F, IRGenContext &C);
224
225   bool isUnaryOp() const { return IsOperator && Args.size() == 1; }
226   bool isBinaryOp() const { return IsOperator && Args.size() == 2; }
227
228   char getOperatorName() const {
229     assert(isUnaryOp() || isBinaryOp());
230     return Name[Name.size()-1];
231   }
232
233   std::string Name;
234   std::vector<std::string> Args;
235   bool IsOperator;
236   unsigned Precedence;  // Precedence if a binary op.
237 };
238
239 /// FunctionAST - This class represents a function definition itself.
240 struct FunctionAST {
241   FunctionAST(std::unique_ptr<PrototypeAST> Proto,
242               std::unique_ptr<ExprAST> Body)
243     : Proto(std::move(Proto)), Body(std::move(Body)) {}
244
245   Function *IRGen(IRGenContext &C) const;
246
247   std::unique_ptr<PrototypeAST> Proto;
248   std::unique_ptr<ExprAST> Body;
249 };
250
251 //===----------------------------------------------------------------------===//
252 // Parser
253 //===----------------------------------------------------------------------===//
254
255 /// CurTok/getNextToken - Provide a simple token buffer.  CurTok is the current
256 /// token the parser is looking at.  getNextToken reads another token from the
257 /// lexer and updates CurTok with its results.
258 static int CurTok;
259 static int getNextToken() {
260   return CurTok = gettok();
261 }
262
263 /// BinopPrecedence - This holds the precedence for each binary operator that is
264 /// defined.
265 static std::map<char, int> BinopPrecedence;
266
267 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
268 static int GetTokPrecedence() {
269   if (!isascii(CurTok))
270     return -1;
271
272   // Make sure it's a declared binop.
273   int TokPrec = BinopPrecedence[CurTok];
274   if (TokPrec <= 0) return -1;
275   return TokPrec;
276 }
277
278 template <typename T>
279 std::unique_ptr<T> ErrorU(const std::string &Str) {
280   std::cerr << "Error: " << Str << "\n";
281   return nullptr;
282 }
283
284 template <typename T>
285 T* ErrorP(const std::string &Str) {
286   std::cerr << "Error: " << Str << "\n";
287   return nullptr;
288 }
289
290 static std::unique_ptr<ExprAST> ParseExpression();
291
292 /// identifierexpr
293 ///   ::= identifier
294 ///   ::= identifier '(' expression* ')'
295 static std::unique_ptr<ExprAST> ParseIdentifierExpr() {
296   std::string IdName = IdentifierStr;
297
298   getNextToken();  // eat identifier.
299
300   if (CurTok != '(') // Simple variable ref.
301     return llvm::make_unique<VariableExprAST>(IdName);
302
303   // Call.
304   getNextToken();  // eat (
305   std::vector<std::unique_ptr<ExprAST>> Args;
306   if (CurTok != ')') {
307     while (1) {
308       auto Arg = ParseExpression();
309       if (!Arg) return nullptr;
310       Args.push_back(std::move(Arg));
311
312       if (CurTok == ')') break;
313
314       if (CurTok != ',')
315         return ErrorU<CallExprAST>("Expected ')' or ',' in argument list");
316       getNextToken();
317     }
318   }
319
320   // Eat the ')'.
321   getNextToken();
322
323   return llvm::make_unique<CallExprAST>(IdName, std::move(Args));
324 }
325
326 /// numberexpr ::= number
327 static std::unique_ptr<NumberExprAST> ParseNumberExpr() {
328   auto Result = llvm::make_unique<NumberExprAST>(NumVal);
329   getNextToken(); // consume the number
330   return Result;
331 }
332
333 /// parenexpr ::= '(' expression ')'
334 static std::unique_ptr<ExprAST> ParseParenExpr() {
335   getNextToken();  // eat (.
336   auto V = ParseExpression();
337   if (!V)
338     return nullptr;
339
340   if (CurTok != ')')
341     return ErrorU<ExprAST>("expected ')'");
342   getNextToken();  // eat ).
343   return V;
344 }
345
346 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
347 static std::unique_ptr<ExprAST> ParseIfExpr() {
348   getNextToken();  // eat the if.
349
350   // condition.
351   auto Cond = ParseExpression();
352   if (!Cond)
353     return nullptr;
354
355   if (CurTok != tok_then)
356     return ErrorU<ExprAST>("expected then");
357   getNextToken();  // eat the then
358
359   auto Then = ParseExpression();
360   if (!Then)
361     return nullptr;
362
363   if (CurTok != tok_else)
364     return ErrorU<ExprAST>("expected else");
365
366   getNextToken();
367
368   auto Else = ParseExpression();
369   if (!Else)
370     return nullptr;
371
372   return llvm::make_unique<IfExprAST>(std::move(Cond), std::move(Then),
373                                       std::move(Else));
374 }
375
376 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
377 static std::unique_ptr<ForExprAST> ParseForExpr() {
378   getNextToken();  // eat the for.
379
380   if (CurTok != tok_identifier)
381     return ErrorU<ForExprAST>("expected identifier after for");
382
383   std::string IdName = IdentifierStr;
384   getNextToken();  // eat identifier.
385
386   if (CurTok != '=')
387     return ErrorU<ForExprAST>("expected '=' after for");
388   getNextToken();  // eat '='.
389
390   auto Start = ParseExpression();
391   if (!Start)
392     return nullptr;
393   if (CurTok != ',')
394     return ErrorU<ForExprAST>("expected ',' after for start value");
395   getNextToken();
396
397   auto End = ParseExpression();
398   if (!End)
399     return nullptr;
400
401   // The step value is optional.
402   std::unique_ptr<ExprAST> Step;
403   if (CurTok == ',') {
404     getNextToken();
405     Step = ParseExpression();
406     if (!Step)
407       return nullptr;
408   }
409
410   if (CurTok != tok_in)
411     return ErrorU<ForExprAST>("expected 'in' after for");
412   getNextToken();  // eat 'in'.
413
414   auto Body = ParseExpression();
415   if (Body)
416     return nullptr;
417
418   return llvm::make_unique<ForExprAST>(IdName, std::move(Start), std::move(End),
419                                        std::move(Step), std::move(Body));
420 }
421
422 /// varexpr ::= 'var' identifier ('=' expression)?
423 //                    (',' identifier ('=' expression)?)* 'in' expression
424 static std::unique_ptr<VarExprAST> ParseVarExpr() {
425   getNextToken();  // eat the var.
426
427   VarExprAST::BindingList VarBindings;
428
429   // At least one variable name is required.
430   if (CurTok != tok_identifier)
431     return ErrorU<VarExprAST>("expected identifier after var");
432
433   while (1) {
434     std::string Name = IdentifierStr;
435     getNextToken();  // eat identifier.
436
437     // Read the optional initializer.
438     std::unique_ptr<ExprAST> Init;
439     if (CurTok == '=') {
440       getNextToken(); // eat the '='.
441
442       Init = ParseExpression();
443       if (!Init)
444         return nullptr;
445     }
446
447     VarBindings.push_back(VarExprAST::Binding(Name, std::move(Init)));
448
449     // End of var list, exit loop.
450     if (CurTok != ',') break;
451     getNextToken(); // eat the ','.
452
453     if (CurTok != tok_identifier)
454       return ErrorU<VarExprAST>("expected identifier list after var");
455   }
456
457   // At this point, we have to have 'in'.
458   if (CurTok != tok_in)
459     return ErrorU<VarExprAST>("expected 'in' keyword after 'var'");
460   getNextToken();  // eat 'in'.
461
462   auto Body = ParseExpression();
463   if (!Body)
464     return nullptr;
465
466   return llvm::make_unique<VarExprAST>(std::move(VarBindings), std::move(Body));
467 }
468
469 /// primary
470 ///   ::= identifierexpr
471 ///   ::= numberexpr
472 ///   ::= parenexpr
473 ///   ::= ifexpr
474 ///   ::= forexpr
475 ///   ::= varexpr
476 static std::unique_ptr<ExprAST> ParsePrimary() {
477   switch (CurTok) {
478   default: return ErrorU<ExprAST>("unknown token when expecting an expression");
479   case tok_identifier: return ParseIdentifierExpr();
480   case tok_number:     return ParseNumberExpr();
481   case '(':            return ParseParenExpr();
482   case tok_if:         return ParseIfExpr();
483   case tok_for:        return ParseForExpr();
484   case tok_var:        return ParseVarExpr();
485   }
486 }
487
488 /// unary
489 ///   ::= primary
490 ///   ::= '!' unary
491 static std::unique_ptr<ExprAST> ParseUnary() {
492   // If the current token is not an operator, it must be a primary expr.
493   if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
494     return ParsePrimary();
495
496   // If this is a unary operator, read it.
497   int Opc = CurTok;
498   getNextToken();
499   if (auto Operand = ParseUnary())
500     return llvm::make_unique<UnaryExprAST>(Opc, std::move(Operand));
501   return nullptr;
502 }
503
504 /// binoprhs
505 ///   ::= ('+' unary)*
506 static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
507                                               std::unique_ptr<ExprAST> LHS) {
508   // If this is a binop, find its precedence.
509   while (1) {
510     int TokPrec = GetTokPrecedence();
511
512     // If this is a binop that binds at least as tightly as the current binop,
513     // consume it, otherwise we are done.
514     if (TokPrec < ExprPrec)
515       return LHS;
516
517     // Okay, we know this is a binop.
518     int BinOp = CurTok;
519     getNextToken();  // eat binop
520
521     // Parse the unary expression after the binary operator.
522     auto RHS = ParseUnary();
523     if (!RHS)
524       return nullptr;
525
526     // If BinOp binds less tightly with RHS than the operator after RHS, let
527     // the pending operator take RHS as its LHS.
528     int NextPrec = GetTokPrecedence();
529     if (TokPrec < NextPrec) {
530       RHS = ParseBinOpRHS(TokPrec+1, std::move(RHS));
531       if (!RHS)
532         return nullptr;
533     }
534
535     // Merge LHS/RHS.
536     LHS = llvm::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS));
537   }
538 }
539
540 /// expression
541 ///   ::= unary binoprhs
542 ///
543 static std::unique_ptr<ExprAST> ParseExpression() {
544   auto LHS = ParseUnary();
545   if (!LHS)
546     return nullptr;
547
548   return ParseBinOpRHS(0, std::move(LHS));
549 }
550
551 /// prototype
552 ///   ::= id '(' id* ')'
553 ///   ::= binary LETTER number? (id, id)
554 ///   ::= unary LETTER (id)
555 static std::unique_ptr<PrototypeAST> ParsePrototype() {
556   std::string FnName;
557
558   unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
559   unsigned BinaryPrecedence = 30;
560
561   switch (CurTok) {
562   default:
563     return ErrorU<PrototypeAST>("Expected function name in prototype");
564   case tok_identifier:
565     FnName = IdentifierStr;
566     Kind = 0;
567     getNextToken();
568     break;
569   case tok_unary:
570     getNextToken();
571     if (!isascii(CurTok))
572       return ErrorU<PrototypeAST>("Expected unary operator");
573     FnName = "unary";
574     FnName += (char)CurTok;
575     Kind = 1;
576     getNextToken();
577     break;
578   case tok_binary:
579     getNextToken();
580     if (!isascii(CurTok))
581       return ErrorU<PrototypeAST>("Expected binary operator");
582     FnName = "binary";
583     FnName += (char)CurTok;
584     Kind = 2;
585     getNextToken();
586
587     // Read the precedence if present.
588     if (CurTok == tok_number) {
589       if (NumVal < 1 || NumVal > 100)
590         return ErrorU<PrototypeAST>("Invalid precedecnce: must be 1..100");
591       BinaryPrecedence = (unsigned)NumVal;
592       getNextToken();
593     }
594     break;
595   }
596
597   if (CurTok != '(')
598     return ErrorU<PrototypeAST>("Expected '(' in prototype");
599
600   std::vector<std::string> ArgNames;
601   while (getNextToken() == tok_identifier)
602     ArgNames.push_back(IdentifierStr);
603   if (CurTok != ')')
604     return ErrorU<PrototypeAST>("Expected ')' in prototype");
605
606   // success.
607   getNextToken();  // eat ')'.
608
609   // Verify right number of names for operator.
610   if (Kind && ArgNames.size() != Kind)
611     return ErrorU<PrototypeAST>("Invalid number of operands for operator");
612
613   return llvm::make_unique<PrototypeAST>(FnName, std::move(ArgNames), Kind != 0,
614                                          BinaryPrecedence);
615 }
616
617 /// definition ::= 'def' prototype expression
618 static std::unique_ptr<FunctionAST> ParseDefinition() {
619   getNextToken();  // eat def.
620   auto Proto = ParsePrototype();
621   if (!Proto)
622     return nullptr;
623
624   if (auto Body = ParseExpression())
625     return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(Body));
626   return nullptr;
627 }
628
629 /// toplevelexpr ::= expression
630 static std::unique_ptr<FunctionAST> ParseTopLevelExpr() {
631   if (auto E = ParseExpression()) {
632     // Make an anonymous proto.
633     auto Proto =
634       llvm::make_unique<PrototypeAST>("__anon_expr", std::vector<std::string>());
635     return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E));
636   }
637   return nullptr;
638 }
639
640 /// external ::= 'extern' prototype
641 static std::unique_ptr<PrototypeAST> ParseExtern() {
642   getNextToken();  // eat extern.
643   return ParsePrototype();
644 }
645
646 //===----------------------------------------------------------------------===//
647 // Code Generation
648 //===----------------------------------------------------------------------===//
649
650 // FIXME: Obviously we can do better than this
651 std::string GenerateUniqueName(const std::string &Root) {
652   static int i = 0;
653   std::ostringstream NameStream;
654   NameStream << Root << ++i;
655   return NameStream.str();
656 }
657
658 std::string MakeLegalFunctionName(std::string Name)
659 {
660   std::string NewName;
661   assert(!Name.empty() && "Base name must not be empty");
662
663   // Start with what we have
664   NewName = Name;
665
666   // Look for a numberic first character
667   if (NewName.find_first_of("0123456789") == 0) {
668     NewName.insert(0, 1, 'n');
669   }
670
671   // Replace illegal characters with their ASCII equivalent
672   std::string legal_elements = "_abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
673   size_t pos;
674   while ((pos = NewName.find_first_not_of(legal_elements)) != std::string::npos) {
675     std::ostringstream NumStream;
676     NumStream << (int)NewName.at(pos);
677     NewName = NewName.replace(pos, 1, NumStream.str());
678   }
679
680   return NewName;
681 }
682
683 class SessionContext {
684 public:
685   SessionContext(LLVMContext &C)
686     : Context(C), TM(EngineBuilder().selectTarget()) {}
687   LLVMContext& getLLVMContext() const { return Context; }
688   TargetMachine& getTarget() { return *TM; }
689   void addPrototypeAST(std::unique_ptr<PrototypeAST> P);
690   PrototypeAST* getPrototypeAST(const std::string &Name);
691 private:
692   typedef std::map<std::string, std::unique_ptr<PrototypeAST>> PrototypeMap;
693
694   LLVMContext &Context;
695   std::unique_ptr<TargetMachine> TM;
696
697   PrototypeMap Prototypes;
698 };
699
700 void SessionContext::addPrototypeAST(std::unique_ptr<PrototypeAST> P) {
701   Prototypes[P->Name] = std::move(P);
702 }
703
704 PrototypeAST* SessionContext::getPrototypeAST(const std::string &Name) {
705   PrototypeMap::iterator I = Prototypes.find(Name);
706   if (I != Prototypes.end())
707     return I->second.get();
708   return nullptr;
709 }
710
711 class IRGenContext {
712 public:
713
714   IRGenContext(SessionContext &S)
715     : Session(S),
716       M(new Module(GenerateUniqueName("jit_module_"),
717                    Session.getLLVMContext())),
718       Builder(Session.getLLVMContext()) {
719     M->setDataLayout(Session.getTarget().createDataLayout());
720   }
721
722   SessionContext& getSession() { return Session; }
723   Module& getM() const { return *M; }
724   std::unique_ptr<Module> takeM() { return std::move(M); }
725   IRBuilder<>& getBuilder() { return Builder; }
726   LLVMContext& getLLVMContext() { return Session.getLLVMContext(); }
727   Function* getPrototype(const std::string &Name);
728
729   std::map<std::string, AllocaInst*> NamedValues;
730 private:
731   SessionContext &Session;
732   std::unique_ptr<Module> M;
733   IRBuilder<> Builder;
734 };
735
736 Function* IRGenContext::getPrototype(const std::string &Name) {
737   if (Function *ExistingProto = M->getFunction(Name))
738     return ExistingProto;
739   if (PrototypeAST *ProtoAST = Session.getPrototypeAST(Name))
740     return ProtoAST->IRGen(*this);
741   return nullptr;
742 }
743
744 /// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
745 /// the function.  This is used for mutable variables etc.
746 static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,
747                                           const std::string &VarName) {
748   IRBuilder<> TmpB(&TheFunction->getEntryBlock(),
749                  TheFunction->getEntryBlock().begin());
750   return TmpB.CreateAlloca(Type::getDoubleTy(getGlobalContext()), nullptr,
751                            VarName.c_str());
752 }
753
754 Value *NumberExprAST::IRGen(IRGenContext &C) const {
755   return ConstantFP::get(C.getLLVMContext(), APFloat(Val));
756 }
757
758 Value *VariableExprAST::IRGen(IRGenContext &C) const {
759   // Look this variable up in the function.
760   Value *V = C.NamedValues[Name];
761
762   if (!V)
763     return ErrorP<Value>("Unknown variable name '" + Name + "'");
764
765   // Load the value.
766   return C.getBuilder().CreateLoad(V, Name.c_str());
767 }
768
769 Value *UnaryExprAST::IRGen(IRGenContext &C) const {
770   if (Value *OperandV = Operand->IRGen(C)) {
771     std::string FnName = MakeLegalFunctionName(std::string("unary")+Opcode);
772     if (Function *F = C.getPrototype(FnName))
773       return C.getBuilder().CreateCall(F, OperandV, "unop");
774     return ErrorP<Value>("Unknown unary operator");
775   }
776
777   // Could not codegen operand - return null.
778   return nullptr;
779 }
780
781 Value *BinaryExprAST::IRGen(IRGenContext &C) const {
782   // Special case '=' because we don't want to emit the LHS as an expression.
783   if (Op == '=') {
784     // Assignment requires the LHS to be an identifier.
785     auto &LHSVar = static_cast<VariableExprAST &>(*LHS);
786     // Codegen the RHS.
787     Value *Val = RHS->IRGen(C);
788     if (!Val) return nullptr;
789
790     // Look up the name.
791     if (auto Variable = C.NamedValues[LHSVar.Name]) {
792       C.getBuilder().CreateStore(Val, Variable);
793       return Val;
794     }
795     return ErrorP<Value>("Unknown variable name");
796   }
797
798   Value *L = LHS->IRGen(C);
799   Value *R = RHS->IRGen(C);
800   if (!L || !R) return nullptr;
801
802   switch (Op) {
803   case '+': return C.getBuilder().CreateFAdd(L, R, "addtmp");
804   case '-': return C.getBuilder().CreateFSub(L, R, "subtmp");
805   case '*': return C.getBuilder().CreateFMul(L, R, "multmp");
806   case '/': return C.getBuilder().CreateFDiv(L, R, "divtmp");
807   case '<':
808     L = C.getBuilder().CreateFCmpULT(L, R, "cmptmp");
809     // Convert bool 0/1 to double 0.0 or 1.0
810     return C.getBuilder().CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
811                                 "booltmp");
812   default: break;
813   }
814
815   // If it wasn't a builtin binary operator, it must be a user defined one. Emit
816   // a call to it.
817   std::string FnName = MakeLegalFunctionName(std::string("binary")+Op);
818   if (Function *F = C.getPrototype(FnName)) {
819     Value *Ops[] = { L, R };
820     return C.getBuilder().CreateCall(F, Ops, "binop");
821   }
822
823   return ErrorP<Value>("Unknown binary operator");
824 }
825
826 Value *CallExprAST::IRGen(IRGenContext &C) const {
827   // Look up the name in the global module table.
828   if (auto CalleeF = C.getPrototype(CalleeName)) {
829     // If argument mismatch error.
830     if (CalleeF->arg_size() != Args.size())
831       return ErrorP<Value>("Incorrect # arguments passed");
832
833     std::vector<Value*> ArgsV;
834     for (unsigned i = 0, e = Args.size(); i != e; ++i) {
835       ArgsV.push_back(Args[i]->IRGen(C));
836       if (!ArgsV.back()) return nullptr;
837     }
838
839     return C.getBuilder().CreateCall(CalleeF, ArgsV, "calltmp");
840   }
841
842   return ErrorP<Value>("Unknown function referenced");
843 }
844
845 Value *IfExprAST::IRGen(IRGenContext &C) const {
846   Value *CondV = Cond->IRGen(C);
847   if (!CondV) return nullptr;
848
849   // Convert condition to a bool by comparing equal to 0.0.
850   ConstantFP *FPZero =
851     ConstantFP::get(C.getLLVMContext(), APFloat(0.0));
852   CondV = C.getBuilder().CreateFCmpONE(CondV, FPZero, "ifcond");
853
854   Function *TheFunction = C.getBuilder().GetInsertBlock()->getParent();
855
856   // Create blocks for the then and else cases.  Insert the 'then' block at the
857   // end of the function.
858   BasicBlock *ThenBB = BasicBlock::Create(C.getLLVMContext(), "then", TheFunction);
859   BasicBlock *ElseBB = BasicBlock::Create(C.getLLVMContext(), "else");
860   BasicBlock *MergeBB = BasicBlock::Create(C.getLLVMContext(), "ifcont");
861
862   C.getBuilder().CreateCondBr(CondV, ThenBB, ElseBB);
863
864   // Emit then value.
865   C.getBuilder().SetInsertPoint(ThenBB);
866
867   Value *ThenV = Then->IRGen(C);
868   if (!ThenV) return nullptr;
869
870   C.getBuilder().CreateBr(MergeBB);
871   // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
872   ThenBB = C.getBuilder().GetInsertBlock();
873
874   // Emit else block.
875   TheFunction->getBasicBlockList().push_back(ElseBB);
876   C.getBuilder().SetInsertPoint(ElseBB);
877
878   Value *ElseV = Else->IRGen(C);
879   if (!ElseV) return nullptr;
880
881   C.getBuilder().CreateBr(MergeBB);
882   // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
883   ElseBB = C.getBuilder().GetInsertBlock();
884
885   // Emit merge block.
886   TheFunction->getBasicBlockList().push_back(MergeBB);
887   C.getBuilder().SetInsertPoint(MergeBB);
888   PHINode *PN = C.getBuilder().CreatePHI(Type::getDoubleTy(getGlobalContext()), 2,
889                                   "iftmp");
890
891   PN->addIncoming(ThenV, ThenBB);
892   PN->addIncoming(ElseV, ElseBB);
893   return PN;
894 }
895
896 Value *ForExprAST::IRGen(IRGenContext &C) const {
897   // Output this as:
898   //   var = alloca double
899   //   ...
900   //   start = startexpr
901   //   store start -> var
902   //   goto loop
903   // loop:
904   //   ...
905   //   bodyexpr
906   //   ...
907   // loopend:
908   //   step = stepexpr
909   //   endcond = endexpr
910   //
911   //   curvar = load var
912   //   nextvar = curvar + step
913   //   store nextvar -> var
914   //   br endcond, loop, endloop
915   // outloop:
916
917   Function *TheFunction = C.getBuilder().GetInsertBlock()->getParent();
918
919   // Create an alloca for the variable in the entry block.
920   AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
921
922   // Emit the start code first, without 'variable' in scope.
923   Value *StartVal = Start->IRGen(C);
924   if (!StartVal) return nullptr;
925
926   // Store the value into the alloca.
927   C.getBuilder().CreateStore(StartVal, Alloca);
928
929   // Make the new basic block for the loop header, inserting after current
930   // block.
931   BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
932
933   // Insert an explicit fall through from the current block to the LoopBB.
934   C.getBuilder().CreateBr(LoopBB);
935
936   // Start insertion in LoopBB.
937   C.getBuilder().SetInsertPoint(LoopBB);
938
939   // Within the loop, the variable is defined equal to the PHI node.  If it
940   // shadows an existing variable, we have to restore it, so save it now.
941   AllocaInst *OldVal = C.NamedValues[VarName];
942   C.NamedValues[VarName] = Alloca;
943
944   // Emit the body of the loop.  This, like any other expr, can change the
945   // current BB.  Note that we ignore the value computed by the body, but don't
946   // allow an error.
947   if (!Body->IRGen(C))
948     return nullptr;
949
950   // Emit the step value.
951   Value *StepVal;
952   if (Step) {
953     StepVal = Step->IRGen(C);
954     if (!StepVal) return nullptr;
955   } else {
956     // If not specified, use 1.0.
957     StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
958   }
959
960   // Compute the end condition.
961   Value *EndCond = End->IRGen(C);
962   if (!EndCond) return nullptr;
963
964   // Reload, increment, and restore the alloca.  This handles the case where
965   // the body of the loop mutates the variable.
966   Value *CurVar = C.getBuilder().CreateLoad(Alloca, VarName.c_str());
967   Value *NextVar = C.getBuilder().CreateFAdd(CurVar, StepVal, "nextvar");
968   C.getBuilder().CreateStore(NextVar, Alloca);
969
970   // Convert condition to a bool by comparing equal to 0.0.
971   EndCond = C.getBuilder().CreateFCmpONE(EndCond,
972                               ConstantFP::get(getGlobalContext(), APFloat(0.0)),
973                                   "loopcond");
974
975   // Create the "after loop" block and insert it.
976   BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
977
978   // Insert the conditional branch into the end of LoopEndBB.
979   C.getBuilder().CreateCondBr(EndCond, LoopBB, AfterBB);
980
981   // Any new code will be inserted in AfterBB.
982   C.getBuilder().SetInsertPoint(AfterBB);
983
984   // Restore the unshadowed variable.
985   if (OldVal)
986     C.NamedValues[VarName] = OldVal;
987   else
988     C.NamedValues.erase(VarName);
989
990   // for expr always returns 0.0.
991   return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
992 }
993
994 Value *VarExprAST::IRGen(IRGenContext &C) const {
995   std::vector<AllocaInst *> OldBindings;
996
997   Function *TheFunction = C.getBuilder().GetInsertBlock()->getParent();
998
999   // Register all variables and emit their initializer.
1000   for (unsigned i = 0, e = VarBindings.size(); i != e; ++i) {
1001     auto &VarName = VarBindings[i].first;
1002     auto &Init = VarBindings[i].second;
1003
1004     // Emit the initializer before adding the variable to scope, this prevents
1005     // the initializer from referencing the variable itself, and permits stuff
1006     // like this:
1007     //  var a = 1 in
1008     //    var a = a in ...   # refers to outer 'a'.
1009     Value *InitVal;
1010     if (Init) {
1011       InitVal = Init->IRGen(C);
1012       if (!InitVal) return nullptr;
1013     } else // If not specified, use 0.0.
1014       InitVal = ConstantFP::get(getGlobalContext(), APFloat(0.0));
1015
1016     AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
1017     C.getBuilder().CreateStore(InitVal, Alloca);
1018
1019     // Remember the old variable binding so that we can restore the binding when
1020     // we unrecurse.
1021     OldBindings.push_back(C.NamedValues[VarName]);
1022
1023     // Remember this binding.
1024     C.NamedValues[VarName] = Alloca;
1025   }
1026
1027   // Codegen the body, now that all vars are in scope.
1028   Value *BodyVal = Body->IRGen(C);
1029   if (!BodyVal) return nullptr;
1030
1031   // Pop all our variables from scope.
1032   for (unsigned i = 0, e = VarBindings.size(); i != e; ++i)
1033     C.NamedValues[VarBindings[i].first] = OldBindings[i];
1034
1035   // Return the body computation.
1036   return BodyVal;
1037 }
1038
1039 Function *PrototypeAST::IRGen(IRGenContext &C) const {
1040   std::string FnName = MakeLegalFunctionName(Name);
1041
1042   // Make the function type:  double(double,double) etc.
1043   std::vector<Type*> Doubles(Args.size(),
1044                              Type::getDoubleTy(getGlobalContext()));
1045   FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1046                                        Doubles, false);
1047   Function *F = Function::Create(FT, Function::ExternalLinkage, FnName,
1048                                  &C.getM());
1049
1050   // If F conflicted, there was already something named 'FnName'.  If it has a
1051   // body, don't allow redefinition or reextern.
1052   if (F->getName() != FnName) {
1053     // Delete the one we just made and get the existing one.
1054     F->eraseFromParent();
1055     F = C.getM().getFunction(Name);
1056
1057     // If F already has a body, reject this.
1058     if (!F->empty()) {
1059       ErrorP<Function>("redefinition of function");
1060       return nullptr;
1061     }
1062
1063     // If F took a different number of args, reject.
1064     if (F->arg_size() != Args.size()) {
1065       ErrorP<Function>("redefinition of function with different # args");
1066       return nullptr;
1067     }
1068   }
1069
1070   // Set names for all arguments.
1071   unsigned Idx = 0;
1072   for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1073        ++AI, ++Idx)
1074     AI->setName(Args[Idx]);
1075
1076   return F;
1077 }
1078
1079 /// CreateArgumentAllocas - Create an alloca for each argument and register the
1080 /// argument in the symbol table so that references to it will succeed.
1081 void PrototypeAST::CreateArgumentAllocas(Function *F, IRGenContext &C) {
1082   Function::arg_iterator AI = F->arg_begin();
1083   for (unsigned Idx = 0, e = Args.size(); Idx != e; ++Idx, ++AI) {
1084     // Create an alloca for this variable.
1085     AllocaInst *Alloca = CreateEntryBlockAlloca(F, Args[Idx]);
1086
1087     // Store the initial value into the alloca.
1088     C.getBuilder().CreateStore(AI, Alloca);
1089
1090     // Add arguments to variable symbol table.
1091     C.NamedValues[Args[Idx]] = Alloca;
1092   }
1093 }
1094
1095 Function *FunctionAST::IRGen(IRGenContext &C) const {
1096   C.NamedValues.clear();
1097
1098   Function *TheFunction = Proto->IRGen(C);
1099   if (!TheFunction)
1100     return nullptr;
1101
1102   // If this is an operator, install it.
1103   if (Proto->isBinaryOp())
1104     BinopPrecedence[Proto->getOperatorName()] = Proto->Precedence;
1105
1106   // Create a new basic block to start insertion into.
1107   BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1108   C.getBuilder().SetInsertPoint(BB);
1109
1110   // Add all arguments to the symbol table and create their allocas.
1111   Proto->CreateArgumentAllocas(TheFunction, C);
1112
1113   if (Value *RetVal = Body->IRGen(C)) {
1114     // Finish off the function.
1115     C.getBuilder().CreateRet(RetVal);
1116
1117     // Validate the generated code, checking for consistency.
1118     verifyFunction(*TheFunction);
1119
1120     return TheFunction;
1121   }
1122
1123   // Error reading body, remove function.
1124   TheFunction->eraseFromParent();
1125
1126   if (Proto->isBinaryOp())
1127     BinopPrecedence.erase(Proto->getOperatorName());
1128   return nullptr;
1129 }
1130
1131 //===----------------------------------------------------------------------===//
1132 // Top-Level parsing and JIT Driver
1133 //===----------------------------------------------------------------------===//
1134
1135 static std::unique_ptr<llvm::Module> IRGen(SessionContext &S,
1136                                            const FunctionAST &F) {
1137   IRGenContext C(S);
1138   auto LF = F.IRGen(C);
1139   if (!LF)
1140     return nullptr;
1141 #ifndef MINIMAL_STDERR_OUTPUT
1142   fprintf(stderr, "Read function definition:");
1143   LF->dump();
1144 #endif
1145   return C.takeM();
1146 }
1147
1148 template <typename T>
1149 static std::vector<T> singletonSet(T t) {
1150   std::vector<T> Vec;
1151   Vec.push_back(std::move(t));
1152   return Vec;
1153 }
1154
1155 static void EarthShatteringKaboom() {
1156   fprintf(stderr, "Earth shattering kaboom.");
1157   exit(1);
1158 }
1159
1160 class KaleidoscopeJIT {
1161 public:
1162   typedef ObjectLinkingLayer<> ObjLayerT;
1163   typedef IRCompileLayer<ObjLayerT> CompileLayerT;
1164   typedef LazyEmittingLayer<CompileLayerT> LazyEmitLayerT;
1165   typedef LazyEmitLayerT::ModuleSetHandleT ModuleHandleT;
1166
1167   KaleidoscopeJIT(SessionContext &Session)
1168     : Session(Session),
1169       CompileLayer(ObjectLayer, SimpleCompiler(Session.getTarget())),
1170       LazyEmitLayer(CompileLayer),
1171       CompileCallbacks(LazyEmitLayer, CCMgrMemMgr, Session.getLLVMContext(),
1172                        reinterpret_cast<uintptr_t>(EarthShatteringKaboom),
1173                        64) {}
1174
1175   std::string mangle(const std::string &Name) {
1176     std::string MangledName;
1177     {
1178       raw_string_ostream MangledNameStream(MangledName);
1179       Mangler::getNameWithPrefix(MangledNameStream, Name,
1180                                  Session.getTarget().createDataLayout());
1181     }
1182     return MangledName;
1183   }
1184
1185   void addFunctionAST(std::unique_ptr<FunctionAST> FnAST) {
1186     std::cerr << "Adding AST: " << FnAST->Proto->Name << "\n";
1187     FunctionDefs[mangle(FnAST->Proto->Name)] = std::move(FnAST);
1188   }
1189
1190   ModuleHandleT addModule(std::unique_ptr<Module> M) {
1191     // We need a memory manager to allocate memory and resolve symbols for this
1192     // new module. Create one that resolves symbols by looking back into the
1193     // JIT.
1194     auto Resolver = createLambdaResolver(
1195                       [&](const std::string &Name) {
1196                         // First try to find 'Name' within the JIT.
1197                         if (auto Symbol = findSymbol(Name))
1198                           return RuntimeDyld::SymbolInfo(Symbol.getAddress(),
1199                                                          Symbol.getFlags());
1200
1201                         // If we don't already have a definition of 'Name' then search
1202                         // the ASTs.
1203                         return searchFunctionASTs(Name);
1204                       },
1205                       [](const std::string &S) { return nullptr; } );
1206
1207     return LazyEmitLayer.addModuleSet(singletonSet(std::move(M)),
1208                                       make_unique<SectionMemoryManager>(),
1209                                       std::move(Resolver));
1210   }
1211
1212   void removeModule(ModuleHandleT H) { LazyEmitLayer.removeModuleSet(H); }
1213
1214   JITSymbol findSymbol(const std::string &Name) {
1215     return LazyEmitLayer.findSymbol(Name, false);
1216   }
1217
1218   JITSymbol findSymbolIn(ModuleHandleT H, const std::string &Name) {
1219     return LazyEmitLayer.findSymbolIn(H, Name, false);
1220   }
1221
1222   JITSymbol findUnmangledSymbol(const std::string &Name) {
1223     return findSymbol(mangle(Name));
1224   }
1225
1226   JITSymbol findUnmangledSymbolIn(ModuleHandleT H, const std::string &Name) {
1227     return findSymbolIn(H, mangle(Name));
1228   }
1229
1230 private:
1231
1232   // This method searches the FunctionDefs map for a definition of 'Name'. If it
1233   // finds one it generates a stub for it and returns the address of the stub.
1234   RuntimeDyld::SymbolInfo searchFunctionASTs(const std::string &Name) {
1235     auto DefI = FunctionDefs.find(Name);
1236     if (DefI == FunctionDefs.end())
1237       return nullptr;
1238
1239     // Return the address of the stub.
1240     // Take the FunctionAST out of the map.
1241     auto FnAST = std::move(DefI->second);
1242     FunctionDefs.erase(DefI);
1243
1244     // IRGen the AST, add it to the JIT, and return the address for it.
1245     auto H = irGenStub(std::move(FnAST));
1246     auto Sym = findSymbolIn(H, Name);
1247     return RuntimeDyld::SymbolInfo(Sym.getAddress(), Sym.getFlags());
1248   }
1249
1250   // This method will take the AST for a function definition and IR-gen a stub
1251   // for that function that will, on first call, IR-gen the actual body of the
1252   // function.
1253   ModuleHandleT irGenStub(std::unique_ptr<FunctionAST> FnAST) {
1254     // Step 1) IRGen a prototype for the stub. This will have the same type as
1255     //         the function.
1256     IRGenContext C(Session);
1257     Function *F = FnAST->Proto->IRGen(C);
1258
1259     // Step 2) Get a compile callback that can be used to compile the body of
1260     //         the function. The resulting CallbackInfo type will let us set the
1261     //         compile and update actions for the callback, and get a pointer to
1262     //         the jit trampoline that we need to call to trigger those actions.
1263     auto CallbackInfo =
1264       CompileCallbacks.getCompileCallback(F->getContext());
1265
1266     // Step 3) Create a stub that will indirectly call the body of this
1267     //         function once it is compiled. Initially, set the function
1268     //         pointer for the indirection to point at the trampoline.
1269     std::string BodyPtrName = (F->getName() + "$address").str();
1270     GlobalVariable *FunctionBodyPointer =
1271       createImplPointer(*F->getType(), *F->getParent(), BodyPtrName,
1272                         createIRTypedAddress(*F->getFunctionType(),
1273                                              CallbackInfo.getAddress()));
1274     makeStub(*F, *FunctionBodyPointer);
1275
1276     // Step 4) Add the module containing the stub to the JIT.
1277     auto StubH = addModule(C.takeM());
1278
1279     // Step 5) Set the compile and update actions.
1280     //
1281     //   The compile action will IRGen the function and add it to the JIT, then
1282     // request its address, which will trigger codegen. Since we don't need the
1283     // AST after this, we pass ownership of the AST into the compile action:
1284     // compile actions (and update actions) are deleted after they're run, so
1285     // this will free the AST for us.
1286     //
1287     //   The update action will update FunctionBodyPointer to point at the newly
1288     // compiled function.
1289     std::shared_ptr<FunctionAST> Fn = std::move(FnAST);
1290     CallbackInfo.setCompileAction([this, Fn, BodyPtrName, StubH]() {
1291       auto H = addModule(IRGen(Session, *Fn));
1292       auto BodySym = findUnmangledSymbolIn(H, Fn->Proto->Name);
1293       auto BodyPtrSym = findUnmangledSymbolIn(StubH, BodyPtrName);
1294       assert(BodySym && "Missing function body.");
1295       assert(BodyPtrSym && "Missing function pointer.");
1296       auto BodyAddr = BodySym.getAddress();
1297       auto BodyPtr = reinterpret_cast<void*>(
1298                        static_cast<uintptr_t>(BodyPtrSym.getAddress()));
1299       memcpy(BodyPtr, &BodyAddr, sizeof(uintptr_t));
1300       return BodyAddr;
1301     });
1302
1303     return StubH;
1304   }
1305
1306   SessionContext &Session;
1307   SectionMemoryManager CCMgrMemMgr;
1308   ObjLayerT ObjectLayer;
1309   CompileLayerT CompileLayer;
1310   LazyEmitLayerT LazyEmitLayer;
1311
1312   std::map<std::string, std::unique_ptr<FunctionAST>> FunctionDefs;
1313
1314   JITCompileCallbackManager<LazyEmitLayerT, OrcX86_64> CompileCallbacks;
1315 };
1316
1317 static void HandleDefinition(SessionContext &S, KaleidoscopeJIT &J) {
1318   if (auto F = ParseDefinition()) {
1319     S.addPrototypeAST(llvm::make_unique<PrototypeAST>(*F->Proto));
1320     J.addFunctionAST(std::move(F));
1321   } else {
1322     // Skip token for error recovery.
1323     getNextToken();
1324   }
1325 }
1326
1327 static void HandleExtern(SessionContext &S) {
1328   if (auto P = ParseExtern())
1329     S.addPrototypeAST(std::move(P));
1330   else {
1331     // Skip token for error recovery.
1332     getNextToken();
1333   }
1334 }
1335
1336 static void HandleTopLevelExpression(SessionContext &S, KaleidoscopeJIT &J) {
1337   // Evaluate a top-level expression into an anonymous function.
1338   if (auto F = ParseTopLevelExpr()) {
1339     IRGenContext C(S);
1340     if (auto ExprFunc = F->IRGen(C)) {
1341 #ifndef MINIMAL_STDERR_OUTPUT
1342       std::cerr << "Expression function:\n";
1343       ExprFunc->dump();
1344 #endif
1345       // Add the CodeGen'd module to the JIT. Keep a handle to it: We can remove
1346       // this module as soon as we've executed Function ExprFunc.
1347       auto H = J.addModule(C.takeM());
1348
1349       // Get the address of the JIT'd function in memory.
1350       auto ExprSymbol = J.findUnmangledSymbol("__anon_expr");
1351
1352       // Cast it to the right type (takes no arguments, returns a double) so we
1353       // can call it as a native function.
1354       double (*FP)() = (double (*)())(intptr_t)ExprSymbol.getAddress();
1355 #ifdef MINIMAL_STDERR_OUTPUT
1356       FP();
1357 #else
1358       std::cerr << "Evaluated to " << FP() << "\n";
1359 #endif
1360
1361       // Remove the function.
1362       J.removeModule(H);
1363     }
1364   } else {
1365     // Skip token for error recovery.
1366     getNextToken();
1367   }
1368 }
1369
1370 /// top ::= definition | external | expression | ';'
1371 static void MainLoop() {
1372   SessionContext S(getGlobalContext());
1373   KaleidoscopeJIT J(S);
1374
1375   while (1) {
1376     switch (CurTok) {
1377     case tok_eof:    return;
1378     case ';':        getNextToken(); continue;  // ignore top-level semicolons.
1379     case tok_def:    HandleDefinition(S, J); break;
1380     case tok_extern: HandleExtern(S); break;
1381     default:         HandleTopLevelExpression(S, J); break;
1382     }
1383 #ifndef MINIMAL_STDERR_OUTPUT
1384     std::cerr << "ready> ";
1385 #endif
1386   }
1387 }
1388
1389 //===----------------------------------------------------------------------===//
1390 // "Library" functions that can be "extern'd" from user code.
1391 //===----------------------------------------------------------------------===//
1392
1393 /// putchard - putchar that takes a double and returns 0.
1394 extern "C"
1395 double putchard(double X) {
1396   putchar((char)X);
1397   return 0;
1398 }
1399
1400 /// printd - printf that takes a double prints it as "%f\n", returning 0.
1401 extern "C"
1402 double printd(double X) {
1403   printf("%f", X);
1404   return 0;
1405 }
1406
1407 extern "C"
1408 double printlf() {
1409   printf("\n");
1410   return 0;
1411 }
1412
1413 //===----------------------------------------------------------------------===//
1414 // Main driver code.
1415 //===----------------------------------------------------------------------===//
1416
1417 int main() {
1418   InitializeNativeTarget();
1419   InitializeNativeTargetAsmPrinter();
1420   InitializeNativeTargetAsmParser();
1421
1422   // Install standard binary operators.
1423   // 1 is lowest precedence.
1424   BinopPrecedence['='] = 2;
1425   BinopPrecedence['<'] = 10;
1426   BinopPrecedence['+'] = 20;
1427   BinopPrecedence['-'] = 20;
1428   BinopPrecedence['/'] = 40;
1429   BinopPrecedence['*'] = 40;  // highest.
1430
1431   // Prime the first token.
1432 #ifndef MINIMAL_STDERR_OUTPUT
1433   std::cerr << "ready> ";
1434 #endif
1435   getNextToken();
1436
1437   std::cerr << std::fixed;
1438
1439   // Run the main "interpreter loop" now.
1440   MainLoop();
1441
1442   return 0;
1443 }