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