No OneTemporary
Actions

Subscribers

None

File Metadata

Created: Sun, Feb 15, 11:42 PM

View Options

	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 <v.melnychenko@xreate.org>
	*
	* 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 <list>
	#include <iostream>
	#include <boost/format.hpp>

	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<ScopeNode*> nodesFrom;
	+ std::list<ScopeNode*> nodesTo;
	};

	-/*
	-bool operator !=(const Node& a, const Node& b){
	- return (a.tree != b.tree) \|\| (a.scope != b.scope);
	-}
	+struct CFAGraphAdapter {
	+ std::list<ScopeNode> 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<ScopePacked>, multiset_of<ScopePacked>> CHILD_RELATIONS;
	- CHILD_RELATIONS edges;
	- std::vector<Node> 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<unsigned int, NODE_MARK> 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; i<tree->size; ++i){
	- tree->nodes[i]= Node{(unsigned int) i, tree};
	+ std::list<ScopePacked> nodeRoots;
	+ for(auto nodeMark: nodeMarks){
	+ if(nodeMark.second == POSSIBLE_ROOT) nodeRoots.push_back(nodeMark.first);
	}

	- return tree;
	- }
	-
	- std::list<unsigned int> getRootFunctions() const{
	- size_t idMax = size;
	- size_t id =0;
	- std::list<unsigned int> 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<Node*> {
	- typedef Node* nodes_iterator;
	- typedef Node NodeType;
	-
	- typedef std::function<Node*(ControlFlowTree::CHILD_RELATIONS::left_value_type)> Transformer;
	- typedef typename boost::transform_iterator<Transformer, ControlFlowTree::CHILD_RELATIONS::left_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<ScopeNode*> {
	+ typedef ScopeNode NodeType;
	+ typedef std::list<ScopeNode*>::iterator ChildIteratorType;

	- return boost::make_transform_iterator(range.second, x);
	- }
	- };
	+ static ChildIteratorType
	+ child_begin(NodeType* node) {
	+ return node->nodesTo.begin();
	+ }

	- template <> struct GraphTraits<Inverse<Node*>> {
	- typedef Node* nodes_iterator;
	- typedef Node NodeType;
	+ static ChildIteratorType
	+ child_end(NodeType* node) {
	+ return node->nodesTo.end();
	+ }
	+};

	- typedef std::function<Node*(ControlFlowTree::CHILD_RELATIONS::right_value_type)> Transformer;
	- typedef typename boost::transform_iterator<Transformer, ControlFlowTree::CHILD_RELATIONS::right_iterator> ChildIteratorType;
	+template<>
	+struct GraphTraits<CFAGraphAdapter> : public GraphTraits<ScopeNode> {
	+ typedef std::list<ScopeNode>::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<ControlFlowTree>: public GraphTraits<Node> {
	- static NodeType*
	- getEntryNode(ControlFlowTree* F) {
	- if (F->entry) return F->entry;

	- list<unsigned int>&& roots = F->getRootFunctions();
	- assert(roots.size()==1);
	+template<>
	+struct GraphTraits<Inverse<ScopeNode*>>
	+{
	+ typedef ScopeNode NodeType;
	+ typedef std::list<ScopeNode*>::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<Node> {
	+namespace xreate {
	+namespace dominators {
	+
	+class DominatorTree : public llvm::DominatorTreeBase<ScopeNode> {
	public:
	DominatorsTreeAnalysisProvider::Dominators dominators;

	- DominatorTree(bool isPostDom): llvm::DominatorTreeBase<Node>(isPostDom) {}
	+ DominatorTree(bool isPostDom) : llvm::DominatorTreeBase<ScopeNode>(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<<formatAtom%(entry.first)%(entry.second.first)%(entry.second.second)
	+ <<endl;
	}
	}
	};

	void
	-DominatorsTreeAnalysisProvider::run(const ClaspLayer* engine, cfa::CFAGraph* graph){
	- boost::scoped_ptr<ControlFlowTree> program(ControlFlowTree::build(engine, graph));
	+DominatorsTreeAnalysisProvider::run(const cfa::CFAGraph* graph) {
	+ boost::scoped_ptr<CFAGraphAdapter> 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<Node*> Traits;
	// for (size_t i=0; i<size; ++i){
	//
	// for (auto j = Traits::child_begin(&nodes[i]); j!= Traits::child_end(&nodes[i]); ++j){
	// cout << 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 <v.melnychenko@xreate.org>
	*
	* Created on May 13, 2016, 11:39 AM
	*/

	#ifndef DOMINATORSTREEANALYSISPROVIDER_H
	#define DOMINATORSTREEANALYSISPROVIDER_H

	#include "clasplayer.h"
	#include <boost/smart_ptr/scoped_ptr.hpp>

	namespace xreate{namespace dominators{
	class DominatorTree;

	/** \brief Dominators Analysis report */
	class DominatorsTreeAnalysisProvider: public IAnalysisReport {
	public:
	typedef std::pair<ScopePacked, ScopePacked> DominatedRange;
	typedef std::map<ScopePacked, DominatedRange> 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<DominatorTree> treeForwardDominators;
	boost::scoped_ptr<DominatorTree> 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 <v.melnychenko@xreate.org>
	*
	* 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<string> 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<string> 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<ManagedFnPtr>& functions = __clasp->ast->getAllFunctions();
	for (auto f: functions){
	if (f->guardContext.isValid()){
	list<string> 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<ScopePacked, ScopePacked> __dependencyRelations;
	}

	void
	CFAGraph::addFunctionAnnotations(const std::string& function, const std::map<std::string, Expression>& tags) {
	unsigned int fid = registerNodeFunction(function);

	for (auto& tag: tags){
	__functionTags.emplace(fid, tag.second);
	}
	}

	void
	CFAGraph::addScopeAnnotations(const ScopePacked& scope, const std::vector<Expression>& tags){
	for (Expression tag: tags){
	__scopeTags.emplace(scope, tag);
	}
	}

	void
	CFAGraph::addContextRules(const ScopePacked& scope, const std::vector<Expression>& 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<ScopePacked> 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 <v.melnychenko@xreate.org>
	*
	* 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<ScopePacked, boost::bimaps::multiset_of<unsigned int>> PARENT_FUNCTION_RELATIONS;
	PARENT_FUNCTION_RELATIONS __parentFunctionRelations;
	std::map<ScopePacked, ScopePacked> __parentScopeRelations;
	+ std::multimap<ScopePacked, ScopePacked> __dependencyRelations;

	typedef boost::bimap<
	boost::bimaps::multiset_of<ScopePacked>,
	boost::bimaps::multiset_of<unsigned int>,
	boost::bimaps::set_of_relation<>
	> CALL_RELATIONS;

	CALL_RELATIONS __callRelations;

	boost::bimap<unsigned int, std::string > __nodesFunction;
	std::multimap<unsigned int, Expression> __functionTags;
	std::multimap<ScopePacked, Expression> __scopeTags;
	std::multimap<ScopePacked, ContextRule> __contextRules;

	void print(std::ostringstream& output) const override;
	CFAGraph(ClaspLayer* engine): __clasp(engine){}

	void addFunctionAnnotations(const std::string& function, const std::map<std::string, Expression>& tags);
	void addScopeAnnotations(const ScopePacked& scope, const std::vector<Expression>&tags);
	void addContextRules(const ScopePacked& scope, const std::vector<Expression>&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 <v.melnychenko@xreate.org>
	* File: clasplayer.h
	*/

	#ifndef CLASPLAYER_H
	#define CLASPLAYER_H

	#include "ast.h"
	#include "contextrule.h"

	#include <clingo/clingocontrol.hh>
	#include <string>
	#include <climits>
	#include <boost/bimap.hpp>
	#include <boost/bimap/multiset_of.hpp>
	#include <boost/optional.hpp>
	#include <boost/scoped_ptr.hpp>
	#include <list>
	+#include <limits>

	namespace xreate {

	typedef unsigned int ScopePacked;
	+const ScopePacked SCOPE_ABSTRACT_GLOBAL = std::numeric_limits<ScopePacked>::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<IAnalysisReport*> __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<class ...Types>
	static std::tuple<Types...> parse(const Gringo::Symbol& atom);

	typedef std::multimap<std::string, Gringo::Symbol>::const_iterator ModelIterator;
	typedef boost::optional<std::pair<ClaspLayer::ModelIterator, ClaspLayer::ModelIterator>> 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<QueryId, IQuery*> __queries;
	std::multimap<std::string, Gringo::Symbol> __model;
	std::map<SymbolPacked, std::string> __indexSymbolNameHints;
	std::unordered_map<const CodeScope*, unsigned int> __indexScopes;
	std::vector<const CodeScope*> __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<unsigned int, std::string> __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<class typ>
	struct ParseImplAtom {

	static typ get(const Gringo::Symbol& atom) {
	return atom.num();
	}
	};

	template<>
	struct ParseImplAtom<int> {
	static int get(const Gringo::Symbol& atom);
	};

	template<>
	struct ParseImplAtom<std::string> {
	static std::string get(const Gringo::Symbol& atom);
	};

	template<>
	struct ParseImplAtom<SymbolPacked> {
	static SymbolPacked get(const Gringo::Symbol& atom);
	};

	template<>
	struct ParseImplAtom<Gringo::Symbol> {
	static Gringo::Symbol get(const Gringo::Symbol& atom);
	};

	template<>
	struct ParseImplAtom<std::list<Gringo::Symbol>>{
	static std::list<Gringo::Symbol> get(const Gringo::Symbol& atom);
	};

	template<>
	struct ParseImplAtom<Expression> {
	static Expression get(const Gringo::Symbol& atom);
	};

	template<class Tuple, size_t index>
	struct Parse_Impl {

	static void parse(Tuple& tup, Gringo::SymSpan::iterator arg) {
	const size_t tupleSize = std::tuple_size<Tuple>::value;
	typedef typename std::tuple_element < tupleSize - index, Tuple>::type ElType;

	ElType& el = std::get < tupleSize - index > (tup);

	Gringo::Symbol atom = *arg;
	el = ParseImplAtom<ElType>::get(atom);

	Parse_Impl<Tuple, index - 1 > ::parse(tup, ++arg);
	}
	};

	template<class Tuple>
	struct Parse_Impl<Tuple, 0> {

	static void parse(Tuple& tup, Gringo::SymSpan::iterator arg) {
	}
	};

	template<class ...Types>
	std::tuple<Types...>
	ClaspLayer::parse(const Gringo::Symbol& atom) {
	typedef std::tuple < Types...> Tuple;
	Tuple tup;
	Parse_Impl<Tuple, std::tuple_size<Tuple>::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 <v.melnychenko@xreate.org>
	*/

	#ifndef ABSTRACTPASS_H
	#define ABSTRACTPASS_H
	#include "ast.h"
	#include "xreatemanager.h"

	#include<iostream>
	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<class Output>
	Output defaultValue();

	template<>
	void defaultValue<void>();

	/** \brief Stores processing results for already visited nodes */
	template<class Output>
	class SymbolCache: private std::map<Symbol, Output>{
	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<void>: private std::set<Symbol>{
	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 Output>
	class AbstractPass: public IPass {
	SymbolCache<Output> __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>();
	}

	Output processExpressionCall(const Expression& expression, PassContext context){
	const std::string &calleeName = expression.getValueString();
	std::list<ManagedFnPtr> 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<Output>();
	}
	}

	SymbolCache<Output>& getSymbolCache(){
	return __visitedSymbols;
	}

	public:
	AbstractPass(PassManager* manager)
	: IPass(manager){}

	/** \brief Processes function invocation instruction */
	virtual Output processFnCall(ManagedFnPtr functionCallee, PassContext context){
	return defaultValue<Output>();
	}

	/** \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<IdentifierSymbol>(expression), context, expression.getValueString());
	}

	assert(false);
	return defaultValue<Output>();
	}

	/** \brief Executes AST traverse */
	void run() {
	ManagedRulePtr rule = man->root->begin<MetaRuleAbstract>();
	while (rule.isValid()) {
	process(rule);
	++rule;
	}

	ManagedFnPtr f = man->root->begin<Function>();
	while (f.isValid()) {
	process(f);
	++f;
	}
	}

	};

	template<>
	void
	AbstractPass<void>::processSymbol(const Symbol& symbol, PassContext context, const std::string& hintSymbol);

	template<>
	void
	AbstractPass<void>::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 <v.melnychenko@xreate.org>
	*/

	/**
	* \file cfapass.h
	* \brief Control Flow Analysis(CFA)
	*/

	#include "cfapass.h"
	#include "analysis/cfagraph.h"
	#include "analysis/DominatorsTreeAnalysisProvider.h"

	#include <boost/range/iterator_range_core.hpp>

	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 <v.melnychenko@xreate.org>
	*
	* 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<void>
	-{
	+class CFAPassBasic : public AbstractPass<void>{
	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<Operator, Expression> __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 <v.melnychenko@xreate.org>
	*/

	#include "xreatemanager.h"
	#include "pass/dfapass.h"
	#include "pass/cfapass.h"

	#include "analysis/DominatorsTreeAnalysisProvider.h"

	#include "gtest/gtest.h"
	+#include "analysis/cfagraph.h"

	#include <boost/scoped_ptr.hpp>
	#include <boost/smart_ptr/scoped_array.hpp>

	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<ScopePacked>(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<CFAPassBasic*>(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<CFAPassBasic*>(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<details::tier1::XreateManager> man(details::tier1::XreateManager::prepare(move(program)));
	- man->analyse();
	+ std::unique_ptr<details::tier2::XreateManager> 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;
	}

No OneTemporaryActions

File Metadata

View Options

Event Timeline

No OneTemporary
Actions