diff --git a/.gitignore b/.gitignore index 1acf416..672d37a 100644 --- a/.gitignore +++ b/.gitignore @@ -1,82 +1,81 @@ # Compiled Object files *.slo *.lo *.o *.obj # Compiled Dynamic libraries *.so *.so.* *.dylib *.dll # Compiled Static libraries *.lai *.la *.a *.lib # Executables *.exe *.out *.app *.class # Mobile Tools for Java (J2ME) .mtj.tmp/ # Package Files # *.jar *.war *.ear # virtual machine crash logs, see http://www.java.com/en/download/help/error_hotspot.xml hs_err_pid* # Qt-es /.qmake.cache /.qmake.stash *.pro.user *.pro.user.* *.moc moc_*.cpp qrc_*.cpp ui_*.h Makefile* *-build-* # QtCreator *.autosave coco/*.old coco/*~ *~ cpp/build-*/* cpp/xreate-debug/* cpp/xreate-release/* cpp/.idea CMakeLists.txt.user cmake_install.cmake project/* nb*.xml .* target/* /tools/phabricator/xreate-frontend/nbproject/private/ documentation/trash4/ trash/ CMakeFiles/ gen-cpp/ generated-cpp/ gen-php/ generated-js/ books/ build/ coco/Parser.* coco/Scanner.* -scripts/ tools/phabricator/administration/ diff --git a/config/default.json b/config/default.json index 1cf60ec..9f1f85a 100644 --- a/config/default.json +++ b/config/default.json @@ -1,70 +1,69 @@ { "containers": { "id": { "implementations": "impl_fulfill_cluster", "clusters": "var_cluster", "prototypes": "proto_cluster", "linkedlist": "linkedlist" }, "impl": { "solid": "solid", "onthefly": "on_the_fly" } }, "logging": { "id": "logging" }, "function-entry": "entry", "clasp": { "bindings" : { "variable": "bind", "function": "bind_func", "scope": "bind_scope", "function_demand" : "bind_function_demand", "scope_decision": "bind_scope_decision" }, "context" : { "decisions":{ "dependent": "resolution_dependency" }, }, "nonevalue": "nonevalue", "ret": { "symbol": "retv", "tag": "ret" } }, "tests": { "template": "default", "templates": { "default": "*-", "adhocs": "Adhoc.*", "effects": "Effects.*", "basic": "Attachments.*", "ast": "AST.*", "cfa": "CFA.*", "dfa": "DFA.*", "compilation": "Compilation.*", "diagnostic": "Diagnostic.*", "ExpressionSerializer": "ExpressionSerializer.*", "externc": "InterfaceExternC.*", "types": "Types.*-", "vendorsAPI/clang": "ClangAPI.*", "vendorsAPI/xml2": "libxml2*", "dsl": "Interpretation.*", "context": "Context.*", "containers": "Containers.*", - "loops": "Loop.*" } } } diff --git a/cpp/src/CMakeLists.txt b/cpp/src/CMakeLists.txt index e0f83ad..c42834a 100644 --- a/cpp/src/CMakeLists.txt +++ b/cpp/src/CMakeLists.txt @@ -1,215 +1,218 @@ cmake_minimum_required(VERSION 2.8.11) project(xreate) cmake_policy(SET CMP0022 NEW) message("MODULES" ${CMAKE_MODULE_PATH}) # LLVM #====================== FIND_PACKAGE (LLVM REQUIRED) set(LLVM_VERSION ${LLVM_VERSION_MAJOR}.${LLVM_VERSION_MINOR}) message(STATUS "Found LLVM ${LLVM_PACKAGE_VERSION}") message("LLVM LIB PATH:" ${LLVM_LIBRARY_DIRS}) message(STATUS "Using LLVMConfig.cmake in: ${LLVM_DIR}") INCLUDE_DIRECTORIES(${LLVM_INCLUDE_DIRS}) message(STATUS "INCLUDE DIR: ${LLVM_INCLUDE_DIRS}") add_definitions(${LLVM_DEFINITIONS}) message("LLVM DEFS: " ${LLVM_DEFINITIONS}) llvm_map_components_to_libnames(LLVM_LIBS core nativecodegen native executionengine mcjit support option) message("LLVM LIBS: " ${LLVM_LIBS}) # CLANG #====================== set(CLANG_LIBS clangCodeGen clangASTMatchers clangQuery clangTooling clangFrontend clangSerialization clangDriver clangParse clangSema clangAnalysis clangAST clangEdit clangLex clangBasic ) # POTASSCO #====================== set(POTASSCO_PATH "/opt/potassco/clingo" CACHE PATH "Path to potassco sources") set(POTASSCO_INCLUDE_PATH ${POTASSCO_PATH}/libgringo ${POTASSCO_PATH}/libclasp ${POTASSCO_PATH}/libclingo ${POTASSCO_PATH}/libprogram_opts ${POTASSCO_PATH}/liblp ) INCLUDE_DIRECTORIES(${POTASSCO_INCLUDE_PATH}) set(LIBCLASP_LIBS clingo clasp gringo program_opts reify lp ) message("CLASP LIBS: " ${LIBCLASP_LIBS}) # OTHER DEPENDENCIES #=========================== set(JEAYESON_INCLUDE_PATH ${CMAKE_HOME_DIRECTORY}/../vendors/jeayeson/include/ ) INCLUDE_DIRECTORIES(${JEAYESON_INCLUDE_PATH}) # COCO #=========================== set(COCO_EXECUTABLE "" CACHE PATH "Path to coco executable") set(COCO_FRAMES_PATH "" CACHE PATH "Path to coco frames") set(COCO_GRAMMAR_PATH ${CMAKE_HOME_DIRECTORY}/../coco/) set(COCO_SOURCE_FILES ${COCO_GRAMMAR_PATH}/Parser.cpp ${COCO_GRAMMAR_PATH}/Scanner.cpp) INCLUDE_DIRECTORIES(${COCO_GRAMMAR_PATH}) add_custom_command(OUTPUT ${COCO_SOURCE_FILES} COMMAND ${COCO_GRAMMAR_PATH}/gen-grammar ${COCO_EXECUTABLE} ${COCO_FRAMES_PATH} WORKING_DIRECTORY ${COCO_GRAMMAR_PATH} MAIN_DEPENDENCY ${COCO_GRAMMAR_PATH}/xreate.ATG ) message(STATUS "COCO GRAMMAR BUILD STATUS:" ${COCO_OUTPUT}) # XREATE #====================== set(SOURCE_FILES + compilation/transformations.cpp + compilation/transformersaturation.cpp + pass/compilepass.cpp pass/dfapass.cpp analysis/dfagraph.cpp pass/versionspass.cpp compilation/targetinterpretation.cpp - pass/compilepass.cpp + attachments.cpp ast.cpp ExternLayer.cpp analysis/cfagraph.cpp analysis/aux.cpp compilation/containers.cpp compilation/advanced.cpp clasplayer.cpp compilation/latecontextcompiler2.cpp query/context.cpp llvmlayer.cpp utils.cpp passmanager-bare.cpp passmanager-full.cpp pass/abstractpass.cpp pass/cfapass.cpp pass/adhocpass.cpp contextrule.cpp query/containers.cpp pass/interpretationpass.cpp analysis/DominatorsTreeAnalysisProvider.cpp serialization/expressionserializer.cpp ) set(XREATE_INCLUDE_DIRS ${CMAKE_CURRENT_SOURCE_DIR}/ ) INCLUDE_DIRECTORIES(${XREATE_INCLUDE_DIRS}) set(XREATE_PRIVATE_INCLUDE_DIRS ${XREATE_INCLUDE_DIRS} ${COCO_GRAMMAR_PATH} ${JEAYESON_INCLUDE_PATH} ${LLVM_INCLUDE_DIRS} ${POTASSCO_INCLUDE_PATH} ) add_library(${PROJECT_NAME} SHARED ${SOURCE_FILES} ${COCO_SOURCE_FILES}) target_link_libraries(${PROJECT_NAME}) target_include_directories(${PROJECT_NAME} INTERFACE ${XREATE_INCLUDE_DIRS} ${COCO_GRAMMAR_PATH} ${JEAYESON_INCLUDE_PATH} ${LLVM_INCLUDE_DIRS} ${POTASSCO_INCLUDE_PATH} ) get_directory_property(DEFINITIONS_ALL DIRECTORY ${CMAKE_CURRENT_SOURCE_DIR} COMPILE_DEFINITIONS) message("definitions all: " ${DEFINITIONS_ALL}) target_compile_definitions(${PROJECT_NAME} INTERFACE ${DEFINITIONS_ALL}) get_directory_property(COMPILATION_OPTIONS_ALL DIRECTORY ${CMAKE_CURRENT_SOURCE_DIR} COMPILE_OPTIONS) message("compilations all: " ${COMPILATION_OPTIONS_ALL}) target_compile_options(${PROJECT_NAME} INTERFACE ${COMPILATION_OPTIONS_ALL}) SET_PROPERTY(TARGET ${PROJECT_NAME} PROPERTY INTERFACE_LINK_LIBRARIES ${LIBCLASP_LIBS} ${CLANG_LIBS} ${LLVM_LIBS} tbb ) #${CLANG_LIBS} #set (LINK_INTERFACE_LIBRARIES "") # FUNCTION(PREPEND var prefix) # SET(listVar "") # FOREACH(f ${ARGN}) # LIST(APPEND listVar "${prefix}/${f}") # ENDFOREACH(f) # SET(${var} "${listVar}" PARENT_SCOPE) # ENDFUNCTION(PREPEND) #set(COTIRE_UNITY_SOURCE_MAXIMUM_NUMBER_OF_INCLUDES "-j4") #cotire(xreate) # MACRO (ADD_PCH_RULE _header_filename _src_list) # SET(_gch_filename "${_header_filename}.gch") # LIST(APPEND ${_src_list} ${_gch_filename}) # SET (_args ${CMAKE_CXX_FLAGS}) # LIST(APPEND _args -c ${_header_filename} -o ${_gch_filename}) # GET_DIRECTORY_PROPERTY(DIRINC INCLUDE_DIRECTORIES) # foreach (_inc ${DIRINC}) # LIST(APPEND _args "-I" ${_inc}) # endforeach(_inc ${DIRINC}) # SEPARATE_ARGUMENTS(_args) # add_custom_command(OUTPUT ${_gch_filename} # COMMAND rm -f ${_gch_filename} # COMMAND ${CMAKE_CXX_COMPILER} ${CMAKE_CXX_COMPILER_ARG1} ${_args} # DEPENDS ${_header_filename}) # ENDMACRO(ADD_PCH_RULE _header_filename _src_list) # ADD_PCH_RULE (${CMAKE_HOME_DIRECTORY}/src/ast.h SOURCE_FILES) # ADD_PCH_RULE (${CMAKE_HOME_DIRECTORY}/src/llvmlayer.h SOURCE_FILES) # ADD_PCH_RULE (${CMAKE_HOME_DIRECTORY}/src/clasplayer.h SOURCE_FILES) # ADD_PCH_RULE (${CMAKE_HOME_DIRECTORY}/src/pass/abstractpass.h SOURCE_FILES) diff --git a/cpp/src/compilation/advanced.cpp b/cpp/src/compilation/advanced.cpp index afef03a..d5183a8 100644 --- a/cpp/src/compilation/advanced.cpp +++ b/cpp/src/compilation/advanced.cpp @@ -1,404 +1,403 @@ /* * File: InstructionsAdvanced.cpp * Author: pgess * * Created on June 26, 2016, 6:00 PM */ //#include #include "compilation/advanced.h" #include "compilation/containers.h" +#include "compilation/transformersaturation.h" #include "query/context.h" #include "query/containers.h" #include "llvmlayer.h" #include "ast.h" using namespace std; using namespace llvm; using namespace xreate; using namespace xreate::containers; using namespace xreate::compilation; #define NAME(x) (hintRetVar.empty()? x : hintRetVar) #define UNUSED(x) (void)(x) #define EXPAND_CONTEXT \ LLVMLayer* llvm = context.pass->man->llvm; \ compilation::AbstractCodeScopeUnit* scope = context.scope; \ compilation::FunctionUnit* function = context.function; Advanced::Advanced(compilation::Context ctx) : context(ctx), tyNum(static_cast (ctx.pass->man->llvm->toLLVMType(ExpandedType(TypeAnnotation(TypePrimitive::Num))))) { } llvm::Value* Advanced::compileMapSolidOutput(const Expression &expr, const std::string hintRetVar) { EXPAND_CONTEXT //initialization Symbol symbolIn = Attachments::get(expr.getOperands()[0]); ImplementationRec implIn = containers::Query::queryImplementation(symbolIn).extract(); // impl of input list size_t size = implIn.size; CodeScope* scopeLoop = expr.blocks.front(); std::string varEl = scopeLoop->__bindings[0]; Iterator* it = Iterator::create(context, symbolIn); llvm::Value *rangeFrom = it->begin(); llvm::Value *rangeTo = it->end(); //definitions ArrayType* tyNumArray = (ArrayType*) (llvm->toLLVMType(ExpandedType(TypeAnnotation(tag_array, TypePrimitive::Num, size)))); llvm::IRBuilder<> &builder = llvm->builder; llvm::BasicBlock *blockLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "loop", function->raw); llvm::BasicBlock *blockBeforeLoop = builder.GetInsertBlock(); llvm::BasicBlock *blockAfterLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "postloop", function->raw); Value* dataOut = llvm->builder.CreateAlloca(tyNumArray, ConstantInt::get(tyNum, size), NAME("map")); // * initial check Value* condBefore = builder.CreateICmpSLE(rangeFrom, rangeTo); builder.CreateCondBr(condBefore, blockLoop, blockAfterLoop); // create PHI: builder.SetInsertPoint(blockLoop); llvm::PHINode *stateLoop = builder.CreatePHI(tyNum, 2, "mapIt"); stateLoop->addIncoming(rangeFrom, blockBeforeLoop); // loop body: Value* elIn = it->get(stateLoop, varEl); compilation::AbstractCodeScopeUnit* scopeLoopUnit = function->getScopeUnit(scopeLoop); scopeLoopUnit->bindArg(elIn, move(varEl)); Value* elOut = scopeLoopUnit->compile(); Value *pElOut = builder.CreateGEP(dataOut, ArrayRef(std::vector{ConstantInt::get(tyNum, 0), stateLoop})); builder.CreateStore(elOut, pElOut); //next iteration preparing Value *stateLoopNext = builder.CreateAdd(stateLoop, llvm::ConstantInt::get(tyNum, 1)); - stateLoop->addIncoming(stateLoopNext, blockLoop); + stateLoop->addIncoming(stateLoopNext, builder.GetInsertBlock()); //next iteration checks: Value* condAfter = builder.CreateICmpSLE(stateLoopNext, rangeTo); builder.CreateCondBr(condAfter, blockLoop, blockAfterLoop); //finalization: builder.SetInsertPoint(blockAfterLoop); return dataOut; } Value* Advanced::compileArrayIndex(llvm::Value* aggregate, std::vector indexes, std::string hintRetVar) { EXPAND_CONTEXT UNUSED(function); indexes.insert(indexes.begin(), llvm::ConstantInt::get(tyNum, 0)); llvm::Value *pEl = llvm->builder.CreateGEP(aggregate, llvm::ArrayRef(indexes)); return llvm->builder.CreateLoad(pEl, NAME("el")); } Value* Advanced::compileStructIndex(llvm::Value* aggregate, const ExpandedType& t, const std::string& idx) { EXPAND_CONTEXT UNUSED(scope); TypeUtils types(llvm); std::vector&& fields = types.getStructFields(t); for (unsigned i = 0, size = fields.size(); i < size; ++i) { if (fields.at(i) == idx) { std::vector refs; llvm::IntegerType* tyInt = llvm::Type::getInt32Ty(llvm::getGlobalContext()); llvm::ConstantInt* zero = llvm::ConstantInt::get(tyInt, 0, false); llvm::BasicBlock *blockSafe = llvm::BasicBlock::Create(llvm::getGlobalContext(), "safe", function->raw); // TODO review safety check: validPtr for `aggregate` // SECTIONTAG validptr exception PointerType* tyAggr = dyn_cast(aggregate->getType()); llvm::Value* null = llvm::ConstantPointerNull::get(tyAggr); Value* condNull = llvm->builder.CreateICmpNE(aggregate, null); llvm::BasicBlock *blockException = llvm::BasicBlock::Create(llvm::getGlobalContext(), "exception", function->raw); llvm->builder.CreateCondBr(condNull, blockSafe, blockException); llvm->initExceptionBlock(blockException); llvm->builder.SetInsertPoint(blockSafe); std::vector indexes; //dereference pointer if (types.isPointer(t)) { indexes.push_back(zero); } indexes.push_back(ConstantInt::get(tyInt, i)); Value* addr = llvm->builder.CreateGEP(aggregate, indexes); return llvm->builder.CreateLoad(addr); } } assert(false && "not found required struct field"); return nullptr; } llvm::Value* Advanced::compileFold(const Expression& fold, const std::string& hintRetVar) { EXPAND_CONTEXT assert(fold.op == Operator::FOLD); //initialization: Symbol varInSymbol = Attachments::get(fold.getOperands()[0]); Implementation info = Query::queryImplementation(varInSymbol); Iterator* it = Iterator::create(context, varInSymbol); llvm::Value* rangeBegin = it->begin(); llvm::Value* rangeEnd = it->end(); llvm::Value* accumInit = scope->process(fold.getOperands()[1]); std::string varIn = fold.getOperands()[0].getValueString(); std::string varAccum = fold.bindings[1]; std::string varEl = fold.bindings[0]; - //require transformers feature - //TransformerSaturation* transformerSaturation = context.pass->transformations->get(); - llvm::BasicBlock *blockBeforeLoop = llvm->builder.GetInsertBlock(); + std::unique_ptr transformerSaturation(new TransformerSaturation(blockBeforeLoop, context.pass->managerTransformations)); + + llvm::BasicBlock *blockLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "fold", function->raw); - llvm::BasicBlock *blockBody = llvm::BasicBlock::Create(llvm::getGlobalContext(), "body", function->raw); - llvm::BasicBlock *blockAfterLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "postfold", function->raw); + llvm::BasicBlock *blockLoopBody = llvm::BasicBlock::Create(llvm::getGlobalContext(), "fold_body", function->raw); + llvm::BasicBlock *blockAfterLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "fold_after", function->raw); + llvm::BasicBlock *blockNext = llvm::BasicBlock::Create(llvm::getGlobalContext(), "fold_next", function->raw); llvm->builder.CreateBr(blockLoop); // * create phi llvm->builder.SetInsertPoint(blockLoop); - llvm::PHINode *accum = llvm->builder.CreatePHI(accumInit->getType(), 2, NAME("accum")); + llvm::PHINode *accum = llvm->builder.CreatePHI(accumInit->getType(), 2, varAccum); accum->addIncoming(accumInit, blockBeforeLoop); llvm::PHINode *itLoop = llvm->builder.CreatePHI(rangeBegin->getType(), 2, "foldIt"); itLoop->addIncoming(rangeBegin, blockBeforeLoop); + // * loop checks + Value* condRange = llvm->builder.CreateICmpNE(itLoop, rangeEnd); + llvm->builder.CreateCondBr(condRange, blockLoopBody, blockAfterLoop); + // * loop body - llvm->builder.SetInsertPoint(blockBody); + llvm->builder.SetInsertPoint(blockLoopBody); CodeScope* scopeLoop = fold.blocks.front(); compilation::AbstractCodeScopeUnit* loopUnit = function->getScopeUnit(scopeLoop); Value* elIn = it->get(itLoop); loopUnit->bindArg(accum, move(varAccum)); loopUnit->bindArg(elIn, move(varEl)); Value* accumNext = loopUnit->compile(); + // * Loop saturation checks + bool flagSaturationTriggered = transformerSaturation->insertSaturationChecks(blockNext, blockAfterLoop, context); + llvm::BasicBlock* blockSaturation = llvm->builder.GetInsertBlock(); + if (!flagSaturationTriggered){ + llvm->builder.CreateBr(blockNext); + } + // * computing next iteration state + llvm->builder.SetInsertPoint(blockNext); Value *itLoopNext = it->advance(itLoop); accum->addIncoming(accumNext, llvm->builder.GetInsertBlock()); itLoop->addIncoming(itLoopNext, llvm->builder.GetInsertBlock()); llvm->builder.CreateBr(blockLoop); - // * break checks, continue checks - //!! only after compiled Loop Body in order to fetch saturation expression - llvm->builder.SetInsertPoint(blockLoop); - - //reuiqre transformers feature -// if (transformerSaturation->exists()) { -// transformerSaturation->inject(blockBeforeLoop, blockAfterLoop, context); -// } - - // * next iteration checks - Value* condRange = llvm->builder.CreateICmpNE(itLoop, rangeEnd); - llvm->builder.CreateCondBr(condRange, blockBody, blockAfterLoop); - - // finalization: + // * finalization: llvm->builder.SetInsertPoint(blockAfterLoop); + if (!flagSaturationTriggered){ + return accum; + } - return accum; + llvm::PHINode* result = llvm->builder.CreatePHI(accumInit->getType(), 2); + result->addIncoming(accum, blockLoop); + result->addIncoming(accumNext, blockSaturation); + return result; } llvm::Value* Advanced::compileFoldInf(const Expression& fold, const std::string& hintRetVar) { EXPAND_CONTEXT assert(fold.op == Operator::FOLD_INF); std::string accumName = fold.bindings[0]; llvm::Value* accumInit = scope->process(fold.getOperands()[0]); llvm::BasicBlock *blockBeforeLoop = llvm->builder.GetInsertBlock(); - llvm::BasicBlock *blockLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "fold", function->raw); - llvm::BasicBlock *blockBody = llvm::BasicBlock::Create(llvm::getGlobalContext(), "body", function->raw); - llvm::BasicBlock *blockAfterLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "postfold", function->raw); - - //require transformers feature - //TransformerSaturation* transformerSaturation = context.pass->transformations->get(); + llvm::BasicBlock *blockLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "foldinf", function->raw); + llvm::BasicBlock *blockNext = llvm::BasicBlock::Create(llvm::getGlobalContext(), "foldinf_next", function->raw); + llvm::BasicBlock *blockAfterLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "foldinf_post", function->raw); + std::unique_ptr transformerSaturation(new TransformerSaturation(blockBeforeLoop, context.pass->managerTransformations)); llvm->builder.CreateBr(blockLoop); // * create phi llvm->builder.SetInsertPoint(blockLoop); - llvm::PHINode *accum = llvm->builder.CreatePHI(accumInit->getType(), 2, NAME("accum")); + llvm::PHINode *accum = llvm->builder.CreatePHI(accumInit->getType(), 2, accumName); accum->addIncoming(accumInit, blockBeforeLoop); // * loop body - llvm->builder.SetInsertPoint(blockBody); CodeScope* scopeLoop = fold.blocks.front(); compilation::AbstractCodeScopeUnit* unitLoop = function->getScopeUnit(scopeLoop); unitLoop->bindArg(accum, move(accumName)); Value* accumNext = unitLoop->compile(); + // * Loop saturation checks + bool flagSaturationTriggered = transformerSaturation->insertSaturationChecks(blockNext, blockAfterLoop, context); + assert(flagSaturationTriggered); + // * computing next iteration state + llvm->builder.SetInsertPoint(blockNext); accum->addIncoming(accumNext, llvm->builder.GetInsertBlock()); llvm->builder.CreateBr(blockLoop); - // * break checks, continue checks - llvm->builder.SetInsertPoint(blockLoop); - - //require transformers feature -// assert(transformerSaturation->exists()); -// transformerSaturation->inject(blockBeforeLoop, blockAfterLoop, context); - - llvm->builder.CreateBr(blockBody); - // finalization: llvm->builder.SetInsertPoint(blockAfterLoop); - return accum; + return accumNext; } - - - llvm::Value* Advanced::compileIf(const Expression& exprIf, const std::string& hintRetVar) { EXPAND_CONTEXT //initialization: const Expression& condExpr = exprIf.getOperands()[0]; llvm::IRBuilder<>& builder = llvm->builder; //llvm::Type* tyResultType = llvm->toLLVMType(llvm->ast->expandType(exprIf.type)); llvm::BasicBlock *blockAfter = llvm::BasicBlock::Create(llvm::getGlobalContext(), "ifAfter", function->raw); llvm::BasicBlock *blockTrue = llvm::BasicBlock::Create(llvm::getGlobalContext(), "ifTrue", function->raw); llvm::BasicBlock *blockFalse = llvm::BasicBlock::Create(llvm::getGlobalContext(), "ifFalse", function->raw); llvm::Value* cond = scope->process(condExpr); llvm->builder.CreateCondBr(cond, blockTrue, blockFalse); builder.SetInsertPoint(blockTrue); CodeScope* scopeTrue = exprIf.blocks.front(); llvm::Value* resultTrue = function->getScopeUnit(scopeTrue)->compile(); + blockTrue = builder.GetInsertBlock(); builder.CreateBr(blockAfter); builder.SetInsertPoint(blockFalse); CodeScope* scopeFalse = exprIf.blocks.back(); llvm::Value* resultFalse = function->getScopeUnit(scopeFalse)->compile(); + blockFalse = builder.GetInsertBlock(); builder.CreateBr(blockAfter); builder.SetInsertPoint(blockAfter); llvm::PHINode *ret = builder.CreatePHI(resultTrue->getType(), 2, NAME("if")); ret->addIncoming(resultTrue, blockTrue); ret->addIncoming(resultFalse, blockFalse); return ret; } //TODO Switch: default variant no needed when all possible conditions are considered llvm::Value* Advanced::compileSwitch(const Expression& exprSwitch, const std::string& hintRetVar) { EXPAND_CONTEXT UNUSED(function); assert(exprSwitch.operands.size() >= 2); assert(exprSwitch.operands[1].op == Operator::CASE_DEFAULT && "No default case in Switch Statement"); int countCases = exprSwitch.operands.size() - 1; llvm::IRBuilder<>& builder = llvm->builder; llvm::BasicBlock* blockProlog = builder.GetInsertBlock(); llvm::BasicBlock *blockEpilog = llvm::BasicBlock::Create(llvm::getGlobalContext(), "switchAfter", function->raw); builder.SetInsertPoint(blockEpilog); llvm::Type* exprSwitchType = llvm->toLLVMType(ExpandedType(exprSwitch.type)); llvm::PHINode *ret = builder.CreatePHI(exprSwitchType, countCases, NAME("switch")); builder.SetInsertPoint(blockProlog); llvm::Value * conditionSwitch = scope->process(exprSwitch.operands[0]); llvm::BasicBlock *blockDefault = llvm::BasicBlock::Create(llvm::getGlobalContext(), "caseDefault", function->raw); llvm::SwitchInst * instructionSwitch = builder.CreateSwitch(conditionSwitch, blockDefault, countCases); for (int size = exprSwitch.operands.size(), i = 2; i < size; ++i) { llvm::BasicBlock *blockCase = llvm::BasicBlock::Create(llvm::getGlobalContext(), "case" + std::to_string(i), function->raw); llvm::Value* condCase = function->getScopeUnit(exprSwitch.operands[i].blocks.front())->compile(); builder.SetInsertPoint(blockCase); llvm::Value* resultCase = function->getScopeUnit(exprSwitch.operands[i].blocks.back())->compile(); builder.CreateBr(blockEpilog); ret->addIncoming(resultCase, builder.GetInsertBlock()); builder.SetInsertPoint(blockProlog); instructionSwitch->addCase(dyn_cast(condCase), blockCase); } //compile default block: builder.SetInsertPoint(blockDefault); CodeScope* scopeDefault = exprSwitch.operands[1].blocks.front(); llvm::Value* resultDefault = function->getScopeUnit(scopeDefault)->compile(); builder.CreateBr(blockEpilog); ret->addIncoming(resultDefault, builder.GetInsertBlock()); builder.SetInsertPoint(blockEpilog); return ret; } //TODO recognize cases to make const arrays/stored in global mem/stack alloced. llvm::Value* Advanced::compileListAsSolidArray(const Expression &expr, const std::string& hintRetVar) { EXPAND_CONTEXT UNUSED(scope); UNUSED(function); AST* root = context.pass->man->root; const size_t& length = expr.getOperands().size(); const Expression& expression = expr; llvm::Value* zero = ConstantInt::get(tyNum, 0); llvm::Value* one = ConstantInt::get(tyNum, 1); ExpandedType typAggrExpanded = root->expandType(expression.type); assert(typAggrExpanded->__operator == TypeOperator::ARRAY); llvm::Type* typEl = llvm->toLLVMType(ExpandedType(typAggrExpanded->__operands[0])); ArrayType* typAggr = (ArrayType*) llvm::ArrayType::get(typEl, length); llvm::Value* list = llvm->builder.CreateAlloca(typAggr, ConstantInt::get(Type::getInt32Ty(llvm::getGlobalContext()), length, false), hintRetVar); const std::vector& operands = expression.getOperands(); llvm::Value* addrOperand = llvm->builder.CreateGEP(typAggr, list, ArrayRef(std::vector{zero, zero})); llvm->builder.CreateStore(scope->process(operands.front()), addrOperand) ; for (auto i=++operands.begin(); i!=operands.end(); ++i){ addrOperand = llvm->builder.CreateGEP(typEl, addrOperand, ArrayRef(std::vector{one})); llvm->builder.CreateStore(scope->process(*i), addrOperand) ; } return list; // Value* listDest = l.builder.CreateAlloca(typList, ConstantInt::get(typI32, __size), *hintRetVar); // l.buil1der.CreateMemCpy(listDest, listSource, __size, 16); } llvm::Value* Advanced::compileConstantStringAsPChar(const string& data, const std::string& hintRetVar) { EXPAND_CONTEXT UNUSED(function); UNUSED(scope); Type* typPchar = PointerType::getUnqual(Type::getInt8Ty(llvm::getGlobalContext())); //ArrayType* typStr = (ArrayType*) (llvm->toLLVMType(ExpandedType(TypeAnnotation(tag_array, TypePrimitive::I8, size+1)))); /* std::vector chars; chars.reserve(size+1); for (size_t i=0; i< size; ++i){ chars[i] = ConstantInt::get(typI8, (unsigned char) data[i]); } chars[size] = ConstantInt::get(typI8, 0); */ Value* rawData = ConstantDataArray::getString(llvm::getGlobalContext(), data); Value* rawPtrData = llvm->builder.CreateAlloca(rawData->getType(), ConstantInt::get(Type::getInt32Ty(llvm::getGlobalContext()), 1, false)); llvm->builder.CreateStore(rawData, rawPtrData); return llvm->builder.CreateCast(llvm::Instruction::BitCast, rawPtrData, typPchar, hintRetVar); } diff --git a/cpp/src/compilation/scopedecorators.h b/cpp/src/compilation/scopedecorators.h index 1bc15da..612d68a 100644 --- a/cpp/src/compilation/scopedecorators.h +++ b/cpp/src/compilation/scopedecorators.h @@ -1,120 +1,123 @@ /* * File: scopedecorators.h * Author: pgess * * Created on February 24, 2017, 11:35 AM */ #ifndef SCOPEDECORATORS_H #define SCOPEDECORATORS_H #include "ast.h" #include "compilation/targetinterpretation.h" #include "compilation/versions.h" +#include "compilation/transformations.h" namespace xreate { class CompilePass; namespace compilation { class AbstractCodeScopeUnit; class FunctionUnit; template class CachedScopeDecorator: public Parent{ typedef CachedScopeDecorator SELF; public: CachedScopeDecorator(CodeScope* codeScope, FunctionUnit* f, CompilePass* compilePass): Parent(codeScope, f, compilePass){} void reset(){ __rawVars.clear(); } void bindArg(llvm::Value* value, std::string&& alias) { //ensure existence of an alias assert(Parent::scope->__identifiers.count(alias)); //memorize new value for an alias ScopedSymbol id{Parent::scope->__identifiers.at(alias), VERSION_NONE}; __rawVars[id] = value; } void bindArg(llvm::Value* value, const ScopedSymbol& s) { __rawVars[s] = value; } llvm::Value* compile(const std::string& hintBlockDecl="") override{ if (__rawVars.count(ScopedSymbol::RetSymbol)){ return __rawVars[ScopedSymbol::RetSymbol]; } return Parent::compile(hintBlockDecl); } llvm::Value* processSymbol(const Symbol& s, std::string hintRetVar) override{ CodeScope* scope = s.scope; SELF* self = dynamic_cast(Parent::function->getScopeUnit(scope)); if (self->__rawVars.count(s.identifier)){ return self->__rawVars[s.identifier]; } - //compilation transformations could override symbol declarations. + //Declaration could be overriden Expression declaration = CodeScope::getDeclaration(s); if (!declaration.isDefined()){ if (self->__declarationsOverriden.count(s.identifier)){ declaration = self->__declarationsOverriden[s.identifier]; } else { - assert(false); //in case of bindings there should be raws already. + assert(false); //in case of binding there should be raws provided. } } return self->__rawVars[s.identifier] = Parent::processSymbol(s, hintRetVar); } void overrideDeclaration(const Symbol binding, Expression&& declaration){ SELF* self = dynamic_cast(Parent::function->getScopeUnit(binding.scope)); self->__declarationsOverriden.emplace(binding.identifier, std::move(declaration)); } private: std::unordered_map __declarationsOverriden; std::unordered_map __rawVars; }; typedef CachedScopeDecorator< - InterpretationScopeDecorator< - VersionsScopeDecorator>> + compilation::TransformationsScopeDecorator< + compilation::InterpretationScopeDecorator< + compilation::VersionsScopeDecorator>>> DefaultScopeUnit; } //end of compilation namespace struct CachedScopeDecoratorTag; struct VersionsScopeDecoratorTag; template<> struct DecoratorsDict{ typedef compilation::CachedScopeDecorator< + compilation::TransformationsScopeDecorator< compilation::InterpretationScopeDecorator< - compilation::VersionsScopeDecorator>> result; + compilation::VersionsScopeDecorator>>> result; }; template<> struct DecoratorsDict{ typedef compilation::VersionsScopeDecorator< - compilation::VersionsScopeDecorator> result; + compilation::BasicCodeScopeUnit> result; }; } //end of xreate #endif /* SCOPEDECORATORS_H */ diff --git a/cpp/src/compilation/transformations.cpp b/cpp/src/compilation/transformations.cpp new file mode 100644 index 0000000..1588af8 --- /dev/null +++ b/cpp/src/compilation/transformations.cpp @@ -0,0 +1,29 @@ +/* + * transformation.cpp + * + * Author: pgess + * Created on March 27, 2017, 4:04 PM + */ + +#include "transformations.h" + +namespace xreate { namespace compilation { + +std::list +TransformationsManager::getRelevantTransformers(const Expression& expression){ + std::list result; + + for (auto tag: expression.tags) { + if (__subscriptions.count(tag.first)){ + auto handlers = __subscriptions.equal_range(tag.first); + + for (auto handler = handlers.first; handler != handlers.second; ++handler){ + result.push_back(__transformers[handler->second]); + } + } + } + + return result; +} + +} } //namespace xreate \ No newline at end of file diff --git a/cpp/src/compilation/transformations.h b/cpp/src/compilation/transformations.h new file mode 100644 index 0000000..4350147 --- /dev/null +++ b/cpp/src/compilation/transformations.h @@ -0,0 +1,111 @@ +/* + * File: transformations.h + * Author: pgess + * + * Created on March 25, 2017, 9:04 PM + */ + +#ifndef TRANSFORMATIONS_H +#define TRANSFORMATIONS_H + +#include "pass/compilepass.h" + +namespace xreate { namespace compilation { + +template +struct TransformerInfo { + //static const unsigned int id = 1; (current vacant id) +}; + +class Transformer{ +public: + virtual llvm::Value* transform(const Expression& expression, llvm::Value* raw, const Context& ctx)=0; + virtual ~Transformer(){}; +}; + +class TransformationsManager { +public: + std::list getRelevantTransformers(const Expression& expression); + + + template + void registerTransformer(const std::string& annotation, TransformerType* t){ + const int id = TransformerInfo::id; + + assert(!__transformers.count(id)); + __transformers[id] = t; + __subscriptions.emplace(annotation, id); + } + + template + void unregisterTransformer(const std::string& annotation, TransformerType* t){ + const unsigned int id = TransformerInfo::id; + + auto range = __subscriptions.equal_range(annotation); + const auto entry = make_pair(annotation, id); + __subscriptions.erase(std::find_if(range.first, range.second, [id](const auto& el){return el.second == id;})); + __transformers.erase(id); + } + + template + TransformerType* update(TransformerType* newInstance){ + const int id = TransformerInfo::id; + + Transformer* oldInstance = __transformers[id]; + __transformers[id] = newInstance; + + return static_cast(oldInstance); + } + + template + bool exists(){ + const int id = TransformerInfo::id; + + return __transformers.count(id); + } + + template + TransformerType* get(){ + const int id = TransformerInfo::id; + return static_cast(__transformers.at(id)); + } + +private: + std::map __transformers; + std::multimap __subscriptions; +}; + +template +class TransformationsScopeDecorator: public Transformer, public Parent { + // SCOPE DECORATOR PART +public: + TransformationsScopeDecorator(CodeScope* codeScope, FunctionUnit* f, CompilePass* compilePass) + : Parent(codeScope, f, compilePass){} + + virtual llvm::Value* + process(const Expression& expr, const std::string& hintVarDecl=""){ + llvm::Value* result = Parent::process(expr, hintVarDecl); + + return transform(expr, result, Context{this, Parent::function, Parent::pass}); + } + + // TRANSFORMER PART +public: + virtual llvm::Value* + transform(const Expression& expression, llvm::Value* raw, const Context& ctx) { + llvm::Value* result = raw; + TransformationsManager* man = Parent::pass->managerTransformations; + + if (expression.tags.size()) + for (Transformer* handler: man->getRelevantTransformers(expression)){ + result = handler->transform(expression, result, ctx); + } + + return result; + } +}; + +} } + +#endif /* TRANSFORMATIONS_H */ + diff --git a/cpp/src/compilation/transformersaturation.cpp b/cpp/src/compilation/transformersaturation.cpp new file mode 100644 index 0000000..4ea90d0 --- /dev/null +++ b/cpp/src/compilation/transformersaturation.cpp @@ -0,0 +1,77 @@ +/* + * transformersaturation.cpp + * + * Author: pgess + * Created on March 25, 2017, 10:06 PM + */ + +#include "transformersaturation.h" +#include "llvmlayer.h" + +using namespace llvm; + +namespace xreate { namespace compilation { + +TransformerSaturation::TransformerSaturation(llvm::BasicBlock* allocationBlock, TransformationsManager* manager) + : man(manager), blockAllocation(allocationBlock){ + + llvm::Type* tyInt1 = llvm::Type::getInt1Ty(llvm::getGlobalContext()); + + constTrue = llvm::ConstantInt::get(tyInt1, 1); + constFalse = llvm::ConstantInt::get(tyInt1, 0); + + if (man->exists()){ + oldInstance = man->update(this); + + } else { + man->registerTransformer("break", this); + } +} + +TransformerSaturation::~TransformerSaturation(){ + if (oldInstance) { + man->update(oldInstance); + + } else { + man->unregisterTransformer("break", this); + } +} + +llvm::Value* +TransformerSaturation::transform(const Expression& expression, llvm::Value* raw, const Context& ctx){ + processBreak(ctx); + + return raw; +} + + +void +TransformerSaturation::processBreak(const Context& ctx){ + allocateFlag(ctx); + + //show the saturation flag + llvm::IRBuilder<>& builder = ctx.pass->man->llvm->builder; + builder.CreateStore(constTrue, flagSaturation, true); +} + +void +TransformerSaturation::allocateFlag(const Context& ctx){ + //allocation of saturation flag + llvm::Type* tyInt1 = llvm::Type::getInt1Ty(llvm::getGlobalContext()); + IRBuilder<> builder(blockAllocation, blockAllocation->getFirstInsertionPt()); + + flagSaturation = builder.CreateAlloca(tyInt1, constTrue, "flagSaturation"); + builder.CreateStore(constFalse, flagSaturation, true); +} + +bool +TransformerSaturation::insertSaturationChecks(llvm::BasicBlock* blockContinue, llvm::BasicBlock* blockExit, const Context& ctx){ + if (!flagSaturation) return false; + + llvm::IRBuilder<>& builder = ctx.pass->man->llvm->builder; + builder.CreateCondBr(builder.CreateLoad(flagSaturation), blockExit, blockContinue); + + return true; +} + +} } \ No newline at end of file diff --git a/cpp/src/compilation/transformersaturation.h b/cpp/src/compilation/transformersaturation.h new file mode 100644 index 0000000..b4e368a --- /dev/null +++ b/cpp/src/compilation/transformersaturation.h @@ -0,0 +1,46 @@ +/* + * File: transformersaturation.h + * Author: pgess + * + * Created on March 25, 2017, 9:59 PM + */ + +#ifndef TRANSFORMERSATURATION_H +#define TRANSFORMERSATURATION_H + +#include "transformations.h" + +namespace xreate { namespace compilation { + +class TransformerSaturation: public Transformer{ +public: + TransformerSaturation(llvm::BasicBlock* allocationBlock, TransformationsManager* manager); + ~TransformerSaturation(); + + llvm::Value* transform(const Expression& expression, llvm::Value* raw, const Context& ctx) override; + + void processBreak(const Context& ctx); + + void allocateFlag(const Context& ctx); + bool insertSaturationChecks(llvm::BasicBlock* blockContinue, llvm::BasicBlock* blockExit, const Context& ctx); + +private: + TransformationsManager* man; + TransformerSaturation* oldInstance = nullptr; + + llvm::BasicBlock* blockAllocation; + + llvm::Value* constTrue; + llvm::Value* constFalse; + llvm::Value* flagSaturation = nullptr; +}; + +template <> +struct TransformerInfo { + static const unsigned int id = 0; +}; + +} } + +#endif /* TRANSFORMERSATURATION_H */ + diff --git a/cpp/src/pass/compilepass.cpp b/cpp/src/pass/compilepass.cpp index a84bb49..b1967c8 100644 --- a/cpp/src/pass/compilepass.cpp +++ b/cpp/src/pass/compilepass.cpp @@ -1,770 +1,765 @@ #include "compilepass.h" #include "clasplayer.h" #include #include "llvmlayer.h" #include "query/containers.h" #include "query/context.h" #include "compilation/containers.h" #include "compilation/latecontextcompiler2.h" #include "ExternLayer.h" #include "pass/adhocpass.h" #include "compilation/targetinterpretation.h" #include "pass/versionspass.h" #include "compilation/scopedecorators.h" #include #include #include using namespace std; using namespace xreate; using namespace xreate::compilation; using namespace llvm; //TODO use Scope //SECTIONTAG types/convert implementation //TODO type conversion: //a) automatically expand types int -> bigger int; int -> floating //b) detect exact type of `num` based on max used numeral / function type //c) warning if need to truncate (allow/dissalow based on annotations) namespace xreate { llvm::Value* doAutomaticTypeConversion(llvm::Value* source, llvm::Type* tyTarget, llvm::IRBuilder<>& builder){ if (tyTarget->isIntegerTy() && source->getType()->isIntegerTy()) { llvm::IntegerType* tyTargetInt = llvm::dyn_cast(tyTarget); llvm::IntegerType* tySourceInt = llvm::dyn_cast(source->getType()); if (tyTargetInt->getBitWidth() < tySourceInt->getBitWidth()){ return builder.CreateCast(llvm::Instruction::Trunc, source, tyTarget); } if (tyTargetInt->getBitWidth() > tySourceInt->getBitWidth()){ return builder.CreateCast(llvm::Instruction::SExt, source, tyTarget); } } if (source->getType()->isIntegerTy() && tyTarget->isFloatingPointTy()){ return builder.CreateCast(llvm::Instruction::SIToFP, source, tyTarget); } return source; } std::string BasicFunctionDecorator::prepareName(){ AST* ast = FunctionUnit::pass->man->root; string name = ast->getFunctionVariants(FunctionUnit::function->__name).size() > 1? FunctionUnit::function->__name + std::to_string(FunctionUnit::function.id()) : FunctionUnit::function->__name; return name; } std::vector BasicFunctionDecorator::prepareArguments(){ LLVMLayer* llvm = FunctionUnit::pass->man->llvm; AST* ast = FunctionUnit::pass->man->root; CodeScope* entry = FunctionUnit::function->__entry; std::vector signature; std::transform(entry->__bindings.begin(), entry->__bindings.end(), std::inserter(signature, signature.end()), [llvm, ast, entry](const std::string &arg)->llvm::Type* { assert(entry->__identifiers.count(arg)); ScopedSymbol argid{entry->__identifiers.at(arg), VERSION_NONE}; return llvm->toLLVMType(ast->expandType(entry->__declarations.at(argid).type)); }); return signature; } llvm::Type* BasicFunctionDecorator::prepareResult(){ LLVMLayer* llvm = FunctionUnit::pass->man->llvm; AST* ast = FunctionUnit::pass->man->root; CodeScope* entry = FunctionUnit::function->__entry; return llvm->toLLVMType(ast->expandType(entry->__declarations.at(ScopedSymbol::RetSymbol).type)); } llvm::Function::arg_iterator BasicFunctionDecorator::prepareBindings(){ CodeScope* entry = FunctionUnit::function->__entry; AbstractCodeScopeUnit* entryCompilation = FunctionUnit::getScopeUnit(entry); llvm::Function::arg_iterator fargsI = FunctionUnit::raw->arg_begin(); for (std::string &arg : entry->__bindings) { ScopedSymbol argid{entry->__identifiers[arg], VERSION_NONE}; entryCompilation->bindArg(&*fargsI, argid); fargsI->setName(arg); ++fargsI; } return fargsI; } //SECTIONTAG late-context FunctionDecorator template class LateContextFunctionDecorator: public Parent{ public: LateContextFunctionDecorator(ManagedFnPtr f, CompilePass* p) : Parent(f, p), contextCompiler(this, p) {} protected: std::vector prepareArguments(){ std::vector&& arguments = Parent::prepareArguments(); size_t sizeLateContextDemand = contextCompiler.getFunctionDemandSize(); if (sizeLateContextDemand) { llvm::Type* ty32 = llvm::Type::getInt32Ty(llvm::getGlobalContext()); llvm::Type* tyDemand = llvm::ArrayType::get(ty32, sizeLateContextDemand); arguments.push_back(tyDemand); } return arguments; } llvm::Function::arg_iterator prepareBindings(){ llvm::Function::arg_iterator fargsI = Parent::prepareBindings(); size_t sizeLateContextDemand = contextCompiler.getFunctionDemandSize(); if (sizeLateContextDemand){ fargsI->setName("latecontext"); contextCompiler.rawContextArgument = &*fargsI; ++fargsI; } return fargsI; } public: LateContextCompiler2 contextCompiler; }; //SECTIONTAG adhoc FunctionDecorator template class AdhocFunctionDecorator: public Parent{ public: AdhocFunctionDecorator(ManagedFnPtr f, CompilePass* p) : Parent(f, p) {} protected: llvm::Type* prepareResult(){ PassManager* man = Parent::pass->man; CodeScope* entry = Parent::function->__entry; LLVMLayer* llvm = Parent::pass->man->llvm; AST* ast = Parent::pass->man->root; AdhocPass* adhocpass = reinterpret_cast(man->getPassById(PassId::AdhocPass)); if (! Parent::function->isPrefunction){ return Parent::prepareResult(); } adhocImplementation = adhocpass->findAssotiatedScheme(entry); return llvm->toLLVMType(ast->expandType(adhocImplementation->getResultType())); } public: AdhocScheme* adhocImplementation=nullptr; }; //DEBT compiler rigidly depends on exact definition of DefaultFunctionUnit typedef LateContextFunctionDecorator< AdhocFunctionDecorator< BasicFunctionDecorator>> DefaultFunctionUnit; AbstractCodeScopeUnit::AbstractCodeScopeUnit(CodeScope* codeScope, FunctionUnit* f, CompilePass* compilePass) : pass(compilePass), function(f), scope(codeScope) {} llvm::Value* CallStatementRaw::operator() (std::vector&& args, const std::string& hintDecl) { llvm::Function* calleeInfo = dyn_cast(__callee); if (calleeInfo){ auto argsFormal = calleeInfo->args(); int pos=0; //SECTIONTAG types/convert function ret value for (auto argFormal = argsFormal.begin(); argFormal!=argsFormal.end(); ++argFormal, ++pos){ args[pos] = doAutomaticTypeConversion(args[pos], argFormal->getType(), llvm->builder); } } return llvm->builder.CreateCall(__calleeTy, __callee, args, hintDecl); } //DESABLEDFEATURE implement inlining class CallStatementInline: public CallStatement{ public: CallStatementInline(FunctionUnit* caller, FunctionUnit* callee, LLVMLayer* l) : __caller(caller), __callee(callee), llvm(l) {} llvm::Value* operator() (std::vector&& args, const std::string& hintDecl) { //TOTEST inlining // CodeScopeUnit* entryCompilation = outer->getScopeUnit(function->__entry); // for(int i=0, size = args.size(); ibindArg(args.at(i), string(entryCompilation->scope->__bindings.at(i))); // } // // // return entryCompilation->compile(); return nullptr; } private: FunctionUnit* __caller; FunctionUnit* __callee; LLVMLayer* llvm; bool isInline(){ // Symbol ret = Symbol{0, function->__entry}; // bool flagOnTheFly = SymbolAttachments::get(ret, false); //TODO consider inlining return false; } }; } BasicCodeScopeUnit::BasicCodeScopeUnit(CodeScope* codeScope, FunctionUnit* f, CompilePass* compilePass) : AbstractCodeScopeUnit(codeScope, f, compilePass) {} llvm::Value* BasicCodeScopeUnit::processSymbol(const Symbol& s, std::string hintRetVar){ Expression declaration = CodeScope::getDeclaration(s); CodeScope* scope = s.scope; AbstractCodeScopeUnit* self = AbstractCodeScopeUnit::function->getScopeUnit(scope); return self->process(declaration, hintRetVar); } //SECTIONTAG late-context find callee function //TOTEST static late context decisions //TOTEST dynamic late context decisions CallStatement* BasicCodeScopeUnit::findFunction(const std::string& calleeName){ LLVMLayer* llvm = pass->man->llvm; ClaspLayer* clasp = pass->man->clasp; DefaultFunctionUnit* function = dynamic_cast(this->function); ContextQuery* queryContext = pass->queryContext; const std::list& specializations = pass->man->root->getFunctionVariants(calleeName); //if no specializations registered - check external function if (specializations.size()==0){ llvm::Function* external = llvm->layerExtern->lookupFunction(calleeName); return new CallStatementRaw(external, llvm); } //no decisions required if (specializations.size()==1){ if (!specializations.front()->guardContext.isValid()) { return new CallStatementRaw( pass->getFunctionUnit(specializations.front())->compile(), llvm); } } //TODO move dictSpecialization over to a separate function in order to perform cache, etc. //prepare specializations dictionary std::map dictSpecializations; boost::optional variantDefault; boost::optional variant; for(const ManagedFnPtr& f: specializations){ const Expression& guard = f->guardContext; //default case: if (!guard.isValid()){ variantDefault = f; continue; } assert(dictSpecializations.emplace(guard, f).second && "Found several identical specializations"); } //check static context ScopePacked scopeCaller = clasp->pack(this->scope); const string atomSpecialization = "specialization"; const Expression topicSpecialization(Operator::CALL, {(Atom(string(atomSpecialization))), (Atom(string(calleeName))), (Atom(scopeCaller))}); const Decisions& decisions = queryContext->getFinalDecisions(scopeCaller); if (decisions.count(topicSpecialization)){ variant = dictSpecializations.at(decisions.at(topicSpecialization)); } //TODO check only demand for this particular topic. size_t sizeDemand = function->contextCompiler.getFunctionDemandSize(); //decision made if static context found or no late context exists(and there is default variant) bool flagHasStaticDecision = variant || (variantDefault && !sizeDemand); //if no late context exists if (flagHasStaticDecision) { FunctionUnit* calleeUnit = pass->getFunctionUnit(variant? *variant: *variantDefault); //inlining possible based on static decision only // if (calleeUnit->isInline()) { // return new CallStatementInline(function, calleeUnit); // } return new CallStatementRaw(calleeUnit->compile(), llvm); } //require default variant if no static decision made assert(variantDefault); llvm::Function* functionVariantDefault = this->pass->getFunctionUnit(*variantDefault)->compile(); llvm::Value* resultFn = function->contextCompiler.findFunction(calleeName, functionVariantDefault, scopeCaller); llvm::PointerType *resultPTy = cast(resultFn->getType()); llvm::FunctionType *resultFTy = cast(resultPTy->getElementType()); return new CallStatementRaw(resultFn, resultFTy, llvm); } //DISABLEDFEATURE transformations // if (pass->transformations->isAcceptable(expr)){ // return pass->transformations->transform(expr, result, ctx); // } llvm::Value* BasicCodeScopeUnit::process(const Expression& expr, const std::string& hintVarDecl){ #define DEFAULT(x) (hintVarDecl.empty()? x: hintVarDecl) llvm::Value *left; llvm::Value *right; LLVMLayer& l = *pass->man->llvm; xreate::compilation::Advanced instructions = xreate::compilation::Advanced({this, function, pass}); switch (expr.op) { case Operator::ADD: case Operator::SUB: case Operator::MUL: case Operator::DIV: case Operator::EQU: case Operator::LSS: case Operator::GTR: case Operator::NE: case Operator::LSE: case Operator::GTE: assert(expr.__state == Expression::COMPOUND); assert(expr.operands.size() == 2); left = process(expr.operands[0]); right = process(expr.operands[1]); //SECTIONTAG types/convert binary operation right = doAutomaticTypeConversion(right, left->getType(), l.builder); break; default:; } switch (expr.op) { case Operator::ADD: return l.builder.CreateAdd(left, right, DEFAULT("tmp_add")); break; case Operator::SUB: return l.builder.CreateSub(left, right, DEFAULT("tmp_sub")); break; case Operator::MUL: return l.builder.CreateMul(left, right, DEFAULT("tmp_mul")); break; case Operator::DIV: return l.builder.CreateSDiv(left, right, DEFAULT("tmp_div")); break; case Operator::EQU: if (left->getType()->isIntegerTy()) return l.builder.CreateICmpEQ(left, right, DEFAULT("tmp_equ")); if (left->getType()->isFloatingPointTy()) return l.builder.CreateFCmpOEQ(left, right, DEFAULT("tmp_equ")); break; case Operator::NE: return l.builder.CreateICmpNE(left, right, DEFAULT("tmp_ne")); break; case Operator::LSS: return l.builder.CreateICmpSLT(left, right, DEFAULT("tmp_lss")); break; case Operator::LSE: return l.builder.CreateICmpSLE(left, right, DEFAULT("tmp_lse")); break; case Operator::GTR: return l.builder.CreateICmpSGT(left, right, DEFAULT("tmp_gtr")); break; case Operator::GTE: return l.builder.CreateICmpSGE(left, right, DEFAULT("tmp_gte")); break; case Operator::NEG: left = process(expr.operands[0]); return l.builder.CreateNeg(left, DEFAULT("tmp_neg")); break; case Operator::CALL: { assert(expr.__state == Expression::COMPOUND); std::string nameCallee = expr.getValueString(); shared_ptr callee(findFunction(nameCallee)); //prepare arguments std::vector args; args.reserve(expr.operands.size()); std::transform(expr.operands.begin(), expr.operands.end(), std::inserter(args, args.end()), [this](const Expression &operand) { return process(operand); } ); ScopePacked outerScopeId = pass->man->clasp->pack(this->scope); //TASK a) refactor CALL/ADHOC/find function //SECTIONTAG late-context propagation arg size_t calleeDemandSize = pass->queryContext->getFunctionDemand(nameCallee).size(); if (calleeDemandSize){ DefaultFunctionUnit* function = dynamic_cast(this->function); llvm::Value* argLateContext = function->contextCompiler.compileContextArgument(nameCallee, outerScopeId); args.push_back(argLateContext); } return (*callee)(move(args), DEFAULT("res_"+nameCallee)); } case Operator::IF: { return instructions.compileIf(expr, DEFAULT("tmp_if")); } case Operator::SWITCH: { return instructions.compileSwitch(expr, DEFAULT("tmp_switch")); } case Operator::LOOP_CONTEXT: { assert(false); return nullptr; //return instructions.compileLoopContext(expr, DEFAULT("tmp_loop")); } case Operator::LOGIC_AND: { assert(expr.operands.size() == 1); return process (expr.operands[0]); } case Operator::LIST: { return instructions.compileListAsSolidArray(expr, DEFAULT("tmp_list")); }; case Operator::LIST_RANGE: { assert(false); //no compilation phase for a range list // return InstructionList(this).compileConstantArray(expr, l, hintRetVar); }; case Operator::LIST_NAMED: { typedef Expanded ExpandedType; ExpandedType tyRaw = l.ast->expandType(expr.type); const std::vector fields = (tyRaw.get().__operator == TypeOperator::CUSTOM)? l.layerExtern->getStructFields(l.layerExtern->lookupType(tyRaw.get().__valueCustom)) : tyRaw.get().fields; std::map indexFields; for(size_t i=0, size = fields.size(); i(l.toLLVMType(tyRaw)); llvm::Value* record = llvm::UndefValue::get(tyRecord); for (size_t i=0; igetElementType(fieldId); // result = llvm::UndefValue::get(tyNullField); // // } else { result = process(operand); // } assert (result); record = l.builder.CreateInsertValue(record, result, llvm::ArrayRef({fieldId})); } return record; }; case Operator::MAP: { assert(expr.blocks.size()); return instructions.compileMapSolidOutput(expr, DEFAULT("map")); }; case Operator::FOLD: { return instructions.compileFold(expr, DEFAULT("fold")); }; case Operator::FOLD_INF: { return instructions.compileFoldInf(expr, DEFAULT("fold")); }; case Operator::INDEX: { //TODO allow multiindex assert(expr.operands.size()==2); assert(expr.operands[0].__state == Expression::IDENT); const std::string& hintIdent= expr.operands[0].getValueString(); Symbol s = Attachments::get(expr.operands[0]); const ExpandedType& t2 = pass->man->root->expandType(CodeScope::getDeclaration(s).type); llvm::Value* aggr = processSymbol(s, hintIdent); switch (t2.get().__operator) { case TypeOperator::STRUCT: case TypeOperator::CUSTOM: { const Expression& idx = expr.operands.at(1); assert(idx.__state == Expression::STRING); std::string idxField = idx.getValueString(); return instructions.compileStructIndex(aggr, t2, idxField); }; case TypeOperator::ARRAY: { std::vector indexes; std::transform(++expr.operands.begin(), expr.operands.end(), std::inserter(indexes, indexes.end()), [this] (const Expression& op){ return process(op); } ); return instructions.compileArrayIndex(aggr, indexes, DEFAULT(string("el_") + hintIdent)); }; default: assert(false); } }; //SECTIONTAG adhoc actual compilation //TODO a) make sure that it's correct: function->adhocImplementation built for Entry scope and used in another scope case Operator::ADHOC: { DefaultFunctionUnit* function = dynamic_cast(this->function); assert(function->adhocImplementation && "Adhoc implementation not found"); const Expression& comm = AdhocExpression(expr).getCommand(); CodeScope* scope = function->adhocImplementation->getCommandImplementation(comm); AbstractCodeScopeUnit* unitScope = function->getScopeUnit(scope); //SECTIONTAG types/convert ADHOC ret convertation llvm::Type* resultTy = l.toLLVMType( pass->man->root->expandType(function->adhocImplementation->getResultType())); return doAutomaticTypeConversion(unitScope->compile(), resultTy, l.builder); }; case Operator::CALL_INTRINSIC:{ const std::string op = expr.getValueString(); if (op == "copy") { llvm::Value* result = process(expr.getOperands().at(0)); auto decoratorVersions = Decorators::getInterface(this); llvm::Value* storage = decoratorVersions->processIntrinsicInit(result->getType()); decoratorVersions->processIntrinsicCopy(result, storage); return l.builder.CreateLoad(storage, hintVarDecl); } assert(false && "undefined intrinsic"); } case Operator::NONE: assert(expr.__state != Expression::COMPOUND); switch (expr.__state) { case Expression::IDENT: { Symbol s = Attachments::get(expr); return processSymbol(s, expr.getValueString()); } case Expression::NUMBER: { llvm::Type* typConst; if (expr.type.isValid()){ typConst = l.toLLVMType(pass->man->root->expandType(expr.type)); } else { typConst = llvm::Type::getInt32Ty(llvm::getGlobalContext()); } int literal = expr.getValueDouble(); return llvm::ConstantInt::get(typConst, literal); } case Expression::STRING: { return instructions.compileConstantStringAsPChar(expr.getValueString(), DEFAULT("tmp_str")); }; case Expression::VARIANT: { const ExpandedType& typVariant = pass->man->root->expandType(expr.type); llvm::Type* typRaw = l.toLLVMType(typVariant); int value = expr.getValueDouble(); return llvm::ConstantInt::get(typRaw, value); } default: { break; } }; break; default: break; } assert(false); return 0; } llvm::Value* BasicCodeScopeUnit::compile(const std::string& hintBlockDecl){ if (!hintBlockDecl.empty()) { llvm::BasicBlock *block = llvm::BasicBlock::Create(llvm::getGlobalContext(), hintBlockDecl, function->raw); pass->man->llvm->builder.SetInsertPoint(block); } Symbol symbScope = Symbol{ScopedSymbol::RetSymbol, scope}; return processSymbol(symbScope); } llvm::Function* FunctionUnit::compile(){ if (raw != nullptr) return raw; LLVMLayer* llvm = pass->man->llvm; llvm::IRBuilder<>& builder = llvm->builder; string&& functionName = prepareName(); std::vector&& types = prepareArguments(); llvm::Type* expectedResultType = prepareResult(); llvm::FunctionType *ft = llvm::FunctionType::get(expectedResultType, types, false); raw = llvm::cast(llvm->module->getOrInsertFunction(functionName, ft)); prepareBindings(); const std::string&blockName = "entry"; llvm::BasicBlock* blockCurrent = builder.GetInsertBlock(); llvm::Value* result =getScopeUnit(function->__entry)->compile(blockName); assert(result); //SECTIONTAG types/convert function ret value builder.CreateRet(doAutomaticTypeConversion(result, expectedResultType, llvm->builder)); if (blockCurrent){ builder.SetInsertPoint(blockCurrent); } llvm->moveToGarbage(ft); return raw; } AbstractCodeScopeUnit* FunctionUnit::getScopeUnit(CodeScope* scope){ if (!scopes.count(scope)){ AbstractCodeScopeUnit* unit = new DefaultScopeUnit(scope, this, pass); scopes.emplace(scope, std::unique_ptr(unit)); } return scopes.at(scope).get(); } AbstractCodeScopeUnit* FunctionUnit::getEntry(){ return getScopeUnit(function->getEntryScope()); } AbstractCodeScopeUnit* FunctionUnit::getScopeUnit(ManagedScpPtr scope){ return getScopeUnit(&*scope); } FunctionUnit* CompilePass::getFunctionUnit(const ManagedFnPtr& function){ unsigned int id = function.id(); if (!functions.count(id)){ FunctionUnit* unit = new DefaultFunctionUnit(function, this); functions.emplace(id, unit); return unit; } return functions.at(id); } void CompilePass::run(){ -// transformations = new Transformations(this); - - //DISABLEDFEATURE transformerSaturation - //transformations->registerTransformer(new TransformerSaturation(transformations)); - + managerTransformations = new TransformationsManager(); targetInterpretation = new TargetInterpretation(this->man->root, this); - queryContext = reinterpret_cast (man->clasp->getQuery(QueryId::ContextQuery)); //Find out main function; ClaspLayer::ModelFragment model = man->clasp->query(Config::get("function-entry")); assert(model && "Error: No entry function found"); assert(model->first != model->second && "Error: Ambiguous entry function"); string nameMain = std::get<0>(ClaspLayer::parse(model->first->second)); FunctionUnit* unitMain = getFunctionUnit(man->root->findFunction(nameMain)); entry = unitMain->compile(); } llvm::Function* CompilePass::getEntryFunction(){ assert(entry); return entry; } void CompilePass::prepareQueries(ClaspLayer* clasp){ clasp->registerQuery(new containers::Query(), QueryId::ContainersQuery); clasp->registerQuery(new ContextQuery(), QueryId::ContextQuery); } \ No newline at end of file diff --git a/cpp/src/pass/compilepass.h b/cpp/src/pass/compilepass.h index 1297617..2c84988 100644 --- a/cpp/src/pass/compilepass.h +++ b/cpp/src/pass/compilepass.h @@ -1,166 +1,167 @@ #ifndef COMPILEPASS_H #define COMPILEPASS_H #include "abstractpass.h" #include "llvm/IR/Function.h" namespace xreate { class AdhocScheme; class ClaspLayer; class ContextQuery; class LLVMLayer; } //namespace llvm { // class Function; // class Value; // class Type; //} namespace xreate { class CompilePass; namespace compilation { class AbstractCodeScopeUnit; class FunctionUnit; class TargetInterpretation; +class TransformationsManager; struct Context{ AbstractCodeScopeUnit* scope; FunctionUnit* function; CompilePass* pass; }; class CallStatement { public: virtual llvm::Value* operator() (std::vector&& args, const std::string& hintDecl="") = 0; }; class CallStatementRaw: public CallStatement{ public: CallStatementRaw(llvm::Function* callee, LLVMLayer* l) : __callee(callee), __calleeTy(callee->getFunctionType()), llvm(l) {} CallStatementRaw(llvm::Value* callee, llvm::FunctionType* ty, LLVMLayer* l) : __callee(callee), __calleeTy(ty), llvm(l) {} llvm::Value* operator() (std::vector&& args, const std::string& hintDecl=""); private: llvm::Value* __callee; llvm::FunctionType* __calleeTy; LLVMLayer* llvm; }; class AbstractCodeScopeUnit{ public: CompilePass* const pass; FunctionUnit* const function; CodeScope* const scope; AbstractCodeScopeUnit(CodeScope* codeScope, FunctionUnit* f, CompilePass* compilePass); ~AbstractCodeScopeUnit(){} virtual llvm::Value* compile(const std::string& hintBlockDecl="")=0; virtual llvm::Value* processSymbol(const Symbol& s, std::string hintRetVar="")=0; virtual llvm::Value* process(const Expression& expr, const std::string& hintVarDecl="")=0; virtual void bindArg(llvm::Value* value, std::string&& alias)=0; virtual void bindArg(llvm::Value* value, const ScopedSymbol& s)=0; protected: virtual CallStatement* findFunction(const std::string& callee)=0; }; class BasicCodeScopeUnit: public AbstractCodeScopeUnit{ public: BasicCodeScopeUnit(CodeScope* codeScope, FunctionUnit* f, CompilePass* compilePass); ~BasicCodeScopeUnit(){} llvm::Value* processSymbol(const Symbol& s, std::string hintRetVar=""); llvm::Value* process(const Expression& expr, const std::string& hintVarDecl=""); llvm::Value* compile(const std::string& hintBlockDecl=""); protected: CallStatement* findFunction(const std::string& callee); }; class IFunctionDecorator { protected: virtual std::string prepareName() = 0; virtual std::vector prepareArguments() = 0; virtual llvm::Type* prepareResult() = 0; virtual llvm::Function::arg_iterator prepareBindings() = 0; virtual ~IFunctionDecorator(){} }; class FunctionUnit: public IFunctionDecorator{ public: FunctionUnit(ManagedFnPtr f, CompilePass* p) : function(f), pass(p) {} llvm::Function* compile(); AbstractCodeScopeUnit* getEntry(); AbstractCodeScopeUnit* getScopeUnit(CodeScope* scope); AbstractCodeScopeUnit* getScopeUnit(ManagedScpPtr scope); ManagedFnPtr function; llvm::Function* raw = nullptr; protected: CompilePass* pass=nullptr; private: std::map> scopes; }; class BasicFunctionDecorator: public FunctionUnit{ public: BasicFunctionDecorator(ManagedFnPtr f, CompilePass* p) : FunctionUnit(f, p) {} protected: std::string prepareName(); virtual std::vector prepareArguments(); virtual llvm::Type* prepareResult(); virtual llvm::Function::arg_iterator prepareBindings(); }; } // end of namespace `xreate::compilation` class CompilePass : public AbstractPass { friend class LateContextCompiler; friend class LateContextCompiler2; friend class compilation::BasicCodeScopeUnit; friend class compilation::FunctionUnit; public: -// compilation::Transformations* transformations; + compilation::TransformationsManager* managerTransformations; compilation::TargetInterpretation* targetInterpretation; CompilePass(PassManager* manager): AbstractPass(manager) {} compilation::FunctionUnit* getFunctionUnit(const ManagedFnPtr& function); void run() override; llvm::Function* getEntryFunction(); static void prepareQueries(ClaspLayer* clasp); private: //TODO free `functions` in destructor std::map functions; llvm::Function* entry = 0; ContextQuery* queryContext; }; } #endif // COMPILEPASS_H diff --git a/cpp/tests/loops.cpp b/cpp/tests/loops.cpp index efa66a5..be08250 100644 --- a/cpp/tests/loops.cpp +++ b/cpp/tests/loops.cpp @@ -1,59 +1,178 @@ #include "passmanager.h" #include "gtest/gtest.h" using namespace std; +TEST(Loop, SimpleLoop1){ + string code = +R"CODE( + main = function:: int; entry { + input = [1..5]:: [int]. + + loop fold(input->el::int, 0->sum)::int + { + sum + el + } + } + +)CODE"; + + xreate::PassManager* man = xreate::PassManager::prepareForCode(move(code)); + int (*funcMain)() = (int (*)()) man->run(); + + int answerActual = funcMain(); + ASSERT_EQ(15, answerActual); +} + TEST(Loop, Break1){ string code = R"CODE( main = function:: int; entry { - input = [0..10]:: [int]. + input = [1..10]:: [int]. - loop fold(input->el::int, 0->a)::[int] + loop fold(input->el::int, 0->sum)::int { - if (a>=5)::int { - 5:: int; break + if (sum>5)::int { + sum:: int; break - } else {a+el} + } else {sum+el} } } )CODE"; xreate::PassManager* man = xreate::PassManager::prepareForCode(move(code)); int (*funcMain)() = (int (*)()) man->run(); int answerActual = funcMain(); - ASSERT_EQ(5, answerActual); + ASSERT_EQ(6, answerActual); +} + +TEST(Loop, NestedLoopsSimple1){ + string code = +R"CODE( + main = function:: int; entry { + listX = [1..5]:: [int]. + loop fold(listX->x::int, 0->acc)::int + { + listY = [1..5]:: [int]. + + row = loop fold(listY->y::int, 1->acc):: int { + acc * ( y + x) + }. + + acc + row + } + } + +)CODE"; + + xreate::PassManager* man = xreate::PassManager::prepareForCode(move(code)); + int (*funcMain)() = (int (*)()) man->run(); + int answerActual = funcMain(); + + ASSERT_EQ(55320, answerActual); +} + +TEST(Loop, NestedLoopsBreak1){ + string code = +R"CODE( + main = function:: int; entry { + listX = [1..5]:: [int]. + loop fold(listX->x::int, 0->acc)::int + { + listY = [1..5]:: [int]. + row = loop fold(listY->y::int, 1->acc):: int { + res = acc * ( y + x) :: int. + + if (res > 20):: int { + 20:: int; break + + } else { + res + } + }. + + acc + row + } + } + +)CODE"; + + xreate::PassManager* man = xreate::PassManager::prepareForCode(move(code)); + int (*funcMain)() = (int (*)()) man->run(); + int answerActual = funcMain(); + + ASSERT_EQ(100, answerActual); +} + +TEST(Loop, NestedLoopsBreak2){ + string code = +R"CODE( + main = function:: int; entry { + listX = [1..3]:: [int]. + loop fold(listX->x::int, 0->acc)::int + { + listY = [1..5]:: [int]. + row = loop fold(listY->y::int, 1->acc):: int { + res = acc * y :: int. + + if (res > 24):: int { + 24:: int; break + + } else { + res + } + }. + + if (x==3)::int{ + acc:: int; break + + } else { + acc + row + } + } + } + +)CODE"; + + xreate::PassManager* man = xreate::PassManager::prepareForCode(move(code)); + int (*funcMain)() = (int (*)()) man->run(); + int answerActual = funcMain(); + + ASSERT_EQ(48, answerActual); } +//TEST nested loop breaks. +//TEST 2 breaks^ outer loop break, inner loop break + TEST(Loop, InfiniteLoop1){ string code = R"Code( fac = function(x:: int):: int{ range = [2..x] :: [int]. loop fold(range->i::int, 1->acc)::int { acc * i } } main = function:: int; entry { loop fold inf(2->state) :: int { if (fac(state)==120)::int { state::int; break } else {state + 1} } } )Code" ; xreate::PassManager* man = xreate::PassManager::prepareForCode(move(code)); int (*funcMain)() = (int (*)()) man->run(); int answerActual = funcMain(); ASSERT_EQ(5, answerActual); } \ No newline at end of file