ROSE  0.9.9.109
iteratedDominanceFrontier.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 <boostGraphCFG.h>
9 #include <vector>
10 #include <set>
11 #include <map>
12 #include <iterator>
13 #include <boost/foreach.hpp>
14 #include <boost/graph/adjacency_list.hpp>
15 #include <boost/graph/topological_sort.hpp>
16 
17 namespace ssa_private
18 {
19  using namespace std;
20  using namespace boost;
21 
24  template<class CfgNodeT>
25  set<CfgNodeT> calculateIteratedDominanceFrontier(const map<CfgNodeT, set<CfgNodeT> >& dominanceFrontiers,
26  const vector<CfgNodeT>& startNodes)
27  {
28  set<CfgNodeT> result;
29  set<CfgNodeT> visitedNodes;
30  vector<CfgNodeT> worklist;
31 
32  worklist.insert(worklist.end(), startNodes.begin(), startNodes.end());
33 
34  while (!worklist.empty())
35  {
36  CfgNodeT currentNode = worklist.back();
37  worklist.pop_back();
38  visitedNodes.insert(currentNode);
39 
40  //Get the dominance frontier of the node and add it to the results
41  ROSE_ASSERT(dominanceFrontiers.count(currentNode) != 0);
42  const set<CfgNodeT>& dominanceFrontier = dominanceFrontiers.find(currentNode)->second;
43 
44  //Add all the children to the result and to the worklist
45 
46  BOOST_FOREACH(CfgNodeT dfNode, dominanceFrontier)
47  {
48  if (visitedNodes.count(dfNode) > 0)
49  continue;
50 
51  result.insert(dfNode);
52  worklist.push_back(dfNode);
53  }
54  }
55 
56  return result;
57  }
58 
62  template<class CfgNodeT, class CfgEdgeT>
63  map<CfgNodeT, set<CfgNodeT> > calculateDominanceFrontiers(SgFunctionDefinition* func, map<CfgNodeT, CfgNodeT>* iDominatorMap,
64  map<CfgNodeT, CfgNodeT>* iPostDominatorMap)
65  {
66  typedef CFG<CfgNodeT, CfgEdgeT> ControlFlowGraph;
67 
68  //Build a CFG first
69  ControlFlowGraph functionCfg(func);
70 
71  //Build the dominator tree
72  typename ControlFlowGraph::VertexVertexMap dominatorTreeMap = functionCfg.getDominatorTree();
73 
74  //TODO: This code converts a VertexVertex Map to a boost graph. Should be factored out
75  typedef adjacency_list<vecS, vecS, bidirectionalS, CfgNodeT> TreeType;
76  TreeType domTree;
77  typedef typename graph_traits<TreeType>::vertex_descriptor TreeVertex;
78 
79  set<CfgNodeT> addedNodes;
80  map<CfgNodeT, TreeVertex> cfgNodeToVertex;
81 
82  BOOST_FOREACH(typename ControlFlowGraph::VertexVertexMap::value_type& nodeDominatorPair, dominatorTreeMap)
83  {
84  CfgNodeT node = *functionCfg[nodeDominatorPair.first];
85  CfgNodeT dominator = *functionCfg[nodeDominatorPair.second];
86 
87  if (addedNodes.count(dominator) == 0)
88  {
89  TreeVertex newVertex = add_vertex(domTree);
90  cfgNodeToVertex[dominator] = newVertex;
91  domTree[newVertex] = dominator;
92  addedNodes.insert(dominator);
93  }
94 
95  if (addedNodes.count(node) == 0)
96  {
97  TreeVertex newVertex = add_vertex(domTree);
98  cfgNodeToVertex[node] = newVertex;
99  domTree[newVertex] = node;
100  addedNodes.insert(node);
101  }
102 
103  //Add the edge from dominator to node
104  add_edge(cfgNodeToVertex[dominator], cfgNodeToVertex[node], domTree);
105 
106  if (iDominatorMap != NULL)
107  {
108  ROSE_ASSERT(iDominatorMap->count(node) == 0);
109  iDominatorMap->insert(make_pair(node, dominator));
110  }
111  }
112 
113  //Get a topological ordering of the vertices
114  vector<TreeVertex> reverseTopological;
115  topological_sort(domTree, back_inserter(reverseTopological));
116 
117  //Calculate all the dominance frontiers. This algorithm is from figure 10, Cytron et. al 1991
118  map<CfgNodeT, set<CfgNodeT> > dominanceFrontiers;
119 
120  BOOST_FOREACH(TreeVertex v, reverseTopological)
121  {
122  CfgNodeT currentNode = domTree[v];
123  set<CfgNodeT>& currentDominanceFrontier = dominanceFrontiers[currentNode];
124 
125  //Local contribution: Iterate over all the successors of v in the control flow graph
126 
127  BOOST_FOREACH(CfgEdgeT outEdge, currentNode.outEdges())
128  {
129  CfgNodeT successor = outEdge.target();
130 
131  //Get the immediate dominator of the successor
132  typename ControlFlowGraph::Vertex successorVertex = functionCfg.getVertexForNode(successor);
133 #if !USE_ROSE
134  // DQ (11/3/2011): EDG compilains about this (but GNU allowed it, I think that EDG might be correct.
135  // since it might be a private variable. But since we are only trying to compile ROSE with ROSE (using the
136  // new EDG 4.3 front-end as a tests) we can just skip this case for now.
137  ROSE_ASSERT(successorVertex != ControlFlowGraph::GraphTraits::null_vertex());
138 #endif
139  ROSE_ASSERT(dominatorTreeMap.count(successorVertex) == 1);
140  typename ControlFlowGraph::Vertex iDominatorVertex = dominatorTreeMap[successorVertex];
141  CfgNodeT iDominator = *functionCfg[iDominatorVertex];
142 
143  //If we have a successor that we don't dominate, that successor is in our dominance frontier
144  if (iDominator != currentNode)
145  {
146  currentDominanceFrontier.insert(successor);
147  }
148  }
149 
150  //"Up" contribution. Iterate over all children in the dominator tree
151  typename graph_traits<TreeType>::adjacency_iterator currentIter, lastIter;
152  for (tie(currentIter, lastIter) = adjacent_vertices(v, domTree); currentIter != lastIter; currentIter++)
153  {
154  CfgNodeT childNode = domTree[*currentIter];
155  const set<CfgNodeT>& childDominanceFrontier = dominanceFrontiers[childNode];
156 
157  BOOST_FOREACH(CfgNodeT childDFNode, childDominanceFrontier)
158  {
159  //Get the immediate dominator of the child DF node
160  typename ControlFlowGraph::Vertex childDFVertex = functionCfg.getVertexForNode(childDFNode);
161 #if !USE_ROSE
162  // DQ (11/3/2011): EDG compilains about this (but GNU allowed it, I think that EDG might be correct.
163  // since it might be a private variable. But since we are only trying to compile ROSE with ROSE (using the
164  // new EDG 4.3 front-end as a tests) we can just skip this case for now.
165  ROSE_ASSERT(childDFVertex != ControlFlowGraph::GraphTraits::null_vertex());
166 #endif
167  ROSE_ASSERT(dominatorTreeMap.count(childDFVertex) == 1);
168  typename ControlFlowGraph::Vertex iDominatorVertex = dominatorTreeMap[childDFVertex];
169  CfgNodeT iDominator = *functionCfg[iDominatorVertex];
170 
171  if (iDominator != currentNode)
172  {
173  currentDominanceFrontier.insert(childDFNode);
174  }
175  }
176  }
177  }
178 
179  //While we're at it, calculate the postdominator tree
180  if (iPostDominatorMap != NULL)
181  {
182  typename ControlFlowGraph::VertexVertexMap postDominatorTreeMap = functionCfg.getPostdominatorTree();
183 
184  BOOST_FOREACH(typename ControlFlowGraph::VertexVertexMap::value_type& nodePostDominatorPair, postDominatorTreeMap)
185  {
186  CfgNodeT node = *functionCfg[nodePostDominatorPair.first];
187  CfgNodeT postDominator = *functionCfg[nodePostDominatorPair.second];
188 
189  ROSE_ASSERT(iPostDominatorMap->count(node) == 0);
190  iPostDominatorMap->insert(make_pair(node, postDominator));
191  }
192  }
193 
194  return dominanceFrontiers;
195  }
196 
197 }
STL namespace.
Sawyer::Container::Graph< CfgVertex, CfgEdge > ControlFlowGraph
Control flow graph.
This class represents the concept of a scope in C++ (e.g. global scope, fuction scope, etc.).