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