From ca0890e5fc8e5abbb1edd253e66c6c273e7756c0 Mon Sep 17 00:00:00 2001 From: Luke Lau Date: Mon, 22 Oct 2018 00:03:54 +0100 Subject: [PATCH] WIP --- Kaleidoscope.xcodeproj/project.pbxproj | 116 +++++++++++++++---- Kaleidoscope/.gitignore | 3 + Kaleidoscope/ast.cpp | 6 +- Kaleidoscope/ast.hpp | 55 ++++++++- Kaleidoscope/codegen.cpp | 135 ++++++++++++++++++++-- Kaleidoscope/codegen.hpp | 2 - Kaleidoscope/lexer.cpp | 154 ++++++++++++++++++++++--- Kaleidoscope/makefile | 2 +- Kaleidoscope/shared.h | 1 + 9 files changed, 415 insertions(+), 59 deletions(-) create mode 100644 Kaleidoscope/.gitignore diff --git a/Kaleidoscope.xcodeproj/project.pbxproj b/Kaleidoscope.xcodeproj/project.pbxproj index 01ca27d..81ffeb0 100644 --- a/Kaleidoscope.xcodeproj/project.pbxproj +++ b/Kaleidoscope.xcodeproj/project.pbxproj @@ -265,21 +265,57 @@ buildSettings = { CLANG_ENABLE_OBJC_WEAK = YES; DEVELOPMENT_TEAM = 7R888D749H; - HEADER_SEARCH_PATHS = /usr/local/opt/llvm/include; - LIBRARY_SEARCH_PATHS = ( - /usr/local/opt/llvm/lib, - /usr/local/Cellar/llvm/5.0.1/lib, - ); + HEADER_SEARCH_PATHS = /usr/local/Cellar/llvm/5.0.1/include; + LIBRARY_SEARCH_PATHS = /usr/local/Cellar/llvm/5.0.1/lib; + MACOSX_DEPLOYMENT_TARGET = 10.13; + OTHER_CPLUSPLUSFLAGS = "$(OTHER_CFLAGS)"; OTHER_LDFLAGS = ( - "-lz", - "-ltermcap", - "-lc++", - "-lLLVMCore", - "-lLLVMSupport", + "-Wl,-search_paths_first", + "-Wl,-headerpad_max_install_names", + "-lLLVMInterpreter", + "-lLLVMPasses", + "-lLLVMipo", + "-lLLVMInstrumentation", + "-lLLVMVectorize", + "-lLLVMLinker", + "-lLLVMIRReader", + "-lLLVMAsmParser", + "-lLLVMX86Disassembler", + "-lLLVMX86AsmParser", + "-lLLVMX86CodeGen", + "-lLLVMGlobalISel", + "-lLLVMSelectionDAG", + "-lLLVMAsmPrinter", + "-lLLVMDebugInfoCodeView", + "-lLLVMDebugInfoMSF", + "-lLLVMCodeGen", + "-lLLVMScalarOpts", + "-lLLVMInstCombine", "-lLLVMTransformUtils", - "-lLLVMBitReader", + "-lLLVMBitWriter", + "-lLLVMX86Desc", + "-lLLVMMCDisassembler", + "-lLLVMX86Info", + "-lLLVMX86AsmPrinter", + "-lLLVMX86Utils", + "-lLLVMMCJIT", + "-lLLVMExecutionEngine", + "-lLLVMTarget", "-lLLVMAnalysis", + "-lLLVMProfileData", + "-lLLVMRuntimeDyld", + "-lLLVMObject", + "-lLLVMMCParser", + "-lLLVMBitReader", + "-lLLVMMC", + "-lLLVMCore", + "-lLLVMBinaryFormat", + "-lLLVMSupport", "-lLLVMDemangle", + "-lz", + "-lm", + "-lcurses", + "-lc++", ); PRODUCT_NAME = "$(TARGET_NAME)"; }; @@ -290,21 +326,57 @@ buildSettings = { CLANG_ENABLE_OBJC_WEAK = YES; DEVELOPMENT_TEAM = 7R888D749H; - HEADER_SEARCH_PATHS = /usr/local/opt/llvm/include; - LIBRARY_SEARCH_PATHS = ( - /usr/local/opt/llvm/lib, - /usr/local/Cellar/llvm/5.0.1/lib, - ); + HEADER_SEARCH_PATHS = /usr/local/Cellar/llvm/5.0.1/include; + LIBRARY_SEARCH_PATHS = /usr/local/Cellar/llvm/5.0.1/lib; + MACOSX_DEPLOYMENT_TARGET = 10.13; + OTHER_CPLUSPLUSFLAGS = "$(OTHER_CFLAGS)"; OTHER_LDFLAGS = ( - "-lz", - "-ltermcap", - "-lc++", - "-lLLVMCore", - "-lLLVMSupport", + "-Wl,-search_paths_first", + "-Wl,-headerpad_max_install_names", + "-lLLVMInterpreter", + "-lLLVMPasses", + "-lLLVMipo", + "-lLLVMInstrumentation", + "-lLLVMVectorize", + "-lLLVMLinker", + "-lLLVMIRReader", + "-lLLVMAsmParser", + "-lLLVMX86Disassembler", + "-lLLVMX86AsmParser", + "-lLLVMX86CodeGen", + "-lLLVMGlobalISel", + "-lLLVMSelectionDAG", + "-lLLVMAsmPrinter", + "-lLLVMDebugInfoCodeView", + "-lLLVMDebugInfoMSF", + "-lLLVMCodeGen", + "-lLLVMScalarOpts", + "-lLLVMInstCombine", "-lLLVMTransformUtils", - "-lLLVMBitReader", + "-lLLVMBitWriter", + "-lLLVMX86Desc", + "-lLLVMMCDisassembler", + "-lLLVMX86Info", + "-lLLVMX86AsmPrinter", + "-lLLVMX86Utils", + "-lLLVMMCJIT", + "-lLLVMExecutionEngine", + "-lLLVMTarget", "-lLLVMAnalysis", + "-lLLVMProfileData", + "-lLLVMRuntimeDyld", + "-lLLVMObject", + "-lLLVMMCParser", + "-lLLVMBitReader", + "-lLLVMMC", + "-lLLVMCore", + "-lLLVMBinaryFormat", + "-lLLVMSupport", "-lLLVMDemangle", + "-lz", + "-lm", + "-lcurses", + "-lc++", ); PRODUCT_NAME = "$(TARGET_NAME)"; }; diff --git a/Kaleidoscope/.gitignore b/Kaleidoscope/.gitignore new file mode 100644 index 0000000..fb1a5e8 --- /dev/null +++ b/Kaleidoscope/.gitignore @@ -0,0 +1,3 @@ +bin +tags +*.swp diff --git a/Kaleidoscope/ast.cpp b/Kaleidoscope/ast.cpp index 19f5101..2c367e8 100644 --- a/Kaleidoscope/ast.cpp +++ b/Kaleidoscope/ast.cpp @@ -1,6 +1,8 @@ #include "ast.hpp" +#include +#include -std::unique_ptr LogError(const char *Str) { - fprintf(stderr, "LogError: %s\n", Str); +std::unique_ptr LogError(std::string str) { + std::cerr << "LogError: " << str << std::endl; return nullptr; } diff --git a/Kaleidoscope/ast.hpp b/Kaleidoscope/ast.hpp index 34a5225..7730f8e 100644 --- a/Kaleidoscope/ast.hpp +++ b/Kaleidoscope/ast.hpp @@ -11,6 +11,8 @@ public: virtual Value *codegen() = 0; }; +std::unique_ptr LogError(std::string str); + class NumberExprAST: public ExprAST { double Val; @@ -48,21 +50,35 @@ public: virtual Value *codegen(); }; -/* +/** Captures the prototype for a function which is basically its name and arguments */ class PrototypeAST { std::string Name; std::vector Args; + bool IsOperator; + unsigned Precedence; public: virtual ~PrototypeAST() = default; - PrototypeAST(std::string Name, std::vector Args) - : Name(Name), Args(std::move(Args)) {} + PrototypeAST(std::string Name, std::vector Args, + bool IsOperator = false, unsigned Prec = 0) + : Name(Name), Args(std::move(Args)), IsOperator(IsOperator), + Precedence(Prec) {} const std::string &getName() const { return Name; } virtual Function *codegen(); + + bool isUnaryOp() const { return IsOperator && Args.size() == 1; } + bool isBinaryOp() const { return IsOperator && Args.size() == 2; } + + char getOperatorName() const { + assert(isUnaryOp() || isBinaryOp()); + return Name[Name.size() - 1]; + } + + unsigned getBinaryPrecedence() const { return Precedence; } }; class FunctionAST { @@ -76,4 +92,35 @@ public: virtual Function *codegen(); }; -std::unique_ptr LogError(const char *Str); +/// An expression for an if/then/else combo +class IfExprAST: public ExprAST { + std::unique_ptr Cond, Then, Else; + +public: + IfExprAST(std::unique_ptr Cond, + std::unique_ptr Then, + std::unique_ptr Else) + : Cond(std::move(Cond)), Then(std::move(Then)), Else(std::move(Else)) {} + + Value *codegen() override; +}; + +/// An expression for a for loop +class ForExprAST: public ExprAST { + std::string VarName; + std::unique_ptr Start, End, Step, Body; + +public: + ForExprAST(const std::string &VarName, + std::unique_ptr Start, + std::unique_ptr End, + std::unique_ptr Step, + std::unique_ptr Body) + : VarName(VarName), + Start(std::move(Start)), + End(std::move(End)), + Step(std::move(Step)), + Body(std::move(Body)) {} + + Value *codegen() override; +}; diff --git a/Kaleidoscope/codegen.cpp b/Kaleidoscope/codegen.cpp index c185a3e..e9e1d24 100644 --- a/Kaleidoscope/codegen.cpp +++ b/Kaleidoscope/codegen.cpp @@ -11,7 +11,6 @@ #include #include #include -#include #include #include #include "ast.hpp" @@ -43,10 +42,6 @@ void InitializeModuleAndPassManager(void) { TheFPM->addPass(GVNSinkPass()); } -void PrintModule() { - TheModule->print(errs(), nullptr); -} - std::map> functionProtos; Function *getFunction(std::string name) { @@ -60,8 +55,8 @@ Function *getFunction(std::string name) { return nullptr; } -Value *LogErrorV(const char *Str) { - LogError(Str); +Value *LogErrorV(std::string str) { + LogError(str); return nullptr; } @@ -93,9 +88,23 @@ Value *BinaryExprAST::codegen() { L = Builder.CreateFCmpULT(L, R, "cmptmp"); // convert bool 0/1 to double 0.0/1.0 return Builder.CreateUIToFP(L, Type::getDoubleTy(TheContext), "booltmp"); + case '>': + L = Builder.CreateFCmpUGT(L, R, "cmptmp"); + return Builder.CreateUIToFP(L, Type::getDoubleTy(TheContext), "booltmp"); + case '|': + L = Builder.CreateFCmpUGE(L, ConstantFP::get(TheContext, APFloat(1.0)), "leftbooltmp"); + R = Builder.CreateFCmpUGE(R, ConstantFP::get(TheContext, APFloat(1.0)), "leftbooltmp"); + L = Builder.CreateOr(L, R, "orbooltmp"); + return Builder.CreateUIToFP(L, Type::getDoubleTy(TheContext), "ortmp"); default: - return LogErrorV("Invalid binary operator"); + break; } + + Function *F = getFunction(std::string("binary") + Op); + assert(F && "binary oprator not found!"); + + Value *Ops[2] = {L, R}; + return Builder.CreateCall(F, Ops, "binop"); } Value *CallExprAST::codegen() { @@ -137,6 +146,9 @@ Function *FunctionAST::codegen() { if (!func) return nullptr; + if (P.isBinaryOp()) + BinopPrecedence[P.getOperatorName()] = P.getBinaryPrecedence(); + BasicBlock *bb = BasicBlock::Create(TheContext, "entry", func); Builder.SetInsertPoint(bb); @@ -146,7 +158,13 @@ Function *FunctionAST::codegen() { if (Value *retVal = Body->codegen()) { Builder.CreateRet(retVal); - verifyFunction(*func); + + if (verifyFunction(*func, &errs())) { + func->print(errs()); + func->eraseFromParent(); + return nullptr; + } + TheFPM->run(*func, *TheFAM); return func; } @@ -154,3 +172,102 @@ Function *FunctionAST::codegen() { func->eraseFromParent(); return nullptr; } + +Value *IfExprAST::codegen() { + Value *condV = Cond->codegen(); + if (!condV) return nullptr; + + //convert to bool + condV = Builder.CreateFCmpONE(condV, ConstantFP::get(TheContext, APFloat(0.0)), "ifcond"); + + Function *func = Builder.GetInsertBlock()->getParent(); + + BasicBlock *thenBB = BasicBlock::Create(TheContext, "then", func); + BasicBlock *elseBB = BasicBlock::Create(TheContext, "else", func); + BasicBlock *mergeBB = BasicBlock::Create(TheContext, "merge", func); + + Builder.CreateCondBr(condV, thenBB, elseBB); + + Builder.SetInsertPoint(thenBB); + + Value *thenV = Then->codegen(); + if (!thenV) return nullptr; + + Builder.CreateBr(mergeBB); + + //codegen of then can change the current block, so get then again + thenBB = Builder.GetInsertBlock(); + + Builder.SetInsertPoint(elseBB); + + Value *elseV = Else->codegen(); + if (!elseV) return nullptr; + + Builder.CreateBr(mergeBB); + + //codegen of else can change the current block, so get else again + elseBB = Builder.GetInsertBlock(); + + Builder.SetInsertPoint(mergeBB); + PHINode *phiNode = Builder.CreatePHI(Type::getDoubleTy(TheContext), 2, "iftmp"); + phiNode->addIncoming(thenV, thenBB); + phiNode->addIncoming(elseV, elseBB); + + return phiNode; +} + +Value *ForExprAST::codegen() { + auto *startValue = Start->codegen(); + if (!startValue) return nullptr; + + auto *func = Builder.GetInsertBlock()->getParent(); + auto *preheaderBB = Builder.GetInsertBlock(); + auto *loopBB = BasicBlock::Create(TheContext, "loop", func); + + Builder.CreateBr(loopBB); + + Builder.SetInsertPoint(loopBB); + + auto *index = Builder.CreatePHI(Type::getDoubleTy(TheContext), 2, VarName.c_str()); + index->addIncoming(startValue, preheaderBB); + + // if the index variable shadows an existing value, save it to restore later + auto *oldVal = NamedValues[VarName]; + NamedValues[VarName] = index; + + // emit the loop body + if (!Body->codegen()) return nullptr; + + Value *stepVal = nullptr; + if (Step) { + stepVal = Step->codegen(); + if (!stepVal) return nullptr; + } else { + stepVal = ConstantFP::get(TheContext, APFloat(1.0)); + } + + // increment the index + auto *nextVar = Builder.CreateFAdd(index, stepVal, "nextvar"); + + auto *endCond = End->codegen(); + if (!endCond) return nullptr; + + endCond = Builder.CreateFCmpONE(endCond, ConstantFP::get(TheContext, APFloat(0.0)), "loopcond"); + + auto *loopEndBB = Builder.GetInsertBlock(); + auto *afterBB = BasicBlock::Create(TheContext, "afterloop", func); + + Builder.CreateCondBr(endCond, loopBB, afterBB); + + Builder.SetInsertPoint(afterBB); + + index->addIncoming(nextVar, loopEndBB); + + // restore shadowed index variable + if (oldVal) + NamedValues[VarName] = oldVal; + else + NamedValues.erase(VarName); + + return Constant::getNullValue(Type::getDoubleTy(TheContext)); +} diff --git a/Kaleidoscope/codegen.hpp b/Kaleidoscope/codegen.hpp index 300282a..15f10cc 100644 --- a/Kaleidoscope/codegen.hpp +++ b/Kaleidoscope/codegen.hpp @@ -2,6 +2,4 @@ void InitializeModuleAndPassManager(void); -void PrintModule(); - extern std::map> functionProtos; diff --git a/Kaleidoscope/lexer.cpp b/Kaleidoscope/lexer.cpp index ac75490..049dc51 100644 --- a/Kaleidoscope/lexer.cpp +++ b/Kaleidoscope/lexer.cpp @@ -35,6 +35,17 @@ enum Token { tok_identifier = -4, tok_number = -5, + + //control flow + tok_if = -6, + tok_then = -7, + tok_else = -8, + tok_for = -9, + tok_in = -10, + + //operators + tok_binary = -11, + tok_unary = -12 }; static std::string IdentifierStr; @@ -52,10 +63,14 @@ static int gettok() { while (isalnum((LastChar = getchar()))) IdentifierStr += LastChar; - if(IdentifierStr == "def") - return tok_def; - if(IdentifierStr == "extern") - return tok_extern; + if (IdentifierStr == "def") return tok_def; + if (IdentifierStr == "extern") return tok_extern; + if (IdentifierStr == "if") return tok_if; + if (IdentifierStr == "then") return tok_then; + if (IdentifierStr == "else") return tok_else; + if (IdentifierStr == "binary") return tok_binary; + if (IdentifierStr == "unary") return tok_unary; + return tok_identifier; } @@ -74,7 +89,7 @@ static int gettok() { //Coment until the end of the line do LastChar = getchar(); - while(LastChar != EOF && LastChar != '\n' && LastChar != 'r'); + while(LastChar != EOF && LastChar != '\n' && LastChar != '\r'); if(LastChar != EOF) return gettok(); @@ -95,8 +110,8 @@ static int getNextToken() { return CurTok = gettok(); } -std::unique_ptr LogErrorP(const char *Str) { - LogError(Str); +std::unique_ptr LogErrorP(std::string str) { + LogError(str); return nullptr; } @@ -149,21 +164,95 @@ static std::unique_ptr ParseIdentifierExpr() { return llvm::make_unique(IdName, std::move(Args)); } +static std::unique_ptr ParseIfExpr() { + getNextToken(); // eat the if + + auto condExpr = ParseExpression(); + if (!condExpr) return nullptr; + + if (CurTok != tok_then) + return LogError("Expected then"); + getNextToken(); // eat the then + + auto thenExpr = ParseExpression(); + if (!thenExpr) return nullptr; + + if (CurTok != tok_else) + return LogError("Expected else"); + getNextToken(); // eat the else + + auto elseExpr = ParseExpression(); + if (!elseExpr) return nullptr; + + return llvm::make_unique(std::move(condExpr), + std::move(thenExpr), + std::move(elseExpr)); +} + +static std::unique_ptr ParseForExpr() { + getNextToken(); // eat the for + + if (CurTok != tok_identifier) + return LogError("Expected identifier after for"); + + std::string id = IdentifierStr; + getNextToken(); // eat the identifier + + if (CurTok != '=') + return LogError("Expected = after for"); + getNextToken(); // eat the = + + auto start = ParseExpression(); + if (!start) return nullptr; + + if (CurTok != ',') + return LogError("Expected , after for start value"); + getNextToken(); // eat the , + + auto end = ParseExpression(); + if (!end) + return nullptr; + + // optional step value + std::unique_ptr step; + if (CurTok == ',') { + getNextToken(); // eat the , + step = ParseExpression(); + if (!step) return nullptr; + } + + if (CurTok != tok_in) + return LogError("Expected in after for"); + getNextToken(); // eat the in + + auto body = ParseExpression(); + if (!body) return nullptr; + + return llvm::make_unique(id, + std::move(start), + std::move(end), + std::move(step), + std::move(body)); +} + static std::unique_ptr ParsePrimary() { switch (CurTok) { default: - return LogError("Unknown token when expected an expression"); + return LogError(std::string("Unknown token when expected an expression: ") + + std::to_string(CurTok)); case tok_identifier: return ParseIdentifierExpr(); case tok_number: return ParseNumberExpr(); case '(': return ParseParenExpr(); + case tok_if: + return ParseIfExpr(); + case tok_for: + return ParseForExpr(); } } -static std::map BinopPrecedence; - static int GetTokPrecedence() { if (!isascii(CurTok)) return -1; @@ -206,11 +295,34 @@ static std::unique_ptr ParseBinOpRHS(int ExprPrec, } static std::unique_ptr ParsePrototype() { - if (CurTok != tok_identifier) - return LogErrorP("Expected function name in prototype"); + std::string FnName; + + unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary + unsigned BinaryPrecedence = 30; - std::string FnName = IdentifierStr; + switch (CurTok) { + default: + return LogErrorP("Expected function name in prototype"); + case tok_identifier: + FnName = IdentifierStr; + Kind = 0; getNextToken(); + break; + case tok_binary: + getNextToken(); + if (!isascii(CurTok)) return LogErrorP("Expected binary operator"); + FnName = "binary"; + FnName += (char)CurTok; + Kind = 2; + getNextToken(); + if (CurTok == tok_number) { + if (NumVal < 1 || NumVal > 100) + return LogErrorP("Invalid precedence: must be 1..100"); + BinaryPrecedence = (unsigned)NumVal; + getNextToken(); + } + break; + } if (CurTok != '(') return LogErrorP("Expected '(' in prototype"); @@ -223,7 +335,13 @@ static std::unique_ptr ParsePrototype() { getNextToken(); // eat ')' - return llvm::make_unique(FnName, std::move(ArgNames)); + if (Kind && ArgNames.size() != Kind) + return LogErrorP("Invalid number of of arguments for operator"); + + return llvm::make_unique(FnName, + std::move(ArgNames), + Kind != 0, + BinaryPrecedence); } static std::unique_ptr ParseDefinition() { @@ -281,8 +399,6 @@ static void HandleExtern() { static void HandleTopLevelExpr() { if (auto expr = ParseTopLevelExpr()) { if (auto gen = expr->codegen()) { - gen->print(errs()); - auto module = TheModule.get(); TheEngine->addModule(std::move(TheModule)); InitializeModuleAndPassManager(); @@ -326,6 +442,8 @@ int main() { InitializeNativeTargetAsmParser(); BinopPrecedence['<'] = 10; + BinopPrecedence['>'] = 10; + BinopPrecedence['|'] = 5; BinopPrecedence['+'] = 20; BinopPrecedence['-'] = 20; BinopPrecedence['*'] = 40; @@ -333,7 +451,7 @@ int main() { InitializeModuleAndPassManager(); std::string engineError; - TheEngine = EngineBuilder(std::move(TheModule)).setErrorStr(&engineError).create(); + TheEngine = EngineBuilder(std::move(TheModule)).setEngineKind(EngineKind::JIT).setErrorStr(&engineError).create(); if (!engineError.empty()) std::cout << engineError << "\n"; @@ -345,8 +463,6 @@ int main() { mainLoop(); - PrintModule(); - return 0; } diff --git a/Kaleidoscope/makefile b/Kaleidoscope/makefile index aee7f4b..9f4dc1d 100644 --- a/Kaleidoscope/makefile +++ b/Kaleidoscope/makefile @@ -1,2 +1,2 @@ all: - clang++ -g `llvm-config --cxxflags --ldflags --system-libs --libs core mcjit native passes interpreter` -o bin/kaleidoscope *.cpp + clang++ -g `/usr/local/opt/llvm/bin/llvm-config --cxxflags --ldflags --system-libs --libs core mcjit native passes interpreter` -o bin/kaleidoscope *.cpp diff --git a/Kaleidoscope/shared.h b/Kaleidoscope/shared.h index b92baf0..5148813 100644 --- a/Kaleidoscope/shared.h +++ b/Kaleidoscope/shared.h @@ -10,5 +10,6 @@ #define shared_h extern std::unique_ptr TheModule; +static std::map BinopPrecedence; #endif /* shared_h */ -- 2.30.2