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

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