ROSE  0.9.9.139
controlDependence.h
1 #pragma once
2 
3 // DQ (10/5/2014): This is more strict now that we include rose_config.h in the sage3basic.h.
4 // #include "rose.h"
5 // rose.h and sage3basic.h should not be included in librose header files. [Robb P. Matzke 2014-10-15]
6 // #include "sage3basic.h"
7 
8 #include <map>
9 #include <utility>
10 #include "staticSingleAssignment.h"
11 #include <boost/foreach.hpp>
12 
13 namespace ssa_private
14 {
15  using namespace boost;
16  using namespace std;
17 
21  template<class CfgNodeT, class CfgEdgeT>
22  multimap< CfgNodeT, pair<CfgNodeT, CfgEdgeT> >
23  calculateControlDependence(SgFunctionDefinition* function, const map<CfgNodeT, CfgNodeT>& iPostDominatorMap)
24  {
25  //Map from each node to the nodes it's control dependent on (and corresponding edges)
26  multimap< CfgNodeT, pair<CfgNodeT, CfgEdgeT> > controlDepdendences;
27 
28  //Let's iterate the control flow graph and stop every time we hit an edge with a condition
29  set<CfgNodeT> visited;
30  set<CfgNodeT> worklist;
31 
32  CfgNodeT sourceNode = function->cfgForBeginning();
33  worklist.insert(sourceNode);
34 
35  while (!worklist.empty())
36  {
37  //Get the node to work on
38  sourceNode = *worklist.begin();
39  worklist.erase(worklist.begin());
40  visited.insert(sourceNode);
41 
42  //For every edge, add it to the worklist
43 
44  BOOST_FOREACH(const CfgEdgeT& edge, sourceNode.outEdges())
45  {
46  CfgNodeT targetNode = edge.target();
47 
48  //Insert the child in the worklist if the it hasn't been visited yet
49  if (visited.count(targetNode) == 0)
50  {
51  worklist.insert(targetNode);
52  }
53 
54  //Check if we need to process this edge in control dependence calculation
55  if (edge.condition() == VirtualCFG::eckUnconditional)
56  continue;
57 
58  //We traverse from nextNode up in the postdominator tree until we reach the parent of currNode.
59  CfgNodeT parent;
60  typename map<CfgNodeT, CfgNodeT>::const_iterator parentIter = iPostDominatorMap.find(sourceNode);
61  ROSE_ASSERT(parentIter != iPostDominatorMap.end());
62  parent = parentIter->second;
63 
64  //This is the node that we'll be marking as control dependent
65  CfgNodeT currNode = targetNode;
66 
67  while (true)
68  {
69  //If we reach the parent of the source, stop
70  if (currNode == parent)
71  {
72  break;
73  }
74 
75  //Add a control dependence from the source to the new node
76  controlDepdendences.insert(make_pair(currNode, make_pair(sourceNode, edge)));
77 
78  if (StaticSingleAssignment::getDebugExtra())
79  {
80  printf("%s is control-dependent on %s - %s \n", currNode.toStringForDebugging().c_str(),
81  sourceNode.toStringForDebugging().c_str(), edge.condition() == VirtualCFG::eckTrue ? "true" : "false");
82  }
83 
84  //Move to the parent of the current node
85  parentIter = iPostDominatorMap.find(currNode);
86  ROSE_ASSERT(parentIter != iPostDominatorMap.end());
87  currNode = parentIter->second;
88  }
89  }
90  }
91 
92  return controlDepdendences;
93  }
94 }
95 
STL namespace.
This class represents the concept of a scope in C++ (e.g. global scope, fuction scope, etc.).