51#include <boost/format.hpp>
52#include <boost/graph/breadth_first_search.hpp>
53#include <boost/graph/depth_first_search.hpp>
54#include <boost/graph/graph_utility.hpp>
55#include <boost/graph/properties.hpp>
56#include <boost/graph/reverse_graph.hpp>
57#include <boost/graph/strong_components.hpp>
99 startAddress_(
TTAProgram::NullAddress::instance()),
100 analyzed_(
false), entryNode_(NULL), componentsDetected_(
false) {
131 std::vector<Node*> cdNodes;
142 for (
unsigned int i = 0; i <
iDomTree_.size(); i++) {
143 Node* cNode = cdNodes[i];
149 DependenceMap::iterator rItr;
150 rItr = regionNodes.begin();
157 while (rItr != regionNodes.end()) {
160 "Node %s of procedure %s is missing dependencies. "
161 "Most likely CFG with unreachable BB. Can not create CDG!")
166 dependencies[cNode], (*rItr).second, (*rItr).first)){
171 if (found ==
true && dependencies[cNode]->size() == 1) {
175 *dependencies[cNode]->at(0).first, *cNode);
178 if (dependencies[cNode]->size() > 0) {
185 std::pair<Node*, DependentOn*>(newNode, dOn));
191 DependenceMap::iterator regionItr;
192 regionItr = regionNodes.begin();
193 while (regionItr != regionNodes.end()) {
196 for (
unsigned int i = 0; i < (*regionItr).second->size(); i++) {
198 *(*regionItr).second->at(i).first, *(*regionItr).first,
199 (*regionItr).second->at(i).second);
220 "Entry node of procedure %s has more then one child node."
221 "Invalid graph!") %
name()).str();
257 if (subSet->size() > wholeSet->size()) {
260 std::vector<SourceType> missing;
261 unsigned int numberOfFound = 0;
262 for (
unsigned int i = 0; i < wholeSet->size(); i++) {
265 for (
unsigned int j = 0; j < subSet->size(); j++) {
267 if (test.first == tmp.first && test.second == tmp.second) {
272 if (found ==
false) {
273 missing.push_back(test);
276 if (numberOfFound != subSet->size()) {
280 for (
unsigned int i = 0; i < missing.size(); i++) {
281 wholeSet->push_back(missing[i]);
304 std::vector<int>& iDom,
311 while (finger1 < finger2) {
312 finger1 = iDom[finger1];
314 while (finger2 < finger1) {
315 finger2 = iDom[finger2];
317 }
while (finger1 != finger2);
342 theEdge =
new Edge(edgeValue);
370 bool modified =
false;
372 std::vector<ControlFlowEdge*> addedEdges;
379 boost::time_stamper<PostOrder, int, boost::on_finish_vertex>
380 pOrderStamper(postOrder, tStamp);
384 boost::depth_first_visit(
386 boost::make_dfs_visitor(pOrderStamper), colors);
392 std::vector<BasicBlockNode*> postZero;
396 postZero.push_back(testedNode);
399 if (postZero.size() > 1) {
400 for (
unsigned int i = 0; i < postZero.size(); i++) {
408 addedEdges.push_back(
edge);
429 for (
unsigned int i = 0; i < nodes.size(); i++) {
462 "Missing postOrder number of predecessor!";
466 for (predIndex = predIndex + 1;
482 for (
unsigned int i = 0; i < addedEdges.size(); i++) {
506 "Graph %s has node %s with no input edges which is "
507 "not the entry node!\n") %
name()
515 "Corrupted graph. Found multiple entry nodes!");
517 result =
dynamic_cast<Node*
>(&
node(i));
521 if (found ==
false || result == NULL) {
523 "Graph %s does not have entry node or has mutliple nodes with"
524 " no input edges!") %
name()).str();
547 std::vector<Node*>& cdNodes,
551 std::map<BasicBlockNode*, Node*> BBCD;
558 if (nodeOutDegree == 2 && (!bbNode->
isEntryBB())) {
562 }
else if(nodeOutDegree > 2){
569 "Basic block %s has out degree of %d. Most likely "
570 "indirect jump. Can not create CDG for that atm.")
571 % bbNode->
toString() % nodeOutDegree).str();
574 cd =
new Node(typeOfNode, bbNode);
576 BBCD.insert(std::pair<BasicBlockNode*,Node*>(
579 if (nodeOutDegree < 2) {
582 }
else if(nodeOutDegree > 2){
589 "Basic block %s has out degree of %d. Most likely "
590 "indirect jump. Can not create CDG for that atm.")
591 % bbNode->
toString() % nodeOutDegree).str();
594 for (
int j = 0 ; j < nodeOutDegree; j++) {
617 BBCD, bbNode), edgeType);
619 while (nPoDom != runnerPo) {
622 Node* runnerCD = NULL;
625 BBCD, nodes[runnerPo]);
628 !nodes[runnerPo]->isEntryBB()) {
639 std::pair<BasicBlockNode*,Node*>(
640 nodes[runnerPo], runnerCD));
644 dependencies, runnerCD);
645 dep->push_back(newSource);
648 dep->push_back(newSource);
650 std::pair<Node*, DependentOn*>(
658 for (
unsigned int i = 0; i < nodes.size(); i++) {
662 cdNodes.push_back(cdNode);
695 std::vector<Node*> trueLinks;
696 std::vector<Node*> falseLinks;
699 for (
int j = 0; j < currDegree; j++) {
702 trueLinks.push_back(&
headNode(*currentOutEdge));
706 falseLinks.push_back(&
headNode(*currentOutEdge));
711 if (trueLinks.size() > 1) {
716 for (
unsigned int j = 0; j < trueLinks.size(); j++) {
722 if (falseLinks.size() > 1) {
727 for (
unsigned int j = 0; j < falseLinks.size(); j++) {
751 "\tStarting CDG serialization for %s with %d nodes and %d edges.\n")
757 auto timer = std::chrono::steady_clock::now();
763 long elapsed = std::chrono::duration_cast<std::chrono::seconds>(
764 std::chrono::steady_clock::now() - timer)
768 "\t\tStrong components: %d components, %d minutes and %d seconds.\n")
778 Color colorsDFS(colorMap);
781 boost::time_stamper<CDGOrder, int, boost::on_finish_vertex>
782 lastOrderStamper(lastOrder, fStamp);
783 timer = std::chrono::steady_clock::now();
785 boost::depth_first_visit(
787 boost::make_dfs_visitor(lastOrderStamper), colorsDFS);
788 elapsed = std::chrono::duration_cast<std::chrono::seconds>(
789 std::chrono::steady_clock::now() - timer)
793 "\t\tPost order: %d minutes and %d seconds.\n")
794 % (elapsed/60) % (elapsed%60)).str();
797 timer = std::chrono::steady_clock::now();
802 elapsed = std::chrono::duration_cast<std::chrono::seconds>(
803 std::chrono::steady_clock::now() - timer)
807 "\t\tRegion: %d minutes and %d seconds.\n")
808 % (elapsed/60) % (elapsed%60)).str();
811 timer = std::chrono::steady_clock::now();
816 elapsed = std::chrono::duration_cast<std::chrono::seconds>(
817 std::chrono::steady_clock::now() - timer)
821 "\t\tEEC: %d minutes and %d seconds.\n")
822 % (elapsed/60) % (elapsed%60)).str();
825 timer = std::chrono::steady_clock::now();
830 elapsed = std::chrono::duration_cast<std::chrono::seconds>(
831 std::chrono::steady_clock::now() - timer)
835 "\t\tRelations: %d minutes and %d seconds.\n")
836 % (elapsed/60) % (elapsed%60)).str();
864 std::vector<std::pair<Node*, Node*> > backEdges;
866 int currentComponents = 0;
870 CDGOrder componentOrder(components);
872 currentComponents = 0;
874 currentComponents = boost::strong_components(
875 graph_, componentOrder, boost::root_map(componentRoots));
878 std::vector<std::set<Node*> > componentVector;
891 for (CDGOrderMap::iterator iterA = components.begin();
892 iterA != components.end(); iterA ++) {
894 componentVector[(*iterA).second].insert(cNode);
897 for (
unsigned int i =
componentCount; i < componentVector.size(); i++) {
898 if (componentVector[i].size() > 1) {
899 std::set<Node*>& vector = componentVector[i];
902 for (std::set<Node*>::iterator iterB = vector.begin();
903 iterB != vector.end();
907 if ((*iterB)->component() == -1){
918 std::vector<std::pair<Node*,int> > newEntry;
921 std::map<Node*, std::vector<Node*> > incomingToEntry;
926 for (std::set<Node*>::iterator iterD = nodes.begin();
927 iterD != nodes.end();
930 for (EdgeSet::iterator ei = edges.begin();
934 if (nodes.find(testedNode) == nodes.end()) {
935 if (!(*iterD)->isLoopEntryNode(i)) {
937 (*iterD)->setLoopEntryNode(i);
939 std::pair<Node*,int>(*iterD,i));
940 incomingToEntry[*iterD].push_back(testedNode);
945 incomingToEntry[*iterD].push_back(testedNode);
954 for (
unsigned int j = 0; j < newEntry.size(); j++) {
955 Node* loopNode = newEntry[j].first;
956 std::set<Node*>& nodes =
968 std::vector<Edge*> storeEdges;
969 for (EdgeSet::iterator ei = edges.begin();
973 if (nodes.find(sourceNode) != nodes.end()){
974 storeEdges.push_back(*ei);
978 for (
unsigned int counter = 0;
979 counter < storeEdges.size();
981 moveInEdge(*loopNode, *close, *storeEdges[counter]);
985 std::pair<Node*, Node*>(close, loopNode));
990 "Close node for loop entry node %s was not connected!\n")
997 std::vector<Node*> tmp =
999 incomingToEntry, loopNode);
1000 if (tmp.size() > 1) {
1003 for (
unsigned int i = 0; i < tmp.size(); i++) {
1004 Node* input = tmp[i];
1019 for (
unsigned int i = 0; i < backEdges.size(); i++) {
1042 int mapSize = orderMap.size();
1045 "No nodes in CDG graph for " +
name() +
"!");
1048 for (
int i = mapSize -1 ; i >= 0 ; i--) {
1052 if (!
node->isLoopEntryNode()) {
1058 for (Node::NodesInfo::iterator k = finalNodesInfo.begin();
1059 k != finalNodesInfo.end(); k++) {
1060 node->addToRegion(**k);
1062 }
else if (
node->region().size() == 0) {
1068 std::vector<Node*> entries;
1070 for (std::set<Node*>::iterator si = component.begin();
1071 si != component.end(); si++) {
1075 if ((*si)->isLoopEntryNode(
node->component())) {
1076 entries.push_back(*si);
1080 for (
unsigned int i = 0; i < entries.size(); i++) {
1084 for (
unsigned j = 0; j < entries.size(); j++) {
1085 Node* result = entries[j];
1086 for (Node::NodesInfo::iterator k = finalNodesInfo.begin();
1087 k != finalNodesInfo.end(); k++) {
1109 int mapSize = orderMap.size();
1110 for (
int i = 0; i < mapSize; i++) {
1116 if (
node->eec().size() > 0) {
1121 if (
node->isLoopCloseNode() &&
node->eec().size() == 0) {
1122 std::vector<Node*> closeNodes;
1125 for (std::set<Node*>::iterator si = component.begin();
1126 si != component.end(); si++) {
1127 if ((*si)->isLoopCloseNode()) {
1128 closeNodes.push_back(*si);
1129 }
else if ((*si)->isRegionNode()
1130 || (*si)->isPredicateNode()) {
1131 (*si)->setLastNode();
1136 finalInfo.insert(
node->region().begin(),
node->region().end());
1137 for (
unsigned int i = 0; i < closeNodes.size(); i++) {
1139 finalInfo, closeNodes[i]->region(), storeResult);
1140 finalInfo.swap(storeResult);
1141 storeResult.clear();
1144 for (
unsigned j = 0; j < closeNodes.size(); j++) {
1145 Node* result = closeNodes[j];
1146 if(result->
eec().size() != 0) {
1148 "Close node %s in %s already has eec!\n")
1152 for (Node::NodesInfo::iterator k = finalInfo.begin();
1153 k != finalInfo.end(); k++) {
1162 for (Node::NodesInfo::iterator t = regionX.begin();
1163 t != regionX.end(); t++) {
1164 node->addToEEC( **t);
1168 if (
node->isPredicateNode()) {
1173 for (Node::NodesInfo::iterator t = regionX.begin();
1174 t != regionX.end(); t++) {
1175 node->addToPseudoPredicateEEC( **t);
1186 for (NodeSet::iterator su = succ.begin();
1187 su != succ.end(); su++) {
1188 childNodes.insert(*su);
1194 (*(childNodes.begin()))->eec().begin(),
1195 (*(childNodes.begin()))->eec().end());
1197 for(Node::NodesInfo::iterator j = childNodes.begin();
1198 j != childNodes.end(); j++ ) {
1201 finalEEC.swap(storeResult);
1202 storeResult.clear();
1204 std::vector<Node*> result(finalEEC.size(), NULL);
1207 std::vector<Node*>::iterator resultEnd =
1208 std::set_difference(finalEEC.begin(), finalEEC.end(),
1209 childNodes.begin(), childNodes.end(), result.begin());
1211 for (std::vector<Node*>::iterator t = result.begin();
1212 t != resultEnd; t++) {
1213 node->addToEEC(**t);
1257 && AinA ==
true && BinB ==
true) {
1273 && AinA ==
false && BinB ==
true) {
1278 && AinA ==
false && BinB ==
false) {
1342 std::vector<Node::NodesInfo> tmpResult;
1345 for (EdgeSet::iterator ei = edges.begin();
1352 if (previous->
region().size() == 0 &&
1358 for (Node::NodesInfo::iterator k = addedNodesInfo.begin();
1359 k != addedNodesInfo.end();
1367 for (EdgeSet::iterator ei = outgoingEdges.begin();
1368 ei != outgoingEdges.end();
1371 tmp.insert(testedNode);
1373 tmpResult.push_back(tmp);
1377 tmpResult.push_back(tmp);
1381 "Node: %s , parent %s.")
1388 if (tmpResult.size() > 0) {
1389 finalNodesInfo.insert(
1390 tmpResult[0].begin(), tmpResult[0].end());
1395 for (
unsigned int l = 1; l < tmpResult.size(); l++) {
1398 finalNodesInfo, tmpResult[l], storeResult);
1399 finalNodesInfo.swap(storeResult);
1400 storeResult.clear();
1414 int mapSize = orderMap.size();
1415 for (
int i = 0; i < mapSize; i++) {
1420 if (
node->isRegionNode()
1421 ||
node->isLoopEntryNode()
1422 ||
node->isPredicateNode()) {
1443 std::vector<std::pair<Node*, Node*> > newEdges;
1444 for (EdgeSet::iterator ei1 = edges.begin();
1451 EdgeSet::iterator ei2 = ei1;
1453 for (; ei2 != edges.end(); ++ei2) {
1458 if (result ==
ERROR) {
1463 newEdges.push_back(std::pair<Node*, Node*>(node1, node2));
1466 newEdges.push_back(std::pair<Node*, Node*>(node2, node1));
1471 "Nodes %s and %s can not be put into any order.\n")
1479 __FILE__, __LINE__,
__func__, (boost::format(
1480 "Ordering error for A='%s' and B='%s'.")
1491 for (
unsigned int i = 0; i < newEdges.size(); i++) {
1493 connectNodes(*newEdges[i].first, *newEdges[i].second, *direction);
#define IGNORE_COMPILER_WARNING(X)
#define POP_COMPILER_DIAGS
#define IGNORE_CLANG_WARNING(X)
find Finds info of the inner loops in the false
static int verboseLevel()
static std::ostream & logStream()
std::string toString() const
virtual void removeEdge(Edge &e)
virtual void disconnectNodes(const Node &nTail, const Node &nHead)
EdgeDescriptor descriptor(const Edge &e) const
GraphTraits::vertex_descriptor NodeDescriptor
Type with which nodes of the graph are seen internally.
virtual void moveOutEdges(const Node &source, const Node &destination)
virtual Node & headNode(const Edge &edge) const
std::set< ControlDependenceEdge *, typename GraphEdge::Comparator > EdgeSet
virtual Edge & outEdge(const Node &node, const int index) const
virtual void removeNode(Node &node)
virtual bool hasEdge(const Node &nTail, const Node &nHead) const
virtual void addNode(Node &node)
virtual NodeSet successors(const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
Node & node(const int index) const
EdgeDescriptor connectingEdge(const Node &nTail, const Node &nHead) const
virtual const TCEString & name() const
GraphTraits::edge_descriptor EdgeDescriptor
Type with which edges of the graph are seen internally.
virtual int inDegree(const Node &node) const
std::set< ControlDependenceNode *, typename GraphNode::Comparator > NodeSet
virtual void moveInEdge(const Node &source, const Node &destination, Edge &edge, const Node *tail=NULL, bool childs=false)
virtual int outDegree(const Node &node) const
ControlDependenceNode Node
The (base) node type managed by this graph.
virtual EdgeSet outEdges(const Node &node) const
virtual Node & tailNode(const Edge &edge) const
virtual Edge & edge(const int index) const
ControlDependenceEdge Edge
The (base) edge type managed by this graph.
Graph graph_
The internal graph structure.
virtual EdgeSet inEdges(const Node &node) const
virtual void connectNodes(const Node &nTail, const Node &nHead, Edge &e)
std::map< NodeDescriptor, boost::default_color_type > ColorMap
Storage for color property used by dfs.
std::vector< SourceType > DependentOn
ControlDependenceEdge & createControlDependenceEdge(Node &bTail, Node &bHead, Edge::CDGEdgeType edgeValue=Edge::CDEP_EDGE_NORMAL)
int nearestCommonDom(std::vector< int > &iDom, int node1, int node2) const
void computeRegionInfo(const CDGOrderMap &orderMap)
ControlDependenceGraph(const ControlFlowGraph &cGraph)
int componentCount() const
void detectControlDependencies(BlockVector &nodes, std::vector< Node * > &cdNodes, PostOrder &postOrder, DependenceMap &dependencies)
boost::associative_property_map< PostOrderMap > PostOrder
TTAProgram::Program * program_
std::vector< std::set< Node * > > strongComponents_
boost::associative_property_map< DescriptorMap > Descriptors
std::map< NodeDescriptor, int > CDGOrderMap
Stores data to compute post order relation on CDG and strong components.
void computeEECInfo(const CDGOrderMap &orderMap)
virtual ~ControlDependenceGraph()
ControlFlowGraph * cGraph_
std::map< NodeDescriptor, NodeDescriptor > DescriptorMap
Storage for relations between nodes.
void eliminateMultipleOutputs()
void regionHelper(Node *, Node::NodesInfo &)
std::vector< int > iDomTree_
boost::associative_property_map< CDGOrderMap > CDGOrder
void createPostDominanceTree(BlockVector &nodes, PostOrder &postOrder)
boost::associative_property_map< ColorMap > Color
void computeRelations(const CDGOrderMap &orderMap)
CompareResult compareSiblings(Node *a, Node *b) const
TTAProgram::Program * program() const
std::pair< Node *, Edge::CDGEdgeType > SourceType
std::vector< BasicBlockNode * > BlockVector
Node * entryNode_
Stores reference to entryNode of the graph.
std::map< ControlFlowGraph::NodeDescriptor, int > PostOrderMap
Stores data to compute post order relation on CFG.
int detectStrongComponents(CDGOrderMap &components, DescriptorMap &roots)
bool findSubset(DependentOn *, DependentOn *, Node *)
std::map< Node *, DependentOn *, Node::Comparator > DependenceMap
void processRegion(Node *region)
ControlDependenceNode & entryNode()
bool analyzed_
Indicates that CDG already has data required for serialization.
void addToRegion(ControlDependenceNode &node)
const NodesInfo & region()
bool isLoopEntryNode() const
std::string toString() const
bool isPredicateNode() const
void setComponent(int component)
bool isRegionNode() const
std::set< ControlDependenceNode * > NodesInfo
Storage type for other nodes of same graph needed to define some non graph relations....
void addToEEC(ControlDependenceNode &node)
bool isLoopCloseNode() const
ReversedGraph & reversedGraph() const
reverse_graph< ControlFlowGraph::Graph > ReversedGraph
BasicBlockNode & exitNode() const
void removeEntryExitEdge()
TTAProgram::Program * program() const
std::string errorMessageStack(bool messagesOnly=false) const
virtual std::string toString() const