DominatorsTreeAnalysisProvider.cpp
No OneTemporary
Actions

Subscribers

None

File Metadata

Created: Fri, Mar 13, 2:36 AM

DominatorsTreeAnalysisProvider.cpp
View Options

	/*
	* To change this license header, choose License Headers in Project Properties.
	* To change this template file, choose Tools \| Templates
	* and open the template in the editor.
	*/

	/*
	* File: DominatorsTreeAnalysisProvider.cpp
	* Author: pgess
	*
	* Created on May 13, 2016, 11:39 AM
	*/

	#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;

	struct ControlFlowTree;

	struct Node {
	ScopePacked scope;
	ControlFlowTree* tree;
	};

	/*
	bool operator !=(const Node& a, const Node& b){
	return (a.tree != b.tree) \|\| (a.scope != b.scope);
	}

	Node& operator++(Node& a){
	++a.scope;
	return a;
	}
	*/

	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;

	ControlFlowTree(const size_t nodesCount): nodes(nodesCount), size(nodesCount){
	}

	static ControlFlowTree* build(const ClaspLayer* engine){
	ControlFlowTree* tree = new ControlFlowTree(engine->getScopesCount());

	xreate::analysis::CFAGraph* graph = engine->dataCFA.get();

	for (const auto& edge: graph->__parentScopeRelations){
	tree->edges.insert(CHILD_RELATIONS::value_type(edge.second, edge.first));
	}

	for (const auto& edge: graph->__callRelations){
	unsigned int calleeFunction = edge.right;
	ScopePacked caller = edge.left;

	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));
	}
	}

	for (size_t i=0; i<tree->size; ++i){
	tree->nodes[i]= Node{(unsigned int) i, tree};
	}

	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);
	}

	++id;
	}

	return std::move(results);
	}
	};

	namespace llvm {
	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);
	}

	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];};

	return boost::make_transform_iterator(range.second, x);
	}
	};

	template <> struct GraphTraits<Inverse<Node*>> {
	typedef Node* nodes_iterator;
	typedef Node NodeType;

	typedef std::function<Node*(ControlFlowTree::CHILD_RELATIONS::right_value_type)> Transformer;
	typedef typename boost::transform_iterator<Transformer, ControlFlowTree::CHILD_RELATIONS::right_iterator> ChildIteratorType;

	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];};

	return boost::make_transform_iterator(range.first, x);
	}

	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];};

	return boost::make_transform_iterator(range.second, x);
	}
	};

	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);

	return F->entry = &F->nodes[roots.front()];
	}

	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; }
	};
	}

	class xreate::DominatorTree: public llvm::DominatorTreeBase<Node> {
	public:
	DominatorsTreeAnalysisProvider::Dominators dominators;

	DominatorTree(bool isPostDom): llvm::DominatorTreeBase<Node>(isPostDom) {}

	void run(ControlFlowTree& program){
	recalculate(program);

	//extract dominators info
	for (auto& entry: DomTreeNodes){
	if (!entry.getFirst()) continue;

	dominators.emplace(entry.getFirst()->scope, 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
	DominatorsTreeAnalysisProvider::run(const ClaspLayer* engine){
	boost::scoped_ptr<ControlFlowTree> program(ControlFlowTree::build(engine));

	treeForwardDominators->run(*program);
	treePostDominators->run(*program);
	}

	void
	DominatorsTreeAnalysisProvider::print(std::ostringstream& output) const{
	treeForwardDominators->print(output, "cfa_forwdom");
	treePostDominators->print(output, "cfa_postdom");
	}

	const DominatorsTreeAnalysisProvider::Dominators&
	DominatorsTreeAnalysisProvider::getForwardDominators() const{
	return treeForwardDominators->dominators;
	}

	const DominatorsTreeAnalysisProvider::Dominators&
	DominatorsTreeAnalysisProvider::getPostDominators() const{
	return treePostDominators->dominators;
	}

	DominatorsTreeAnalysisProvider::DominatorsTreeAnalysisProvider()
	: treeForwardDominators(new DominatorTree(false))
	, treePostDominators(new DominatorTree(true))
	{}

	DominatorsTreeAnalysisProvider::~DominatorsTreeAnalysisProvider() {}

	//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;
	// }
	// }
	//}

DominatorsTreeAnalysisProvider.cppNo OneTemporaryActions

File Metadata

DominatorsTreeAnalysisProvider.cppView Options

Event Timeline

DominatorsTreeAnalysisProvider.cpp
No OneTemporary
Actions

DominatorsTreeAnalysisProvider.cpp
View Options