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