ROSE  0.11.39.0
Dominance.h
1 // [Robb P Matzke 2017-06-29]: This entire API has been deprecated in favor of using the control flow graphs in
2 // Rose::BinaryAnalysis::Partitioner2 and the dominance algorithms in Sawyer::Container::Algorithm.
3 #ifndef ROSE_BinaryAnalysis_Dominance_H
4 #define ROSE_BinaryAnalysis_Dominance_H
5 #include <featureTests.h>
6 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
7 
8 #include <Rose/BinaryAnalysis/ControlFlow.h>
9 
10 #include <boost/graph/depth_first_search.hpp>
11 #include <boost/graph/reverse_graph.hpp>
12 
13 namespace Rose {
14 namespace BinaryAnalysis {
15 
16 class Dominance {
17 public:
18  Dominance(): debug(NULL) {}
19 
20  typedef boost::adjacency_list<boost::setS, /* edge storage */
21  boost::vecS, /* vertex storage */
22  boost::bidirectionalS,
23  boost::property<boost::vertex_name_t, SgAsmBlock*>
24  > Graph;
25 
26  template<class ControlFlowGraph>
27  struct RelationMap: public std::vector<typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor> {
28  };
29 
30 public:
31  void clear_ast(SgNode *ast) ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
32 
33  template<class DominanceGraph>
34  void apply_to_ast(const DominanceGraph &idg)
35  ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
36 
37  template<class ControlFlowGraph>
38  void apply_to_ast(const ControlFlowGraph &cfg, const RelationMap<ControlFlowGraph> &relation_map)
39  ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
40 
41  template<class DominanceGraph>
42  void cache_vertex_descriptors(const DominanceGraph&)
43  ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
44 
45  bool is_consistent(SgNode *ast, std::set<SgAsmBlock*> *bad_blocks=NULL)
46  ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
47 
48 public:
49  template<class ControlFlowGraph>
50  RelationMap<ControlFlowGraph>
51  build_idom_relation_from_cfg(const ControlFlowGraph &cfg,
52  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start)
53  ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
54 
55  template<class ControlFlowGraph>
56  void build_idom_relation_from_cfg(const ControlFlowGraph &cfg,
57  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
58  RelationMap<ControlFlowGraph> &idom/*out*/)
59  ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
60 
61  template<class ControlFlowGraph>
62  RelationMap<ControlFlowGraph>
63  build_postdom_relation_from_cfg(const ControlFlowGraph &cfg,
64  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start)
65  ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
66 
67  template<class ControlFlowGraph>
68  RelationMap<ControlFlowGraph>
69  build_postdom_relation_from_cfg(const ControlFlowGraph &cfg,
70  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
71  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor stop)
72  ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
73 
74  template<class ControlFlowGraph>
75  void build_postdom_relation_from_cfg(const ControlFlowGraph &cfg,
76  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
77  RelationMap<ControlFlowGraph> &idom/*out*/)
78  ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
79 
80  template<class ControlFlowGraph>
81  void build_postdom_relation_from_cfg(const ControlFlowGraph &cfg,
82  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
83  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor stop,
84  RelationMap<ControlFlowGraph> &idom/*out*/)
85  ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
86 
87 public:
88  template<class DominanceGraph, class ControlFlowGraph>
89  DominanceGraph build_idom_graph_from_cfg(const ControlFlowGraph &cfg,
90  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start)
91  ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
92 
93  template<class ControlFlowGraph, class DominanceGraph>
94  void build_idom_graph_from_cfg(const ControlFlowGraph &cfg,
95  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
96  DominanceGraph &dg/*out*/)
97  ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
98 
99  template<class DominanceGraph, class ControlFlowGraph>
100  DominanceGraph build_postdom_graph_from_cfg(const ControlFlowGraph &cfg,
101  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start)
102  ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
103 
104  template<class DominanceGraph, class ControlFlowGraph>
105  DominanceGraph build_postdom_graph_from_cfg(const ControlFlowGraph &cfg,
106  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
107  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor stop)
108  ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
109 
110  template<class ControlFlowGraph, class DominanceGraph>
111  void build_postdom_graph_from_cfg(const ControlFlowGraph &cfg,
112  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
113  DominanceGraph &pdg/*out*/)
114  ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
115 
116  template<class ControlFlowGraph, class DominanceGraph>
117  void build_postdom_graph_from_cfg(const ControlFlowGraph &cfg,
118  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
119  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor stop,
120  DominanceGraph &pdg/*out*/)
121  ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
122 
123 public:
124  template<class DominanceGraph, class ControlFlowGraph>
125  DominanceGraph build_graph_from_relation(const ControlFlowGraph &cfg,
126  const RelationMap<ControlFlowGraph> &relmap)
127  ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
128 
129  template<class ControlFlowGraph, class DominanceGraph>
130  void build_graph_from_relation(const ControlFlowGraph &cfg,
131  const RelationMap<ControlFlowGraph> &relmap,
132  DominanceGraph &dg/*out*/)
133  ROSE_DEPRECATED("Use Sawyer::Container::Algorithm::graphDominators");
134 
135  void set_debug(FILE *debug) { this->debug = debug; }
136 
137  FILE *get_debug() const { return debug; }
138 
139 protected:
140  FILE *debug;
141 };
142 
143 /******************************************************************************************************************************
144  * Function templates for methods that operate on the AST
145  ******************************************************************************************************************************/
146 
147 template<class DominanceGraph>
148 void
149 Dominance::apply_to_ast(const DominanceGraph &idg)
150 {
151  if (debug)
152  fprintf(debug, "Rose::BinaryAnalysis::Dominance::apply_to_ast:\n");
153 
154  typename boost::graph_traits<DominanceGraph>::edge_iterator ei, ei_end;
155  for (boost::tie(ei, ei_end)=edges(idg); ei!=ei_end; ++ei) {
156  SgAsmBlock *dom_block = get(boost::vertex_name, idg, source(*ei, idg));
157  SgAsmBlock *sub_block = get(boost::vertex_name, idg, target(*ei, idg));
158  if (debug) {
159  fprintf(debug, " edge (d,s) = (%" PRIuPTR ",%" PRIuPTR ") = (0x%08" PRIx64 ", 0x%08" PRIx64 ")\n",
160  source(*ei, idg), target(*ei, idg), dom_block->get_address(), sub_block->get_address());
161  }
162  sub_block->set_immediate_dominator(dom_block);
163  }
164 }
165 
166 template<class ControlFlowGraph>
167 void
168 Dominance::apply_to_ast(const ControlFlowGraph &cfg,
169  const RelationMap<ControlFlowGraph> &idom)
170 {
171  typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor CFG_Vertex;
172 
173  assert(idom.size()<=num_vertices(cfg));
174  for (size_t subordinate=0; subordinate<idom.size(); subordinate++) {
175  SgAsmBlock *sub_block = get(boost::vertex_name, cfg, (CFG_Vertex)subordinate);
176  if (sub_block && idom[subordinate]!=boost::graph_traits<ControlFlowGraph>::null_vertex()) {
177  CFG_Vertex dominator = idom[subordinate];
178  SgAsmBlock *dom_block = get(boost::vertex_name, cfg, dominator);
179  sub_block->set_immediate_dominator(dom_block);
180  }
181  }
182 }
183 
184 template<class DominanceGraph>
185 void
186 Dominance::cache_vertex_descriptors(const DominanceGraph &dg)
187 {
188  typename boost::graph_traits<DominanceGraph>::vertex_iterator vi, vi_end;
189  for (boost::tie(vi, vi_end)=vertices(dg); vi!=vi_end; ++vi) {
190  SgAsmBlock *block = get(boost::vertex_name, dg, *vi);
191  if (block)
192  block->set_cached_vertex(*vi);
193  }
194 }
195 
196 /******************************************************************************************************************************
197  * Function templates for immediate dominators
198  ******************************************************************************************************************************/
199 
200 
201 template<class ControlFlowGraph, class DominanceGraph>
202 void
203 Dominance::build_idom_graph_from_cfg(const ControlFlowGraph &cfg,
204  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
205  DominanceGraph &result)
206 {
207  RelationMap<ControlFlowGraph> idoms;
208  build_idom_relation_from_cfg(cfg, start, idoms);
209  build_graph_from_relation(cfg, idoms, result);
210 }
211 
212 template<class DominanceGraph, class ControlFlowGraph>
213 DominanceGraph
214 Dominance::build_idom_graph_from_cfg(const ControlFlowGraph &cfg,
215  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start)
216 {
217  DominanceGraph dg;
218  build_idom_graph_from_cfg(cfg, start, dg);
219  return dg;
220 }
221 
222 template<class ControlFlowGraph>
223 Dominance::RelationMap<ControlFlowGraph>
224 Dominance::build_idom_relation_from_cfg(const ControlFlowGraph &cfg,
225  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start)
226 {
227  RelationMap<ControlFlowGraph> idom;
228  build_idom_relation_from_cfg(cfg, start, idom);
229  return idom;
230 }
231 
232 /* Loosely based on an algorithm from Rice University known to be O(n^2) where n is the number of vertices in the control flow
233  * subgraph connected to the start vertex. According to the Rice paper, their algorithm outperforms Lengauer-Tarjan on
234  * typicall control flow graphs even though asymptotically, Lengauer-Tarjan is better. The Rice algorithm is also much
235  * simpler, as evidenced below.
236  *
237  * I've added a few minor optimizations:
238  * (1) reverse post-order dfs is calculated once rather than each time through the loop. Rice's analysis indicates that
239  * they also made this optimization, although their listed algorithm does not show it.
240  * (2) the first processed predecessor of the vertex under consideration is determined in the same loop that processes
241  * the other predecessors, while in the listed algorithm this was a separate operation.
242  * (3) self loops in the control flow graph are not processed, since they don't contribute to the dominance relation.
243  * (4) undefined state for idom(x) is represented by idom(x)==x.
244  * (5) nodes are labeled in reverse order from Rice, but traversed in the same order. This simplifies the code a bit
245  * because the vertices are traversed according to the "flowlist" vector, and the index into the "flowlist" vector
246  * can serve as the node label.
247  *
248  * The set of dominators of vertex v, namely dom(v), is represented as a linked list stored as an array indexed by vertex
249  * number. That is
250  * dom(v) = { v, idom(v), idom(idom(v)), ..., start }
251  *
252  * is stored in the idom array as:
253  *
254  * dom(v) = { v, idom[v], idom[idom[v]], ..., start }
255  *
256  * This representation, combined with the fact that:
257  *
258  * a ELEMENT_OF dom(v) implies dom(a) SUBSET_OF dom(v)
259  *
260  * allows us to perform intersection by simply walking the two sorted lists until we find an element in common, and including
261  * that element an all subsequent elements in the intersection result. The idom array uses the flow-list vertex numbering
262  * produced by a post-order visitor of a depth-first search, and the nodes are processed from highest to lowest.
263  */
264 template<class ControlFlowGraph>
265 void
266 Dominance::build_idom_relation_from_cfg(const ControlFlowGraph &cfg,
267  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
268  RelationMap<ControlFlowGraph> &result)
269 {
270  typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor CFG_Vertex;
271 
272  struct debug_dom_set {
273  debug_dom_set(FILE *debug, size_t vertex_i, size_t idom_i,
274  const std::vector<size_t> &domsets, const std::vector<CFG_Vertex> &flowlist) {
275  if (debug) {
276  fprintf(debug, "{ #%" PRIuPTR "(%" PRIuPTR ")", vertex_i, flowlist[vertex_i]);
277  for (size_t d=idom_i; d!=vertex_i; vertex_i=d, d=domsets[d])
278  fprintf(debug, " #%" PRIuPTR "(%" PRIuPTR ")", d, flowlist[d]);
279  fprintf(debug, " }");
280  }
281  }
282  };
283 
284  if (debug) {
285  fprintf(debug, "Rose::BinaryAnalysis::Dominance::build_idom_relation_from_cfg: starting at vertex %" PRIuPTR "\n", start);
286  SgAsmBlock *block = get(boost::vertex_name, cfg, start);
287  SgAsmFunction *func = block ? block->get_enclosing_function() : NULL;
288  if (func) {
289  fprintf(debug, " Vertex %" PRIuPTR " is %s block of", start, func->get_entry_block()==block?"the entry":"a");
290  if (func->get_name().empty()) {
291  fprintf(debug, " an unnamed function");
292  } else {
293  fprintf(debug, " function <%s>", func->get_name().c_str());
294  }
295  fprintf(debug, " at 0x%08" PRIx64 "\n", func->get_entry_va());
296  }
297  }
298 
299  /* Initialize */
300  std::vector<size_t> rflowlist; /* reverse mapping; flowlist[i]==v implies rflowlist[v]==i */
301  std::vector<CFG_Vertex> flowlist = ControlFlow().flow_order(cfg, start, &rflowlist);
302  std::vector<size_t> idom(flowlist.size());
303  for (size_t i=0; i<flowlist.size(); i++)
304  idom[i] = i; /* idom[i]==i implies idom[i] is unknown */
305 
306  if (debug) {
307  fprintf(debug, " CFG:\n");
308  typename boost::graph_traits<ControlFlowGraph>::vertex_iterator vi, vi_end;
309  for (boost::tie(vi, vi_end)=vertices(cfg); vi!=vi_end; ++vi) {
310  SgAsmBlock *block = get(boost::vertex_name, cfg, *vi);
311  fprintf(debug, " %" PRIuPTR " 0x%08" PRIx64 " --> {", (size_t)(*vi), block?block->get_address():0);
312  typename boost::graph_traits<ControlFlowGraph>::out_edge_iterator ei, ei_end;
313  for (boost::tie(ei, ei_end)=out_edges(*vi, cfg); ei!=ei_end; ++ei) {
314  fprintf(debug, " %" PRIuPTR "", (size_t)target(*ei, cfg));
315  }
316  fprintf(debug, " }\n");
317  }
318 
319  fprintf(debug, " Note: notation #M(N) means CFG vertex N at position M in the flow list.\n");
320  fprintf(debug, " Flowlist: {");
321  for (size_t i=0; i<flowlist.size(); i++) {
322  fprintf(debug, " #%" PRIuPTR "(%" PRIuPTR ")", i, (size_t)flowlist[i]);
323  assert((size_t)flowlist[i]<rflowlist.size());
324  assert(rflowlist[flowlist[i]]==i);
325  }
326  fprintf(debug, " }\n");
327  }
328 
329  /* Iterative data flow */
330  bool changed;
331  do {
332  changed = false;
333  if (debug)
334  fprintf(debug, " Next pass through vertices...\n");
335  for (size_t vertex_i=0; vertex_i<flowlist.size(); vertex_i++) {
336  CFG_Vertex vertex = flowlist[vertex_i];
337  if (debug) {
338  fprintf(debug, " vertex #%" PRIuPTR "(%" PRIuPTR ")", (size_t)vertex_i, (size_t)vertex);
339  if (vertex==start) {
340  fprintf(debug, " [skipping start vertex]\n");
341  } else {
342  fprintf(debug, " dominators are ");
343  debug_dom_set(debug, vertex_i, idom[vertex_i], idom, flowlist);
344  fprintf(debug, "\n");
345  }
346  }
347 
348  if (vertex!=start) {
349  typename boost::graph_traits<ControlFlowGraph>::in_edge_iterator pi, pi_end; /*predecessors*/
350  size_t new_idom = vertex_i; /*undefined for now*/
351  for (boost::tie(pi, pi_end)=in_edges(vertex, cfg); pi!=pi_end; ++pi) {
352  CFG_Vertex predecessor = source(*pi, cfg);
353  assert(predecessor>=0 && predecessor<rflowlist.size());
354  size_t predecessor_i = rflowlist[predecessor];
355  if (debug)
356  fprintf(debug, " pred #%zd(%" PRIuPTR ")", (size_t)predecessor_i, (size_t)predecessor);
357 
358  /* It's possible that the predecessor lies outside the part of the CFG connected to the entry node. We
359  * should not consider those predecessors. */
360  if (predecessor!=vertex && predecessor_i!=boost::graph_traits<ControlFlowGraph>::null_vertex()) {
361  if (predecessor==start) {
362  new_idom = predecessor_i;
363  if (debug) {
364  fprintf(debug, "; new doms of #%" PRIuPTR "(%" PRIuPTR ") are ", vertex_i, vertex);
365  debug_dom_set(debug, vertex_i, predecessor_i, idom, flowlist);
366  }
367  } else if (idom[predecessor_i]!=predecessor_i) {
368  if (new_idom==vertex_i) {
369  new_idom = predecessor_i;
370  if (debug) {
371  fprintf(debug, "; new doms of #%" PRIuPTR "(%" PRIuPTR ") are ", vertex_i, vertex);
372  debug_dom_set(debug, vertex_i, predecessor_i, idom, flowlist);
373  }
374  } else {
375  if (debug) {
376  fprintf(debug, "; new doms of #%" PRIuPTR "(%" PRIuPTR ") are intersect(", vertex_i, vertex);
377  debug_dom_set(debug, vertex_i, new_idom, idom, flowlist);
378  fprintf(debug, ", ");
379  debug_dom_set(debug, vertex_i, predecessor_i, idom, flowlist);
380  }
381  size_t f1=new_idom, f2=predecessor_i;
382  while (f1!=f2) {
383  while (f1 > f2)
384  f1 = idom[f1];
385  while (f2 > f1)
386  f2 = idom[f2];
387  }
388  new_idom = f1;
389  if (debug) {
390  fprintf(debug, ") = ");
391  debug_dom_set(debug, vertex_i, new_idom, idom, flowlist);
392  }
393  }
394  }
395  }
396  if (debug)
397  fprintf(debug, "\n");
398  }
399  if (idom[vertex_i]!=new_idom) {
400  idom[vertex_i] = new_idom;
401  changed = true;
402  }
403  }
404  }
405  } while (changed);
406 
407  /* Build result relation */
408  result.clear();
409  result.resize(num_vertices(cfg), boost::graph_traits<ControlFlowGraph>::null_vertex());
410  for (size_t i=0; i<flowlist.size(); i++) {
411  if (idom[i]!=i)
412  result[flowlist[i]] = flowlist[idom[i]];
413  }
414 
415  if (debug) {
416  fprintf(debug, " Final dom sets:\n");
417  for (size_t vertex_i=0; vertex_i<flowlist.size(); vertex_i++) {
418  CFG_Vertex vertex = flowlist[vertex_i];
419  fprintf(debug, " #%" PRIuPTR "(%" PRIuPTR ") has dominators ", (size_t)vertex_i, (size_t)vertex);
420  debug_dom_set(debug, vertex_i, idom[vertex_i], idom, flowlist);
421  fprintf(debug, "\n");
422  }
423  fprintf(debug, " Final result:\n");
424  for (size_t i=0; i<result.size(); i++) {
425  if (result[i]==boost::graph_traits<ControlFlow::Graph>::null_vertex()) {
426  fprintf(debug, " CFG vertex %" PRIuPTR " has no immediate dominator\n", i);
427  } else {
428  fprintf(debug, " CFG vertex %" PRIuPTR " has immediate dominator %" PRIuPTR "\n", i, result[i]);
429  }
430  }
431  }
432 }
433 
434 
435 
436 
437 
438 /******************************************************************************************************************************
439  * Function templates for post dominators
440  ******************************************************************************************************************************/
441 
442 template<class ControlFlowGraph, class DominanceGraph>
443 void
444 Dominance::build_postdom_graph_from_cfg(const ControlFlowGraph &cfg,
445  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
446  DominanceGraph &result)
447 {
448  RelationMap<ControlFlowGraph> pdoms;
449  build_postdom_relation_from_cfg(cfg, start, pdoms);
450  build_graph_from_relation(cfg, pdoms, result);
451 }
452 
453 template<class ControlFlowGraph, class DominanceGraph>
454 void
455 Dominance::build_postdom_graph_from_cfg(const ControlFlowGraph &cfg,
456  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
457  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor stop,
458  DominanceGraph &result)
459 {
460  RelationMap<ControlFlowGraph> pdoms;
461  build_postdom_relation_from_cfg(cfg, start, stop, pdoms);
462  build_graph_from_relation(cfg, pdoms, result);
463 }
464 
465 template<class DominanceGraph, class ControlFlowGraph>
466 DominanceGraph
467 Dominance::build_postdom_graph_from_cfg(const ControlFlowGraph &cfg,
468  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start)
469 {
470  DominanceGraph dg;
471  build_postdom_graph_from_cfg(cfg, start, dg);
472  return dg;
473 }
474 
475 template<class DominanceGraph, class ControlFlowGraph>
476 DominanceGraph
477 Dominance::build_postdom_graph_from_cfg(const ControlFlowGraph &cfg,
478  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
479  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor stop)
480 {
481  DominanceGraph dg;
482  build_postdom_graph_from_cfg(cfg, start, stop, dg);
483  return dg;
484 }
485 
486 template<class ControlFlowGraph>
487 Dominance::RelationMap<ControlFlowGraph>
488 Dominance::build_postdom_relation_from_cfg(const ControlFlowGraph &cfg,
489  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start)
490 {
491  RelationMap<ControlFlowGraph> pdom;
492  build_postdom_relation_from_cfg(cfg, start, pdom);
493  return pdom;
494 }
495 
496 template<class ControlFlowGraph>
497 Dominance::RelationMap<ControlFlowGraph>
498 Dominance::build_postdom_relation_from_cfg(const ControlFlowGraph &cfg,
499  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
500  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor stop)
501 {
502  RelationMap<ControlFlowGraph> pdom;
503  build_postdom_relation_from_cfg(cfg, start, stop, pdom);
504  return pdom;
505 }
506 
507 template<class ControlFlowGraph>
508 void
509 Dominance::build_postdom_relation_from_cfg(const ControlFlowGraph &cfg,
510  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
511  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor stop,
512  RelationMap<ControlFlowGraph> &result)
513 {
514  /* Post dominance is the same as doing dominance, but on a reversed CFG, using the stop vertex as the starting point. */
515  if (debug)
516  fprintf(debug, " Calling build_idom_relation_from_cfg() on reversed CFG...\n");
517  typedef typename boost::reverse_graph<ControlFlowGraph> ReversedControlFlowGraph;
518  ReversedControlFlowGraph rcfg(cfg);
519  RelationMap<ReversedControlFlowGraph> rrelation;
520  build_idom_relation_from_cfg(rcfg, stop, rrelation);
521  result.assign(rrelation.begin(), rrelation.end());
522 }
523 
524 template<class ControlFlowGraph>
525 void
526 Dominance::build_postdom_relation_from_cfg(const ControlFlowGraph &cfg,
527  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
528  RelationMap<ControlFlowGraph> &result)
529 {
530  if (debug) {
531  fprintf(debug, "Rose::BinaryAnalysis::Dominance::build_postdom_relation_from_cfg: starting at vertex %" PRIuPTR "\n", start);
532  SgAsmBlock *block = get(boost::vertex_name, cfg, start);
533  SgAsmFunction *func = block ? block->get_enclosing_function() : NULL;
534  if (func) {
535  fprintf(debug, " Vertex %" PRIuPTR " is %s block of", start, func->get_entry_block()==block?"the entry":"a");
536  if (func->get_name().empty()) {
537  fprintf(debug, " an unnamed function");
538  } else {
539  fprintf(debug, " function <%s>", func->get_name().c_str());
540  }
541  fprintf(debug, " at 0x%08" PRIx64 "\n", func->get_entry_va());
542  }
543  }
544 
545  /* Does the graph have more than one return block? By "return", we mean any block whose control flow successor is possibly
546  * outside the start node's function. See ControlFlow::return_blocks(). */
547  typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor CFG_Vertex;
548  std::vector<CFG_Vertex> retblocks = ControlFlow().return_blocks(cfg, start);
549  if (1==retblocks.size()) {
550  if (debug)
551  fprintf(debug, " CFG has unique exit vertex %" PRIuPTR ", block 0x%08" PRIx64 "\n",
552  retblocks[0],
553  get(boost::vertex_name, cfg, retblocks[0])->get_address());
554  build_postdom_relation_from_cfg(cfg, start, retblocks[0], result);
555  } else if (0==retblocks.size()) {
556  // This can happen for a function like "void f() { while(1); }", or the assembly code
557  // f: jmp f
558  // It can also happen for functions with more than one basic block as long as every basic block branches to
559  // another basic block in the same function. Post-dominance is defined in terms of a stop node (i.e., function return,
560  // HLT instruction, etc), but such a function has no stop node.
561  if (debug)
562  fprintf(debug, " CFG has no exit or terminal vertex; post-dominance cannot be calculated\n");
563  result.insert(result.begin(), num_vertices(cfg), boost::graph_traits<ControlFlowGraph>::null_vertex());
564  } else {
565  // Create a temporary unique exit/halt vertex and make all the others point to it.
566  ControlFlowGraph cfg_copy = cfg; /* we need our own copy to modify */
567  assert(!retblocks.empty());
568  CFG_Vertex unique_exit = add_vertex(cfg_copy);
569  put(boost::vertex_name, cfg_copy, unique_exit, (SgAsmBlock*)0); /* vertex has no basic block */
570  for (size_t i=0; i<retblocks.size(); i++)
571  add_edge(retblocks[i], unique_exit, cfg_copy);
572  if (debug)
573  fprintf(debug, " CFG has %" PRIuPTR " exit blocks. Added unique exit vertex %" PRIuPTR "\n", retblocks.size(), unique_exit);
574 
575  // Perform the post dominance on this new CFG using the unique exit vertex.
576  build_postdom_relation_from_cfg(cfg_copy, start, unique_exit, result);
577 
578  // Remove the unique exit vertex from the returned relation
579  assert(unique_exit+1==num_vertices(cfg_copy));
580  result.pop_back();
581  for (size_t i=0; i<result.size(); ++i) {
582  if (result[i]>=result.size())
583  result[i] = boost::graph_traits<ControlFlowGraph>::null_vertex();
584  }
585  }
586 
587  if (debug) {
588  fprintf(debug, " Final result:\n");
589  for (size_t i=0; i<result.size(); i++) {
590  if (result[i]==boost::graph_traits<ControlFlowGraph>::null_vertex()) {
591  fprintf(debug, " CFG vertex %" PRIuPTR " has no immediate post dominator\n", i);
592  } else {
593  fprintf(debug, " CFG vertex %" PRIuPTR " has immediate post dominator %" PRIuPTR "\n", i, result[i]);
594  }
595  }
596  }
597 }
598 
599 
600 
601 
602 /******************************************************************************************************************************
603  * Function templates for miscellaneous methods
604  ******************************************************************************************************************************/
605 
606 template<class DominanceGraph, class ControlFlowGraph>
607 DominanceGraph
608 Dominance::build_graph_from_relation(const ControlFlowGraph &cfg,
609  const RelationMap<ControlFlowGraph> &relmap)
610 {
611  DominanceGraph g;
612  build_graph_from_relation(cfg, relmap, g);
613  return g;
614 }
615 
616 template<class ControlFlowGraph, class DominanceGraph>
617 void
618 Dominance::build_graph_from_relation(const ControlFlowGraph &cfg,
619  const RelationMap<ControlFlowGraph> &relmap,
620  DominanceGraph &dg/*out*/)
621 {
622  typedef typename boost::graph_traits<DominanceGraph>::vertex_descriptor D_Vertex;
623  typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor CFG_Vertex;
624 
625  if (debug) {
626  fprintf(debug, "Rose::BinaryAnalysis::Dominance::build_graph_from_relation:\n");
627  fprintf(debug, " building from this relation:\n");
628  for (size_t i=0; i<relmap.size(); i++) {
629  if (relmap[i]==boost::graph_traits<ControlFlowGraph>::null_vertex()) {
630  fprintf(debug, " CFG vertex %" PRIuPTR " has no immediate dominator\n", i);
631  } else {
632  fprintf(debug, " CFG vertex %" PRIuPTR " has immediate dominator %" PRIuPTR "\n", i, relmap[i]);
633  }
634  }
635  }
636 
637  dg.clear();
638  typename boost::graph_traits<ControlFlowGraph>::vertex_iterator vi, vi_end;
639  for (boost::tie(vi, vi_end)=vertices(cfg); vi!=vi_end; vi++) {
640  D_Vertex v = add_vertex(dg);
641  assert(v==*vi); /* because relmap[] refers to CFG vertices; otherwise we need to map them */
642  SgAsmBlock *block = get(boost::vertex_name, cfg, *vi);
643  put(boost::vertex_name, dg, v, block);
644  }
645  for (boost::tie(vi, vi_end)=vertices(cfg); vi!=vi_end; vi++) {
646  CFG_Vertex subordinate = *vi;
647  CFG_Vertex dominator = relmap[subordinate];
648  if (dominator!=boost::graph_traits<ControlFlowGraph>::null_vertex()) {
649  if (debug)
650  fprintf(debug, " adding edge (d,s) = (%" PRIuPTR ",%" PRIuPTR ")\n", dominator, subordinate);
651  add_edge(dominator, subordinate, dg);
652  }
653  }
654 }
655 
656 } // namespace
657 } // namespace
658 
659 #endif
660 #endif
SgAsmBlock
Instruction basic block.
Definition: binaryInstruction.C:4324
SgAsmBlock::set_cached_vertex
void set_cached_vertex(size_t)
Property: Cached vertex for control flow graphs.
SgAsmFunction::get_entry_block
SgAsmBlock * get_entry_block() const
Function entry basic block.
std
STL namespace.
SgAsmFunction
Represents a synthesized function.
Definition: binaryInstruction.C:3892
Rose
Main namespace for the ROSE library.
Definition: BinaryTutorial.dox:3
Sawyer
Name space for the entire library.
Definition: FeasiblePath.h:787
SgAsmBlock::set_immediate_dominator
void set_immediate_dominator(SgAsmBlock *)
Property: Holds the immediate dominator block in the control flow graph.
SgAsmFunction::get_name
const std::string & get_name() const
Property: Name.
SgNode
This class represents the base class for all IR nodes within Sage III.
Definition: Cxx_Grammar.h:9507
SgAsmBlock::get_enclosing_function
SgAsmFunction * get_enclosing_function() const
Returns the function that owns this block.
SgAsmFunction::get_entry_va
rose_addr_t get_entry_va() const
Property: Primary entry address.
SgAsmStatement::get_address
rose_addr_t get_address() const
Property: Starting virtual address.
Generated on Mon Jun 28 2021 04:27:45 for ROSE by   doxygen 1.8.10