ROSE  0.9.10.54
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 #if 1
16  // using namespace boost;
17  // using namespace std;
18 
22  template<class CfgNodeT, class CfgEdgeT>
23  std::multimap< CfgNodeT, std::pair<CfgNodeT, CfgEdgeT> > calculateControlDependence(SgFunctionDefinition* function, const std::map<CfgNodeT, CfgNodeT>& iPostDominatorMap);
24 #else
25  using namespace boost;
26  using namespace std;
27 
28  // DQ (1/7/2018): Move this from the header file to the source code file (staticSingleAssignmentCalculation.C).
32  template<class CfgNodeT, class CfgEdgeT>
33  multimap< CfgNodeT, pair<CfgNodeT, CfgEdgeT> >
34  calculateControlDependence(SgFunctionDefinition* function, const map<CfgNodeT, CfgNodeT>& iPostDominatorMap)
35  {
36  //Map from each node to the nodes it's control dependent on (and corresponding edges)
37  multimap< CfgNodeT, pair<CfgNodeT, CfgEdgeT> > controlDepdendences;
38 
39  //Let's iterate the control flow graph and stop every time we hit an edge with a condition
40  set<CfgNodeT> visited;
41  set<CfgNodeT> worklist;
42 
43  CfgNodeT sourceNode = function->cfgForBeginning();
44  worklist.insert(sourceNode);
45 
46  while (!worklist.empty())
47  {
48  //Get the node to work on
49  sourceNode = *worklist.begin();
50  worklist.erase(worklist.begin());
51  visited.insert(sourceNode);
52 
53  //For every edge, add it to the worklist
54 
55  BOOST_FOREACH(const CfgEdgeT& edge, sourceNode.outEdges())
56  {
57  CfgNodeT targetNode = edge.target();
58 
59  //Insert the child in the worklist if the it hasn't been visited yet
60  if (visited.count(targetNode) == 0)
61  {
62  worklist.insert(targetNode);
63  }
64 
65  //Check if we need to process this edge in control dependence calculation
66  if (edge.condition() == VirtualCFG::eckUnconditional)
67  continue;
68 
69  //We traverse from nextNode up in the postdominator tree until we reach the parent of currNode.
70  CfgNodeT parent;
71  typename map<CfgNodeT, CfgNodeT>::const_iterator parentIter = iPostDominatorMap.find(sourceNode);
72 
73  ROSE_ASSERT(parentIter != iPostDominatorMap.end());
74 
75  parent = parentIter->second;
76 
77  //This is the node that we'll be marking as control dependent
78  CfgNodeT currNode = targetNode;
79 
80  while (true)
81  {
82  //If we reach the parent of the source, stop
83  if (currNode == parent)
84  {
85  break;
86  }
87 
88  //Add a control dependence from the source to the new node
89  controlDepdendences.insert(make_pair(currNode, make_pair(sourceNode, edge)));
90 
91  if (StaticSingleAssignment::getDebugExtra())
92  {
93  printf("%s is control-dependent on %s - %s \n", currNode.toStringForDebugging().c_str(),
94  sourceNode.toStringForDebugging().c_str(), edge.condition() == VirtualCFG::eckTrue ? "true" : "false");
95  }
96 
97  //Move to the parent of the current node
98  parentIter = iPostDominatorMap.find(currNode);
99  ROSE_ASSERT(parentIter != iPostDominatorMap.end());
100  currNode = parentIter->second;
101  }
102  }
103  }
104 
105  return controlDepdendences;
106  }
107 #endif
108 
109 }
110 
STL namespace.
This class represents the concept of a scope in C++ (e.g. global scope, fuction scope, etc.).