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

source code of llvm/examples/Kaleidoscope/Chapter5/toy.cpp