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