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