This is the refactoring part of the patch -- essentially bits move from tree-ssa-sccvn into domwalk so that other domwalk clients can benefit from the ability to detect unreachable blocks and propagate unreachable edge properties.
This also fixes up tree-ssa-sccvn to use the new bits from domwalk.
commit 0485724b3e1c80ed1d4c3f4d263f6675cebe27a7
Author: Jeff Law <l...@redhat.com>
Date:   Mon Dec 7 11:32:58 2015 -0700

    2015-12-05  Jeff Law  <l...@redhat.com>
    
        * domwalk.h (dom_walker::dom_walker): Add new argument
        skip_unreachable_blocks.  Don't provide empty constructor body.
        (dom_walker::before_dom_children): Change return type.
        (dom_walker::bb_reachable): Declare new private method.
        (dom_walker::propagate_unreachable_to_edges): Likewise.
        (dom_walker::m_unreachable_dom): Declare new private data member.
        (dom_walker::m_skip_unreachable_blocks): Likewise.
        * domwalk.c: Include dumpfile.h.
        (dom_walker::dom_walker): New constructor.  Initialize private data
        members.  If needed, set EDGE_EXECUTABLE for all edges in the CFG,
        extracted from tree-ssa-sccvn.c.
        (dom_walker::bb_reachable): New method extracted from tree-ssa-sccvn.c
        (dom_walker::propagate_unreachable_to_edges): Likewise.
        (dom_walker::walk): Only call before_dom_children on reachable
        blocks.  If before_dom_children returns an edge, then clear
        EDGE_EXECUTABLE for all other outgoing edges from the same block.
        For unreachable blocks, call propagate_unreachable_to_edges.
        Similarly, only call after_dom_children on reachable blocks.  For
        unreachable blocks, conditionally clear m_unreachable_dom.
        * 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.
        (run_scc_vn): Likewise.
        (sccvn_dom_walker::before_dom_children): Likewise.  Return the taken
        outgoing edge if a COND, SWITCH, or GOTO are optimized.

diff --git a/gcc/domwalk.c b/gcc/domwalk.c
index 167fc38..2332191 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,91 @@ cmp_bb_postorder (const void *a, const void *b)
   return 1;
 }
 
+/* Constructor for a dom walker.
+
+   If SKIP_UNREACHBLE_BLOCKS is true, then we need to set
+   EDGE_EXECUTABLE on every edge in the CFG. */
+dom_walker::dom_walker (cdi_direction direction,
+                       bool skip_unreachable_blocks)
+  : m_dom_direction (direction),
+    m_skip_unreachable_blocks (skip_unreachable_blocks), 
+    m_unreachable_dom (NULL)
+{
+  /* If we are not skipping unreachable blocks, then there is nothing
+     to do.  */
+  if (!m_skip_unreachable_blocks)
+    return;
+
+  basic_block bb;
+  FOR_ALL_BB_FN (bb, cfun)
+    {
+      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 we're not skipping unreachable blocks, then assume everything
+     is reachable.  */
+  if (!m_skip_unreachable_blocks)
+    return true;
+
+  /* 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;
+}
+
 /* Recursively walk the dominator tree.
    BB is the basic block we are currently visiting.  */
 
@@ -171,9 +257,23 @@ dom_walker::walk (basic_block bb)
          || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
          || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
        {
+
          /* Callback for subclasses to do custom things before we have walked
             the dominator children, but before we walk statements.  */
-         before_dom_children (bb);
+         if (this->bb_reachable (cfun, bb))
+           {
+             edge taken_edge = before_dom_children (bb);
+             if (taken_edge)
+               {
+                 edge_iterator ei;
+                 edge e;
+                 FOR_EACH_EDGE (e, ei, bb->succs)
+                   if (e != taken_edge)
+                     e->flags &= ~EDGE_EXECUTABLE;
+               }
+           }
+         else
+           propagate_unreachable_to_edges (bb, dump_file, dump_flags);
 
          /* Mark the current BB to be popped out of the recursion stack
             once children are processed.  */
@@ -203,7 +303,10 @@ dom_walker::walk (basic_block bb)
 
          /* Callback allowing subclasses to do custom things after we have
             walked dominator children, but before we walk statements.  */
-         after_dom_children (bb);
+         if (bb_reachable (cfun, bb))
+           after_dom_children (bb);
+         else if (m_unreachable_dom == bb)
+           m_unreachable_dom = NULL;
        }
       if (sp)
        bb = worklist[--sp];
diff --git a/gcc/domwalk.h b/gcc/domwalk.h
index 71a7c47..7c4a534 100644
--- a/gcc/domwalk.h
+++ b/gcc/domwalk.h
@@ -30,13 +30,26 @@ along with GCC; see the file COPYING3.  If not see
 class dom_walker
 {
 public:
-  dom_walker (cdi_direction direction) : m_dom_direction (direction) {}
+  /* Use SKIP_UNREACHBLE_BLOCKS = true when your client can discover
+     that some edges are not executable.
+
+     If a client can discover that a COND, SWITCH or GOTO has a static
+     target in the before_dom_children callback, the taken edge should
+     be returned.  The generic walker will clear EDGE_EXECUTABLE on all
+     edges it can determine are not executable.  */
+  dom_walker (cdi_direction direction, bool skip_unreachable_blocks = false);
 
   /* 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) {}
+  /* Function to call before the recursive walk of the dominator children. 
+
+     Return value is the always taken edge if the block has multiple outgoing
+     edges, NULL otherwise.  When skipping unreachable blocks, the walker
+     uses the taken edge information to clear EDGE_EXECUTABLE on the other
+     edges, exposing unreachable blocks.  A NULL return value means all
+     outgoing edges should still be considered executable.  */
+  virtual edge before_dom_children (basic_block) { return NULL; }
 
   /* Function to call after the recursive walk of the dominator children.  */
   virtual void after_dom_children (basic_block) {}
@@ -47,6 +60,18 @@ 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;
+  bool m_skip_unreachable_blocks;
+  basic_block m_unreachable_dom;
+
+  /* Query whether or not the given block is reachable or not.  */
+  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);
+
 };
 
 #endif
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index 2014ee7..1d1c3e3 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -4207,11 +4207,10 @@ 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, true), fail (false), cond_stack (vNULL) {}
   ~sccvn_dom_walker ();
 
-  virtual void before_dom_children (basic_block);
+  virtual edge before_dom_children (basic_block);
   virtual void after_dom_children (basic_block);
 
   void record_cond (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,9 +4299,6 @@ 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;
-
   while (!cond_stack.is_empty ()
         && cond_stack.last ().first == bb)
     {
@@ -4318,56 +4313,14 @@ sccvn_dom_walker::after_dom_children (basic_block bb)
 
 /* Value number all statements in BB.  */
 
-void
+edge
 sccvn_dom_walker::before_dom_children (basic_block bb)
 {
   edge e;
   edge_iterator ei;
 
   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)
-    {
-      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;
-
-      return;
-    }
+    return NULL;
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "Visiting BB %d\n", bb->index);
@@ -4428,7 +4381,7 @@ sccvn_dom_walker::before_dom_children (basic_block bb)
          && !DFS (res))
        {
          fail = true;
-         return;
+         return NULL;
        }
     }
   for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
@@ -4441,20 +4394,20 @@ sccvn_dom_walker::before_dom_children (basic_block bb)
            && !DFS (op))
          {
            fail = true;
-           return;
+           return NULL;
          }
     }
 
   /* Finally look at the last stmt.  */
   gimple *stmt = last_stmt (bb);
   if (!stmt)
-    return;
+    return NULL;
 
   enum gimple_code code = gimple_code (stmt);
   if (code != GIMPLE_COND
       && code != GIMPLE_SWITCH
       && code != GIMPLE_GOTO)
-    return;
+    return NULL;
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
@@ -4497,19 +4450,17 @@ sccvn_dom_walker::before_dom_children (basic_block bb)
       gcc_unreachable ();
     }
   if (!val)
-    return;
+    return NULL;
 
   edge taken = find_taken_edge (bb, vn_valueize (val));
   if (!taken)
-    return;
+    return NULL;
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "Marking all edges out of BB %d but (%d -> %d) as "
             "not executable\n", bb->index, bb->index, taken->dest->index);
 
-  FOR_EACH_EDGE (e, ei, bb->succs)
-    if (e != taken)
-      e->flags &= ~EDGE_EXECUTABLE;
+  return taken;
 }
 
 /* Do SCCVN.  Returns true if it finished, false if we bailed out
@@ -4519,7 +4470,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,15 +4499,6 @@ 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;

Reply via email to