ROSE: BinaryDominance.h Source File

00001 #ifndef ROSE_BinaryAnalysis_Dominance_H
00002 #define ROSE_BinaryAnalysis_Dominance_H
00003 
00004 #include "BinaryControlFlow.h"
00005 
00006 #include <boost/graph/depth_first_search.hpp>
00007 #include <boost/graph/reverse_graph.hpp>
00008 
00009 namespace BinaryAnalysis {
00010 
00093     class Dominance {
00094     public:
00095         Dominance(): debug(NULL) {}
00096 
00129         typedef boost::adjacency_list<boost::setS,      /* edge storage */
00130                                       boost::vecS,      /* vertex storage */
00131                                       boost::bidirectionalS,
00132                                       boost::property<boost::vertex_name_t, SgAsmBlock*>
00133                                      > Graph;
00134 
00148         template<class ControlFlowGraph>
00149         struct RelationMap: public std::vector<typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor> {
00150         };
00151 
00152 
00153 
00154         /**********************************************************************************************************************
00155          *                                      Methods that operate on the AST
00156          **********************************************************************************************************************/
00157     public:
00158 
00166         void clear_ast(SgNode *ast);
00167 
00168 
00182         template<class DominanceGraph>
00183         void apply_to_ast(const DominanceGraph &idg);
00184 
00185         template<class ControlFlowGraph>
00186         void apply_to_ast(const ControlFlowGraph &cfg, const RelationMap<ControlFlowGraph> &relation_map);
00201         template<class DominanceGraph>
00202         void cache_vertex_descriptors(const DominanceGraph&);
00203 
00204 
00221         bool is_consistent(SgNode *ast, std::set<SgAsmBlock*> *bad_blocks=NULL);
00222 
00223 
00224 
00225         /**********************************************************************************************************************
00226          *                                      Methods that build relationships
00227          **********************************************************************************************************************/
00228     public:
00229 
00246         template<class ControlFlowGraph>
00247         RelationMap<ControlFlowGraph>
00248         build_idom_relation_from_cfg(const ControlFlowGraph &cfg,
00249                                      typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start);
00250 
00251         template<class ControlFlowGraph>
00252         void build_idom_relation_from_cfg(const ControlFlowGraph &cfg,
00253                                           typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
00254                                           RelationMap<ControlFlowGraph> &idom/*out*/);
00272         template<class ControlFlowGraph>
00273         RelationMap<ControlFlowGraph>
00274         build_postdom_relation_from_cfg(const ControlFlowGraph &cfg,
00275                                         typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start);
00276 
00277         template<class ControlFlowGraph>
00278         void build_postdom_relation_from_cfg(const ControlFlowGraph &cfg,
00279                                              typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
00280                                              RelationMap<ControlFlowGraph> &idom/*out*/);
00285         /**********************************************************************************************************************
00286          *                                      Methods that build graphs
00287          **********************************************************************************************************************/
00288     public:
00289 
00300         template<class DominanceGraph, class ControlFlowGraph>
00301         DominanceGraph build_idom_graph_from_cfg(const ControlFlowGraph &cfg,
00302                                                  typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start);
00303 
00304         template<class ControlFlowGraph, class DominanceGraph>
00305         void build_idom_graph_from_cfg(const ControlFlowGraph &cfg,
00306                                        typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
00307                                        DominanceGraph &dg/*out*/);
00328         template<class DominanceGraph, class ControlFlowGraph>
00329         DominanceGraph build_postdom_graph_from_cfg(const ControlFlowGraph &cfg,
00330                                                     typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start);
00331 
00332         template<class ControlFlowGraph, class DominanceGraph>
00333         void build_postdom_graph_from_cfg(const ControlFlowGraph &cfg,
00334                                           typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
00335                                           DominanceGraph &pdg/*out*/);
00340         /**********************************************************************************************************************
00341          *                                      Miscellaneous methods
00342          **********************************************************************************************************************/
00343     public:
00344 
00354         template<class DominanceGraph, class ControlFlowGraph>
00355         DominanceGraph build_graph_from_relation(const ControlFlowGraph &cfg,
00356                                                  const RelationMap<ControlFlowGraph> &relmap);
00357 
00358         template<class ControlFlowGraph, class DominanceGraph>
00359         void build_graph_from_relation(const ControlFlowGraph &cfg,
00360                                        const RelationMap<ControlFlowGraph> &relmap,
00361                                        DominanceGraph &dg/*out*/);
00368         void set_debug(FILE *debug) { this->debug = debug; }
00369 
00374         FILE *get_debug() const { return debug; }
00375 
00376     protected:
00377         FILE *debug;                    
00378     };
00379 }
00380 
00381 
00382 
00383 /******************************************************************************************************************************
00384  *                              Function templates for methods that operate on the AST
00385  ******************************************************************************************************************************/
00386 
00387 template<class DominanceGraph>
00388 void
00389 BinaryAnalysis::Dominance::apply_to_ast(const DominanceGraph &idg)
00390 {
00391     if (debug)
00392         fprintf(debug, "BinaryAnalysis::Dominance::apply_to_ast:\n");
00393 
00394     typename boost::graph_traits<DominanceGraph>::edge_iterator ei, ei_end;
00395     for (boost::tie(ei, ei_end)=edges(idg); ei!=ei_end; ++ei) {
00396         SgAsmBlock *dom_block = get(boost::vertex_name, idg, source(*ei, idg));
00397         SgAsmBlock *sub_block = get(boost::vertex_name, idg, target(*ei, idg));
00398         if (debug) {
00399             fprintf(debug, "  edge (d,s) = (%zu,%zu) = (0x%08"PRIx64", 0x%08"PRIx64")\n",
00400                     source(*ei, idg), target(*ei, idg), dom_block->get_address(), sub_block->get_address());
00401         }
00402         sub_block->set_immediate_dominator(dom_block);
00403     }
00404 }
00405 
00406 template<class ControlFlowGraph>
00407 void
00408 BinaryAnalysis::Dominance::apply_to_ast(const ControlFlowGraph &cfg,
00409                                         const RelationMap<ControlFlowGraph> &idom)
00410 {
00411     typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor CFG_Vertex;
00412 
00413     assert(idom.size()<=num_vertices(cfg));
00414     for (size_t subordinate=0; subordinate<idom.size(); subordinate++) {
00415         SgAsmBlock *sub_block = get(boost::vertex_name, cfg, (CFG_Vertex)subordinate);
00416         if (sub_block && idom[subordinate]!=boost::graph_traits<ControlFlowGraph>::null_vertex()) {
00417             CFG_Vertex dominator = idom[subordinate];
00418             SgAsmBlock *dom_block = get(boost::vertex_name, cfg, dominator);
00419             sub_block->set_immediate_dominator(dom_block);
00420         }
00421     }
00422 }
00423 
00424 template<class DominanceGraph>
00425 void
00426 BinaryAnalysis::Dominance::cache_vertex_descriptors(const DominanceGraph &dg)
00427 {
00428     typename boost::graph_traits<DominanceGraph>::vertex_iterator vi, vi_end;
00429     for (boost::tie(vi, vi_end)=vertices(dg); vi!=vi_end; ++vi) {
00430         SgAsmBlock *block = get(boost::vertex_name, dg, *vi);
00431         if (block)
00432             block->set_cached_vertex(*vi);
00433     }
00434 }
00435 
00436 /******************************************************************************************************************************
00437  *                              Function templates for immediate dominators
00438  ******************************************************************************************************************************/
00439 
00440 
00441 template<class ControlFlowGraph, class DominanceGraph>
00442 void
00443 BinaryAnalysis::Dominance::build_idom_graph_from_cfg(const ControlFlowGraph &cfg,
00444                                                      typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
00445                                                      DominanceGraph &result)
00446 {
00447     RelationMap<ControlFlowGraph> idoms;
00448     build_idom_relation_from_cfg(cfg, start, idoms);
00449     build_graph_from_relation(cfg, idoms, result);
00450 }
00451 
00452 template<class DominanceGraph, class ControlFlowGraph>
00453 DominanceGraph
00454 BinaryAnalysis::Dominance::build_idom_graph_from_cfg(const ControlFlowGraph &cfg,
00455                                                      typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start)
00456 {
00457     DominanceGraph dg;
00458     build_idom_graph_from_cfg(cfg, start, dg);
00459     return dg;
00460 }
00461 
00462 template<class ControlFlowGraph>
00463 BinaryAnalysis::Dominance::RelationMap<ControlFlowGraph>
00464 BinaryAnalysis::Dominance::build_idom_relation_from_cfg(const ControlFlowGraph &cfg,
00465                                                         typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start)
00466 {
00467     RelationMap<ControlFlowGraph> idom;
00468     build_idom_relation_from_cfg(cfg, start, idom);
00469     return idom;
00470 }
00471 
00472 /* 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
00473  * subgraph connected to the start vertex.  According to the Rice paper, their algorithm outperforms Lengauer-Tarjan on
00474  * typicall control flow graphs even though asymptotically, Lengauer-Tarjan is better.  The Rice algorithm is also much
00475  * simpler, as evidenced below.
00476  *
00477  * I've added a few minor optimizations:
00478  *   (1) reverse post-order dfs is calculated once rather than each time through the loop.  Rice's analysis indicates that
00479  *       they also made this optimization, although their listed algorithm does not show it.
00480  *   (2) the first processed predecessor of the vertex under consideration is determined in the same loop that processes
00481  *       the other predecessors, while in the listed algorithm this was a separate operation.
00482  *   (3) self loops in the control flow graph are not processed, since they don't contribute to the dominance relation.
00483  *   (4) undefined state for idom(x) is represented by idom(x)==x.
00484  *   (5) nodes are labeled in reverse order from Rice, but traversed in the same order.  This simplifies the code a bit
00485  *       because the vertices are traversed according to the "flowlist" vector, and the index into the "flowlist" vector
00486  *       can serve as the node label.
00487  *
00488  * The set of dominators of vertex v, namely dom(v), is represented as a linked list stored as an array indexed by vertex
00489  * number. That is
00490  *      dom(v) = { v, idom(v), idom(idom(v)), ..., start }
00491  *
00492  * is stored in the idom array as:
00493  *
00494  *      dom(v) = { v, idom[v], idom[idom[v]], ..., start }
00495  *
00496  * This representation, combined with the fact that:
00497  *
00498  *      a ELEMENT_OF dom(v) implies dom(a) SUBSET_OF dom(v)
00499  *
00500  * allows us to perform intersection by simply walking the two sorted lists until we find an element in common, and including
00501  * that element an all subsequent elements in the intersection result.  The idom array uses the flow-list vertex numbering
00502  * produced by a post-order visitor of a depth-first search, and the nodes are processed from highest to lowest.
00503  */
00504 template<class ControlFlowGraph>
00505 void
00506 BinaryAnalysis::Dominance::build_idom_relation_from_cfg(const ControlFlowGraph &cfg,
00507                                                         typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
00508                                                         RelationMap<ControlFlowGraph> &result)
00509 {
00510     typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor CFG_Vertex;
00511 
00512     struct debug_dom_set {
00513         debug_dom_set(FILE *debug, size_t vertex_i, size_t idom_i,
00514                       const std::vector<size_t> &domsets, const std::vector<CFG_Vertex> &flowlist) {
00515             if (debug) {
00516                 fprintf(debug, "{ #%zu(%zu)", vertex_i, flowlist[vertex_i]);
00517                 for (size_t d=idom_i; d!=vertex_i; vertex_i=d, d=domsets[d])
00518                     fprintf(debug, " #%zu(%zu)", d, flowlist[d]);
00519                 fprintf(debug, " }");
00520             }
00521         }
00522     };
00523 
00524     if (debug) {
00525         fprintf(debug, "BinaryAnalysis::Dominance::build_idom_relation_from_cfg: starting at vertex %zu\n", start);
00526         SgAsmBlock *block = get(boost::vertex_name, cfg, start);
00527         SgAsmFunction *func = block ? block->get_enclosing_function() : NULL;
00528         if (func) {
00529             fprintf(debug, "  Vertex %zu is %s block of", start, func->get_entry_block()==block?"the entry":"a");
00530             if (func->get_name().empty()) {
00531                 fprintf(debug, " an unnamed function");
00532             } else {
00533                 fprintf(debug, " function <%s>", func->get_name().c_str());
00534             }
00535             fprintf(debug, " at 0x%08"PRIx64"\n", func->get_entry_va());
00536         }
00537     }
00538 
00539     /* Initialize */
00540     std::vector<size_t> rflowlist; /* reverse mapping; flowlist[i]==v implies rflowlist[v]==i */
00541     std::vector<CFG_Vertex> flowlist = ControlFlow().flow_order(cfg, start, &rflowlist);
00542     std::vector<size_t> idom(flowlist.size());
00543     for (size_t i=0; i<flowlist.size(); i++)
00544         idom[i] = i; /* idom[i]==i implies idom[i] is unknown */
00545 
00546     if (debug) {
00547         fprintf(debug, "  CFG:\n");
00548         typename boost::graph_traits<ControlFlowGraph>::vertex_iterator vi, vi_end;
00549         for (boost::tie(vi, vi_end)=vertices(cfg); vi!=vi_end; ++vi) {
00550             SgAsmBlock *block = get(boost::vertex_name, cfg, *vi);
00551             fprintf(debug, "    %zu 0x%08"PRIx64" --> {", (size_t)(*vi), block?block->get_address():0);
00552             typename boost::graph_traits<ControlFlowGraph>::out_edge_iterator ei, ei_end;
00553             for (boost::tie(ei, ei_end)=out_edges(*vi, cfg); ei!=ei_end; ++ei) {
00554                 fprintf(debug, " %zu", (size_t)target(*ei, cfg));
00555             }
00556             fprintf(debug, " }\n");
00557         }
00558 
00559         fprintf(debug, "  Note: notation #M(N) means CFG vertex N at position M in the flow list.\n");
00560         fprintf(debug, "  Flowlist: {");
00561         for (size_t i=0; i<flowlist.size(); i++) {
00562             fprintf(debug, " #%zu(%zu)", i, (size_t)flowlist[i]);
00563             assert((size_t)flowlist[i]<rflowlist.size());
00564             assert(rflowlist[flowlist[i]]==i);
00565         }
00566         fprintf(debug, " }\n");
00567     }
00568 
00569     /* Iterative data flow */
00570     bool changed;
00571     do {
00572         changed = false;
00573         if (debug)
00574             fprintf(debug, "  Next pass through vertices...\n");
00575         for (size_t vertex_i=0; vertex_i<flowlist.size(); vertex_i++) {
00576             CFG_Vertex vertex = flowlist[vertex_i];
00577             if (debug) {
00578                 fprintf(debug, "    vertex #%zu(%zu)", (size_t)vertex_i, (size_t)vertex);
00579                 if (vertex==start) {
00580                     fprintf(debug, " [skipping start vertex]\n");
00581                 } else {
00582                     fprintf(debug, " dominators are ");
00583                     debug_dom_set(debug, vertex_i, idom[vertex_i], idom, flowlist);
00584                     fprintf(debug, "\n");
00585                 }
00586             }
00587 
00588             if (vertex!=start) {
00589                 typename boost::graph_traits<ControlFlowGraph>::in_edge_iterator pi, pi_end; /*predecessors*/
00590                 size_t new_idom = vertex_i; /*undefined for now*/
00591                 for (boost::tie(pi, pi_end)=in_edges(vertex, cfg); pi!=pi_end; ++pi) {
00592                     CFG_Vertex predecessor = source(*pi, cfg);
00593                     assert(predecessor>=0 && predecessor<rflowlist.size());
00594                     size_t predecessor_i = rflowlist[predecessor];
00595                     if (debug)
00596                         fprintf(debug, "      pred #%zd(%zu)", (size_t)predecessor_i, (size_t)predecessor);
00597 
00598                     /* It's possible that the predecessor lies outside the part of the CFG connected to the entry node. We
00599                      * should not consider those predecessors. */
00600                     if (predecessor!=vertex && predecessor_i!=boost::graph_traits<ControlFlowGraph>::null_vertex()) {
00601                         if (predecessor==start) {
00602                             new_idom = predecessor_i;
00603                             if (debug) {
00604                                 fprintf(debug, "; new doms of #%zu(%zu) are ", vertex_i, vertex);
00605                                 debug_dom_set(debug, vertex_i, predecessor_i, idom, flowlist);
00606                             }
00607                         } else if (idom[predecessor_i]!=predecessor_i) {
00608                             if (new_idom==vertex_i) {
00609                                 new_idom = predecessor_i;
00610                                 if (debug) {
00611                                     fprintf(debug, "; new doms of #%zu(%zu) are ", vertex_i, vertex);
00612                                     debug_dom_set(debug, vertex_i, predecessor_i, idom, flowlist);
00613                                 }
00614                             } else {
00615                                 if (debug) {
00616                                     fprintf(debug, "; new doms of #%zu(%zu) are intersect(", vertex_i, vertex);
00617                                     debug_dom_set(debug, vertex_i, new_idom, idom, flowlist);
00618                                     fprintf(debug, ", ");
00619                                     debug_dom_set(debug, vertex_i, predecessor_i, idom, flowlist);
00620                                 }
00621                                 size_t f1=new_idom, f2=predecessor_i;
00622                                 while (f1!=f2) {
00623                                     while (f1 > f2)
00624                                         f1 = idom[f1];
00625                                     while (f2 > f1)
00626                                         f2 = idom[f2];
00627                                 }
00628                                 new_idom = f1;
00629                                 if (debug) {
00630                                     fprintf(debug, ") = ");
00631                                     debug_dom_set(debug, vertex_i, new_idom, idom, flowlist);
00632                                 }
00633                             }
00634                         }
00635                     }
00636                     if (debug)
00637                         fprintf(debug, "\n");
00638                 }
00639                 if (idom[vertex_i]!=new_idom) {
00640                     idom[vertex_i] = new_idom;
00641                     changed = true;
00642                 }
00643             }
00644         }
00645     } while (changed);
00646 
00647     /* Build result relation */
00648     result.clear();
00649     result.resize(num_vertices(cfg), boost::graph_traits<ControlFlowGraph>::null_vertex());
00650     for (size_t i=0; i<flowlist.size(); i++) {
00651         if (idom[i]!=i)
00652             result[flowlist[i]] = flowlist[idom[i]];
00653     }
00654 
00655     if (debug) {
00656         fprintf(debug, "  Final dom sets:\n");
00657         for (size_t vertex_i=0; vertex_i<flowlist.size(); vertex_i++) {
00658             CFG_Vertex vertex = flowlist[vertex_i];
00659             fprintf(debug, "    #%zu(%zu) has dominators ", (size_t)vertex_i, (size_t)vertex);
00660             debug_dom_set(debug, vertex_i, idom[vertex_i], idom, flowlist);
00661             fprintf(debug, "\n");
00662         }
00663         fprintf(debug, "  Final result:\n");
00664         for (size_t i=0; i<result.size(); i++) {
00665             if (result[i]==boost::graph_traits<ControlFlow::Graph>::null_vertex()) {
00666                 fprintf(debug, "    CFG vertex %zu has no immediate dominator\n", i);
00667             } else {
00668                 fprintf(debug, "    CFG vertex %zu has immediate dominator %zu\n", i, result[i]);
00669             }
00670         }
00671     }
00672 }
00673 
00674 
00675 
00676 
00677 
00678 /******************************************************************************************************************************
00679  *                              Function templates for post dominators
00680  ******************************************************************************************************************************/
00681 
00682 template<class ControlFlowGraph, class DominanceGraph>
00683 void
00684 BinaryAnalysis::Dominance::build_postdom_graph_from_cfg(const ControlFlowGraph &cfg,
00685                                                         typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
00686                                                         DominanceGraph &result)
00687 {
00688     RelationMap<ControlFlowGraph> pdoms;
00689     build_postdom_relation_from_cfg(cfg, start, pdoms);
00690     build_graph_from_relation(cfg, pdoms, result);
00691 }
00692 
00693 template<class DominanceGraph, class ControlFlowGraph>
00694 DominanceGraph
00695 BinaryAnalysis::Dominance::build_postdom_graph_from_cfg(const ControlFlowGraph &cfg,
00696                                                         typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start)
00697 {
00698     DominanceGraph dg;
00699     build_postdom_graph_from_cfg(cfg, start, dg);
00700     return dg;
00701 }
00702 
00703 template<class ControlFlowGraph>
00704 BinaryAnalysis::Dominance::RelationMap<ControlFlowGraph>
00705 BinaryAnalysis::Dominance::build_postdom_relation_from_cfg(const ControlFlowGraph &cfg,
00706                                                            typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start)
00707 {
00708     RelationMap<ControlFlowGraph> pdom;
00709     build_postdom_relation_from_cfg(cfg, start, pdom);
00710     return pdom;
00711 }
00712 
00713 template<class ControlFlowGraph>
00714 void
00715 BinaryAnalysis::Dominance::build_postdom_relation_from_cfg(const ControlFlowGraph &_cfg,
00716                                                            typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
00717                                                            RelationMap<ControlFlowGraph> &result)
00718 {
00719     ControlFlowGraph cfg = _cfg;        /* we need our own copy since we might modify it */
00720 
00721     if (debug) {
00722         fprintf(debug, "BinaryAnalysis::Dominance::build_postdom_relation_from_cfg: starting at vertex %zu\n", start);
00723         SgAsmBlock *block = get(boost::vertex_name, cfg, start);
00724         SgAsmFunction *func = block ? block->get_enclosing_function() : NULL;
00725         if (func) {
00726             fprintf(debug, "  Vertex %zu is %s block of", start, func->get_entry_block()==block?"the entry":"a");
00727             if (func->get_name().empty()) {
00728                 fprintf(debug, " an unnamed function");
00729             } else {
00730                 fprintf(debug, " function <%s>", func->get_name().c_str());
00731             }
00732             fprintf(debug, " at 0x%08"PRIx64"\n", func->get_entry_va());
00733         }
00734     }
00735 
00736     /* Does the graph have more than one return block?  By "return", we mean any block whose control flow successor is possibly
00737      * outside the start node's function.  See ControlFlow::return_blocks(). */
00738     typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor CFG_Vertex;
00739     CFG_Vertex unique_exit;
00740     bool unique_exit_created = false;
00741     std::vector<CFG_Vertex> retblocks = ControlFlow().return_blocks(cfg, start);
00742     if (1==retblocks.size()) {
00743         if (debug)
00744             fprintf(debug, "  CFG has unique exit vertex %zu, block 0x%08"PRIx64"\n",
00745                     retblocks[0],
00746                     get(boost::vertex_name, cfg, retblocks[0])->get_address());
00747         unique_exit = retblocks[0];
00748     } else {
00749         assert(!retblocks.empty());
00750         unique_exit = add_vertex(cfg);
00751         unique_exit_created = true;
00752         put(boost::vertex_name, cfg, unique_exit, (SgAsmBlock*)0); /* vertex has no basic block */
00753         for (size_t i=0; i<retblocks.size(); i++)
00754             add_edge(retblocks[i], unique_exit, cfg);
00755         if (debug)
00756             fprintf(debug, "  CFG has %zu exit blocks. Added unique exit vertex %zu\n", retblocks.size(), unique_exit);
00757     }
00758 
00759     /* Post dominance is the same as doing dominance, but on a reversed CFG, using the unique return vertex as the starting
00760      * point. */
00761     if (debug)
00762         fprintf(debug, "  Calling build_idom_relation_from_cfg() on reversed CFG...\n");
00763     typedef typename boost::reverse_graph<ControlFlowGraph> ReversedControlFlowGraph;
00764     ReversedControlFlowGraph rcfg(cfg);
00765     RelationMap<ReversedControlFlowGraph> rrelation;
00766     build_idom_relation_from_cfg(rcfg, unique_exit, rrelation);
00767     if (debug)
00768         fprintf(debug, "BinaryAnalysis::Dominance::build_postdom_relation_from_cfg() resuming...\n");
00769 
00770     /* Remove the unique exit vertex if appropriate. */
00771     if (unique_exit_created) {
00772         assert(unique_exit+1==num_vertices(cfg));
00773         rrelation.pop_back();
00774         for (size_t i=0; i<rrelation.size(); ++i) {
00775             if (rrelation[i]>=rrelation.size())
00776                 rrelation[i] = boost::graph_traits<ControlFlowGraph>::null_vertex();
00777         }
00778     }
00779 
00780     /* Intiailize the result vector. */
00781     result.assign(rrelation.begin(), rrelation.end());
00782     if (debug) {
00783         fprintf(debug, "  Final result:\n");
00784         for (size_t i=0; i<result.size(); i++) {
00785             if (result[i]==boost::graph_traits<ControlFlowGraph>::null_vertex()) {
00786                 fprintf(debug, "    CFG vertex %zu has no immediate post dominator\n", i);
00787             } else {
00788                 fprintf(debug, "    CFG vertex %zu has immediate post dominator %zu\n", i, result[i]);
00789             }
00790         }
00791     }
00792 }
00793 
00794 
00795 
00796 
00797 /******************************************************************************************************************************
00798  *                              Function templates for miscellaneous methods
00799  ******************************************************************************************************************************/
00800 
00801 template<class DominanceGraph, class ControlFlowGraph>
00802 DominanceGraph
00803 BinaryAnalysis::Dominance::build_graph_from_relation(const ControlFlowGraph &cfg,
00804                                                      const RelationMap<ControlFlowGraph> &relmap)
00805 {
00806     DominanceGraph g;
00807     build_graph_from_relation(cfg, relmap, g);
00808     return g;
00809 }
00810 
00811 template<class ControlFlowGraph, class DominanceGraph>
00812 void
00813 BinaryAnalysis::Dominance::build_graph_from_relation(const ControlFlowGraph &cfg,
00814                                                      const RelationMap<ControlFlowGraph> &relmap,
00815                                                      DominanceGraph &dg/*out*/)
00816 {
00817     typedef typename boost::graph_traits<DominanceGraph>::vertex_descriptor D_Vertex;
00818     typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor CFG_Vertex;
00819 
00820     if (debug) {
00821         fprintf(debug, "BinaryAnalysis::Dominance::build_graph_from_relation:\n");
00822         fprintf(debug, "  building from this relation:\n");
00823         for (size_t i=0; i<relmap.size(); i++) {
00824             if (relmap[i]==boost::graph_traits<ControlFlowGraph>::null_vertex()) {
00825                 fprintf(debug, "    CFG vertex %zu has no immediate dominator\n", i);
00826             } else {
00827                 fprintf(debug, "    CFG vertex %zu has immediate dominator %zu\n", i, relmap[i]);
00828             }
00829         }
00830     }
00831 
00832     dg.clear();
00833     typename boost::graph_traits<ControlFlowGraph>::vertex_iterator vi, vi_end;
00834     for (boost::tie(vi, vi_end)=vertices(cfg); vi!=vi_end; vi++) {
00835         D_Vertex v = add_vertex(dg);
00836         assert(v==*vi); /* because relmap[] refers to CFG vertices; otherwise we need to map them */
00837         SgAsmBlock *block = get(boost::vertex_name, cfg, *vi);
00838         put(boost::vertex_name, dg, v, block);
00839     }
00840     for (boost::tie(vi, vi_end)=vertices(cfg); vi!=vi_end; vi++) {
00841         CFG_Vertex subordinate = *vi;
00842         CFG_Vertex dominator = relmap[subordinate];
00843         if (dominator!=boost::graph_traits<ControlFlowGraph>::null_vertex()) {
00844             if (debug)
00845                 fprintf(debug, "  adding edge (d,s) = (%zu,%zu)\n", dominator, subordinate);
00846             add_edge(dominator, subordinate, dg);
00847         }
00848     }
00849 }
00850 
00851 #endif