diff --git a/config/default.json b/config/default.json index 7d84629..09f405f 100644 --- a/config/default.json +++ b/config/default.json @@ -1,75 +1,73 @@ { "containers": { "id": { - "implementations": "impl_fulfill_cluster", - "clusters": "var_cluster", - "prototypes": "proto_cluster", + "implementations": "containers_impl", "linkedlist": "linkedlist" }, "impl": { "solid": "solid", "onthefly": "on_the_fly" } }, "logging": { "id": "logging" }, "function-entry": "entry", "transcend": { "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": "virtualization", + "template": "troubleshooting", "templates": { - "current-fix":"*", - "default": "*-Adhoc.*:Containers.*:Compilation.full_IFStatementWithVariantType:Types.full_VariantType_Switch1:Context.full_LateContext:Context.pathDependentContext:CFA.testLoopContextExists", + "troubleshooting":"*", + "default": "*", "ast": "AST.*", "effects": "Effects.*", "basic": "Attachments.*", - "compilation": "Compilation.*-Compilation.full_IFStatementWithVariantType", + "compilation": "Compilation.*", "communication": "Communication.*", "cfa": "CFA.*", "containers": "Containers.*", "dfa": "DFA.*", "diagnostic": "Diagnostic.*", "dsl": "Association.*:Interpretation.*", "exploitation": "Exploitation.*", "ExpressionSerializer": "ExpressionSerializer.*", "externc": "InterfaceExternC.*", "loops": "Loop.*", - "latereasoning": "LateReasoning.Syntax1:LateReasoning.Pass_DFAPassDec_1", - "latex": "Latex.Compilation_TransitFn1", + "latereasoning": "LateReasoning.*", + "latex": "Latex.*", "modules": "Modules.*", "polymorphs": "Polymorphs.*", "intrinsic-query": "Types.SlaveTypes*:Association.TypedQuery*", "types": "Types.*", "virtualization": "Virtualization.*", "vendorsAPI/clang": "ClangAPI.*", "vendorsAPI/xml2": "libxml2*" } } } diff --git a/cpp/src/CMakeLists.txt b/cpp/src/CMakeLists.txt index f86a842..f9092a6 100644 --- a/cpp/src/CMakeLists.txt +++ b/cpp/src/CMakeLists.txt @@ -1,236 +1,236 @@ 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(STATUS "LLVM DEFS: " ${LLVM_DEFINITIONS}) execute_process( COMMAND llvm-config --libs OUTPUT_VARIABLE LLVM_LIBS OUTPUT_STRIP_TRAILING_WHITESPACE) message(STATUS "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}/../grammar/) set(COCO_SOURCE_FILES_MAIN ${COCO_GRAMMAR_PATH}/main/Parser.cpp ${COCO_GRAMMAR_PATH}/main/Scanner.cpp ) set(COCO_SOURCE_FILES_MODULES ${COCO_GRAMMAR_PATH}/modules/Parser.cpp ${COCO_GRAMMAR_PATH}/modules/Scanner.cpp ) set(COCO_SOURCE_FILES ${COCO_SOURCE_FILES_MODULES} ${COCO_SOURCE_FILES_MAIN}) INCLUDE_DIRECTORIES(${COCO_GRAMMAR_PATH}) add_custom_command(OUTPUT ${COCO_SOURCE_FILES_MAIN} COMMAND ${COCO_GRAMMAR_PATH}/gen-grammar main ${COCO_EXECUTABLE} ${COCO_FRAMES_PATH} WORKING_DIRECTORY ${COCO_GRAMMAR_PATH} MAIN_DEPENDENCY ${COCO_GRAMMAR_PATH}/xreate.ATG ) add_custom_command(OUTPUT ${COCO_SOURCE_FILES_MODULES} COMMAND ${COCO_GRAMMAR_PATH}/gen-grammar modules ${COCO_EXECUTABLE} ${COCO_FRAMES_PATH} WORKING_DIRECTORY ${COCO_GRAMMAR_PATH} MAIN_DEPENDENCY ${COCO_GRAMMAR_PATH}/modules.ATG ) message(STATUS "COCO GRAMMAR BUILD STATUS:" ${COCO_OUTPUT}) # XREATE #====================== set(SOURCE_FILES + analysis/DominatorsAnalysisProvider.cpp compilation/interpretation-instructions.cpp ExternLayer.cpp analysis/cfagraph.cpp compilation/latereasoning.cpp analysis/interpretation.cpp query/latex.cpp query/polymorph.cpp compilation/polymorph.cpp aux/latereasoning.cpp compilation/latex.cpp analysis/typeinference.cpp xreatemanager.cpp transcendlayer.cpp analysis/dfagraph.cpp - analysis/DominatorsTreeAnalysisProvider.cpp llvmlayer.cpp pass/compilepass.cpp analysis/utils.cpp pass/dfapass.cpp compilation/targetinterpretation.cpp pass/interpretationpass.cpp ast.cpp aux/xreatemanager-decorators.cpp compilation/operators.cpp compilation/transformations.cpp compilation/transformersaturation.cpp pass/versionspass.cpp attachments.cpp compilation/containers.cpp compilation/advancedinstructions.cpp utils.cpp pass/abstractpass.cpp pass/cfapass.cpp contextrule.cpp query/containers.cpp aux/serialization/expressionserializer.cpp modules.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 ${COCO_SOURCE_FILES} ${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 boost_system boost_filesystem ) #${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/analysis/DominatorsAnalysisProvider.cpp b/cpp/src/analysis/DominatorsAnalysisProvider.cpp new file mode 100644 index 0000000..69f4b71 --- /dev/null +++ b/cpp/src/analysis/DominatorsAnalysisProvider.cpp @@ -0,0 +1,274 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * File: DominatorsAnalysisProvider.cpp + * Author: pgess + * + * Created on May 13, 2016, 11:39 AM + */ + +/** + * \file DominatorsAnalysisProvider.h + * \brief Dominators Tree analysis + */ + +#include "analysis/cfagraph.h" +#include "analysis/DominatorsAnalysisProvider.h" + +#include "llvm/ADT/GraphTraits.h" +#include "llvm/Support/GenericDomTreeConstruction.h" +#include "llvm/Support/GenericDomTree.h" + +#include +#include +#include + +using namespace std; +using namespace xreate; +using namespace boost; +using namespace boost::bimaps; + +namespace xreate { namespace dominators { + +struct CFAGraphAdapter; + +struct ScopeNode { + ScopePacked id; + CFAGraphAdapter* parent; + std::list nodesFrom; + std::list nodesTo; + + CFAGraphAdapter* getParent(){ return parent; } + void printAsOperand(llvm::raw_ostream&, bool) {} + ScopeNode(ScopePacked scope, CFAGraphAdapter* parentAdapter): + id(scope), parent(parentAdapter) {} +}; + +} +} //end of namespace xreate::dominators + +namespace llvm { +using namespace xreate::dominators; + +template<> +struct GraphTraits { + typedef ScopeNode* NodeRef; + typedef std::list::iterator ChildIteratorType; + + static ChildIteratorType + child_begin(ScopeNode* node) { + return node->nodesTo.begin(); + } + + static ChildIteratorType + child_end(ScopeNode* node) { + return node->nodesTo.end(); + } +}; + +template<> +struct GraphTraits> +{ + typedef ScopeNode* NodeRef; + typedef std::list::iterator ChildIteratorType; + + static ChildIteratorType + child_begin(ScopeNode* node) { + return node->nodesFrom.begin(); + } + + static ChildIteratorType + child_end(ScopeNode* node) { + return node->nodesFrom.end(); + } +}; + +template<> +struct GraphTraits { + typedef std::list::iterator nodes_iterator; + + static nodes_iterator + nodes_begin(CFAGraphAdapter* graph) { + return graph->nodes.begin(); + } + + static nodes_iterator + nodes_end(CFAGraphAdapter* graph) { + return graph->nodes.end(); + } + + static ScopeNode* + getEntryNode(CFAGraphAdapter* F) { + return F->nodeRoot; + } + + static unsigned int + size(CFAGraphAdapter* graph) { + return graph->nodes.size(); + } +}; +} + +namespace xreate { +namespace dominators { + +class DominatorTree : public llvm::DominatorTreeBase { +friend class DominatorsAnalysisProvider; +public: + DominatorTree() : llvm::DominatorTreeBase() {} + + void + run(CFAGraphAdapter& program) { + recalculate(program); + updateDFSNumbers(); + + //extract dominators info + for(auto& entry : DomTreeNodes) { + if(!entry.getFirst()) continue; + + dominators.emplace(entry.getFirst()->id, make_pair(entry.getSecond()->getDFSNumIn(), entry.getSecond()->getDFSNumOut())); + } + } + + void + print(std::ostringstream& output, const std::string& atom) const { + boost::format formatAtom(atom+"(%1%, range(%2%, %3%))."); + + for(auto entry : dominators) { + output< { +friend class DominatorsAnalysisProvider; +public: + PostDominatorTree() : llvm::DominatorTreeBase() {} + + void + run(CFAGraphAdapter& program) { + recalculate(program); + updateDFSNumbers(); + //extract dominators info + for(auto& entry : DomTreeNodes) { + if(!entry.getFirst()) continue; + + dominators.emplace(entry.getFirst()->id, make_pair(entry.getSecond()->getDFSNumIn(), entry.getSecond()->getDFSNumOut())); + } + } + + void + print(std::ostringstream& output, const std::string& atom) const { + boost::format formatAtom(atom+"(%1%, range(%2%, %3%))."); + + for(auto entry : dominators) { + output<id < b->id;}; + auto posLowerBound = std::lower_bound(nodes.begin(), nodes.end(), &elemNew, fnComp); + + if(posLowerBound==nodes.end()|| (*posLowerBound)->id > scope){ + ScopeNode* elemNewP = new ScopeNode(elemNew); + *elemNewP = elemNew; + return *nodes.insert(posLowerBound, elemNewP); + } + + return *posLowerBound; +} + +CFAGraphAdapter* +CFAGraphAdapter::build(const cfa::CFAGraph* graph) { + return build(graph->__dependencyRelations); +} + +CFAGraphAdapter* +CFAGraphAdapter::build(const std::multimap& dataScopesOrder){ + CFAGraphAdapter* tree=new CFAGraphAdapter(); + + enum NODE_MARK{NO_ROOT, POSSIBLE_ROOT}; + std::unordered_map nodeMarks; + for (const auto& edge: dataScopesOrder){ + + ScopeNode* nodeTo = tree->registerScope(edge.first); + ScopeNode* nodeFrom = tree->registerScope(edge.second); + nodeTo->nodesFrom.push_back(nodeFrom); + nodeFrom->nodesTo.push_back(nodeTo); + + nodeMarks.emplace(edge.second, POSSIBLE_ROOT); //weak optional insert + auto result = nodeMarks.emplace(edge.first, NO_ROOT); //strong insert or update + if(!result.second){ + result.first->second = NO_ROOT; + } + } + + std::list nodeRoots; + for(auto nodeMark: nodeMarks){ + if(nodeMark.second == POSSIBLE_ROOT) nodeRoots.push_back(nodeMark.first); + } + + if(nodeRoots.size()>1){ + ScopeNode* nodeGlobalRoot = tree->registerScope(SCOPE_ABSTRACT_GLOBAL); + for(auto rootLocal: nodeRoots){ + ScopeNode* nodeLocalRoot = tree->registerScope(rootLocal); + nodeLocalRoot->nodesFrom.push_back(nodeGlobalRoot); + nodeGlobalRoot->nodesTo.push_back(nodeLocalRoot); + } + + tree->nodeRoot = nodeGlobalRoot; + + } else if (nodeRoots.size()==1){ + tree->nodeRoot = tree->registerScope(nodeRoots.front()); + + } else { + ScopeNode* nodeGlobalRoot = tree->registerScope(SCOPE_ABSTRACT_GLOBAL); + tree->nodeRoot = nodeGlobalRoot; + } + + return tree; +} + +void +DominatorsAnalysisProvider::run(CFAGraphAdapter* program) { + treeForwardDominators.reset(new DominatorTree()); + treePostDominators.reset(new PostDominatorTree()); + + treeForwardDominators->run(*program); + treePostDominators->run(*program); +} + +void +DominatorsAnalysisProvider::print(std::ostringstream& output) const { + treeForwardDominators->print(output, "cfa_forwdom"); + treePostDominators->print(output, "cfa_postdom"); +} + +const DominatorsAnalysisProvider::Dominators& +DominatorsAnalysisProvider::getForwardDominators() const { + return treeForwardDominators->dominators; +} + +const DominatorsAnalysisProvider::Dominators& +DominatorsAnalysisProvider::getPostDominators() const { + return treePostDominators->dominators; +} + +DominatorsAnalysisProvider::DominatorsAnalysisProvider() {} +DominatorsAnalysisProvider::~DominatorsAnalysisProvider() { } + + +}} //end of namespace xreate::dominators diff --git a/cpp/src/analysis/DominatorsAnalysisProvider.h b/cpp/src/analysis/DominatorsAnalysisProvider.h new file mode 100644 index 0000000..a7124cc --- /dev/null +++ b/cpp/src/analysis/DominatorsAnalysisProvider.h @@ -0,0 +1,56 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * File: DominatorsAnalysisProvider.h + * Author: pgess + * + * Created on May 13, 2016, 11:39 AM + */ + +#ifndef DominatorsAnalysisProvider_H +#define DominatorsAnalysisProvider_H + +#include "transcendlayer.h" +#include + +namespace xreate{namespace dominators{ + +class DominatorTree; +class PostDominatorTree; +class ScopeNode; + +struct CFAGraphAdapter { + std::list nodes; + ScopeNode* nodeRoot; + + ScopeNode* registerScope(ScopePacked scope); + static CFAGraphAdapter* build(const cfa::CFAGraph* graph); + static CFAGraphAdapter* build(const std::multimap& dataScopesOrder); + CFAGraphAdapter() { } +}; + +/** \brief Dominators Analysis report */ +class DominatorsAnalysisProvider: public IAnalysisReport { +public: + typedef std::pair DominatedRange; + typedef std::map Dominators; + + DominatorsAnalysisProvider(); + virtual ~DominatorsAnalysisProvider(); + + void run(CFAGraphAdapter* program); + void print(std::ostringstream& output) const override; + + const Dominators& getForwardDominators() const; + const Dominators& getPostDominators() const; + +private: + boost::shared_ptr treeForwardDominators; + boost::shared_ptr treePostDominators; +}; + +}} //end of namespace xreate::dominators + +#endif /* DominatorsAnalysisProvider_H */ + diff --git a/cpp/src/analysis/DominatorsTreeAnalysisProvider.cpp b/cpp/src/analysis/DominatorsTreeAnalysisProvider.cpp deleted file mode 100644 index 93d52bd..0000000 --- a/cpp/src/analysis/DominatorsTreeAnalysisProvider.cpp +++ /dev/null @@ -1,275 +0,0 @@ -/* This Source Code Form is subject to the terms of the Mozilla Public - * License, v. 2.0. If a copy of the MPL was not distributed with this - * file, You can obtain one at http://mozilla.org/MPL/2.0/. - * - * File: DominatorsTreeAnalysisProvider.cpp - * Author: pgess - * - * Created on May 13, 2016, 11:39 AM - */ - -/** - * \file DominatorsTreeAnalysisProvider.h - * \brief Dominators Tree analysis - */ - -#include "analysis/cfagraph.h" -#include "analysis/DominatorsTreeAnalysisProvider.h" - -#include "llvm/ADT/GraphTraits.h" -#include "llvm/Support/GenericDomTreeConstruction.h" -#include "llvm/Support/GenericDomTree.h" - -#include -#include -#include - -using namespace std; -using namespace xreate; -using namespace boost; -using namespace boost::bimaps; - -namespace xreate { namespace dominators { - -struct CFAGraphAdapter; - -//struct ScopeNode { -// ScopePacked id; -// std::list nodesFrom; -// std::list nodesTo; -//}; -// -//struct CFAGraphAdapter { -// std::list nodes; -// ScopeNode* nodeRoot; -// -// ScopeNode* getOrCreateNode(ScopePacked id){ -// ScopeNode elemNew; elemNew.id = id; -// auto fnComp = [](const ScopeNode &a, const ScopeNode &b){return a.id < b.id;}; -// auto posLowerBound = std::lower_bound(nodes.begin(), nodes.end(), elemNew, fnComp); -// -// if(posLowerBound==nodes.end()|| posLowerBound->id > id){ -// return &*nodes.insert(posLowerBound, elemNew); -// } -// -// return &*posLowerBound; -// } -// -// static CFAGraphAdapter* build(const cfa::CFAGraph* graph) { -// CFAGraphAdapter* tree=new CFAGraphAdapter(); -// -// enum NODE_MARK{NO_ROOT, POSSIBLE_ROOT}; -// std::unordered_map nodeMarks; -// for (const auto& edge: graph->__dependencyRelations){ -// -// ScopeNode* nodeTo = tree->getOrCreateNode(edge.first); -// ScopeNode* nodeFrom = tree->getOrCreateNode(edge.second); -// nodeTo->nodesFrom.push_back(nodeFrom); -// nodeFrom->nodesTo.push_back(nodeTo); -// -// nodeMarks.emplace(edge.second, POSSIBLE_ROOT); //weak optional insert -// auto result = nodeMarks.emplace(edge.first, NO_ROOT); //strong insert or update -// if(!result.second){ -// result.first->second = NO_ROOT; -// } -// } -// -// std::list nodeRoots; -// for(auto nodeMark: nodeMarks){ -// if(nodeMark.second == POSSIBLE_ROOT) nodeRoots.push_back(nodeMark.first); -// } -// -// if(nodeRoots.size()>1){ -// ScopeNode* nodeGlobalRoot = tree->getOrCreateNode(SCOPE_ABSTRACT_GLOBAL); -// for(auto rootLocal: nodeRoots){ -// ScopeNode* nodeLocalRoot = tree->getOrCreateNode(rootLocal); -// nodeLocalRoot->nodesFrom.push_back(nodeGlobalRoot); -// nodeGlobalRoot->nodesTo.push_back(nodeLocalRoot); -// } -// -// } else if (nodeRoots.size()==1){ -// tree->nodeRoot = tree->getOrCreateNode(nodeRoots.front()); -// -// } else { -// ScopeNode* nodeGlobalRoot = tree->getOrCreateNode(SCOPE_ABSTRACT_GLOBAL); -// tree->nodeRoot = nodeGlobalRoot; -// } -// -// return tree; -// } -// -// CFAGraphAdapter() { } -//}; -//} -//} //end of namespace xreate::dominators -// -//namespace llvm { -//using namespace xreate::dominators; -// -//template<> -//struct GraphTraits { -// typedef ScopeNode NodeType; -// typedef std::list::iterator ChildIteratorType; -// -// static ChildIteratorType -// child_begin(NodeType* node) { -// return node->nodesTo.begin(); -// } -// -// static ChildIteratorType -// child_end(NodeType* node) { -// return node->nodesTo.end(); -// } -//}; -// -//template<> -//struct GraphTraits : public GraphTraits { -// typedef std::list::iterator nodes_iterator; -// -// static nodes_iterator -// nodes_begin(CFAGraphAdapter* graph) { -// return graph->nodes.begin(); -// } -// -// static nodes_iterator -// nodes_end(CFAGraphAdapter* graph) { -// return graph->nodes.end(); -// } -// -// static NodeType* -// getEntryNode(CFAGraphAdapter* F) { -// return F->nodeRoot; -// } -// -// static unsigned int -// size(CFAGraphAdapter* graph) { -// return graph->nodes.size(); -// } -//}; -// -// -//template<> -//struct GraphTraits> -//{ -// typedef ScopeNode NodeType; -// typedef std::list::iterator ChildIteratorType; -// -// static ChildIteratorType -// child_begin(NodeType* node) { -// return node->nodesFrom.begin(); -// } -// -// static ChildIteratorType -// child_end(NodeType* node) { -// return node->nodesFrom.end(); -// } -//}; -//} -// -//namespace xreate { -//namespace dominators { -// -//class DominatorTree : public llvm::DominatorTreeBase { -//public: -// DominatorTree() : llvm::DominatorTreeBase() {} -// -// void -// run(CFAGraphAdapter& program) { -// recalculate(program); -// -// //extract dominators info -// for(auto& entry : DomTreeNodes) { -// if(!entry.getFirst()) continue; -// -// dominators.emplace(entry.getFirst()->id, make_pair(entry.getSecond()->getDFSNumIn(), entry.getSecond()->getDFSNumOut())); -// } -// } -// -// void -// print(std::ostringstream& output, const std::string& atom) const { -// boost::format formatAtom(atom+"(%1%, range(%2%, %3%))."); -// -// for(auto entry : dominators) { -// output< { -//public: -// PostDominatorTree() : llvm::DominatorTreeBase() {} -// -// void -// run(CFAGraphAdapter& program) { -// recalculate(program); -// -// //extract dominators info -// for(auto& entry : DomTreeNodes) { -// if(!entry.getFirst()) continue; -// -// dominators.emplace(entry.getFirst()->id, make_pair(entry.getSecond()->getDFSNumIn(), entry.getSecond()->getDFSNumOut())); -// } -// } -// -// void -// print(std::ostringstream& output, const std::string& atom) const { -// boost::format formatAtom(atom+"(%1%, range(%2%, %3%))."); -// -// for(auto entry : dominators) { -// output< treeForwardDominators; -// boost::scoped_ptr treePostDominators; -}; - - -void -DominatorsTreeAnalysisProvider::run(const cfa::CFAGraph* graph) { -// boost::scoped_ptr program(CFAGraphAdapter::build(graph)); -// -// treeForwardDominators->run(*program); -// treePostDominators->run(*program); -} - -void -DominatorsTreeAnalysisProvider::print(std::ostringstream& output) const { -// treeForwardDominators->print(output, "cfa_forwdom"); -// treePostDominators->print(output, "cfa_postdom"); -} - -const DominatorsTreeAnalysisProvider::Dominators& -DominatorsTreeAnalysisProvider::getForwardDominators() const { - //return treeForwardDominators->dominators; -} - -const DominatorsTreeAnalysisProvider::Dominators& -DominatorsTreeAnalysisProvider::getPostDominators() const { - // return treePostDominators->dominators; -} - -DominatorsTreeAnalysisProvider::DominatorsTreeAnalysisProvider() - : __private(new DominatorsProviderPrivate()) {} - -DominatorsTreeAnalysisProvider::~DominatorsTreeAnalysisProvider() { } - - -}} //end of namespace xreate::dominators \ No newline at end of file diff --git a/cpp/src/analysis/DominatorsTreeAnalysisProvider.h b/cpp/src/analysis/DominatorsTreeAnalysisProvider.h deleted file mode 100644 index f3b2aee..0000000 --- a/cpp/src/analysis/DominatorsTreeAnalysisProvider.h +++ /dev/null @@ -1,43 +0,0 @@ -/* This Source Code Form is subject to the terms of the Mozilla Public - * License, v. 2.0. If a copy of the MPL was not distributed with this - * file, You can obtain one at http://mozilla.org/MPL/2.0/. - * - * File: DominatorsTreeAnalysisProvider.h - * Author: pgess - * - * Created on May 13, 2016, 11:39 AM - */ - -#ifndef DOMINATORSTREEANALYSISPROVIDER_H -#define DOMINATORSTREEANALYSISPROVIDER_H - -#include "transcendlayer.h" -#include - -namespace xreate{namespace dominators{ - -class DominatorsProviderPrivate; - -/** \brief Dominators Analysis report */ -class DominatorsTreeAnalysisProvider: public IAnalysisReport { -public: - typedef std::pair DominatedRange; - typedef std::map Dominators; - - DominatorsTreeAnalysisProvider(); - virtual ~DominatorsTreeAnalysisProvider(); - - void run(const cfa::CFAGraph* graph); - void print(std::ostringstream& output) const override; - - const Dominators& getForwardDominators() const; - const Dominators& getPostDominators() const; - -private: - std::unique_ptr __private; -}; - -}} //end of namespace xreate::dominators - -#endif /* DOMINATORSTREEANALYSISPROVIDER_H */ - diff --git a/cpp/src/analysis/dfagraph.cpp b/cpp/src/analysis/dfagraph.cpp index ef28ec9..ee076b6 100644 --- a/cpp/src/analysis/dfagraph.cpp +++ b/cpp/src/analysis/dfagraph.cpp @@ -1,218 +1,244 @@ /* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. * * File: DFAGraph.h * Author: pgess * */ /** * \file dfagraph.h * \brief Data Flow Analysis(DFA) graph data * */ #include "analysis/dfagraph.h" #include "analysis/utils.h" using namespace std; using namespace xreate::analysis; namespace xreate { namespace dfa { void DFACallInstance::print(std::ostringstream& output) const{ boost::format formatArgs; boost::format formatInstance("dfa_callfn(%1%, %2%)."); switch (type) { case WEAK: formatArgs = boost::format("weak(dfa_callargs(%1%, %2%, %3%))."); break; case STRONG: formatArgs = boost::format("weak(dfa_callargs(%1%, %2%, %3%)).\ndfa_callargs(%1%, %2%, %3%)."); break; } output << formatInstance % analysis::writeSymbolNode(retActual) % fnName << endl; for(std::pair rec: args) { SymbolNode argFormal(rec.first); output << formatArgs % analysis::writeSymbolNode(retActual) % analysis::writeSymbolNode(argFormal) % analysis::writeSymbolNode(rec.second) << endl; } } void DFAGraph::addDependency(const SymbolNode& node, const SymbolNode& subnode){ __dependencies.emplace(node, subnode); if (boost::get(&node)){ __usedSymbols.insert(node); } if (boost::get(&subnode)){ __usedSymbols.insert(node); } } void DFAGraph::printDependencies(std::ostringstream& output) const{ for(const SymbolNode& root: __roots){ printDependency(output, root, root); } } void DFAGraph::printDependency(std::ostringstream& output, const SymbolNode& nodeCurrent, const SymbolNode& nodeDependent) const { auto range = __dependencies.equal_range(nodeCurrent); for (auto it = range.first; it != range.second; ++it){ if (boost::get(&it->second)){ if (!__usedSymbols.count(it->second)){ printDependency(output, it->second, nodeDependent); continue; } } boost::format formatDependency("dfa_depends(%1%, %2%)."); output << formatDependency % analysis::writeSymbolNode(nodeDependent) % analysis::writeSymbolNode(it->second) << endl; printDependency(output, it->second, it->second); } } void DFAGraph::printInplaceAnnotation(const SymbolNode& node, const Expression& expression) { // write down in-place expression tags: boost::format formatBind("bind(%1%, %2%)."); __usedSymbols.insert(node); for (const string& tag: xreate::analysis::compile(expression)) { __output << formatBind % analysis::writeSymbolNode(node) % tag << endl; } } void DFAGraph::printLateAnnotation(const SymbolNode& node, const Expression& expression, const std::list& symbols, const std::list& domains){ boost::format formatLateAnnotation("late(%1%, (%2%), (%3%), %4%):- %5%."); boost::format formatDom("%1%(%2%)"); std::list exprSerialized = xreate::analysis::compile(expression); assert(exprSerialized.size() == 1); list identSymbols, identNames, domainsSerialised; auto domainI = domains.begin(); for(auto symbol: symbols){ identSymbols.push_back(analysis::writeSymbolNode(symbol.second).str()); identNames.push_back(symbol.first); domainsSerialised.push_back((formatDom % *domainI % symbol.first).str()); ++domainI; } __output << formatLateAnnotation % analysis::writeSymbolNode(node) % boost::algorithm::join(identSymbols, ", ") % boost::algorithm::join(identNames, ", ") % exprSerialized.front() % boost::algorithm::join(domainsSerialised, "; ") << endl; } void DFAGraph::printAlias(const SymbolNode& symbFormal, const SymbolNode& symbActual){ __usedSymbols.insert(symbFormal); __usedSymbols.insert(symbActual); boost::format formatAlias("dfa_alias(%1%, %2%)."); __output << formatAlias % analysis::writeSymbolNode(symbFormal) % analysis::writeSymbolNode(symbActual) << endl; } void DFAGraph::printWeakAlias(const SymbolNode& symbFormal, const SymbolNode& symbActual){ __usedSymbols.insert(symbFormal); __usedSymbols.insert(symbActual); boost::format formatAlias("weak(dfa_alias(%1%, %2%))."); __output << formatAlias % analysis::writeSymbolNode(symbFormal) % analysis::writeSymbolNode(symbActual) << endl; } void DFAGraph::printFunctionRet(ManagedFnPtr function, const SymbolNode& symbolRet){ boost::format formatRet("dfa_fnret(%1%, %2%)."); __usedSymbols.insert(symbolRet); __output << formatRet % function->getName() % analysis::writeSymbolNode(symbolRet) << endl; __roots.insert(symbolRet); } void DFAGraph::addCallInstance(DFACallInstance&& instance){ __usedSymbols.insert(instance.retActual); for(const auto arg: instance.args){ __usedSymbols.insert(SymbolNode(arg.first)); __usedSymbols.insert(arg.second); } __callInstances.push_back(std::move(instance)); } void DFAGraph::print(std::ostringstream& output) const{ output << endl << "%\t\tStatic analysis: DFA" << endl; //Dependencies printDependencies(output); //Add generated report output << __output.str() << endl; //Call instances for(const DFACallInstance& instance: __callInstances){ instance.print(output); } output << endl; } void DFAGraph::printSymbols(TranscendLayer* transcend){ boost::format formatHint("shint(%1%, \"%2%\")."); for (const SymbolNode& node : __usedSymbols) { __output << "v(" << analysis::writeSymbolNode(node) << "). "; if (const SymbolPacked* symbol = boost::get(&node)){ __output << formatHint % analysis::writeSymbolNode(node) % transcend->getHintForPackedSymbol(*symbol); } __output << endl; } } +void +DFAGraph::printOperator(Operator op, std::list&& operands, int dataOpListSize){ + std::string opStr; + switch(op){ + case Operator::MAP: opStr = "map"; break; + case Operator::FOLD: opStr = "fold"; break; + case Operator::LIST: opStr = "list"; break; + case Operator::LIST_RANGE: opStr = "list_range"; break; + case Operator::INDEX: opStr = "index"; break; + default: assert(false); + } + + std::ostringstream bufOperands; + for(const SymbolNode& operand: operands){ + __usedSymbols.insert(operand); + bufOperands << analysis::writeSymbolNode(operand) << ", "; + } + + if(op == Operator::LIST){ + bufOperands << dataOpListSize << ", "; + } + + boost::format formatOperator("ast_op_%1%(%2%)."); + __output << (formatOperator % opStr % bufOperands.str().substr(0, bufOperands.str().size() - 2)) << endl; +} + }} //end of namespace xreate::dfa diff --git a/cpp/src/analysis/dfagraph.h b/cpp/src/analysis/dfagraph.h index 00ccb67..dfe1859 100644 --- a/cpp/src/analysis/dfagraph.h +++ b/cpp/src/analysis/dfagraph.h @@ -1,65 +1,66 @@ /* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. * * File: dfa.h * Author: pgess * * Created on June 27, 2016, 1:50 PM */ #ifndef DFA_H #define DFA_H #include "transcendlayer.h" #include namespace xreate { namespace latereasoning { typedef std::pair LateSymbolRecognized; }} namespace xreate {namespace dfa { enum DFACallInstanceType { STRONG, WEAK }; class DFACallInstance { public: std::string fnName; std::vector> args; SymbolNode retActual; DFACallInstanceType type; void print(std::ostringstream& output) const; }; /** \brief Holds DFA Analysis report produced by DFAPass */ class DFAGraph : public IAnalysisReport { public: // DFAGraph(TranscendLayer* engine): __transcend(engine){} virtual void print(std::ostringstream& output) const override; void addCallInstance(DFACallInstance && instance); void addDependency(const SymbolNode& node, const SymbolNode& subnodeBlock); void printInplaceAnnotation(const SymbolNode& node, const Expression& expression); void printLateAnnotation(const SymbolNode& node, const Expression& expression, const std::list& symbols, const std::list& domains); void printAlias(const SymbolNode& symbFormal, const SymbolNode& symbActual); void printWeakAlias(const SymbolNode& symbFormal, const SymbolNode& symbActual); void printFunctionRet(ManagedFnPtr function, const SymbolNode& symbolRet); void printDependencies(std::ostringstream& output) const; void printSymbols(TranscendLayer* transcend); + void printOperator(Operator, std::list&& operands, int dataOpListSize = 0); private: mutable std::ostringstream __output; std::list __callInstances; std::unordered_multimap __dependencies; std::unordered_set __usedSymbols; std::unordered_set __roots; void printDependency(std::ostringstream& output, const SymbolNode& nodeCurrent, const SymbolNode& nodeDependent) const; }; }} // end of namespace xreate::dfa #endif /* DFA_H */ diff --git a/cpp/src/analysis/interpretation.cpp b/cpp/src/analysis/interpretation.cpp index 79e2bf8..f46027d 100644 --- a/cpp/src/analysis/interpretation.cpp +++ b/cpp/src/analysis/interpretation.cpp @@ -1,273 +1,274 @@ /* * This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ /* * Author: pgess * Created on June 25, 2018, 3:25 PM * * \file interpretation.cpp * \brief interpretation */ #include "analysis/interpretation.h" using namespace std; namespace xreate{ namespace interpretation{ typedef vector InstancePacked; std::list generateAllInstancesInDomain2(const ExpandedType& domainT) { if(!domainT->isValid()) { return {Expression()}; } assert(domainT->__operator == TypeOperator::VARIANT); std::list results; int variantId = -1; bool flagDomainStateless = std::all_of(domainT->__operands.begin(), domainT->__operands.end(), [](const TypeAnnotation & subdomainT) { return !subdomainT.isValid(); }); for(const TypeAnnotation& subdomainT : domainT->__operands) { ++variantId; if(flagDomainStateless) { Expression result(Operator::VARIANT,{}); result.setValueDouble(variantId); results.push_back(result); continue; } std::list subresults = generateAllInstancesInDomain2(ExpandedType(subdomainT)); for (const Expression& subresult : subresults) { Expression result(Operator::VARIANT,{}); result.setValueDouble(variantId); result.operands.push_back(subresult); results.push_back(result); } } return results; } TypeAnnotation collapseFnGroup(const std::list& symbols) { Gringo::Symbol symbolAny = symbols.front(); size_t operandsCount = symbolAny.args().size; TypeAnnotation resultT; resultT.__operands.reserve(operandsCount); for(size_t operandId = 0; operandId < operandsCount; ++operandId) { std::list column; for(const Gringo::Symbol& row : symbols) { column.push_back(row.args()[operandId]); } TypeAnnotation operandT = collapseColumn(column); resultT.__operands.push_back(operandT); } if(resultT.__operands.size() == 1) { return resultT.__operands.front(); } if(resultT.__operands.size() > 1) { resultT.__operator = TypeOperator::LIST_NAMED; return resultT; } return resultT; } TypeAnnotation collapseColumn(const std::list& symbols) { TypeAnnotation resultT; if(!symbols.size()) return resultT; Gringo::Symbol symbolAny = symbols.front(); switch(symbolAny.type()) { case Gringo::SymbolType::Num: { return TypeAnnotation(TypePrimitive::Num); } case Gringo::SymbolType::Str: { return TypeAnnotation(TypePrimitive::String); } case Gringo::SymbolType::Fun: { map> fnGroups; for(const Gringo::Symbol& row : symbols) { fnGroups[row.name().c_str()].push_back(row); } TypeAnnotation resultT; resultT.__operands.reserve(fnGroups.size()); resultT.bindings.reserve(fnGroups.size()); for(const auto& group : fnGroups) { if(!group.second.size()) continue; TypeAnnotation variantT = collapseFnGroup(group.second); Gringo::Symbol symbolAny = group.second.front(); string variantName = symbolAny.name().c_str(); resultT.fields.push_back(variantName); resultT.__operands.push_back(variantT); } resultT.__operator = TypeOperator::VARIANT; // if(resultT.__operands.size() == 1) { // return resultT.__operands.front(); // } return resultT; } case Gringo::SymbolType::Inf: case Gringo::SymbolType::Special: case Gringo::SymbolType::Sup: { break; } } assert(false); return TypeAnnotation(); } ExpandedType dereferenceSlaveType(ExpandedType t, const TranscendLayer* transcend) { assert(t->__operator == TypeOperator::SLAVE); const string& domain = t->__valueCustom; StaticModel model = transcend->query(domain); if(!model.size()) return ExpandedType(TypeAnnotation()); std::list symbols; for(auto row : model) { symbols.push_back(row.second); } return ExpandedType(collapseFnGroup(symbols)); } Expression representTransExpression(const Gringo::Symbol& atom, ExpandedType schemaT, TranscendLayer* transcend) { + atom.print(std::cout); std::cout<__operator) { case TypeOperator::NONE: { switch(schemaT->__value) { case TypePrimitive::I8: case TypePrimitive::I32: case TypePrimitive::I64: case TypePrimitive::Num: case TypePrimitive::Int: { return Expression(Atom(atom.num())); } case TypePrimitive::String: { return Expression(Atom(atom.string().c_str())); } case TypePrimitive::Invalid: case TypePrimitive::Bool: case TypePrimitive::Float: { assert(false); return Expression(); } } break; } case TypeOperator::SLAVE: { ExpandedType contentT = dereferenceSlaveType(schemaT, transcend); return representTransExpression(atom, contentT, transcend); } case TypeOperator::VARIANT: { map dictVariants; for(size_t variantId = 0; variantId < schemaT->fields.size(); ++variantId) { dictVariants.emplace(schemaT->fields.at(variantId), variantId); } string predicateName = atom.name().c_str(); assert(dictVariants.count(predicateName)); size_t predicateId = dictVariants.at(predicateName); Expression result(Operator::VARIANT,{}); result.op = Operator::VARIANT; result.setValueDouble(predicateId); if(!schemaT->__operands.size()) return result; ExpandedType contentT = schemaT->__operands.at(predicateId).__operator == TypeOperator::SLAVE ? dereferenceSlaveType(ExpandedType(schemaT->__operands.at(predicateId)), transcend) : ExpandedType(schemaT->__operands.at(predicateId)); //edge case, content's type is LIST_NAMED: if (contentT->__operator == TypeOperator::LIST_NAMED) { result.operands.push_back(representTransExpression(atom, contentT, transcend)); } else if(!contentT->isValid()) { return result; } else { assert(atom.args().size); result.operands.push_back(representTransExpression(atom.args()[0], contentT, transcend)); } return result; } case TypeOperator::LIST_NAMED: { const Gringo::SymSpan& operandsRaw = atom.args(); size_t opCount = operandsRaw.size; assert(opCount == schemaT->__operands.size()); size_t operandId = 0; std::vector operands; operands.reserve(opCount); for(const TypeAnnotation operandT : schemaT->__operands) { operands.push_back(representTransExpression(operandsRaw[operandId], ExpandedType(operandT), transcend)); ++operandId; } Expression result(Operator::LIST_NAMED,{}); result.operands = operands; result.type = schemaT; return result; } case TypeOperator::LIST: case TypeOperator::CALL: case TypeOperator::CUSTOM: case TypeOperator::ACCESS: case TypeOperator::LINK: { assert(false); return Expression(); } } assert(false); return Expression(); } } -} //end of xreate namespace \ No newline at end of file +} //end of xreate namespace diff --git a/cpp/src/compilation/advancedinstructions.cpp b/cpp/src/compilation/advancedinstructions.cpp index 3fca3d7..1409e5e 100644 --- a/cpp/src/compilation/advancedinstructions.cpp +++ b/cpp/src/compilation/advancedinstructions.cpp @@ -1,459 +1,470 @@ /* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. * * File: InstructionsAdvanced.cpp * Author: pgess * * Created on June 26, 2016, 6:00 PM */ /** * \file advanced.h * \brief Compilation of statements that require more than one LLVM instruction */ +#include "analysis/typeinference.h" #include "compilation/advancedinstructions.h" #include "compilation/containers.h" #include "compilation/transformersaturation.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::ICodeScopeUnit* scope = context.scope; \ compilation::IFunctionUnit* function = context.function; AdvancedInstructions::AdvancedInstructions(compilation::Context ctx) : context(ctx), tyNum(static_cast (ctx.pass->man->llvm->toLLVMType(ExpandedType(TypeAnnotation(TypePrimitive::Num))))) { } llvm::Value* AdvancedInstructions::compileMapSolidOutput(const Expression &expr, const std::string hintRetVar) { EXPAND_CONTEXT UNUSED(scope); //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->llvmContext, "loop", function->raw); llvm::BasicBlock *blockBeforeLoop = builder.GetInsertBlock(); llvm::BasicBlock *blockAfterLoop = llvm::BasicBlock::Create(llvm->llvmContext, "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::ICodeScopeUnit* 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, builder.GetInsertBlock()); //next iteration checks: Value* condAfter = builder.CreateICmpSLE(stateLoopNext, rangeTo); builder.CreateCondBr(condAfter, blockLoop, blockAfterLoop); //finalization: builder.SetInsertPoint(blockAfterLoop); return dataOut; } Value* AdvancedInstructions::compileArrayIndex(llvm::Value* aggregate, std::vector indexes, std::string hintRetVar) { EXPAND_CONTEXT UNUSED(function); UNUSED(scope); 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* AdvancedInstructions::compileStructIndex(llvm::Value* aggregate, const ExpandedType& t, const std::string& idx) { EXPAND_CONTEXT UNUSED(scope); UNUSED(function); TypeUtils types(llvm); std::vector&& fields = types.getStructFields(t); for (unsigned i = 0, size = fields.size(); i < size; ++i) { if (fields.at(i) == idx) { //dereference pointer if (types.isPointer(t)) { llvm::Value* addr = llvm->builder.CreateConstGEP2_32(nullptr, aggregate, 0, i); return llvm->builder.CreateLoad(addr); } return llvm->builder.CreateExtractValue(aggregate, llvm::ArrayRef{i}); } } assert(false && "not found required struct field"); return nullptr; } llvm::Value* AdvancedInstructions::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]; llvm::BasicBlock *blockBeforeLoop = llvm->builder.GetInsertBlock(); std::unique_ptr transformerSaturation(new TransformerSaturation(blockBeforeLoop, context.pass->managerTransformations)); llvm::BasicBlock *blockLoop = llvm::BasicBlock::Create(llvm->llvmContext, "fold", function->raw); llvm::BasicBlock *blockLoopBody = llvm::BasicBlock::Create(llvm->llvmContext, "fold_body", function->raw); llvm::BasicBlock *blockAfterLoop = llvm::BasicBlock::Create(llvm->llvmContext, "fold_after", function->raw); llvm::BasicBlock *blockNext = llvm::BasicBlock::Create(llvm->llvmContext, "fold_next", function->raw); llvm->builder.CreateBr(blockLoop); // * create phi llvm->builder.SetInsertPoint(blockLoop); 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(blockLoopBody); CodeScope* scopeLoop = fold.blocks.front(); compilation::ICodeScopeUnit* 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); // * finalization: llvm->builder.SetInsertPoint(blockAfterLoop); if (!flagSaturationTriggered){ return accum; } llvm::PHINode* result = llvm->builder.CreatePHI(accumInit->getType(), 2); result->addIncoming(accum, blockLoop); result->addIncoming(accumNext, blockSaturation); return result; } llvm::Value* AdvancedInstructions::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->llvmContext, "foldinf", function->raw); llvm::BasicBlock *blockNext = llvm::BasicBlock::Create(llvm->llvmContext, "foldinf_next", function->raw); llvm::BasicBlock *blockAfterLoop = llvm::BasicBlock::Create(llvm->llvmContext, "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, accumName); accum->addIncoming(accumInit, blockBeforeLoop); // * loop body CodeScope* scopeLoop = fold.blocks.front(); compilation::ICodeScopeUnit* 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); // finalization: llvm->builder.SetInsertPoint(blockAfterLoop); return accumNext; } llvm::Value* AdvancedInstructions::compileIf(const Expression& exprIf, const std::string& hintRetVar) { EXPAND_CONTEXT const Expression& condExpr = exprIf.getOperands()[0]; llvm::IRBuilder<>& builder = llvm->builder; assert(builder.GetInsertBlock() == scope->currentBlockRaw); //initialization: llvm::BasicBlock *blockEpilog = llvm::BasicBlock::Create(llvm->llvmContext, "ifAfter", function->raw); llvm::BasicBlock *blockTrue = llvm::BasicBlock::Create(llvm->llvmContext, "ifTrue", function->raw); llvm::BasicBlock *blockFalse = llvm::BasicBlock::Create(llvm->llvmContext, "ifFalse", function->raw); llvm::Value* cond = scope->process(condExpr); builder.SetInsertPoint(blockTrue); CodeScope* scopeTrue = exprIf.blocks.front(); llvm::Value* resultTrue = function->getScopeUnit(scopeTrue)->compile(); llvm::BasicBlock * blockTrueEnd = builder.GetInsertBlock(); builder.CreateBr(blockEpilog); builder.SetInsertPoint(blockFalse); CodeScope* scopeFalse = exprIf.blocks.back(); llvm::Value* resultFalse = function->getScopeUnit(scopeFalse)->compile(); llvm::BasicBlock * blockFalseEnd = builder.GetInsertBlock(); builder.CreateBr(blockEpilog); builder.SetInsertPoint(scope->currentBlockRaw); llvm->builder.CreateCondBr(cond, blockTrue, blockFalse); builder.SetInsertPoint(blockEpilog); llvm::PHINode *ret = builder.CreatePHI(resultTrue->getType(), 2, NAME("if")); ret->addIncoming(resultTrue, blockTrueEnd); ret->addIncoming(resultFalse, blockFalseEnd); return ret; } //TODO Switch: default variant no needed when all possible conditions are considered llvm::Value* AdvancedInstructions::compileSwitch(const Expression& exprSwitch, const std::string& hintRetVar) { EXPAND_CONTEXT UNUSED(function); AST* root = context.pass->man->root; llvm::IRBuilder<>& builder = llvm->builder; 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::BasicBlock* blockProlog = builder.GetInsertBlock(); llvm::BasicBlock *blockEpilog = llvm::BasicBlock::Create(llvm->llvmContext, "switchAfter", function->raw); builder.SetInsertPoint(blockEpilog); llvm::Type* exprSwitchType = llvm->toLLVMType(root->getType(exprSwitch)); llvm::PHINode *ret = builder.CreatePHI(exprSwitchType, countCases, NAME("switch")); + llvm::Type* typI8 = llvm::Type::getInt8Ty(llvm->llvmContext); builder.SetInsertPoint(blockProlog); llvm::Value * conditionSwitch = scope->process(exprSwitch.operands[0]); llvm::BasicBlock *blockDefault = llvm::BasicBlock::Create(llvm->llvmContext, "caseDefault", function->raw); - llvm::SwitchInst * instructionSwitch = builder.CreateSwitch(conditionSwitch, blockDefault, countCases); + llvm::SwitchInst * instructionSwitch = builder.CreateSwitch( + typeinference::doAutomaticTypeConversion(conditionSwitch, typI8, builder), + blockDefault, + countCases); for (int size = exprSwitch.operands.size(), i = 2; i < size; ++i) { llvm::BasicBlock *blockCase = llvm::BasicBlock::Create(llvm->llvmContext, "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); + instructionSwitch->addCase( + dyn_cast( + typeinference::doAutomaticTypeConversion(condCase, typI8, builder)), + 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; } llvm::Value* AdvancedInstructions::compileSwitchVariant(const Expression& exprSwitch, const std::string& hintRetVar) { EXPAND_CONTEXT UNUSED(function); AST* root = context.pass->man->root; llvm::IRBuilder<>& builder = llvm->builder; llvm::Type* typI8= llvm::Type::getInt8Ty(llvm->llvmContext); const ExpandedType& typVariant = root->getType(exprSwitch.operands.at(0)); llvm::Type* typVariantRaw = llvm->toLLVMType(typVariant); assert(typVariant->__operands.size() == exprSwitch.operands.size() - 1 && "Ill-formed Switch Variant"); int casesCount = exprSwitch.operands.size(); llvm::BasicBlock* blockProlog = builder.GetInsertBlock(); llvm::BasicBlock *blockEpilog = llvm::BasicBlock::Create(llvm->llvmContext, "switchAfter", function->raw); builder.SetInsertPoint(blockEpilog); llvm::Type* resultType = llvm->toLLVMType(root->getType(exprSwitch)); llvm::PHINode *ret = builder.CreatePHI(resultType, casesCount, NAME("switch")); builder.SetInsertPoint(blockProlog); llvm::Value * conditionSwitchRaw = scope->process(exprSwitch.operands.at(0)); llvm::Value* idRaw = builder.CreateExtractValue(conditionSwitchRaw, llvm::ArrayRef({0})); //Dereference preparation - const bool flagDoDerefence = llvm::cast(typVariantRaw)->getStructNumElements() > 1; + const bool flagPrepareDerefence = std::any_of(typVariant->__operands.begin(), typVariant->__operands.end(), [](const TypeAnnotation& op){ + return op.isValid(); + }); + llvm::Value* addrAsStorage = nullptr; - if (flagDoDerefence){ + if (flagPrepareDerefence){ + assert(exprSwitch.bindings.size() && "Switch condition alias not found"); llvm::Type* typStorageRaw = llvm::cast(typVariantRaw)->getElementType(1); llvm::Value* storageRaw = builder.CreateExtractValue(conditionSwitchRaw, llvm::ArrayRef({1})); addrAsStorage = llvm->builder.CreateAlloca(typStorageRaw); llvm->builder.CreateStore(storageRaw, addrAsStorage); } llvm::SwitchInst * instructionSwitch = builder.CreateSwitch(idRaw, nullptr, casesCount); llvm::BasicBlock* blockDefaultUndefined; std::list::const_iterator scopeCaseIt = exprSwitch.blocks.begin(); for (int instancesSize = exprSwitch.operands.size()-1, instId = 0; instId < instancesSize; ++instId) { llvm::BasicBlock *blockCase = llvm::BasicBlock::Create(llvm->llvmContext, "case" + std::to_string(instId), function->raw); builder.SetInsertPoint(blockCase); ICodeScopeUnit* unitCase = function->getScopeUnit(*scopeCaseIt); + const ExpandedType& instType = ExpandedType(typVariant->__operands.at(instId)); - //Actual variant Derefence - if (flagDoDerefence) { - assert(exprSwitch.bindings.size() && "Switch condition alias not found"); + //Actual variant derefence + if (instType->isValid()) { string identCondition = exprSwitch.bindings.front(); - const ExpandedType& instType = ExpandedType(typVariant->__operands.at(instId)); llvm::Type* instTypeRaw = llvm->toLLVMType(instType); llvm::Value* addrAsInst = llvm->builder.CreateBitOrPointerCast(addrAsStorage, instTypeRaw->getPointerTo()); llvm::Value* instRaw = llvm->builder.CreateLoad(instTypeRaw, addrAsInst); const Symbol& identSymb = unitCase->bindArg(instRaw, move(identCondition)); Attachments::put(identSymb, instType); } llvm::Value* resultCase = function->getScopeUnit(*scopeCaseIt)->compile(); builder.CreateBr(blockEpilog); ret->addIncoming(resultCase, blockDefaultUndefined = builder.GetInsertBlock()); builder.SetInsertPoint(blockProlog); instructionSwitch->addCase(dyn_cast(llvm::ConstantInt::get(typI8, exprSwitch.operands.at(instId+1).getValueDouble())), blockCase); ++scopeCaseIt; } instructionSwitch->setDefaultDest(blockDefaultUndefined); builder.SetInsertPoint(blockEpilog); return ret; } //TODO recognize cases to make const arrays/stored in global mem/stack alloced. llvm::Value* AdvancedInstructions::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->getType(expression); assert(typAggrExpanded->__operator == TypeOperator::LIST); 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->llvmContext), 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* AdvancedInstructions::compileConstantStringAsPChar(const string& data, const std::string& hintRetVar) { EXPAND_CONTEXT UNUSED(function); UNUSED(scope); Type* typPchar = PointerType::getUnqual(Type::getInt8Ty(llvm->llvmContext)); //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->llvmContext, data); Value* rawPtrData = llvm->builder.CreateAlloca(rawData->getType(), ConstantInt::get(Type::getInt32Ty(llvm->llvmContext), 1, false)); llvm->builder.CreateStore(rawData, rawPtrData); return llvm->builder.CreateCast(llvm::Instruction::BitCast, rawPtrData, typPchar, hintRetVar); } llvm::Value* AdvancedInstructions::compileSequence(const Expression &expr){ EXPAND_CONTEXT UNUSED(scope); UNUSED(llvm); llvm::Value* result; for(CodeScope* scope: expr.blocks){ result = function->getScopeUnit(scope)->compile(); } return result; } diff --git a/cpp/src/compilation/latereasoning.cpp b/cpp/src/compilation/latereasoning.cpp index 45f8ccd..4b32156 100644 --- a/cpp/src/compilation/latereasoning.cpp +++ b/cpp/src/compilation/latereasoning.cpp @@ -1,175 +1,179 @@ /* * This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. * * latereasoning.cpp * * Author: pgess * Created on May 26, 2018, 3:54 PM */ #include "compilation/latereasoning.h" //#include "aux/latereasoning.h" #include "compilation/scopedecorators.h" #include "analysis/interpretation.h" #include "compilation/targetinterpretation.h" #include using namespace xreate::interpretation; using namespace xreate::compilation; using namespace std; namespace xreate{ namespace latereasoning{ #define HINT(x) (hint.empty()? x : hint) +std::map LateReasoningCompiler:: __dictGuardDefinitions = std::map(); + llvm::Value* LateReasoningCompiler::processSwitchLateStatement(const Expression& expr, const std::string& hint) { AST* root = __context.pass->man->root; LLVMLayer* llvm = __context.pass->man->llvm; CodeScope* scopeBody = expr.blocks.front(); Symbol guardS = Symbol{scopeBody->getSymbol(expr.bindings.front()), scopeBody}; const ExpandedType& guardT = root->getType(expr.operands.at(0)); - const ExpandedType& guardTPlain = interpretation::dereferenceSlaveType(guardT, __context.pass->man->transcend); + const ExpandedType& guardTPlain = guardT->__operator == TypeOperator::SLAVE? + interpretation::dereferenceSlaveType(guardT, __context.pass->man->transcend) + : guardT; llvm::Value * guardRaw = __context.scope->process(expr.operands.at(0)); llvm::Type* instructionT = llvm->toLLVMType(root->getType(expr)); return compileExpand(guardS, guardRaw, guardTPlain, instructionT, hint, [this, scopeBody]() { ICodeScopeUnit* bodyUnit = this->__context.function->getScopeUnit(scopeBody); bodyUnit->reset(); return this->__context.function->getScopeUnit(scopeBody)->compile(); }); } llvm::Value* LateReasoningCompiler::compileAutoExpand(const LateAnnotation& annotation, llvm::Type* resultT, const std::string& hint, Handler handler) { TranscendLayer* transcend = __context.pass->man->transcend; AST* root = __context.pass->man->root; const std::list& guardKeys = annotation.guardKeys; std::list guardsToExpand; for(const SymbolPacked key : guardKeys) { if(!__dictGuardDefinitions.count(key)) { const Symbol& keyS = transcend->unpack(key); InterpretationScope* keyScope = __fnI12n->getScope(keyS.scope); if (!keyScope->isBindingDefined(keyS.identifier)) { guardsToExpand.push_back(keyS); } } } typedef std::function < llvm::Value * () > Compiler; Compiler programInit([handler, annotation, this]() { std::list&& values = findKeys(annotation.guardKeys); auto answer = annotation.select(values, __context.pass->man->root, __context.pass->man->transcend); assert(answer); return handler(*answer); }); Compiler aggregate = std::accumulate(guardsToExpand.begin(), guardsToExpand.end(), programInit, [this, root, transcend, &resultT, hint](Compiler program, const Symbol & key) { const ExpandedType& keyT = root->getType(CodeScope::getDefinition(key)); const ExpandedType& keyTPlain = keyT->__operator == TypeOperator::SLAVE? interpretation::dereferenceSlaveType(keyT, transcend) : keyT; return Compiler([this, key, keyTPlain, resultT, hint, program](){ llvm::Value * keyRaw = __context.scope->processSymbol(key); return compileExpand(key, keyRaw, keyTPlain, resultT, hint, program); }); } ); return aggregate(); } llvm::Value* LateReasoningCompiler::compileExpand(const Symbol& keyS, llvm::Value* keyRaw, const ExpandedType& domainT, llvm::Type* resultT, const std::string& hint, CompilerHandler compilerBody) { assert(domainT->__operator == TypeOperator::VARIANT); std::list domInstancesList = generateAllInstancesInDomain2(domainT); std::vector domInstances(domInstancesList.begin(), domInstancesList.end()); const int countInstances = domInstances.size(); assert(countInstances); TranscendLayer* transcend = __context.pass->man->transcend; SymbolPacked keyP = transcend->pack(keyS); LLVMLayer* llvm = __context.pass->man->llvm; llvm::IRBuilder<>& builder = llvm->builder; compilation::IFunctionUnit* function = __context.function; llvm::Type* typI8 = llvm::Type::getInt8Ty(llvm->llvmContext); llvm::Value* keyVariantRaw = builder.CreateExtractValue(keyRaw, llvm::ArrayRef({0})); llvm::SwitchInst* instructionSwitch = builder.CreateSwitch(keyVariantRaw, nullptr, countInstances); llvm::BasicBlock *blockEpilog = llvm::BasicBlock::Create( llvm->llvmContext, "epilog", function->raw); builder.SetInsertPoint(blockEpilog); llvm::PHINode *ret = builder.CreatePHI(resultT, countInstances, HINT("reverse")); llvm::BasicBlock* blockDefault = nullptr; for (int instanceId = 0; instanceId < countInstances; ++instanceId) { llvm::BasicBlock *blockCase = llvm::BasicBlock::Create( llvm->llvmContext, "case" + std::to_string(instanceId), function->raw); if(instanceId == 0) blockDefault = blockCase; builder.SetInsertPoint(blockCase); //assign guard values const Expression& instanceE = domInstances.at(instanceId); __dictGuardDefinitions[keyP] = instanceE; // __fnI12n->getScope(keyS.scope)->overrideBindings({ // {instanceE, keyS.identifier} // }); //invoke further compilation handler llvm::Value* resultCase = compilerBody(); ret->addIncoming(resultCase, builder.GetInsertBlock()); instructionSwitch->addCase(llvm::dyn_cast(llvm::ConstantInt::get(typI8, instanceId)), blockCase); builder.CreateBr(blockEpilog); } //erase guard assignment __dictGuardDefinitions.erase(keyP); instructionSwitch->setDefaultDest(blockDefault); builder.SetInsertPoint(blockEpilog); return ret; } std::list LateReasoningCompiler::findKeys(const std::list& keys) { TranscendLayer* transcend = __context.pass->man->transcend; std::list result; InterpretationScope* scopeI12n = __fnI12n->getScope(__context.scope->scope); std::transform(keys.begin(), keys.end(), std::inserter(result, result.end()), [this, scopeI12n, transcend](const SymbolPacked & key) { if (__dictGuardDefinitions.count(key)){ return __dictGuardDefinitions.at(key); } return scopeI12n->processSymbol(transcend->unpack(key)); }); return result; } } } diff --git a/cpp/src/compilation/latereasoning.h b/cpp/src/compilation/latereasoning.h index c88d298..7dc6d59 100644 --- a/cpp/src/compilation/latereasoning.h +++ b/cpp/src/compilation/latereasoning.h @@ -1,72 +1,72 @@ /* * This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. * * File: latereasoning.h * Author: pgess * * Created on May 26, 2018, 3:44 PM */ #ifndef CMPLLATEREASONING_H #define CMPLLATEREASONING_H #include "ast.h" #include "aux/latereasoning.h" #include "pass/compilepass.h" #include "llvmlayer.h" #include "transcendlayer.h" #include "targets.h" namespace xreate{ namespace interpretation{ class InterpretationFunction; } } namespace llvm{ class Value; } namespace xreate{ namespace latereasoning{ typedef std::function CompilerHandler; typedef std::function Handler; class LateReasoningCompiler{ public: LateReasoningCompiler(interpretation::InterpretationFunction* fn, compilation::Context ctx) : __context(ctx), __fnI12n(fn){ } llvm::Value* processSwitchLateStatement(const Expression& expr, const std::string& identHint); llvm::Value* compileAutoExpand(const LateAnnotation& annotation, llvm::Type* resultT, const std::string& hint, Handler handler); private: compilation::Context __context; interpretation::InterpretationFunction* __fnI12n; - std::map __dictGuardDefinitions; + static std::map __dictGuardDefinitions; llvm::Value* compileExpand(const Symbol& keyS, llvm::Value* keyRaw, const ExpandedType& domainT, llvm::Type* resultT, const std::string& hint, CompilerHandler compilerBody); std::list findKeys(const std::list& keys); }; } } #endif /* CMPLLATEREASONING_H */ diff --git a/cpp/src/compilation/polymorph.cpp b/cpp/src/compilation/polymorph.cpp index 64bbeb9..5d07277 100644 --- a/cpp/src/compilation/polymorph.cpp +++ b/cpp/src/compilation/polymorph.cpp @@ -1,53 +1,53 @@ /* * This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ /* * Author: pgess * Created on July 9, 2018, 6:04 PM * * \file polymorph.cpp * \brief polymorph */ #include "compilation/polymorph.h" using namespace std; namespace xreate{ namespace polymorph{ PolymorphFnInvocation::PolymorphFnInvocation(const latereasoning::LateAnnotation& selector, std::list calleeSpecializations, CompilePass* pass, PolymorphQuery* query, LLVMLayer* llvm, latereasoning::LateReasoningCompiler* compiler) : __selector(selector), __calleeSpecializations(calleeSpecializations), __pass(pass), __query(query), __llvm(llvm), __compiler(compiler) { } llvm::Value* PolymorphFnInvocation::operator()(std::vector&& args, const std::string& hintDecl) { std::map dictSelectors; for(ManagedFnPtr specialization : __calleeSpecializations) { dictSelectors.emplace(specialization->guard, specialization); } compilation::IFunctionUnit* specAny = __pass->getFunctionUnit(__calleeSpecializations.front()); return __compiler->compileAutoExpand( __selector, specAny->prepareResult(), hintDecl, [this, &args, hintDecl, &dictSelectors](const Gringo::Symbol & selectorRaw) { const Expression & selectorE = __query->getValue(selectorRaw); assert(dictSelectors.count(selectorE) && "Inappropriate specialization guard"); - compilation::RawFnInvocation* invoc = new compilation::RawFnInvocation( + compilation::BruteFnInvocation* invoc = new compilation::BruteFnInvocation( __pass->getFunctionUnit(dictSelectors.at(selectorE))->compile(), __llvm); return invoc->operator()(move(args), hintDecl); }); } } } diff --git a/cpp/src/compilation/targetinterpretation.cpp b/cpp/src/compilation/targetinterpretation.cpp index 31da3ea..17457db 100644 --- a/cpp/src/compilation/targetinterpretation.cpp +++ b/cpp/src/compilation/targetinterpretation.cpp @@ -1,628 +1,628 @@ /* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. * * File: targetinterpretation.cpp * Author: pgess * * Created on June 29, 2016, 6:45 PM */ /** * \file targetinterpretation.h * \brief Interpretation support. See more [details on Interpretation](/w/concepts/dsl/) */ #include "compilation/targetinterpretation.h" #include "pass/interpretationpass.h" #include "analysis/typeinference.h" #include "llvmlayer.h" #include "compilation/scopedecorators.h" #include "compilation/interpretation-instructions.h" #include #include #include using namespace std; using namespace xreate::compilation; namespace xreate{ namespace interpretation{ const Expression EXPRESSION_FALSE = Expression(Atom(0)); const Expression EXPRESSION_TRUE = Expression(Atom(1)); CodeScope* InterpretationScope::processOperatorIf(const Expression& expression) { const Expression& exprCondition = process(expression.getOperands()[0]); if (exprCondition == EXPRESSION_TRUE) { return expression.blocks.front(); } return expression.blocks.back(); } CodeScope* InterpretationScope::processOperatorSwitch(const Expression& expression) { const Expression& exprCondition = process(expression.operands[0]); bool flagHasDefault = expression.operands[1].op == Operator::CASE_DEFAULT; //TODO check that one and only one case variant is appropriate for (size_t size = expression.operands.size(), i = flagHasDefault ? 2 : 1; i < size; ++i) { const Expression& exprCase = process(expression.operands[i]); if (function->getScope((const CodeScope*) exprCase.blocks.front())->processScope() == exprCondition) { return exprCase.blocks.back(); } } if (flagHasDefault) { const Expression& exprCaseDefault = expression.operands[1]; return exprCaseDefault.blocks.front(); } assert(false && "Switch has no appropriate variant"); return nullptr; } CodeScope* InterpretationScope::processOperatorSwitchVariant(const Expression& expression) { const Expression& condition = process(expression.operands.at(0)); assert(condition.op == Operator::VARIANT); const string& identCondition = expression.bindings.front(); Expression opExpected(Atom(condition.getValueDouble())); auto itFoundValue = std::find(++expression.operands.begin(), expression.operands.end(), opExpected); assert(itFoundValue != expression.operands.end()); int indexBlock = itFoundValue - expression.operands.begin() - 1; auto blockFound = expression.blocks.begin(); std::advance(blockFound, indexBlock); InterpretationScope* scopeI12n = function->getScope(*blockFound); if(condition.operands.size()) { const Expression& value = condition.operands.at(0); scopeI12n->overrideBindings({ {value, identCondition} }); } return *blockFound; } llvm::Value* InterpretationScope::processLate(const InterpretationOperator& op, const Expression& expression, const Context& context) { switch(op) { case IF_INTERPRET_CONDITION: { CodeScope* scopeResult = processOperatorIf(expression); llvm::Value* result = context.function->getScopeUnit(scopeResult)->compile(); return result; } case SWITCH_INTERPRET_CONDITION: { CodeScope* scopeResult = processOperatorSwitch(expression); llvm::Value* result = context.function->getScopeUnit(scopeResult)->compile(); return result; } case SWITCH_VARIANT: { CodeScope* scopeResult = processOperatorSwitchVariant(expression); const Expression& condition = expression.operands.at(0); const Expression& valueCondition = process(condition); const string identCondition = expression.bindings.front(); auto scopeCompilation = Decorators::getInterface(context.function->getScopeUnit(scopeResult)); if(valueCondition.operands.size()) { //override value Symbol symbCondition{ScopedSymbol{scopeResult->__identifiers.at(identCondition), versions::VERSION_NONE}, scopeResult}; scopeCompilation->overrideDeclarations({ {symbCondition, Expression(valueCondition.operands.at(0))}} ); //set correct type for binding: TypeAnnotation typeVariant = typeinference::getType(condition, *function->man->ast); int conditionIndex = valueCondition.getValueDouble(); ScopedSymbol symbolInternal = scopeResult->getSymbol(identCondition); scopeResult->__declarations[symbolInternal].bindType(typeVariant.__operands.at(conditionIndex)); } llvm::Value* result = context.function->getScopeUnit(scopeResult)->compile(); return result; } case SWITCH_LATE: { latereasoning::LateReasoningCompiler compiler(dynamic_cast(this->function), context); return compiler.processSwitchLateStatement(expression, ""); } case FOLD_INTERPRET_INPUT: { //initialization const Expression& exprInput = process(expression.getOperands()[0]); assert(exprInput.op == Operator::LIST); CodeScope* scopeBody = expression.blocks.front(); const string& nameEl = expression.bindings[0]; Symbol symbEl{ScopedSymbol{scopeBody->__identifiers.at(nameEl), versions::VERSION_NONE}, scopeBody}; const std::string& idAccum = expression.bindings[1]; llvm::Value* rawAccum = context.scope->process(expression.getOperands()[1]); InterpretationScope* intrBody = function->getScope(scopeBody); auto unitBody = Decorators::getInterface(context.function->getScopeUnit(scopeBody)); const std::vector elementsInput = exprInput.getOperands(); for(size_t i = 0; i < elementsInput.size(); ++i) { const Expression& exprElement = elementsInput[i]; intrBody->overrideBindings({ {exprElement, nameEl} }); unitBody->overrideDeclarations({ {symbEl, exprElement} }); //resets unitBody unitBody->bindArg(rawAccum, string(idAccum)); rawAccum = unitBody->compile(); } return rawAccum; } // case FOLD_INF_INTERPRET_INOUT: // { // } //TODO refactor as InterpretationCallStatement class case CALL_INTERPRET_PARTIAL: { const std::string &calleeName = expression.getValueString(); ICodeScopeUnit* scopeUnitSelf = context.scope; ManagedFnPtr callee = this->function->man->ast->findFunction(calleeName); const FunctionInterpretationData& calleeData = FunctionInterpretationHelper::getSignature(callee); std::vector argsActual; PIFSignature sig; sig.declaration = callee; for(size_t no = 0, size = expression.operands.size(); no < size; ++no) { const Expression& op = expression.operands[no]; if (calleeData.signature.at(no) == INTR_ONLY) { sig.bindings.push_back(process(op)); continue; } argsActual.push_back(scopeUnitSelf->process(op)); } TargetInterpretation* man = dynamic_cast (this->function->man); PIFunction* pifunction = man->getFunction(move(sig)); llvm::Function* raw = pifunction->compile(); - boost::scoped_ptr statement(new RawFnInvocation(raw, man->pass->man->llvm)); + boost::scoped_ptr statement(new BruteFnInvocation(raw, man->pass->man->llvm)); return (*statement)(move(argsActual)); } case QUERY_LATE: { return IntrinsicQueryInstruction( dynamic_cast(this->function)) .processLate(expression, context); } default: break; } assert(false && "Unknown late interpretation operator"); return nullptr; } llvm::Value* InterpretationScope::compile(const Expression& expression, const Context& context) { const InterpretationData& data = Attachments::get(expression); if (data.op != InterpretationOperator::NONE) { return processLate(data.op, expression, context); } Expression result = process(expression); return context.scope->process(result); } Expression InterpretationScope::process(const Expression& expression) { #ifndef NDEBUG if (expression.tags.count("bpoint")) { std::raise(SIGINT); } #endif PassManager* man = (static_cast (function->man))->pass->man; switch (expression.__state) { case Expression::INVALID: assert(false); case Expression::NUMBER: case Expression::STRING: return expression; case Expression::IDENT: { Symbol s = Attachments::get(expression); return Parent::processSymbol(s); } case Expression::COMPOUND: break; default: assert(false); } switch (expression.op) { case Operator::EQU: { const Expression& left = process(expression.operands[0]); const Expression& right = process(expression.operands[1]); if (left == right) return EXPRESSION_TRUE; return EXPRESSION_FALSE; } case Operator::NE: { const Expression& left = process(expression.operands[0]); const Expression& right = process(expression.operands[1]); if (left == right) return EXPRESSION_FALSE; return EXPRESSION_TRUE; } case Operator::LOGIC_AND: { assert(expression.operands.size() == 1); return process (expression.operands[0]); } // case Operator::LOGIC_OR: case Operator::CALL: { const std::string &fnName = expression.getValueString(); ManagedFnPtr fnAst = this->function->man->ast->findFunction(fnName); InterpretationFunction* fnUnit = this->function->man->getFunction(fnAst); vector args; args.reserve(expression.getOperands().size()); for(size_t i = 0, size = expression.getOperands().size(); i < size; ++i) { args.push_back(process(expression.getOperands()[i])); } return fnUnit->process(args); } case Operator::CALL_INTRINSIC: { assert(false && "Unknown intrinsic"); } case Operator::QUERY: { return IntrinsicQueryInstruction(dynamic_cast(this->function)) .process(expression); } case Operator::QUERY_LATE: { assert(false && "Can't be interpretated"); return Expression(); } case Operator::IF: { CodeScope* scopeResult = processOperatorIf(expression); return function->getScope(scopeResult)->processScope(); } case Operator::SWITCH: { CodeScope* scopeResult = processOperatorSwitch(expression); return function->getScope(scopeResult)->processScope(); } case Operator::SWITCH_VARIANT: { CodeScope* scopeResult = processOperatorSwitchVariant(expression); return function->getScope(scopeResult)->processScope(); } case Operator::VARIANT: { if(!expression.operands.size()) return expression; Expression variantData = process(expression.operands[0]); Expression result{Operator::VARIANT, {variantData}}; result.setValueDouble(expression.getValueDouble()); return result; } case Operator::INDEX: { Expression exprData = process(expression.operands[0]); for (size_t keyId = 1; keyId < expression.operands.size(); ++keyId) { const Expression& exprKey = process(expression.operands[keyId]); if (exprKey.__state == Expression::STRING) { const string& key = exprKey.getValueString(); assert(exprData.__indexBindings.count(key)); size_t idxKey = exprData.__indexBindings.at(key); exprData = Expression(exprData.operands.at(idxKey)); continue; } if (exprKey.__state == Expression::NUMBER) { int key = exprKey.getValueDouble(); exprData = Expression(exprData.operands[key]); continue; } assert(false && "Inappropriate key"); } return exprData; } case Operator::FOLD: { const Expression& exprInput = process(expression.getOperands()[0]); const Expression& exprInit = process(expression.getOperands()[1]); const std::string& argEl = expression.bindings[0]; const std::string& argAccum = expression.bindings[1]; InterpretationScope* body = function->getScope(expression.blocks.front()); Expression accum = exprInit; for(size_t size = exprInput.getOperands().size(), i = 0; i < size; ++i) { body->overrideBindings({ {exprInput.getOperands()[i], argEl}, {accum, argAccum} }); accum = body->processScope(); } return accum; } case Operator::LIST: case Operator::LIST_NAMED: case Operator::LIST_RANGE: { Expression result(expression.op,{}); result.operands.resize(expression.operands.size()); result.bindings = expression.bindings; result.__indexBindings = expression.__indexBindings; int keyId = 0; for(const Expression& opCurrent : expression.operands) { result.operands[keyId++] = process(opCurrent); } return result; } // case Operator::MAP: { // break; // } default: break; } return expression; } InterpretationFunction* TargetInterpretation::getFunction(IFunctionUnit* unit) { if (__dictFunctionsByUnit.count(unit)) { return __dictFunctionsByUnit.at(unit); } InterpretationFunction* f = new InterpretationFunction(unit->function, this); __dictFunctionsByUnit.emplace(unit, f); assert(__functions.emplace(unit->function.id(), f).second); return f; } PIFunction* TargetInterpretation::getFunction(PIFSignature&& sig) { auto f = __pifunctions.find(sig); if (f != __pifunctions.end()) { return f->second; } PIFunction* result = new PIFunction(PIFSignature(sig), __pifunctions.size(), this); __pifunctions.emplace(move(sig), result); assert(__dictFunctionsByUnit.emplace(result->functionUnit, result).second); return result; } InterpretationScope* TargetInterpretation::transformContext(const Context& c) { return this->getFunction(c.function)->getScope(c.scope->scope); } llvm::Value* TargetInterpretation::compile(const Expression& expression, const Context& ctx) { return transformContext(ctx)->compile(expression, ctx); } InterpretationFunction::InterpretationFunction(const ManagedFnPtr& function, Target* target) : Function(function, target) { } Expression InterpretationFunction::process(const std::vector& args) { InterpretationScope* body = getScope(__function->__entry); list> bindings; for(size_t i = 0, size = args.size(); i < size; ++i) { bindings.push_back(make_pair(args.at(i), body->scope->__bindings.at(i))); } body->overrideBindings(bindings); return body->processScope(); } // Partial function interpretation typedef BasicFunctionUnit PIFunctionUnitParent; class PIFunctionUnit : public PIFunctionUnitParent{ public: PIFunctionUnit(ManagedFnPtr f, std::set&& arguments, size_t id, CompilePass* p) : PIFunctionUnitParent(f, p), argumentsActual(move(arguments)), __id(id) { } protected: std::vector - prepareArguments() { + prepareSignature() override { LLVMLayer* llvm = PIFunctionUnitParent::pass->man->llvm; AST* ast = PIFunctionUnitParent::pass->man->root; CodeScope* entry = PIFunctionUnitParent::function->__entry; std::vector signature; for(size_t no : argumentsActual) { VNameId argId = entry->__identifiers.at(entry->__bindings.at(no)); ScopedSymbol arg{argId, versions::VERSION_NONE}; signature.push_back(llvm->toLLVMType(ast->expandType(entry->__declarations.at(arg).type))); } return signature; } llvm::Function::arg_iterator - prepareBindings() { + prepareBindings() override{ CodeScope* entry = PIFunctionUnitParent::function->__entry; ICodeScopeUnit* entryCompilation = PIFunctionUnitParent::getScopeUnit(entry); llvm::Function::arg_iterator fargsI = PIFunctionUnitParent::raw->arg_begin(); for(size_t no : argumentsActual) { ScopedSymbol arg{entry->__identifiers.at(entry->__bindings.at(no)), versions::VERSION_NONE}; entryCompilation->bindArg(&*fargsI, arg); fargsI->setName(entry->__bindings.at(no)); ++fargsI; } return fargsI; } virtual std::string - prepareName() { + prepareName() override { return PIFunctionUnitParent::prepareName() + "_" + std::to_string(__id); } private: std::set argumentsActual; size_t __id; } ; PIFunction::PIFunction(PIFSignature&& sig, size_t id, TargetInterpretation* target) : InterpretationFunction(sig.declaration, target), signatureInstance(move(sig)) { const FunctionInterpretationData& functionData = FunctionInterpretationHelper::getSignature(signatureInstance.declaration); std::set argumentsActual; for (size_t no = 0, size = functionData.signature.size(); no < size; ++no) { if (functionData.signature.at(no) != INTR_ONLY) { argumentsActual.insert(no); } } functionUnit = new PIFunctionUnit(signatureInstance.declaration, move(argumentsActual), id, target->pass); CodeScope* entry = signatureInstance.declaration->__entry; auto entryUnit = Decorators::getInterface<>(functionUnit->getEntry()); InterpretationScope* entryIntrp = InterpretationFunction::getScope(entry); list> bindingsPartial; list> declsPartial; for(size_t no = 0, sigNo = 0, size = entry->__bindings.size(); no < size; ++no) { if(functionData.signature.at(no) == INTR_ONLY) { bindingsPartial.push_back({signatureInstance.bindings[sigNo], entry->__bindings[no]}); VNameId argId = entry->__identifiers.at(entry->__bindings[no]); Symbol argSymbol{ScopedSymbol {argId, versions::VERSION_NONE}, entry}; declsPartial.push_back({argSymbol, signatureInstance.bindings[sigNo]}); ++sigNo; } } entryIntrp->overrideBindings(bindingsPartial); entryUnit->overrideDeclarations(declsPartial); } llvm::Function* PIFunction::compile() { llvm::Function* raw = functionUnit->compile(); return raw; } bool operator<(const PIFSignature& lhs, const PIFSignature& rhs) { if (lhs.declaration.id() != rhs.declaration.id()) { return lhs.declaration.id() < rhs.declaration.id(); } return lhs.bindings < rhs.bindings; } bool operator<(const PIFSignature& lhs, PIFunction * const rhs) { return lhs < rhs->signatureInstance; } bool operator<(PIFunction * const lhs, const PIFSignature& rhs) { return lhs->signatureInstance < rhs; } } } /** \class xreate::interpretation::InterpretationFunction * * Holds list of xreate::interpretation::InterpretationScope 's focused on interpretation of individual code scopes * * There is particulat subclass PIFunction intended to represent partially interpreted functions *\sa TargetInterpretation, [Interpretation Concept](/w/concepts/dfa) */ /** \class xreate::interpretation::TargetInterpretation * * Executed during compilation and intented to preprocess eligible parts of code. * Established on [Targets Infrastructure](\ref compilation::Target) * * Holds list of InterpretationFunction / PIFunction to represent interpretation process for individual functions * * In order to be activated during compilation process there is * InterpretationScopeDecorator implementation of ICodeScopeUnit * \sa InterpretationPass, compilation::Target, [Interpretation Concept](/w/concepts/dfa) * */ diff --git a/cpp/src/pass/cfapass.cpp b/cpp/src/pass/cfapass.cpp index ac93e15..2a51dc4 100644 --- a/cpp/src/pass/cfapass.cpp +++ b/cpp/src/pass/cfapass.cpp @@ -1,198 +1,198 @@ /* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. * * cfapass.cpp * * Author: pgess */ /** * \file cfapass.h * \brief Control Flow Analysis(CFA) */ #include "cfapass.h" #include "analysis/cfagraph.h" -#include "analysis/DominatorsTreeAnalysisProvider.h" +#include "analysis/DominatorsAnalysisProvider.h" #include using namespace std; using namespace xreate::cfa; void CFAPassBasic::initSignatures(){ auto range = man->root->__interfacesData.equal_range(CFA); for (auto i = range.first; i!= range.second; ++i){ __signatures.emplace(i->second.op, i->second); } } void CFAPassBasic::run(){ initSignatures(); return AbstractPass::run(); } void CFAPassBasic::finish(){ man->transcend->registerReport(__context.graph); - - dominators::DominatorsTreeAnalysisProvider* reportDominators = new dominators::DominatorsTreeAnalysisProvider(); - reportDominators->run(__context.graph); + boost::scoped_ptr cfaAdapter(dominators::CFAGraphAdapter::build(__context.graph)); + dominators::DominatorsAnalysisProvider* reportDominators = new dominators::DominatorsAnalysisProvider(); + reportDominators->run(cfaAdapter.get()); man->transcend->registerReport(reportDominators); return AbstractPass::finish(); } void CFAPassBasic::processFnCall(ManagedFnPtr function, PassContext context){ TranscendLayer* transcend = man->transcend; __context.graph->addCallConnection(transcend->pack(context.scope), function->getName()); return AbstractPass::processFnCall(function, context); } void CFAPassBasic::processFnCallUncertain(ManagedFnPtr function, PassContext context){ TranscendLayer* transcend = man->transcend; __context.graph->addCallConnection(transcend->pack(context.scope), function->getName()); return AbstractPass::processFnCallUncertain(function, context); } void CFAPassBasic::process(CodeScope* scope, PassContext context, const std::string& hintBlockDecl){ TranscendLayer* transcend = man->transcend; const CodeScope* scopeParent = context.scope; ScopePacked scopeId = transcend->pack(scope); __context.graph->addScope(scope); //Parent Relations if (scopeParent){ __context.graph->addParentConnection(scopeId, transcend->pack(scopeParent)); } else { __context.graph->addParentConnection(scopeId, context.function->getName()); } //TOTEST scope annotations //SECTIONTAG context gather scope annotations __context.graph->addScopeAnnotations(scopeId, scope->tags); __context.graph->addContextRules(scopeId, scope->contextRules); return AbstractPass::process(scope, context, hintBlockDecl); } //TOTEST scope annotations via scheme void CFAPassBasic::process(const Expression& expression, PassContext context, const std::string& varDecl){ TranscendLayer* transcend = man->transcend; if (expression.__state == Expression::COMPOUND){ Operator op= expression.op; if (__signatures.count(op)) { assert(expression.blocks.size()); for (const auto& scheme: boost::make_iterator_range(__signatures.equal_range(expression.op))) { __context.graph->addScopeAnnotations(transcend->pack(expression.blocks.front()), scheme.second.getOperands()); } } } return AbstractPass::process(expression, context, varDecl); } void CFAPassBasic::process(ManagedFnPtr function){ __context.graph->addFunctionAnnotations(function->getName(), function->getTags()); return AbstractPass::process(function); } CFAPassBasic::CFAPassBasic(PassManager* manager) : AbstractPass(manager) , __context{new CFAGraph(manager->transcend)} {} /****************************SCOPE DEPENDENCIES********************************/ void CFAPassDependenciesDecorator::process(const Expression& expression, PassContext context, const std::string& varDecl){ TranscendLayer* transcend = man->transcend; if (expression.__state == Expression::COMPOUND) switch(expression.op){ case Operator::SEQUENCE:{ ScopePacked scopePrev = transcend->pack(expression.blocks.front()); for(auto scopeIt= ++expression.blocks.begin(); scopeIt != expression.blocks.end(); ++scopeIt){ ScopePacked scopeCurrent = transcend->pack(*scopeIt); __context.graph->addDependency(scopeCurrent, scopePrev); scopePrev = scopeCurrent; } break; } default: break; } return Parent::process(expression, context, varDecl); } void CFAPassDependenciesDecorator::processFnCall(ManagedFnPtr function, PassContext context){ TranscendLayer* transcend = man->transcend; const CodeScope* scopeCaller = context.scope; assert(scopeCaller); ScopePacked scopeCallerPacked = transcend->pack(scopeCaller); if(__context.graph->isDependent(scopeCallerPacked)){ ScopePacked scopeCalleePacked = transcend->pack(function->getEntryScope()); __context.graph->transmitDependencies(scopeCalleePacked, scopeCallerPacked); } Parent::processFnCall(function, context); } void CFAPassDependenciesDecorator::processFnCallUncertain(ManagedFnPtr function, PassContext context){ TranscendLayer* transcend = man->transcend; const CodeScope* scopeCaller = context.scope; assert(scopeCaller); ScopePacked scopeCallerPacked = transcend->pack(scopeCaller); if(__context.graph->isDependent(scopeCallerPacked)){ ScopePacked scopeCalleePacked = transcend->pack(function->getEntryScope()); __context.graph->transmitDependencies(scopeCalleePacked, scopeCallerPacked); } Parent::processFnCallUncertain(function, context); } void CFAPassDependenciesDecorator::process(CodeScope* scope, PassContext context, const std::string& hintBlockDecl){ TranscendLayer* transcend = man->transcend; const CodeScope* scopeParent = context.scope; if (scopeParent){ ScopePacked scopePacked = transcend->pack(scope); ScopePacked scopeParentPacked = transcend->pack(scopeParent); if (!__context.graph->isDependent(scopePacked) && __context.graph->isDependent(scopeParentPacked)) { __context.graph->transmitDependencies(scopePacked, scopeParentPacked); } } Parent::process(scope, context, hintBlockDecl); } /** * \class xreate::cfa::CFAPass * \details Provides CFA, important analysis for reasoning. Iterates over AST and stores collected data in CFAGraph */ diff --git a/cpp/src/pass/compilepass.cpp b/cpp/src/pass/compilepass.cpp index 4ca0142..d747d1b 100644 --- a/cpp/src/pass/compilepass.cpp +++ b/cpp/src/pass/compilepass.cpp @@ -1,737 +1,750 @@ /* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. * * Author: pgess * * compilepass.cpp */ /** * \file compilepass.h * \brief Compilation pass */ #include "compilepass.h" #include "transcendlayer.h" #include #include "llvmlayer.h" #include "query/containers.h" #include "compilation/containers.h" #include "ExternLayer.h" #include "compilation/targetinterpretation.h" #include "pass/versionspass.h" #include "compilation/scopedecorators.h" #include "compilation/operators.h" #include "compilation/latex.h" #include "analysis/typeinference.h" #include #include #include using namespace std; using namespace llvm; namespace xreate{ namespace compilation{ std::string BasicFunctionUnit::prepareName() { AST* ast = IFunctionUnit::pass->man->root; string name = ast->getFunctionSpecializations(IFunctionUnit::function->__name).size() > 1 ? IFunctionUnit::function->__name + std::to_string(IFunctionUnit::function.id()) : IFunctionUnit::function->__name; return name; } std::vector BasicFunctionUnit::prepareSignature() { LLVMLayer* llvm = IFunctionUnit::pass->man->llvm; AST* ast = IFunctionUnit::pass->man->root; CodeScope* entry = IFunctionUnit::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), versions::VERSION_NONE}; return llvm->toLLVMType(ast->expandType(entry->__declarations.at(argid).type)); }); return signature; } llvm::Type* BasicFunctionUnit::prepareResult() { LLVMLayer* llvm = IFunctionUnit::pass->man->llvm; AST* ast = IFunctionUnit::pass->man->root; CodeScope* entry = IFunctionUnit::function->__entry; return llvm->toLLVMType(ast->expandType(entry->__declarations.at(ScopedSymbol::RetSymbol).type)); } llvm::Function::arg_iterator BasicFunctionUnit::prepareBindings() { CodeScope* entry = IFunctionUnit::function->__entry; ICodeScopeUnit* entryCompilation = IFunctionUnit::getScopeUnit(entry); llvm::Function::arg_iterator fargsI = IFunctionUnit::raw->arg_begin(); for (std::string &arg : entry->__bindings) { ScopedSymbol argid{entry->__identifiers[arg], versions::VERSION_NONE}; entryCompilation->bindArg(&*fargsI, argid); fargsI->setName(arg); ++fargsI; } return fargsI; } //DEBT compiler rigidly depends on exact definition of DefaultFunctionUnit typedef latex::LatexBruteFunctionDecorator< compilation::BasicFunctionUnit> BruteFunctionDefault; ICodeScopeUnit::ICodeScopeUnit(const CodeScope * const codeScope, IFunctionUnit* f, CompilePass* compilePass) : pass(compilePass), function(f), scope(codeScope), currentBlockRaw(nullptr) { } llvm::Value* -RawFnInvocation::operator()(std::vector&& args, const std::string& hintDecl) { +BruteFnInvocation::operator()(std::vector&& args, const std::string& hintDecl) { llvm::Function* calleeInfo = dyn_cast(__callee); if (calleeInfo) { auto argsFormal = calleeInfo->args(); size_t sizeArgsF = std::distance(argsFormal.begin(), argsFormal.end()); assert(args.size() >= sizeArgsF); assert(calleeInfo->isVarArg() || args.size() == sizeArgsF); auto argFormal = argsFormal.begin(); for(size_t argId = 0; argId < args.size(); ++argId){ if(argFormal != argsFormal.end()){ args[argId] = typeinference::doAutomaticTypeConversion( args.at(argId), argFormal->getType(), llvm->builder); ++argFormal; } } } //Do not name function call that returns Void. std::string nameStatement = hintDecl; if (calleeInfo->getReturnType()->isVoidTy()) { nameStatement.clear(); } return llvm->builder.CreateCall(__calleeTy, __callee, args, nameStatement); } //DESABLEDFEATURE implement inlining class CallStatementInline : public IFnInvocation{ public: CallStatementInline(IFunctionUnit* caller, IFunctionUnit* 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: IFunctionUnit* __caller; IFunctionUnit* __callee; LLVMLayer* llvm; bool isInline() { // Symbol ret = Symbol{0, function->__entry}; // bool flagOnTheFly = SymbolAttachments::get(ret, false); //TODO consider inlining return false; } } ; BasicCodeScopeUnit::BasicCodeScopeUnit(const CodeScope * const codeScope, IFunctionUnit* f, CompilePass* compilePass) : ICodeScopeUnit(codeScope, f, compilePass) { } llvm::Value* BasicCodeScopeUnit::processSymbol(const Symbol& s, std::string hintRetVar) { Expression declaration = CodeScope::getDefinition(s); const CodeScope* scopeExternal = s.scope; ICodeScopeUnit* scopeBruteExternal = ICodeScopeUnit::function->getScopeUnit(scopeExternal); assert(scopeBruteExternal->currentBlockRaw); llvm::Value* resultRaw; llvm::BasicBlock* blockOwn = pass->man->llvm->builder.GetInsertBlock(); if (scopeBruteExternal->currentBlockRaw == blockOwn) { resultRaw = scopeBruteExternal->process(declaration, hintRetVar); scopeBruteExternal->currentBlockRaw = currentBlockRaw = pass->man->llvm->builder.GetInsertBlock(); } else { pass->man->llvm->builder.SetInsertPoint(scopeBruteExternal->currentBlockRaw); resultRaw = scopeBruteExternal->processSymbol(s, hintRetVar); pass->man->llvm->builder.SetInsertPoint(blockOwn); } return resultRaw; } IFnInvocation* BasicCodeScopeUnit::findFunction(const Expression& opCall) { const std::string& calleeName = opCall.getValueString(); LLVMLayer* llvm = pass->man->llvm; const std::list& specializations = pass->man->root->getFunctionSpecializations(calleeName); //if no specializations registered - check external function if (specializations.size() == 0) { llvm::Function* external = llvm->layerExtern->lookupFunction(calleeName); llvm::outs() << "Debug/External function: " << calleeName; external->getType()->print(llvm::outs(), true); llvm::outs() << "\n"; - return new RawFnInvocation(external, llvm); + return new BruteFnInvocation(external, llvm); } //There should be only one specialization without any valid guards at this point - return new RawFnInvocation(pass->getFunctionUnit( + return new BruteFnInvocation(pass->getFunctionUnit( pass->man->root->findFunction(calleeName))->compile(), 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::AdvancedInstructions instructions = xreate::compilation::AdvancedInstructions({this, function, pass}); switch (expr.op) { 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]); break; default:; } switch (expr.op) { case Operator::ADD: { left = process(expr.operands[0]); Context context{this, function, pass}; llvm::Value* resultSU = StructUpdate::add(expr.operands[0], left, expr.operands[1], context, DEFAULT("tmp_add")); if (resultSU) return resultSU; right = process(expr.operands[1]); llvm::Value* resultAddPA = pointerarithmetic::PointerArithmetic::add(left, right, context, DEFAULT("tmp_add")); if (resultAddPA) { return resultAddPA; } 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: + 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")); + + const ExpandedType& leftT = pass->man->root->getType(expr.operands[0]); + const ExpandedType& rightT = pass->man->root->getType(expr.operands[0]); + + if(leftT->__operator == TypeOperator::VARIANT && rightT->__operator == TypeOperator::VARIANT){ + llvm::Type* selectorT = llvm::cast(left->getType())->getElementType(0); + llvm::Value* leftUnwapped = typeinference::doAutomaticTypeConversion(left, selectorT, l.builder); + llvm::Value* rightUnwapped = typeinference::doAutomaticTypeConversion(right, selectorT, l.builder); + return l.builder.CreateICmpEQ(leftUnwapped, rightUnwapped, 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); shared_ptr callee(findFunction(expr)); const std::string& nameCallee = expr.getValueString(); //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); } ); 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::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 tyStructLiteral = l.ast->getType(expr); const std::vector fieldsFormal = (tyStructLiteral.get().__operator == TypeOperator::CUSTOM) ? l.layerExtern->getStructFields(l.layerExtern->lookupType(tyStructLiteral.get().__valueCustom)) : tyStructLiteral.get().fields; std::map indexFields; for (size_t i = 0, size = fieldsFormal.size(); i < size; ++i) { indexFields.emplace(fieldsFormal[i], i); } llvm::StructType* tyLiteralRaw = llvm::cast(l.toLLVMType(tyStructLiteral)); llvm::Value* record = llvm::UndefValue::get(tyLiteralRaw); for (size_t i = 0; i < expr.operands.size(); ++i) { const Expression& operand = expr.operands.at(i); unsigned int fieldId = indexFields.at(expr.bindings.at(i)); llvm::Value* 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: { //TASK allow multiindex compilation 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->getType(expr.operands[0]); llvm::Value* aggr = processSymbol(s, hintIdent); switch (t2.get().__operator) { case TypeOperator::LIST_NAMED: case TypeOperator::CUSTOM: { std::string idxField; const Expression& idx = expr.operands.at(1); switch (idx.__state) { //named struct field case Expression::STRING: idxField = idx.getValueString(); break; //anonymous struct field case Expression::NUMBER: idxField = to_string((int) idx.getValueDouble()); break; default: assert(false && "Wrong index for a struct"); } return instructions.compileStructIndex(aggr, t2, idxField); }; case TypeOperator::LIST: { 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); } }; 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::QUERY: case Operator::QUERY_LATE: { assert(false && "Should be processed by interpretation"); } case Operator::VARIANT: { const ExpandedType& typVariant = pass->man->root->getType(expr); llvm::Type* typVariantRaw = l.toLLVMType(typVariant); llvm::Type* typIdRaw = llvm::cast(typVariantRaw)->getElementType(0); uint64_t id = expr.getValueDouble(); llvm::Value* variantRaw = llvm::UndefValue::get(typVariantRaw); variantRaw = l.builder.CreateInsertValue(variantRaw, llvm::ConstantInt::get(typIdRaw, id), llvm::ArrayRef({0})); const bool flagDoReference = expr.operands.size(); if (flagDoReference) { const ExpandedType& subtyp = ExpandedType(typVariant->__operands.at(id)); llvm::Type* subtypRaw = l.toLLVMType(subtyp); Attachments::put(expr.operands.at(0), subtyp); llvm::Value* subtypValue = process(expr.operands.at(0)); llvm::Type* typStorageRaw = llvm::cast(typVariantRaw)->getElementType(1); llvm::Value* addrAsStorage = l.builder.CreateAlloca(typStorageRaw); llvm::Value* addrAsSubtyp = l.builder.CreateBitOrPointerCast(addrAsStorage, subtypRaw->getPointerTo()); l.builder.CreateStore(subtypValue, addrAsSubtyp); llvm::Value* storageRaw = l.builder.CreateLoad(typStorageRaw, addrAsStorage); variantRaw = l.builder.CreateInsertValue(variantRaw, storageRaw, llvm::ArrayRef({1})); } return variantRaw; } case Operator::SWITCH_VARIANT: { return instructions.compileSwitchVariant(expr, DEFAULT("tmpswitch")); } case Operator::SWITCH_LATE: { assert(false && "Instruction's compilation should've been redirected to interpretation"); return nullptr; } case Operator::SEQUENCE: { return instructions.compileSequence(expr); } case Operator::UNDEF: { llvm::Type* typExprUndef = l.toLLVMType(typeinference::getType(expr, *pass->man->root)); return llvm::UndefValue::get(typExprUndef); } case Operator::INVALID: 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 = l.toLLVMType(typeinference::getType(expr, *pass->man->root)); int literal = expr.getValueDouble(); return llvm::ConstantInt::get(typConst, literal); } case Expression::STRING: { return instructions.compileConstantStringAsPChar(expr.getValueString(), DEFAULT("tmp_str")); }; default: { break; } }; break; default: break; } assert(false && "Can't compile expression"); return 0; } llvm::Value* BasicCodeScopeUnit::compile(const std::string& hintBlockDecl) { LLVMLayer* llvm = pass->man->llvm; if (!hintBlockDecl.empty()) { llvm::BasicBlock *block = llvm::BasicBlock::Create(llvm->llvmContext, hintBlockDecl, function->raw); pass->man->llvm->builder.SetInsertPoint(block); } currentBlockRaw = pass->man->llvm->builder.GetInsertBlock(); Symbol symbScope = Symbol{ScopedSymbol::RetSymbol, scope}; return processSymbol(symbScope); } ICodeScopeUnit::~ICodeScopeUnit() { } IFunctionUnit::~IFunctionUnit() { } llvm::Function* IFunctionUnit::compile() { if (raw != nullptr) return raw; LLVMLayer* llvm = pass->man->llvm; llvm::IRBuilder<>& builder = llvm->builder; string&& functionName = prepareName(); std::vector&& types = prepareSignature(); 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(typeinference::doAutomaticTypeConversion(result, expectedResultType, llvm->builder)); if (blockCurrent) { builder.SetInsertPoint(blockCurrent); } llvm->moveToGarbage(ft); return raw; } ICodeScopeUnit* IFunctionUnit::getScopeUnit(const CodeScope * const scope) { if (__scopes.count(scope)) { auto result = __scopes.at(scope).lock(); if (result) { return result.get(); } } std::shared_ptr unit(pass->buildCodeScopeUnit(scope, this)); if (scope->__parent != nullptr) { auto parentUnit = Decorators::getInterface(getScopeUnit(scope->__parent)); parentUnit->registerChildScope(unit); } else { __orphanedScopes.push_back(unit); } if (!__scopes.emplace(scope, unit).second) { __scopes[scope] = unit; } return unit.get(); } ICodeScopeUnit* IFunctionUnit::getScopeUnit(ManagedScpPtr scope) { return getScopeUnit(&*scope); } ICodeScopeUnit* IFunctionUnit::getEntry() { return getScopeUnit(function->getEntryScope()); } template<> compilation::IFunctionUnit* CompilePassCustomDecorators ::buildFunctionUnit(const ManagedFnPtr& function) { return new BruteFunctionDefault(function, this); } template<> compilation::ICodeScopeUnit* CompilePassCustomDecorators ::buildCodeScopeUnit(const CodeScope * const scope, IFunctionUnit* function) { return new DefaultCodeScopeUnit(scope, function, this); } } // end of compilation compilation::IFunctionUnit* CompilePass::getFunctionUnit(const ManagedFnPtr& function) { unsigned int id = function.id(); if (!functions.count(id)) { compilation::IFunctionUnit* unit = buildFunctionUnit(function); functions.emplace(id, unit); return unit; } return functions.at(id); } void CompilePass::run() { //Initialization: managerTransformations = new xreate::compilation::TransformationsManager(); targetInterpretation = new interpretation::TargetInterpretation(this->man->root, this); //Determine entry function: StaticModel model = man->transcend->query(Config::get("function-entry")); assert(model.size() && "Error: No entry function found"); assert(model.size() == 1 && "Error: Ambiguous entry function"); string nameMain = std::get<0>(TranscendLayer::parse(model.begin()->second)); compilation::IFunctionUnit* unitMain = getFunctionUnit(man->root->findFunction(nameMain)); //Compilation itself: entry = unitMain->compile(); } llvm::Function* CompilePass::getEntryFunction() { assert(entry); return entry; } void CompilePass::prepareQueries(TranscendLayer* transcend) { transcend->registerQuery(new containers::Query(), QueryId::ContainersQuery); transcend->registerQuery(new polymorph::PolymorphQuery(), QueryId::PolymorphQuery); transcend->registerQuery(new latex::LatexQuery(), QueryId::LatexQuery); } } //end of namespace xreate /** * \class xreate::CompilePass * \brief Encapsulates all compilation activities * * xreate::CompilePass iterates over xreate::AST tree and produces executable code fed by data(via xreate::Attachments) gathered by previous passes as well as data via queries(xreate::IQuery) from xreate:TranscendLayer reasoner. * Compilation's done using xreate::LLVMLayer(wrapper over LLVM toolchain) and based on following aspects: * - Containers support. See \ref compilation/containers.h * - Late Conext compilation. See xreate::context::LateContextCompiler2 * - Interpretation support. See xreate::interpretation::TargetInterpretation * - Loop saturation support. See xreate::compilation::TransformerSaturation * - External Code access. See xreate::ExternLayer(wrapper over Clang library) * * \section adaptability_sect Adaptability * xreate::CompilePass's architecture provides adaptability by employing: * - %Function Decorators to alter function-level compilation. See xreate::compilation::IFunctionUnit * - Code Block Decorators to alter code block level compilation. See xreate::compilation::ICodeScopeUnit * Default functionality defined by \ref xreate::compilation::DefaultCodeScopeUnit * - Targets to allow more versitile extensions. * Currently only xreate::interpretation::TargetInterpretation use Targets infrastructure. See xreate::compilation::Target * - %Altering Function invocation. xreate::compilation::ICallStatement * * Client able to construct compiler with desired decorators using xreate::compilation::CompilePassCustomDecorators. * As a handy alias, `CompilePassCustomDecorators` constructs default compiler * */ diff --git a/cpp/src/pass/compilepass.h b/cpp/src/pass/compilepass.h index fd2ab05..7853fb8 100644 --- a/cpp/src/pass/compilepass.h +++ b/cpp/src/pass/compilepass.h @@ -1,208 +1,208 @@ /* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. * * Author: pgess * * compilepass.h */ #ifndef COMPILEPASS_H #define COMPILEPASS_H #include "abstractpass.h" #include "llvm/IR/Function.h" namespace xreate { class TranscendLayer; class CompilePass; class LLVMLayer; namespace interpretation{ class TargetInterpretation; } } namespace xreate { namespace compilation { class ICodeScopeUnit; class IFunctionUnit; class TransformationsManager; /** \brief Holds current position in %AST while traversing*/ struct Context{ ICodeScopeUnit* scope; IFunctionUnit* function; CompilePass* pass; }; /** \brief Interface to specify custom way of function invocation * \details Default implementation is xreate::compilation::RawFnInvocation */ class IFnInvocation { public: /** \brief Returns result of custom function invocation for given arguments*/ virtual llvm::Value* operator() (std::vector&& args, const std::string& hintDecl="") = 0; }; /** \brief Default IFnInvocation implementation */ -class RawFnInvocation: public IFnInvocation{ +class BruteFnInvocation: public IFnInvocation{ public: - RawFnInvocation(llvm::Function* callee, LLVMLayer* l) + BruteFnInvocation(llvm::Function* callee, LLVMLayer* l) : __callee(callee), __calleeTy(callee->getFunctionType()), llvm(l) {} - RawFnInvocation(llvm::Value* callee, llvm::FunctionType* ty, LLVMLayer* l) + BruteFnInvocation(llvm::Value* callee, llvm::FunctionType* ty, LLVMLayer* l) : __callee(callee), __calleeTy(ty), llvm(l) {} /** \brief Makes type conversions and returns LLVM call statement with given arguments*/ llvm::Value* operator() (std::vector&& args, const std::string& hintDecl=""); protected: llvm::Value* __callee; llvm::FunctionType* __calleeTy; LLVMLayer* llvm; }; /** \brief Interface to allow modification of CodeScope compilation * \details Default implementation defined in xreate::compilation::DefaultCodeScopeUnit */ class ICodeScopeUnit{ public: CompilePass* const pass; IFunctionUnit* const function; const CodeScope* const scope; llvm::BasicBlock* currentBlockRaw; ICodeScopeUnit(const CodeScope* const codeScope, IFunctionUnit* f, CompilePass* compilePass); virtual ~ICodeScopeUnit(); 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 Symbol bindArg(llvm::Value* value, std::string&& alias)=0; virtual void bindArg(llvm::Value* value, const ScopedSymbol& s)=0; virtual void reset() = 0; protected: virtual IFnInvocation* findFunction(const Expression& opCall)=0; }; /** \brief Minimal useful ICodeScopeUnit implementation suited for inheritance */ class BasicCodeScopeUnit: public ICodeScopeUnit{ public: BasicCodeScopeUnit(const CodeScope* const codeScope, IFunctionUnit* f, CompilePass* compilePass); llvm::Value* processSymbol(const Symbol& s, std::string hintRetVar="") override; llvm::Value* process(const Expression& expr, const std::string& hintVarDecl="") override; llvm::Value* compile(const std::string& hintBlockDecl="") override; protected: IFnInvocation* findFunction(const Expression& opCall) override; }; /** \brief Interface to specify compilation of %Function */ class IFunctionUnit{ public: IFunctionUnit(ManagedFnPtr f, CompilePass* p): function(f), pass(p) {} virtual ~IFunctionUnit(); llvm::Function* compile(); ICodeScopeUnit* getEntry(); ICodeScopeUnit* getScopeUnit(const CodeScope * const scope); ICodeScopeUnit* getScopeUnit(ManagedScpPtr scope); virtual llvm::Type* prepareResult() = 0; ManagedFnPtr function; llvm::Function* raw = nullptr; protected: CompilePass* pass=nullptr; virtual std::string prepareName() = 0; virtual std::vector prepareSignature() = 0; virtual llvm::Function::arg_iterator prepareBindings() = 0; private: std::map> __scopes; std::list> __orphanedScopes; }; /** \brief Minimal useful IFunctionUnit implementation suited for inheritance */ class BasicFunctionUnit: public IFunctionUnit{ public: BasicFunctionUnit(ManagedFnPtr f, CompilePass* p) : IFunctionUnit(f, p) {} protected: std::string prepareName() override; virtual std::vector prepareSignature() override; virtual llvm::Type* prepareResult() override; virtual llvm::Function::arg_iterator prepareBindings() override; }; } // end of namespace compilation class CompilePass : public AbstractPass { friend class compilation::BasicCodeScopeUnit; friend class compilation::IFunctionUnit; public: compilation::TransformationsManager* managerTransformations; interpretation::TargetInterpretation* targetInterpretation; CompilePass(PassManager* manager): AbstractPass(manager) {} /** \brief Executes compilation process */ void run() override; /**\brief Returns compiled specified %Function * \details Executes function compilation or read cache if it's already done */ compilation::IFunctionUnit* getFunctionUnit(const ManagedFnPtr& function); /**\brief Returns compiled main(entry) %Function in program */ llvm::Function* getEntryFunction(); /** \brief Initializes queries required by compiler. See xreate::IQuery, xreate::TranscendLayer */ static void prepareQueries(TranscendLayer* transcend); protected: virtual compilation::IFunctionUnit* buildFunctionUnit(const ManagedFnPtr& function)=0; virtual compilation::ICodeScopeUnit* buildCodeScopeUnit(const CodeScope* const scope, compilation::IFunctionUnit* function)=0; private: //TODO free `functions` in destructor std::map functions; llvm::Function* entry = 0; }; namespace compilation{ /** \brief Constructs compiler with desired %Function and %Code Scope decorators. See adaptability in xreate::CompilePass*/ template class CompilePassCustomDecorators: public ::xreate::CompilePass{ public: CompilePassCustomDecorators(PassManager* manager): ::xreate::CompilePass(manager) {} virtual compilation::IFunctionUnit* buildFunctionUnit(const ManagedFnPtr& function) override{ return new FUNCTION_DECORATOR(function, this); } virtual compilation::ICodeScopeUnit* buildCodeScopeUnit(const CodeScope* const scope, IFunctionUnit* function) override{ return new SCOPE_DECORATOR(scope, function, this); } }; template<> compilation::IFunctionUnit* CompilePassCustomDecorators::buildFunctionUnit(const ManagedFnPtr& function); template<> compilation::ICodeScopeUnit* CompilePassCustomDecorators::buildCodeScopeUnit(const CodeScope* const scope, IFunctionUnit* function); }} //end of namespace xreate::compilation #endif // COMPILEPASS_H diff --git a/cpp/src/pass/dfapass.cpp b/cpp/src/pass/dfapass.cpp index 26ca47b..de02dc1 100644 --- a/cpp/src/pass/dfapass.cpp +++ b/cpp/src/pass/dfapass.cpp @@ -1,241 +1,266 @@ /* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. * * Author: pgess * * dfapass.cpp */ /** * \file dfapass.h * \brief Data Flow Analysis(DFA) */ //DEBT DFA represent VersionaPass in declarative form using applyDependencies // applyDependencies(expression, context, cache, decl); //DEBT DFA prepare static annotations and represent InterpretationPass in declarative form // applyStaticAnnotations(expression, context, cache, decl); //DEBT DFA Eliminate dfa schemes #include "pass/dfapass.h" #include "xreatemanager.h" #include "transcendlayer.h" #include #include using namespace std; namespace xreate {namespace dfa { DFAPass::DFAPass(PassManager* manager) : AbstractPass(manager) , graph{new DFAGraph()} , transcend(manager->transcend) { } void DFAPass::processCallInstance(const Expression& expr, PassContext context, const SymbolNode& result) { const string &nameCalleeFunction=expr.getValueString(); //TODO implement processFnCall/Uncertain list variantsCalleeFunction=man->root->getFunctionSpecializations(nameCalleeFunction); vector operands; operands.reserve(expr.getOperands().size()); for(const Expression& arg : expr.getOperands()) { operands.push_back(process(arg, context)); } //Set calling relations: DFACallInstanceType type=variantsCalleeFunction.size()>1?WEAK:STRONG; for(ManagedFnPtr function : variantsCalleeFunction) { CodeScope *scopeRemote=function->getEntryScope(); DFACallInstance callInstance; callInstance.fnName=function->getName(); callInstance.type=type; std::vector::const_iterator nodeActual=operands.begin(); for(const std::string &identFormal : scopeRemote->__bindings) { const ScopedSymbol symbolFormal{scopeRemote->__identifiers.at(identFormal), versions::VERSION_NONE}; SymbolPacked symbolFormalPacked=transcend->pack(Symbol{symbolFormal, scopeRemote}, nameCalleeFunction+":"+identFormal); callInstance.args.push_back(std::make_pair(symbolFormalPacked, *nodeActual)); ++nodeActual; } callInstance.retActual=result; SymbolNode retFormal=SymbolNode(transcend->pack(Symbol{ScopedSymbol::RetSymbol, scopeRemote}, nameCalleeFunction+":[ret]")); graph->addCallInstance(std::move(callInstance)); } } void DFAPass::processDependencies(const SymbolNode& node, const Expression& expression, PassContext context, ProcessingCache& cache) { cache.operands.reserve(expression.getOperands().size()); for(const Expression &op : expression.getOperands()) { const SymbolNode& subnodeOperand=process(op, context); cache.operands.push_back(subnodeOperand); graph->addDependency(node, subnodeOperand); } cache.blocks.reserve(expression.blocks.size()); for(CodeScope* block : expression.blocks) { const SymbolNode& subnodeBlock=process(block, context); cache.blocks.push_back(subnodeBlock); graph->addDependency(node, subnodeBlock); } } void DFAPass::processAnnotations(const Expression& expression, PassContext context, const SymbolNode& ident){ for (const pair& tag : expression.tags){ graph->printInplaceAnnotation(ident, tag.second); } } SymbolNode DFAPass::process(const Expression& expression, PassContext context, const std::string& varDecl) { SymbolNode result; if(Attachments::exists(expression)){ Symbol varSymbol=Attachments::get(expression); result=transcend->pack(varSymbol, varDecl); } else if(expression.__state==Expression::IDENT&&expression.tags.size()==0){ Symbol varSymbol=Attachments::get(expression); result=transcend->pack(varSymbol, expression.getValueString()); } else { result=SymbolAnonymous{expression.id}; } processAnnotations(expression, context, result); + ProcessingCache cache; switch(expression.__state) { case Expression::COMPOUND: { switch(expression.op) { case Operator::CALL: { processCallInstance(expression, context, result); break; } case Operator::IF: { const SymbolNode& scopeA=process(expression.blocks.front(), context, "ifTrue" + std::to_string(expression.id)); const SymbolNode& scopeB=process(expression.blocks.back(), context, "ifFalse" + std::to_string(expression.id)); const SymbolNode& condition=process(expression.operands.at(0), context); graph->addDependency(result, scopeA); graph->addDependency(result, scopeB); graph->addDependency(result, condition); graph->printWeakAlias(result, scopeA); graph->printWeakAlias(result, scopeB); break; } case Operator::SWITCH: case Operator::SWITCH_VARIANT: { for(CodeScope* block : expression.blocks) { const SymbolNode& subnodeBlock=process(block, context, "case"+to_string(block->getBody().id)); graph->addDependency(result, subnodeBlock); graph->printWeakAlias(result, subnodeBlock); } const SymbolNode& condition=process(expression.operands.at(0), context); graph->addDependency(result, condition); break; } + case Operator::MAP: + processDependencies(result, expression, context, cache); + graph->printOperator(Operator::MAP, {result, cache.operands.at(0), cache.blocks.at(0)}); + break; + + case Operator::FOLD: + processDependencies(result, expression, context, cache); + graph->printOperator(Operator::FOLD, {result, cache.operands.at(0), cache.operands.at(1), cache.blocks.at(0)}); + break; + + case Operator::LIST: + processDependencies(result, expression, context, cache); + graph->printOperator(Operator::LIST, {result}, expression.getOperands().size()); + break; + + case Operator::LIST_RANGE: + processDependencies(result, expression, context, cache); + graph->printOperator(Operator::LIST_RANGE, {result}); + break; + + case Operator::INDEX: + processDependencies(result, expression, context, cache); + graph->printOperator(Operator::INDEX, {result, cache.operands.at(0), cache.operands.at(1)}); + break; + default: { - ProcessingCache cache; processDependencies(result, expression, context, cache); break; } } break; } case Expression::IDENT: { SymbolNode symbIdent=AbstractPass::process(expression, context, varDecl); if(!(result==symbIdent)){ graph->addDependency(result, symbIdent); graph->printAlias(result, symbIdent); } break; } case Expression::NUMBER: case Expression::STRING: { break; } case Expression::INVALID: case Expression::BINDING: { assert(false); break; } } return result; } SymbolNode DFAPass::process(CodeScope* scope, PassContext context, const std::string& hintBlockDecl) { if (!hintBlockDecl.empty()) { Symbol symbRet{ScopedSymbol::RetSymbol, scope}; transcend->pack(symbRet, hintBlockDecl + ":[ret]"); } for(const std::string& binding : scope->__bindings) { Symbol bindingSymb{scope->getSymbol(binding), scope}; SymbolPacked bindingSymbP=transcend->pack(bindingSymb, binding); getSymbolCache().setCachedValue(bindingSymb, SymbolNode(bindingSymbP)); processAnnotations(scope->getDefinition(bindingSymb), context, SymbolNode(bindingSymbP)); } return AbstractPass::process(scope, context, hintBlockDecl); } SymbolNode DFAPass::process(ManagedFnPtr function) { transcend->pack(Symbol{ScopedSymbol::RetSymbol, function->getEntryScope()}, function->getName()+to_string(function.id())+":[ret]"); SymbolNode result=AbstractPass::process(function); graph->printFunctionRet(function, result); return result; } void DFAPass::finish() { transcend->registerReport(graph); //Declare symbols: graph->printSymbols(transcend); AbstractPass::finish(); } } //end of namespace dfa template<> SymbolNode defaultValue() { assert(false); } } //end of xreate namespace /** * \class xreate::dfa::DFAPass * \details Provides DFA, important analysis for reasoning. Iterates over AST and stores collected data in DFAGraph */ diff --git a/cpp/src/query/containers.cpp b/cpp/src/query/containers.cpp index b08c36b..543fc00 100644 --- a/cpp/src/query/containers.cpp +++ b/cpp/src/query/containers.cpp @@ -1,178 +1,119 @@ /* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. * * Author: pgess * * containers.cpp * Created on 3/14/15. */ /** * \file query/containers.h * \brief Represents reasoner's solution on [Container implementations](/w/concepts/containers) */ #include #include "query/containers.h" using namespace std; using namespace xreate::containers; using namespace xreate; Implementation Query::queryImplementation(xreate::Symbol const &s) { if (Attachments::exists(s)) { return Attachments::get(s); } return Implementation::create(s); } Query::Query(){ Attachments::init(); } void Query::init(TranscendLayer* transcend) { - if (flagIsDataLoaded) return; - - map prototypes; - map roots; - - //Read all proto data - auto range = transcend->query(Config::get("containers.id.prototypes")); - if (range.size()) - for(auto atom: range) { - auto data = TranscendLayer::parse(atom.second); - Symbol root = transcend->unpack(get<0> (data)); - Symbol prototype = transcend->unpack(get<1> (data)); - - prototypes[root] = prototype; - } + if (flagDataIsLoaded) return; //Fill implementation data for a data sources: - range = transcend->query(Config::get("containers.id.implementations")); + auto range = transcend->query(Config::get("containers.id.implementations")); if (range.size()) for(auto atom: range) { - auto data = TranscendLayer::parse(atom.second); + auto data = TranscendLayer::parse(atom.second); Symbol var = transcend->unpack(get<0>(data)); - string implSerialized = get<1>(data); + string implStr = get<1>(data).name().c_str(); - //data source, has no prototypes: - if (!prototypes.count(var)) + if (implStr == Config::get("containers.impl.solid")) { - Implementation impl = Implementation::create(var); - Attachments::put(var, move(impl)); - continue; - } - - roots.emplace(move(var), move(implSerialized)); - } - - //fill implementation data for a cluster roots - for (const pair & root: roots) - { - Symbol prototype = prototypes[root.first]; - - while (prototypes.count(prototype)) { - prototype = prototypes.at(prototype); - } - - Attachments::put(root.first, Implementation(Attachments::get(prototype))); - } - - // read cluster data and fill implementation data for cluster members - range = transcend->query(Config::get("containers.id.clusters")); - if (range.size()) - for(auto atom: range) - { - auto info = TranscendLayer::parse(atom.second); + auto size = TranscendLayer::parse(get<1>(data)); + Attachments::put(var, {SOLID, ImplementationRec{get<0>(size)}}); - Symbol root = transcend->unpack(get<0>(info)); - Symbol child = transcend->unpack(get<1>(info)); + } else if (implStr == Config::get("containers.impl.onthefly")) { + Attachments::put(var, {ON_THE_FLY, ImplementationRec{var}}); - if (!(child == root) && (Attachments::exists(root))) { - Implementation rootImpl = Attachments::get(root); - Attachments::put(child, move(rootImpl)); + } else { + assert(false && "Unable to determine proper implementation for the symbol"); } } - flagIsDataLoaded = true; + flagDataIsLoaded = true; } -//static ImplementationData* create(Symbol var, std::string implSerialized, const ImplementationData* implPrototype); - Implementation Implementation::create(const Symbol &var) { //TODO review implementation determination strategy Expression varDecl = CodeScope::getDefinition(var); switch (varDecl.op) { case Operator::LIST_RANGE: { ImplementationRec rec{var}; return {ON_THE_FLY, rec}; } case Operator::LIST: { return {SOLID, ImplementationRec {varDecl.getOperands().size()}}; } default: break; }; ImplementationLinkedList ill(var); if (ill){ return ill.getImplementationData(); } assert(false && "Unable to determine proper implementation for the symbol"); return Implementation(); } -Implementation -Implementation::create(const Symbol& var, const std::string& implSerialized) -{ - Expression varDecl = CodeScope::getDefinition(var); - if (implSerialized == Config::get("containers.impl.solid")) - { - return {SOLID, ImplementationRec{varDecl.operands.size()}}; - - } else if (implSerialized == Config::get("containers.impl.onthefly")) { - return {ON_THE_FLY, ImplementationRec{var}}; - } - - assert(false && "unable to determine proper implementation for the symbol"); - return Implementation(); -} - - ImplementationLinkedList::ImplementationLinkedList(const Symbol& source) : flagIsValid(false), s(source){ const Expression& sourceExpr = CodeScope::getDefinition(source); if (sourceExpr.tags.count(Config::get("containers.id.linkedlist"))){ flagIsValid = true; Expression tagLinkedlist = sourceExpr.tags.at(Config::get("containers.id.linkedlist")); assert(tagLinkedlist.operands.size() == 2); fieldPointer = tagLinkedlist.operands.at(0).getValueString(); terminator = tagLinkedlist.operands.at(1); } } ImplementationLinkedList:: operator bool () const{ return flagIsValid; } Implementation ImplementationLinkedList::getImplementationData() const { return {ON_THE_FLY, ImplementationRec{s}}; } diff --git a/cpp/src/query/containers.h b/cpp/src/query/containers.h index 8a814f3..ab8de85 100644 --- a/cpp/src/query/containers.h +++ b/cpp/src/query/containers.h @@ -1,93 +1,92 @@ /* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. * * Author: pgess * * containers.h * Created on 3/14/15. */ #ifndef _XREATE_CONTAINERSQUERY_H_ #define _XREATE_CONTAINERSQUERY_H_ #include "xreatemanager.h" #include "transcendlayer.h" #include namespace xreate { namespace containers { enum ImplementationType {SOLID, ON_THE_FLY, LINKED_LIST}; template struct ImplementationRec; template<> struct ImplementationRec { size_t size; }; template<> struct ImplementationRec{ Symbol source; }; struct Implementation; struct ImplementationLinkedList { bool flagIsValid; std::string fieldPointer; Expression terminator; ImplementationLinkedList(const Symbol& source); operator bool() const; Implementation getImplementationData() const; private: Symbol s; }; struct Implementation { typedef boost::variant, ImplementationRec> Variant; ImplementationType impl; Variant data; static Implementation create(const Symbol &var); static Implementation create(const Symbol& var, const std::string &implSerialized); - static Implementation create(const Symbol& var, const Implementation& proto); template const ImplementationRec& extract() const{ const ImplementationRec& rec = boost::get>(data); return rec; } }; /** \brief Extracts solution about container implementation * \sa xreate::containers::Iterator */ class Query : public xreate::IQuery { public: static Implementation queryImplementation(xreate::Symbol const &s); void init(TranscendLayer* transcend); Query(); ~Query(){} private: - bool flagIsDataLoaded = false; + bool flagDataIsLoaded = false; PassManager *man; }; } template<> struct AttachmentsDict { typedef containers::Implementation Data; static const unsigned int key = 1; }; } #endif //_XREATE_CONTAINERSQUERY_H_ diff --git a/cpp/src/query/latex.cpp b/cpp/src/query/latex.cpp index 04a7826..6970cc7 100644 --- a/cpp/src/query/latex.cpp +++ b/cpp/src/query/latex.cpp @@ -1,98 +1,101 @@ /* * This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ /* * Author: pgess * Created on June 25, 2018, 12:14 PM * * \file latex.cpp * \brief latex */ #include "query/latex.h" #include "aux/transcend-decorators.h" using namespace std; using namespace xreate::latereasoning; namespace xreate{ namespace latex{ void LatexQuery::init(TranscendLayer* transcend) { __transcend = transcend; //schema: latex_fn_demand(Fn, Subject) StaticModel data = __transcend->query("latex_fn_demand_ordered"); for(const auto& entry : data) { string fnName, subject; size_t id; tie(fnName, subject, id) = __transcend->parse(entry.second); __demand[fnName].resize(std::max(__demand[fnName].size(), id+1)); __demand[fnName][id] = subject; } //schema: latex_registered_subjects(Subject, Decision) data = __transcend->query("latex_registered_subjects"); for(const auto& entry : data) { string subject; Gringo::Symbol decision; tie(subject, decision) = __transcend->parse(entry.second); __domains[subject].push_back(decision); } //schema: latex_decision(Scope, Subject, Decision) data = __transcend->query("latex_decision"); for(const auto& entry : data) { ScopePacked scope; string subject; Gringo::Symbol decision; tie(scope, subject, decision) = __transcend->parse(entry.second); __decisions[make_pair(scope, subject)] = entry.second; } - //schema: latex_parameters_group_offset(int) - data = __transcend->query("latex_parameters_group_offset"); - LatexParametersOffset = std::get<0>(__transcend->parse(data.begin()->second)); + //schema: latex_parameters_offset(int) + //Override parameter from transcend + data = __transcend->query("latex_parameters_offset"); + if(data.size()) { + LatexParametersOffset = std::get<0>(__transcend->parse(data.begin()->second)); + } auto transcendLate = Decorators::getInterface(__transcend); //Later decisions. schema: Scope, Subject, Decision LateAnnotationsGroup group = transcendLate->queryLate("latex_decision"); for (auto entry: group.annotations) { auto key = __transcend->parse(entry.first); __decisionsLate.emplace(make_pair(get<0>(key), get<1>(key)), entry.second); } } Demand LatexQuery::getFnDemand(const std::string& fnName) { if (!__demand.count(fnName)) return Demand(); return __demand.at(fnName); } latereasoning::LateAnnotation LatexQuery::getDecision(const std::string& subject, const CodeScope* scopeCaller) { ScopePacked scopeP = __transcend->pack(scopeCaller); if(__decisions.count(make_pair(scopeP, subject))){ //found static decision return LateAnnotation(__decisions.at(make_pair(scopeP, subject))); } return __decisionsLate.at(make_pair(scopeP, subject)); } std::list LatexQuery::getSubjectDomain(const std::string& subject) { assert(__domains.count(subject)); return __domains.at(subject); } } -} \ No newline at end of file +} diff --git a/cpp/src/query/latex.h b/cpp/src/query/latex.h index 1239ae9..42e5d9e 100644 --- a/cpp/src/query/latex.h +++ b/cpp/src/query/latex.h @@ -1,46 +1,46 @@ /* * This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ /** * \file query/context.h * \brief Represents reasoner's solution on [Context](/w/concepts/context) * * \class xreate::latex::LatexQuery */ #ifndef LATEXQUERY_H #define LATEXQUERY_H #include "transcendlayer.h" #include "aux/latereasoning.h" #include namespace xreate{ namespace latex{ typedef std::vector Demand; class LatexQuery: public IQuery{ public: - VNameId LatexParametersOffset; + VNameId LatexParametersOffset = 1000; //Default value. Overriden by `latex_parameters_offset` from transcend Demand getFnDemand(const std::string& fnName); latereasoning::LateAnnotation getDecision(const std::string& subject, const CodeScope* scopeCaller); std::list getSubjectDomain(const std::string& subject); void init(TranscendLayer* transcend); private: TranscendLayer* __transcend; std::map __demand; std::map, Gringo::Symbol> __decisions; std::map, latereasoning::LateAnnotation> __decisionsLate; std::map> __domains; }; } } -#endif \ No newline at end of file +#endif diff --git a/cpp/src/transcendlayer.cpp b/cpp/src/transcendlayer.cpp index e960481..26ced04 100644 --- a/cpp/src/transcendlayer.cpp +++ b/cpp/src/transcendlayer.cpp @@ -1,496 +1,496 @@ /* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. * * Author: pgess * File: transcendlayer.cpp */ /** * \file transcendlayer.h * \brief Reasoner. Wrapper over the external Clasp reasoner library */ #include "transcendlayer.h" #include "analysis/utils.h" #include "utils.h" #include #include #include #include #include #include using namespace std; //TODO escape identifiers started with upper case symbol namespace xreate{ bool operator==(const SymbolAnonymous& s1, const SymbolAnonymous& s2) { return s1.id == s2.id && s1.flagIsUsed == s2.flagIsUsed; } struct VisitorSymbolNodeHash : public boost::static_visitor{ std::size_t operator()(const xreate::SymbolPacked& node) const noexcept { return 2 * (node.identifier + 3 * node.scope + 5 * std::abs(node.version)); } std::size_t operator()(const xreate::SymbolAnonymous& node) const noexcept { return 7 * node.id; } } ; } namespace std{ std::size_t hash::operator()(xreate::SymbolNode const& s) const noexcept { return boost::apply_visitor(xreate::VisitorSymbolNodeHash(), s); } std::size_t hash::operator()(xreate::SymbolGeneralized const& s) const noexcept { return xreate::AttachmentsId::getId(s); } } namespace xreate{ void TranscendLayer::printWarnings(std::ostream& out) { const std::string warningTag = "warning"; auto warningsModel = query(warningTag); if(warningsModel.size()) for(auto warning : warningsModel) { unsigned int warningId; Gringo::Symbol params; std::tie(warningId, params) = parse(warning.second); cout << "Warning: " << __warnings.at(warningId) << " "; params.print(out); out << params; } } bool TranscendLayer::processSolution(Gringo::Model const &model) { cout << "Model: " << endl; const string& atomBindVar = Config::get("transcend.bindings.variable"); const string& atomBindFunc = Config::get("transcend.bindings.function"); const string& atomBindScope = Config::get("transcend.bindings.scope"); for(Gringo::Symbol atom : model.atoms(clingo_show_type_atoms)) { atom.print(cout); cout << " | " << endl; string atomName(atom.name().c_str()); if(atomName == atomBindVar || atomName == atomBindFunc || atomName == atomBindScope) { string atomAlias = std::get<1>(parse(atom)).name().c_str(); __model.emplace(atomAlias, atom); continue; } __model.emplace(atomName, atom); } return true; } void TranscendLayer::registerReport(IAnalysisReport * report) { __reports.push_back(report); } void TranscendLayer::runReports() { for(IAnalysisReport* report : __reports) { report->print(__partGeneral); delete report; } __reports.clear(); } void TranscendLayer::addRuleWarning(const RuleWarning & rule) { //__partGeneral << rule << endl; list domains; boost::format formatDef("%1%(%2%)"); std::transform(rule.__args.begin(), rule.__args.end(), std::inserter(domains, domains.begin()), [&formatDef](const std::pair &argument) { string domain; switch(argument.second) { case DomainAnnotation::FUNCTION: domain = "function"; break; case DomainAnnotation::VARIABLE: domain = "variable"; break; } return boost::str(formatDef % domain % argument.first); }); list vars; std::transform(rule.__args.begin(), rule.__args.end(), std::inserter(vars, vars.begin()), [](const std::pair &argument) { return argument.first.c_str(); }); list> guardsRaw; std::transform(rule.__guards.begin(), rule.__guards.end(), std::inserter(guardsRaw, guardsRaw.begin()), [this](const Expression & guard) { return xreate::analysis::compile(guard); }); const list& guards = xreate::analysis::multiplyLists(std::move(guardsRaw)); list &&branches = xreate::analysis::compileNeg(rule.__condition); boost::format formatWarning("warning(%1%, (%2%)):- %3%, %4%, %5%."); for(const string &guardsJoined : guards) for(const string &branch : branches) { unsigned int hook = registerWarning(string(rule.__message)); __partGeneral << formatWarning % (hook) % (boost::algorithm::join(vars, ", ")) % (branch) % (guardsJoined) % (boost::algorithm::join(domains, ", ")) << endl; } } unsigned int TranscendLayer::registerWarning(std::string && message) { static int warningId = 0; __warnings.emplace(warningId, message); return warningId++; } void TranscendLayer::involveImports() { ostream &out = __partGeneral; if(ast) for(string fn : ast->__rawImports) { std::ifstream file(fn); if(!file) { std::cout << "Can't process script file: " << fn << std::endl; assert(false); } while(!file.eof()) { string line; std::getline(file, line); out << line << endl; } } } void TranscendLayer::addRawScript(std::string && script) { __partGeneral << script; } void TranscendLayer::run() { involveImports(); runReports(); ostringstream program; program << __partTags.str() << __partGeneral.str(); cout << FYEL(program.str()) << endl; std::vector args{"clingo", nullptr}; DefaultGringoModule moduleDefault; Gringo::Scripts scriptsDefault(moduleDefault); ClingoLib ctl(scriptsDefault, 0, args.data(), { }, 0); ctl.add("base",{}, program.str()); ctl.ground({ {"base", {}} }, nullptr); // solve Gringo::SolveResult result = ctl.solve([this](Gringo::Model const &model) { this->processSolution(model); return true; }, { }); if(result.satisfiable() == Gringo::SolveResult::Satisfiable) { cout << FGRN("SUCCESSFULLY") << endl; } else { cout << FRED("UNSUCCESSFULLY") << endl; } // invoke all query plugins to process solution for(auto q : __queries) { q.second->init(this); } } TranscendLayer::TranscendLayer() : ast(nullptr) { } StaticModel TranscendLayer::query(const std::string & atom) const { StaticModel result; if (! __model.count(atom)) { return result; } auto currentDataRange = __model.equal_range(atom); std::copy(currentDataRange.first, currentDataRange.second, std::inserter(result, result.end())); return result; } ScopePacked TranscendLayer::pack(const CodeScope * const scope) { auto pos = __indexScopes.emplace(scope, __indexScopes.size()); if(pos.second) __registryScopes.push_back(scope); return pos.first->second; } size_t TranscendLayer::getScopesCount() const { return __registryScopes.size(); } SymbolPacked TranscendLayer::pack(const Symbol& symbol, std::string hintSymbolName) { SymbolPacked result(symbol.identifier.id, symbol.identifier.version, pack(symbol.scope)); __indexSymbolNameHints.emplace(result, hintSymbolName); return result; } Symbol TranscendLayer::unpack(const SymbolPacked & symbol) const { return Symbol{ScopedSymbol {symbol.identifier, symbol.version}, __registryScopes[symbol.scope]}; }; std::string TranscendLayer::getHintForPackedSymbol(const SymbolPacked & symbol) { auto result = __indexSymbolNameHints.find(symbol); return(result == __indexSymbolNameHints.end()) ? "" : result->second; } IQuery * TranscendLayer::registerQuery(IQuery *query, const QueryId & id) { return __queries.emplace(id, query).first->second; } IQuery * TranscendLayer::getQuery(const QueryId & id) { assert(__queries.count(id) && "Undefined query"); return __queries.at(id); } class VisitorUnpackSymbol : public boost::static_visitor{ public: VisitorUnpackSymbol(const TranscendLayer* transcend) : __transcend(transcend) { } SymbolGeneralized operator()(const SymbolPacked& symbol) const { return __transcend->unpack(symbol); } SymbolGeneralized operator()(const SymbolAnonymous& symbol) const { return symbol; } private: const TranscendLayer* __transcend; } ; class VisitorPackSymbol : public boost::static_visitor{ public: VisitorPackSymbol(TranscendLayer* transcend, const std::string& hintSymbolName) : __transcend(transcend), __hint(hintSymbolName) { } SymbolNode operator()(const Symbol& symbol) const { return __transcend->pack(symbol, __hint); } SymbolNode operator()(const SymbolAnonymous& symbol) const { return symbol; } private: TranscendLayer* __transcend; std::string __hint; } ; SymbolNode TranscendLayer::pack(const SymbolGeneralized& symbol, const std::string & hintSymbolName) { return boost::apply_visitor(VisitorPackSymbol(this, hintSymbolName), symbol); } SymbolGeneralized TranscendLayer::unpack(const SymbolNode & symbol) const { return boost::apply_visitor(VisitorUnpackSymbol(this), symbol); } bool operator==(const SymbolPacked& s1, const SymbolPacked & s2) { return s1.identifier == s2.identifier && s1.scope == s2.scope; } bool operator<(const SymbolPacked& s1, const SymbolPacked & s2) { return s1.scope < s2.scope || (s1.scope == s2.scope && s1.identifier < s2.identifier); } Expression ParseImplAtom ::get(const Gringo::Symbol & atom) { switch(atom.type()) { case Gringo::SymbolType::Num: return Expression(atom.num()); case Gringo::SymbolType::Str: return Expression(Atom(std::string(atom.string().c_str()))); case Gringo::SymbolType::Fun: { //FUNC Expression result(Operator::CALL,{Expression(Atom(std::string(atom.name().c_str())))}); for(const Gringo::Symbol& arg : atom.args()) { result.addArg(ParseImplAtom::get(arg)); } return result; } default: { assert(false); } } } int ParseImplAtom ::get(const Gringo::Symbol & atom) { switch(atom.type()) { case Gringo::SymbolType::Num: return atom.num(); default: break; } assert(false && "Inappropriate symbol type"); } std::string ParseImplAtom ::get(const Gringo::Symbol & atom) { switch(atom.type()) { case Gringo::SymbolType::Str: return atom.string().c_str(); case Gringo::SymbolType::Fun: return atom.name().c_str(); default: break; } assert(false && "Inappropriate symbol type"); } SymbolPacked ParseImplAtom ::get(const Gringo::Symbol & atom) { auto result = TranscendLayer::parse(atom); return SymbolPacked(std::get<0>(result), std::get<1>(result), std::get<2>(result)); }; Gringo::Symbol ParseImplAtom ::get(const Gringo::Symbol & atom) { return atom; } SymbolNode ParseImplAtom ::get(const Gringo::Symbol & atom) { assert(atom.type() == Gringo::SymbolType::Fun && "Inappropriate symbol type"); if(atom.name() == "a") { return SymbolAnonymous{(unsigned int) std::get<0>(TranscendLayer::parse(atom))}; } else if(atom.name() == "s") { return ParseImplAtom::get(atom); } assert(false && "Wrong symbol format"); } class VisitorSymbolId : public boost::static_visitor{ public: unsigned int operator()(const Symbol& symbol) const { return AttachmentsId::getId(symbol); } unsigned int operator()(const SymbolAnonymous& symbol) const { return symbol.id; } } ; unsigned int AttachmentsId ::getId(const SymbolGeneralized & symbol) { return boost::apply_visitor(VisitorSymbolId(), symbol); } } //end of xreate namespace /** * \class xreate::TranscendLayer * \brief Reasoning and logic Solver. * * Wraps external brilliant fantastic tool [Clasp solver](https://potassco.org/clasp/) * * For building *logic program* for reasoning TranscendLayer takes input from: * - Raw scripts. Client could append arbitrary ASP script to _logic program_. \ref addRawScript() * - Includes. There is possibility to specify external files with ASP scripts * to append to _logic program_. \ref involveImports() (private member) * - Diagnostic rules. Rules that produce diagnostic messages during * compilation(warnings) or even able to halt compilation with errors. * addRuleWarning(), \ref registerWarning() * - DFA data. \ref setDFAData() * - CFA data. \ref setCFAData() - * - Dominators Analysis. See xreate::dominators::DominatorsTreeAnalysisProvider. + * - Dominators Analysis. See xreate::dominators::DominatorsAnalysisProvider. * Executed by \ref run() * - Context rules. See xreate::ContextRule and general [Context Explanation](/w/concepts/context) * * Data sources implement xreate::IAnalysisReport. Generally, input could be loosely divided into three categories: * - *Internally derived* data. CFA, DFA, Dominators analyses *automatically* feed reasoner by * useful insights about data, structure and algorithms of a program * - *User provided* data. CFA, DFA, Diagnostic/Context rules feed reasoner by * annotations Developer specifically provides manually * - *External* data. Raw scripts and includes feed reasoner with third-party data * related to a different aspects of a program possibly produced by external analyzers * * Once TranscendLayer got input from all providers and logic program is fully constructed * it runs external Clasp reasoner and receives back desired solutions. * * Output of the external Clasp reasoner is recognized and accessed via *queries*. * IQuery represents an interface between reasoner's output and rest of Xreate. * Each query inherits xreate::IQuery interface. Currently there are queries as follows: * - xreate::containers::Query to catch solutions regarding Containers implementation. See [Containers Explanation](/w/concepts/containers) * - xreate::context::ContextQuery to catch solution regarding Context. See [Context Explanation](/w/concepts/context) * - * \sa See xreate::dfa::DFAPass, xreate::cfa::CFAPass, xreate::IQuery, xreate::IAnalysisReport, xreate::dominators::DominatorsTreeAnalysisProvider + * \sa See xreate::dfa::DFAPass, xreate::cfa::CFAPass, xreate::IQuery, xreate::IAnalysisReport, xreate::dominators::DominatorsAnalysisProvider */ diff --git a/cpp/tests/cfa.cpp b/cpp/tests/cfa.cpp index 325ee81..fff0a97 100644 --- a/cpp/tests/cfa.cpp +++ b/cpp/tests/cfa.cpp @@ -1,224 +1,248 @@ /* Any copyright is dedicated to the Public Domain. * http://creativecommons.org/publicdomain/zero/1.0/ * * cfa.cpp * * Created on: Jul 17, 2015 * Author: pgess */ #include "xreatemanager.h" #include "pass/dfapass.h" #include "pass/cfapass.h" -#include "analysis/DominatorsTreeAnalysisProvider.h" +#include "analysis/DominatorsAnalysisProvider.h" #include "analysis/cfagraph.h" #include "pass/compilepass.h" #include "compilation/scopedecorators.h" #include "gtest/gtest.h" #include "aux/xreatemanager-decorators.h" #include #include #include using namespace xreate; using namespace xreate::cfa; using namespace std; TEST(CFA, testFunctionAnnotations) { string&& program = "f2 = function::int; annotationF2 {\n" " 0\n" "}\n" "\n" "f1 = function:: int; entry; annotationF1 {\n" " f2() + 10\n" "}"; details::tier1::XreateManager* man = details::tier1::XreateManager::prepare(move(program)); man->analyse(); StaticModel answer = man->transcend->query("annotationF1"); EXPECT_EQ(1, answer.size()); answer = man->transcend->query("annotationF2"); EXPECT_EQ(1, answer.size()); } TEST(CFA, testLoopContextExists) { details::tier1::XreateManager* man = details::tier1::XreateManager::prepare ( "interface(cfa){\n" " operator fold:: annotation1.\n" "}\n" "\n" "main = function:: int; entry {\n" " x = [1..10]:: [int].\n" " sum = loop fold (x->el:: int, 0->sum):: int {\n" " el + sum + f1()\n" " }. \n" " sum\n" "}" - "case context:: annotation1 {" + "guard:: annotation1 {" " f1 = function::int {\n" " x = 0:: int. " " x\n" " }" "}" ); man->analyse(); StaticModel model = man->transcend->query("annotation1"); ScopePacked scopeIdActual = std::get<0>(TranscendLayer::parse(model.begin()->second)); CodeScope* scopeEntry = man->root->findFunction("main")->getEntryScope(); const Expression& exprSum = scopeEntry->getDefinition(scopeEntry->getSymbol("sum")); CodeScope* scopeExpected = exprSum.blocks.front(); ScopePacked scopeIdExpected = man->transcend->pack(scopeExpected); ASSERT_EQ(scopeIdExpected, scopeIdActual); } TEST(CFA, DependenciesFnCall) { details::tier2::XreateManager* man = details::tier2::XreateManager::prepare( R"Code( a = function::int{ seq {x = 0:: int. x} {x = b():: int. x}::int } b = function::int {y = 0. y} )Code"); CodeScope* scopeSeq1 = man->root->findFunction("a")->getEntryScope()->getBody().blocks.front(); CodeScope* scopeSeq2 = *(++man->root->findFunction("a")->getEntryScope()->getBody().blocks.begin()); CodeScope* scopeB = man->root->findFunction("b")->getEntryScope(); ScopePacked psSeq1 = man->transcend->pack(scopeSeq1); ScopePacked psSeq2 = man->transcend->pack(scopeSeq2); ScopePacked psB = man->transcend->pack(scopeB); CFAPass* pass = new CFAPass(man); man->registerPass(pass, PassId::CFAPass); man->executePasses(); const CFAGraph* report = dynamic_cast (man->getPassById(PassId::CFAPass))->getReport(); auto dependencies = report->__dependencyRelations; delete pass; ASSERT_EQ(1, dependencies.count(psSeq2)); ASSERT_EQ(1, dependencies.count(psB)); } TEST(CFA, DependenciesChildScope) { details::tier2::XreateManager* man = details::tier2::XreateManager::prepare( R"Code( a = function::int{ seq {x = 0:: int. x} {x=0::int. if(x>0)::int{1} else {0}}::int } )Code"); CodeScope* scopeSeq1 = man->root->findFunction("a")->getEntryScope()->getBody().blocks.front(); CodeScope* scopeSeq2 = *(++man->root->findFunction("a")->getEntryScope()->getBody().blocks.begin()); CodeScope* scopeIf1 = scopeSeq2->getBody().blocks.front(); CodeScope* scopeIf2 = *(++scopeSeq2->getBody().blocks.begin()); ScopePacked psSeq1 = man->transcend->pack(scopeSeq1); ScopePacked psSeq2 = man->transcend->pack(scopeSeq2); ScopePacked psIf1 = man->transcend->pack(scopeIf1); ScopePacked psIf2 = man->transcend->pack(scopeIf2); CFAPass* pass = new CFAPass(man); man->registerPass(pass, PassId::CFAPass); man->executePasses(); const CFAGraph* report = dynamic_cast (man->getPassById(PassId::CFAPass))->getReport(); auto dependencies = report->__dependencyRelations; delete pass; ASSERT_EQ(0, dependencies.count(psSeq1)); ASSERT_EQ(1, dependencies.count(psSeq2)); ASSERT_EQ(1, dependencies.count(psIf1)); ASSERT_EQ(1, dependencies.count(psIf2)); for(auto rec : dependencies) { std::cout << rec.first << " " << rec.second << std::endl; } } -TEST(CFA, DomReportOneRoot) { +TEST(CFA, Dominators1){ + std::multimap dataScopes = { + {1, 0}, {2, 0}, {3, 1}, {4, 1}, {4, 2} + }; + + dominators::DominatorsAnalysisProvider domProvider; + boost::scoped_ptr adapter(dominators::CFAGraphAdapter::build(dataScopes)); + domProvider.run(adapter.get()); + + dominators::DominatorsAnalysisProvider::Dominators expectedFDom= { + {0, {0, 9}} + ,{1, {1, 4}} + ,{2, {7, 8}} + ,{3, {2, 3}} + ,{4, {5, 6}} + }; + + dominators::DominatorsAnalysisProvider::Dominators expectedPostDom= { + {0, {5, 6}} + ,{1, {3, 4}} + ,{2, {8, 9}} + ,{3, {1, 2}} + ,{4, {7, 10}} + }; + + ASSERT_EQ(expectedFDom, domProvider.getForwardDominators()); + ASSERT_EQ(expectedPostDom, domProvider.getPostDominators()); +} + +TEST(CFA, Dominators2) { std::string program = R"CODE( a = function:: int; entry{ seq {x = 0:: int. x} {x = 1:: int. x}::int } )CODE"; std::unique_ptr man(details::tier2::XreateManager::prepare(move(program))); CFAPass* pass = new CFAPass(man.get()); man->registerPass(pass, PassId::CFAPass); pass->run(); ScopePacked scope1 = man->transcend->pack(man->root->findFunction("a")->getEntryScope()->getBody().blocks.front()); ScopePacked scope2 = man->transcend->pack(*++man->root->findFunction("a")->getEntryScope()->getBody().blocks.begin()); - dominators::DominatorsTreeAnalysisProvider* providerDomAnalysis = new dominators::DominatorsTreeAnalysisProvider(); - providerDomAnalysis->run(pass->getReport()); + dominators::DominatorsAnalysisProvider* providerDomAnalysis = new dominators::DominatorsAnalysisProvider(); + boost::scoped_ptr adapter(dominators::CFAGraphAdapter::build(pass->getReport())); + providerDomAnalysis->run(adapter.get()); - dominators::DominatorsTreeAnalysisProvider::Dominators expectedFDom = { - {1, - {0, 3}} - , - {2, - {1, 2}} + dominators::DominatorsAnalysisProvider::Dominators expectedFDom = { + {1, {0, 3}}, + {2, {1, 2}} }; - dominators::DominatorsTreeAnalysisProvider::Dominators expectedPostDom = { - {2, - {0, 3}} - , - {1, - {1, 2}} + dominators::DominatorsAnalysisProvider::Dominators expectedPostDom = { + {2, {1, 4}}, + {1, {2, 3}} }; auto actualFDom = providerDomAnalysis->getForwardDominators(); auto actualPostDom = providerDomAnalysis->getPostDominators(); ASSERT_EQ(expectedFDom, actualFDom); ASSERT_EQ(expectedPostDom, actualPostDom); delete providerDomAnalysis; delete pass; } TEST(CFA, ASTCorrespondence_Scope_Bindings_1){ std::string program = R"CODE( test = function(x::int, y::int):: int; entry{ x + y } )CODE"; std::unique_ptr man(details::tier2::XreateManager::prepare(move(program))); CFAPass* pass = new CFAPass(man.get()); man->registerPass(pass, PassId::CFAPass); man->executePasses(); testing::internal::CaptureStdout(); man->analyse(); std::string outputActual = testing::internal::GetCapturedStdout(); cout << outputActual << endl; string outputExpected = "ast_scope_binding(0,0,\"x\")"; ASSERT_NE(std::string::npos, outputActual.find(outputExpected)); outputExpected = "ast_scope_binding(0,1,\"y\")"; ASSERT_NE(std::string::npos, outputActual.find(outputExpected)); } diff --git a/cpp/tests/containers.cpp b/cpp/tests/containers.cpp index 92b1e1e..a68b8cd 100644 --- a/cpp/tests/containers.cpp +++ b/cpp/tests/containers.cpp @@ -1,112 +1,103 @@ /* Any copyright is dedicated to the Public Domain. * http://creativecommons.org/publicdomain/zero/1.0/ * * containers.cpp * * Created on: Jun 9, 2015 * Author: pgess */ #include "xreatemanager.h" #include "query/containers.h" #include "main/Parser.h" #include "gtest/gtest.h" using namespace std; using namespace xreate::grammar::main; using namespace xreate::containers; using namespace xreate; TEST(Containers, ListAsArray){ XreateManager* man = XreateManager::prepare( R"Code( main = function(x:: int):: int;entry { a = [1, 2, 3]:: [int]. a[x] } )Code" ); void* mainPtr = man->run(); int (*main)(int) = (int (*)(int))mainPtr; ASSERT_EQ(2, main(1)); delete man; } TEST(Containers, ListAsArray2){ XreateManager* man = XreateManager::prepare( R"Code( // CONTAINERS - interface(dfa) { - operator map:: (op(seqaccess)) -> impl(solid). - operator list_range:: ()->impl(on_the_fly). - operator list:: ()->impl(solid). - operator fold:: (op(seqaccess)). - operator index:: (op(randaccess)). - } - - import raw("core/containers.lp"). + import raw("scripts/dfa/ast-attachments.lp"). + import raw("scripts/containers/containers.lp"). main = function:: int;entry { - - a= [1, 2, 3]:: [int]. b= loop map(a->el:: int):: [int]{ 2 * el }. sum = loop fold(b->el:: int, 0->acc):: int { acc + el }. sum } -)Code" ); +)Code"); void* mainPtr = man->run(); int (*main)() = (int (*)())mainPtr; ASSERT_EQ(12, main()); delete man; } TEST(Containers, ContanierLinkedList1){ FILE* input = fopen("scripts/containers/Containers_Implementation_LinkedList1.xreate","r"); assert(input != nullptr); Scanner scanner(input); Parser parser(&scanner); parser.Parse(); AST* ast = parser.root->finalize(); CodeScope* body = ast->findFunction("test")->getEntryScope(); const Symbol symb_chilrenRaw{body->getSymbol("childrenRaw"), body}; containers::ImplementationLinkedList iLL(symb_chilrenRaw); ASSERT_EQ(true, static_cast(iLL)); ASSERT_EQ("next", iLL.fieldPointer); Implementation impl = Implementation::create(symb_chilrenRaw); ASSERT_NO_FATAL_FAILURE(impl.extract()); ImplementationRec recOnthefly = impl.extract(); ASSERT_EQ(symb_chilrenRaw, recOnthefly.source); } TEST(Containers, Implementation_LinkedListFull){ FILE* input = fopen("scripts/containers/Containers_Implementation_LinkedList1.xreate","r"); assert(input != nullptr); std::unique_ptr program(XreateManager::prepare(input)); void* mainPtr = program->run(); int (*main)() = (int (*)())(intptr_t)mainPtr; int answer = main(); ASSERT_EQ(17, answer); fclose(input); } diff --git a/cpp/tests/polymorph.cpp b/cpp/tests/polymorph.cpp index d1b0b8c..9835ac1 100644 --- a/cpp/tests/polymorph.cpp +++ b/cpp/tests/polymorph.cpp @@ -1,146 +1,147 @@ /* Any copyright is dedicated to the Public Domain. * http://creativecommons.org/publicdomain/zero/1.0/ * * polymorph.cpp * * Author: pgess * Created on October 11, 2017, 8:37 PM */ #include "xreatemanager.h" #include "ast.h" #include "transcendlayer.h" #include "aux/latereasoning.h" #include #include "gtest/gtest.h" #include "query/polymorph.h" using namespace xreate; using namespace xreate::latereasoning; using namespace xreate::polymorph; using namespace std; TEST(Polymorphs, ast1) { xreate::XreateManager* man = xreate::XreateManager::prepare( R"CODE( guard:: a { test = function:: int {0} } guard:: b { test = function:: int {1} } main = function:: int; entry { test() } )CODE"); const std::list& specs = man->root->getFunctionSpecializations("test"); ASSERT_EQ(2, specs.size()); auto itSpecs = specs.begin(); ASSERT_EQ("a", (*itSpecs)->guard.getValueString()); itSpecs++; ASSERT_EQ("b", (*itSpecs)->guard.getValueString()); } TEST(Polymorphs, PolymorphQuery_Static_1) { xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare( R"CODE( import raw("scripts/dfa/polymorphism.lp"). guard:: a { test = function:: int {0} } guard:: b { test = function:: int {1} } main = function:: int; entry { test()::int; callguard(b); dfa_polym(ret)} )CODE"); man->analyse(); PolymorphQuery* query = dynamic_cast (man->transcend->getQuery(QueryId::PolymorphQuery)); const Expression& bodyE = man->root->findFunction("main")->getEntryScope()->getBody(); LateAnnotation decisionLA = query->get(bodyE); ASSERT_EQ(1, decisionLA.guardedContent.size()); auto decisionOptSymb = decisionLA.select({}, man->root, man->transcend); ASSERT_TRUE(decisionOptSymb); decisionOptSymb->print(cout); cout << endl; string guard = query->getValue(*decisionOptSymb).getValueString(); ASSERT_STREQ("b", guard.c_str()); } TEST(Polymorphs, PolymorphQuery_Late_1){ xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare( R"CODE( - main = function:: int; entry{key= 0:: int; test. key} + Late = type variant{a, b}. + main = function:: int; entry{key= a():: Late; test. key::int} )CODE"); man->transcend->addRawScript( R"RULE( late(S, S, a, dfa_callguard(S, a)):- bind(S, test). late(S, S, b, dfa_callguard(S, b)):- bind(S, test). )RULE"); man->analyse(); PolymorphQuery* query = dynamic_cast (man->transcend->getQuery(QueryId::PolymorphQuery)); CodeScope* scopeMain = man->root->findFunction("main")->getEntryScope(); Symbol keyS = Symbol{scopeMain->getSymbol("key"), scopeMain}; Expression keyE = scopeMain->getDefinition(keyS); latereasoning::LateAnnotation answerLA = query->get(keyE); - auto answerRaw = answerLA.select({Expression(Operator::CALL, {Atom("b")})}, man->root, man->transcend); + Expression valueB(Operator::VARIANT, {}); valueB.setValueDouble(1); + auto answerRaw = answerLA.select({valueB}, man->root, man->transcend); ASSERT_TRUE(answerRaw); Expression answerE = query->getValue(*answerRaw); ASSERT_STREQ("b", answerE.getValueString().c_str()); } TEST(Polymorphs, PSCU_1){ auto man = details::tier1::XreateManager::prepare(R"Code( - DomLow = type variant {guard1, guard2}. - Dom = type slave dom. + Dom = type variant {guard1, guard2}. guard:: guard1 { compute = function :: int {0} } guard:: guard2 { compute = function :: int {1} } test = function:: int; entry { - xLate = guard2():: DomLow. - y1= switch late ((xLate::Dom):: Dom; alias(xLate)):: int + xLate = guard2():: Dom. + y1= switch late (xLate:: Dom; alias(xLate)):: int { compute():: int; guardkey(xLate) }. y1 } )Code"); man->transcend->addRawScript(R"RAW( dom(guard1; guard2). late(Target, Key, Variant, dfa_callguard(Target, Variant)):- bind(Target, guardkey(Alias)); bind(Key, alias(Alias)); dom(Variant). )RAW"); man->analyse(); int (*program)() = (int (*)())man->run(); int result = program(); ASSERT_EQ(1, result); -} \ No newline at end of file +} diff --git a/cpp/tests/types.cpp b/cpp/tests/types.cpp index 73f8349..a25c7d4 100644 --- a/cpp/tests/types.cpp +++ b/cpp/tests/types.cpp @@ -1,248 +1,248 @@ /* Any copyright is dedicated to the Public Domain. * http://creativecommons.org/publicdomain/zero/1.0/ * * types.cpp * * Created on: Jun 4, 2015 * Author: pgess */ #include "gtest/gtest.h" #include "xreatemanager.h" #include "llvmlayer.h" #include "main/Parser.h" #include "transcendlayer.h" #include "analysis/typeinference.h" #include "analysis/interpretation.h" using namespace std; using namespace xreate; using namespace xreate::grammar::main; TEST(Types, DependantTypes1) { string&& code = "XmlNode = type {\n" " tag:: string,\n" " attrs:: [string], \n" " content:: string\n" "}.\n"; std::unique_ptr program(XreateManager::prepare(move(code))); ExpandedType typeXmlNode = program->root->findType("XmlNode"); ASSERT_EQ(TypeOperator::LIST_NAMED, typeXmlNode->__operator); ASSERT_EQ(3, typeXmlNode->__operands.size()); ASSERT_EQ(TypePrimitive::String, typeXmlNode->__operands.at(0).__value); ASSERT_EQ(TypeOperator::LIST, typeXmlNode->__operands.at(1).__operator); ASSERT_EQ(TypePrimitive::String, typeXmlNode->__operands.at(2).__value); } TEST(Types, ast_ParameterizedTypes_FeatureTypeIndex_1) { string&& code = "XmlNode = type {\n" " tag:: string,\n" " attrs:: [string],\n" " content:: string\n" "}.\n" "" - "Template = type(Leaf) {Leaf, [Leaf[content]]}." + "Template = type(Leaf) {Leaf, [Leaf[\"content\"]]}." "Concrete = type Template(XmlNode)."; std::unique_ptr program(XreateManager::prepare(move(code))); ExpandedType typeConcrete = program->root->findType("Concrete"); ASSERT_EQ(TypeOperator::LIST_NAMED, typeConcrete->__operator); ASSERT_EQ(2, typeConcrete->__operands.size()); ASSERT_EQ(TypeOperator::LIST_NAMED, typeConcrete->__operands.at(0).__operator); ASSERT_EQ(TypeOperator::LIST, typeConcrete->__operands.at(1).__operator); ASSERT_EQ(TypePrimitive::String, typeConcrete->__operands.at(1).__operands.at(0).__value); } TEST(Types, TreeType1) { string&& code = "XmlNode = type {\n" " tag:: string,\n" " attrs:: [string],\n" " content:: string\n" "}.\n" "" "Tree = type(Leaf) {Leaf, [Tree(Leaf)]}." "Concrete = type Tree(XmlNode)."; std::unique_ptr program(XreateManager::prepare(move(code))); ExpandedType typeConcrete = program->root->findType("Concrete"); ASSERT_EQ(TypeOperator::LIST_NAMED, typeConcrete->__operator); ASSERT_EQ(2, typeConcrete->__operands.size()); ASSERT_EQ(TypeOperator::LIST_NAMED, typeConcrete->__operands.at(0).__operator); ASSERT_EQ(TypeOperator::LIST, typeConcrete->__operands.at(1).__operator); auto typeLink = typeConcrete->__operands.at(1).__operands.at(0); ASSERT_EQ(TypeOperator::LINK, typeLink.__operator); ASSERT_EQ(typeConcrete->conjuctionId, typeLink.conjuctionId); } TEST(Types, TreeType1LLvm) { string&& code = "XmlNode = type {\n" " tag:: string,\n" " /* attrs:: [string],*/\n" " content:: string\n" "}.\n" "" "Tree = type(Leaf) {Leaf, [Tree(Leaf)]}." "Concrete = type Tree(XmlNode)."; std::unique_ptr program(XreateManager::prepare(move(code))); ExpandedType typeConcrete = program->root->findType("Concrete"); llvm::Type* raw = program->llvm->toLLVMType(typeConcrete); } TEST(Types, ArrayOfExternal1) { FILE* input = fopen("scripts/containers/Containers_Implementation_LinkedList1.xreate", "r"); assert(input != nullptr); Scanner scanner(input); Parser parser(&scanner); parser.Parse(); AST* ast = parser.root->finalize(); CodeScope* body = ast->findFunction("test")->getEntryScope(); const ExpandedType& t2 = ast->getType(body->getDefinition(body->getSymbol("childrenRaw"))); EXPECT_EQ(t2->__operator, TypeOperator::LIST); } TEST(Types, ExternType1) { FILE* input = fopen("scripts/containers/Containers_Implementation_LinkedList1.xreate", "r"); assert(input != nullptr); Scanner scanner(input); Parser parser(&scanner); parser.Parse(); AST* ast = parser.root->finalize(); CodeScope* body = ast->findFunction("test")->getEntryScope(); const ExpandedType& t2 = ast->getType(body->getDefinition(body->getSymbol("tree"))); EXPECT_EQ(t2->__operator, TypeOperator::CUSTOM); } TEST(Types, ast_VariantType1) { string&& code = " colors = type variant {RED, BLUE, GREEN}.\n" " test = function:: colors; entry {GREEN()}"; std::unique_ptr program(XreateManager::prepare(move(code))); ExpandedType typ = program->root->findType("colors"); EXPECT_EQ(TypeOperator::VARIANT, typ->__operator); Expression eRed = program->root->findFunction("test")->getEntryScope()->getBody(); EXPECT_EQ(Operator::VARIANT, eRed.op); const ExpandedType& typ2 = program->root->getType(eRed); EXPECT_EQ(TypeOperator::VARIANT, typ2->__operator); } TEST(Types, full_VariantType_Switch1) { string&& code = "colors = type variant{RED, BLUE, GREEN}. \n" " test = function:: colors {GREEN()} \n" "main = function:: int; entry { \n" " switch(test()):: int \n" " case (GREEN()) {0} \n" " case default {1} \n" "}"; XreateManager* man = XreateManager::prepare(move(code)); int (*main)() = (int (*)()) man->run(); EXPECT_EQ(0, main()); } TEST(Types, ast_VariantType2) { std::string script = R"Code( Annotation = type variant { Num:: int, String:: string, Func:: {name::string, arguments::[Expression]} }. )Code"; std::unique_ptr program(XreateManager::prepare(move(script))); ExpandedType typ = program->root->findType("Annotation"); ASSERT_EQ(3, typ.get().fields.size()); } TEST(Types, SlaveTypes_UnwrapSlaveType1) { auto man = details::tier1::XreateManager::prepare(R"Code( AtomNumT = type slave atomNumT. AtomStrT = type slave atomStrT. CmpndIntStrT = type slave cmpndIntStrT. VariantT = type slave variantT. VariantComplicatedT = type slave variantComplicatedT. )Code"); man->transcend->addRawScript(R"RAW( atomNumT(5). atomNumT(8). atomStrT("a"). atomStrT("b"). cmpndIntStrT(1, "a"). cmpndIntStrT(2, "b"). variantT(first). variantT(second). variantT(third). variantComplicatedT(first(1, "a")). variantComplicatedT(second("b")). )RAW"); man->analyse(); ExpandedType AtomNumT = man->root->findType("AtomNumT"); ASSERT_EQ(AtomNumT->__operator, TypeOperator::SLAVE); ExpandedType ContentAtomNumT = interpretation::dereferenceSlaveType(AtomNumT, man->transcend); ASSERT_EQ(TypePrimitive::Num, ContentAtomNumT->__value); ExpandedType AtomStrT = man->root->findType("AtomStrT"); ExpandedType ContentAtomStrT = interpretation::dereferenceSlaveType(AtomStrT, man->transcend); ASSERT_EQ(TypePrimitive::String, ContentAtomStrT->__value); ExpandedType CmpndIntStrT = man->root->findType("CmpndIntStrT"); ExpandedType ContentCmpndIntStrT = interpretation::dereferenceSlaveType(CmpndIntStrT, man->transcend); ASSERT_EQ(TypeOperator::LIST_NAMED, ContentCmpndIntStrT->__operator); ASSERT_EQ(2, ContentCmpndIntStrT->__operands.size()); ExpandedType VariantT = man->root->findType("VariantT"); ExpandedType ContentVariantT = interpretation::dereferenceSlaveType(VariantT, man->transcend); ASSERT_EQ(TypeOperator::VARIANT, ContentVariantT->__operator); ASSERT_EQ(3, ContentVariantT->fields.size()); ExpandedType VariantComplicatedT = man->root->findType("VariantComplicatedT"); ExpandedType ContentVariantComplicatedT = interpretation::dereferenceSlaveType(VariantComplicatedT, man->transcend); ASSERT_EQ(TypeOperator::VARIANT, ContentVariantComplicatedT->__operator); ASSERT_EQ(2, ContentVariantComplicatedT->fields.size()); ASSERT_EQ(2, ContentVariantComplicatedT->__operands.at(0).__operands.size()); } TEST(Types, IndexNumber_1) { string&& code = R"CODE( Tuple = type {string, int}. Int = type Tuple[1]. )CODE"; std::unique_ptr program(XreateManager::prepare(move(code))); ExpandedType typeInt = program->root->findType("Int"); -} \ No newline at end of file +} diff --git a/documentation-api/AST-correspondence.fods b/documentation-api/AST-correspondence.fods index fb51aa6..2c9d3e7 100644 --- a/documentation-api/AST-correspondence.fods +++ b/documentation-api/AST-correspondence.fods @@ -1,556 +1,620 @@ - 2018-08-02T18:59:05.238218130LibreOffice/6.0.5.2$Linux_X86_64 LibreOffice_project/00m0$Build-22018-09-19T18:48:14.346688728PT4H42M8S7 + 2018-08-02T18:59:05.238218130LibreOffice/6.0.5.2$Linux_X86_64 LibreOffice_project/00m0$Build-22018-10-01T19:29:44.753564292PT6H30M19S9 0 0 - 38555 - 18048 + 38038 + 22621 view1 - 1 - 25 + 2 + 38 0 0 0 0 2 0 0 0 - 9 + 15 0 100 60 true false Sheet1 - 1241 + 1237 0 100 60 false true true true 12632256 true true true true false false false 1270 1270 1 1 true false 7 true false false 0 true - sgH+/0xleG1hcmstWDY1NmRlAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAQ1VQUzpMZXhtYXJrLVg2NTZkZQAAAAAAAAAAAAAAAAAWAAMA0wAAAAAAAAAIAFZUAAAkbQAASm9iRGF0YSAxCnByaW50ZXI9TGV4bWFyay1YNjU2ZGUKb3JpZW50YXRpb249UG9ydHJhaXQKY29waWVzPTEKY29sbGF0ZT1mYWxzZQptYXJnaW5kYWp1c3RtZW50PTAsMCwwLDAKY29sb3JkZXB0aD0yNApwc2xldmVsPTAKcGRmZGV2aWNlPTEKY29sb3JkZXZpY2U9MApQUERDb250ZXhEYXRhClBhZ2VTaXplOkxldHRlcgBEdXBsZXg6Tm9uZQBJbnB1dFNsb3Q6VHJheTEAABIAQ09NUEFUX0RVUExFWF9NT0RFDwBEdXBsZXhNb2RlOjpPZmY= + sgH+/0xleG1hcmstWDY1NmRlAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAQ1VQUzpMZXhtYXJrLVg2NTZkZQAAAAAAAAAAAAAAAAAWAAMA0wAAAAAAAAAIAFZUAAAkbQAASm9iRGF0YSAxCnByaW50ZXI9TGV4bWFyay1YNjU2ZGUKb3JpZW50YXRpb249UG9ydHJhaXQKY29waWVzPTEKY29sbGF0ZT1mYWxzZQptYXJnaW5kYWp1c3RtZW50PTAsMCwwLDAKY29sb3JkZXB0aD0yNApwc2xldmVsPTAKcGRmZGV2aWNlPTEKY29sb3JkZXZpY2U9MApQUERDb250ZXhEYXRhCkR1cGxleDpOb25lAElucHV0U2xvdDpUcmF5MQBQYWdlU2l6ZTpMZXR0ZXIAABIAQ09NUEFUX0RVUExFWF9NT0RFDwBEdXBsZXhNb2RlOjpPZmY= Lexmark-X656de true 3 true false true true 12632256 true true true false true false true 1 false 1270 1270 false 1 true - + + + - + + + + + + + + + + ??? Page 1 ???(???) - 00/00/0000, 00:00:00 + 00/00/0000, 00:00:00 Page 1/ 99 AST Current Transcend Proposition 1 Types Tests Expr op id state bindings operands type tags bind(var, annotation) blocks value CodeScope scope(scopeId) ast_scope(scopeId) bindings ast_scope_binding(scopeId, BindingId, ScopeBindName) ast_scope_binding(scopeId, BindingId, ScopeBindName) LIST CFA.ASTCorrespondence_Scope_Bindings_1 identifiers ast_scope_identifier(scopeId, Var) LIST parent cfa_parent(scopeCurrent, scope(scopeParent)) ast_scope_parent(ScopeId, ScopeParentId) SINGLE declarations LIST tags bind_scope(scopeId, tag, strong/weak(..)) LIST contextRules Function entry cfa_parent(scopeEntry, functon(name)) SINGLE name function(name) SINGLE guard cfa_function_specializations(funcName, tag) SINGLE tags bind_func(name, tag) LIST Special Expressions CALL - cfa_call(scopeFrom, functionTo)dfa_callfn(SymbRet, FnName)weak/dfa_callargs(SymbRet, argFormal, argActual)weak/dfa_alias(aliasFormal, Actual) + cfa_call(scopeFrom, functionTo)dfa_callfn(SymbRet, FnName)weak/dfa_callargs(SymbRet, argFormal, argActual)dfa_fnret(fnName, symbRet) - + - + + + Operator::MAP + + + + ast_op_map(SymbResult, SymbSource, ScopeBody) + + + + + + Operator::FOLD + + + + ast_op_fold(SymbResult, SymbSource, SymbAcc, ScopeBody) + + + + + + Operator::LIST + + + + ast_op_list(SymbResult, Size) + + + + + + Operator::LIST_RANGE + + + + ast_op_list_range(SymbResult) + + + + + + Operator::INDEX + + + + ast_op_index(SymbResult, SymbSource, SymbIndex) + + + + + + + OTHER var: s(id, version, scope), a(Num) v(var1) - dfa_fnret(fnName, symbRet) + weak/dfa_alias(aliasFormal, Actual) \ No newline at end of file diff --git a/documentation-api/containers.graphml b/documentation-api/containers.graphml new file mode 100644 index 0000000..18a5edb --- /dev/null +++ b/documentation-api/containers.graphml @@ -0,0 +1,570 @@ + + + + + + + + + + + + + + + + + + + + + + + Containers + Output + Processing + Input + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + cluster_root(Var) + + + + + + + + + + + + + + + + + + dfa_connection/3 + + + + + + + + + + + + + + + + + + var_cluster + + + + + + + + + + + + + + + + + + impl_fulfill/3 + + + + + + + + + + + + + + + + + + -impl_fulfill/2 + + + + + + + + + + + + + + + + + + relation_op/2 + + + + + + + + + + + + + + + + + + relation_score/2 + + + + + + + + + + + + + + + + + + -impl_fulfill_cluster/2 + + + + + + + + + + + + + + + + + + impl_fulfill_cluster/3 + + + + + + + + + + + + + + + + + + bind(V, op(Op))}; + + + + + + + + + + + + + + + + + + bind(V, impl(Impl)) + + + + + + + + + + + + + + + + + + ast_op_* + + + + + + + + + + + + + + + + + + cluster_link + + + + + + + + + + + + + + + + + + + + containers_impl + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/grammar/xreate.ATG b/grammar/xreate.ATG index 5342343..c7fde77 100644 --- a/grammar/xreate.ATG +++ b/grammar/xreate.ATG @@ -1,708 +1,710 @@ //TODO add ListLiteral //TODO ExprTyped: assign default(none) type #include "ast.h" #include "ExternLayer.h" #include #include #define wprintf(format, ...) \ char __buffer[100]; \ wcstombs(__buffer, format, 100); \ fprintf(stderr, __buffer, __VA_ARGS__) using namespace std; COMPILER Xreate details::inconsistent::AST* root = nullptr; // current program unit void ensureInitalizedAST(){ if (root == nullptr) root = new details::inconsistent::AST(); } struct { std::stack scopesOld; CodeScope* scope = nullptr; } context; void pushContextScope(CodeScope* scope){ context.scopesOld.push(context.scope); context.scope = scope; } void popContextScope(){ context.scope = context.scopesOld.top(); context.scopesOld.pop(); } int nextToken() { scanner->ResetPeek(); return scanner->Peek()->kind; } bool checkTokenAfterIdent(int key){ if (la->kind != _ident) return false; return nextToken() == key; } bool checkParametersList() { return la->kind == _ident && nextToken() == _lparen; } bool checkInfix() { return la->kind == _ident && nextToken() == _ident; } bool checkIndex() { return la->kind == _ident && nextToken() == _lbrack; } bool checkFuncDecl() { if (la->kind != _ident) return false; int token2 = nextToken(); int token3 = scanner->Peek()->kind; return token2 == _assign && (token3 == _function || token3 == _pre); } bool checkAssignment() { if (la->kind != _ident) return false; scanner->ResetPeek(); int token2 = scanner->Peek()->kind; if (token2 == _lcurbrack) { scanner->Peek(); int token3 = scanner->Peek()->kind; if (token3 != _rcurbrack) return false; int token4 = scanner->Peek()->kind; return token4 == _assign; } return token2 == _assign; } void recognizeIdentifier(Expression& i){ if (!context.scope->recognizeIdentifier(i)){ root->postponeIdentifier(context.scope, i); } } enum SwitchKind{SWITCH_NORMAL, SWITCH_META}; CHARACTERS letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz". any = ANY - '"'. digit = "0123456789". cr = '\r'. lf = '\n'. tab = '\t'. TOKENS ident = (letter | '_') {letter | digit | '_'}. number = (digit | '-' digit) {digit}. string = '"' { any } '"'. function = "function". pre = "pre". comma = ','. period = '.'. lparen = '('. rparen = ')'. lbrack = '['. rbrack = ']'. lcurbrack = '{'. rcurbrack = '}'. equal = "==". assign = '='. implic = '-' '>'. colon = ':'. context = "context". tagcolon = "::". lse = "<=". lss = "<". gte = ">=". gtr = ">". ne1 = "!=". ne2= "<>". COMMENTS FROM "/*" TO "*/" NESTED COMMENTS FROM "//" TO lf IGNORE cr + lf + tab PRODUCTIONS Xreate = (. Function* function; ensureInitalizedAST(); .) {( RuleDecl | InterfaceData | Imprt | GuardSection | IF(checkFuncDecl()) FDecl (. root->add(function); .) | TDecl | SkipModulesSection )} (. .) . Ident = ident (. name = t->val; .). VarIdent = ident (. e = Expression(Atom(t->val)); .) [ lcurbrack ( ident (. SemErr(coco_string_create("var version as ident is not implemented yet")); .) | number (. Attachments::put(e, Atom(t->val).get()); .) ) rcurbrack ] . FDecl = (. std::wstring fname; std::wstring argName; TypeAnnotation typIn; TypeAnnotation typOut; bool flagIsPrefunct = false; Expression binding; .) Ident assign [pre (. flagIsPrefunct = true; .)] function (. f = new Function(fname); f->isPrefunction = flagIsPrefunct; CodeScope* entry = f->getEntryScope(); .) [lparen Ident tagcolon ExprAnnotations (. f->addBinding(Atom(argName), move(binding)); .) {comma Ident tagcolon ExprAnnotations (. f->addBinding(Atom (argName), move(binding));.) } rparen] [ tagcolon ( IF(flagIsPrefunct) FnTag | Type ) {';' FnTag }] BDecl (. const_cast(entry->getBody()).bindType(move(typOut));.) . GuardSection<>= (. Expression guard; Function* f; .) "guard" tagcolon MetaSimpExpr lcurbrack { FDecl (. f->guard = guard; root->add(f); .) } rcurbrack. /** * TYPES * */ TypeTerm = (. std::wstring tid; .) ("string" (. typ = TypePrimitive::String;.) | "num" (. typ = TypePrimitive::Num;.) | "int" (. typ = TypePrimitive::Int;.) | "float" (. typ = TypePrimitive::Float;.) | "bool" (. typ = TypePrimitive::Bool; .) | "i8" (. typ = TypePrimitive::I8; .) | "i32" (. typ = TypePrimitive::I32; .) | "i64" (. typ = TypePrimitive::I64; .) ). Type = (. TypeAnnotation typ2; TypePrimitive typ3; std::wstring tid; std::string field; .) ( TList | TStruct | TVariant | TSlave | TypeTerm (. typ = typ3; .) | IF (checkIndex()) Ident lbrack TypeIndex (. typ = TypeAnnotation(TypeOperator::ACCESS, {}); typ.__valueCustom = Atom(tid).get(); typ.fields.push_back(field); .) {comma TypeIndex (. typ.fields.push_back(field); .) } rbrack | Ident (. typ = TypeAnnotation(TypeOperator::CUSTOM, {}); typ.__valueCustom = Atom(tid).get(); .) [lparen Type (. typ.__operator = TypeOperator::CALL; typ.__operands.push_back(typ2); .) {comma Type (. typ.__operands.push_back(typ2); .) } rparen] +| '*' (.typ = TypeAnnotation(); .) ) . TypeIndex = ( number (. name = Atom(t->val).get(); .) | string (. name = Atom(t->val).get(); .) ) . TList = (. TypeAnnotation ty; .) lbrack Type rbrack (. typ = TypeAnnotation(TypeOperator::LIST, {ty}); .) . TStruct = (. TypeAnnotation t; std::wstring key; size_t keyCounter=0; .) lcurbrack ( IF(checkTokenAfterIdent(_tagcolon)) Ident tagcolon Type | Type (. key = to_wstring(keyCounter++); .) ) (. typ = TypeAnnotation(TypeOperator::LIST_NAMED, {t}); typ.fields.push_back(Atom(key).get()); .) {comma ( IF(checkTokenAfterIdent(_tagcolon)) Ident tagcolon Type | Type (. key = to_wstring(keyCounter++); .) ) (. typ.__operands.push_back(t); typ.fields.push_back(Atom(key).get()); .) } rcurbrack. TVariant= (. TypeAnnotation t, typVoid; std::vector operands; std::vector> keys; std::wstring variant; .) "variant" lcurbrack Ident (. t=typVoid; .) [tagcolon Type] (. keys.push_back(Atom(variant)); operands.push_back(t); .) {comma Ident (. t=typVoid; .) [tagcolon Type] (. keys.push_back(Atom(variant)); operands.push_back(t); .) } rcurbrack (. typ = TypeAnnotation(TypeOperator::VARIANT, {}); typ.__operands = operands; typ.addFields(std::move(keys)); .) . TSlave= (. std::wstring identMaster; .) "slave" Ident (. typ = TypeAnnotation(TypeOperator::SLAVE, {}); typ.__valueCustom = Atom(identMaster).get(); .) . TDecl = (. TypeAnnotation t; std::wstring tname, arg; std::vector> args; .) Ident assign "type" [lparen Ident (. args.push_back(Atom(arg)); .) {comma Ident (. args.push_back(Atom(arg)); .) } rparen] Typeperiod (. t.addBindings(move(args)); root->add(move(t), Atom(tname)); .) . ContextDecl = (. Expression tag; .) context tagcolon MetaSimpExpr (. scope->tags.push_back(tag); .) {';' MetaSimpExpr (. scope->tags.push_back(tag); .) }. VDecl = (. std::wstring vname; Expression var, value;.) VarIdent assign ExprTyped (. Symbol identSymbol = f->addDefinition(move(var), move(value)); Attachments::put(value, identSymbol); .) . BDecl = lcurbrack (. Expression body; pushContextScope(scope); .) {(IF(checkAssignment()) VDecl period | RuleContextDecl | ContextDeclperiod | ExprTyped (. scope->setBody(body); Attachments::put(body, Symbol{ScopedSymbol::RetSymbol, scope});.) )} rcurbrack (. popContextScope(); .) . IfDecl = (. Expression cond; ManagedScpPtr blockTrue = root->add(new CodeScope(context.scope)); ManagedScpPtr blockFalse = root->add(new CodeScope(context.scope)); .) "if" lparen Expr rparen (. e = Expression(Operator::IF, {cond}); .) tagcolon ExprAnnotations BDecl<&*blockTrue> "else" BDecl<&*blockFalse> (. e.addBlock(blockTrue); e.addBlock(blockFalse); .) . LoopDecl = (. Expression eIn, eAcc, eFilters; std::wstring varEl, varAcc, contextClass; Expression tagsEl; ManagedScpPtr block = root->add(new CodeScope(context.scope)); .) "loop" ("map" lparen Expr implic Ident (. e = Expression(Operator::MAP, {eIn}); .) tagcolon ExprAnnotations rparen tagcolon ExprAnnotations (. e.addBindings({Atom(varEl)}); block->addBinding(Atom(varEl), move(tagsEl)); .) BDecl<&*block> (. e.addBlock(block); .) |"fold" ("inf" lparen Expr implic Ident rparen (. e = Expression(Operator::FOLD_INF, {eAcc}); e.addBindings({Atom(varAcc)}); block->addBinding(Atom(varAcc), Expression()); .) tagcolon ExprAnnotations BDecl<&*block> (. e.addBlock(block); .) | lparen Expr implic Ident tagcolon ExprAnnotations ['|' Expr ] comma Expr implic Identrparen (. e = Expression(Operator::FOLD, {eIn, eAcc}); e.addBindings({Atom(varEl), Atom(varAcc)}); .) tagcolon ExprAnnotations (. block->addBinding(Atom(varEl), move(tagsEl)); block->addBinding(Atom(varAcc), Expression()); .) BDecl<&*block> (. e.addBlock(block); .) ) ). // Switches SwitchDecl = (. TypeAnnotation typ; eSwitch = Expression(Operator::SWITCH, {}); Expression eCondition; Expression tag;.) "switch" ( SwitchVariantDecl | SwitchLateDecl | lparen ExprTyped rparen tagcolon ExprAnnotations (. eSwitch.operands.push_back(eCondition);.) CaseDecl {CaseDecl} ) . CaseDecl = (. ManagedScpPtr scope = root->add(new CodeScope(context.scope)); Expression condition; .) "case" ( IF(flagSwitchKind == SWITCH_META) lparen MetaSimpExpr rparen BDecl<&*scope> (. Expression exprCase(Operator::CASE, {}); exprCase.addTags({condition}); exprCase.addBlock(scope); outer.addArg(move(exprCase));.) | "default" BDecl<&*scope> (. Expression exprCase(Operator::CASE_DEFAULT, {}); exprCase.addBlock(scope); outer.operands.insert(++outer.operands.begin(), exprCase); .) | lparen CaseParams<&*scope> rparen (. ManagedScpPtr scopeBody = root->add(new CodeScope(&*scope)); Expression exprCase(Operator::CASE, {}); .) BDecl<&*scopeBody> (. exprCase.addBlock(scope); exprCase.addBlock(scopeBody); outer.addArg(move(exprCase)); .) ). CaseParams = (. Expression condition; Expression guard(Operator::LOGIC_AND, {}); pushContextScope(scope); .) ExprTyped (. guard.addArg(Expression(condition)); .) {comma ExprTyped (. guard.addArg(Expression(condition)); .) } (. scope->setBody(guard); popContextScope(); .) . SwitchLateDecl = (. std::wstring aliasCondition; Expression exprCondition, aliasAnns; expr = Expression(Operator::SWITCH_LATE, {}); ManagedScpPtr scope = root->add(new CodeScope(context.scope)); .) "late" lparen Expr [implic Ident] [tagcolon ExprAnnotations] rparen tagcolon ExprAnnotations BDecl<&*scope> (. expr.addArg(Expression(exprCondition)); expr.addBlock(scope); std::string alias; if(aliasCondition.empty()){ if(exprCondition.__state != Expression::IDENT){ SemErr(coco_string_create("An identifier expected in the short form")); return; } //Use exprCondition as identifier alias = exprCondition.getValueString(); } else { //Use aliasCondition alias = Atom(move(aliasCondition)).get(); } expr.addBindings({Atom(string(alias))}); scope->addBinding(Atom(move(alias)), move(aliasAnns)); .) . SwitchVariantDecl = (. Expression varTested; std::wstring varAlias; bool flagAliasFound = false; expr = Expression(Operator::SWITCH_VARIANT, {}); .) "variant" lparen Expr [implic Ident (. flagAliasFound = true; .) ] [tagcolon ExprAnnotations] rparen tagcolon ExprAnnotations (. expr.addArg(std::move(varTested)); if (flagAliasFound) { expr.addBindings({Atom(varAlias)}); } else { if(varTested.__state == Expression::IDENT){ expr.addBindings({Atom(string(varTested.getValueString()))}); } } .) CaseVariantDecl {CaseVariantDecl} . CaseVariantDecl = (. ManagedScpPtr scope = root->add(new CodeScope(context.scope)); std::wstring key; scope->addBinding(Atom(string(expr.bindings.front())), Expression()); .) "case" lparen Ident rparen (. expr.addArg(root->recognizeVariantConstructor(Atom(std::move(key)))); .) BDecl<&*scope> (. expr.addBlock(scope); .) . -IntrinsicDecl= (. std::wstring name; .) +IntrinsicDecl= (. std::wstring name; .) "intrinsic" ( - Ident< name> lparen [CalleeParams] rparen - (. outer = Expression(Operator::CALL_INTRINSIC, {}); outer.setValue(Atom(name)); .) + Ident< name> (. outer = Expression(Operator::CALL_INTRINSIC, {}); outer.setValue(Atom(name)); .) + lparen [CalleeParams] rparen + | "query" (. outer = Expression(Operator::QUERY, {}); .) ( "late" IntrinsicQueryLateDecl | lparen [CalleeParams] rparen ) ). IntrinsicQueryLateDecl = (. std::wstring predicateAlias; Expression predicateE, predicateAnns; expr = Expression(Operator::QUERY_LATE, {}); ManagedScpPtr scope = root->add(new CodeScope(context.scope)); .) lparen Expr implic Ident tagcolon ExprAnnotations rparen tagcolon ExprAnnotations BDecl<&*scope> (. expr.addArg(move(predicateE)); expr.addBindings({Atom(wstring(predicateAlias))}); scope->addBinding(Atom(move(predicateAlias)), move(predicateAnns)); expr.addBlock(scope); .) . SequenceDecl = (. sequence = Expression(); sequence.setOp(Operator::SEQUENCE); ManagedScpPtr scope = root->add(new CodeScope(context.scope)); .) "seq" BDecl<&*scope> (. sequence.blocks.push_back(&*scope); scope = root->add(new CodeScope(&*scope)); .) { (. scope = root->add(new CodeScope(&*scope)); .) BDecl<&*scope> (. sequence.blocks.push_back(&*scope); .) }. /*============================ INTERFACES ===============================*/ Imprt<> = "import" "raw" lparen string (. root->__rawImports.push_back(Atom(t->val).get()); .) rparen period. InterfaceData<> = "interface" lparen ( "dfa" rparen InterfaceDFA | "extern-c" rparen InterfaceExternC | "cfa" rparen InterfaceCFA ). InterfaceExternC<> = (. ExternData data; .) lcurbrack {IncludeExternDecl | LibExternDecl } rcurbrack (. root->addExternData(move(data)); .) . LibExternDecl = (. std::wstring pkgname, libname; .) Ident assign "library" tagcolon "pkgconfig" lparen string (. pkgname = t->val; .) rparen period (. data.addLibrary(Atom(libname), Atom(pkgname)); .) . IncludeExternDecl = (. Expression inc; .) "include" StructLiteral period (. data.addIncludeDecl(move(inc)); .) . InterfaceDFA<> = lcurbrack { InstructDecl } rcurbrack . InstructDecl = (.Operator op; Expression tag; Expression scheme; std::vector& tags = scheme.operands; tags.push_back(Expression()); /* return value */ .) "operator" InstructAlias tagcolon lparen (.scheme.setOp(op); .) [ MetaSimpExpr (. tags.push_back(tag); .) { comma MetaSimpExpr (. tags.push_back(tag); .) } ] rparen [ implic MetaSimpExpr (. tags[0] = tag; .) ] (. root->addDFAData(move(scheme)); .) period. InstructAlias = ( "map" (. op = Operator::MAP; .) | "list_range" (. op = Operator::LIST_RANGE; .) | "list" (. op = Operator::LIST; .) | "fold" (. op = Operator::FOLD; .) | "index" (. op = Operator::INDEX; .) ). InterfaceCFA<> = lcurbrack { InstructCFADecl } rcurbrack . InstructCFADecl<> = (.Operator op; Expression tag; Expression scheme; std::vector& tags = scheme.operands; .) "operator" InstructAlias tagcolon (. scheme.setOp(op); .) [ MetaSimpExpr (. tags.push_back(tag); .) { comma MetaSimpExpr (. tags.push_back(tag); .) } ] period (. root->addInterfaceData(CFA, move(scheme)); .). /*============================ METAPROGRAMMING ===============================*/ // TagsDecl = (. Expression tag; TagModifier mod = TagModifier::NONE; .) // ':' { MetaSimpExpr (. /*f.addTag(std::move(tag), mod); */ .) // }. FnTag = (. Expression tag; TagModifier mod = TagModifier::NONE; .) MetaSimpExpr ['-' TagMod] (. f->addTag(std::move(tag), mod); .). TagMod = ( "assert" (. mod = TagModifier::ASSERT; .) | "require" (. mod = TagModifier::REQUIRE; .) ). RuleDecl<> = "rule" tagcolon (. RuleArguments args; RuleGuards guards; DomainAnnotation typ; std::wstring arg; .) lparen Ident tagcolon Domain (. args.add(arg, typ); .) {comma Ident tagcolon Domain (. args.add(arg, typ); .) } rparen ["case" RGuard {comma RGuard}] lcurbrack RBody rcurbrack . /* - TODO use RGuard for guards-*/ RuleContextDecl = (.Expression eHead, eGuards, eBody; .) "rule" "context" tagcolon MetaSimpExpr "case" lparen MetaSimpExpr rparen lcurbrack MetaSimpExpr rcurbrack (.scope->contextRules.push_back(Expression(Operator::CONTEXT_RULE, {eHead, eGuards, eBody})); .). Domain = ( "function" (. dom = DomainAnnotation::FUNCTION; .) | "variable" (. dom = DomainAnnotation::VARIABLE; .) ). RGuard= (. Expression e; .) MetaExpr (. guards.add(std::move(e)); .). MetaExpr= (.Operator op; Expression e2; .) MetaExpr2 [MetaOp MetaExpr2 (. e = Expression(op, {e, e2}); .) ]. MetaExpr2= ( lparen MetaExpr rparen | MetaSimpExpr ). MetaSimpExpr= (. std::wstring i1, infix; Expression e2; .) ( '-' MetaSimpExpr (. e = Expression(Operator::NEG, {e2}); .) | IF(checkParametersList()) Ident (. e = Expression(Operator::CALL, {Expression(Atom(i1))}); .) lparen [ MetaCalleeParams ] rparen | IF(checkInfix()) Ident Ident MetaSimpExpr (. e = Expression(Operator::CALL, {Expression(Atom(infix))}); e.addArg(Expression(Atom(i1))); e.addArg(std::move(e2)); .) | Ident (. e = Expression(Operator::CALL, {Atom(i1)}); .) ). MetaCalleeParams = (. Expression e2; .) MetaSimpExpr (. e.addArg(Expression(e2)); .) {comma MetaSimpExpr (. e.addArg(Expression(e2)); .) }. RBody = (. Expression e; std::wstring msg; .) "warning" MetaExpr ["message" string (. msg = t->val; .) ] (. root->add(new RuleWarning(RuleArguments(args), RuleGuards(guards), std::move(e), Atom(msg))); .) . MetaOp< Operator& op> = implic (. op = Operator::IMPL; .) . /*============================ Expressions ===============================*/ ExprAnnotations = (. TypeAnnotation typ; std::list tags; Expression tag; e.tags.clear();.) Type (. e.bindType(move(typ)); .) {';' MetaSimpExpr (. tags.push_back(tag); .) } (. e.addTags(tags); .) . ExprTyped = Expr [tagcolon ExprAnnotations]. Expr< Expression& e> (. Operator op; Expression e2; .) = ExprArithmAdd [ RelOp ExprArithmAdd (. e = Expression(op, {e, e2}); .) ]. ExprArithmAdd< Expression& e>= (. Operator op; Expression e2; .) ExprArithmMul< e> [ AddOp< op> ExprArithmAdd< e2> (. e = Expression(op, {e, e2});.) ]. ExprArithmMul< Expression& e> (. Operator op; Expression e2; .) = ExprPostfix< e> [ MulOp< op> ExprArithmMul< e2> (. e = Expression(op, {e, e2}); .) ]. ExprPostfix = Term [ (. e = Expression(Operator::INDEX, {e}); .) {lbrack CalleeParams rbrack } ]. Term< Expression& e> (. std::wstring name; e = Expression(); .) = (IF (checkParametersList()) Ident< name> (. e = Expression(Operator::CALL, {Atom(name)}); root->recognizeVariantConstructor(e); .) lparen [CalleeParams] rparen | VarIdent (. recognizeIdentifier(e); .) | ListLiteral (. /* tuple */.) | StructLiteral (. /* struct */.) | LoopDecl | IfDecl | SwitchDecl | IntrinsicDecl | SequenceDecl | number (. e = Expression(Atom(t->val)); .) | string (. e = Expression(Atom(t->val)); .) | "true" (. e = Expression(Atom(1)); e.bindType(TypePrimitive::Bool); .) | "false" (. e = Expression(Atom(0)); e.bindType(TypePrimitive::Bool); .) | "undef" (. e = Expression(Operator::UNDEF, {}); .) | '-' Term (. e = Expression(Operator::NEG, {e}); .) | lparen ExprTyped rparen ). StructLiteral = (. std::wstring key; Expression val; std::list> keys; size_t keyCounter=0; .) lcurbrack (IF(checkTokenAfterIdent(_assign)) Ident assign Expr | Expr (. key = to_wstring(keyCounter++); .) ) (. keys.push_back(Atom(key)); e = Expression(Operator::LIST_NAMED, {val}); .) {comma (IF(checkTokenAfterIdent(_assign)) Ident assign Expr | Expr (. key = to_wstring(keyCounter++); .) ) (. e.addArg(Expression(val)); keys.push_back(Atom(key)); .) } rcurbrack (. e.addBindings(keys.begin(), keys.end()); .) . ListLiteral = (. Expression eFrom, eTo; .) lbrack (. e.setOp(Operator::LIST); .) [ Expr (. e.addArg(Expression(eFrom)); .) ( ".." Expr (. e.addArg(Expression(eTo)); e.setOp(Operator::LIST_RANGE); .) |{comma Expr (. e.addArg(Expression(eFrom)); .) } ) ] rbrack. CalleeParams = (. Expression e2; .) ExprTyped (. e.addArg(Expression(e2)); .) {comma ExprTyped (. e.addArg(Expression(e2)); .) }. AddOp< Operator& op> = (. op = Operator::ADD; .) ( '+' | '-' (. op = Operator::SUB; .) ). MulOp< Operator& op> = (. op = Operator::MUL; .) ( '*' | '/' (. op = Operator::DIV; .) ). RelOp< Operator& op> = (. op = Operator::EQU; .) ( equal | (ne1 | ne2) (. op = Operator::NE; .) | lse (. op = Operator::LSE; .) | lss (. op = Operator::LSS; .) | gte (. op = Operator::GTE; .) | gtr (. op = Operator::GTR; .) ). SkipModulesSection = "module" lcurbrack {ANY} rcurbrack. END Xreate. diff --git a/scripts/cfa/context.lp b/scripts/cfa/context.lp index b8167e0..f97d57a 100644 --- a/scripts/cfa/context.lp +++ b/scripts/cfa/context.lp @@ -1,106 +1,106 @@ % This Source Code Form is subject to the terms of the Mozilla Public % License, v. 2.0. If a copy of the MPL was not distributed with this % file, You can obtain one at http://mozilla.org/MPL/2.0/. %% INPUT: %% - latex_scope_demand(Scope, Subject) %% Initial demand from clients %% %% - latex_registered_subjects(Subject, PossibleDecision) %% Clients register possible decisions for respective subjects %% %% - latex_fn_signature %% %% OUTPUT: %% - latex_fn_demand(Fn, Subject) %% Which functions demand hidden latex arguments %% %% - latex_decision(Scope, Subject, Decision) %% Provided decisions, values for hidden latex arguments %% %% SIGNATURES: %% -Subject: string %% % CONTEXT PROPAGATION %=========================================================== % nested scope propagation: bind_scope(Scope, Context, Info):- bind_scope(ScopeParent, Context, Info); cfa_parent(Scope, scope(ScopeParent)). % Strong or Uniform inter-function propagation: bind_scope(Scope, Context, Info):- bind_scope(ScopeParent, Context, Info): cfa_call(ScopeParent, FnCurrent); cfa_parent(Scope, function(FnCurrent)); cfa_call(_, FnCurrent); bind_scope(_, Context, Info); scope(Scope). % weak inter-function propagation bind_scope(Scope, Context, weak(ScopeParent)):- not bind_scope(Scope, Context, strong); bind_scope(ScopeParent, Context, strong); cfa_call(ScopeParent, FnCurrent); cfa_parent(Scope, function(FnCurrent)). % DEMAND %=========================================================== %demand propagations: scope level latex_scope_demand(Scope, Subject):- latex_scope_demand(ScopeChild, Subject); cfa_parent(ScopeChild, scope(Scope)). %propagation: fn level latex_fn_demand(Fn, Subject):- latex_scope_demand(ScopeFnBody, Subject); cfa_parent(ScopeFnBody, function(Fn)). latex_fn_demand_ordered(Fn, Subject, Id):- Id= #sum{ 1, SubjLess : latex_fn_demand(Fn, SubjLess), SubjLess < Subject}; latex_fn_demand(Fn, Subject). %propagation: inter-fn level latex_scope_demand(Scope, Subject):- latex_fn_demand(FnCallee, Subject); not latex_decision(Scope, Subject, _); cfa_call(Scope, FnCallee). % DECISIONS %=========================================================== latex_decision(Scope, Subject, Decision):- latex_fn_demand(FnCallee, Subject); bind_scope(Scope, Decision, strong); cfa_call(Scope, FnCallee); latex_registered_subjects(Subject, Decision). %late decision late((ScopeCaller, Subject), SubjectS, (AnyDecision), latex_decision(ScopeCaller, Subject, AnyDecision)):- scope_fn(ScopeCaller, FnCaller); cfa_parent(FnCallerBody, function(FnCaller)); latex_symbol(FnCaller, Subject, SubjectS); cfa_call(ScopeCaller, FnCallee); latex_fn_demand(FnCallee, Subject); latex_registered_subjects(Subject, AnyDecision). % UTILITY %=========================================================== latex_symbol(Fn, Topic, s(TopicsOffset + TopicId, -2, FnBody)):- cfa_parent(FnBody, function(Fn)); - latex_parameters_group_offset(TopicsOffset); + latex_parameters_offset(TopicsOffset); latex_fn_demand_ordered(Fn, Topic, TopicId). % IMPLEMENTATION %=========================================================== scope_fn(Scope, Fn):-cfa_parent(Scope, function(Fn)). scope_fn(Scope, Fn):- scope_fn(ScopeParent, Fn); cfa_parent(Scope, scope(ScopeParent)). -latex_parameters_group_offset(1000). +latex_parameters_offset(1000). diff --git a/scripts/containers/containers.lp b/scripts/containers/containers.lp index d2f472d..2a05f4d 100644 --- a/scripts/containers/containers.lp +++ b/scripts/containers/containers.lp @@ -1,48 +1,87 @@ % This Source Code Form is subject to the terms of the Mozilla Public % License, v. 2.0. If a copy of the MPL was not distributed with this % file, You can obtain one at http://mozilla.org/MPL/2.0/. %defines - impl(llvm_array; llvm_const_array; on_the_fly). + impl(solid; llvm_const_array; on_the_fly). op(seqaccess). op(randaccess). relation(recommends; satisfied; unsupported). relation_score(satisfied, 0). relation_score(recommends, 1). relation_score(unsupported, -1). score(-1..1). -%domain facts: - relation_op(seqaccess, on_the_fly, recommends). - relation_op(randaccess, llvm_const_array, recommends). - relation_op(randaccess, on_the_fly, unsupported). + %domain facts: +relation_op(seqaccess, on_the_fly, recommends). +relation_op(randaccess, llvm_const_array, recommends). +relation_op(randaccess, on_the_fly, unsupported). -%dfa analysis: -% -- + %AST ATTACHMENTS +attach_operator_map(none, op(seqaccess)). +attach_operator_fold(none, op(seqaccess), none). -%compilation: -%-- +attach_operator_list_range(impl(on_the_fly)). +attach_operator_list(impl(solid)). +attach_operator_index(op(randaccess)). -%domain rules: - -impl_fulfill(OP, IMPL) :- relation_op(OP, IMPL, unsupported). - impl_fulfill(OP, IMPL, SCORE):- SCORE = #sum{SCORE1, (OP, IMPL, RL): relation_op(OP, IMPL, RL),relation_score(RL, SCORE1)} - ; op(OP); impl(IMPL); not -impl_fulfill(OP, IMPL). - - cluster_root(VAR) :- not dfa_connection(VAR, _, strong), v(VAR). - var_cluster(VAR0, VAR_TO) :- dfa_connection(VAR_TO, VAR0, strong), cluster_root(VAR0). - var_cluster(VAR0, VAR_TO2) :- dfa_connection(VAR_TO2, VAR_TO1, strong), var_cluster(VAR0, VAR_TO1). - var_cluster(VAR0, VAR0):- cluster_root(VAR0). + %CLUSTERS +cluster_link(VTo, VFrom):- %aliases + dfa_connection(VTo, VFrom, strong). + +cluster_link(VResult, VSource):- %Operator MAP + ast_op_map(VResult, VSource, _). + +cluster_root(V):- + not cluster_link(V, _); + v(V). - -impl_fulfill_cluster(Var0, Impl) :- var_cluster(Var0, Var_Any); bind(Var_Any, op(Op)); -impl_fulfill(Op, Impl). - impl_fulfill_cluster(VAR0, IMPL, Score) :- - Score = #sum{SCORE, (OP, IMPL, VAR_ANY): impl_fulfill(OP, IMPL, SCORE), var_cluster(VAR0, VAR_ANY), bind(VAR_ANY, op(OP))} - ; bind(VAR0, impl(IMPL)); cluster_root(VAR0); not -impl_fulfill_cluster(VAR0, IMPL). - - - proto_cluster(V0, Vproto) :- cluster_root(V0); cluster_root(Vproto); var_cluster(Vproto, Vp); dfa_connection(V0, Vp, proto). - +var_cluster(V, V):- %self referencing + cluster_root(V). + +var_cluster(VRoot, VTo):- %propagation down the tree + cluster_link(VTo, VFrom); + var_cluster(VRoot, VFrom). + + + %ALGORITHM +-impl_fulfill(OP, IMPL):- + relation_op(OP, IMPL, unsupported). + +impl_fulfill(OP, IMPL, SCORE):- + SCORE = #sum{SCORE1, (OP, IMPL, RL): relation_op(OP, IMPL, RL), relation_score(RL, SCORE1)}; + not -impl_fulfill(OP, IMPL); + op(OP); impl(IMPL). + +-impl_fulfill_cluster(Var0, Impl):- + var_cluster(Var0, Var_Any); + bind(Var_Any, op(Op)); + -impl_fulfill(Op, Impl). + +impl_fulfill_cluster(VAR0, IMPL, Score):- + Score = #sum{SCORE, (OP, IMPL, VAR_ANY): impl_fulfill(OP, IMPL, SCORE), var_cluster(VAR0, VAR_ANY), bind(VAR_ANY, op(OP))}; + bind(VAR0, impl(IMPL)); + cluster_root(VAR0); + not -impl_fulfill_cluster(VAR0, IMPL). + + + %OUTPUT +containers_impl(V, Impl):- + containers_impl(VRoot, Impl); + var_cluster(VRoot, V). + +containers_impl(V, solid(Size)):- + impl_fulfill_cluster(V, solid, _); + ast_op_list(V, Size); + cluster_root(V). + +containers_impl(V, on_the_fly):- + impl_fulfill_cluster(V, on_the_fly, _); + ast_op_list_range(V); + cluster_root(V). + %optimization % #maximize {SCORE, (VAR0, IMPL) : impl_fulfill_cluster(VAR0, IMPL, SCORE)}. #show var_cluster/2. #show impl_fulfill_cluster/3. diff --git a/scripts/dfa/ast-attachments.lp b/scripts/dfa/ast-attachments.lp new file mode 100644 index 0000000..0c2add9 --- /dev/null +++ b/scripts/dfa/ast-attachments.lp @@ -0,0 +1,57 @@ +% This Source Code Form is subject to the terms of the Mozilla Public +% License, v. 2.0. If a copy of the MPL was not distributed with this +% file, You can obtain one at http://mozilla.org/MPL/2.0/. + +% USAGE: +% attach_operator_map(A->SymbResult, B->SymbSource) +% attach_operator_fold(A->SymbResult, B->SymbSource, C-> SymbAcc) +% attach_operator_list_range(A -> SymbResult) +% attach_operator_list(A -> SymbResult) +% attach_operator_index(A -> SymbResult) + + +% OPERATOR MAP +bind(SymbResult, A):- + attach_operator_map(A, _); + ast_op_map(SymbResult, _, _); + A<>none. + +bind(SymbSource, B):- + attach_operator_map(_, B); + ast_op_map(_, SymbSource, _); + B<>none. + + +% OPERATOR LIST_RANGE +bind(SymbResult, A):- + ast_op_list_range(SymbResult); + attach_operator_list_range(A). + + +% OPERATOR LIST +bind(SymbResult, A):- + ast_op_list(SymbResult, _); + attach_operator_list(A). + + +% OPERATOR FOLD +bind(SymbResult, A):- + attach_operator_fold(A, _, _); + ast_op_fold(SymbResult, _, _, _); + A<>none. + +bind(SymbSource, B):- + attach_operator_fold(_, B, _); + ast_op_fold(_, SymbSource, _, _); + B<>none. + +bind(SymbAcc, C):- + attach_operator_fold(_, _, C); + ast_op_fold(_, _, SymbAcc, _); + C<>none. + + +% OPERATOR INDEX +bind(SymbSource, A):- + attach_operator_index(A); + ast_op_index(_, SymbSource, _). diff --git a/scripts/dsl/regexp.xreate b/scripts/dsl/regexp.xreate index 3651cc1..1bfb6e6 100644 --- a/scripts/dsl/regexp.xreate +++ b/scripts/dsl/regexp.xreate @@ -1,76 +1,76 @@ /* Any copyright is dedicated to the Public Domain. * http://creativecommons.org/publicdomain/zero/1.0/ */ interface(extern-c){ xml2 = library:: pkgconfig("libxml-2.0"). include { xml2 = ["string.h"] }. } Matcher = type variant {Sequence, ZeroOrMore, Text}. matchText = function(text::string, matcher::string, posStart::i64):: i64 { textLength = strlen(text):: i64. matcherLength = strlen(matcher):: i64. if(textLength >= posStart + matcherLength):: i64{ if(strncmp(text + posStart, matcher, matcherLength) == 0):: i64 { matcherLength } else {-1:: i64} } else {-2:: i64} } matchSequence = function(text::string, pattern::undefType; interpretation(force), posStart::i64):: i64; interpretation(suppress){ textLength = length(text):: i64. loop fold(pattern-> matcher:: undefType, posStart->pos):: i64{ recognizedSymbols = match(text, matcher, pos):: i64. - if (recognizedSymbols > 0):: i64{ + if (recognizedSymbols > (0::i64)):: i64{ pos+recognizedSymbols } else { pos:: i64; break } } } matchZeroOrMore= function(text::string, matcher::undefType; interpretation(force), posStart::i64):: i64; interpretation(suppress){ textLength = length(text):: i64. loop fold inf(posStart->pos):: i64{ recognizedSymbols = match(text, matcher, pos):: i64. - if (recognizedSymbols > 0):: i64{ + if (recognizedSymbols > (0::i64)):: i64{ pos+recognizedSymbols } else { pos:: i64; break } } } match = function(text::string, pattern::undefType; interpretation(force), posStart::i64)::i64; interpretation(suppress){ key= pattern[0]::Matcher. switch variant(key) :: int case (Sequence) {matchSequence(text, pattern[1], posStart)} case (ZeroOrMore) {matchZeroOrMore(text, pattern[1], posStart)} case (Text) {matchText(text, pattern[1], posStart)} } main = function:: i64; entry { patternAB = [Sequence(), [[ZeroOrMore(), [Text(), "a"]], [Text(), "b"]]] :: undefType; interpretation(force). // matchers = ["The ", "only ", "way "] :: [string]; interpretation(force). match("aaab", patternAB, 0):: i64 } diff --git a/scripts/effects-communication/example1-wr.xreate b/scripts/effects-communication/example1-wr.xreate index 738486c..6d6dc0c 100644 --- a/scripts/effects-communication/example1-wr.xreate +++ b/scripts/effects-communication/example1-wr.xreate @@ -1,38 +1,41 @@ //Only Direct implementatino defined import raw ("scripts/dfa/propagation.lp"). import raw ("scripts/dfa/polymorphism.lp"). import raw ("scripts/effects-communication/communication.lp"). import raw ("scripts/effects-communication/config.lp"). CommGuard = type variant{Invalid, Valid, Outdated}. CommDirect = type { value:: int }. CommGuarded = type { value:: int, state:: CommGuard }. guard:: commDirect { - init=function::CommDirect{ - {value = 0} + init=function::CommDirect + { + {value = 0} } - read= function(vault1:: CommDirect):: int{ - (vault1::CommDirect; commop(read))["value"] + read= function(vault1:: CommDirect):: int + { + (vault1:: *;commop(read))["value"] } - write= function(vault2:: CommDirect, valueNew:: int)::CommDirect{ - (vault2::CommDirect;dfa_pseudo(vault2)) + {value = valueNew}:: int; commop(write); dfa_uppy(vault2) + write= function(vault2:: CommDirect, valueNew:: int)::CommDirect + { + (vault2:: *; dfa_pseudo(vault2)) + {value = valueNew}:: int; commop(write); dfa_uppy(vault2) } } main=function::int; entry { - x1 = init()::Comm; dfa_polym(ret). - x2 = write(x1, 1)::Comm; dfa_polym(arg). - a = read(x2)::int; dfa_polym(arg). + x1 = init()::*; dfa_polym(ret). + x2 = write(x1, 1)::*; dfa_polym(arg). + a = read(x2)::int; dfa_polym(arg). a } diff --git a/scripts/effects-communication/example2-wr.xreate b/scripts/effects-communication/example2-wr.xreate index fd4b342..7a53acd 100644 --- a/scripts/effects-communication/example2-wr.xreate +++ b/scripts/effects-communication/example2-wr.xreate @@ -1,76 +1,76 @@ //Direct and Guarded implementation defined import raw ("scripts/effects-communication/communication.lp"). import raw ("scripts/dfa/propagation.lp"). import raw ("scripts/dfa/polymorphism.lp"). import raw ("scripts/effects-communication/config.lp"). CommGuard = type variant{Invalid, Valid, Outdated}. CommDirect = type { value:: int }. CommGuarded = type { value:: int, state:: CommGuard }. guard:: commDirect { init=function::CommDirect{ {value = 0} } read= function(vault1:: CommDirect):: int{ (vault1::CommDirect; commop(read))["value"] } write= function(vault2:: CommDirect, valueNew:: int)::CommDirect{ (vault2::CommDirect;dfa_pseudo(vault2)) + {value = valueNew}:: int; commop(write); dfa_uppy(vault2) } } errorRead = function:: int { -1 } errorWrite = function:: CommGuarded{ { value = -1, state = Invalid() } } guard:: commGuarded{ init=function::CommGuarded{ { value = 0, state = Invalid() } } read=function(vault3:: CommGuarded):: int { switch variant (vault3::CommGuarded;commop(read)):: int case (Invalid) { errorRead() } case (Outdated) { errorRead() } case (Valid) { vault3["value"] } } write=function(vault4:: CommGuarded, valueNew:: int)::CommGuarded{ switch variant (vault4)::int case (Invalid) { {value = valueNew, state = Valid()} } case (Outdated) { {value = valueNew, state = Valid()} } case (Valid) { errorWrite() } } } main=function::int; entry { - x1 = init():: Comm; dfa_polym(ret). - x2 = write(x1, 1)::Comm; dfa_polym(arg). + x1 = init():: *; dfa_polym(ret). + x2 = write(x1, 1)::*; dfa_polym(arg). a = read(x2):: int; dfa_polym(arg). a } diff --git a/scripts/effects-communication/example3-wrwr.xreate b/scripts/effects-communication/example3-wrwr.xreate index 29796c7..39f6f89 100644 --- a/scripts/effects-communication/example3-wrwr.xreate +++ b/scripts/effects-communication/example3-wrwr.xreate @@ -1,86 +1,86 @@ //Direct and Guarded implementation defined import raw ("scripts/effects-communication/communication.lp"). import raw ("scripts/dfa/propagation.lp"). import raw ("scripts/dfa/polymorphism.lp"). import raw ("scripts/effects-communication/config.lp"). CommGuard = type variant{Invalid, Valid, Outdated}. CommDirect = type { value:: int }. CommGuarded = type { value:: int, state:: CommGuard }. guard:: commDirect { init=function::CommDirect{ {value = 0} } read= function(vault1:: CommDirect):: int{ (vault1::CommDirect; commop(read))["value"] } write= function(vault2:: CommDirect, valueNew1:: int)::CommDirect{ (vault2::CommDirect;dfa_pseudo(vault2)) + {value = valueNew1}:: int; commop(write); dfa_uppy(vault2) } } errorRead = function:: int { -1 } errorWrite = function:: CommGuarded{ { value = -1, state = Invalid() } } guard:: commGuarded{ init=function::CommGuarded{ { value = 0, state = Invalid() } } read=function(vault3:: CommGuarded):: int { switch variant (vault3["state"]->whatever::CommGuard;commop(read)):: int case (Invalid) { errorRead() } case (Outdated) { errorRead() } case (Valid) { vault3["value"] } } write=function(vault4:: CommGuarded, valueNew2:: int)::CommGuarded{ switch variant (vault4["state"]->whatever::CommGuard;commop(write); dfa_pseudo(vault4))::int case (Invalid) { {value = valueNew2, state = Valid()}:: CommGuarded; dfa_uppy(vault4) } case (Outdated) { {value = valueNew2, state = Valid()}:: CommGuarded; dfa_uppy(vault4) } case (Valid) { errorWrite():: CommGuarded; dfa_uppy(vault4) } } } main=function(cmd:: num)::int; entry { - x1 = init():: Comm; dfa_polym(ret). - x2 = write(x1, 1)::Comm; dfa_polym(arg). + x1 = init():: *; dfa_polym(ret). + x2 = write(x1, 1)::*; dfa_polym(arg). - x3 = if (cmd > 0)::Comm { + x3 = if (cmd > 0)::int { y = read(x2):: int; dfa_polym(arg). y } else { - z = write(x2, 2)::Comm; dfa_polym(arg). + z = write(x2, 2)::*; dfa_polym(arg). a = read(z):: int; dfa_polym(arg). a }. x3 }