On Tue, Dec 8, 2015 at 7:15 AM, Jeff Law <l...@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 <l...@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)
> {
>
