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