ROSE  0.9.6a
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
DominatorTreeImpl.h
Go to the documentation of this file.
1 // #include "rose.h"
2 #include "filteredCFG.h"
3 #include "DominatorTree.h"
4 #include <map>
5 namespace DominatorTreesAndDominanceFrontiers
6 {
7  template < typename CFGFilterFunction > void TemplatedDominatorTree <
8  CFGFilterFunction >::writeDot(char *filename)
9  {
10  std::ofstream f(filename);
11 
12  f << "digraph \"G" << filename << "\" {" << std::endl;
13  // output all of the nodes
14  int dtSize = getSize();
15  for (int i = 0; i < dtSize; i++)
16  {
17  f << "\"" << i << "\" [label = \"ID " <<i<<"\\n"<< escapeString(getCFGNodeFromID(i).
18  toString()) << "\"];" << std::endl;
19  if (i > 0)
20  f << "\"" << getImDomID(i) << "\" -> \"" << i << "\";" << std::endl;
21  }
22  f << "}" << std::endl;
23 
24  f.close();
25  }
26 
28  template < typename CFGFilterFunction > TemplatedDominatorTree < CFGFilterFunction >::TemplatedDominatorTree(SgNode * head, Direction d):DominatorForwardBackwardWrapperClass < CFGFilterFunction > (d),
29  cfgRoot((d ==
30  PRE_DOMINATOR) ? (head->cfgForBeginning()) : (head->cfgForEnd()))//,treeDirection(d)
31  {
32 // treeDirection = d;
33  init();
34  depthFirstSearch();
35  calculateImmediateDominators();
36  }
37 
38  // create the dfs-order for imdom calculations
39  template < typename CFGFilterFunction > void TemplatedDominatorTree <
40  CFGFilterFunction >::depthFirstSearch()
41  {
42  std::vector < VirtualCFG::FilteredCFGNode < CFGFilterFunction > >workList;
43  workList.push_back(cfgRoot);
44  std::vector<int>parentWorkList;
45  parentWorkList.push_back(0);
46  int nodeCount = 0;
47 
48  while (workList.size() > 0)
49  {
50  int parent;
51  VirtualCFG::FilteredCFGNode < CFGFilterFunction > current = workList.back();
52  workList.pop_back();
53  parent=parentWorkList.back();parentWorkList.pop_back();
54 #ifdef DEBUG
55  std::cout <<"DFS: processing node <"<<current.toString()<<">"<<nodeCount<<std::endl;
56 #endif
57  // if the node is not in the map, it has not been processed
58  if (nodeToIdMap.count(current) == 0)
59  {
60 #ifdef DEBUG
61  std::cout <<"\tThis node has not been process, assigning ID "<<nodeCount<<std::endl;
62 #endif
63  // the first ID is 0. therefore idToNode.size() returns the
64  // next id
65  nodeToIdMap[current] = nodeCount;
66  // put the node in the vector
67  idToNode.push_back(current);
68  semi.push_back(nodeCount);
69  idom.push_back(-1);
70  ancestor.push_back(-1);
71  dfsParent.push_back(parent);
72  buckets.push_back(std::set < int >());
73 
74  std::vector < VirtualCFG::FilteredCFGEdge < CFGFilterFunction > >outEdges =
75  this->getDirectionModifiedOutEdges(current);
76  for (unsigned int i = 0; i < outEdges.size(); i++)
77  {
78  workList.push_back(this->target(outEdges[i]));
79  parentWorkList.push_back(nodeCount);
80  }
81  nodeCount++;
82  }
83  }
84 #ifdef DEBUG
85  std::cout << "Depth First Search order of CFG-Nodes" << std::endl;
86 // VirtualCFG::FilteredCFGNode < CFGFilterFunction > testVar;
87 // typename std::map < VirtualCFG::FilteredCFGNode < CFGFilterFunction >, int>::iterator mapTest;
88  typename std::map < VirtualCFG::FilteredCFGNode < CFGFilterFunction >, int>::iterator i;
89 //, std::less < VirtualCFG::FilteredCFGNode < CFGFilterFunction > > >::iterator i;
90  for (i = nodeToIdMap.begin(); i != nodeToIdMap.end(); i++)
91  {
92  std::cout << (*i).first.toString() << "\t" << (*i).second << std::endl;
93  }
94 #endif
95  }
96 
98  template < typename CFGFilterFunction > void TemplatedDominatorTree <
99  CFGFilterFunction >::link(int ancest, int current)
100  {
101  ancestor[current] = ancest;
102  }
103 
104  template < typename CFGFilterFunction > int TemplatedDominatorTree <
105  CFGFilterFunction >::eval(int node)
106  {
107  int cmp = node;
108  int tmp = ancestor[cmp];
109  while (tmp > -1 && ancestor[tmp] != -1)
110  {
111  if (semi[cmp] > semi[tmp])
112  cmp = tmp;
113  tmp = ancestor[tmp];
114  }
115  return cmp;
116  }
117 
118 
119  template < typename CFGFilterFunction > void TemplatedDominatorTree <
120  CFGFilterFunction >::init()
121  {
122  semi.clear();
123  idom.clear();
124  ancestor.clear();
125  dfsParent.clear();
126  buckets.clear();
127 
128  }
129 
130 #ifdef DEBUG
131  template < typename CFGFilterFunction > void TemplatedDominatorTree <
133  CFGFilterFunction >::calculateImmediateDominators()
134  {
135  // do the bottom up part of calculating the semidominators
136  // cout << "calculation semidominators"<<endl;;
137  std::cout << "init:"<<std::endl;
138  printInfo();
139  std::cout <<std::endl;
140  for (int i = idToNode.size() - 1; i > 0; i--)
141  {
142  std::cout <<"dfs#"<<i<<std::endl;
143  printInfo();
144  std::cout<<std::endl;
145  // get the correct defs parent
146  int dfsP = dfsParent[i];
147 
148  // get current node from dfs-number
149  VirtualCFG::FilteredCFGNode < CFGFilterFunction > current = idToNode[i];
150  // cout <<"processing: \""<<current.toString()<<"\""<<endl;
151 
152  // for all predecessors of the current node
153  std::vector < VirtualCFG::FilteredCFGEdge < CFGFilterFunction > >inEdges =
154  getDirectionModifiedInEdges(current);
155  for (unsigned int j = 0; j < inEdges.size(); j++)
156  {
157  int nodeID = nodeToIdMap[source(inEdges[j])];
158  std::cout <<"v="<<nodeID<<std::endl;
159  // get the smallest possible semidom from that dfs-subtree
160  int possiblySmallestSemiDom = eval(nodeID);
161  std::cout <<"u=EVAL("<<nodeID<<")="<<possiblySmallestSemiDom<<std::endl;
162  std::cout <<"semi("<<possiblySmallestSemiDom<<")="<<semi[possiblySmallestSemiDom]<<" < semi("<<i<<")="<<semi[i];
163  if (semi[possiblySmallestSemiDom] < semi[i])
164  {
165  std::cout <<" -> semi("<<i<<")="<<semi[possiblySmallestSemiDom];
166  semi[i] = semi[possiblySmallestSemiDom];
167  }
168  std::cout <<std::endl;
169  }
170  // add this node to the list of nodes controlled by its
171  // semidomniator
172  std::cout <<"add "<<i<<" to bucket semi["<<i<<"]"<<semi[i]<<std::endl;
173  buckets[semi[i]].insert(i);
174  std::cout <<"link "<<dfsP<<","<<i<<std::endl;
175  link(dfsP, i);
176 
177  // for all nodes in the bucket of this nodes parent
178  for (std::set < int >::iterator j = buckets[dfsP].begin();
179  j != buckets[dfsP].end(); j++)
180  {
181  int tmpNodeID = eval(*j);
182 
183  // semi[(*j) is dfsParent
184  if (semi[tmpNodeID] < dfsP)
185  idom[(*j)] = tmpNodeID;
186  else
187  idom[(*j)] = dfsP;
188  }
189  printInfo();
190 
191  buckets[dfsP].clear();
192  }
193  for (unsigned int i = 1; i < idToNode.size(); i++)
194  {
195  if (idom[i] != semi[i])
196  {
197  idom[i] = idom[idom[i]];
198  }
199  }
200  idom[0] = 0;
201  std::cout << "Dominators:" << std::endl;
202  for (unsigned int i = 0; i < idToNode.size(); i++)
203  {
204  std::cout << ">" << idToNode[i].toString() << "<: " << idom[i] << std::endl;
205  }
206  }
207 #else
208  template < typename CFGFilterFunction > void TemplatedDominatorTree <
209  CFGFilterFunction >::calculateImmediateDominators()
210  {
211  // do the bottom up part of calculating the semidominators
212  for (int i = idToNode.size() - 1; i > 0; i--)
213  {
214  // get the correct defs parent
215  int dfsP = dfsParent[i];
216 
217  // get current node from dfs-number
218  VirtualCFG::FilteredCFGNode < CFGFilterFunction > current = idToNode[i];
219 
220  // for all predecessors of the current node
221  std::vector < VirtualCFG::FilteredCFGEdge < CFGFilterFunction > >inEdges =
222  this->getDirectionModifiedInEdges(current);
223  for (unsigned int j = 0; j < inEdges.size(); j++)
224  {
225  int nodeID = nodeToIdMap[this->source(inEdges[j])];
226 
227  // get the smallest possible semidom from that dfs-subtree
228  int possiblySmallestSemiDom = eval(nodeID);
229  if (semi[possiblySmallestSemiDom] < semi[i])
230  {
231  semi[i] = semi[possiblySmallestSemiDom];
232  }
233  }
234  // add this node to the list of nodes controlled by its
235  // semidomniator
236  buckets[semi[i]].insert(i);
237  link(dfsP, i);
238 
239  // for all nodes in the bucket of this nodes parent
240  for (std::set < int >::iterator j = buckets[dfsP].begin();
241  j != buckets[dfsP].end(); j++)
242  {
243  int tmpNodeID = eval(*j);
244 
245  // semi[(*j) is dfsParent
246  if (semi[tmpNodeID] < dfsP)
247  idom[(*j)] = tmpNodeID;
248  else
249  idom[(*j)] = dfsP;
250  }
251 
252  buckets[dfsP].clear();
253  }
254  for (unsigned int i = 1; i < idToNode.size(); i++)
255  {
256  if (idom[i] != semi[i])
257  {
258  idom[i] = idom[idom[i]];
259  }
260  }
261  idom[0] = 0;
262  }
263 #endif
264 
265 }