Page Menu
Home
Xreate
Search
Configure Global Search
Log In
Docs
Questions
Repository
Issues
Patches
Internal API
Files
F3999690
DominatorsAnalysisProvider.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, 2:47 AM
Size
7 KB
Mime Type
text/x-c++
Expires
Sat, Jul 11, 2:47 AM (1 d, 6 h)
Engine
blob
Format
Raw Data
Handle
273157
Attached To
rXR Xreate
DominatorsAnalysisProvider.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: DominatorsAnalysisProvider.cpp
* Author: pgess <v.melnychenko@xreate.org>
*
* Created on May 13, 2016, 11:39 AM
*/
/**
* \file DominatorsAnalysisProvider.h
* \brief Dominators Tree analysis
*/
#include "analysis/cfagraph.h"
#include "analysis/DominatorsAnalysisProvider.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;
CFAGraphAdapter* parent;
std::list<ScopeNode*> nodesFrom;
std::list<ScopeNode*> nodesTo;
CFAGraphAdapter* getParent(){ return parent; }
void printAsOperand(llvm::raw_ostream&, bool) {}
ScopeNode(ScopePacked scope, CFAGraphAdapter* parentAdapter):
id(scope), parent(parentAdapter) {}
};
}
} //end of namespace xreate::dominators
namespace llvm {
using namespace xreate::dominators;
template<>
struct GraphTraits<ScopeNode*> {
typedef ScopeNode* NodeRef;
typedef std::list<ScopeNode*>::iterator ChildIteratorType;
static ChildIteratorType
child_begin(ScopeNode* node) {
return node->nodesTo.begin();
}
static ChildIteratorType
child_end(ScopeNode* node) {
return node->nodesTo.end();
}
};
template<>
struct GraphTraits<Inverse<ScopeNode*>>
{
typedef ScopeNode* NodeRef;
typedef std::list<ScopeNode*>::iterator ChildIteratorType;
static ChildIteratorType
child_begin(ScopeNode* node) {
return node->nodesFrom.begin();
}
static ChildIteratorType
child_end(ScopeNode* node) {
return node->nodesFrom.end();
}
};
template<>
struct GraphTraits<CFAGraphAdapter*> {
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 ScopeNode*
getEntryNode(CFAGraphAdapter* F) {
return F->nodeRoot;
}
static unsigned int
size(CFAGraphAdapter* graph) {
return graph->nodes.size();
}
};
}
namespace xreate {
namespace dominators {
class DominatorTree : public llvm::DominatorTreeBase<ScopeNode, false> {
friend class DominatorsAnalysisProvider;
public:
DominatorTree() : llvm::DominatorTreeBase<ScopeNode, false>() {}
void
run(CFAGraphAdapter& program) {
recalculate(program);
updateDFSNumbers();
//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)
<<std::endl;
}
}
private:
DominatorsAnalysisProvider::Dominators dominators;
};
class PostDominatorTree : public llvm::DominatorTreeBase<ScopeNode, true> {
friend class DominatorsAnalysisProvider;
public:
PostDominatorTree() : llvm::DominatorTreeBase<ScopeNode, true>() {}
void
run(CFAGraphAdapter& program) {
recalculate(program);
updateDFSNumbers();
//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)
<<std::endl;
}
}
private:
DominatorsAnalysisProvider::Dominators dominators;
};
ScopeNode*
CFAGraphAdapter::registerScope(ScopePacked scope){
ScopeNode elemNew(scope, this);
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 > scope){
ScopeNode* elemNewP = new ScopeNode(elemNew);
*elemNewP = elemNew;
return *nodes.insert(posLowerBound, elemNewP);
}
return *posLowerBound;
}
CFAGraphAdapter*
CFAGraphAdapter::build(const cfa::CFAGraph* graph) {
return build(graph->__dependencyRelations);
}
CFAGraphAdapter*
CFAGraphAdapter::build(const std::multimap<ScopePacked, ScopePacked>& dataScopesOrder){
CFAGraphAdapter* tree=new CFAGraphAdapter();
enum NODE_MARK{NO_ROOT, POSSIBLE_ROOT};
std::unordered_map<unsigned int, NODE_MARK> nodeMarks;
for (const auto& edge: dataScopesOrder){
ScopeNode* nodeTo = tree->registerScope(edge.first);
ScopeNode* nodeFrom = tree->registerScope(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->registerScope(SCOPE_ABSTRACT_GLOBAL);
for(auto rootLocal: nodeRoots){
ScopeNode* nodeLocalRoot = tree->registerScope(rootLocal);
nodeLocalRoot->nodesFrom.push_back(nodeGlobalRoot);
nodeGlobalRoot->nodesTo.push_back(nodeLocalRoot);
}
tree->nodeRoot = nodeGlobalRoot;
} else if (nodeRoots.size()==1){
tree->nodeRoot = tree->registerScope(nodeRoots.front());
} else {
ScopeNode* nodeGlobalRoot = tree->registerScope(SCOPE_ABSTRACT_GLOBAL);
tree->nodeRoot = nodeGlobalRoot;
}
return tree;
}
void
DominatorsAnalysisProvider::run(CFAGraphAdapter* program) {
treeForwardDominators.reset(new DominatorTree());
treePostDominators.reset(new PostDominatorTree());
treeForwardDominators->run(*program);
treePostDominators->run(*program);
}
void
DominatorsAnalysisProvider::print(std::ostringstream& output) const {
treeForwardDominators->print(output, "cfa_forwdom");
treePostDominators->print(output, "cfa_postdom");
}
const DominatorsAnalysisProvider::Dominators&
DominatorsAnalysisProvider::getForwardDominators() const {
return treeForwardDominators->dominators;
}
const DominatorsAnalysisProvider::Dominators&
DominatorsAnalysisProvider::getPostDominators() const {
return treePostDominators->dominators;
}
DominatorsAnalysisProvider::DominatorsAnalysisProvider() {}
DominatorsAnalysisProvider::~DominatorsAnalysisProvider() { }
}} //end of namespace xreate::dominators
Event Timeline
Log In to Comment