| Message ID | 56667585.5040307@redhat.com |
|---|---|
| State | New |
| Headers | show |
On Tue, Dec 8, 2015 at 7:15 AM, Jeff Law <law@redhat.com> wrote: > > First in the series. This merely refactors code from tree-ssa-sccvn.c into > domwalk.c so that other walkers can use it as they see fit. > > > There's an initialization function which sets all edges to executable. > > There's a test function to see if a block is reachable. > > There's a propagation function to propagate the unreachable property to > edges. > > Finally a function to clear m_unreachable_dom. I consider this a wart. > Essentially that data member contains the highest unreachable block in the > dominator tree. Once we've finished processing that block's children, we > need to clear the member. Ideally clients wouldn't need to call this member > function. > > Bikeshedding on the members names is encouraged. And if someone has a > clean, simple way to ensure that the m_unreachable_dom member gets cleared > regardless of whether or not a client has its own after_dom_children > callback, I'd love to hear it. I wonder if it makes more sense to integrate this with the domwalker itself. Add a constructor flag to it and do everything in itself. By letting the before_dom_children return a taken edge (or NULL if unknown) it can drive the outgoing edge marking. And the domwalk worker would simply not recurse to dom children for unreachable blocks. Richard. > OK for trunk? > > > Jeff > > commit 5e53fefae0373768b98d51d5746d43f36cecbe2a > Author: Jeff Law <law@redhat.com> > 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<std::pair <basic_block, std::pair <vn_nary_op_t, vn_nary_op_t> > > > 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) > { >
On Mon, Dec 07, 2015 at 11:15:33PM -0700, Jeff Law wrote: > > First in the series. This merely refactors code from tree-ssa-sccvn.c into > domwalk.c so that other walkers can use it as they see fit. > > > There's an initialization function which sets all edges to executable. > > There's a test function to see if a block is reachable. > > There's a propagation function to propagate the unreachable property to > edges. > > Finally a function to clear m_unreachable_dom. I consider this a wart. > Essentially that data member contains the highest unreachable block in the > dominator tree. Once we've finished processing that block's children, we > need to clear the member. Ideally clients wouldn't need to call this member > function. Hmm, I expect you thought about this, but why not always see if we need to clear it before calling after_dom_children () ? I think that would amount to an extra compare of a register and cached memory (we're just about to use the vtable pointer anyway) so I expect that wouldn't effect performance significantly. Thinking about this more I wonder if we could move more of this into the dom walker, and skip calling before / after dom_children on unreachable blocks all together. That would seem to work for sccvn, but I'm not sure about what tree-ssa-dom.c is doing with the mark pushing and clearing. Trev
On 12/08/2015 07:23 AM, Richard Biener wrote: > > I wonder if it makes more sense to integrate this with the domwalker > itself. I seriously considered that. Essentially, letting the optimizer concern itself merely with asking for the improved domwalk and clearing EDGE_EXECUTABLE when the optimizer finds a conditional it can collapse. Bury the rest entirely within domwalk.c. It shouldn't be hard to prototype on top of the refactoring I've already done. jeff
On 12/08/2015 08:36 AM, Trevor Saunders wrote: > > Thinking about this more I wonder if we could move more of this into the > dom walker, and skip calling before / after dom_children on unreachable > blocks all together. That would seem to work for sccvn, but I'm not > sure about what tree-ssa-dom.c is doing with the mark pushing and > clearing. Total brain lock, it hit when I got Richi's message, dumping it in the walker itself is the obvious choice. jeff
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<std::pair <basic_block, std::pair <vn_nary_op_t, vn_nary_op_t> > > 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) {
First in the series. This merely refactors code from tree-ssa-sccvn.c into domwalk.c so that other walkers can use it as they see fit. There's an initialization function which sets all edges to executable. There's a test function to see if a block is reachable. There's a propagation function to propagate the unreachable property to edges. Finally a function to clear m_unreachable_dom. I consider this a wart. Essentially that data member contains the highest unreachable block in the dominator tree. Once we've finished processing that block's children, we need to clear the member. Ideally clients wouldn't need to call this member function. Bikeshedding on the members names is encouraged. And if someone has a clean, simple way to ensure that the m_unreachable_dom member gets cleared regardless of whether or not a client has its own after_dom_children callback, I'd love to hear it. OK for trunk? Jeff commit 5e53fefae0373768b98d51d5746d43f36cecbe2a Author: Jeff Law <law@redhat.com> 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.