OpenASIP 2.2
Loading...
Searching...
No Matches
ControlDependenceGraph.cc
Go to the documentation of this file.
1/*
2 Copyright (c) 2002-2009 Tampere University.
3
4 This file is part of TTA-Based Codesign Environment (TCE).
5
6 Permission is hereby granted, free of charge, to any person obtaining a
7 copy of this software and associated documentation files (the "Software"),
8 to deal in the Software without restriction, including without limitation
9 the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 and/or sell copies of the Software, and to permit persons to whom the
11 Software is furnished to do so, subject to the following conditions:
12
13 The above copyright notice and this permission notice shall be included in
14 all copies or substantial portions of the Software.
15
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22 DEALINGS IN THE SOFTWARE.
23 */
24/**
25 * @file ControlDependenceGraph.cc
26 *
27 * Implementation of prototype control dependence graph of TTA program
28 * representation.
29 *
30 * @author Andrea Cilio 2005 (cilio-no.spam-cs.tut.fi)
31 * @author Vladimir Guzma 2006 (vladimir.guzma-no.spam-tut.fi)
32 * @note rating: red
33 */
34
35#include <algorithm>
36#include <chrono>
37#include <functional>
38#include <iostream>
39#include <list>
40#include <map>
41#include <vector>
42
43// these need to be included before Boost so we include a working
44// and warning-free hash_map
45#include "hash_set.hh"
46#include "hash_map.hh"
47
48#include "CompilerWarnings.hh"
49IGNORE_CLANG_WARNING("-Wunused-local-typedef")
50IGNORE_COMPILER_WARNING("-Wunused-parameter")
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>
60
62#include "ControlFlowGraph.hh"
63#include "BasicBlockNode.hh"
64#include "ControlFlowEdge.hh"
65#include "BaseType.hh"
66#include "MapTools.hh"
67#include "Conversion.hh"
68#include "SetTools.hh"
69#include "AssocTools.hh"
70#include "SequenceTools.hh"
71#include "Instruction.hh"
72#include "Move.hh"
74#include "Immediate.hh"
75
76#define DEBUG_LEVEL 0
77//#define DEBUG_ANNOTATOR
78
80 // removeNode() also removes edges and deletes them
81 while (nodeCount() > 0) {
83 removeNode(*n);
84 delete n;
85 }
86 for (unsigned int i = 0; i < strongComponents_.size(); i++) {
87 strongComponents_[i].clear();
88 }
89 strongComponents_.clear();
90}
91/**
92 * Reads ControlFlowGraph of procedure and creates ControlDependenceGraph
93 * @param cGraph Control Flow Graph
94 */
95
97 const ControlFlowGraph& cGraph) :
98 BoostGraph<Node, Edge>(cGraph.name()) ,
99 startAddress_(TTAProgram::NullAddress::instance()),
100 analyzed_(false), entryNode_(NULL), componentsDetected_(false) {
101
102 program_ = cGraph.program();
103 alignment_ = cGraph.alignment();
104 cGraph_ = &const_cast<ControlFlowGraph&>(cGraph);
106}
107/**
108 * Compute control flow post-dominance information (in the form of an
109 * immediate post-dominator tree).
110 * Compute the control dependencies of the control flow graph using the
111 * pre-computed tree of immediate post-dominators.
112 *
113 * The base algorithm implemented is described in
114 * K.D. Cooper, T.J. Harvey, K. Kennedy: "A Simple, Fast Dominance Algorithm"
115 * and Ferrante, Ottenstein, Warren: "The Program Dependence Graphs and Its
116 * Use in Optimisation"
117 *
118 * @throw Throws InvalidData exception in case CFG can not be analyzed
119 */
120void
122
123 BlockVector nodes;
124 PostOrderMap poMap;
125 PostOrder postOrder(poMap);
126
127 createPostDominanceTree(nodes, postOrder);
128 // For each edge we have to record what is predicate it is controlled
129 // by...
130 DependenceMap dependencies;
131 std::vector<Node*> cdNodes;
132 detectControlDependencies(nodes, cdNodes, postOrder, dependencies);
133
134 // edge added while creating CD dependencies, not part of CFG by
135 // itself so it should be removed now that we have dominance tree
137 // set of control dependencies for given region node
138 DependenceMap regionNodes;
139
140 // Creates region node for each set of control dependencies
141 // and adds the record to regionNodes
142 for (unsigned int i = 0; i < iDomTree_.size(); i++) {
143 Node* cNode = cdNodes[i];
144 if (cNode->isEntryNode() || cNode->isExitNode()) {
145 // Exit postdominate every node including Entry so
146 // they do not have any dependencies
147 continue;
148 }
149 DependenceMap::iterator rItr;
150 rItr = regionNodes.begin();
151 bool found = false;
152 // Find if previously created region node have subset of dependencies
153 // of currently tested node. If so, replace subset with dependence
154 // on previously created region node
155 // TODO: The tested set of created nodes should be sorted from
156 // largest to smallest
157 while (rItr != regionNodes.end()) {
158 if (!MapTools::containsKey(dependencies, cNode)) {
159 TCEString msg = (boost::format(
160 "Node %s of procedure %s is missing dependencies. "
161 "Most likely CFG with unreachable BB. Can not create CDG!")
162 % cNode->toString() % name()).str();
163 throw InvalidData(__FILE__, __LINE__, __func__, msg);
164 }
165 if (findSubset(
166 dependencies[cNode], (*rItr).second, (*rItr).first)){
167 found = true;
168 }
169 rItr ++;
170 }
171 if (found == true && dependencies[cNode]->size() == 1) {
172 // only one dependence and is identical
173 // with already existing one, just create edge to existing region
175 *dependencies[cNode]->at(0).first, *cNode);
176 continue;
177 }
178 if (dependencies[cNode]->size() > 0) {
179 // Create new region node and add edge from it to tested node
180 // record set of dependences for future reuse
181 Node* newNode = new Node(Node::CDEP_NODE_REGION);
182 addNode(*newNode);
183 DependentOn* dOn = new DependentOn(*(dependencies[cNode]));
184 regionNodes.insert(
185 std::pair<Node*, DependentOn*>(newNode, dOn));
186 createControlDependenceEdge(*newNode, *cNode);
187 }
188 }
189
190 // create dependent edges INTO region nodes
191 DependenceMap::iterator regionItr;
192 regionItr = regionNodes.begin();
193 while (regionItr != regionNodes.end()) {
194 // For each region node, add edge from all nodes it is depending on
195 // into the region node
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);
200 }
201 regionItr++;
202 }
203
205 /// Removes artificial Exit node, it is not dependent on anything
206 /// Move edges from Entry's child region to Entry and delete region
207 for (int i = 0; i < nodeCount(); i++) {
208 Node& testNode = node(i);
209 if (testNode.isExitNode()) {
210 if (outDegree(testNode) == 0 && inDegree(testNode) == 0) {
211 removeNode(testNode);
212 delete &testNode;
213 continue;
214 }
215 }
216
217 if (testNode.isEntryNode()) {
218 if (outDegree(testNode) != 1) {
219 TCEString msg = (boost::format(
220 "Entry node of procedure %s has more then one child node."
221 "Invalid graph!") % name()).str();
222 throw ModuleRunTimeError(__FILE__, __LINE__, __func__, msg);
223 }
224 Edge& edge = outEdge(testNode, 0);
225 Node& entryChild = headNode(edge);
226 moveOutEdges(entryChild, testNode);
227 removeNode(entryChild);
228 delete &entryChild;
229 }
230 }
231 MapTools::deleteAllValues(regionNodes);
232 MapTools::deleteAllKeys(regionNodes);
233 MapTools::deleteAllValues(dependencies);
234 MapTools::deleteAllKeys(dependencies);
235 cdNodes.clear();
236 nodes.clear();
237}
238
239/**
240 * Internal helper. Find already existing region node in set of dependencies.
241 *
242 * Find if set of dependencies contains a subset that has already a region
243 * node. If so, modifies dependencies to contain dependence to existing
244 * region node.
245 *
246 * @param wholeSet Set of dependencies for node we want to test
247 * @param subSet Set corresponding to some already existing region node
248 * @param regNode Region node we are testing
249 * @return True if the intersection was found
250 */
251bool
253 DependentOn* wholeSet,
254 DependentOn* subSet,
255 Node* regNode) {
256
257 if (subSet->size() > wholeSet->size()) {
258 return false;
259 }
260 std::vector<SourceType> missing;
261 unsigned int numberOfFound = 0;
262 for (unsigned int i = 0; i < wholeSet->size(); i++) {
263 SourceType test = wholeSet->at(i);
264 bool found = false;
265 for (unsigned int j = 0; j < subSet->size(); j++) {
266 SourceType tmp = subSet->at(j);
267 if (test.first == tmp.first && test.second == tmp.second) {
268 found = true;
269 numberOfFound++;
270 }
271 }
272 if (found == false) {
273 missing.push_back(test);
274 }
275 }
276 if (numberOfFound != subSet->size()) {
277 return false;
278 }
279 wholeSet->clear();
280 for (unsigned int i = 0; i < missing.size(); i++) {
281 wholeSet->push_back(missing[i]);
282 }
283 wholeSet->push_back(
285 missing.clear();
286 return true;
287}
288
289/**
290 * Internal hepler. Compute the nearest common dominator of two nodes.
291 *
292 * Given two nodes (identified by their traversal order), find the nearest
293 * common ancestor that dominates both.
294 *
295 * Note: this method should go in separate immediate dominator class.
296 *
297 * @param iDom Tree of immediate dominators.
298 * @param node1 A graph node.
299 * @param node2 Another graph node.
300 * @return The post-order number of the nearest dominator of given nodes.
301 */
302int
304 std::vector<int>& iDom,
305 int node1,
306 int node2) const {
307
308 int finger1 = node1;
309 int finger2 = node2;
310 do {
311 while (finger1 < finger2) {
312 finger1 = iDom[finger1];
313 }
314 while (finger2 < finger1) {
315 finger2 = iDom[finger2];
316 }
317 } while (finger1 != finger2);
318 return finger1;
319}
320
321/**
322 * Create a control dependence edge between two basic blocks.
323 *
324 * Creates new Control Dependence edge between two basic blocks passed as
325 * parameters
326 * @param bTail The tail basic block.
327 * @param bHead The head basic block.
328 * @return The created control dependence edge.
329 */
332 Node& bTail,
333 Node& bHead,
334 Edge::CDGEdgeType edgeValue) {
335
336 Edge* theEdge = 0;
337 try {
338 // By construction, there should not! be duplication of CD edges!!!
339 if (hasEdge(bTail, bHead)) {
340 theEdge = graph_[connectingEdge(bTail, bHead)];
341 } else {
342 theEdge = new Edge(edgeValue);
343 connectNodes(bTail, bHead, *theEdge);
344 }
345 } catch (const ObjectAlreadyExists& e) {
347 __FILE__, __LINE__, __func__, e.errorMessageStack());
348 }
349 return *theEdge;
350}
351
352/**
353 * Internal helper. Creates a tree of immediate post dominators for
354 * constructing a control dependencies
355 *
356 * @param nodes Will be filled with pointers to BasicBlocks indexed
357 * by post order number
358 * @param postOrder Will be filled by post order numbers
359 */
360void
362 BlockVector& nodes,
363 PostOrder& postOrder) {
364
365 // Add false edge from entry to exit
367 ControlFlowGraph::ReversedGraph* revGraph_ = NULL;
368 revGraph_ = &cGraph_->reversedGraph();
369
370 bool modified = false;
371 int counter = 0; // NOLINT Disable claim this is unused
372 std::vector<ControlFlowEdge*> addedEdges;
373 BasicBlockNode& cfgExitNode = cGraph_->exitNode();
374 do {
375 ColorMap cMap;
376 Color colors(cMap);
377 modified = false;
378 int tStamp(-1);
379 boost::time_stamper<PostOrder, int, boost::on_finish_vertex>
380 pOrderStamper(postOrder, tStamp);
381 // the order of nodes within the reversed graph remains unchanged,
382 // have to look for the sink node (of the original graph) when we
383 // want to get the start node of the reverse graph.
384 boost::depth_first_visit(
385 *revGraph_, cGraph_->descriptor(cfgExitNode),
386 boost::make_dfs_visitor(pOrderStamper), colors);
387 // there can be just one node with post order number 0
388 // if there are several, then some of them are not post
389 // dominated by Exit - endless loop without break or return
390 // we add and edge from one of those nodes to exit and redo
391 // the dfs visit.
392 std::vector<BasicBlockNode*> postZero;
393 for (int i = cGraph_->nodeCount() - 1; i >=0; i--) {
394 BasicBlockNode* testedNode = &cGraph_->node(i);
395 if (postOrder[cGraph_->descriptor(*testedNode)] == 0) {
396 postZero.push_back(testedNode);
397 }
398 }
399 if (postZero.size() > 1) {
400 for (unsigned int i = 0; i < postZero.size(); i++) {
401 BasicBlockNode* testedNode = postZero[i];
402 if (!testedNode->isEntryBB()) {
403 ControlFlowEdge* edge = new
407 *testedNode, cGraph_->exitNode(), *edge);
408 addedEdges.push_back(edge);
409 delete revGraph_;
410 revGraph_ = &cGraph_->reversedGraph();
411 modified = true;
412 break;
413 }
414 }
415 }
416 postZero.clear();
417 counter++;
418 } while (modified);
419 delete revGraph_;
420 revGraph_ = NULL;
421
422 // tree of immediate dominators, mapping a node to its immediate
423 // dominator; each node is represented by its inverted post-order number
424 iDomTree_.resize(cGraph_->nodeCount());
425 const int startNodePO = cGraph_->nodeCount() - 1;
426 // create inverse map from post-order to node
427 // initialise tree of immediate dominators
428 nodes.resize(cGraph_->nodeCount());
429 for (unsigned int i = 0; i < nodes.size(); i++) {
430 nodes[postOrder[cGraph_->descriptor(cGraph_->node(i))]] =
431 &(cGraph_->node(i));
432 iDomTree_[i] = -1;
433 }
434
435 iDomTree_[startNodePO] = startNodePO;
436 bool changed = true;
437 while (changed) {
438 changed = false;
439 // traverse graph in reverse post-order, skipping start node
440 for (int i = cGraph_->nodeCount() - 2; i >= 0; i--) {
441 BasicBlockNode& b(*nodes[i]);
442 int newDom;
443 int predIndex;
444 for (predIndex = 0; predIndex < cGraph_->outDegree(b);
445 predIndex++) {
446 BasicBlockNode& predecessor(cGraph_->headNode(
447 cGraph_->outEdge(b, predIndex)));
448 int predPO = postOrder[cGraph_->descriptor(predecessor)];
449 // Find first processed predecessor of b
450 if (iDomTree_[predPO] != -1) {
451 break;
452 }
453 }
454 // outgoing edges of original graph are in-edges of reverse graph
455 BasicBlockNode& predecessor(cGraph_->headNode(
456 cGraph_->outEdge(b, predIndex)));
457 newDom = postOrder[cGraph_->descriptor(predecessor)];
458 // because nodes are searched in inverse post-order, at least
459 // one of predecessors of current node must have been processed
460 if (newDom == -1) {
461 TCEString message =
462 "Missing postOrder number of predecessor!";
463 throw ModuleRunTimeError(__FILE__, __LINE__, __func__, message);
464 }
465
466 for (predIndex = predIndex + 1;
467 predIndex < cGraph_->outDegree(b);
468 predIndex++) {
469 BasicBlockNode& predecessor(cGraph_->headNode(
470 cGraph_->outEdge(b, predIndex)));
471 int predPO = postOrder[cGraph_->descriptor(predecessor)];
472 if (iDomTree_[predPO] != -1) {
473 newDom = nearestCommonDom(iDomTree_, newDom, predPO);
474 }
475 }
476 if (newDom != iDomTree_[i]) {
477 changed = true;
478 iDomTree_[i] = newDom;
479 }
480 }
481 }
482 for (unsigned int i = 0; i < addedEdges.size(); i++) {
483 cGraph_->removeEdge(*addedEdges[i]);
484 }
485}
486
487/**
488 * Return the entry node of the graph. Cache it after it's found for alter use
489 *
490 * @return The entry node of the graph.
491 * @exception InstanceNotFound if the graph does not have a entry node.
492 * @exception ModuleRunTimeError if the graph has multiple nodes that are
493 * recognised as entry nodes.
494 */
497 if (entryNode_ == NULL) {
498 Node* result = NULL;
499 bool found = false;
500 for (int i = 0; i < nodeCount(); i++) {
501 if (inDegree(node(i)) == 0) {
502 // sanity check
503 if (!static_cast<Node&>(node(i)).isEntryNode()) {
504 // probably the entry node is not present
505 TCEString errorMsg = (boost::format(
506 "Graph %s has node %s with no input edges which is "
507 "not the entry node!\n") % name()
508 % node(i).toString()).str();
509 throw ModuleRunTimeError(__FILE__, __LINE__, __func__,
510 errorMsg);
511 }
512 if (found == true) {
513 throw ModuleRunTimeError(
514 __FILE__, __LINE__, __func__,
515 "Corrupted graph. Found multiple entry nodes!");
516 }
517 result = dynamic_cast<Node*>(&node(i));
518 found = true;
519 }
520 }
521 if (found == false || result == NULL) {
522 TCEString errorMsg = (boost::format(
523 "Graph %s does not have entry node or has mutliple nodes with"
524 " no input edges!") % name()).str();
525 throw ModuleRunTimeError(__FILE__, __LINE__, __func__, errorMsg);
526 }
527 entryNode_ = result;
528 return *result;
529 } else {
530 return *entryNode_;
531 }
532}
533
534/**
535 * Internal helper. Implemented detection of control dependencies.
536 *
537 * @param nodes Vector of basic block nodes indexed by reverse post order
538 * number
539 * @param cdNodes Vector of control dependence nodes indexed by reverse post
540 * order number
541 * @param postOrder Post order numbering of nodes
542 * @param dependencies For each node, the list of nodes it is dependent on
543 */
544void
546 BlockVector& nodes,
547 std::vector<Node*>& cdNodes,
548 PostOrder& postOrder,
549 DependenceMap& dependencies) {
550
551 std::map<BasicBlockNode*, Node*> BBCD;
552 for (int i = 0; i < cGraph_->nodeCount(); i++) {
553 BasicBlockNode* bbNode = &cGraph_->node(i);
554 int nodeOutDegree = cGraph_->outDegree(*bbNode);
555 if (!MapTools::containsKey(BBCD, bbNode)) {
556 Node* cd = NULL;
558 if (nodeOutDegree == 2 && (!bbNode->isEntryBB())) {
559 // 2 out edges in CFG means BB ends with conditional jump
560 // therefore it is predicate BB
561 typeOfNode = Node::CDEP_NODE_PREDICATE;
562 } else if(nodeOutDegree > 2){
563 /// Basic block is either 3way jump - forbidden
564 /// or it is indirect jump with edges to all data-code
565 /// rellocations. We can not deal with such situation
566 /// at the moment. Fix cfg to original form and throw exception
568 TCEString msg = (boost::format(
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();
572 throw InvalidData(__FILE__, __LINE__, __func__, msg);
573 }
574 cd = new Node(typeOfNode, bbNode);
575 addNode(*cd);
576 BBCD.insert(std::pair<BasicBlockNode*,Node*>(
577 bbNode, cd));
578 }
579 if (nodeOutDegree < 2) {
580 /// node is not predicate
581 continue;
582 } else if(nodeOutDegree > 2){
583 /// Basic block is either 3way jump - forbidden
584 /// or it is indirect jump with edges to all data-code
585 /// rellocations. We can not deal with such situation
586 /// at the moment. Fix cfg to original form and throw exception
588 TCEString msg = (boost::format(
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();
592 throw InvalidData(__FILE__, __LINE__, __func__, msg);
593 }
594 for (int j = 0 ; j < nodeOutDegree; j++) {
595 Edge::CDGEdgeType edgeType =
598 cGraph_->outEdge(*bbNode, j)));
599
600 int nPO = postOrder[cGraph_->descriptor(*bbNode)];
601 int tPO = postOrder[cGraph_->descriptor(*t)];
602 int nPoDom = iDomTree_[nPO];
603 if (nPoDom == tPO) {
604 // t is target of n, so if it post-dominate n
605 // it is immediate post dominator!
606 continue;
607 }
608 int runnerPo = tPO;
609 if (cGraph_->outEdge(*bbNode, j).isTrueEdge()) {
610 edgeType = Edge::CDEP_EDGE_TRUE;
611 }
612 if (cGraph_->outEdge(*bbNode, j).isFalseEdge()) {
613 edgeType = Edge::CDEP_EDGE_FALSE;
614 }
615 SourceType newSource = SourceType(
617 BBCD, bbNode), edgeType);
618
619 while (nPoDom != runnerPo) {
620 // Walk through postDominator tree
621 // Store found CD in multimap
622 Node* runnerCD = NULL;
623 if (MapTools::containsKey(BBCD, nodes[runnerPo])) {
625 BBCD, nodes[runnerPo]);
626 } else {
627 if (cGraph_->outDegree(*nodes[runnerPo]) == 2 &&
628 !nodes[runnerPo]->isEntryBB()) {
629 // 2 out edges in CFG means BB ends with conditional
630 //jump therefore it is predicate BB
631 runnerCD = new Node(
632 Node::CDEP_NODE_PREDICATE, nodes[runnerPo]);
633 } else {
634 runnerCD = new Node(
635 Node::CDEP_NODE_BB, nodes[runnerPo]);
636 }
637 addNode(*runnerCD);
638 BBCD.insert(
639 std::pair<BasicBlockNode*,Node*>(
640 nodes[runnerPo], runnerCD));
641 }
642 if (MapTools::containsKey(dependencies, runnerCD)) {
644 dependencies, runnerCD);
645 dep->push_back(newSource);
646 } else {
647 DependentOn* dep = new DependentOn;
648 dep->push_back(newSource);
649 dependencies.insert(
650 std::pair<Node*, DependentOn*>(
651 runnerCD, dep));
652 }
653 runnerPo = iDomTree_[runnerPo];
654 }
655 }
656
657 }
658 for (unsigned int i = 0; i < nodes.size(); i++) {
659 Node* cdNode;
661 BBCD, nodes[i]);
662 cdNodes.push_back(cdNode);
663 }
664 BBCD.clear();
665}
666
667/**
668 * Returns an alignment of procedure in original POM
669 * @return Alignment take from original POM
670 */
671int
675
676/**
677 * Returns the pointer to Program object of POM procedure
678 * belongs to.
679 * @return Pointer to TTAProgram::Program
680 */
683 return program_;
684}
685
686/**
687 * Internal helper. Replaces several output edges with same truth value with
688 * region node. Combines several output edges without truth value (indirect
689 * jumps for example);
690 */
691void
693 for (int i = 0; i < nodeCount(); i++) {
694 if (outDegree(node(i)) > 1 && node(i).isBBNode()) {
695 std::vector<Node*> trueLinks;
696 std::vector<Node*> falseLinks;
697 Node& currNode = node(i);
698 int currDegree = outDegree(currNode);
699 for (int j = 0; j < currDegree; j++) {
700 Edge* currentOutEdge = &outEdge(currNode, j);
701 if (currentOutEdge->isTrueEdge()) {
702 trueLinks.push_back(&headNode(*currentOutEdge));
703 continue;
704 }
705 if (currentOutEdge->isFalseEdge()) {
706 falseLinks.push_back(&headNode(*currentOutEdge));
707 continue;
708 }
709 }
710 /// Combine all "true" children of predicate with region
711 if (trueLinks.size() > 1) {
712 Node* regNode = new Node(Node::CDEP_NODE_REGION);
713 addNode(*regNode);
715 currNode, *regNode, Edge::CDEP_EDGE_TRUE);
716 for (unsigned int j = 0; j < trueLinks.size(); j++) {
717 createControlDependenceEdge(*regNode, *trueLinks[j]);
718 disconnectNodes(currNode, *(trueLinks[j]));
719 }
720 }
721 /// Combine all "false" children of predicate with region
722 if (falseLinks.size() > 1) {
723 Node* regNode = new Node(Node::CDEP_NODE_REGION);
724 addNode(*regNode);
726 currNode, *regNode, Edge::CDEP_EDGE_FALSE);
727 for (unsigned int j = 0; j < falseLinks.size(); j++) {
728 createControlDependenceEdge(*regNode, *falseLinks[j]);
729 disconnectNodes(currNode, *(falseLinks[j]));
730 }
731 }
732 }
733 }
734}
735
736/**
737 * Performs serialization of ControlDependenceGraph, turning it into
738 * Control Flow Graph.
739 *
740 * @return ControlFlowGraph representation of CDG
741 * @throw InvalidData in case serialization of graph is not possible
742 */
743void
745 // CDG was previously analyzed
746 if (analyzed()) {
747 return;
748 }
750 Application::logStream() << (boost::format(
751 "\tStarting CDG serialization for %s with %d nodes and %d edges.\n")
752 % name() % nodeCount() % edgeCount()).str();
753 }
754
755 CDGOrderMap componentMap;
756 DescriptorMap rootMap;
757 auto timer = std::chrono::steady_clock::now();
758 /// Find all strong components (loops) in a graph, loop entry nodes
759 /// will have number identifying for which loop component they are entries
760 /// and the strongComponents_ will contains all nodes that are part
761 /// of each component
762 int componentCount = detectStrongComponents(componentMap, rootMap);
763 long elapsed = std::chrono::duration_cast<std::chrono::seconds>(
764 std::chrono::steady_clock::now() - timer)
765 .count();
767 Application::logStream() << (boost::format(
768 "\t\tStrong components: %d components, %d minutes and %d seconds.\n")
769 % componentCount % (elapsed/60) % (elapsed%60)).str();
770 }
771
772 /// map to store post order information for all the nodes of a graph
773 /// From now on, post order info in lastMap will not change
774 CDGOrderMap lastMap;
775 CDGOrder lastOrder(lastMap);
776 /// map to store color information during dfs
777 ColorMap colorMap;
778 Color colorsDFS(colorMap);
779 int fStamp(-1);
780 /// boost::on_finish_vertex will give us post order numbering
781 boost::time_stamper<CDGOrder, int, boost::on_finish_vertex>
782 lastOrderStamper(lastOrder, fStamp);
783 timer = std::chrono::steady_clock::now(); // restart
784 /// Sort nodes in post order, starting from entry node
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)
790 .count();
792 Application::logStream() << (boost::format(
793 "\t\tPost order: %d minutes and %d seconds.\n")
794 % (elapsed/60) % (elapsed%60)).str();
795 }
796
797 timer = std::chrono::steady_clock::now(); // restart
798 /// Computes "region" information, for each node X, set of nodes that are
799 /// executed when X is executed (for node Z, on all paths from X to entry,
800 /// if node Z is region all children of Z will be in "region" of X
801 computeRegionInfo(lastMap);
802 elapsed = std::chrono::duration_cast<std::chrono::seconds>(
803 std::chrono::steady_clock::now() - timer)
804 .count();
806 Application::logStream() << (boost::format(
807 "\t\tRegion: %d minutes and %d seconds.\n")
808 % (elapsed/60) % (elapsed%60)).str();
809 }
810
811 timer = std::chrono::steady_clock::now(); // restart
812 /// Computes "eec" information, for each node X, set of nodes that are
813 /// executed when any node in subgraph of X is executed, computed using
814 /// region information
815 computeEECInfo(lastMap);
816 elapsed = std::chrono::duration_cast<std::chrono::seconds>(
817 std::chrono::steady_clock::now() - timer)
818 .count();
820 Application::logStream() << (boost::format(
821 "\t\tEEC: %d minutes and %d seconds.\n")
822 % (elapsed/60) % (elapsed%60)).str();
823 }
824 analyzed_ = true;
825 timer = std::chrono::steady_clock::now(); // restart
826#if 0
827 // This is really not needed, just for comparing with PDG edge generation
828 // if necessary
829 computeRelations(lastMap);
830 elapsed = std::chrono::duration_cast<std::chrono::seconds>(
831 std::chrono::steady_clock::now() - timer)
832 .count();
834 Application::logStream() << (boost::format(
835 "\t\tRelations: %d minutes and %d seconds.\n")
836 % (elapsed/60) % (elapsed%60)).str();
837 }
838#endif
839}
840
841/**
842 * Detects all strong components of a CDG graph (loops). Strong components are
843 * maximal sets of nodes that are reachable from each other. Each node is member
844 * of some component. If it is not in loop then node is components of it's own.
845 * Augments graph with loop entry and close nodes.
846 * Works iterativly, first detects maximal component, then proceeds to ones
847 * that are "embedded".
848 *
849 * @param components After return contains for each node number of component
850 * to which node belongs
851 * @param roots After return contains for each node a node that is root of
852 * component to which node belongs
853 * @return returns number of components in a graph
854 */
855int
857 CDGOrderMap& components,
858 DescriptorMap& roots) {
859
861 return strongComponents_.size();
862 }
863
864 std::vector<std::pair<Node*, Node*> > backEdges;
865 int componentCount = 0;
866 int currentComponents = 0;
867 /// Will repeat untill all the strong components will be found
868 /// Including weirdly nested :-)
869 do {
870 CDGOrder componentOrder(components);
871 Descriptors componentRoots(roots);
872 currentComponents = 0;
873 /// Node count will change with addition of close nodes
874 currentComponents = boost::strong_components(
875 graph_, componentOrder, boost::root_map(componentRoots));
876
877 // for each component add vector of nodes that belongs to it
878 std::vector<std::set<Node*> > componentVector;
879 componentVector.resize(componentCount + currentComponents);
880
881 /// If the number of components is identical to number of nodes
882 /// there are no loops in graph
883 if (currentComponents == nodeCount()) {
885 break;
886 }
887 /// Add to strong components only those which are loops
888 /// Store them as CDNode*, use of descriptors is not possible
889 /// due to later addition of Nodes which will invalidate
890 /// descriptors
891 for (CDGOrderMap::iterator iterA = components.begin();
892 iterA != components.end(); iterA ++) {
893 Node* cNode = graph_[(*iterA).first];
894 componentVector[(*iterA).second].insert(cNode);
895 }
896
897 for (unsigned int i = componentCount; i < componentVector.size(); i++) {
898 if (componentVector[i].size() > 1) {
899 std::set<Node*>& vector = componentVector[i];
900 std::set<Node*> ref;
901 int componentsSize = strongComponents_.size();
902 for (std::set<Node*>::iterator iterB = vector.begin();
903 iterB != vector.end();
904 iterB++) {
905 ref.insert(*iterB);
906 // Set component number
907 if ((*iterB)->component() == -1){
908 (*iterB)->setComponent(componentsSize);
909 }
910 }
911 strongComponents_.push_back(ref);
912 }
913 }
914
915 /// Detects all loop entry nodes
916 /// Stores Nodes which are identified as loop entry nodes
917 /// together with number to which loop they belong
918 std::vector<std::pair<Node*,int> > newEntry;
919 /// for each entry node, collect edges that points to it from outside
920 /// the loop, deals only with newly added components
921 std::map<Node*, std::vector<Node*> > incomingToEntry;
922 for (unsigned int i = componentCount;
923 i < strongComponents_.size();
924 i++) {
925 std::set<Node*>& nodes = strongComponents_[i];
926 for (std::set<Node*>::iterator iterD = nodes.begin();
927 iterD != nodes.end();
928 iterD++) {
929 EdgeSet edges = inEdges(**iterD);
930 for (EdgeSet::iterator ei = edges.begin();
931 ei != edges.end();
932 ei++) {
933 Node* testedNode = &tailNode(**ei);
934 if (nodes.find(testedNode) == nodes.end()) {
935 if (!(*iterD)->isLoopEntryNode(i)) {
936 /// This may change in which component node it
937 (*iterD)->setLoopEntryNode(i);
938 newEntry.push_back(
939 std::pair<Node*,int>(*iterD,i));
940 incomingToEntry[*iterD].push_back(testedNode);
941 } else {
942 /// Several nodes points to loop entry node
943 /// we create dummy region node to collect those
944 /// edges
945 incomingToEntry[*iterD].push_back(testedNode);
946 }
947 }
948 }
949 }
950 }
951
952 /// Adds close nodes for each loop entry node
953 /// Node and edge descriptors are invalidated here!
954 for (unsigned int j = 0; j < newEntry.size(); j++) {
955 Node* loopNode = newEntry[j].first;
956 std::set<Node*>& nodes =
957 strongComponents_[newEntry[j].second];
958 /// Create one "close" node for each loop entry
959 Node* close = new Node(Node::CDEP_NODE_LOOPCLOSE);
960 close->setComponent(newEntry[j].second);
961 addNode(*close);
962 /// Close node is also part of component
963 strongComponents_[newEntry[j].second].insert(close);
964
965 /// Detect edges to loop entry node from inside component and
966 /// redirect them to close node
967 EdgeSet edges = inEdges(*loopNode);
968 std::vector<Edge*> storeEdges;
969 for (EdgeSet::iterator ei = edges.begin();
970 ei != edges.end();
971 ei++) {
972 Node* sourceNode = &tailNode(**ei);
973 if (nodes.find(sourceNode) != nodes.end()){
974 storeEdges.push_back(*ei);
975 }
976 }
977 /// Actually redirect edges
978 for (unsigned int counter = 0;
979 counter < storeEdges.size();
980 counter++) {
981 moveInEdge(*loopNode, *close, *storeEdges[counter]);
982 }
983 /// Back edge will be added later, after all loops are found
984 backEdges.push_back(
985 std::pair<Node*, Node*>(close, loopNode));
986
987 /// Test if edges were redirected successfully
988 if (inDegree(*close) == 0) {
989 TCEString msg = (boost::format(
990 "Close node for loop entry node %s was not connected!\n")
991 % loopNode->toString()).str();
992 throw ModuleRunTimeError(__FILE__, __LINE__, __func__, msg);
993 }
994
995 /// In case loop entry has multiple incoming edges
996 /// outside loop, we add new region to group them together
997 std::vector<Node*> tmp =
999 incomingToEntry, loopNode);
1000 if (tmp.size() > 1) {
1001 Node* collect = new Node(Node::CDEP_NODE_REGION);
1002 addNode(*collect);
1003 for (unsigned int i = 0; i < tmp.size(); i++) {
1004 Node* input = tmp[i];
1005 EdgeDescriptor ed = connectingEdge(*input, *loopNode);
1006 Edge* e = graph_[ed];
1007 moveInEdge(*loopNode, *collect, *e);
1008 }
1009 ControlDependenceEdge* edge2 =
1011 connectNodes(*collect, *loopNode, *edge2);
1012 }
1013 }
1014 newEntry.clear();
1016 } while (true);
1017
1018 // Add edges from close nodes to their respective loop entries
1019 for (unsigned int i = 0; i < backEdges.size(); i++) {
1021 *backEdges[i].first, *backEdges[i].second, Edge::CDEP_EDGE_LOOPCLOSE);
1022 }
1023 backEdges.clear();
1024 componentsDetected_ = true;
1025 return componentCount;
1026}
1027
1028/**
1029 * Compute the "region" information for each node of graph. Region is used to
1030 * compute "eec" to determine order in which sibling subgraphs will be in
1031 * resulting cfg.
1032 *
1033 * "Region" of node X is set of nodes that will be executed in case is X
1034executed.
1035 *
1036 * @param orderMap post order map of CDG graph, nodes will be augmented with
1037 * "region" information.
1038 */
1039void
1041
1042 int mapSize = orderMap.size();
1043 if (mapSize == 0) {
1044 throw ModuleRunTimeError(__FILE__, __LINE__, __func__,
1045 "No nodes in CDG graph for " + name() + "!");
1046 }
1047 /// Compute "region" information using reverse post-order processing
1048 for (int i = mapSize -1 ; i >= 0 ; i--) {
1049 NodeDescriptor des =
1051 Node* node = graph_[des];
1052 if (!node->isLoopEntryNode()) {
1053 /// For non loop entry nodes, simply compute region info
1054 /// and store it in the node
1055 Node::NodesInfo finalNodesInfo;
1056 regionHelper(node, finalNodesInfo);
1057
1058 for (Node::NodesInfo::iterator k = finalNodesInfo.begin();
1059 k != finalNodesInfo.end(); k++) {
1060 node->addToRegion(**k);
1061 }
1062 } else if (node->region().size() == 0) {
1063 /// for loop entry node, find all other entry nodes
1064 /// of the same loop (component)
1065 /// final region info will be intersection of region infos from
1066 /// all the entry nodes in the same loop
1067 /// it will be same for all the nodes too (they are reachable)
1068 std::vector<Node*> entries;
1069 std::set<Node*> component = strongComponents_[node->component()];
1070 for (std::set<Node*>::iterator si = component.begin();
1071 si != component.end(); si++) {
1072 /// Test for loop entries of same component
1073 /// Loop entry of one component can be regular region node of
1074 /// other "larger" loop
1075 if ((*si)->isLoopEntryNode(node->component())) {
1076 entries.push_back(*si);
1077 }
1078 }
1079 Node::NodesInfo finalNodesInfo;
1080 for (unsigned int i = 0; i < entries.size(); i++) {
1081 Node* entryNode = entries[i];
1082 regionHelper(entryNode, finalNodesInfo);
1083 }
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++) {
1088 result->addToRegion(**k);
1089 }
1090 }
1091 }
1092 }
1093}
1094
1095/**
1096 * Compute the "eec" information for each node of graph. Eec is used to
1097 * determine order in which sibling subgraphs needs to be scheduled in
1098 * resulting cfg.
1099 *
1100 * "eec" of node X is set of nodes that will be executed in case any of the
1101nodes
1102 * in subgraph of X will be executed.
1103 *
1104 * @param orderMap post order map of CDG graph, nodes augmented with
1105 * "region" information, "eec" information will be added.
1106 */
1107void
1109 int mapSize = orderMap.size();
1110 for (int i = 0; i < mapSize; i++) {
1111 NodeDescriptor des =
1113 orderMap, i);
1114 Node* node = graph_[des];
1115 /// eec already exists, skip
1116 if (node->eec().size() > 0) {
1117 continue;
1118 }
1119 /// Found close node, eec(node) == intersection of all close
1120 /// nodes of same loop region(node) (close node is as leaf node)
1121 if (node->isLoopCloseNode() && node->eec().size() == 0) {
1122 std::vector<Node*> closeNodes;
1123 std::set<Node*> component = strongComponents_[node->component()];
1124 // collect all loop close nodes of same loop
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();
1132 }
1133 }
1134 Node::NodesInfo finalInfo;
1135 Node::NodesInfo storeResult;
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();
1142 }
1143 // add intersection of all region infos to each close node in loop
1144 for (unsigned j = 0; j < closeNodes.size(); j++) {
1145 Node* result = closeNodes[j];
1146 if(result->eec().size() != 0) {
1147 TCEString msg = (boost::format(
1148 "Close node %s in %s already has eec!\n")
1149 % result->toString() % node->toString()).str();
1150 throw ModuleRunTimeError(__FILE__, __LINE__, __func__, msg);
1151 }
1152 for (Node::NodesInfo::iterator k = finalInfo.begin();
1153 k != finalInfo.end(); k++) {
1154 result->addToEEC(**k);
1155 }
1156 }
1157 continue;
1158 }
1159 if (outDegree(*node) == 0) {
1160 /// Found leaf node, eec(node) == region(node)
1161 Node::NodesInfo regionX = node->region();
1162 for (Node::NodesInfo::iterator t = regionX.begin();
1163 t != regionX.end(); t++) {
1164 node->addToEEC( **t);
1165 }
1166 continue;
1167 } else {
1168 if (node->isPredicateNode()) {
1169 /// if node is predicate we also store pseudo information for
1170 /// part of basic block which does not compute predicate
1171 /// itself, it is just set of statements - leafs
1172 Node::NodesInfo regionX = node->region();
1173 for (Node::NodesInfo::iterator t = regionX.begin();
1174 t != regionX.end(); t++) {
1175 node->addToPseudoPredicateEEC( **t);
1176 }
1177 }
1178
1179 /// Not a leaf node,
1180 /// eec(x) = intersection(eec(children(x)) \ children(x)
1181 NodeSet succ = successors(*node);
1182 Node::NodesInfo childNodes;
1183 // copy successors from NodeSet to NodesInfo otherwise
1184 // comparator function object in NodeSet makes chaos with
1185 // set_difference
1186 for (NodeSet::iterator su = succ.begin();
1187 su != succ.end(); su++) {
1188 childNodes.insert(*su);
1189 }
1190 Node::NodesInfo finalEEC;
1191
1192 // Fill in candidate set with data from first successor
1193 finalEEC.insert(
1194 (*(childNodes.begin()))->eec().begin(),
1195 (*(childNodes.begin()))->eec().end());
1196 // compute intersection of successors eec
1197 for(Node::NodesInfo::iterator j = childNodes.begin();
1198 j != childNodes.end(); j++ ) {
1199 Node::NodesInfo storeResult;
1200 SetTools::intersection(finalEEC, (*j)->eec(), storeResult);
1201 finalEEC.swap(storeResult);
1202 storeResult.clear();
1203 }
1204 std::vector<Node*> result(finalEEC.size(), NULL);
1205 // compute set difference, returns iterator pointing to .end()
1206 // of the result
1207 std::vector<Node*>::iterator resultEnd =
1208 std::set_difference(finalEEC.begin(), finalEEC.end(),
1209 childNodes.begin(), childNodes.end(), result.begin());
1210 // push resulting eec into the node eec info
1211 for (std::vector<Node*>::iterator t = result.begin();
1212 t != resultEnd; t++) {
1213 node->addToEEC(**t);
1214 }
1215 }
1216 }
1217}
1218
1219/**
1220 * Defined relation between two sibling nodes based on their type and eec info
1221 */
1224 bool AinA = false;
1225 bool BinB = false;
1226 bool BinA = false;
1227 bool AinB = false;
1228 // both a and b are simple basic blocks, order is given by data dependencies
1229 // no need to test eec info
1230 if (a->isBBNode() && b->isBBNode()
1231 && !a->isPredicateNode() && !b->isPredicateNode()) {
1232 return ANY_ORDER;
1233 }
1234
1235 if (AssocTools::containsKey(a->eec(), a)) {
1236 AinA = true;
1237 }
1238 if (AssocTools::containsKey(b->eec(), b)) {
1239 BinB = true;
1240 }
1241 if (AssocTools::containsKey(a->eec(), b)) {
1242 BinA = true;
1243 }
1244 if (AssocTools::containsKey(b->eec(), a)) {
1245 AinB = true;
1246 }
1247 if ((a->isLoopEntryNode() || a->isPredicateNode())
1248 && (b->isBBNode() && !b->isPredicateNode())
1249 && AinA == true) {
1250 if (a->isLastNode()) {
1251 return B_BEFORE_A;
1252 }
1253 return ANY_ORDER;
1254 }
1255 if ((a->isLoopEntryNode() || a->isPredicateNode())
1256 && (b->isLoopEntryNode() || b->isPredicateNode())
1257 && AinA == true && BinB == true) {
1258 if (a->isLastNode()) {
1259 return B_BEFORE_A;
1260 }
1261 if (b->isLastNode()) {
1262 return A_BEFORE_B;
1263 }
1264 return ANY_ORDER;
1265 }
1266 if ((a->isLoopEntryNode() || a->isPredicateNode())
1267 && (b->isBBNode() && !b->isPredicateNode())
1268 && AinA == false) {
1269 return B_BEFORE_A;
1270 }
1271 if ((a->isLoopEntryNode() || a->isPredicateNode())
1272 && (b->isLoopEntryNode() || b->isPredicateNode())
1273 && AinA == false && BinB == true) {
1274 return B_BEFORE_A;
1275 }
1276 if ((a->isLoopEntryNode() || a->isPredicateNode())
1277 && (b->isLoopEntryNode() || b->isPredicateNode())
1278 && AinA == false && BinB == false) {
1279 return UNORDERABLE;
1280 }
1281 if ((a->isRegionNode() && AinB == true)
1282 && (b->isBBNode() || b->isLoopEntryNode() || b->isPredicateNode())) {
1283 return B_BEFORE_A;
1284 }
1285 if ((a->isRegionNode() && AinB == false)
1286 && (b->isLoopEntryNode() || b->isPredicateNode())
1287 && AinB == false) {
1288 return UNORDERABLE;
1289 }
1290 if ((a->isRegionNode() && AinB == false)
1291 && (b->isRegionNode() && BinA == true)) {
1292 return B_BEFORE_A;
1293 }
1294 if ((a->isRegionNode() && AinB == false)
1295 && (b->isRegionNode() && BinA == false)) {
1296 return UNORDERABLE;
1297 }
1298 if ((a->isLoopCloseNode() && AinB == true)
1299 && (b->isBBNode() || b->isPredicateNode() || b->isLoopEntryNode()
1300 || b->isRegionNode())) {
1301 return B_BEFORE_A;
1302 }
1303 if ((a->isLoopCloseNode() && AinB == false)
1304 && (b->isPredicateNode() || b->isLoopEntryNode()
1305 || b->isRegionNode())) {
1306 return UNORDERABLE;
1307 }
1308 /// FIXME:
1309 /// Unique region node rule is broken when creating loop
1310 /// entry nodes (removing loop back edge) and creating new region for
1311 /// incoming edges into loop entry - there can be another region
1312 /// which already has same set of dependences and loop entry was
1313 /// supposed to be child of that, but was not. Problem with detection
1314 /// of subsets of dependencies when creating region nodes!
1315 if ((a->isRegionNode() && AinB == true)
1316 && (b->isRegionNode() && BinA == true)) {
1317 if (a->isLastNode()) {
1318 return B_BEFORE_A;
1319 }
1320 if (b->isLastNode()) {
1321 return A_BEFORE_B;
1322 }
1323 return ANY_ORDER;
1324 }
1325 return ERROR;
1326}
1327
1328/**
1329 * Helper function to compute actual region information for a node.
1330 * Called several times for a case when there are loop entry nodes
1331 * detected.
1332 *
1333 * @param node Node for which to compute region info
1334 * @param cdg Filtered PDG graph with only control dependence edges
1335 * @param finalNodesInfo stores actuall computed region info
1336 */
1337void
1339 Node* node,
1340 Node::NodesInfo& finalNodesInfo){
1341
1342 std::vector<Node::NodesInfo> tmpResult;
1343 /// Find all incoming control dependence edges
1344 EdgeSet edges = inEdges(*node);
1345 for (EdgeSet::iterator ei = edges.begin();
1346 ei != edges.end();
1347 ++ei) {
1348 Node* previous = &tailNode(**ei);
1349 if (previous->isRegionNode()
1350 || previous->isLoopEntryNode()
1351 || previous->isEntryNode()) {
1352 if (previous->region().size() == 0 &&
1353 !previous->isEntryNode()) {
1354 /// If parent's region is not yet computed (should be btw)
1355 /// compute it before continuing.
1356 Node::NodesInfo addedNodesInfo;
1357 regionHelper(previous, addedNodesInfo);
1358 for (Node::NodesInfo::iterator k = addedNodesInfo.begin();
1359 k != addedNodesInfo.end();
1360 k++) {
1361 previous->addToRegion(**k);
1362 }
1363 }
1364 /// region(node,parent) == region(parent) U childern(parent)
1365 Node::NodesInfo tmp = previous->region();
1366 EdgeSet outgoingEdges = outEdges(*previous);
1367 for (EdgeSet::iterator ei = outgoingEdges.begin();
1368 ei != outgoingEdges.end();
1369 ++ei) {
1370 Node* testedNode = &headNode(**ei);
1371 tmp.insert(testedNode);
1372 }
1373 tmpResult.push_back(tmp);
1374 } else if (previous->isPredicateNode()){
1375 /// region(node,parent) == region(parent)
1376 Node::NodesInfo tmp = previous->region();
1377 tmpResult.push_back(tmp);
1378 } else {
1379 if (!previous->isLoopCloseNode()) {
1380 TCEString message = (boost::format(
1381 "Node: %s , parent %s.")
1382 % node->toString() % previous->toString()).str();
1383 throw ModuleRunTimeError(__FILE__, __LINE__, __func__, message);
1384 }
1385 }
1386 }
1387 /// fill in final region info with info from first of parents
1388 if (tmpResult.size() > 0) {
1389 finalNodesInfo.insert(
1390 tmpResult[0].begin(), tmpResult[0].end());
1391 }
1392 /// region(node) = intersection(region(node,parent(node)))
1393 /// for all parents. finalNodesInfo is already initialized from
1394 /// counter 0
1395 for (unsigned int l = 1; l < tmpResult.size(); l++) {
1396 Node::NodesInfo storeResult;
1398 finalNodesInfo, tmpResult[l], storeResult);
1399 finalNodesInfo.swap(storeResult);
1400 storeResult.clear();
1401 }
1402}
1403
1404/**
1405 * Computes relation between every pair of nodes in a graph that has
1406 * common parent.
1407 *
1408 * @param orderMap Post order map of a graph
1409 */
1410void
1412 /// Process nodes in post order, guarantees child nodes will be processed
1413 /// before their parent
1414 int mapSize = orderMap.size();
1415 for (int i = 0; i < mapSize; i++) {
1416 NodeDescriptor des =
1418 Node* node = graph_[des];
1419 /// MoveNodes are skipped here, they are always child of region
1420 if (node->isRegionNode()
1421 || node->isLoopEntryNode()
1422 || node->isPredicateNode()) {
1424 continue;
1425 }
1426 }
1427}
1428
1429/**
1430 * "Sorts" all the child nodes of a region in topological order based on
1431 * their control and data dependencies.
1432 *
1433 * @param regionNode Region node who's child nodes to process
1434 * @param cdgGraph Control Dependence subraph
1435 */
1436void
1438
1439 /// Get all child nodes of region node
1440
1441 EdgeSet edges = outEdges(*regionNode);
1442
1443 std::vector<std::pair<Node*, Node*> > newEdges;
1444 for (EdgeSet::iterator ei1 = edges.begin();
1445 ei1 != edges.end();
1446 ++ei1) {
1447 Node* node1 = &headNode(**ei1);
1448
1449 /// node1 will be compared against all the other previously untested
1450 /// nodes
1451 EdgeSet::iterator ei2 = ei1;
1452 ei2++;
1453 for (; ei2 != edges.end(); ++ei2) {
1454 Node* node2 = &headNode(**ei2);
1455
1456 /// Test relation between siblings, should never return ERROR twice!
1457 CompareResult result = compareSiblings(node1, node2);
1458 if (result == ERROR) {
1459 result = compareSiblings(node2, node1);
1460 }
1461 switch(result) {
1462 case A_BEFORE_B:
1463 newEdges.push_back(std::pair<Node*, Node*>(node1, node2));
1464 break;
1465 case B_BEFORE_A:
1466 newEdges.push_back(std::pair<Node*, Node*>(node2, node1));
1467 break;
1468 case UNORDERABLE:
1470 Application::logStream() << (boost::format(
1471 "Nodes %s and %s can not be put into any order.\n")
1472 % node1->toString()% node2->toString()).str();
1473 }
1474 break;
1475 case ANY_ORDER:
1476 break;
1477 case ERROR:
1478 throw ModuleRunTimeError(
1479 __FILE__, __LINE__, __func__, (boost::format(
1480 "Ordering error for A='%s' and B='%s'.")
1481 % node1->toString() % node2->toString()).str());
1482 break;
1483 }
1484 }
1485 }
1486 return;
1487#if 0
1488 /// This is just for testing
1489 /// Add actuall control dependence edges for serialization
1490 /// Edges are really not needed here, they will be added into PDG
1491 for (unsigned int i = 0; i < newEdges.size(); i++) {
1493 connectNodes(*newEdges[i].first, *newEdges[i].second, *direction);
1494 }
1495 return;
1496#endif
1497}
#define __func__
#define IGNORE_COMPILER_WARNING(X)
#define POP_CLANG_DIAGS
#define POP_COMPILER_DIAGS
#define IGNORE_CLANG_WARNING(X)
#define DEBUG_LEVEL
find Finds info of the inner loops in the false
static int verboseLevel()
static std::ostream & logStream()
static bool containsKey(const ContainerType &aContainer, const KeyType &aKey)
bool isEntryBB() const
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
Definition BoostGraph.hh:87
virtual Edge & outEdge(const Node &node, const int index) const
virtual bool hasEdge(const Node &nTail, const Node &nHead) const
virtual NodeSet successors(const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
EdgeDescriptor connectingEdge(const Node &nTail, const Node &nHead) const
GraphTraits::edge_descriptor EdgeDescriptor
Type with which edges of the graph are seen internally.
std::set< ControlDependenceNode *, typename GraphNode::Comparator > NodeSet
Definition BoostGraph.hh:86
virtual void moveInEdge(const Node &source, const Node &destination, Edge &edge, const Node *tail=NULL, bool childs=false)
ControlDependenceNode Node
The (base) node type managed by this graph.
Definition BoostGraph.hh:90
virtual EdgeSet outEdges(const Node &node) const
virtual Node & tailNode(const Edge &edge) const
ControlDependenceEdge Edge
The (base) edge type managed by this graph.
Definition BoostGraph.hh:92
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)
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)
std::map< NodeDescriptor, NodeDescriptor > DescriptorMap
Storage for relations between nodes.
void regionHelper(Node *, Node::NodesInfo &)
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
ControlDependenceNode & entryNode()
bool analyzed_
Indicates that CDG already has data required for serialization.
void addToRegion(ControlDependenceNode &node)
std::string toString() const
void setComponent(int component)
std::set< ControlDependenceNode * > NodesInfo
Storage type for other nodes of same graph needed to define some non graph relations....
void addToEEC(ControlDependenceNode &node)
ReversedGraph & reversedGraph() const
reverse_graph< ControlFlowGraph::Graph > ReversedGraph
BasicBlockNode & exitNode() const
TTAProgram::Program * program() const
std::string errorMessageStack(bool messagesOnly=false) const
Definition Exception.cc:138
virtual std::string toString() const
Definition GraphNode.cc:61
static void deleteAllKeys(MapType &aMap)
static KeyType keyForValue(const MapType &aMap, const ValueType &aValue)
static void deleteAllValues(MapType &aMap)
static bool containsKey(const MapType &aMap, const KeyType &aKey)
static void intersection(const std::set< ValueType > &firstContainer, const std::set< ValueType > &secondContainer, std::set< ValueType > &intersection)