Page Menu
Home
Xreate
Search
Configure Global Search
Log In
Docs
Questions
Repository
Issues
Patches
Internal API
Files
F3995294
DominatorsTreeAnalysisProvider.cpp
No One
Temporary
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Mute Notifications
Subscribers
None
File Metadata
Details
File Info
Storage
Attached
Created
Tue, Jul 7, 1:35 AM
Size
7 KB
Mime Type
text/x-c++
Expires
Thu, Jul 9, 1:35 AM (5 h, 21 m)
Engine
blob
Format
Raw Data
Handle
271533
Attached To
rXR Xreate
DominatorsTreeAnalysisProvider.cpp
View Options
/* 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 {
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());
cfa::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);
}
};
}} //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);
}
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; }
};
}
namespace xreate{ namespace dominators {
class 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() {}
}} //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;
// }
// }
//}
Event Timeline
Log In to Comment