commit 5e53fefae0373768b98d51d5746d43f36cecbe2a Author: Jeff Law Date: Mon Dec 7 11:32:58 2015 -0700 * domwalk.h (dom_walker::init_edge_executable): New method. (dom_walker::maybe_clear_unreachable_dom): Likewise. (dom_walker::bb_reachable): Likewise. (dom_walker::propagate_unreachable_to_edges): Likewise. (dom_walker::m_unreachable_dom): New private data member. * domwalk.c: Include dumpfile.h. (dom_walker::init_edge_executable): New method. (dom_walker::maybe_clear_unreachable_dom): Likewise. (dom_walker::bb_reachable): Likewise. Factored out of tree-ssa-sccvn.c (dom_walker::propagate_unreachable_to_edges): Likewise. * tree-ssa-sccvn.c (sccvn_dom_walker::unreachable_dom): Remove private data member. (sccvn_dom_walker::after_dom_children): Use methods from dom_walker class. (sccvn_dom_walker::before_dom_children): Similarly. (run_scc_vn): Likewise. diff --git a/gcc/domwalk.c b/gcc/domwalk.c index 167fc38..feb6478 100644 --- a/gcc/domwalk.c +++ b/gcc/domwalk.c @@ -24,6 +24,7 @@ along with GCC; see the file COPYING3. If not see #include "backend.h" #include "cfganal.h" #include "domwalk.h" +#include "dumpfile.h" /* This file implements a generic walker for dominator trees. @@ -142,6 +143,93 @@ cmp_bb_postorder (const void *a, const void *b) return 1; } +/* Mark all edges in the CFG as possibly being executable. */ + +void +dom_walker::init_edge_executable (struct function *fun) +{ + basic_block bb; + FOR_ALL_BB_FN (bb, fun) + { + edge_iterator ei; + edge e; + FOR_EACH_EDGE (e, ei, bb->succs) + e->flags |= EDGE_EXECUTABLE; + } +} + +/* Return TRUE if BB is reachable, false otherwise. */ + +bool +dom_walker::bb_reachable (struct function *fun, basic_block bb) +{ + /* If any of the predecessor edges that do not come from blocks dominated + by us are still marked as possibly executable consider this block + reachable. */ + bool reachable = false; + if (!m_unreachable_dom) + { + reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (fun); + edge_iterator ei; + edge e; + FOR_EACH_EDGE (e, ei, bb->preds) + if (!dominated_by_p (CDI_DOMINATORS, e->src, bb)) + reachable |= (e->flags & EDGE_EXECUTABLE); + } + + return reachable; +} + +/* BB has been determined to be unreachable. Propagate that property + to incoming and outgoing edges of BB as appropriate. */ + +void +dom_walker::propagate_unreachable_to_edges (basic_block bb, + FILE *dump_file, + int dump_flags) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Marking all outgoing edges of unreachable " + "BB %d as not executable\n", bb->index); + + edge_iterator ei; + edge e; + FOR_EACH_EDGE (e, ei, bb->succs) + e->flags &= ~EDGE_EXECUTABLE; + + FOR_EACH_EDGE (e, ei, bb->preds) + { + if (dominated_by_p (CDI_DOMINATORS, e->src, bb)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Marking backedge from BB %d into " + "unreachable BB %d as not executable\n", + e->src->index, bb->index); + e->flags &= ~EDGE_EXECUTABLE; + } + } + + if (!m_unreachable_dom) + m_unreachable_dom = bb; +} + +/* When we propagate the unreachable property to edges, we + also arrange to track the highest block in the dominator + walk which was unreachable. We can use that to identify + more unreachable blocks. + + When we finish processing the dominator children for that + highest unreachable block, we need to make sure to clear + that recorded highest block unreachable block in the + dominator tree. */ + +void +dom_walker::maybe_clear_unreachable_dom (basic_block bb) +{ + if (m_unreachable_dom == bb) + m_unreachable_dom = NULL; +} + /* Recursively walk the dominator tree. BB is the basic block we are currently visiting. */ diff --git a/gcc/domwalk.h b/gcc/domwalk.h index 71a7c47..d6b37a2 100644 --- a/gcc/domwalk.h +++ b/gcc/domwalk.h @@ -30,7 +30,8 @@ along with GCC; see the file COPYING3. If not see class dom_walker { public: - dom_walker (cdi_direction direction) : m_dom_direction (direction) {} + dom_walker (cdi_direction direction) : m_dom_direction (direction), + m_unreachable_dom (NULL) {} /* Walk the dominator tree. */ void walk (basic_block); @@ -41,12 +42,41 @@ public: /* Function to call after the recursive walk of the dominator children. */ virtual void after_dom_children (basic_block) {} + /* The next several methods support discovering unreachable blocks + and edges in the CFG during the dominator walk. Using these routines + is totally optional and only makes sense if your walker can change + the state of a block/edge to unreachable/unexecutable and your walker + can exploit that information to optimize better. */ + + /* Set EDGE_EXECUTABLE for every edge in the CFG. This must be done + before walking begins. */ + void init_edge_executable (struct function *); + + /* Query whether or not the given block is reachable or not. + + Typically used in the before_dom_children callback. */ + bool bb_reachable (struct function *, basic_block); + + /* Given an unreachable block, propagate that property to outgoing + and possibly incoming edges for the block. Typically called after + determining a block is unreachable in the before_dom_children + callback. */ + void propagate_unreachable_to_edges (basic_block, FILE *, int); + + /* This is a bit of a wart. We need to conditionally clear a bit of + state after we have process the dominator children. + + I'd prefer to hide this detail within domwalk, but right now it + bleeds out into the clients. */ + void maybe_clear_unreachable_dom (basic_block); + private: /* This is the direction of the dominator tree we want to walk. i.e., if it is set to CDI_DOMINATORS, then we walk the dominator tree, if it is set to CDI_POST_DOMINATORS, then we walk the post dominator tree. */ const ENUM_BITFIELD (cdi_direction) m_dom_direction : 2; + basic_block m_unreachable_dom; }; #endif diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c index 2014ee7..dbd61c9 100644 --- a/gcc/tree-ssa-sccvn.c +++ b/gcc/tree-ssa-sccvn.c @@ -4207,8 +4207,7 @@ class sccvn_dom_walker : public dom_walker { public: sccvn_dom_walker () - : dom_walker (CDI_DOMINATORS), fail (false), unreachable_dom (NULL), - cond_stack (vNULL) {} + : dom_walker (CDI_DOMINATORS), fail (false), cond_stack (vNULL) {} ~sccvn_dom_walker (); virtual void before_dom_children (basic_block); @@ -4220,7 +4219,6 @@ public: enum tree_code code, tree lhs, tree rhs, bool value); bool fail; - basic_block unreachable_dom; vec > > cond_stack; }; @@ -4301,8 +4299,7 @@ sccvn_dom_walker::record_conds (basic_block bb, void sccvn_dom_walker::after_dom_children (basic_block bb) { - if (unreachable_dom == bb) - unreachable_dom = NULL; + this->maybe_clear_unreachable_dom (bb); while (!cond_stack.is_empty () && cond_stack.last ().first == bb) @@ -4327,45 +4324,11 @@ sccvn_dom_walker::before_dom_children (basic_block bb) if (fail) return; - /* If any of the predecessor edges that do not come from blocks dominated - by us are still marked as possibly executable consider this block - reachable. */ - bool reachable = false; - if (!unreachable_dom) + /* If BB is not reachable, then propagate that property to edges, but + do not process this block any further. */ + if (!this->bb_reachable (cfun, bb)) { - reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (cfun); - FOR_EACH_EDGE (e, ei, bb->preds) - if (!dominated_by_p (CDI_DOMINATORS, e->src, bb)) - reachable |= (e->flags & EDGE_EXECUTABLE); - } - - /* If the block is not reachable all outgoing edges are not - executable. Neither are incoming edges with src dominated by us. */ - if (!reachable) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Marking all outgoing edges of unreachable " - "BB %d as not executable\n", bb->index); - - FOR_EACH_EDGE (e, ei, bb->succs) - e->flags &= ~EDGE_EXECUTABLE; - - FOR_EACH_EDGE (e, ei, bb->preds) - { - if (dominated_by_p (CDI_DOMINATORS, e->src, bb)) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Marking backedge from BB %d into " - "unreachable BB %d as not executable\n", - e->src->index, bb->index); - e->flags &= ~EDGE_EXECUTABLE; - } - } - - /* Record the most dominating unreachable block. */ - if (!unreachable_dom) - unreachable_dom = bb; - + this->propagate_unreachable_to_edges (bb, dump_file, dump_flags); return; } @@ -4519,7 +4482,6 @@ sccvn_dom_walker::before_dom_children (basic_block bb) bool run_scc_vn (vn_lookup_kind default_vn_walk_kind_) { - basic_block bb; size_t i; default_vn_walk_kind = default_vn_walk_kind_; @@ -4549,18 +4511,10 @@ run_scc_vn (vn_lookup_kind default_vn_walk_kind_) } } - /* Mark all edges as possibly executable. */ - FOR_ALL_BB_FN (bb, cfun) - { - edge_iterator ei; - edge e; - FOR_EACH_EDGE (e, ei, bb->succs) - e->flags |= EDGE_EXECUTABLE; - } - /* Walk all blocks in dominator order, value-numbering stmts SSA defs and decide whether outgoing edges are not executable. */ sccvn_dom_walker walker; + walker.init_edge_executable (cfun); walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); if (walker.fail) {