· 4 years ago · May 01, 2021, 05:30 PM
1#include "llvm/ADT/APFloat.h"
2#include "llvm/ADT/Optional.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/Instructions.h"
9#include "llvm/IR/IRBuilder.h"
10#include "llvm/IR/LLVMContext.h"
11#include "llvm/IR/LegacyPassManager.h"
12#include "llvm/IR/Module.h"
13#include "llvm/IR/Type.h"
14#include "llvm/IR/Verifier.h"
15#include "llvm/Support/FileSystem.h"
16#include "llvm/Support/Host.h"
17#include "llvm/Support/raw_ostream.h"
18#include "llvm/Support/TargetRegistry.h"
19#include "llvm/Support/TargetSelect.h"
20#include "llvm/Target/TargetMachine.h"
21#include "llvm/Target/TargetOptions.h"
22#include <algorithm>
23#include <cassert>
24#include <cctype>
25#include <cstdio>
26#include <cstdlib>
27#include <map>
28#include <memory>
29#include <string>
30#include <system_error>
31#include <utility>
32#include <vector>
33
34using namespace llvm;
35using namespace llvm::sys;
36
37//===----------------------------------------------------------------------===//
38// Lexer
39//===----------------------------------------------------------------------===//
40
41// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
42// of these for known things.
43enum Token {
44 tok_eof = -1,
45
46 // commands
47 tok_def = -2,
48 tok_extern = -3,
49
50 // primary
51 tok_identifier = -4,
52 tok_number = -5,
53 tok_string = -6,
54
55 // control
56 tok_if = -7,
57 tok_then = -8,
58 tok_else = -9,
59 tok_for = -10,
60 tok_in = -11,
61
62 // operators
63 tok_binary = -12,
64 tok_unary = -13,
65
66 // var definition
67 tok_var = -14
68};
69
70static std::string IdentifierStr; // Filled in if tok_identifier
71static double NumVal; // Filled in if tok_number
72static std::string StringVal;
73
74/// gettok - Return the next token from standard input.
75static int gettok() {
76 static int LastChar = ' ';
77
78 // Skip any whitespace.
79 while (isspace(LastChar))
80 LastChar = getchar();
81// "Test"
82 //String literal
83 if(LastChar == '"'){
84 LastChar = getchar();
85 std::string NumStr;
86
87 while(LastChar != '"'){
88 NumStr += LastChar;
89 LastChar = getchar();
90 }
91 LastChar = getchar();
92 StringVal = NumStr;
93 return tok_string;
94 }
95
96
97 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
98 IdentifierStr = LastChar;
99 while (isalnum((LastChar = getchar())))
100 IdentifierStr += LastChar;
101
102 if (IdentifierStr == "def")
103 return tok_def;
104 if (IdentifierStr == "extern")
105 return tok_extern;
106 if (IdentifierStr == "if")
107 return tok_if;
108 if (IdentifierStr == "then")
109 return tok_then;
110 if (IdentifierStr == "else")
111 return tok_else;
112 if (IdentifierStr == "for")
113 return tok_for;
114 if (IdentifierStr == "in")
115 return tok_in;
116 if (IdentifierStr == "binary")
117 return tok_binary;
118 if (IdentifierStr == "unary")
119 return tok_unary;
120 if (IdentifierStr == "var")
121 return tok_var;
122 return tok_identifier;
123 }
124
125 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
126 std::string NumStr;
127 do {
128 NumStr += LastChar;
129 LastChar = getchar();
130 } while (isdigit(LastChar) || LastChar == '.');
131
132 NumVal = strtod(NumStr.c_str(), nullptr);
133 return tok_number;
134 }
135
136 if (LastChar == '#') {
137 // Comment until end of line.
138 do
139 LastChar = getchar();
140 while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
141
142 if (LastChar != EOF)
143 return gettok();
144 }
145
146 // Check for end of file. Don't eat the EOF.
147 if (LastChar == EOF)
148 return tok_eof;
149
150 // Otherwise, just return the character as its ascii value.
151 int ThisChar = LastChar;
152 LastChar = getchar();
153 return ThisChar;
154}
155
156//===----------------------------------------------------------------------===//
157// Abstract Syntax Tree (aka Parse Tree)
158//===----------------------------------------------------------------------===//
159
160namespace {
161
162/// ExprAST - Base class for all expression nodes.
163class ExprAST {
164public:
165 virtual ~ExprAST() = default;
166
167 virtual Value *codegen() = 0;
168};
169
170/// NumberExprAST - Expression class for numeric literals like "1.0".
171class NumberExprAST : public ExprAST {
172 double Val;
173
174public:
175 NumberExprAST(double Val) : Val(Val) {}
176
177 Value *codegen() override;
178};
179
180/// StringLiteralExprAST - Expression class for numeric literals like 'testString'.
181class StringLiteralExprAST : public ExprAST {
182 std::string StringValue;
183
184public:
185 StringLiteralExprAST(std::string StringValue) : StringValue(StringValue) {}
186
187 Value *codegen() override;
188};
189
190/// VariableExprAST - Expression class for referencing a variable, like "a".
191class VariableExprAST : public ExprAST {
192 std::string Name;
193
194public:
195 VariableExprAST(const std::string &Name) : Name(Name) {}
196
197 Value *codegen() override;
198 const std::string &getName() const { return Name; }
199};
200
201/// UnaryExprAST - Expression class for a unary operator.
202class UnaryExprAST : public ExprAST {
203 char Opcode;
204 std::unique_ptr<ExprAST> Operand;
205
206public:
207 UnaryExprAST(char Opcode, std::unique_ptr<ExprAST> Operand)
208 : Opcode(Opcode), Operand(std::move(Operand)) {}
209
210 Value *codegen() override;
211};
212
213/// BinaryExprAST - Expression class for a binary operator.
214class BinaryExprAST : public ExprAST {
215 char Op;
216 std::unique_ptr<ExprAST> LHS, RHS;
217
218public:
219 BinaryExprAST(char Op, std::unique_ptr<ExprAST> LHS,
220 std::unique_ptr<ExprAST> RHS)
221 : Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}
222
223 Value *codegen() override;
224};
225
226/// CallExprAST - Expression class for function calls.
227class CallExprAST : public ExprAST {
228 std::string Callee;
229 std::vector<std::unique_ptr<ExprAST>> Args;
230
231public:
232 CallExprAST(const std::string &Callee,
233 std::vector<std::unique_ptr<ExprAST>> Args)
234 : Callee(Callee), Args(std::move(Args)) {}
235
236 Value *codegen() override;
237};
238
239/// IfExprAST - Expression class for if/then/else.
240class IfExprAST : public ExprAST {
241 std::unique_ptr<ExprAST> Cond, Then, Else;
242
243public:
244 IfExprAST(std::unique_ptr<ExprAST> Cond, std::unique_ptr<ExprAST> Then,
245 std::unique_ptr<ExprAST> Else)
246 : Cond(std::move(Cond)), Then(std::move(Then)), Else(std::move(Else)) {}
247
248 Value *codegen() override;
249};
250
251/// ForExprAST - Expression class for for/in.
252class ForExprAST : public ExprAST {
253 std::string VarName;
254 std::unique_ptr<ExprAST> Start, End, Step, Body;
255
256public:
257 ForExprAST(const std::string &VarName, std::unique_ptr<ExprAST> Start,
258 std::unique_ptr<ExprAST> End, std::unique_ptr<ExprAST> Step,
259 std::unique_ptr<ExprAST> Body)
260 : VarName(VarName), Start(std::move(Start)), End(std::move(End)),
261 Step(std::move(Step)), Body(std::move(Body)) {}
262
263 Value *codegen() override;
264};
265
266/// VarExprAST - Expression class for var/in
267class VarExprAST : public ExprAST {
268 std::vector<std::pair<std::string, std::pair<std::string, std::unique_ptr<ExprAST>>>> Variables;
269 std::unique_ptr<ExprAST> Body;
270
271public:
272 VarExprAST(
273 std::vector<std::pair<std::string, std::pair<std::string, std::unique_ptr<ExprAST>>>> Variables,
274 std::unique_ptr<ExprAST> Body)
275 : Variables(std::move(Variables)), Body(std::move(Body)) {}
276
277 Value *codegen() override;
278};
279
280/// PrototypeAST - This class represents the "prototype" for a function,
281/// which captures its name, and its argument names (thus implicitly the number
282/// of arguments the function takes), as well as if it is an operator.
283class PrototypeAST {
284 std::string Name;
285 std::vector<std::string> Args;
286 bool IsOperator;
287 unsigned Precedence; // Precedence if a binary op.
288
289public:
290 PrototypeAST(const std::string &Name, std::vector<std::string> Args,
291 bool IsOperator = false, unsigned Prec = 0)
292 : Name(Name), Args(std::move(Args)), IsOperator(IsOperator),
293 Precedence(Prec) {}
294
295 Function *codegen();
296 const std::string &getName() const { return Name; }
297
298 bool isUnaryOp() const { return IsOperator && Args.size() == 1; }
299 bool isBinaryOp() const { return IsOperator && Args.size() == 2; }
300
301 char getOperatorName() const {
302 assert(isUnaryOp() || isBinaryOp());
303 return Name[Name.size() - 1];
304 }
305
306 unsigned getBinaryPrecedence() const { return Precedence; }
307};
308
309/// FunctionAST - This class represents a function definition itself.
310class FunctionAST {
311 std::unique_ptr<PrototypeAST> Proto;
312 std::unique_ptr<ExprAST> Body;
313
314public:
315 FunctionAST(std::unique_ptr<PrototypeAST> Proto,
316 std::unique_ptr<ExprAST> Body)
317 : Proto(std::move(Proto)), Body(std::move(Body)) {}
318
319 Function *codegen();
320};
321
322} // end anonymous namespace
323
324//===----------------------------------------------------------------------===//
325// Parser
326//===----------------------------------------------------------------------===//
327
328/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
329/// token the parser is looking at. getNextToken reads another token from the
330/// lexer and updates CurTok with its results.
331static int CurTok;
332static int getNextToken() { return CurTok = gettok(); }
333
334/// BinopPrecedence - This holds the precedence for each binary operator that is
335/// defined.
336static std::map<char, int> BinopPrecedence;
337
338/// GetTokPrecedence - Get the precedence of the pending binary operator token.
339static int GetTokPrecedence() {
340 if (!isascii(CurTok))
341 return -1;
342
343 // Make sure it's a declared binop.
344 int TokPrec = BinopPrecedence[CurTok];
345 if (TokPrec <= 0)
346 return -1;
347 return TokPrec;
348}
349
350/// LogError* - These are little helper functions for error handling.
351std::unique_ptr<ExprAST> LogError(const char *Str) {
352 fprintf(stderr, "Error: %s\n", Str);
353 return nullptr;
354}
355
356std::unique_ptr<PrototypeAST> LogErrorP(const char *Str) {
357 LogError(Str);
358 return nullptr;
359}
360
361static std::unique_ptr<ExprAST> ParseExpression();
362
363/// numberexpr ::= number
364static std::unique_ptr<ExprAST> ParseNumberExpr() {
365 auto Result = std::make_unique<NumberExprAST>(NumVal);
366 getNextToken(); // consume the number
367 return std::move(Result);
368}
369
370/// stringexpr ::= string
371static std::unique_ptr<ExprAST> ParseStringExpr() {
372 auto Result = std::make_unique<StringLiteralExprAST>(StringVal);
373 getNextToken(); // consume the string literal
374 return std::move(Result);
375}
376
377/// parenexpr ::= '(' expression ')'
378static std::unique_ptr<ExprAST> ParseParenExpr() {
379 getNextToken(); // eat (.
380 auto V = ParseExpression();
381 if (!V)
382 return nullptr;
383
384 if (CurTok != ')')
385 return LogError("expected ')'");
386 getNextToken(); // eat ).
387 return V;
388}
389
390/// identifierexpr
391/// ::= identifier
392/// ::= identifier '(' expression* ')'
393static std::unique_ptr<ExprAST> ParseIdentifierExpr() {
394 std::string IdName = IdentifierStr;
395
396 getNextToken(); // eat identifier.
397
398 if (CurTok != '(') // Simple variable ref.
399 return std::make_unique<VariableExprAST>(IdName);
400
401 // Call.
402 getNextToken(); // eat (
403 std::vector<std::unique_ptr<ExprAST>> Args;
404 if (CurTok != ')') {
405 while (true) {
406 if (auto Arg = ParseExpression())
407 Args.push_back(std::move(Arg));
408 else
409 return nullptr;
410
411 if (CurTok == ')')
412 break;
413
414 if (CurTok != ',')
415 return LogError("Expected ')' or ',' in argument list");
416 getNextToken();
417 }
418 }
419
420 // Eat the ')'.
421 getNextToken();
422
423 return std::make_unique<CallExprAST>(IdName, std::move(Args));
424}
425
426/// ifexpr ::= 'if' expression 'then' expression 'else' expression
427static std::unique_ptr<ExprAST> ParseIfExpr() {
428 getNextToken(); // eat the if.
429
430 // condition.
431 auto Cond = ParseExpression();
432 if (!Cond)
433 return nullptr;
434
435 if (CurTok != tok_then)
436 return LogError("expected then");
437 getNextToken(); // eat the then
438
439 auto Then = ParseExpression();
440 if (!Then)
441 return nullptr;
442
443 if (CurTok != tok_else)
444 return LogError("expected else");
445
446 getNextToken();
447
448 auto Else = ParseExpression();
449 if (!Else)
450 return nullptr;
451
452 return std::make_unique<IfExprAST>(std::move(Cond), std::move(Then),
453 std::move(Else));
454}
455
456/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
457static std::unique_ptr<ExprAST> ParseForExpr() {
458 getNextToken(); // eat the for.
459
460 if (CurTok != tok_identifier)
461 return LogError("expected identifier after for");
462
463 std::string IdName = IdentifierStr;
464 getNextToken(); // eat identifier.
465
466 if (CurTok != '=')
467 return LogError("expected '=' after for");
468 getNextToken(); // eat '='.
469
470 auto Start = ParseExpression();
471 if (!Start)
472 return nullptr;
473 if (CurTok != ',')
474 return LogError("expected ',' after for start value");
475 getNextToken();
476
477 auto End = ParseExpression();
478 if (!End)
479 return nullptr;
480
481 // The step value is optional.
482 std::unique_ptr<ExprAST> Step;
483 if (CurTok == ',') {
484 getNextToken();
485 Step = ParseExpression();
486 if (!Step)
487 return nullptr;
488 }
489
490 if (CurTok != tok_in)
491 return LogError("expected 'in' after for");
492 getNextToken(); // eat 'in'.
493
494 auto Body = ParseExpression();
495 if (!Body)
496 return nullptr;
497
498 return std::make_unique<ForExprAST>(IdName, std::move(Start), std::move(End),
499 std::move(Step), std::move(Body));
500}
501
502
503static bool hasType(std::string varType){
504 if(varType=="String") {
505 return true;
506 }
507 if(varType=="Double"){
508 return true;
509 }
510 return false;
511}
512
513/// varexpr ::= 'var' identifier ('=' expression)?
514// (',' identifier ('=' expression)?)* 'in' expression
515
516// var a:Double = 2, b:String="1" in
517// var a Double = 2, b String="1" in
518static std::unique_ptr<ExprAST> ParseVarExpr() {
519 getNextToken(); // eat the var.
520
521 std::vector<std::pair<std::string, std::pair<std::string, std::unique_ptr<ExprAST>>>> Variables;
522
523 // At least one variable name is required.
524 if (CurTok != tok_identifier)
525 return LogError("expected identifier after var");
526
527 while (true) {
528 std::string Name = IdentifierStr;
529 printf("%s", Name.c_str());
530 getNextToken(); // eat identifier.
531
532 if(CurTok != ':'){
533 return LogError("Missing : after identifier");
534 }
535 getNextToken();
536
537 std::string Type = IdentifierStr;
538 if(!hasType(Type)){
539 printf("type: %s", IdentifierStr.c_str());
540 return LogError("Missing variable type");
541 }
542 printf("%s", Type.c_str());
543
544 getNextToken();
545
546 std::unique_ptr<ExprAST> Init = nullptr;
547 if (CurTok == '=') {
548 getNextToken(); // eat the '='.
549
550 Init = ParseExpression();
551 if (!Init)
552 return nullptr;
553 }
554
555 Variables.push_back(std::make_pair(Name, std::make_pair(Type, std::move(Init))));
556
557 // End of var list, exit loop.
558 if (CurTok != ',')
559 break;
560 getNextToken(); // eat the ','.
561
562 if (CurTok != tok_identifier)
563 return LogError("expected identifier list after var");
564 }
565
566 // At this point, we have to have 'in'.
567 if (CurTok != tok_in)
568 return LogError("expected 'in' keyword after 'var'");
569 getNextToken(); // eat 'in'.
570
571 auto Body = ParseExpression();
572 if (!Body)
573 return nullptr;
574
575 return std::make_unique<VarExprAST>(std::move(Variables), std::move(Body));
576}
577
578/// primary
579/// ::= identifierexpr
580/// ::= numberexpr
581/// ::= parenexpr
582/// ::= ifexpr
583/// ::= forexpr
584/// ::= varexpr
585static std::unique_ptr<ExprAST> ParsePrimary() {
586 switch (CurTok) {
587 default:
588 return LogError("unknown token when expecting an expression");
589 case tok_identifier:
590 return ParseIdentifierExpr();
591 case tok_number:
592 return ParseNumberExpr();
593 case tok_string:
594 return ParseStringExpr();
595 case '(':
596 return ParseParenExpr();
597 case tok_if:
598 return ParseIfExpr();
599 case tok_for:
600 return ParseForExpr();
601 case tok_var:
602 return ParseVarExpr();
603 }
604}
605
606/// unary
607/// ::= primary
608/// ::= '!' unary
609static std::unique_ptr<ExprAST> ParseUnary() {
610 // If the current token is not an operator, it must be a primary expr.
611 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
612 return ParsePrimary();
613
614 // If this is a unary operator, read it.
615 int Opc = CurTok;
616 getNextToken();
617 if (auto Operand = ParseUnary())
618 return std::make_unique<UnaryExprAST>(Opc, std::move(Operand));
619 return nullptr;
620}
621
622/// binoprhs
623/// ::= ('+' unary)*
624static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
625 std::unique_ptr<ExprAST> LHS) {
626 // If this is a binop, find its precedence.
627 while (true) {
628 int TokPrec = GetTokPrecedence();
629
630 // If this is a binop that binds at least as tightly as the current binop,
631 // consume it, otherwise we are done.
632 if (TokPrec < ExprPrec)
633 return LHS;
634
635 // Okay, we know this is a binop.
636 int BinOp = CurTok;
637 getNextToken(); // eat binop
638
639 // Parse the unary expression after the binary operator.
640 auto RHS = ParseUnary();
641 if (!RHS)
642 return nullptr;
643
644 // If BinOp binds less tightly with RHS than the operator after RHS, let
645 // the pending operator take RHS as its LHS.
646 int NextPrec = GetTokPrecedence();
647 if (TokPrec < NextPrec) {
648 RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS));
649 if (!RHS)
650 return nullptr;
651 }
652
653 // Merge LHS/RHS.
654 LHS =
655 std::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS));
656 }
657}
658
659/// expression
660/// ::= unary binoprhs
661///
662static std::unique_ptr<ExprAST> ParseExpression() {
663 auto LHS = ParseUnary();
664 if (!LHS)
665 return nullptr;
666
667 return ParseBinOpRHS(0, std::move(LHS));
668}
669
670/// prototype
671/// ::= id '(' id* ')'
672/// ::= binary LETTER number? (id, id)
673/// ::= unary LETTER (id)
674static std::unique_ptr<PrototypeAST> ParsePrototype() {
675 std::string FnName;
676
677 unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
678 unsigned BinaryPrecedence = 30;
679
680 switch (CurTok) {
681 default:
682 return LogErrorP("Expected function name in prototype");
683 case tok_identifier:
684 FnName = IdentifierStr;
685 Kind = 0;
686 getNextToken();
687 break;
688 case tok_unary:
689 getNextToken();
690 if (!isascii(CurTok))
691 return LogErrorP("Expected unary operator");
692 FnName = "unary";
693 FnName += (char)CurTok;
694 Kind = 1;
695 getNextToken();
696 break;
697 case tok_binary:
698 getNextToken();
699 if (!isascii(CurTok))
700 return LogErrorP("Expected binary operator");
701 FnName = "binary";
702 FnName += (char)CurTok;
703 Kind = 2;
704 getNextToken();
705
706 // Read the precedence if present.
707 if (CurTok == tok_number) {
708 if (NumVal < 1 || NumVal > 100)
709 return LogErrorP("Invalid precedence: must be 1..100");
710 BinaryPrecedence = (unsigned)NumVal;
711 getNextToken();
712 }
713 break;
714 }
715
716 if (CurTok != '(')
717 return LogErrorP("Expected '(' in prototype");
718
719 std::vector<std::string> ArgNames;
720 while (getNextToken() == tok_identifier)
721 ArgNames.push_back(IdentifierStr);
722 if (CurTok != ')')
723 return LogErrorP("Expected ')' in prototype");
724
725 // success.
726 getNextToken(); // eat ')'.
727
728 // Verify right number of names for operator.
729 if (Kind && ArgNames.size() != Kind)
730 return LogErrorP("Invalid number of operands for operator");
731
732 return std::make_unique<PrototypeAST>(FnName, ArgNames, Kind != 0,
733 BinaryPrecedence);
734}
735
736/// definition ::= 'def' prototype expression
737static std::unique_ptr<FunctionAST> ParseDefinition() {
738 getNextToken(); // eat def.
739 auto Proto = ParsePrototype();
740 if (!Proto)
741 return nullptr;
742
743 if (auto E = ParseExpression())
744 return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
745 return nullptr;
746}
747
748/// toplevelexpr ::= expression
749static std::unique_ptr<FunctionAST> ParseTopLevelExpr() {
750 if (auto E = ParseExpression()) {
751 // Make an anonymous proto.
752 auto Proto = std::make_unique<PrototypeAST>("__anon_expr",
753 std::vector<std::string>());
754 return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
755 }
756 return nullptr;
757}
758
759/// external ::= 'extern' prototype
760static std::unique_ptr<PrototypeAST> ParseExtern() {
761 getNextToken(); // eat extern.
762 return ParsePrototype();
763}
764
765//===----------------------------------------------------------------------===//
766// Code Generation
767//===----------------------------------------------------------------------===//
768
769static std::unique_ptr<LLVMContext> TheContext;
770static std::unique_ptr<Module> TheModule;
771static std::unique_ptr<IRBuilder<>> Builder;
772static std::map<std::string, AllocaInst *> NamedValues;
773static std::map<std::string, std::unique_ptr<PrototypeAST>> FunctionProtos;
774static ExitOnError ExitOnErr;
775
776Value *LogErrorV(const char *Str) {
777 LogError(Str);
778 return nullptr;
779}
780
781Function *getFunction(std::string Name) {
782 // First, see if the function has already been added to the current module.
783 if (auto *F = TheModule->getFunction(Name))
784 return F;
785
786 // If not, check whether we can codegen the declaration from some existing
787 // prototype.
788 auto FI = FunctionProtos.find(Name);
789 if (FI != FunctionProtos.end())
790 return FI->second->codegen();
791
792 // If no existing prototype exists, return null.
793 return nullptr;
794}
795
796/// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
797/// the function. This is used for mutable variables etc.
798static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,
799 StringRef VarName) {
800 IRBuilder<> TmpB(&TheFunction->getEntryBlock(),
801 TheFunction->getEntryBlock().begin());
802 return TmpB.CreateAlloca(Type::getDoubleTy(*TheContext), nullptr, VarName);
803}
804
805Value *NumberExprAST::codegen() {
806 return ConstantFP::get(*TheContext, APFloat(Val));
807}
808
809Value* createString(std::string StringValue){
810 auto str = StringValue;
811 auto charType = llvm::IntegerType::get(*TheContext, 8);
812
813 std::vector<llvm::Constant *> chars(str.length());
814 for(unsigned int i = 0; i < str.size(); i++) {
815 chars[i] = llvm::ConstantInt::get(charType, str[i]);
816 }
817
818 chars.push_back(llvm::ConstantInt::get(charType, 0));
819
820 auto stringType = llvm::ArrayType::get(charType, chars.size());
821
822 auto globalDeclaration = (llvm::GlobalVariable*) TheModule->getOrInsertGlobal(".str", stringType);
823 globalDeclaration->setInitializer(llvm::ConstantArray::get(stringType, chars));
824 globalDeclaration->setConstant(true);
825 globalDeclaration->setLinkage(llvm::GlobalValue::LinkageTypes::PrivateLinkage);
826 globalDeclaration->setUnnamedAddr (llvm::GlobalValue::UnnamedAddr::Global);
827
828 return llvm::ConstantExpr::getBitCast(globalDeclaration, charType->getPointerTo());
829}
830
831Value *StringLiteralExprAST::codegen() {
832 return createString(this->StringValue);
833}
834
835Value *VariableExprAST::codegen() {
836 // Look this variable up in the function.
837 Value *V = NamedValues[Name];
838 if (!V)
839 return LogErrorV("Unknown variable name");
840
841 // Load the value.
842 return Builder->CreateLoad(V, Name.c_str());
843}
844
845Value *UnaryExprAST::codegen() {
846 Value *OperandV = Operand->codegen();
847 if (!OperandV)
848 return nullptr;
849
850 Function *F = getFunction(std::string("unary") + Opcode);
851 if (!F)
852 return LogErrorV("Unknown unary operator");
853
854 return Builder->CreateCall(F, OperandV, "unop");
855}
856
857Value *BinaryExprAST::codegen() {
858 // Special case '=' because we don't want to emit the LHS as an expression.
859 if (Op == '=') {
860 // Assignment requires the LHS to be an identifier.
861 // This assume we're building without RTTI because LLVM builds that way by
862 // default. If you build LLVM with RTTI this can be changed to a
863 // dynamic_cast for automatic error checking.
864 VariableExprAST *LHSE = static_cast<VariableExprAST *>(LHS.get());
865 if (!LHSE)
866 return LogErrorV("destination of '=' must be a variable");
867 // Codegen the RHS.
868 Value *Val = RHS->codegen();
869 if (!Val)
870 return nullptr;
871
872 // Look up the name.
873 Value *Variable = NamedValues[LHSE->getName()];
874 if (!Variable)
875 return LogErrorV("Unknown variable name");
876
877 Builder->CreateStore(Val, Variable);
878 return Val;
879 }
880
881 Value *L = LHS->codegen();
882 Value *R = RHS->codegen();
883 if (!L || !R)
884 return nullptr;
885
886 switch (Op) {
887 case '+':
888 return Builder->CreateFAdd(L, R, "addtmp");
889 case '-':
890 return Builder->CreateFSub(L, R, "subtmp");
891 case '*':
892 return Builder->CreateFMul(L, R, "multmp");
893 case '<':
894 L = Builder->CreateFCmpULT(L, R, "cmptmp");
895 // Convert bool 0/1 to double 0.0 or 1.0
896 return Builder->CreateUIToFP(L, Type::getDoubleTy(*TheContext), "booltmp");
897 default:
898 break;
899 }
900
901 // If it wasn't a builtin binary operator, it must be a user defined one. Emit
902 // a call to it.
903 Function *F = getFunction(std::string("binary") + Op);
904 assert(F && "binary operator not found!");
905
906 Value *Ops[] = {L, R};
907 return Builder->CreateCall(F, Ops, "binop");
908}
909
910Value *CallExprAST::codegen() {
911 // Look up the name in the global module table.
912 Function *CalleeF = getFunction(Callee);
913 if (!CalleeF)
914 return LogErrorV("Unknown function referenced");
915
916 // If argument mismatch error.
917 if (CalleeF->arg_size() != Args.size())
918 return LogErrorV("Incorrect # arguments passed");
919
920 std::vector<Value *> ArgsV;
921 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
922 ArgsV.push_back(Args[i]->codegen());
923 if (!ArgsV.back())
924 return nullptr;
925 }
926
927 return Builder->CreateCall(CalleeF, ArgsV, "calltmp");
928}
929
930Value *IfExprAST::codegen() {
931 Value *CondV = Cond->codegen();
932 if (!CondV)
933 return nullptr;
934
935 // Convert condition to a bool by comparing non-equal to 0.0.
936 CondV = Builder->CreateFCmpONE(
937 CondV, ConstantFP::get(*TheContext, APFloat(0.0)), "ifcond");
938
939 Function *TheFunction = Builder->GetInsertBlock()->getParent();
940
941 // Create blocks for the then and else cases. Insert the 'then' block at the
942 // end of the function.
943 BasicBlock *ThenBB = BasicBlock::Create(*TheContext, "then", TheFunction);
944 BasicBlock *ElseBB = BasicBlock::Create(*TheContext, "else");
945 BasicBlock *MergeBB = BasicBlock::Create(*TheContext, "ifcont");
946
947 Builder->CreateCondBr(CondV, ThenBB, ElseBB);
948
949 // Emit then value.
950 Builder->SetInsertPoint(ThenBB);
951
952 Value *ThenV = Then->codegen();
953 if (!ThenV)
954 return nullptr;
955
956 Builder->CreateBr(MergeBB);
957 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
958 ThenBB = Builder->GetInsertBlock();
959
960 // Emit else block.
961 TheFunction->getBasicBlockList().push_back(ElseBB);
962 Builder->SetInsertPoint(ElseBB);
963
964 Value *ElseV = Else->codegen();
965 if (!ElseV)
966 return nullptr;
967
968 Builder->CreateBr(MergeBB);
969 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
970 ElseBB = Builder->GetInsertBlock();
971
972 // Emit merge block.
973 TheFunction->getBasicBlockList().push_back(MergeBB);
974 Builder->SetInsertPoint(MergeBB);
975 PHINode *PN = Builder->CreatePHI(Type::getDoubleTy(*TheContext), 2, "iftmp");
976
977 PN->addIncoming(ThenV, ThenBB);
978 PN->addIncoming(ElseV, ElseBB);
979 return PN;
980}
981
982// Output for-loop as:
983// var = alloca double
984// ...
985// start = startexpr
986// store start -> var
987// goto loop
988// loop:
989// ...
990// bodyexpr
991// ...
992// loopend:
993// step = stepexpr
994// endcond = endexpr
995//
996// curvar = load var
997// nextvar = curvar + step
998// store nextvar -> var
999// br endcond, loop, endloop
1000// outloop:
1001Value *ForExprAST::codegen() {
1002 Function *TheFunction = Builder->GetInsertBlock()->getParent();
1003
1004 // Create an alloca for the variable in the entry block.
1005 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
1006
1007 // Emit the start code first, without 'variable' in scope.
1008 Value *StartVal = Start->codegen();
1009 if (!StartVal)
1010 return nullptr;
1011
1012 // Store the value into the alloca.
1013 Builder->CreateStore(StartVal, Alloca);
1014
1015 // Make the new basic block for the loop header, inserting after current
1016 // block.
1017 BasicBlock *LoopBB = BasicBlock::Create(*TheContext, "loop", TheFunction);
1018
1019 // Insert an explicit fall through from the current block to the LoopBB.
1020 Builder->CreateBr(LoopBB);
1021
1022 // Start insertion in LoopBB.
1023 Builder->SetInsertPoint(LoopBB);
1024
1025 // Within the loop, the variable is defined equal to the PHI node. If it
1026 // shadows an existing variable, we have to restore it, so save it now.
1027 AllocaInst *OldVal = NamedValues[VarName];
1028 NamedValues[VarName] = Alloca;
1029
1030 // Emit the body of the loop. This, like any other expr, can change the
1031 // current BB. Note that we ignore the value computed by the body, but don't
1032 // allow an error.
1033 if (!Body->codegen())
1034 return nullptr;
1035
1036 // Emit the step value.
1037 Value *StepVal = nullptr;
1038 if (Step) {
1039 StepVal = Step->codegen();
1040 if (!StepVal)
1041 return nullptr;
1042 } else {
1043 // If not specified, use 1.0.
1044 StepVal = ConstantFP::get(*TheContext, APFloat(1.0));
1045 }
1046
1047 // Compute the end condition.
1048 Value *EndCond = End->codegen();
1049 if (!EndCond)
1050 return nullptr;
1051
1052 // Reload, increment, and restore the alloca. This handles the case where
1053 // the body of the loop mutates the variable.
1054 Value *CurVar = Builder->CreateLoad(Alloca, VarName.c_str());
1055 Value *NextVar = Builder->CreateFAdd(CurVar, StepVal, "nextvar");
1056 Builder->CreateStore(NextVar, Alloca);
1057
1058 // Convert condition to a bool by comparing non-equal to 0.0.
1059 EndCond = Builder->CreateFCmpONE(
1060 EndCond, ConstantFP::get(*TheContext, APFloat(0.0)), "loopcond");
1061
1062 // Create the "after loop" block and insert it.
1063 BasicBlock *AfterBB =
1064 BasicBlock::Create(*TheContext, "afterloop", TheFunction);
1065
1066 // Insert the conditional branch into the end of LoopEndBB.
1067 Builder->CreateCondBr(EndCond, LoopBB, AfterBB);
1068
1069 // Any new code will be inserted in AfterBB.
1070 Builder->SetInsertPoint(AfterBB);
1071
1072 // Restore the unshadowed variable.
1073 if (OldVal)
1074 NamedValues[VarName] = OldVal;
1075 else
1076 NamedValues.erase(VarName);
1077
1078 // for expr always returns 0.0.
1079 return Constant::getNullValue(Type::getDoubleTy(*TheContext));
1080}
1081
1082Value *VarExprAST::codegen() {
1083 std::vector<AllocaInst *> OldBindings;
1084
1085 Function *TheFunction = Builder->GetInsertBlock()->getParent();
1086
1087 // Register all variables and emit their initializer.
1088 for (unsigned i = 0, e = Variables.size(); i != e; ++i) {
1089 const std::string &VarName = Variables[i].first;
1090
1091 std::string Type = Variables[i].second.first;
1092 ExprAST *Init = Variables[i].second.second.get();
1093 printf("Got varName %s:%s\n", VarName.c_str(), Type.c_str());
1094 // Emit the initializer before adding the variable to scope, this prevents
1095 // the initializer from referencing the variable itself, and permits stuff
1096 // like this:
1097 // var a = 1 in
1098 // var a = a in ... # refers to outer 'a'.
1099
1100 Value *InitVal;
1101 if (Init) {
1102 InitVal = Init->codegen();
1103 if (!InitVal)
1104 return nullptr;
1105 } else { // If not specified, use 0.0.
1106 if(Type == "String"){
1107 InitVal = createString("");
1108 }else if(Type == "Double"){
1109 InitVal = ConstantFP::get(*TheContext, APFloat(0.0));
1110 }else{
1111 return LogErrorV("Fatal crash");
1112 }
1113 }
1114
1115 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
1116 Builder->CreateStore(InitVal, Alloca);
1117
1118 // Remember the old variable binding so that we can restore the binding when
1119 // we unrecurse.
1120 OldBindings.push_back(NamedValues[VarName]);
1121
1122 // Remember this binding.
1123 NamedValues[VarName] = Alloca;
1124 }
1125
1126 // Codegen the body, now that all vars are in scope.
1127 Value *BodyVal = Body->codegen();
1128 if (!BodyVal)
1129 return nullptr;
1130
1131 // Pop all our variables from scope.
1132 for (unsigned i = 0, e = Variables.size(); i != e; ++i)
1133 NamedValues[Variables[i].first] = OldBindings[i];
1134
1135 // Return the body computation.
1136 return BodyVal;
1137}
1138
1139Function *PrototypeAST::codegen() {
1140 // Make the function type: double(double,double) etc.
1141 std::vector<Type *> Doubles(Args.size(), Type::getDoubleTy(*TheContext));
1142 FunctionType *FT =
1143 FunctionType::get(Type::getDoubleTy(*TheContext), Doubles, false);
1144
1145 Function *F =
1146 Function::Create(FT, Function::ExternalLinkage, Name, TheModule.get());
1147
1148 // Set names for all arguments.
1149 unsigned Idx = 0;
1150 for (auto &Arg : F->args())
1151 Arg.setName(Args[Idx++]);
1152
1153 return F;
1154}
1155
1156Function *FunctionAST::codegen() {
1157 // Transfer ownership of the prototype to the FunctionProtos map, but keep a
1158 // reference to it for use below.
1159 auto &P = *Proto;
1160 FunctionProtos[Proto->getName()] = std::move(Proto);
1161 Function *TheFunction = getFunction(P.getName());
1162 if (!TheFunction)
1163 return nullptr;
1164
1165 // If this is an operator, install it.
1166 if (P.isBinaryOp())
1167 BinopPrecedence[P.getOperatorName()] = P.getBinaryPrecedence();
1168
1169 // Create a new basic block to start insertion into.
1170 BasicBlock *BB = BasicBlock::Create(*TheContext, "entry", TheFunction);
1171 Builder->SetInsertPoint(BB);
1172
1173 // Record the function arguments in the NamedValues map.
1174 NamedValues.clear();
1175 for (auto &Arg : TheFunction->args()) {
1176 // Create an alloca for this variable.
1177 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, Arg.getName());
1178
1179 // Store the initial value into the alloca.
1180 Builder->CreateStore(&Arg, Alloca);
1181
1182 // Add arguments to variable symbol table.
1183 NamedValues[std::string(Arg.getName())] = Alloca;
1184 }
1185
1186 if (Value *RetVal = Body->codegen()) {
1187 // Finish off the function.
1188 Builder->CreateRet(RetVal);
1189
1190 // Validate the generated code, checking for consistency.
1191 verifyFunction(*TheFunction);
1192
1193 return TheFunction;
1194 }
1195
1196 // Error reading body, remove function.
1197 TheFunction->eraseFromParent();
1198
1199 if (P.isBinaryOp())
1200 BinopPrecedence.erase(P.getOperatorName());
1201 return nullptr;
1202}
1203
1204//===----------------------------------------------------------------------===//
1205// Top-Level parsing and JIT Driver
1206//===----------------------------------------------------------------------===//
1207
1208static void InitializeModuleAndPassManager() {
1209 // Open a new module.
1210 TheContext = std::make_unique<LLVMContext>();
1211 TheModule = std::make_unique<Module>("my cool jit", *TheContext);
1212
1213 // Create a new builder for the module.
1214 Builder = std::make_unique<IRBuilder<>>(*TheContext);
1215}
1216
1217static void HandleDefinition() {
1218 if (auto FnAST = ParseDefinition()) {
1219 if (auto *FnIR = FnAST->codegen()) {
1220 fprintf(stderr, "Read function definition:");
1221 FnIR->print(errs());
1222 fprintf(stderr, "\n");
1223 }
1224 } else {
1225 // Skip token for error recovery.
1226 getNextToken();
1227 }
1228}
1229
1230static void HandleExtern() {
1231 if (auto ProtoAST = ParseExtern()) {
1232 if (auto *FnIR = ProtoAST->codegen()) {
1233 fprintf(stderr, "Read extern: ");
1234 FnIR->print(errs());
1235 fprintf(stderr, "\n");
1236 FunctionProtos[ProtoAST->getName()] = std::move(ProtoAST);
1237 }
1238 } else {
1239 // Skip token for error recovery.
1240 getNextToken();
1241 }
1242}
1243
1244static void HandleTopLevelExpression() {
1245 // Evaluate a top-level expression into an anonymous function.
1246 if (auto FnAST = ParseTopLevelExpr()) {
1247 FnAST->codegen();
1248 } else {
1249 // Skip token for error recovery.
1250 getNextToken();
1251 }
1252}
1253
1254/// top ::= definition | external | expression | ';'
1255static void MainLoop() {
1256 while (true) {
1257 switch (CurTok) {
1258 case tok_eof:
1259 return;
1260 case ';': // ignore top-level semicolons.
1261 getNextToken();
1262 break;
1263 case tok_def:
1264 HandleDefinition();
1265 break;
1266 case tok_extern:
1267 HandleExtern();
1268 break;
1269 default:
1270 HandleTopLevelExpression();
1271 break;
1272 }
1273 }
1274}
1275
1276//===----------------------------------------------------------------------===//
1277// "Library" functions that can be "extern'd" from user code.
1278//===----------------------------------------------------------------------===//
1279
1280#ifdef _WIN32
1281#define DLLEXPORT __declspec(dllexport)
1282#else
1283#define DLLEXPORT
1284#endif
1285
1286/// putchard - putchar that takes a double and returns 0.
1287extern "C" DLLEXPORT double putchard(double X) {
1288 fputc((char)X, stderr);
1289 return 0;
1290}
1291
1292/// printd - printf that takes a double prints it as "%f\n", returning 0.
1293extern "C" DLLEXPORT double printd(double X) {
1294 fprintf(stderr, "%f\n", X);
1295 return 0;
1296}
1297
1298//===----------------------------------------------------------------------===//
1299// Main driver code.
1300//===----------------------------------------------------------------------===//
1301
1302int main() {
1303 // Install standard binary operators.
1304 // 1 is lowest precedence.
1305 BinopPrecedence['<'] = 10;
1306 BinopPrecedence['+'] = 20;
1307 BinopPrecedence['-'] = 20;
1308 BinopPrecedence['*'] = 40; // highest.
1309
1310 // Prime the first token.
1311 fprintf(stderr, "ready> ");
1312 getNextToken();
1313
1314 InitializeModuleAndPassManager();
1315
1316 // Run the main "interpreter loop" now.
1317 MainLoop();
1318
1319 // Initialize the target registry etc.
1320 InitializeAllTargetInfos();
1321 InitializeAllTargets();
1322 InitializeAllTargetMCs();
1323 InitializeAllAsmParsers();
1324 InitializeAllAsmPrinters();
1325
1326 auto TargetTriple = sys::getDefaultTargetTriple();
1327 TheModule->setTargetTriple(TargetTriple);
1328
1329 std::string Error;
1330 auto Target = TargetRegistry::lookupTarget(TargetTriple, Error);
1331
1332 // Print an error and exit if we couldn't find the requested target.
1333 // This generally occurs if we've forgotten to initialise the
1334 // TargetRegistry or we have a bogus target triple.
1335 if (!Target) {
1336 errs() << Error;
1337 return 1;
1338 }
1339
1340 auto CPU = "generic";
1341 auto Features = "";
1342
1343 TargetOptions opt;
1344 auto RM = Optional<Reloc::Model>();
1345 auto TheTargetMachine =
1346 Target->createTargetMachine(TargetTriple, CPU, Features, opt, RM);
1347
1348 TheModule->setDataLayout(TheTargetMachine->createDataLayout());
1349
1350 printf("Error");
1351 auto Filename = "output.o";
1352 std::error_code EC;
1353 raw_fd_ostream dest(Filename, EC, sys::fs::OF_None);
1354
1355 if (EC) {
1356 errs() << "Could not open file: " << EC.message();
1357 return 1;
1358 }
1359
1360 legacy::PassManager pass;
1361 auto FileType = CGFT_ObjectFile;
1362
1363 if (TheTargetMachine->addPassesToEmitFile(pass, dest, nullptr, FileType)) {
1364 errs() << "TheTargetMachine can't emit a file of this type";
1365 return 1;
1366 }
1367
1368 pass.run(*TheModule);
1369 dest.flush();
1370
1371 outs() << "Wrote " << Filename << "\n";
1372
1373 return 0;
1374}
1375