1421 lines · cpp
1#define MINIMAL_STDERR_OUTPUT2 3#include "llvm/Analysis/Passes.h"4#include "llvm/ExecutionEngine/ExecutionEngine.h"5#include "llvm/ExecutionEngine/MCJIT.h"6#include "llvm/ExecutionEngine/SectionMemoryManager.h"7#include "llvm/IR/DataLayout.h"8#include "llvm/IR/DerivedTypes.h"9#include "llvm/IR/IRBuilder.h"10#include "llvm/IR/LLVMContext.h"11#include "llvm/IR/LegacyPassManager.h"12#include "llvm/IR/Module.h"13#include "llvm/IR/Verifier.h"14#include "llvm/Support/TargetSelect.h"15#include "llvm/Transforms/Scalar.h"16#include <cctype>17#include <cstdio>18#include <map>19#include <string>20#include <vector>21using namespace llvm;22 23//===----------------------------------------------------------------------===//24// Lexer25//===----------------------------------------------------------------------===//26 27// The lexer returns tokens [0-255] if it is an unknown character, otherwise one28// of these for known things.29enum Token {30 tok_eof = -1,31 32 // commands33 tok_def = -2, tok_extern = -3,34 35 // primary36 tok_identifier = -4, tok_number = -5,37 38 // control39 tok_if = -6, tok_then = -7, tok_else = -8,40 tok_for = -9, tok_in = -10,41 42 // operators43 tok_binary = -11, tok_unary = -12,44 45 // var definition46 tok_var = -1347};48 49static std::string IdentifierStr; // Filled in if tok_identifier50static double NumVal; // Filled in if tok_number51 52/// gettok - Return the next token from standard input.53static int gettok() {54 static int LastChar = ' ';55 56 // Skip any whitespace.57 while (isspace(LastChar))58 LastChar = getchar();59 60 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*61 IdentifierStr = LastChar;62 while (isalnum((LastChar = getchar())))63 IdentifierStr += LastChar;64 65 if (IdentifierStr == "def") return tok_def;66 if (IdentifierStr == "extern") return tok_extern;67 if (IdentifierStr == "if") return tok_if;68 if (IdentifierStr == "then") return tok_then;69 if (IdentifierStr == "else") return tok_else;70 if (IdentifierStr == "for") return tok_for;71 if (IdentifierStr == "in") return tok_in;72 if (IdentifierStr == "binary") return tok_binary;73 if (IdentifierStr == "unary") return tok_unary;74 if (IdentifierStr == "var") return tok_var;75 return tok_identifier;76 }77 78 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+79 std::string NumStr;80 do {81 NumStr += LastChar;82 LastChar = getchar();83 } while (isdigit(LastChar) || LastChar == '.');84 85 NumVal = strtod(NumStr.c_str(), 0);86 return tok_number;87 }88 89 if (LastChar == '#') {90 // Comment until end of line.91 do LastChar = getchar();92 while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');93 94 if (LastChar != EOF)95 return gettok();96 }97 98 // Check for end of file. Don't eat the EOF.99 if (LastChar == EOF)100 return tok_eof;101 102 // Otherwise, just return the character as its ascii value.103 int ThisChar = LastChar;104 LastChar = getchar();105 return ThisChar;106}107 108//===----------------------------------------------------------------------===//109// Abstract Syntax Tree (aka Parse Tree)110//===----------------------------------------------------------------------===//111 112/// ExprAST - Base class for all expression nodes.113class ExprAST {114public:115 virtual ~ExprAST() {}116 virtual Value *Codegen() = 0;117};118 119/// NumberExprAST - Expression class for numeric literals like "1.0".120class NumberExprAST : public ExprAST {121 double Val;122public:123 NumberExprAST(double val) : Val(val) {}124 virtual Value *Codegen();125};126 127/// VariableExprAST - Expression class for referencing a variable, like "a".128class VariableExprAST : public ExprAST {129 std::string Name;130public:131 VariableExprAST(const std::string &name) : Name(name) {}132 const std::string &getName() const { return Name; }133 virtual Value *Codegen();134};135 136/// UnaryExprAST - Expression class for a unary operator.137class UnaryExprAST : public ExprAST {138 char Opcode;139 ExprAST *Operand;140public:141 UnaryExprAST(char opcode, ExprAST *operand)142 : Opcode(opcode), Operand(operand) {}143 virtual Value *Codegen();144};145 146/// BinaryExprAST - Expression class for a binary operator.147class BinaryExprAST : public ExprAST {148 char Op;149 ExprAST *LHS, *RHS;150public:151 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)152 : Op(op), LHS(lhs), RHS(rhs) {}153 virtual Value *Codegen();154};155 156/// CallExprAST - Expression class for function calls.157class CallExprAST : public ExprAST {158 std::string Callee;159 std::vector<ExprAST*> Args;160public:161 CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)162 : Callee(callee), Args(args) {}163 virtual Value *Codegen();164};165 166/// IfExprAST - Expression class for if/then/else.167class IfExprAST : public ExprAST {168 ExprAST *Cond, *Then, *Else;169public:170 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)171 : Cond(cond), Then(then), Else(_else) {}172 virtual Value *Codegen();173};174 175/// ForExprAST - Expression class for for/in.176class ForExprAST : public ExprAST {177 std::string VarName;178 ExprAST *Start, *End, *Step, *Body;179public:180 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,181 ExprAST *step, ExprAST *body)182 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}183 virtual Value *Codegen();184};185 186/// VarExprAST - Expression class for var/in187class VarExprAST : public ExprAST {188 std::vector<std::pair<std::string, ExprAST*> > VarNames;189 ExprAST *Body;190public:191 VarExprAST(const std::vector<std::pair<std::string, ExprAST*> > &varnames,192 ExprAST *body)193 : VarNames(varnames), Body(body) {}194 195 virtual Value *Codegen();196};197 198/// PrototypeAST - This class represents the "prototype" for a function,199/// which captures its argument names as well as if it is an operator.200class PrototypeAST {201 std::string Name;202 std::vector<std::string> Args;203 bool isOperator;204 unsigned Precedence; // Precedence if a binary op.205public:206 PrototypeAST(const std::string &name, const std::vector<std::string> &args,207 bool isoperator = false, unsigned prec = 0)208 : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {}209 210 bool isUnaryOp() const { return isOperator && Args.size() == 1; }211 bool isBinaryOp() const { return isOperator && Args.size() == 2; }212 213 char getOperatorName() const {214 assert(isUnaryOp() || isBinaryOp());215 return Name[Name.size()-1];216 }217 218 unsigned getBinaryPrecedence() const { return Precedence; }219 220 Function *Codegen();221 222 void CreateArgumentAllocas(Function *F);223};224 225/// FunctionAST - This class represents a function definition itself.226class FunctionAST {227 PrototypeAST *Proto;228 ExprAST *Body;229public:230 FunctionAST(PrototypeAST *proto, ExprAST *body)231 : Proto(proto), Body(body) {}232 233 Function *Codegen();234};235 236//===----------------------------------------------------------------------===//237// Parser238//===----------------------------------------------------------------------===//239 240/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current241/// token the parser is looking at. getNextToken reads another token from the242/// lexer and updates CurTok with its results.243static int CurTok;244static int getNextToken() {245 return CurTok = gettok();246}247 248/// BinopPrecedence - This holds the precedence for each binary operator that is249/// defined.250static std::map<char, int> BinopPrecedence;251 252/// GetTokPrecedence - Get the precedence of the pending binary operator token.253static int GetTokPrecedence() {254 if (!isascii(CurTok))255 return -1;256 257 // Make sure it's a declared binop.258 int TokPrec = BinopPrecedence[CurTok];259 if (TokPrec <= 0) return -1;260 return TokPrec;261}262 263/// Error* - These are little helper functions for error handling.264ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}265PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }266FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }267 268static ExprAST *ParseExpression();269 270/// identifierexpr271/// ::= identifier272/// ::= identifier '(' expression* ')'273static ExprAST *ParseIdentifierExpr() {274 std::string IdName = IdentifierStr;275 276 getNextToken(); // eat identifier.277 278 if (CurTok != '(') // Simple variable ref.279 return new VariableExprAST(IdName);280 281 // Call.282 getNextToken(); // eat (283 std::vector<ExprAST*> Args;284 if (CurTok != ')') {285 while (1) {286 ExprAST *Arg = ParseExpression();287 if (!Arg) return 0;288 Args.push_back(Arg);289 290 if (CurTok == ')') break;291 292 if (CurTok != ',')293 return Error("Expected ')' or ',' in argument list");294 getNextToken();295 }296 }297 298 // Eat the ')'.299 getNextToken();300 301 return new CallExprAST(IdName, Args);302}303 304/// numberexpr ::= number305static ExprAST *ParseNumberExpr() {306 ExprAST *Result = new NumberExprAST(NumVal);307 getNextToken(); // consume the number308 return Result;309}310 311/// parenexpr ::= '(' expression ')'312static ExprAST *ParseParenExpr() {313 getNextToken(); // eat (.314 ExprAST *V = ParseExpression();315 if (!V) return 0;316 317 if (CurTok != ')')318 return Error("expected ')'");319 getNextToken(); // eat ).320 return V;321}322 323/// ifexpr ::= 'if' expression 'then' expression 'else' expression324static ExprAST *ParseIfExpr() {325 getNextToken(); // eat the if.326 327 // condition.328 ExprAST *Cond = ParseExpression();329 if (!Cond) return 0;330 331 if (CurTok != tok_then)332 return Error("expected then");333 getNextToken(); // eat the then334 335 ExprAST *Then = ParseExpression();336 if (Then == 0) return 0;337 338 if (CurTok != tok_else)339 return Error("expected else");340 341 getNextToken();342 343 ExprAST *Else = ParseExpression();344 if (!Else) return 0;345 346 return new IfExprAST(Cond, Then, Else);347}348 349/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression350static ExprAST *ParseForExpr() {351 getNextToken(); // eat the for.352 353 if (CurTok != tok_identifier)354 return Error("expected identifier after for");355 356 std::string IdName = IdentifierStr;357 getNextToken(); // eat identifier.358 359 if (CurTok != '=')360 return Error("expected '=' after for");361 getNextToken(); // eat '='.362 363 364 ExprAST *Start = ParseExpression();365 if (Start == 0) return 0;366 if (CurTok != ',')367 return Error("expected ',' after for start value");368 getNextToken();369 370 ExprAST *End = ParseExpression();371 if (End == 0) return 0;372 373 // The step value is optional.374 ExprAST *Step = 0;375 if (CurTok == ',') {376 getNextToken();377 Step = ParseExpression();378 if (Step == 0) return 0;379 }380 381 if (CurTok != tok_in)382 return Error("expected 'in' after for");383 getNextToken(); // eat 'in'.384 385 ExprAST *Body = ParseExpression();386 if (Body == 0) return 0;387 388 return new ForExprAST(IdName, Start, End, Step, Body);389}390 391/// varexpr ::= 'var' identifier ('=' expression)?392// (',' identifier ('=' expression)?)* 'in' expression393static ExprAST *ParseVarExpr() {394 getNextToken(); // eat the var.395 396 std::vector<std::pair<std::string, ExprAST*> > VarNames;397 398 // At least one variable name is required.399 if (CurTok != tok_identifier)400 return Error("expected identifier after var");401 402 while (1) {403 std::string Name = IdentifierStr;404 getNextToken(); // eat identifier.405 406 // Read the optional initializer.407 ExprAST *Init = 0;408 if (CurTok == '=') {409 getNextToken(); // eat the '='.410 411 Init = ParseExpression();412 if (Init == 0) return 0;413 }414 415 VarNames.push_back(std::make_pair(Name, Init));416 417 // End of var list, exit loop.418 if (CurTok != ',') break;419 getNextToken(); // eat the ','.420 421 if (CurTok != tok_identifier)422 return Error("expected identifier list after var");423 }424 425 // At this point, we have to have 'in'.426 if (CurTok != tok_in)427 return Error("expected 'in' keyword after 'var'");428 getNextToken(); // eat 'in'.429 430 ExprAST *Body = ParseExpression();431 if (Body == 0) return 0;432 433 return new VarExprAST(VarNames, Body);434}435 436/// primary437/// ::= identifierexpr438/// ::= numberexpr439/// ::= parenexpr440/// ::= ifexpr441/// ::= forexpr442/// ::= varexpr443static ExprAST *ParsePrimary() {444 switch (CurTok) {445 default: return Error("unknown token when expecting an expression");446 case tok_identifier: return ParseIdentifierExpr();447 case tok_number: return ParseNumberExpr();448 case '(': return ParseParenExpr();449 case tok_if: return ParseIfExpr();450 case tok_for: return ParseForExpr();451 case tok_var: return ParseVarExpr();452 }453}454 455/// unary456/// ::= primary457/// ::= '!' unary458static ExprAST *ParseUnary() {459 // If the current token is not an operator, it must be a primary expr.460 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')461 return ParsePrimary();462 463 // If this is a unary operator, read it.464 int Opc = CurTok;465 getNextToken();466 if (ExprAST *Operand = ParseUnary())467 return new UnaryExprAST(Opc, Operand);468 return 0;469}470 471/// binoprhs472/// ::= ('+' unary)*473static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {474 // If this is a binop, find its precedence.475 while (1) {476 int TokPrec = GetTokPrecedence();477 478 // If this is a binop that binds at least as tightly as the current binop,479 // consume it, otherwise we are done.480 if (TokPrec < ExprPrec)481 return LHS;482 483 // Okay, we know this is a binop.484 int BinOp = CurTok;485 getNextToken(); // eat binop486 487 // Parse the unary expression after the binary operator.488 ExprAST *RHS = ParseUnary();489 if (!RHS) return 0;490 491 // If BinOp binds less tightly with RHS than the operator after RHS, let492 // the pending operator take RHS as its LHS.493 int NextPrec = GetTokPrecedence();494 if (TokPrec < NextPrec) {495 RHS = ParseBinOpRHS(TokPrec+1, RHS);496 if (RHS == 0) return 0;497 }498 499 // Merge LHS/RHS.500 LHS = new BinaryExprAST(BinOp, LHS, RHS);501 }502}503 504/// expression505/// ::= unary binoprhs506///507static ExprAST *ParseExpression() {508 ExprAST *LHS = ParseUnary();509 if (!LHS) return 0;510 511 return ParseBinOpRHS(0, LHS);512}513 514/// prototype515/// ::= id '(' id* ')'516/// ::= binary LETTER number? (id, id)517/// ::= unary LETTER (id)518static PrototypeAST *ParsePrototype() {519 std::string FnName;520 521 unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.522 unsigned BinaryPrecedence = 30;523 524 switch (CurTok) {525 default:526 return ErrorP("Expected function name in prototype");527 case tok_identifier:528 FnName = IdentifierStr;529 Kind = 0;530 getNextToken();531 break;532 case tok_unary:533 getNextToken();534 if (!isascii(CurTok))535 return ErrorP("Expected unary operator");536 FnName = "unary";537 FnName += (char)CurTok;538 Kind = 1;539 getNextToken();540 break;541 case tok_binary:542 getNextToken();543 if (!isascii(CurTok))544 return ErrorP("Expected binary operator");545 FnName = "binary";546 FnName += (char)CurTok;547 Kind = 2;548 getNextToken();549 550 // Read the precedence if present.551 if (CurTok == tok_number) {552 if (NumVal < 1 || NumVal > 100)553 return ErrorP("Invalid precedence: must be 1..100");554 BinaryPrecedence = (unsigned)NumVal;555 getNextToken();556 }557 break;558 }559 560 if (CurTok != '(')561 return ErrorP("Expected '(' in prototype");562 563 std::vector<std::string> ArgNames;564 while (getNextToken() == tok_identifier)565 ArgNames.push_back(IdentifierStr);566 if (CurTok != ')')567 return ErrorP("Expected ')' in prototype");568 569 // success.570 getNextToken(); // eat ')'.571 572 // Verify right number of names for operator.573 if (Kind && ArgNames.size() != Kind)574 return ErrorP("Invalid number of operands for operator");575 576 return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);577}578 579/// definition ::= 'def' prototype expression580static FunctionAST *ParseDefinition() {581 getNextToken(); // eat def.582 PrototypeAST *Proto = ParsePrototype();583 if (Proto == 0) return 0;584 585 if (ExprAST *E = ParseExpression())586 return new FunctionAST(Proto, E);587 return 0;588}589 590/// toplevelexpr ::= expression591static FunctionAST *ParseTopLevelExpr() {592 if (ExprAST *E = ParseExpression()) {593 // Make an anonymous proto.594 PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());595 return new FunctionAST(Proto, E);596 }597 return 0;598}599 600/// external ::= 'extern' prototype601static PrototypeAST *ParseExtern() {602 getNextToken(); // eat extern.603 return ParsePrototype();604}605 606//===----------------------------------------------------------------------===//607// Quick and dirty hack608//===----------------------------------------------------------------------===//609 610// FIXME: Obviously we can do better than this611std::string GenerateUniqueName(const char *root)612{613 static int i = 0;614 char s[16];615 sprintf(s, "%s%d", root, i++);616 std::string S = s;617 return S;618}619 620std::string MakeLegalFunctionName(std::string Name)621{622 std::string NewName;623 if (!Name.length())624 return GenerateUniqueName("anon_func_");625 626 // Start with what we have627 NewName = Name;628 629 // Look for a numeric first character630 if (NewName.find_first_of("0123456789") == 0) {631 NewName.insert(0, 1, 'n');632 }633 634 // Replace illegal characters with their ASCII equivalent635 std::string legal_elements = "_abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";636 size_t pos;637 while ((pos = NewName.find_first_not_of(legal_elements)) != std::string::npos) {638 char old_c = NewName.at(pos);639 char new_str[16];640 sprintf(new_str, "%d", (int)old_c);641 NewName = NewName.replace(pos, 1, new_str);642 }643 644 return NewName;645}646 647//===----------------------------------------------------------------------===//648// MCJIT helper class649//===----------------------------------------------------------------------===//650 651class MCJITHelper652{653public:654 MCJITHelper(LLVMContext& C) : Context(C), OpenModule(NULL) {}655 ~MCJITHelper();656 657 Function *getFunction(const std::string FnName);658 Module *getModuleForNewFunction();659 void *getPointerToFunction(Function* F);660 void *getPointerToNamedFunction(const std::string &Name);661 ExecutionEngine *compileModule(Module *M);662 void closeCurrentModule();663 void dump();664 665private:666 typedef std::vector<Module*> ModuleVector;667 668 LLVMContext &Context;669 Module *OpenModule;670 ModuleVector Modules;671 std::map<Module *, ExecutionEngine *> EngineMap;672};673 674class HelpingMemoryManager : public SectionMemoryManager675{676 HelpingMemoryManager(const HelpingMemoryManager&) = delete;677 void operator=(const HelpingMemoryManager&) = delete;678 679public:680 HelpingMemoryManager(MCJITHelper *Helper) : MasterHelper(Helper) {}681 virtual ~HelpingMemoryManager() {}682 683 /// This method returns the address of the specified function.684 /// Our implementation will attempt to find functions in other685 /// modules associated with the MCJITHelper to cross link functions686 /// from one generated module to another.687 ///688 /// If \p AbortOnFailure is false and no function with the given name is689 /// found, this function returns a null pointer. Otherwise, it prints a690 /// message to stderr and aborts.691 virtual void *getPointerToNamedFunction(const std::string &Name,692 bool AbortOnFailure = true);693private:694 MCJITHelper *MasterHelper;695};696 697void *HelpingMemoryManager::getPointerToNamedFunction(const std::string &Name,698 bool AbortOnFailure)699{700 // Try the standard symbol resolution first, but ask it not to abort.701 void *pfn = SectionMemoryManager::getPointerToNamedFunction(Name, false);702 if (pfn)703 return pfn;704 705 pfn = MasterHelper->getPointerToNamedFunction(Name);706 if (!pfn && AbortOnFailure)707 report_fatal_error("Program used external function '" + Name +708 "' which could not be resolved!");709 return pfn;710}711 712MCJITHelper::~MCJITHelper()713{714 // Walk the vector of modules.715 ModuleVector::iterator it, end;716 for (it = Modules.begin(), end = Modules.end();717 it != end; ++it) {718 // See if we have an execution engine for this module.719 std::map<Module*, ExecutionEngine*>::iterator mapIt = EngineMap.find(*it);720 // If we have an EE, the EE owns the module so just delete the EE.721 if (mapIt != EngineMap.end()) {722 delete mapIt->second;723 } else {724 // Otherwise, we still own the module. Delete it now.725 delete *it;726 }727 }728}729 730Function *MCJITHelper::getFunction(const std::string FnName) {731 ModuleVector::iterator begin = Modules.begin();732 ModuleVector::iterator end = Modules.end();733 ModuleVector::iterator it;734 for (it = begin; it != end; ++it) {735 Function *F = (*it)->getFunction(FnName);736 if (F) {737 if (*it == OpenModule)738 return F;739 740 assert(OpenModule != NULL);741 742 // This function is in a module that has already been JITed.743 // We need to generate a new prototype for external linkage.744 Function *PF = OpenModule->getFunction(FnName);745 if (PF && !PF->empty()) {746 ErrorF("redefinition of function across modules");747 return 0;748 }749 750 // If we don't have a prototype yet, create one.751 if (!PF)752 PF = Function::Create(F->getFunctionType(),753 Function::ExternalLinkage,754 FnName,755 OpenModule);756 return PF;757 }758 }759 return NULL;760}761 762Module *MCJITHelper::getModuleForNewFunction() {763 // If we have a Module that hasn't been JITed, use that.764 if (OpenModule)765 return OpenModule;766 767 // Otherwise create a new Module.768 std::string ModName = GenerateUniqueName("mcjit_module_");769 Module *M = new Module(ModName, Context);770 Modules.push_back(M);771 OpenModule = M;772 return M;773}774 775void *MCJITHelper::getPointerToFunction(Function* F) {776 // Look for this function in an existing module777 ModuleVector::iterator begin = Modules.begin();778 ModuleVector::iterator end = Modules.end();779 ModuleVector::iterator it;780 std::string FnName = F->getName();781 for (it = begin; it != end; ++it) {782 Function *MF = (*it)->getFunction(FnName);783 if (MF == F) {784 std::map<Module*, ExecutionEngine*>::iterator eeIt = EngineMap.find(*it);785 if (eeIt != EngineMap.end()) {786 void *P = eeIt->second->getPointerToFunction(F);787 if (P)788 return P;789 } else {790 ExecutionEngine *EE = compileModule(*it);791 void *P = EE->getPointerToFunction(F);792 if (P)793 return P;794 }795 }796 }797 return NULL;798}799 800void MCJITHelper::closeCurrentModule() {801 OpenModule = NULL;802}803 804ExecutionEngine *MCJITHelper::compileModule(Module *M) {805 if (M == OpenModule)806 closeCurrentModule();807 808 std::string ErrStr;809 ExecutionEngine *NewEngine = EngineBuilder(M)810 .setErrorStr(&ErrStr)811 .setMCJITMemoryManager(new HelpingMemoryManager(this))812 .create();813 if (!NewEngine) {814 fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());815 exit(1);816 }817 818 // Create a function pass manager for this engine819 FunctionPassManager *FPM = new FunctionPassManager(M);820 821 // Set up the optimizer pipeline. Start with registering info about how the822 // target lays out data structures.823 FPM->add(new DataLayout(*NewEngine->getDataLayout()));824 // Provide basic AliasAnalysis support for GVN.825 FPM->add(createBasicAliasAnalysisPass());826 // Promote allocas to registers.827 FPM->add(createPromoteMemoryToRegisterPass());828 // Do simple "peephole" optimizations and bit-twiddling optzns.829 FPM->add(createInstructionCombiningPass());830 // Reassociate expressions.831 FPM->add(createReassociatePass());832 // Eliminate Common SubExpressions.833 FPM->add(createGVNPass());834 // Simplify the control flow graph (deleting unreachable blocks, etc).835 FPM->add(createCFGSimplificationPass());836 FPM->doInitialization();837 838 // For each function in the module839 Module::iterator it;840 Module::iterator end = M->end();841 for (it = M->begin(); it != end; ++it) {842 // Run the FPM on this function843 FPM->run(*it);844 }845 846 // We don't need this anymore847 delete FPM;848 849 // Store this engine850 EngineMap[M] = NewEngine;851 NewEngine->finalizeObject();852 853 return NewEngine;854}855 856void *MCJITHelper::getPointerToNamedFunction(const std::string &Name)857{858 // Look for the functions in our modules, compiling only as necessary859 ModuleVector::iterator begin = Modules.begin();860 ModuleVector::iterator end = Modules.end();861 ModuleVector::iterator it;862 for (it = begin; it != end; ++it) {863 Function *F = (*it)->getFunction(Name);864 if (F && !F->empty()) {865 std::map<Module*, ExecutionEngine*>::iterator eeIt = EngineMap.find(*it);866 if (eeIt != EngineMap.end()) {867 void *P = eeIt->second->getPointerToFunction(F);868 if (P)869 return P;870 } else {871 ExecutionEngine *EE = compileModule(*it);872 void *P = EE->getPointerToFunction(F);873 if (P)874 return P;875 }876 }877 }878 return NULL;879}880 881void MCJITHelper::dump()882{883 ModuleVector::iterator begin = Modules.begin();884 ModuleVector::iterator end = Modules.end();885 ModuleVector::iterator it;886 for (it = begin; it != end; ++it)887 (*it)->dump();888}889 890//===----------------------------------------------------------------------===//891// Code Generation892//===----------------------------------------------------------------------===//893 894static MCJITHelper *TheHelper;895static LLVMContext TheContext;896static IRBuilder<> Builder(TheContext);897static std::map<std::string, AllocaInst*> NamedValues;898 899Value *ErrorV(const char *Str) { Error(Str); return 0; }900 901/// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of902/// the function. This is used for mutable variables etc.903static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,904 const std::string &VarName) {905 IRBuilder<> TmpB(&TheFunction->getEntryBlock(),906 TheFunction->getEntryBlock().begin());907 return TmpB.CreateAlloca(Type::getDoubleTy(TheContext), 0, VarName.c_str());908}909 910Value *NumberExprAST::Codegen() {911 return ConstantFP::get(TheContext, APFloat(Val));912}913 914Value *VariableExprAST::Codegen() {915 // Look this variable up in the function.916 Value *V = NamedValues[Name];917 char ErrStr[256];918 sprintf(ErrStr, "Unknown variable name %s", Name.c_str());919 if (V == 0) return ErrorV(ErrStr);920 921 // Load the value.922 return Builder.CreateLoad(V, Name.c_str());923}924 925Value *UnaryExprAST::Codegen() {926 Value *OperandV = Operand->Codegen();927 if (OperandV == 0) return 0;928 929 Function *F = TheHelper->getFunction(MakeLegalFunctionName(std::string("unary")+Opcode));930 if (F == 0)931 return ErrorV("Unknown unary operator");932 933 return Builder.CreateCall(F, OperandV, "unop");934}935 936Value *BinaryExprAST::Codegen() {937 // Special case '=' because we don't want to emit the LHS as an expression.938 if (Op == '=') {939 // Assignment requires the LHS to be an identifier.940 VariableExprAST *LHSE = static_cast<VariableExprAST*>(LHS);941 if (!LHSE)942 return ErrorV("destination of '=' must be a variable");943 // Codegen the RHS.944 Value *Val = RHS->Codegen();945 if (Val == 0) return 0;946 947 // Look up the name.948 Value *Variable = NamedValues[LHSE->getName()];949 if (Variable == 0) return ErrorV("Unknown variable name");950 951 Builder.CreateStore(Val, Variable);952 return Val;953 }954 955 Value *L = LHS->Codegen();956 Value *R = RHS->Codegen();957 if (L == 0 || R == 0) return 0;958 959 switch (Op) {960 case '+': return Builder.CreateFAdd(L, R, "addtmp");961 case '-': return Builder.CreateFSub(L, R, "subtmp");962 case '*': return Builder.CreateFMul(L, R, "multmp");963 case '/': return Builder.CreateFDiv(L, R, "divtmp");964 case '<':965 L = Builder.CreateFCmpULT(L, R, "cmptmp");966 // Convert bool 0/1 to double 0.0 or 1.0967 return Builder.CreateUIToFP(L, Type::getDoubleTy(TheContext), "booltmp");968 default: break;969 }970 971 // If it wasn't a builtin binary operator, it must be a user defined one. Emit972 // a call to it.973 Function *F = TheHelper->getFunction(MakeLegalFunctionName(std::string("binary")+Op));974 assert(F && "binary operator not found!");975 976 Value *Ops[] = { L, R };977 return Builder.CreateCall(F, Ops, "binop");978}979 980Value *CallExprAST::Codegen() {981 // Look up the name in the global module table.982 Function *CalleeF = TheHelper->getFunction(Callee);983 if (CalleeF == 0)984 return ErrorV("Unknown function referenced");985 986 // If argument mismatch error.987 if (CalleeF->arg_size() != Args.size())988 return ErrorV("Incorrect # arguments passed");989 990 std::vector<Value*> ArgsV;991 for (unsigned i = 0, e = Args.size(); i != e; ++i) {992 ArgsV.push_back(Args[i]->Codegen());993 if (ArgsV.back() == 0) return 0;994 }995 996 return Builder.CreateCall(CalleeF, ArgsV, "calltmp");997}998 999Value *IfExprAST::Codegen() {1000 Value *CondV = Cond->Codegen();1001 if (CondV == 0) return 0;1002 1003 // Convert condition to a bool by comparing equal to 0.0.1004 CondV = Builder.CreateFCmpONE(1005 CondV, ConstantFP::get(TheContext, APFloat(0.0)), "ifcond");1006 1007 Function *TheFunction = Builder.GetInsertBlock()->getParent();1008 1009 // Create blocks for the then and else cases. Insert the 'then' block at the1010 // end of the function.1011 BasicBlock *ThenBB = BasicBlock::Create(TheContext, "then", TheFunction);1012 BasicBlock *ElseBB = BasicBlock::Create(TheContext, "else");1013 BasicBlock *MergeBB = BasicBlock::Create(TheContext, "ifcont");1014 1015 Builder.CreateCondBr(CondV, ThenBB, ElseBB);1016 1017 // Emit then value.1018 Builder.SetInsertPoint(ThenBB);1019 1020 Value *ThenV = Then->Codegen();1021 if (ThenV == 0) return 0;1022 1023 Builder.CreateBr(MergeBB);1024 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.1025 ThenBB = Builder.GetInsertBlock();1026 1027 // Emit else block.1028 TheFunction->insert(TheFunction->end(), ElseBB);1029 Builder.SetInsertPoint(ElseBB);1030 1031 Value *ElseV = Else->Codegen();1032 if (ElseV == 0) return 0;1033 1034 Builder.CreateBr(MergeBB);1035 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.1036 ElseBB = Builder.GetInsertBlock();1037 1038 // Emit merge block.1039 TheFunction->insert(TheFunction->end(), MergeBB);1040 Builder.SetInsertPoint(MergeBB);1041 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(TheContext), 2, "iftmp");1042 1043 PN->addIncoming(ThenV, ThenBB);1044 PN->addIncoming(ElseV, ElseBB);1045 return PN;1046}1047 1048Value *ForExprAST::Codegen() {1049 // Output this as:1050 // var = alloca double1051 // ...1052 // start = startexpr1053 // store start -> var1054 // goto loop1055 // loop:1056 // ...1057 // bodyexpr1058 // ...1059 // loopend:1060 // step = stepexpr1061 // endcond = endexpr1062 //1063 // curvar = load var1064 // nextvar = curvar + step1065 // store nextvar -> var1066 // br endcond, loop, endloop1067 // outloop:1068 1069 Function *TheFunction = Builder.GetInsertBlock()->getParent();1070 1071 // Create an alloca for the variable in the entry block.1072 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);1073 1074 // Emit the start code first, without 'variable' in scope.1075 Value *StartVal = Start->Codegen();1076 if (StartVal == 0) return 0;1077 1078 // Store the value into the alloca.1079 Builder.CreateStore(StartVal, Alloca);1080 1081 // Make the new basic block for the loop header, inserting after current1082 // block.1083 BasicBlock *LoopBB = BasicBlock::Create(TheContext, "loop", TheFunction);1084 1085 // Insert an explicit fall through from the current block to the LoopBB.1086 Builder.CreateBr(LoopBB);1087 1088 // Start insertion in LoopBB.1089 Builder.SetInsertPoint(LoopBB);1090 1091 // Within the loop, the variable is defined equal to the PHI node. If it1092 // shadows an existing variable, we have to restore it, so save it now.1093 AllocaInst *OldVal = NamedValues[VarName];1094 NamedValues[VarName] = Alloca;1095 1096 // Emit the body of the loop. This, like any other expr, can change the1097 // current BB. Note that we ignore the value computed by the body, but don't1098 // allow an error.1099 if (Body->Codegen() == 0)1100 return 0;1101 1102 // Emit the step value.1103 Value *StepVal;1104 if (Step) {1105 StepVal = Step->Codegen();1106 if (StepVal == 0) return 0;1107 } else {1108 // If not specified, use 1.0.1109 StepVal = ConstantFP::get(TheContext, APFloat(1.0));1110 }1111 1112 // Compute the end condition.1113 Value *EndCond = End->Codegen();1114 if (EndCond == 0) return EndCond;1115 1116 // Reload, increment, and restore the alloca. This handles the case where1117 // the body of the loop mutates the variable.1118 Value *CurVar = Builder.CreateLoad(Alloca, VarName.c_str());1119 Value *NextVar = Builder.CreateFAdd(CurVar, StepVal, "nextvar");1120 Builder.CreateStore(NextVar, Alloca);1121 1122 // Convert condition to a bool by comparing equal to 0.0.1123 EndCond = Builder.CreateFCmpONE(1124 EndCond, ConstantFP::get(TheContext, APFloat(0.0)), "loopcond");1125 1126 // Create the "after loop" block and insert it.1127 BasicBlock *AfterBB =1128 BasicBlock::Create(TheContext, "afterloop", TheFunction);1129 1130 // Insert the conditional branch into the end of LoopEndBB.1131 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);1132 1133 // Any new code will be inserted in AfterBB.1134 Builder.SetInsertPoint(AfterBB);1135 1136 // Restore the unshadowed variable.1137 if (OldVal)1138 NamedValues[VarName] = OldVal;1139 else1140 NamedValues.erase(VarName);1141 1142 1143 // for expr always returns 0.0.1144 return Constant::getNullValue(Type::getDoubleTy(TheContext));1145}1146 1147Value *VarExprAST::Codegen() {1148 std::vector<AllocaInst *> OldBindings;1149 1150 Function *TheFunction = Builder.GetInsertBlock()->getParent();1151 1152 // Register all variables and emit their initializer.1153 for (unsigned i = 0, e = VarNames.size(); i != e; ++i) {1154 const std::string &VarName = VarNames[i].first;1155 ExprAST *Init = VarNames[i].second;1156 1157 // Emit the initializer before adding the variable to scope, this prevents1158 // the initializer from referencing the variable itself, and permits stuff1159 // like this:1160 // var a = 1 in1161 // var a = a in ... # refers to outer 'a'.1162 Value *InitVal;1163 if (Init) {1164 InitVal = Init->Codegen();1165 if (InitVal == 0) return 0;1166 } else { // If not specified, use 0.0.1167 InitVal = ConstantFP::get(TheContext, APFloat(0.0));1168 }1169 1170 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);1171 Builder.CreateStore(InitVal, Alloca);1172 1173 // Remember the old variable binding so that we can restore the binding when1174 // we unrecurse.1175 OldBindings.push_back(NamedValues[VarName]);1176 1177 // Remember this binding.1178 NamedValues[VarName] = Alloca;1179 }1180 1181 // Codegen the body, now that all vars are in scope.1182 Value *BodyVal = Body->Codegen();1183 if (BodyVal == 0) return 0;1184 1185 // Pop all our variables from scope.1186 for (unsigned i = 0, e = VarNames.size(); i != e; ++i)1187 NamedValues[VarNames[i].first] = OldBindings[i];1188 1189 // Return the body computation.1190 return BodyVal;1191}1192 1193Function *PrototypeAST::Codegen() {1194 // Make the function type: double(double,double) etc.1195 std::vector<Type *> Doubles(Args.size(), Type::getDoubleTy(TheContext));1196 FunctionType *FT =1197 FunctionType::get(Type::getDoubleTy(TheContext), Doubles, false);1198 1199 std::string FnName = MakeLegalFunctionName(Name);1200 1201 Module* M = TheHelper->getModuleForNewFunction();1202 1203 Function *F = Function::Create(FT, Function::ExternalLinkage, FnName, M);1204 1205 // If F conflicted, there was already something named 'FnName'. If it has a1206 // body, don't allow redefinition or reextern.1207 if (F->getName() != FnName) {1208 // Delete the one we just made and get the existing one.1209 F->eraseFromParent();1210 F = M->getFunction(Name);1211 1212 // If F already has a body, reject this.1213 if (!F->empty()) {1214 ErrorF("redefinition of function");1215 return 0;1216 }1217 1218 // If F took a different number of args, reject.1219 if (F->arg_size() != Args.size()) {1220 ErrorF("redefinition of function with different # args");1221 return 0;1222 }1223 }1224 1225 // Set names for all arguments.1226 unsigned Idx = 0;1227 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();1228 ++AI, ++Idx)1229 AI->setName(Args[Idx]);1230 1231 return F;1232}1233 1234/// CreateArgumentAllocas - Create an alloca for each argument and register the1235/// argument in the symbol table so that references to it will succeed.1236void PrototypeAST::CreateArgumentAllocas(Function *F) {1237 Function::arg_iterator AI = F->arg_begin();1238 for (unsigned Idx = 0, e = Args.size(); Idx != e; ++Idx, ++AI) {1239 // Create an alloca for this variable.1240 AllocaInst *Alloca = CreateEntryBlockAlloca(F, Args[Idx]);1241 1242 // Store the initial value into the alloca.1243 Builder.CreateStore(AI, Alloca);1244 1245 // Add arguments to variable symbol table.1246 NamedValues[Args[Idx]] = Alloca;1247 }1248}1249 1250Function *FunctionAST::Codegen() {1251 NamedValues.clear();1252 1253 Function *TheFunction = Proto->Codegen();1254 if (TheFunction == 0)1255 return 0;1256 1257 // If this is an operator, install it.1258 if (Proto->isBinaryOp())1259 BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence();1260 1261 // Create a new basic block to start insertion into.1262 BasicBlock *BB = BasicBlock::Create(TheContext, "entry", TheFunction);1263 Builder.SetInsertPoint(BB);1264 1265 // Add all arguments to the symbol table and create their allocas.1266 Proto->CreateArgumentAllocas(TheFunction);1267 1268 if (Value *RetVal = Body->Codegen()) {1269 // Finish off the function.1270 Builder.CreateRet(RetVal);1271 1272 // Validate the generated code, checking for consistency.1273 verifyFunction(*TheFunction);1274 1275 return TheFunction;1276 }1277 1278 // Error reading body, remove function.1279 TheFunction->eraseFromParent();1280 1281 if (Proto->isBinaryOp())1282 BinopPrecedence.erase(Proto->getOperatorName());1283 return 0;1284}1285 1286//===----------------------------------------------------------------------===//1287// Top-Level parsing and JIT Driver1288//===----------------------------------------------------------------------===//1289 1290static void HandleDefinition() {1291 if (FunctionAST *F = ParseDefinition()) {1292 TheHelper->closeCurrentModule();1293 if (Function *LF = F->Codegen()) {1294#ifndef MINIMAL_STDERR_OUTPUT1295 fprintf(stderr, "Read function definition:");1296 LF->print(errs());1297 fprintf(stderr, "\n");1298#endif1299 }1300 } else {1301 // Skip token for error recovery.1302 getNextToken();1303 }1304}1305 1306static void HandleExtern() {1307 if (PrototypeAST *P = ParseExtern()) {1308 if (Function *F = P->Codegen()) {1309#ifndef MINIMAL_STDERR_OUTPUT1310 fprintf(stderr, "Read extern: ");1311 F->print(errs());1312 fprintf(stderr, "\n");1313#endif1314 }1315 } else {1316 // Skip token for error recovery.1317 getNextToken();1318 }1319}1320 1321static void HandleTopLevelExpression() {1322 // Evaluate a top-level expression into an anonymous function.1323 if (FunctionAST *F = ParseTopLevelExpr()) {1324 if (Function *LF = F->Codegen()) {1325 // JIT the function, returning a function pointer.1326 void *FPtr = TheHelper->getPointerToFunction(LF);1327 1328 // Cast it to the right type (takes no arguments, returns a double) so we1329 // can call it as a native function.1330 double (*FP)() = (double (*)())(intptr_t)FPtr;1331#ifdef MINIMAL_STDERR_OUTPUT1332 FP();1333#else1334 fprintf(stderr, "Evaluated to %f\n", FP());1335#endif1336 }1337 } else {1338 // Skip token for error recovery.1339 getNextToken();1340 }1341}1342 1343/// top ::= definition | external | expression | ';'1344static void MainLoop() {1345 while (1) {1346#ifndef MINIMAL_STDERR_OUTPUT1347 fprintf(stderr, "ready> ");1348#endif1349 switch (CurTok) {1350 case tok_eof: return;1351 case ';': getNextToken(); break; // ignore top-level semicolons.1352 case tok_def: HandleDefinition(); break;1353 case tok_extern: HandleExtern(); break;1354 default: HandleTopLevelExpression(); break;1355 }1356 }1357}1358 1359//===----------------------------------------------------------------------===//1360// "Library" functions that can be "extern'd" from user code.1361//===----------------------------------------------------------------------===//1362 1363/// putchard - putchar that takes a double and returns 0.1364extern "C"1365double putchard(double X) {1366 putchar((char)X);1367 return 0;1368}1369 1370/// printd - printf that takes a double prints it as "%f\n", returning 0.1371extern "C"1372double printd(double X) {1373 printf("%f", X);1374 return 0;1375}1376 1377extern "C"1378double printlf() {1379 printf("\n");1380 return 0;1381}1382 1383//===----------------------------------------------------------------------===//1384// Main driver code.1385//===----------------------------------------------------------------------===//1386 1387int main() {1388 InitializeNativeTarget();1389 InitializeNativeTargetAsmPrinter();1390 InitializeNativeTargetAsmParser();1391 LLVMContext &Context = TheContext;1392 1393 // Install standard binary operators.1394 // 1 is lowest precedence.1395 BinopPrecedence['='] = 2;1396 BinopPrecedence['<'] = 10;1397 BinopPrecedence['+'] = 20;1398 BinopPrecedence['-'] = 20;1399 BinopPrecedence['/'] = 40;1400 BinopPrecedence['*'] = 40; // highest.1401 1402 // Prime the first token.1403#ifndef MINIMAL_STDERR_OUTPUT1404 fprintf(stderr, "ready> ");1405#endif1406 getNextToken();1407 1408 // Make the helper, which holds all the code.1409 TheHelper = new MCJITHelper(Context);1410 1411 // Run the main "interpreter loop" now.1412 MainLoop();1413 1414#ifndef MINIMAL_STDERR_OUTPUT1415 // Print out all of the generated code.1416 TheHelper->dump();1417#endif1418 1419 return 0;1420}1421