1275 lines · cpp
1#include "llvm/ADT/APFloat.h"2#include "llvm/ADT/STLExtras.h"3#include "llvm/IR/BasicBlock.h"4#include "llvm/IR/Constants.h"5#include "llvm/IR/DerivedTypes.h"6#include "llvm/IR/Function.h"7#include "llvm/IR/IRBuilder.h"8#include "llvm/IR/Instructions.h"9#include "llvm/IR/LLVMContext.h"10#include "llvm/IR/LegacyPassManager.h"11#include "llvm/IR/Module.h"12#include "llvm/IR/Type.h"13#include "llvm/IR/Verifier.h"14#include "llvm/MC/TargetRegistry.h"15#include "llvm/Support/FileSystem.h"16#include "llvm/Support/TargetSelect.h"17#include "llvm/Support/raw_ostream.h"18#include "llvm/Target/TargetMachine.h"19#include "llvm/Target/TargetOptions.h"20#include "llvm/TargetParser/Host.h"21#include <algorithm>22#include <cassert>23#include <cctype>24#include <cstdio>25#include <cstdlib>26#include <map>27#include <memory>28#include <string>29#include <system_error>30#include <utility>31#include <vector>32 33using namespace llvm;34using namespace llvm::sys;35 36//===----------------------------------------------------------------------===//37// Lexer38//===----------------------------------------------------------------------===//39 40// The lexer returns tokens [0-255] if it is an unknown character, otherwise one41// of these for known things.42enum Token {43 tok_eof = -1,44 45 // commands46 tok_def = -2,47 tok_extern = -3,48 49 // primary50 tok_identifier = -4,51 tok_number = -5,52 53 // control54 tok_if = -6,55 tok_then = -7,56 tok_else = -8,57 tok_for = -9,58 tok_in = -10,59 60 // operators61 tok_binary = -11,62 tok_unary = -12,63 64 // var definition65 tok_var = -1366};67 68static std::string IdentifierStr; // Filled in if tok_identifier69static double NumVal; // Filled in if tok_number70 71/// gettok - Return the next token from standard input.72static int gettok() {73 static int LastChar = ' ';74 75 // Skip any whitespace.76 while (isspace(LastChar))77 LastChar = getchar();78 79 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*80 IdentifierStr = LastChar;81 while (isalnum((LastChar = getchar())))82 IdentifierStr += LastChar;83 84 if (IdentifierStr == "def")85 return tok_def;86 if (IdentifierStr == "extern")87 return tok_extern;88 if (IdentifierStr == "if")89 return tok_if;90 if (IdentifierStr == "then")91 return tok_then;92 if (IdentifierStr == "else")93 return tok_else;94 if (IdentifierStr == "for")95 return tok_for;96 if (IdentifierStr == "in")97 return tok_in;98 if (IdentifierStr == "binary")99 return tok_binary;100 if (IdentifierStr == "unary")101 return tok_unary;102 if (IdentifierStr == "var")103 return tok_var;104 return tok_identifier;105 }106 107 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+108 std::string NumStr;109 do {110 NumStr += LastChar;111 LastChar = getchar();112 } while (isdigit(LastChar) || LastChar == '.');113 114 NumVal = strtod(NumStr.c_str(), nullptr);115 return tok_number;116 }117 118 if (LastChar == '#') {119 // Comment until end of line.120 do121 LastChar = getchar();122 while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');123 124 if (LastChar != EOF)125 return gettok();126 }127 128 // Check for end of file. Don't eat the EOF.129 if (LastChar == EOF)130 return tok_eof;131 132 // Otherwise, just return the character as its ascii value.133 int ThisChar = LastChar;134 LastChar = getchar();135 return ThisChar;136}137 138//===----------------------------------------------------------------------===//139// Abstract Syntax Tree (aka Parse Tree)140//===----------------------------------------------------------------------===//141 142namespace {143 144/// ExprAST - Base class for all expression nodes.145class ExprAST {146public:147 virtual ~ExprAST() = default;148 149 virtual Value *codegen() = 0;150};151 152/// NumberExprAST - Expression class for numeric literals like "1.0".153class NumberExprAST : public ExprAST {154 double Val;155 156public:157 NumberExprAST(double Val) : Val(Val) {}158 159 Value *codegen() override;160};161 162/// VariableExprAST - Expression class for referencing a variable, like "a".163class VariableExprAST : public ExprAST {164 std::string Name;165 166public:167 VariableExprAST(const std::string &Name) : Name(Name) {}168 169 Value *codegen() override;170 const std::string &getName() const { return Name; }171};172 173/// UnaryExprAST - Expression class for a unary operator.174class UnaryExprAST : public ExprAST {175 char Opcode;176 std::unique_ptr<ExprAST> Operand;177 178public:179 UnaryExprAST(char Opcode, std::unique_ptr<ExprAST> Operand)180 : Opcode(Opcode), Operand(std::move(Operand)) {}181 182 Value *codegen() override;183};184 185/// BinaryExprAST - Expression class for a binary operator.186class BinaryExprAST : public ExprAST {187 char Op;188 std::unique_ptr<ExprAST> LHS, RHS;189 190public:191 BinaryExprAST(char Op, std::unique_ptr<ExprAST> LHS,192 std::unique_ptr<ExprAST> RHS)193 : Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}194 195 Value *codegen() override;196};197 198/// CallExprAST - Expression class for function calls.199class CallExprAST : public ExprAST {200 std::string Callee;201 std::vector<std::unique_ptr<ExprAST>> Args;202 203public:204 CallExprAST(const std::string &Callee,205 std::vector<std::unique_ptr<ExprAST>> Args)206 : Callee(Callee), Args(std::move(Args)) {}207 208 Value *codegen() override;209};210 211/// IfExprAST - Expression class for if/then/else.212class IfExprAST : public ExprAST {213 std::unique_ptr<ExprAST> Cond, Then, Else;214 215public:216 IfExprAST(std::unique_ptr<ExprAST> Cond, std::unique_ptr<ExprAST> Then,217 std::unique_ptr<ExprAST> Else)218 : Cond(std::move(Cond)), Then(std::move(Then)), Else(std::move(Else)) {}219 220 Value *codegen() override;221};222 223/// ForExprAST - Expression class for for/in.224class ForExprAST : public ExprAST {225 std::string VarName;226 std::unique_ptr<ExprAST> Start, End, Step, Body;227 228public:229 ForExprAST(const std::string &VarName, std::unique_ptr<ExprAST> Start,230 std::unique_ptr<ExprAST> End, std::unique_ptr<ExprAST> Step,231 std::unique_ptr<ExprAST> Body)232 : VarName(VarName), Start(std::move(Start)), End(std::move(End)),233 Step(std::move(Step)), Body(std::move(Body)) {}234 235 Value *codegen() override;236};237 238/// VarExprAST - Expression class for var/in239class VarExprAST : public ExprAST {240 std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames;241 std::unique_ptr<ExprAST> Body;242 243public:244 VarExprAST(245 std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames,246 std::unique_ptr<ExprAST> Body)247 : VarNames(std::move(VarNames)), Body(std::move(Body)) {}248 249 Value *codegen() override;250};251 252/// PrototypeAST - This class represents the "prototype" for a function,253/// which captures its name, and its argument names (thus implicitly the number254/// of arguments the function takes), as well as if it is an operator.255class PrototypeAST {256 std::string Name;257 std::vector<std::string> Args;258 bool IsOperator;259 unsigned Precedence; // Precedence if a binary op.260 261public:262 PrototypeAST(const std::string &Name, std::vector<std::string> Args,263 bool IsOperator = false, unsigned Prec = 0)264 : Name(Name), Args(std::move(Args)), IsOperator(IsOperator),265 Precedence(Prec) {}266 267 Function *codegen();268 const std::string &getName() const { return Name; }269 270 bool isUnaryOp() const { return IsOperator && Args.size() == 1; }271 bool isBinaryOp() const { return IsOperator && Args.size() == 2; }272 273 char getOperatorName() const {274 assert(isUnaryOp() || isBinaryOp());275 return Name[Name.size() - 1];276 }277 278 unsigned getBinaryPrecedence() const { return Precedence; }279};280 281/// FunctionAST - This class represents a function definition itself.282class FunctionAST {283 std::unique_ptr<PrototypeAST> Proto;284 std::unique_ptr<ExprAST> Body;285 286public:287 FunctionAST(std::unique_ptr<PrototypeAST> Proto,288 std::unique_ptr<ExprAST> Body)289 : Proto(std::move(Proto)), Body(std::move(Body)) {}290 291 Function *codegen();292};293 294} // end anonymous namespace295 296//===----------------------------------------------------------------------===//297// Parser298//===----------------------------------------------------------------------===//299 300/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current301/// token the parser is looking at. getNextToken reads another token from the302/// lexer and updates CurTok with its results.303static int CurTok;304static int getNextToken() { return CurTok = gettok(); }305 306/// BinopPrecedence - This holds the precedence for each binary operator that is307/// defined.308static std::map<char, int> BinopPrecedence;309 310/// GetTokPrecedence - Get the precedence of the pending binary operator token.311static int GetTokPrecedence() {312 if (!isascii(CurTok))313 return -1;314 315 // Make sure it's a declared binop.316 int TokPrec = BinopPrecedence[CurTok];317 if (TokPrec <= 0)318 return -1;319 return TokPrec;320}321 322/// LogError* - These are little helper functions for error handling.323std::unique_ptr<ExprAST> LogError(const char *Str) {324 fprintf(stderr, "Error: %s\n", Str);325 return nullptr;326}327 328std::unique_ptr<PrototypeAST> LogErrorP(const char *Str) {329 LogError(Str);330 return nullptr;331}332 333static std::unique_ptr<ExprAST> ParseExpression();334 335/// numberexpr ::= number336static std::unique_ptr<ExprAST> ParseNumberExpr() {337 auto Result = std::make_unique<NumberExprAST>(NumVal);338 getNextToken(); // consume the number339 return std::move(Result);340}341 342/// parenexpr ::= '(' expression ')'343static std::unique_ptr<ExprAST> ParseParenExpr() {344 getNextToken(); // eat (.345 auto V = ParseExpression();346 if (!V)347 return nullptr;348 349 if (CurTok != ')')350 return LogError("expected ')'");351 getNextToken(); // eat ).352 return V;353}354 355/// identifierexpr356/// ::= identifier357/// ::= identifier '(' expression* ')'358static std::unique_ptr<ExprAST> ParseIdentifierExpr() {359 std::string IdName = IdentifierStr;360 361 getNextToken(); // eat identifier.362 363 if (CurTok != '(') // Simple variable ref.364 return std::make_unique<VariableExprAST>(IdName);365 366 // Call.367 getNextToken(); // eat (368 std::vector<std::unique_ptr<ExprAST>> Args;369 if (CurTok != ')') {370 while (true) {371 if (auto Arg = ParseExpression())372 Args.push_back(std::move(Arg));373 else374 return nullptr;375 376 if (CurTok == ')')377 break;378 379 if (CurTok != ',')380 return LogError("Expected ')' or ',' in argument list");381 getNextToken();382 }383 }384 385 // Eat the ')'.386 getNextToken();387 388 return std::make_unique<CallExprAST>(IdName, std::move(Args));389}390 391/// ifexpr ::= 'if' expression 'then' expression 'else' expression392static std::unique_ptr<ExprAST> ParseIfExpr() {393 getNextToken(); // eat the if.394 395 // condition.396 auto Cond = ParseExpression();397 if (!Cond)398 return nullptr;399 400 if (CurTok != tok_then)401 return LogError("expected then");402 getNextToken(); // eat the then403 404 auto Then = ParseExpression();405 if (!Then)406 return nullptr;407 408 if (CurTok != tok_else)409 return LogError("expected else");410 411 getNextToken();412 413 auto Else = ParseExpression();414 if (!Else)415 return nullptr;416 417 return std::make_unique<IfExprAST>(std::move(Cond), std::move(Then),418 std::move(Else));419}420 421/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression422static std::unique_ptr<ExprAST> ParseForExpr() {423 getNextToken(); // eat the for.424 425 if (CurTok != tok_identifier)426 return LogError("expected identifier after for");427 428 std::string IdName = IdentifierStr;429 getNextToken(); // eat identifier.430 431 if (CurTok != '=')432 return LogError("expected '=' after for");433 getNextToken(); // eat '='.434 435 auto Start = ParseExpression();436 if (!Start)437 return nullptr;438 if (CurTok != ',')439 return LogError("expected ',' after for start value");440 getNextToken();441 442 auto End = ParseExpression();443 if (!End)444 return nullptr;445 446 // The step value is optional.447 std::unique_ptr<ExprAST> Step;448 if (CurTok == ',') {449 getNextToken();450 Step = ParseExpression();451 if (!Step)452 return nullptr;453 }454 455 if (CurTok != tok_in)456 return LogError("expected 'in' after for");457 getNextToken(); // eat 'in'.458 459 auto Body = ParseExpression();460 if (!Body)461 return nullptr;462 463 return std::make_unique<ForExprAST>(IdName, std::move(Start), std::move(End),464 std::move(Step), std::move(Body));465}466 467/// varexpr ::= 'var' identifier ('=' expression)?468// (',' identifier ('=' expression)?)* 'in' expression469static std::unique_ptr<ExprAST> ParseVarExpr() {470 getNextToken(); // eat the var.471 472 std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames;473 474 // At least one variable name is required.475 if (CurTok != tok_identifier)476 return LogError("expected identifier after var");477 478 while (true) {479 std::string Name = IdentifierStr;480 getNextToken(); // eat identifier.481 482 // Read the optional initializer.483 std::unique_ptr<ExprAST> Init = nullptr;484 if (CurTok == '=') {485 getNextToken(); // eat the '='.486 487 Init = ParseExpression();488 if (!Init)489 return nullptr;490 }491 492 VarNames.push_back(std::make_pair(Name, std::move(Init)));493 494 // End of var list, exit loop.495 if (CurTok != ',')496 break;497 getNextToken(); // eat the ','.498 499 if (CurTok != tok_identifier)500 return LogError("expected identifier list after var");501 }502 503 // At this point, we have to have 'in'.504 if (CurTok != tok_in)505 return LogError("expected 'in' keyword after 'var'");506 getNextToken(); // eat 'in'.507 508 auto Body = ParseExpression();509 if (!Body)510 return nullptr;511 512 return std::make_unique<VarExprAST>(std::move(VarNames), std::move(Body));513}514 515/// primary516/// ::= identifierexpr517/// ::= numberexpr518/// ::= parenexpr519/// ::= ifexpr520/// ::= forexpr521/// ::= varexpr522static std::unique_ptr<ExprAST> ParsePrimary() {523 switch (CurTok) {524 default:525 return LogError("unknown token when expecting an expression");526 case tok_identifier:527 return ParseIdentifierExpr();528 case tok_number:529 return ParseNumberExpr();530 case '(':531 return ParseParenExpr();532 case tok_if:533 return ParseIfExpr();534 case tok_for:535 return ParseForExpr();536 case tok_var:537 return ParseVarExpr();538 }539}540 541/// unary542/// ::= primary543/// ::= '!' unary544static std::unique_ptr<ExprAST> ParseUnary() {545 // If the current token is not an operator, it must be a primary expr.546 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')547 return ParsePrimary();548 549 // If this is a unary operator, read it.550 int Opc = CurTok;551 getNextToken();552 if (auto Operand = ParseUnary())553 return std::make_unique<UnaryExprAST>(Opc, std::move(Operand));554 return nullptr;555}556 557/// binoprhs558/// ::= ('+' unary)*559static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,560 std::unique_ptr<ExprAST> LHS) {561 // If this is a binop, find its precedence.562 while (true) {563 int TokPrec = GetTokPrecedence();564 565 // If this is a binop that binds at least as tightly as the current binop,566 // consume it, otherwise we are done.567 if (TokPrec < ExprPrec)568 return LHS;569 570 // Okay, we know this is a binop.571 int BinOp = CurTok;572 getNextToken(); // eat binop573 574 // Parse the unary expression after the binary operator.575 auto RHS = ParseUnary();576 if (!RHS)577 return nullptr;578 579 // If BinOp binds less tightly with RHS than the operator after RHS, let580 // the pending operator take RHS as its LHS.581 int NextPrec = GetTokPrecedence();582 if (TokPrec < NextPrec) {583 RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS));584 if (!RHS)585 return nullptr;586 }587 588 // Merge LHS/RHS.589 LHS =590 std::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS));591 }592}593 594/// expression595/// ::= unary binoprhs596///597static std::unique_ptr<ExprAST> ParseExpression() {598 auto LHS = ParseUnary();599 if (!LHS)600 return nullptr;601 602 return ParseBinOpRHS(0, std::move(LHS));603}604 605/// prototype606/// ::= id '(' id* ')'607/// ::= binary LETTER number? (id, id)608/// ::= unary LETTER (id)609static std::unique_ptr<PrototypeAST> ParsePrototype() {610 std::string FnName;611 612 unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.613 unsigned BinaryPrecedence = 30;614 615 switch (CurTok) {616 default:617 return LogErrorP("Expected function name in prototype");618 case tok_identifier:619 FnName = IdentifierStr;620 Kind = 0;621 getNextToken();622 break;623 case tok_unary:624 getNextToken();625 if (!isascii(CurTok))626 return LogErrorP("Expected unary operator");627 FnName = "unary";628 FnName += (char)CurTok;629 Kind = 1;630 getNextToken();631 break;632 case tok_binary:633 getNextToken();634 if (!isascii(CurTok))635 return LogErrorP("Expected binary operator");636 FnName = "binary";637 FnName += (char)CurTok;638 Kind = 2;639 getNextToken();640 641 // Read the precedence if present.642 if (CurTok == tok_number) {643 if (NumVal < 1 || NumVal > 100)644 return LogErrorP("Invalid precedence: must be 1..100");645 BinaryPrecedence = (unsigned)NumVal;646 getNextToken();647 }648 break;649 }650 651 if (CurTok != '(')652 return LogErrorP("Expected '(' in prototype");653 654 std::vector<std::string> ArgNames;655 while (getNextToken() == tok_identifier)656 ArgNames.push_back(IdentifierStr);657 if (CurTok != ')')658 return LogErrorP("Expected ')' in prototype");659 660 // success.661 getNextToken(); // eat ')'.662 663 // Verify right number of names for operator.664 if (Kind && ArgNames.size() != Kind)665 return LogErrorP("Invalid number of operands for operator");666 667 return std::make_unique<PrototypeAST>(FnName, ArgNames, Kind != 0,668 BinaryPrecedence);669}670 671/// definition ::= 'def' prototype expression672static std::unique_ptr<FunctionAST> ParseDefinition() {673 getNextToken(); // eat def.674 auto Proto = ParsePrototype();675 if (!Proto)676 return nullptr;677 678 if (auto E = ParseExpression())679 return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));680 return nullptr;681}682 683/// toplevelexpr ::= expression684static std::unique_ptr<FunctionAST> ParseTopLevelExpr() {685 if (auto E = ParseExpression()) {686 // Make an anonymous proto.687 auto Proto = std::make_unique<PrototypeAST>("__anon_expr",688 std::vector<std::string>());689 return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));690 }691 return nullptr;692}693 694/// external ::= 'extern' prototype695static std::unique_ptr<PrototypeAST> ParseExtern() {696 getNextToken(); // eat extern.697 return ParsePrototype();698}699 700//===----------------------------------------------------------------------===//701// Code Generation702//===----------------------------------------------------------------------===//703 704static std::unique_ptr<LLVMContext> TheContext;705static std::unique_ptr<Module> TheModule;706static std::unique_ptr<IRBuilder<>> Builder;707static std::map<std::string, AllocaInst *> NamedValues;708static std::map<std::string, std::unique_ptr<PrototypeAST>> FunctionProtos;709static ExitOnError ExitOnErr;710 711Value *LogErrorV(const char *Str) {712 LogError(Str);713 return nullptr;714}715 716Function *getFunction(std::string Name) {717 // First, see if the function has already been added to the current module.718 if (auto *F = TheModule->getFunction(Name))719 return F;720 721 // If not, check whether we can codegen the declaration from some existing722 // prototype.723 auto FI = FunctionProtos.find(Name);724 if (FI != FunctionProtos.end())725 return FI->second->codegen();726 727 // If no existing prototype exists, return null.728 return nullptr;729}730 731/// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of732/// the function. This is used for mutable variables etc.733static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,734 StringRef VarName) {735 IRBuilder<> TmpB(&TheFunction->getEntryBlock(),736 TheFunction->getEntryBlock().begin());737 return TmpB.CreateAlloca(Type::getDoubleTy(*TheContext), nullptr, VarName);738}739 740Value *NumberExprAST::codegen() {741 return ConstantFP::get(*TheContext, APFloat(Val));742}743 744Value *VariableExprAST::codegen() {745 // Look this variable up in the function.746 Value *V = NamedValues[Name];747 if (!V)748 return LogErrorV("Unknown variable name");749 750 // Load the value.751 return Builder->CreateLoad(Type::getDoubleTy(*TheContext), V, Name.c_str());752}753 754Value *UnaryExprAST::codegen() {755 Value *OperandV = Operand->codegen();756 if (!OperandV)757 return nullptr;758 759 Function *F = getFunction(std::string("unary") + Opcode);760 if (!F)761 return LogErrorV("Unknown unary operator");762 763 return Builder->CreateCall(F, OperandV, "unop");764}765 766Value *BinaryExprAST::codegen() {767 // Special case '=' because we don't want to emit the LHS as an expression.768 if (Op == '=') {769 // Assignment requires the LHS to be an identifier.770 // This assume we're building without RTTI because LLVM builds that way by771 // default. If you build LLVM with RTTI this can be changed to a772 // dynamic_cast for automatic error checking.773 VariableExprAST *LHSE = static_cast<VariableExprAST *>(LHS.get());774 if (!LHSE)775 return LogErrorV("destination of '=' must be a variable");776 // Codegen the RHS.777 Value *Val = RHS->codegen();778 if (!Val)779 return nullptr;780 781 // Look up the name.782 Value *Variable = NamedValues[LHSE->getName()];783 if (!Variable)784 return LogErrorV("Unknown variable name");785 786 Builder->CreateStore(Val, Variable);787 return Val;788 }789 790 Value *L = LHS->codegen();791 Value *R = RHS->codegen();792 if (!L || !R)793 return nullptr;794 795 switch (Op) {796 case '+':797 return Builder->CreateFAdd(L, R, "addtmp");798 case '-':799 return Builder->CreateFSub(L, R, "subtmp");800 case '*':801 return Builder->CreateFMul(L, R, "multmp");802 case '<':803 L = Builder->CreateFCmpULT(L, R, "cmptmp");804 // Convert bool 0/1 to double 0.0 or 1.0805 return Builder->CreateUIToFP(L, Type::getDoubleTy(*TheContext), "booltmp");806 default:807 break;808 }809 810 // If it wasn't a builtin binary operator, it must be a user defined one. Emit811 // a call to it.812 Function *F = getFunction(std::string("binary") + Op);813 assert(F && "binary operator not found!");814 815 Value *Ops[] = {L, R};816 return Builder->CreateCall(F, Ops, "binop");817}818 819Value *CallExprAST::codegen() {820 // Look up the name in the global module table.821 Function *CalleeF = getFunction(Callee);822 if (!CalleeF)823 return LogErrorV("Unknown function referenced");824 825 // If argument mismatch error.826 if (CalleeF->arg_size() != Args.size())827 return LogErrorV("Incorrect # arguments passed");828 829 std::vector<Value *> ArgsV;830 for (unsigned i = 0, e = Args.size(); i != e; ++i) {831 ArgsV.push_back(Args[i]->codegen());832 if (!ArgsV.back())833 return nullptr;834 }835 836 return Builder->CreateCall(CalleeF, ArgsV, "calltmp");837}838 839Value *IfExprAST::codegen() {840 Value *CondV = Cond->codegen();841 if (!CondV)842 return nullptr;843 844 // Convert condition to a bool by comparing non-equal to 0.0.845 CondV = Builder->CreateFCmpONE(846 CondV, ConstantFP::get(*TheContext, APFloat(0.0)), "ifcond");847 848 Function *TheFunction = Builder->GetInsertBlock()->getParent();849 850 // Create blocks for the then and else cases. Insert the 'then' block at the851 // end of the function.852 BasicBlock *ThenBB = BasicBlock::Create(*TheContext, "then", TheFunction);853 BasicBlock *ElseBB = BasicBlock::Create(*TheContext, "else");854 BasicBlock *MergeBB = BasicBlock::Create(*TheContext, "ifcont");855 856 Builder->CreateCondBr(CondV, ThenBB, ElseBB);857 858 // Emit then value.859 Builder->SetInsertPoint(ThenBB);860 861 Value *ThenV = Then->codegen();862 if (!ThenV)863 return nullptr;864 865 Builder->CreateBr(MergeBB);866 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.867 ThenBB = Builder->GetInsertBlock();868 869 // Emit else block.870 TheFunction->insert(TheFunction->end(), ElseBB);871 Builder->SetInsertPoint(ElseBB);872 873 Value *ElseV = Else->codegen();874 if (!ElseV)875 return nullptr;876 877 Builder->CreateBr(MergeBB);878 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.879 ElseBB = Builder->GetInsertBlock();880 881 // Emit merge block.882 TheFunction->insert(TheFunction->end(), MergeBB);883 Builder->SetInsertPoint(MergeBB);884 PHINode *PN = Builder->CreatePHI(Type::getDoubleTy(*TheContext), 2, "iftmp");885 886 PN->addIncoming(ThenV, ThenBB);887 PN->addIncoming(ElseV, ElseBB);888 return PN;889}890 891// Output for-loop as:892// var = alloca double893// ...894// start = startexpr895// store start -> var896// goto loop897// loop:898// ...899// bodyexpr900// ...901// loopend:902// step = stepexpr903// endcond = endexpr904//905// curvar = load var906// nextvar = curvar + step907// store nextvar -> var908// br endcond, loop, endloop909// outloop:910Value *ForExprAST::codegen() {911 Function *TheFunction = Builder->GetInsertBlock()->getParent();912 913 // Create an alloca for the variable in the entry block.914 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);915 916 // Emit the start code first, without 'variable' in scope.917 Value *StartVal = Start->codegen();918 if (!StartVal)919 return nullptr;920 921 // Store the value into the alloca.922 Builder->CreateStore(StartVal, Alloca);923 924 // Make the new basic block for the loop header, inserting after current925 // block.926 BasicBlock *LoopBB = BasicBlock::Create(*TheContext, "loop", TheFunction);927 928 // Insert an explicit fall through from the current block to the LoopBB.929 Builder->CreateBr(LoopBB);930 931 // Start insertion in LoopBB.932 Builder->SetInsertPoint(LoopBB);933 934 // Within the loop, the variable is defined equal to the PHI node. If it935 // shadows an existing variable, we have to restore it, so save it now.936 AllocaInst *OldVal = NamedValues[VarName];937 NamedValues[VarName] = Alloca;938 939 // Emit the body of the loop. This, like any other expr, can change the940 // current BB. Note that we ignore the value computed by the body, but don't941 // allow an error.942 if (!Body->codegen())943 return nullptr;944 945 // Emit the step value.946 Value *StepVal = nullptr;947 if (Step) {948 StepVal = Step->codegen();949 if (!StepVal)950 return nullptr;951 } else {952 // If not specified, use 1.0.953 StepVal = ConstantFP::get(*TheContext, APFloat(1.0));954 }955 956 // Compute the end condition.957 Value *EndCond = End->codegen();958 if (!EndCond)959 return nullptr;960 961 // Reload, increment, and restore the alloca. This handles the case where962 // the body of the loop mutates the variable.963 Value *CurVar = Builder->CreateLoad(Type::getDoubleTy(*TheContext), Alloca,964 VarName.c_str());965 Value *NextVar = Builder->CreateFAdd(CurVar, StepVal, "nextvar");966 Builder->CreateStore(NextVar, Alloca);967 968 // Convert condition to a bool by comparing non-equal to 0.0.969 EndCond = Builder->CreateFCmpONE(970 EndCond, ConstantFP::get(*TheContext, APFloat(0.0)), "loopcond");971 972 // Create the "after loop" block and insert it.973 BasicBlock *AfterBB =974 BasicBlock::Create(*TheContext, "afterloop", TheFunction);975 976 // Insert the conditional branch into the end of LoopEndBB.977 Builder->CreateCondBr(EndCond, LoopBB, AfterBB);978 979 // Any new code will be inserted in AfterBB.980 Builder->SetInsertPoint(AfterBB);981 982 // Restore the unshadowed variable.983 if (OldVal)984 NamedValues[VarName] = OldVal;985 else986 NamedValues.erase(VarName);987 988 // for expr always returns 0.0.989 return Constant::getNullValue(Type::getDoubleTy(*TheContext));990}991 992Value *VarExprAST::codegen() {993 std::vector<AllocaInst *> OldBindings;994 995 Function *TheFunction = Builder->GetInsertBlock()->getParent();996 997 // Register all variables and emit their initializer.998 for (unsigned i = 0, e = VarNames.size(); i != e; ++i) {999 const std::string &VarName = VarNames[i].first;1000 ExprAST *Init = VarNames[i].second.get();1001 1002 // Emit the initializer before adding the variable to scope, this prevents1003 // the initializer from referencing the variable itself, and permits stuff1004 // like this:1005 // var a = 1 in1006 // var a = a in ... # refers to outer 'a'.1007 Value *InitVal;1008 if (Init) {1009 InitVal = Init->codegen();1010 if (!InitVal)1011 return nullptr;1012 } else { // If not specified, use 0.0.1013 InitVal = ConstantFP::get(*TheContext, APFloat(0.0));1014 }1015 1016 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);1017 Builder->CreateStore(InitVal, Alloca);1018 1019 // Remember the old variable binding so that we can restore the binding when1020 // we unrecurse.1021 OldBindings.push_back(NamedValues[VarName]);1022 1023 // Remember this binding.1024 NamedValues[VarName] = Alloca;1025 }1026 1027 // Codegen the body, now that all vars are in scope.1028 Value *BodyVal = Body->codegen();1029 if (!BodyVal)1030 return nullptr;1031 1032 // Pop all our variables from scope.1033 for (unsigned i = 0, e = VarNames.size(); i != e; ++i)1034 NamedValues[VarNames[i].first] = OldBindings[i];1035 1036 // Return the body computation.1037 return BodyVal;1038}1039 1040Function *PrototypeAST::codegen() {1041 // Make the function type: double(double,double) etc.1042 std::vector<Type *> Doubles(Args.size(), Type::getDoubleTy(*TheContext));1043 FunctionType *FT =1044 FunctionType::get(Type::getDoubleTy(*TheContext), Doubles, false);1045 1046 Function *F =1047 Function::Create(FT, Function::ExternalLinkage, Name, TheModule.get());1048 1049 // Set names for all arguments.1050 unsigned Idx = 0;1051 for (auto &Arg : F->args())1052 Arg.setName(Args[Idx++]);1053 1054 return F;1055}1056 1057Function *FunctionAST::codegen() {1058 // Transfer ownership of the prototype to the FunctionProtos map, but keep a1059 // reference to it for use below.1060 auto &P = *Proto;1061 FunctionProtos[Proto->getName()] = std::move(Proto);1062 Function *TheFunction = getFunction(P.getName());1063 if (!TheFunction)1064 return nullptr;1065 1066 // If this is an operator, install it.1067 if (P.isBinaryOp())1068 BinopPrecedence[P.getOperatorName()] = P.getBinaryPrecedence();1069 1070 // Create a new basic block to start insertion into.1071 BasicBlock *BB = BasicBlock::Create(*TheContext, "entry", TheFunction);1072 Builder->SetInsertPoint(BB);1073 1074 // Record the function arguments in the NamedValues map.1075 NamedValues.clear();1076 for (auto &Arg : TheFunction->args()) {1077 // Create an alloca for this variable.1078 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, Arg.getName());1079 1080 // Store the initial value into the alloca.1081 Builder->CreateStore(&Arg, Alloca);1082 1083 // Add arguments to variable symbol table.1084 NamedValues[std::string(Arg.getName())] = Alloca;1085 }1086 1087 if (Value *RetVal = Body->codegen()) {1088 // Finish off the function.1089 Builder->CreateRet(RetVal);1090 1091 // Validate the generated code, checking for consistency.1092 verifyFunction(*TheFunction);1093 1094 return TheFunction;1095 }1096 1097 // Error reading body, remove function.1098 TheFunction->eraseFromParent();1099 1100 if (P.isBinaryOp())1101 BinopPrecedence.erase(P.getOperatorName());1102 return nullptr;1103}1104 1105//===----------------------------------------------------------------------===//1106// Top-Level parsing and JIT Driver1107//===----------------------------------------------------------------------===//1108 1109static void InitializeModuleAndPassManager() {1110 // Open a new module.1111 TheContext = std::make_unique<LLVMContext>();1112 TheModule = std::make_unique<Module>("my cool jit", *TheContext);1113 1114 // Create a new builder for the module.1115 Builder = std::make_unique<IRBuilder<>>(*TheContext);1116}1117 1118static void HandleDefinition() {1119 if (auto FnAST = ParseDefinition()) {1120 if (auto *FnIR = FnAST->codegen()) {1121 fprintf(stderr, "Read function definition:");1122 FnIR->print(errs());1123 fprintf(stderr, "\n");1124 }1125 } else {1126 // Skip token for error recovery.1127 getNextToken();1128 }1129}1130 1131static void HandleExtern() {1132 if (auto ProtoAST = ParseExtern()) {1133 if (auto *FnIR = ProtoAST->codegen()) {1134 fprintf(stderr, "Read extern: ");1135 FnIR->print(errs());1136 fprintf(stderr, "\n");1137 FunctionProtos[ProtoAST->getName()] = std::move(ProtoAST);1138 }1139 } else {1140 // Skip token for error recovery.1141 getNextToken();1142 }1143}1144 1145static void HandleTopLevelExpression() {1146 // Evaluate a top-level expression into an anonymous function.1147 if (auto FnAST = ParseTopLevelExpr()) {1148 FnAST->codegen();1149 } else {1150 // Skip token for error recovery.1151 getNextToken();1152 }1153}1154 1155/// top ::= definition | external | expression | ';'1156static void MainLoop() {1157 while (true) {1158 switch (CurTok) {1159 case tok_eof:1160 return;1161 case ';': // ignore top-level semicolons.1162 getNextToken();1163 break;1164 case tok_def:1165 HandleDefinition();1166 break;1167 case tok_extern:1168 HandleExtern();1169 break;1170 default:1171 HandleTopLevelExpression();1172 break;1173 }1174 }1175}1176 1177//===----------------------------------------------------------------------===//1178// "Library" functions that can be "extern'd" from user code.1179//===----------------------------------------------------------------------===//1180 1181#ifdef _WIN321182#define DLLEXPORT __declspec(dllexport)1183#else1184#define DLLEXPORT1185#endif1186 1187/// putchard - putchar that takes a double and returns 0.1188extern "C" DLLEXPORT double putchard(double X) {1189 fputc((char)X, stderr);1190 return 0;1191}1192 1193/// printd - printf that takes a double prints it as "%f\n", returning 0.1194extern "C" DLLEXPORT double printd(double X) {1195 fprintf(stderr, "%f\n", X);1196 return 0;1197}1198 1199//===----------------------------------------------------------------------===//1200// Main driver code.1201//===----------------------------------------------------------------------===//1202 1203int main() {1204 // Install standard binary operators.1205 // 1 is lowest precedence.1206 BinopPrecedence['<'] = 10;1207 BinopPrecedence['+'] = 20;1208 BinopPrecedence['-'] = 20;1209 BinopPrecedence['*'] = 40; // highest.1210 1211 // Prime the first token.1212 fprintf(stderr, "ready> ");1213 getNextToken();1214 1215 InitializeModuleAndPassManager();1216 1217 // Run the main "interpreter loop" now.1218 MainLoop();1219 1220 // Initialize the target registry etc.1221 InitializeAllTargetInfos();1222 InitializeAllTargets();1223 InitializeAllTargetMCs();1224 InitializeAllAsmParsers();1225 InitializeAllAsmPrinters();1226 1227 auto TargetTriple = sys::getDefaultTargetTriple();1228 TheModule->setTargetTriple(Triple(TargetTriple));1229 1230 std::string Error;1231 auto Target =1232 TargetRegistry::lookupTarget(TheModule->getTargetTriple(), Error);1233 1234 // Print an error and exit if we couldn't find the requested target.1235 // This generally occurs if we've forgotten to initialise the1236 // TargetRegistry or we have a bogus target triple.1237 if (!Target) {1238 errs() << Error;1239 return 1;1240 }1241 1242 auto CPU = "generic";1243 auto Features = "";1244 1245 TargetOptions opt;1246 auto TheTargetMachine = Target->createTargetMachine(1247 Triple(TargetTriple), CPU, Features, opt, Reloc::PIC_);1248 1249 TheModule->setDataLayout(TheTargetMachine->createDataLayout());1250 1251 auto Filename = "output.o";1252 std::error_code EC;1253 raw_fd_ostream dest(Filename, EC, sys::fs::OF_None);1254 1255 if (EC) {1256 errs() << "Could not open file: " << EC.message();1257 return 1;1258 }1259 1260 legacy::PassManager pass;1261 auto FileType = CodeGenFileType::ObjectFile;1262 1263 if (TheTargetMachine->addPassesToEmitFile(pass, dest, nullptr, FileType)) {1264 errs() << "TheTargetMachine can't emit a file of this type";1265 return 1;1266 }1267 1268 pass.run(*TheModule);1269 dest.flush();1270 1271 outs() << "Wrote " << Filename << "\n";1272 1273 return 0;1274}1275