Page Menu
Home
Xreate
Search
Configure Global Search
Log In
Docs
Questions
Repository
Issues
Patches
Internal API
Files
F4001849
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
Thu, Jul 9, 6:50 AM
Size
6 KB
Mime Type
text/x-c++
Expires
Sat, Jul 11, 6:50 AM (1 d, 3 h)
Engine
blob
Format
Raw Data
Handle
273485
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 CFAGraphAdapter;
struct ScopeNode {
ScopePacked id;
std::list<ScopeNode*> nodesFrom;
std::list<ScopeNode*> nodesTo;
};
struct CFAGraphAdapter {
std::list<ScopeNode> nodes;
ScopeNode* nodeRoot;
ScopeNode* getOrCreateNode(ScopePacked id){
ScopeNode elemNew; elemNew.id = id;
auto fnComp = [](const ScopeNode &a, const ScopeNode &b){return a.id < b.id;};
auto posLowerBound = std::lower_bound(nodes.begin(), nodes.end(), elemNew, fnComp);
if(posLowerBound==nodes.end()|| posLowerBound->id > id){
return &*nodes.insert(posLowerBound, elemNew);
}
return &*posLowerBound;
}
static CFAGraphAdapter* build(const cfa::CFAGraph* graph) {
CFAGraphAdapter* tree=new CFAGraphAdapter();
enum NODE_MARK{NO_ROOT, POSSIBLE_ROOT};
std::unordered_map<unsigned int, NODE_MARK> nodeMarks;
for (const auto& edge: graph->__dependencyRelations){
ScopeNode* nodeTo = tree->getOrCreateNode(edge.first);
ScopeNode* nodeFrom = tree->getOrCreateNode(edge.second);
nodeTo->nodesFrom.push_back(nodeFrom);
nodeFrom->nodesTo.push_back(nodeTo);
nodeMarks.emplace(edge.second, POSSIBLE_ROOT); //weak optional insert
auto result = nodeMarks.emplace(edge.first, NO_ROOT); //strong insert or update
if(!result.second){
result.first->second = NO_ROOT;
}
}
std::list<ScopePacked> nodeRoots;
for(auto nodeMark: nodeMarks){
if(nodeMark.second == POSSIBLE_ROOT) nodeRoots.push_back(nodeMark.first);
}
if(nodeRoots.size()>1){
ScopeNode* nodeGlobalRoot = tree->getOrCreateNode(SCOPE_ABSTRACT_GLOBAL);
for(auto rootLocal: nodeRoots){
ScopeNode* nodeLocalRoot = tree->getOrCreateNode(rootLocal);
nodeLocalRoot->nodesFrom.push_back(nodeGlobalRoot);
nodeGlobalRoot->nodesTo.push_back(nodeLocalRoot);
}
} else {
assert(nodeRoots.size()==1);
tree->nodeRoot = tree->getOrCreateNode(nodeRoots.front());
}
return tree;
}
CFAGraphAdapter() { }
};
}
} //end of namespace xreate::dominators
namespace llvm {
using namespace xreate::dominators;
template<>
struct GraphTraits<ScopeNode*> {
typedef ScopeNode NodeType;
typedef std::list<ScopeNode*>::iterator ChildIteratorType;
static ChildIteratorType
child_begin(NodeType* node) {
return node->nodesTo.begin();
}
static ChildIteratorType
child_end(NodeType* node) {
return node->nodesTo.end();
}
};
template<>
struct GraphTraits<CFAGraphAdapter*> : public GraphTraits<ScopeNode*> {
typedef std::list<ScopeNode>::iterator nodes_iterator;
static nodes_iterator
nodes_begin(CFAGraphAdapter* graph) {
return graph->nodes.begin();
}
static nodes_iterator
nodes_end(CFAGraphAdapter* graph) {
return graph->nodes.end();
}
static NodeType*
getEntryNode(CFAGraphAdapter* F) {
return F->nodeRoot;
}
static unsigned int
size(CFAGraphAdapter* graph) {
return graph->nodes.size();
}
};
template<>
struct GraphTraits<Inverse<ScopeNode*>>
{
typedef ScopeNode NodeType;
typedef std::list<ScopeNode*>::iterator ChildIteratorType;
static ChildIteratorType
child_begin(NodeType* node) {
return node->nodesFrom.begin();
}
static ChildIteratorType
child_end(NodeType* node) {
return node->nodesFrom.end();
}
};
}
namespace xreate {
namespace dominators {
class DominatorTree : public llvm::DominatorTreeBase<ScopeNode> {
public:
DominatorsTreeAnalysisProvider::Dominators dominators;
DominatorTree(bool isPostDom) : llvm::DominatorTreeBase<ScopeNode>(isPostDom) { }
void
run(CFAGraphAdapter& program) {
recalculate(program);
//extract dominators info
for(auto& entry : DomTreeNodes) {
if(!entry.getFirst()) continue;
dominators.emplace(entry.getFirst()->id, make_pair(entry.getSecond()->getDFSNumIn(), entry.getSecond()->getDFSNumOut()));
}
}
void
print(std::ostringstream& output, const std::string& atom) const {
boost::format formatAtom(atom+"(%1%, range(%2%, %3%)).");
for(auto entry : dominators) {
output<<formatAtom%(entry.first)%(entry.second.first)%(entry.second.second)
<<endl;
}
}
};
void
DominatorsTreeAnalysisProvider::run(const cfa::CFAGraph* graph) {
boost::scoped_ptr<CFAGraphAdapter> program(CFAGraphAdapter::build(graph));
treeForwardDominators->run(*program);
treePostDominators->run(*program);
}
void
DominatorsTreeAnalysisProvider::print(std::ostringstream& output) const {
treeForwardDominators->print(output, "cfa_forwdom");
treePostDominators->print(output, "cfa_postdom");
}
const DominatorsTreeAnalysisProvider::Dominators&
DominatorsTreeAnalysisProvider::getForwardDominators() const {
return treeForwardDominators->dominators;
}
const DominatorsTreeAnalysisProvider::Dominators&
DominatorsTreeAnalysisProvider::getPostDominators() const {
return treePostDominators->dominators;
}
DominatorsTreeAnalysisProvider::DominatorsTreeAnalysisProvider()
: 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