diff --git a/config/default.json b/config/default.json index 338ac69..862b37e 100644 --- a/config/default.json +++ b/config/default.json @@ -1,73 +1,72 @@ { "containers": { "id": { "implementations": "impl_fulfill_cluster", "clusters": "var_cluster", "prototypes": "proto_cluster", "linkedlist": "linkedlist" }, "impl": { "solid": "solid", "onthefly": "on_the_fly" } }, "logging": { "id": "logging" }, "function-entry": "entry", "clasp": { "bindings" : { "variable": "bind", "function": "bind_func", "scope": "bind_scope", "function_demand" : "bind_function_demand", "scope_decision": "bind_scope_decision" }, "context" : { "decisions":{ "dependent": "resolution_dependency" } }, "nonevalue": "nonevalue", "ret": { "symbol": "retv", "tag": "ret" } }, "tests": { - "template": "sequence", + "template": "current-fix", "templates": { - "sequence": "Compilation.Sequence1", - "current-fix":"", + "current-fix":"CFA.DomReportOneRoot", "default": "*-Adhoc.*:Containers.*:Compilation.full_IFStatementWithVariantType:Types.full_VariantType_Switch1:Context.full_LateContext:Context.pathDependentContext", "ast": "AST.*", "adhocs": "Adhoc.*", "effects": "Effects.*", "basic": "Attachments.*", "context": "Context.*", "compilation": "Compilation.*-Compilation.full_IFStatementWithVariantType", "communication": "Communication.*", "cfa": "CFA.*", "containers": "Containers.*", "dfa": "DFA.*", "diagnostic": "Diagnostic.*", "dsl": "Association.*:Interpretation.SwitchVariantAlias", "ExpressionSerializer": "ExpressionSerializer.*", "externc": "InterfaceExternC.*", "loops": "Loop.*", "modules": "Modules.*", "polymorphs": "Polymorphs.call1", "types": "Types.*", "vendorsAPI/clang": "ClangAPI.*", "vendorsAPI/xml2": "libxml2*" } } } diff --git a/cpp/src/analysis/DominatorsTreeAnalysisProvider.cpp b/cpp/src/analysis/DominatorsTreeAnalysisProvider.cpp index c6a928b..4aaab5b 100644 --- a/cpp/src/analysis/DominatorsTreeAnalysisProvider.cpp +++ b/cpp/src/analysis/DominatorsTreeAnalysisProvider.cpp @@ -1,239 +1,241 @@ /* 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 { +namespace xreate { +namespace dominators { -struct ControlFlowTree; -struct Node { - ScopePacked scope; - ControlFlowTree* tree; +struct CFAGraphAdapter; + +struct ScopeNode { + ScopePacked id; + std::list nodesFrom; + std::list nodesTo; }; -/* -bool operator !=(const Node& a, const Node& b){ - return (a.tree != b.tree) || (a.scope != b.scope); -} +struct CFAGraphAdapter { + std::list nodes; + ScopeNode* nodeRoot; -Node& operator++(Node& a){ - ++a.scope; - return a; -} - */ + 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); -struct ControlFlowTree{ - typedef bimap, multiset_of> CHILD_RELATIONS; - CHILD_RELATIONS edges; - std::vector nodes; - Node* entry = nullptr; - size_t size; + if(posLowerBound==nodes.end()|| posLowerBound->id > id){ + return &*nodes.insert(posLowerBound, elemNew); + } - ControlFlowTree(const size_t nodesCount): nodes(nodesCount), size(nodesCount){ + return &*posLowerBound; } - static ControlFlowTree* build(const ClaspLayer* engine, cfa::CFAGraph* graph){ - ControlFlowTree* tree = new ControlFlowTree(engine->getScopesCount()); + static CFAGraphAdapter* build(const cfa::CFAGraph* graph) { + CFAGraphAdapter* tree=new CFAGraphAdapter(); - for (const auto& edge: graph->__parentScopeRelations){ - tree->edges.insert(CHILD_RELATIONS::value_type(edge.second, edge.first)); - } + enum NODE_MARK{NO_ROOT, POSSIBLE_ROOT}; + std::unordered_map nodeMarks; + for (const auto& edge: graph->__dependencyRelations){ - for (const auto& edge: graph->__callRelations){ - unsigned int calleeFunction = edge.right; - ScopePacked caller = edge.left; + ScopeNode* nodeTo = tree->getOrCreateNode(edge.first); + ScopeNode* nodeFrom = tree->getOrCreateNode(edge.second); + nodeTo->nodesFrom.push_back(nodeFrom); + nodeFrom->nodesTo.push_back(nodeTo); - auto range = graph->__parentFunctionRelations.right.equal_range(calleeFunction); - for (auto& i=range.first; i!= range.second; ++i){ - tree->edges.insert(CHILD_RELATIONS::value_type(caller, i->second)); + 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; } } - for (size_t i=0; isize; ++i){ - tree->nodes[i]= Node{(unsigned int) i, tree}; + std::list nodeRoots; + for(auto nodeMark: nodeMarks){ + if(nodeMark.second == POSSIBLE_ROOT) nodeRoots.push_back(nodeMark.first); } - return tree; - } - - std::list getRootFunctions() const{ - size_t idMax = size; - size_t id =0; - std::list results; - auto i = edges.right.begin(); - - while (id < idMax) { - if (i!= edges.right.end() && i->first == id){ - i = edges.right.upper_bound(i->first); - - } else { - results.push_back(id); + 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); } - - ++id; + } else { + assert(nodeRoots.size()==1); + tree->nodeRoot = tree->getOrCreateNode(nodeRoots.front()); } - return std::move(results); + return tree; } + + CFAGraphAdapter() { } }; -}} //end of namespace xreate::dominators +} +} //end of namespace xreate::dominators namespace llvm { - using namespace xreate::dominators; - - template <> struct GraphTraits { - typedef Node* nodes_iterator; - typedef Node NodeType; - - typedef std::function Transformer; - typedef typename boost::transform_iterator ChildIteratorType; - - static ChildIteratorType child_begin(const nodes_iterator& node) { - auto range = node->tree->edges.left.equal_range(node->scope); - Transformer x = [node](auto edge){return &node->tree->nodes[edge.second];}; - - return boost::make_transform_iterator(range.first, x); - } +using namespace xreate::dominators; - static ChildIteratorType child_end(const nodes_iterator& node) { - auto range = node->tree->edges.left.equal_range(node->scope); - Transformer x = [node](auto edge){return &node->tree->nodes[edge.second];}; +template<> +struct GraphTraits { + typedef ScopeNode NodeType; + typedef std::list::iterator ChildIteratorType; - return boost::make_transform_iterator(range.second, x); - } - }; + static ChildIteratorType + child_begin(NodeType* node) { + return node->nodesTo.begin(); + } - template <> struct GraphTraits> { - typedef Node* nodes_iterator; - typedef Node NodeType; + static ChildIteratorType + child_end(NodeType* node) { + return node->nodesTo.end(); + } +}; - typedef std::function Transformer; - typedef typename boost::transform_iterator ChildIteratorType; +template<> +struct GraphTraits : public GraphTraits { + typedef std::list::iterator nodes_iterator; - static ChildIteratorType child_begin(const nodes_iterator& node) { - auto range = node->tree->edges.right.equal_range(node->scope); - Transformer x = [node](auto edge){return &node->tree->nodes[edge.second];}; + static nodes_iterator + nodes_begin(CFAGraphAdapter* graph) { + return graph->nodes.begin(); + } - return boost::make_transform_iterator(range.first, x); - } + static nodes_iterator + nodes_end(CFAGraphAdapter* graph) { + return graph->nodes.end(); + } - static ChildIteratorType child_end(const nodes_iterator& node) { - auto range = node->tree->edges.right.equal_range(node->scope); - Transformer x = [node](auto edge){return &node->tree->nodes[edge.second];}; + static NodeType* + getEntryNode(CFAGraphAdapter* F) { + return F->nodeRoot; + } - return boost::make_transform_iterator(range.second, x); - } - }; + static unsigned int + size(CFAGraphAdapter* graph) { + return graph->nodes.size(); + } +}; - template <> struct GraphTraits: public GraphTraits { - static NodeType* - getEntryNode(ControlFlowTree* F) { - if (F->entry) return F->entry; - list&& roots = F->getRootFunctions(); - assert(roots.size()==1); +template<> +struct GraphTraits> +{ + typedef ScopeNode NodeType; + typedef std::list::iterator ChildIteratorType; - return F->entry = &F->nodes[roots.front()]; - } + static ChildIteratorType + child_begin(NodeType* node) { + return node->nodesFrom.begin(); + } - static nodes_iterator nodes_begin(ControlFlowTree* F) { return &F->nodes[0]; } - static nodes_iterator nodes_end(ControlFlowTree* F) { return &F->nodes[F->size]; } - static size_t size(ControlFlowTree* F) { return F->size; } - }; + static ChildIteratorType + child_end(NodeType* node) { + return node->nodesFrom.end(); + } +}; } -namespace xreate{ namespace dominators { -class DominatorTree: public llvm::DominatorTreeBase { +namespace xreate { +namespace dominators { + +class DominatorTree : public llvm::DominatorTreeBase { public: DominatorsTreeAnalysisProvider::Dominators dominators; - DominatorTree(bool isPostDom): llvm::DominatorTreeBase(isPostDom) {} + DominatorTree(bool isPostDom) : llvm::DominatorTreeBase(isPostDom) { } - void run(ControlFlowTree& program){ + void + run(CFAGraphAdapter& program) { recalculate(program); //extract dominators info - for (auto& entry: DomTreeNodes){ - if (!entry.getFirst()) continue; + for(auto& entry : DomTreeNodes) { + if(!entry.getFirst()) continue; - dominators.emplace(entry.getFirst()->scope, make_pair(entry.getSecond()->getDFSNumIn(), entry.getSecond()->getDFSNumOut())); + 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 << formatAtom % (entry.first) % (entry.second.first) % (entry.second.second) - << endl; + void + print(std::ostringstream& output, const std::string& atom) const { + boost::format formatAtom(atom+"(%1%, range(%2%, %3%))."); + + for(auto entry : dominators) { + output< program(ControlFlowTree::build(engine, graph)); +DominatorsTreeAnalysisProvider::run(const cfa::CFAGraph* graph) { + boost::scoped_ptr program(CFAGraphAdapter::build(graph)); - treeForwardDominators->run(*program); - treePostDominators->run(*program); + treeForwardDominators->run(*program); + treePostDominators->run(*program); } void -DominatorsTreeAnalysisProvider::print(std::ostringstream& output) const{ +DominatorsTreeAnalysisProvider::print(std::ostringstream& output) const { treeForwardDominators->print(output, "cfa_forwdom"); treePostDominators->print(output, "cfa_postdom"); } const DominatorsTreeAnalysisProvider::Dominators& -DominatorsTreeAnalysisProvider::getForwardDominators() const{ +DominatorsTreeAnalysisProvider::getForwardDominators() const { return treeForwardDominators->dominators; } const DominatorsTreeAnalysisProvider::Dominators& -DominatorsTreeAnalysisProvider::getPostDominators() const{ +DominatorsTreeAnalysisProvider::getPostDominators() const { return treePostDominators->dominators; } DominatorsTreeAnalysisProvider::DominatorsTreeAnalysisProvider() - : treeForwardDominators(new DominatorTree(false)) - , treePostDominators(new DominatorTree(true)) -{} +: treeForwardDominators(new DominatorTree(false)) +, treePostDominators(new DominatorTree(true)) { } + +DominatorsTreeAnalysisProvider::~DominatorsTreeAnalysisProvider() { } + +} +} //end of namespace xreate::dominators -DominatorsTreeAnalysisProvider::~DominatorsTreeAnalysisProvider() {} -}} //end of namespace xreate::dominators //void //CodeScopesTree::print(){ // typedef llvm::GraphTraits Traits; // for (size_t i=0; i" << (*j)->scope << endl; // } // } //} diff --git a/cpp/src/analysis/DominatorsTreeAnalysisProvider.h b/cpp/src/analysis/DominatorsTreeAnalysisProvider.h index f0223c6..f284208 100644 --- a/cpp/src/analysis/DominatorsTreeAnalysisProvider.h +++ b/cpp/src/analysis/DominatorsTreeAnalysisProvider.h @@ -1,42 +1,42 @@ /* 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 "clasplayer.h" #include namespace xreate{namespace dominators{ class DominatorTree; /** \brief Dominators Analysis report */ class DominatorsTreeAnalysisProvider: public IAnalysisReport { public: typedef std::pair DominatedRange; typedef std::map Dominators; DominatorsTreeAnalysisProvider(); virtual ~DominatorsTreeAnalysisProvider(); - void run(const ClaspLayer* engine, cfa::CFAGraph* graph); + void run(const cfa::CFAGraph* graph); void print(std::ostringstream& output) const override; const Dominators& getForwardDominators() const; const Dominators& getPostDominators() const; private: boost::scoped_ptr treeForwardDominators; boost::scoped_ptr treePostDominators; }; }} //end of namespace xreate::dominators #endif /* DOMINATORSTREEANALYSISPROVIDER_H */ diff --git a/cpp/src/analysis/cfagraph.cpp b/cpp/src/analysis/cfagraph.cpp index cd37e58..3ca5e39 100644 --- a/cpp/src/analysis/cfagraph.cpp +++ b/cpp/src/analysis/cfagraph.cpp @@ -1,175 +1,204 @@ /* 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: CFAGraph.cpp * Author: pgess * * Created on June 27, 2016, 2:09 PM */ /** * \file cfagraph.h * \brief Control Flow Analysis(CFA) graph data * */ #include "analysis/cfagraph.h" #include "analysis/aux.h" using namespace xreate::cfa; using namespace std; void CFAGraph::print(std::ostringstream& output) const { const std::string& atomBinding = Config::get("clasp.bindings.function"); const std::string& atomBindingScope = Config::get("clasp.bindings.scope"); //show function tags int counterTags = 0; std::ostringstream bufFunctionNames; boost::format formatFunction("function(%1%)."); boost::format formatBind(atomBinding + "(%1%, %2%)."); for (auto function: this->__nodesFunction.left) { const auto tags = this->__functionTags.equal_range(function.first); if (tags.first == tags.second) { //no tags bufFunctionNames << "; " << function.second ; continue; } output << formatFunction % (function.second) << std::endl; for (const auto& tag_: boost::make_iterator_range(tags)){ const Expression& tag = tag_.second; list tagRaw = xreate::analysis::compile(tag); assert(tagRaw.size() == 1); output << formatBind % (function.second) % (tagRaw.front()) << endl; ++counterTags; } } if (bufFunctionNames.tellp()){ output << formatFunction % (bufFunctionNames.str().substr(2)) << std::endl; } if (counterTags == 0) { output << "%no functtion tags at all" << endl; } //declare scopes boost::format formatScope("scope(0..%1%)."); output << formatScope % (__clasp->getScopesCount() - 1) << std::endl; //show context rules: for (auto rule: this->__contextRules) { output << ContextRule(rule.second).compile(rule.first) << std::endl; }; //show scope tags: counterTags = 0; boost::format formatScopeBind(atomBindingScope + "(%1%, %2%, strong)."); for (auto entry: this->__scopeTags) { ScopePacked scopeId = entry.first; const Expression& tag = entry.second; list tagRaw = xreate::analysis::compile(tag); assert(tagRaw.size() == 1); output << formatScopeBind % scopeId %(tagRaw.front()) << endl; ++counterTags; } if (counterTags == 0) { output << "%scope tags: no tags at all" << endl; } output << endl << "%\t\tStatic analysis: CFA" << endl; //parent connections //TOTEST CFG parent function boost::format formatFunctionParent("cfa_parent(%1%, function(%2%))."); for (const auto &relation: this->__parentFunctionRelations) { const string& function = this->__nodesFunction.left.at(relation.right); output << formatFunctionParent % relation.left % function << endl; } //TOTEST CFG parent scope boost::format formatScopeParent("cfa_parent(%1%, scope(%2%))."); for (const auto &relation: this->__parentScopeRelations) { output << formatScopeParent % relation.first % relation.second << endl; } //call connections boost::format formatCall("cfa_call(%1%, %2%)."); for (const auto &relation: this->__callRelations) { const ScopePacked scopeFrom = relation.left; const string& functionTo = this->__nodesFunction.left.at(relation.right); output << formatCall % (scopeFrom) % (functionTo) << endl; } //function specializations descrtiption //SECTIONTAG late-context cfa_function_specializations boost::format formatSpecializations("cfa_function_specializations(%1%, %2%)."); const list& functions = __clasp->ast->getAllFunctions(); for (auto f: functions){ if (f->guardContext.isValid()){ list guardRaw = xreate::analysis::compile(f->guardContext); assert(guardRaw.size() == 1); output << formatSpecializations % (f->getName()) % (guardRaw.front()) << endl; } } + + //Dependencies + boost::format formatDependencies("cfa_scope_depends(%1%, %2%)."); + for(const auto relation: __dependencyRelations){ + output << formatDependencies % relation.first % relation.second << endl; + } + std::multimap __dependencyRelations; } void CFAGraph::addFunctionAnnotations(const std::string& function, const std::map& tags) { unsigned int fid = registerNodeFunction(function); for (auto& tag: tags){ __functionTags.emplace(fid, tag.second); } } void CFAGraph::addScopeAnnotations(const ScopePacked& scope, const std::vector& tags){ for (Expression tag: tags){ __scopeTags.emplace(scope, tag); } } void CFAGraph::addContextRules(const ScopePacked& scope, const std::vector& rules){ for (Expression rule: rules){ __contextRules.emplace(scope, rule); } } void CFAGraph::addCallConnection(const ScopePacked& scopeFrom, const std::string& functionTo) { unsigned int idFuncTo = registerNodeFunction(functionTo); __callRelations.insert(CALL_RELATIONS::value_type(scopeFrom, idFuncTo)); } void CFAGraph::addParentConnection(const ScopePacked& scope, const std::string& functionParent){ __parentFunctionRelations.insert(PARENT_FUNCTION_RELATIONS::value_type(scope, registerNodeFunction(functionParent))); } void CFAGraph::addParentConnection(const ScopePacked& scope, const ScopePacked& scopeParent){ __parentScopeRelations.emplace(scope, scopeParent); } unsigned int CFAGraph::registerNodeFunction(const std::string& fname){ auto pos = __nodesFunction.left.insert(make_pair(__nodesFunction.size(), fname)); return pos.first->first; } + +void +CFAGraph::addDependency(const ScopePacked& scope, const ScopePacked& scopeDependency){ + __dependencyRelations.emplace(scope, scopeDependency); +} + +bool CFAGraph::isDependent(const ScopePacked& scope) const{ + return __dependencyRelations.count(scope) > 0; +} + +void CFAGraph::transmitDependencies(const ScopePacked& scopeTo, const ScopePacked& scopeFrom){ + auto range = __dependencyRelations.equal_range(scopeFrom); + + std::list dependencies; + for (auto pairI = range.first; pairI != range.second; ++pairI){ + dependencies.push_back(pairI->second); + } + + for(auto dep: dependencies){ + __dependencyRelations.emplace(scopeTo, dep); + } +} diff --git a/cpp/src/analysis/cfagraph.h b/cpp/src/analysis/cfagraph.h index 49c66d6..7d97e16 100644 --- a/cpp/src/analysis/cfagraph.h +++ b/cpp/src/analysis/cfagraph.h @@ -1,60 +1,63 @@ /* 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: CFAGraph.h * Author: pgess * * Created on June 27, 2016, 2:09 PM */ #ifndef CFAGRAPH_H #define CFAGRAPH_H #include "clasplayer.h" namespace xreate {namespace cfa { /** \brief Represents CFA analysis data produced by CFAPass */ class CFAGraph: public IAnalysisReport { public: typedef boost::bimap> PARENT_FUNCTION_RELATIONS; PARENT_FUNCTION_RELATIONS __parentFunctionRelations; std::map __parentScopeRelations; + std::multimap __dependencyRelations; typedef boost::bimap< boost::bimaps::multiset_of, boost::bimaps::multiset_of, boost::bimaps::set_of_relation<> > CALL_RELATIONS; CALL_RELATIONS __callRelations; boost::bimap __nodesFunction; std::multimap __functionTags; std::multimap __scopeTags; std::multimap __contextRules; void print(std::ostringstream& output) const override; CFAGraph(ClaspLayer* engine): __clasp(engine){} void addFunctionAnnotations(const std::string& function, const std::map& tags); void addScopeAnnotations(const ScopePacked& scope, const std::vector&tags); void addContextRules(const ScopePacked& scope, const std::vector&rules); void addCallConnection(const ScopePacked& scopeFrom, const std::string& functionTo); void addParentConnection(const ScopePacked& scope, const std::string& functionParent); void addParentConnection(const ScopePacked& scope, const ScopePacked& scopeParent); - // void addScopeRetIdentifier(const ScopePacked& scope, const SymbolPacked& identifier); + void addDependency(const ScopePacked& scope, const ScopePacked& scopeDependency); + bool isDependent(const ScopePacked& scope) const; + void transmitDependencies(const ScopePacked& scopeTo, const ScopePacked& scopeFrom); private: ClaspLayer* __clasp; unsigned int registerNodeFunction(const std::string& fname); }; }} //end of namespace xreate::cfa #endif /* CFAGRAPH_H */ diff --git a/cpp/src/clasplayer.h b/cpp/src/clasplayer.h index 2e4157a..1ad660e 100644 --- a/cpp/src/clasplayer.h +++ b/cpp/src/clasplayer.h @@ -1,229 +1,231 @@ /* 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: clasplayer.h */ #ifndef CLASPLAYER_H #define CLASPLAYER_H #include "ast.h" #include "contextrule.h" #include #include #include #include #include #include #include #include +#include namespace xreate { typedef unsigned int ScopePacked; +const ScopePacked SCOPE_ABSTRACT_GLOBAL = std::numeric_limits::max(); struct SymbolPacked { SymbolPacked(){} SymbolPacked(ScopedSymbol i, ScopePacked s): identifier(i.id), version(i.version), scope(s){} SymbolPacked(VNameId symbolId, versions::VariableVersion symbolVersion, ScopePacked symbolScope) : identifier(symbolId), version(symbolVersion), scope(symbolScope){} VNameId identifier; versions::VariableVersion version; ScopePacked scope; }; bool operator==(const SymbolPacked& s1, const SymbolPacked& s2); bool operator<(const SymbolPacked& s1, const SymbolPacked& s2); enum class DFGConnection { STRONG, WEAK, PROTOTYPE }; /** \brief Designated to mark analysis results that can be composed as *logic program* */ class IAnalysisReport { public: /** \brief Composes *logic program* based on analysis data into ASP format and appends to a stream*/ virtual void print(std::ostringstream& output) const = 0; virtual ~IAnalysisReport(){}; }; /** \brief Logic program query interface */ class IQuery { public: virtual void init(ClaspLayer* clasp) = 0; virtual ~IQuery() {} }; enum class QueryId { ContainersQuery, ContextQuery, PtrvalidQuery, PolymorphQuery }; namespace dfa{ class DFAGraph; } namespace cfa { class CFAGraph; } class ClaspLayer { friend class ContextRule; /**\name Data Providers Management */ ///@{ public: void registerReport(IAnalysisReport* report); void runReports(); /** \brief Appends arbitrary string to *logic program* */ void addRawScript(std::string&& script); private: std::list __reports; /** Includes external text files to a *logic program* */ void involveImports(); ///@} /**\name Queries Management */ ///@{ public: /** \brief Adds query. See xreate::IQuery */ IQuery* registerQuery(IQuery* query, const QueryId& id); /** \brief Returns particular query. See xreate::IQuery */ IQuery* getQuery(const QueryId& id); template static std::tuple parse(const Gringo::Symbol& atom); typedef std::multimap::const_iterator ModelIterator; typedef boost::optional> ModelFragment; ModelFragment query(const std::string& atom); size_t getScopesCount() const; SymbolPacked pack(const Symbol& symbol, std::string hintSymbolName = ""); ScopePacked pack(const CodeScope * const scope); Symbol unpack(const SymbolPacked& symbol); std::string getHintForPackedSymbol(const SymbolPacked& symbol); ///@} private: std::map __queries; std::multimap __model; std::map __indexSymbolNameHints; std::unordered_map __indexScopes; std::vector __registryScopes; /**\name Diagnostic */ ///@{ //TODO diagnostic move over to separate provider/query public: /** \brief Adds diagnostic rule */ void addRuleWarning(const RuleWarning &rule); /** \brief Registers diagnostic messages */ unsigned int registerWarning(std::string &&message); private: std::map __warnings; void printWarnings(std::ostream& out); ///@} ///@{ public: ClaspLayer(); /** \brief Executes reasoning */ void run(); ///@} AST *ast; private: std::ostringstream __partTags; std::ostringstream __partGeneral; bool handleSolution(Gringo::Model const &model); }; template struct ParseImplAtom { static typ get(const Gringo::Symbol& atom) { return atom.num(); } }; template<> struct ParseImplAtom { static int get(const Gringo::Symbol& atom); }; template<> struct ParseImplAtom { static std::string get(const Gringo::Symbol& atom); }; template<> struct ParseImplAtom { static SymbolPacked get(const Gringo::Symbol& atom); }; template<> struct ParseImplAtom { static Gringo::Symbol get(const Gringo::Symbol& atom); }; template<> struct ParseImplAtom>{ static std::list get(const Gringo::Symbol& atom); }; template<> struct ParseImplAtom { static Expression get(const Gringo::Symbol& atom); }; template struct Parse_Impl { static void parse(Tuple& tup, Gringo::SymSpan::iterator arg) { const size_t tupleSize = std::tuple_size::value; typedef typename std::tuple_element < tupleSize - index, Tuple>::type ElType; ElType& el = std::get < tupleSize - index > (tup); Gringo::Symbol atom = *arg; el = ParseImplAtom::get(atom); Parse_Impl ::parse(tup, ++arg); } }; template struct Parse_Impl { static void parse(Tuple& tup, Gringo::SymSpan::iterator arg) { } }; template std::tuple ClaspLayer::parse(const Gringo::Symbol& atom) { typedef std::tuple < Types...> Tuple; Tuple tup; Parse_Impl::value>::parse(tup, atom.args().first); return tup; } } //end of xreate namespace #endif diff --git a/cpp/src/pass/abstractpass.h b/cpp/src/pass/abstractpass.h index a91d829..d09f83b 100644 --- a/cpp/src/pass/abstractpass.h +++ b/cpp/src/pass/abstractpass.h @@ -1,206 +1,207 @@ /* 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 */ #ifndef ABSTRACTPASS_H #define ABSTRACTPASS_H #include "ast.h" #include "xreatemanager.h" #include namespace xreate { /** \brief Holds current position in %AST while traversing*/ struct PassContext { const CodeScope* scope = 0; ManagedFnPtr function; ManagedRulePtr rule; std::string varDecl; PassContext() {} PassContext updateScope(const CodeScope* scopeNew) { PassContext context2{*this}; context2.scope = scopeNew; return context2; } ~PassContext(){} }; /** \brief Base class for all passes to inherit */ class IPass { public: IPass(PassManager* manager); + virtual ~IPass(){} /** \brief Executes pass */ virtual void run()=0; /** \brief Finalizes pass. Empty by default*/ virtual void finish(); PassManager* man; }; template Output defaultValue(); template<> void defaultValue(); /** \brief Stores processing results for already visited nodes */ template class SymbolCache: private std::map{ public: bool isCached(const Symbol& symbol){ return this->count(symbol); } Output setCachedValue(const Symbol& symbol, Output&& value){ (*this)[symbol] = value; return value; } Output getCachedValue(const Symbol& symbol){ assert(this->count(symbol)); return this->at(symbol); } }; /** \brief Set of already visited nodes */ template<> class SymbolCache: private std::set{ public: bool isCached(const Symbol& symbol){ bool result = this->count(symbol) > 0; return result; } void setCachedValue(const Symbol& symbol){ this->insert(symbol); } void getCachedValue(const Symbol& symbol){ } }; /** \brief Minimal useful IPass implementation*/ template class AbstractPass: public IPass { SymbolCache __visitedSymbols; protected: virtual Output processSymbol(const Symbol& symbol, PassContext context, const std::string& hintSymbol=""){ if (__visitedSymbols.isCached(symbol)) return __visitedSymbols.getCachedValue(symbol); const Expression& declaration = CodeScope::getDefinition(symbol, true); if (declaration.isDefined()){ PassContext context2 = context.updateScope(symbol.scope); Output&& result = process(declaration, context2, hintSymbol); return __visitedSymbols.setCachedValue(symbol, std::move(result)); } return defaultValue(); } Output processExpressionCall(const Expression& expression, PassContext context){ const std::string &calleeName = expression.getValueString(); std::list callees = man->root->getFunctionSpecializations(calleeName); if (callees.size() == 1 && callees.front()){ return processFnCall(callees.front(), context); } else { for (const ManagedFnPtr& callee: callees){ processFnCallUncertain(callee, context); } return defaultValue(); } } SymbolCache& getSymbolCache(){ return __visitedSymbols; } public: AbstractPass(PassManager* manager) : IPass(manager){} /** \brief Processes function invocation instruction */ virtual Output processFnCall(ManagedFnPtr functionCallee, PassContext context){ return defaultValue(); } /** \brief Processes function invocation instruction in uncertain cases * \details Executed when it's impossible statically determine exact function invocation. * In this case get executed for all possible candidates */ virtual void processFnCallUncertain(ManagedFnPtr functionCallee, PassContext context) {} /** \brief Processes Logic Rule */ virtual void process(ManagedRulePtr rule) {} /** \brief Processes Function */ virtual Output process(ManagedFnPtr function) { PassContext context; context.function = function; return process(function->getEntryScope(), context); } /** \brief Processes single CodeScope */ virtual Output process(CodeScope* scope, PassContext context, const std::string& hintBlockDecl=""){ context.scope = scope; return processSymbol(Symbol{ScopedSymbol::RetSymbol, scope}, context); } //TODO expose Symbol instead of varDecl. Required by DFAPass. /** \brief Processes single Expression */ virtual Output process(const Expression& expression, PassContext context, const std::string& varDecl=""){ if (expression.__state == Expression::IDENT){ assert(context.scope); return processSymbol(Attachments::get(expression), context, expression.getValueString()); } assert(false); return defaultValue(); } /** \brief Executes AST traverse */ void run() { ManagedRulePtr rule = man->root->begin(); while (rule.isValid()) { process(rule); ++rule; } ManagedFnPtr f = man->root->begin(); while (f.isValid()) { process(f); ++f; } } }; template<> void AbstractPass::processSymbol(const Symbol& symbol, PassContext context, const std::string& hintSymbol); template<> void AbstractPass::process(const Expression& expression, PassContext context, const std::string& hintSymbol); } #endif diff --git a/cpp/src/pass/cfapass.cpp b/cpp/src/pass/cfapass.cpp index a317acd..e4fdcb4 100644 --- a/cpp/src/pass/cfapass.cpp +++ b/cpp/src/pass/cfapass.cpp @@ -1,124 +1,196 @@ /* 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 using namespace std; using namespace xreate::cfa; void -CFAPass::initSignatures(){ +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 CFAPass::run(){ +void +CFAPassBasic::run(){ initSignatures(); return AbstractPass::run(); } void -CFAPass::finish() -{ +CFAPassBasic::finish(){ man->clasp->registerReport(__context.graph); dominators::DominatorsTreeAnalysisProvider* reportDominators = new dominators::DominatorsTreeAnalysisProvider(); - reportDominators->run(man->clasp, __context.graph); + reportDominators->run(__context.graph); man->clasp->registerReport(reportDominators); return AbstractPass::finish(); } void -CFAPass::processFnCall(ManagedFnPtr function, PassContext context) -{ +CFAPassBasic::processFnCall(ManagedFnPtr function, PassContext context){ ClaspLayer* clasp = man->clasp; __context.graph->addCallConnection(clasp->pack(context.scope), function->getName()); return AbstractPass::processFnCall(function, context); } void -CFAPass::processFnCallUncertain(ManagedFnPtr function, PassContext context){ +CFAPassBasic::processFnCallUncertain(ManagedFnPtr function, PassContext context){ ClaspLayer* clasp = man->clasp; __context.graph->addCallConnection(clasp->pack(context.scope), function->getName()); return AbstractPass::processFnCallUncertain(function, context); } void -CFAPass::process(CodeScope* scope, PassContext context, const std::string& hintBlockDecl){ +CFAPassBasic::process(CodeScope* scope, PassContext context, const std::string& hintBlockDecl){ ClaspLayer* clasp = man->clasp; const CodeScope* scopeParent = context.scope; ScopePacked scopeId = clasp->pack(scope); + //Parent Relations if (scopeParent){ - __context.graph->addParentConnection(scopeId, clasp->pack(scopeParent)); + __context.graph->addParentConnection(scopeId, clasp->pack(scopeParent)); } else { - __context.graph->addParentConnection(scopeId, context.function->getName()); + __context.graph->addParentConnection(scopeId, context.function->getName()); } - //TOTEST scope annotations - //SECTIONTAG context gather scope annotations + //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 -CFAPass::process(const Expression& expression, PassContext context, const std::string& varDecl){ +CFAPassBasic::process(const Expression& expression, PassContext context, const std::string& varDecl){ ClaspLayer* clasp = man->clasp; 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(clasp->pack(expression.blocks.front()), scheme.second.getOperands()); } } } return AbstractPass::process(expression, context, varDecl); } void -CFAPass::process(ManagedFnPtr function) -{ +CFAPassBasic::process(ManagedFnPtr function){ __context.graph->addFunctionAnnotations(function->getName(), function->getTags()); return AbstractPass::process(function); } -CFAPass::CFAPass(PassManager* manager) - : AbstractPass(manager) +CFAPassBasic::CFAPassBasic(PassManager* manager) +: AbstractPass(manager) , __context{new CFAGraph(manager->clasp)} {} +/****************************SCOPE DEPENDENCIES********************************/ +void +CFAPassDependenciesDecorator::process(const Expression& expression, PassContext context, const std::string& varDecl){ + ClaspLayer* clasp = man->clasp; + + if (expression.__state == Expression::COMPOUND) + switch(expression.op){ + case Operator::SEQUENCE:{ + ScopePacked scopePrev = clasp->pack(expression.blocks.front()); + for(auto scopeIt= ++expression.blocks.begin(); scopeIt != expression.blocks.end(); ++scopeIt){ + ScopePacked scopeCurrent = clasp->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){ + ClaspLayer* clasp = man->clasp; + + const CodeScope* scopeCaller = context.scope; + assert(scopeCaller); + ScopePacked scopeCallerPacked = clasp->pack(scopeCaller); + + if(__context.graph->isDependent(scopeCallerPacked)){ + ScopePacked scopeCalleePacked = clasp->pack(function->getEntryScope()); + __context.graph->transmitDependencies(scopeCalleePacked, scopeCallerPacked); + } + + Parent::processFnCall(function, context); +} + +void +CFAPassDependenciesDecorator::processFnCallUncertain(ManagedFnPtr function, PassContext context){ + ClaspLayer* clasp = man->clasp; + + const CodeScope* scopeCaller = context.scope; + assert(scopeCaller); + ScopePacked scopeCallerPacked = clasp->pack(scopeCaller); + + if(__context.graph->isDependent(scopeCallerPacked)){ + ScopePacked scopeCalleePacked = clasp->pack(function->getEntryScope()); + __context.graph->transmitDependencies(scopeCalleePacked, scopeCallerPacked); + } + + Parent::processFnCallUncertain(function, context); +} + +void +CFAPassDependenciesDecorator::process(CodeScope* scope, + PassContext context, const std::string& hintBlockDecl){ + + ClaspLayer* clasp = man->clasp; + const CodeScope* scopeParent = context.scope; + + if (scopeParent){ + ScopePacked scopePacked = clasp->pack(scope); + ScopePacked scopeParentPacked = clasp->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 */ \ No newline at end of file diff --git a/cpp/src/pass/cfapass.h b/cpp/src/pass/cfapass.h index 7e12062..6351126 100644 --- a/cpp/src/pass/cfapass.h +++ b/cpp/src/pass/cfapass.h @@ -1,49 +1,67 @@ /* 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 * * cfapass.cpp * Control Flow Graph building pass */ #ifndef CFGPASS_H #define CFGPASS_H #include "xreatemanager.h" #include "clasplayer.h" #include "abstractpass.h" namespace xreate{namespace cfa { class CFAGraph; /** \brief Control Flow Analysis Pass(%CFA)*/ -class CFAPass : public AbstractPass -{ +class CFAPassBasic : public AbstractPass{ public: void process(ManagedFnPtr function) override; void processFnCall(ManagedFnPtr function, PassContext context) override; void processFnCallUncertain(ManagedFnPtr function, PassContext context) override; void process(CodeScope* scope, PassContext context, const std::string& hintBlockDecl="") override; void process(const Expression& expression, PassContext context, const std::string& varDecl="") override; - CFAPass(PassManager* manager); - + CFAPassBasic(PassManager* manager); void finish() override; void run() override; -private: + + const CFAGraph* getReport() const {return __context.graph; } + +protected: struct { CFAGraph* graph; } __context; std::multimap __signatures; //CFA data for particular operators void initSignatures(); }; +class CFAPassDependenciesDecorator: public CFAPassBasic{ + typedef CFAPassBasic Parent; + +public: + CFAPassDependenciesDecorator(PassManager* manager): CFAPassBasic(manager) {} + + void process(const Expression& expression, PassContext context, const std::string& varDecl) override; + void processFnCall(ManagedFnPtr function, PassContext context) override; + void processFnCallUncertain(ManagedFnPtr function, PassContext context) override; + void process(CodeScope* scope, PassContext context, const std::string& hintBlockDecl) override; +}; + +class CFAPass: public CFAPassDependenciesDecorator{ +public: + CFAPass(PassManager* manager): CFAPassDependenciesDecorator(manager) {} +}; + }} //end of namespace xreate::cfa #endif // CFGPASS_H diff --git a/cpp/tests/cfa.cpp b/cpp/tests/cfa.cpp index 65ee929..0f8075e 100644 --- a/cpp/tests/cfa.cpp +++ b/cpp/tests/cfa.cpp @@ -1,122 +1,197 @@ /* Any copyright is dedicated to the Public Domain. * http://creativecommons.org/publicdomain/zero/1.0/ * * testsCFG.cpp * * Created on: Jul 17, 2015 * Author: pgess */ #include "xreatemanager.h" #include "pass/dfapass.h" #include "pass/cfapass.h" #include "analysis/DominatorsTreeAnalysisProvider.h" #include "gtest/gtest.h" +#include "analysis/cfagraph.h" #include #include using namespace xreate; using namespace xreate::cfa; using namespace std; TEST(CFA, testFunctionAnnotationsClasp){ 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(); ClaspLayer::ModelFragment answer = man->clasp->query("annotationF1"); int countNoneValue = 0; if (answer) countNoneValue = std::distance(answer->first, answer->second); EXPECT_EQ(1, countNoneValue); answer = man->clasp->query("annotationF2"); countNoneValue = 0; if (answer) countNoneValue = std::distance(answer->first, answer->second); EXPECT_EQ(1, countNoneValue); } 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 {" " f1 = function::int {\n" " x = 0:: int. " " x\n" " }" "}" ); man->analyse(); ClaspLayer::ModelFragment model = man->clasp->query("annotation1"); ScopePacked scopeIdActual = std::get<0>(ClaspLayer::parse(model->first->second)); CodeScope* scopeEntry = man->root->findFunction("main")->getEntryScope(); const Expression& exprSum = scopeEntry->getDefinition(scopeEntry->getSymbol("sum")); CodeScope* scopeExpected = exprSum.blocks.front(); ScopePacked scopeIdExpected = man->clasp->pack(scopeExpected); ASSERT_EQ(scopeIdExpected, scopeIdActual); } -TEST(CFA, CFGRoots){ +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->clasp->pack(scopeSeq1); + ScopePacked psSeq2 = man->clasp->pack(scopeSeq2); + ScopePacked psB = man->clasp->pack(scopeB); + + CFAPass* pass = new CFAPass(man); + + man->registerPass(pass, PassId::CFGPass); + man->executePasses(); + const CFAGraph* report = dynamic_cast(man->getPassById(PassId::CFGPass))->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->clasp->pack(scopeSeq1); + ScopePacked psSeq2 = man->clasp->pack(scopeSeq2); + ScopePacked psIf1 = man->clasp->pack(scopeIf1); + ScopePacked psIf2 = man->clasp->pack(scopeIf2); + + CFAPass* pass = new CFAPass(man); + + man->registerPass(pass, PassId::CFGPass); + man->executePasses(); + const CFAGraph* report = dynamic_cast(man->getPassById(PassId::CFGPass))->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){ std::string program = R"CODE( - main = function::int{a()+ b()} - a= function::int {c1() + c2()} - b= function::int {c2()} - c1=function::int{0} - c2=function::int{0} + a = function:: int; entry{ + seq + {x = 0:: int. x} + {x = 1:: int. x}::int + } )CODE"; - std::unique_ptr man(details::tier1::XreateManager::prepare(move(program))); - man->analyse(); + std::unique_ptr man(details::tier2::XreateManager::prepare(move(program))); + + CFAPass* pass = new CFAPass(man.get()); + man->registerPass(pass, PassId::CFGPass); + pass->run(); + + ScopePacked scope1 = man->clasp->pack(man->root->findFunction("a")->getEntryScope()->getBody().blocks.front()); + ScopePacked scope2 = man->clasp->pack(*++man->root->findFunction("a")->getEntryScope()->getBody().blocks.begin()); + + dominators::DominatorsTreeAnalysisProvider* providerDomAnalysis = new dominators::DominatorsTreeAnalysisProvider(); + providerDomAnalysis->run(pass->getReport()); + + dominators::DominatorsTreeAnalysisProvider::Dominators expectedFDom= { + {1, {0, 3}} + ,{2, {1, 2}} + }; + + dominators::DominatorsTreeAnalysisProvider::Dominators expectedPostDom= { + {2, {0, 3}} + ,{1, {1, 2}} + }; + + auto actualFDom = providerDomAnalysis->getForwardDominators(); + auto actualPostDom = providerDomAnalysis->getPostDominators(); + + ASSERT_EQ(expectedFDom, actualFDom); + ASSERT_EQ(expectedPostDom, actualPostDom); -// manager->registerPass(new CFAPass(manager.get()) , PassId::CFGPass); -// manager->executePasses(); -// manager->clasp->run(); -// -// dominators::DominatorsTreeAnalysisProvider domProvider; -// domProvider.run(manager->clasp); -// -// dominators::DominatorsTreeAnalysisProvider::Dominators expectedFDom= { -// {0, {0, 9}} -// ,{1, {1, 4}} -// ,{2, {7, 8}} -// ,{3, {2, 3}} -// ,{4, {5, 6}} -// }; -// -// dominators::DominatorsTreeAnalysisProvider::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()); + delete providerDomAnalysis; + delete pass; }