[RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3]

[RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3]

[Jeff Law]

[-- Attachment #1: Type: text/plain, Size: 936 bytes --]


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

[-- Attachment #2: PP --]
[-- Type: text/plain, Size: 9680 bytes --]

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)
     {

Re: [RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3]

[Richard Biener]

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)
>      {
>

Re: [RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3]

[Richard Biener]

On Tue, Dec 8, 2015 at 3:23 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> 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.

So interface-wise do

Index: gcc/domwalk.h
===================================================================
--- gcc/domwalk.h       (revision 231396)
+++ gcc/domwalk.h       (working copy)
@@ -30,13 +30,16 @@ along with GCC; see the file COPYING3.
 class dom_walker
 {
 public:
-  dom_walker (cdi_direction direction) : m_dom_direction (direction) {}
+  dom_walker (cdi_direction direction,
+             bool skip_unreachable_blocks = false)
+      : m_dom_direction (direction),
+        m_skip_unreachable_blocks (skip_unreachable_blocks) {}

   /* Walk the dominator tree.  */
   void walk (basic_block);

   /* Function to call before the recursive walk of the dominator children.  */
-  virtual void before_dom_children (basic_block) {}
+  virtual edge before_dom_children (basic_block) {}

   /* Function to call after the recursive walk of the dominator children.  */
   virtual void after_dom_children (basic_block) {}
@@ -47,6 +50,7 @@ private:
      if it is set to CDI_POST_DOMINATORS, then we walk the post
      dominator tree.  */
   const ENUM_BITFIELD (cdi_direction) m_dom_direction : 2;
+  const bool m_skip_unreachable_blocks;
 };

 #endif

and simply inline all the code into dom_walker::walk.

Richard.

> 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)
>>      {
>>

Re: [RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3]

[Trevor Saunders]

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

Re: [RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3]

[Jeff Law]

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

Re: [RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3]

[Jeff Law]

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

Re: [RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3]

[Jeff Law]

On 12/08/2015 07:27 AM, Richard Biener wrote:
>>
>> 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.
>
> So interface-wise do
[ ... ]
Close :-)

If skip_unreachable_blocks is true, then we want the walker to 
initialize EDGE_EXECUTABLE automatically.  So we drop the member 
initialization and constructor body from domwalk.h and instead have a 
ctor in domwalk.c where we can initialize the private members and set 
EDGE_EXECUTABLE as needed.

My first iteration let the clients clear EDGE_EXECUTABLE as they found 
conditionals that could be optimized.  That was pretty clean and 
localized in sccvn & dom.

If we have the before_dom_children return the taken edge, then we have 
to twiddle all the clients due to the api change in before_dom_children. 
  .  There's ~18 in total, so it's not too bad.

2 of the 18 clearly need to use the skip_unreachable_blocks capability 
(dom and sccvn).  2 others might be able to use it (tree-ssa-pre.c and 
tree-ssa-propagate.c)  I converted dom and sccvn, but not pre and the 
generic propagation engine.

I can submit the iteration which lets clients clear EDGE_EXECUTABLE, or 
the iteration where the clients return the taken edge (or NULL) from the 
before_dom_children callback.

Either is fine with me, so if you have a preference, let me know.

jeff

Re: [RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3]

[Richard Biener]

On Wed, Dec 9, 2015 at 9:31 AM, Jeff Law <law@redhat.com> wrote:
> On 12/08/2015 07:27 AM, Richard Biener wrote:
>>>
>>>
>>> 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.
>>
>>
>> So interface-wise do
>
> [ ... ]
> Close :-)
>
> If skip_unreachable_blocks is true, then we want the walker to initialize
> EDGE_EXECUTABLE automatically.  So we drop the member initialization and
> constructor body from domwalk.h and instead have a ctor in domwalk.c where
> we can initialize the private members and set EDGE_EXECUTABLE as needed.
>
> My first iteration let the clients clear EDGE_EXECUTABLE as they found
> conditionals that could be optimized.  That was pretty clean and localized
> in sccvn & dom.
>
> If we have the before_dom_children return the taken edge, then we have to
> twiddle all the clients due to the api change in before_dom_children.  .
> There's ~18 in total, so it's not too bad.
>
> 2 of the 18 clearly need to use the skip_unreachable_blocks capability (dom
> and sccvn).  2 others might be able to use it (tree-ssa-pre.c and
> tree-ssa-propagate.c)  I converted dom and sccvn, but not pre and the
> generic propagation engine.
>
> I can submit the iteration which lets clients clear EDGE_EXECUTABLE, or the
> iteration where the clients return the taken edge (or NULL) from the
> before_dom_children callback.
>
> Either is fine with me, so if you have a preference, let me know.

Return the taken edge.

Richard.

> jeff