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