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

[Richard Biener <richard dot guenther at gmail dot com>]

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