[RFA][PATCH] Refactor duplicated code used by various dom walkers

[RFA][PATCH] Refactor duplicated code used by various dom walkers

[Jeff Law]

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




Several passes which perform dominator walks want to identify when block 
has a single incoming edge, ignoring loop backedges.

I'm aware of 4 implementations of this code.  3 of the 4 are identical 
in function.  The 4th (tree-ssa-dom.c) has an additional twist that it 
also ignores edges that are not marked as executable.

So I've taken the more general implementation from tree-ssa-dom.c and 
conditionalized the handling of unexecutable edges on a flag and moved 
the implementation into cfganal.c where it more naturally belongs.

Bootstrapped and regression tested on x86_64.  OK for the trunk?

Jeff

[-- Attachment #2: P --]
[-- Type: text/plain, Size: 8811 bytes --]

	* cfganal.c (single_incoming_edge_ignoring_loop_edges): New function
	extracted from tree-ssa-dom.c.
	* cfganal.h (single_incoming_edge_ignoring_loop_edges): Prototype.
	* tree-ssa-dom.c (single_incoming_edge_ignoring_loop_edges): Remove.
	(record_equivalences_from_incoming_edge): Add additional argument
	to single_incoming_edge_ignoring_loop_edges call.
	* tree-ssa-uncprop.c (single_incoming_edge_ignoring_loop_edges): Remove.
	(uncprop_dom_walker::before_dom_children): Add additional argument
	to single_incoming_edge_ignoring_loop_edges call.
	* tree-ssa-sccvn.c (sccvn_dom_walker::before_dom_children): Use
	single_incoming_edge_ignoring_loop_edges rather than open coding.
	* tree-vrp.c (evrp_dom_walker::before_dom_children): Similarly.





diff --git a/gcc/cfganal.c b/gcc/cfganal.c
index c506067..14d94b2 100644
--- a/gcc/cfganal.c
+++ b/gcc/cfganal.c
@@ -1554,3 +1554,38 @@ single_pred_before_succ_order (void)
 #undef MARK_VISITED
 #undef VISITED_P
 }
+
+/* Ignoring loop backedges, if BB has precisely one incoming edge then
+   return that edge.  Otherwise return NULL.  */
+edge
+single_incoming_edge_ignoring_loop_edges (basic_block bb,
+					  bool ignore_unreachable)
+{
+  edge retval = NULL;
+  edge e;
+  edge_iterator ei;
+
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    {
+      /* A loop back edge can be identified by the destination of
+	 the edge dominating the source of the edge.  */
+      if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
+	continue;
+
+      /* We can safely ignore edges that are not executable.  */
+      if (ignore_unreachable
+	  && (e->flags & EDGE_EXECUTABLE) == 0)
+	continue;
+
+      /* If we have already seen a non-loop edge, then we must have
+	 multiple incoming non-loop edges and thus we return NULL.  */
+      if (retval)
+	return NULL;
+
+      /* This is the first non-loop incoming edge we have found.  Record
+	 it.  */
+      retval = e;
+    }
+
+  return retval;
+}
diff --git a/gcc/cfganal.h b/gcc/cfganal.h
index 39bb5e5..74975e5 100644
--- a/gcc/cfganal.h
+++ b/gcc/cfganal.h
@@ -77,5 +77,6 @@ extern void bitmap_intersection_of_preds (sbitmap, sbitmap *, basic_block);
 extern void bitmap_union_of_succs (sbitmap, sbitmap *, basic_block);
 extern void bitmap_union_of_preds (sbitmap, sbitmap *, basic_block);
 extern basic_block * single_pred_before_succ_order (void);
+extern edge single_incoming_edge_ignoring_loop_edges (basic_block, bool);
 
 #endif /* GCC_CFGANAL_H */
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index 06be69a..31f88b4 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -113,7 +113,6 @@ static void eliminate_redundant_computations (gimple_stmt_iterator *,
 					      class avail_exprs_stack *);
 static void record_equivalences_from_stmt (gimple *, int,
 					   class avail_exprs_stack *);
-static edge single_incoming_edge_ignoring_loop_edges (basic_block);
 static void dump_dominator_optimization_stats (FILE *file,
 					       hash_table<expr_elt_hasher> *);
 
@@ -1057,39 +1056,6 @@ record_equivalences_from_phis (basic_block bb)
     }
 }
 
-/* Ignoring loop backedges, if BB has precisely one incoming edge then
-   return that edge.  Otherwise return NULL.  */
-static edge
-single_incoming_edge_ignoring_loop_edges (basic_block bb)
-{
-  edge retval = NULL;
-  edge e;
-  edge_iterator ei;
-
-  FOR_EACH_EDGE (e, ei, bb->preds)
-    {
-      /* A loop back edge can be identified by the destination of
-	 the edge dominating the source of the edge.  */
-      if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
-	continue;
-
-      /* We can safely ignore edges that are not executable.  */
-      if ((e->flags & EDGE_EXECUTABLE) == 0)
-	continue;
-
-      /* If we have already seen a non-loop edge, then we must have
-	 multiple incoming non-loop edges and thus we return NULL.  */
-      if (retval)
-	return NULL;
-
-      /* This is the first non-loop incoming edge we have found.  Record
-	 it.  */
-      retval = e;
-    }
-
-  return retval;
-}
-
 /* Record any equivalences created by the incoming edge to BB into
    CONST_AND_COPIES and AVAIL_EXPRS_STACK.  If BB has more than one
    incoming edge, then no equivalence is created.  */
@@ -1107,7 +1073,7 @@ record_equivalences_from_incoming_edge (basic_block bb,
      the parent was followed.  */
   parent = get_immediate_dominator (CDI_DOMINATORS, bb);
 
-  e = single_incoming_edge_ignoring_loop_edges (bb);
+  e = single_incoming_edge_ignoring_loop_edges (bb, true);
 
   /* If we had a single incoming edge from our parent block, then enter
      any data associated with the edge into our tables.  */
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index 306080b..1c99d3b 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -4847,34 +4847,18 @@ sccvn_dom_walker::after_dom_children (basic_block bb)
 edge
 sccvn_dom_walker::before_dom_children (basic_block bb)
 {
-  edge e;
-  edge_iterator ei;
-
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "Visiting BB %d\n", bb->index);
 
   /* If we have a single predecessor record the equivalence from a
      possible condition on the predecessor edge.  */
-  edge pred_e = NULL;
-  FOR_EACH_EDGE (e, ei, bb->preds)
-    {
-      /* Ignore simple backedges from this to allow recording conditions
-         in loop headers.  */
-      if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
-	continue;
-      if (! pred_e)
-	pred_e = e;
-      else
-	{
-	  pred_e = NULL;
-	  break;
-	}
-    }
+  edge pred_e = single_incoming_edge_ignoring_loop_edges (bb, false);
   if (pred_e)
     {
       /* Check if there are multiple executable successor edges in
 	 the source block.  Otherwise there is no additional info
 	 to be recorded.  */
+      edge_iterator ei;
       edge e2;
       FOR_EACH_EDGE (e2, ei, pred_e->src->succs)
 	if (e2 != pred_e
diff --git a/gcc/tree-ssa-uncprop.c b/gcc/tree-ssa-uncprop.c
index 200ec70..4cc7714 100644
--- a/gcc/tree-ssa-uncprop.c
+++ b/gcc/tree-ssa-uncprop.c
@@ -408,40 +408,10 @@ uncprop_into_successor_phis (basic_block bb)
     }
 }
 
-/* Ignoring loop backedges, if BB has precisely one incoming edge then
-   return that edge.  Otherwise return NULL.  */
-static edge
-single_incoming_edge_ignoring_loop_edges (basic_block bb)
-{
-  edge retval = NULL;
-  edge e;
-  edge_iterator ei;
-
-  FOR_EACH_EDGE (e, ei, bb->preds)
-    {
-      /* A loop back edge can be identified by the destination of
-	 the edge dominating the source of the edge.  */
-      if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
-	continue;
-
-      /* If we have already seen a non-loop edge, then we must have
-	 multiple incoming non-loop edges and thus we return NULL.  */
-      if (retval)
-	return NULL;
-
-      /* This is the first non-loop incoming edge we have found.  Record
-	 it.  */
-      retval = e;
-    }
-
-  return retval;
-}
-
 edge
 uncprop_dom_walker::before_dom_children (basic_block bb)
 {
   basic_block parent;
-  edge e;
   bool recorded = false;
 
   /* If this block is dominated by a single incoming edge and that edge
@@ -450,7 +420,7 @@ uncprop_dom_walker::before_dom_children (basic_block bb)
   parent = get_immediate_dominator (CDI_DOMINATORS, bb);
   if (parent)
     {
-      e = single_incoming_edge_ignoring_loop_edges (bb);
+      edge e = single_incoming_edge_ignoring_loop_edges (bb, false);
 
       if (e && e->src == parent && e->aux)
 	{
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 63ee156..39e9156 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -10970,33 +10970,17 @@ evrp_dom_walker::try_find_new_range (tree name,
 edge
 evrp_dom_walker::before_dom_children (basic_block bb)
 {
-  tree op0 = NULL_TREE;
-  edge_iterator ei;
-  edge e;
-
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "Visiting BB%d\n", bb->index);
 
   stack.safe_push (std::make_pair (NULL_TREE, (value_range *)NULL));
 
-  edge pred_e = NULL;
-  FOR_EACH_EDGE (e, ei, bb->preds)
-    {
-      /* Ignore simple backedges from this to allow recording conditions
-	 in loop headers.  */
-      if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
-	continue;
-      if (! pred_e)
-	pred_e = e;
-      else
-	{
-	  pred_e = NULL;
-	  break;
-	}
-    }
+  edge pred_e = single_incoming_edge_ignoring_loop_edges (bb, false);
   if (pred_e)
     {
       gimple *stmt = last_stmt (pred_e->src);
+      tree op0 = NULL_TREE;
+
       if (stmt
 	  && gimple_code (stmt) == GIMPLE_COND
 	  && (op0 = gimple_cond_lhs (stmt))
@@ -11040,6 +11024,8 @@ evrp_dom_walker::before_dom_children (basic_block bb)
 
   /* Visit PHI stmts and discover any new VRs possible.  */
   bool has_unvisited_preds = false;
+  edge_iterator ei;
+  edge e;
   FOR_EACH_EDGE (e, ei, bb->preds)
     if (e->flags & EDGE_EXECUTABLE
 	&& !(e->src->flags & BB_VISITED))

Re: [RFA][PATCH] Refactor duplicated code used by various dom walkers

[Richard Biener]

On Fri, Nov 3, 2017 at 4:49 AM, Jeff Law <law@redhat.com> wrote:
>
>
>
> Several passes which perform dominator walks want to identify when block has
> a single incoming edge, ignoring loop backedges.
>
> I'm aware of 4 implementations of this code.  3 of the 4 are identical in
> function.  The 4th (tree-ssa-dom.c) has an additional twist that it also
> ignores edges that are not marked as executable.
>
> So I've taken the more general implementation from tree-ssa-dom.c and
> conditionalized the handling of unexecutable edges on a flag and moved the
> implementation into cfganal.c where it more naturally belongs.
>
> Bootstrapped and regression tested on x86_64.  OK for the trunk?

Minor nits (sorry...)

> Jeff
>
>         * cfganal.c (single_incoming_edge_ignoring_loop_edges): New function
>         extracted from tree-ssa-dom.c.
>         * cfganal.h (single_incoming_edge_ignoring_loop_edges): Prototype.
>         * tree-ssa-dom.c (single_incoming_edge_ignoring_loop_edges): Remove.
>         (record_equivalences_from_incoming_edge): Add additional argument
>         to single_incoming_edge_ignoring_loop_edges call.
>         * tree-ssa-uncprop.c (single_incoming_edge_ignoring_loop_edges):
> Remove.
>         (uncprop_dom_walker::before_dom_children): Add additional argument
>         to single_incoming_edge_ignoring_loop_edges call.
>         * tree-ssa-sccvn.c (sccvn_dom_walker::before_dom_children): Use
>         single_incoming_edge_ignoring_loop_edges rather than open coding.
>         * tree-vrp.c (evrp_dom_walker::before_dom_children): Similarly.
>
>
>
>
>
> diff --git a/gcc/cfganal.c b/gcc/cfganal.c
> index c506067..14d94b2 100644
> --- a/gcc/cfganal.c
> +++ b/gcc/cfganal.c
> @@ -1554,3 +1554,38 @@ single_pred_before_succ_order (void)
>  #undef MARK_VISITED
>  #undef VISITED_P
>  }
> +
> +/* Ignoring loop backedges, if BB has precisely one incoming edge then
> +   return that edge.  Otherwise return NULL.  */
> +edge
> +single_incoming_edge_ignoring_loop_edges (basic_block bb,
> +                                         bool ignore_unreachable)

single_pred_edge_ignoring_loop_edges and ignore_not_executable

to better match existing CFG functions and actual edge flag use.

Ok with that change.

Thanks,
Richard.

> +{
> +  edge retval = NULL;
> +  edge e;
> +  edge_iterator ei;
> +
> +  FOR_EACH_EDGE (e, ei, bb->preds)
> +    {
> +      /* A loop back edge can be identified by the destination of
> +        the edge dominating the source of the edge.  */
> +      if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
> +       continue;
> +
> +      /* We can safely ignore edges that are not executable.  */
> +      if (ignore_unreachable
> +         && (e->flags & EDGE_EXECUTABLE) == 0)
> +       continue;
> +
> +      /* If we have already seen a non-loop edge, then we must have
> +        multiple incoming non-loop edges and thus we return NULL.  */
> +      if (retval)
> +       return NULL;
> +
> +      /* This is the first non-loop incoming edge we have found.  Record
> +        it.  */
> +      retval = e;
> +    }
> +
> +  return retval;
> +}
> diff --git a/gcc/cfganal.h b/gcc/cfganal.h
> index 39bb5e5..74975e5 100644
> --- a/gcc/cfganal.h
> +++ b/gcc/cfganal.h
> @@ -77,5 +77,6 @@ extern void bitmap_intersection_of_preds (sbitmap, sbitmap
> *, basic_block);
>  extern void bitmap_union_of_succs (sbitmap, sbitmap *, basic_block);
>  extern void bitmap_union_of_preds (sbitmap, sbitmap *, basic_block);
>  extern basic_block * single_pred_before_succ_order (void);
> +extern edge single_incoming_edge_ignoring_loop_edges (basic_block, bool);
>
>  #endif /* GCC_CFGANAL_H */
> diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
> index 06be69a..31f88b4 100644
> --- a/gcc/tree-ssa-dom.c
> +++ b/gcc/tree-ssa-dom.c
> @@ -113,7 +113,6 @@ static void eliminate_redundant_computations
> (gimple_stmt_iterator *,
>                                               class avail_exprs_stack *);
>  static void record_equivalences_from_stmt (gimple *, int,
>                                            class avail_exprs_stack *);
> -static edge single_incoming_edge_ignoring_loop_edges (basic_block);
>  static void dump_dominator_optimization_stats (FILE *file,
>                                                hash_table<expr_elt_hasher>
> *);
>
> @@ -1057,39 +1056,6 @@ record_equivalences_from_phis (basic_block bb)
>      }
>  }
>
> -/* Ignoring loop backedges, if BB has precisely one incoming edge then
> -   return that edge.  Otherwise return NULL.  */
> -static edge
> -single_incoming_edge_ignoring_loop_edges (basic_block bb)
> -{
> -  edge retval = NULL;
> -  edge e;
> -  edge_iterator ei;
> -
> -  FOR_EACH_EDGE (e, ei, bb->preds)
> -    {
> -      /* A loop back edge can be identified by the destination of
> -        the edge dominating the source of the edge.  */
> -      if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
> -       continue;
> -
> -      /* We can safely ignore edges that are not executable.  */
> -      if ((e->flags & EDGE_EXECUTABLE) == 0)
> -       continue;
> -
> -      /* If we have already seen a non-loop edge, then we must have
> -        multiple incoming non-loop edges and thus we return NULL.  */
> -      if (retval)
> -       return NULL;
> -
> -      /* This is the first non-loop incoming edge we have found.  Record
> -        it.  */
> -      retval = e;
> -    }
> -
> -  return retval;
> -}
> -
>  /* Record any equivalences created by the incoming edge to BB into
>     CONST_AND_COPIES and AVAIL_EXPRS_STACK.  If BB has more than one
>     incoming edge, then no equivalence is created.  */
> @@ -1107,7 +1073,7 @@ record_equivalences_from_incoming_edge (basic_block
> bb,
>       the parent was followed.  */
>    parent = get_immediate_dominator (CDI_DOMINATORS, bb);
>
> -  e = single_incoming_edge_ignoring_loop_edges (bb);
> +  e = single_incoming_edge_ignoring_loop_edges (bb, true);
>
>    /* If we had a single incoming edge from our parent block, then enter
>       any data associated with the edge into our tables.  */
> diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
> index 306080b..1c99d3b 100644
> --- a/gcc/tree-ssa-sccvn.c
> +++ b/gcc/tree-ssa-sccvn.c
> @@ -4847,34 +4847,18 @@ sccvn_dom_walker::after_dom_children (basic_block
> bb)
>  edge
>  sccvn_dom_walker::before_dom_children (basic_block bb)
>  {
> -  edge e;
> -  edge_iterator ei;
> -
>    if (dump_file && (dump_flags & TDF_DETAILS))
>      fprintf (dump_file, "Visiting BB %d\n", bb->index);
>
>    /* If we have a single predecessor record the equivalence from a
>       possible condition on the predecessor edge.  */
> -  edge pred_e = NULL;
> -  FOR_EACH_EDGE (e, ei, bb->preds)
> -    {
> -      /* Ignore simple backedges from this to allow recording conditions
> -         in loop headers.  */
> -      if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
> -       continue;
> -      if (! pred_e)
> -       pred_e = e;
> -      else
> -       {
> -         pred_e = NULL;
> -         break;
> -       }
> -    }
> +  edge pred_e = single_incoming_edge_ignoring_loop_edges (bb, false);
>    if (pred_e)
>      {
>        /* Check if there are multiple executable successor edges in
>          the source block.  Otherwise there is no additional info
>          to be recorded.  */
> +      edge_iterator ei;
>        edge e2;
>        FOR_EACH_EDGE (e2, ei, pred_e->src->succs)
>         if (e2 != pred_e
> diff --git a/gcc/tree-ssa-uncprop.c b/gcc/tree-ssa-uncprop.c
> index 200ec70..4cc7714 100644
> --- a/gcc/tree-ssa-uncprop.c
> +++ b/gcc/tree-ssa-uncprop.c
> @@ -408,40 +408,10 @@ uncprop_into_successor_phis (basic_block bb)
>      }
>  }
>
> -/* Ignoring loop backedges, if BB has precisely one incoming edge then
> -   return that edge.  Otherwise return NULL.  */
> -static edge
> -single_incoming_edge_ignoring_loop_edges (basic_block bb)
> -{
> -  edge retval = NULL;
> -  edge e;
> -  edge_iterator ei;
> -
> -  FOR_EACH_EDGE (e, ei, bb->preds)
> -    {
> -      /* A loop back edge can be identified by the destination of
> -        the edge dominating the source of the edge.  */
> -      if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
> -       continue;
> -
> -      /* If we have already seen a non-loop edge, then we must have
> -        multiple incoming non-loop edges and thus we return NULL.  */
> -      if (retval)
> -       return NULL;
> -
> -      /* This is the first non-loop incoming edge we have found.  Record
> -        it.  */
> -      retval = e;
> -    }
> -
> -  return retval;
> -}
> -
>  edge
>  uncprop_dom_walker::before_dom_children (basic_block bb)
>  {
>    basic_block parent;
> -  edge e;
>    bool recorded = false;
>
>    /* If this block is dominated by a single incoming edge and that edge
> @@ -450,7 +420,7 @@ uncprop_dom_walker::before_dom_children (basic_block bb)
>    parent = get_immediate_dominator (CDI_DOMINATORS, bb);
>    if (parent)
>      {
> -      e = single_incoming_edge_ignoring_loop_edges (bb);
> +      edge e = single_incoming_edge_ignoring_loop_edges (bb, false);
>
>        if (e && e->src == parent && e->aux)
>         {
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index 63ee156..39e9156 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -10970,33 +10970,17 @@ evrp_dom_walker::try_find_new_range (tree name,
>  edge
>  evrp_dom_walker::before_dom_children (basic_block bb)
>  {
> -  tree op0 = NULL_TREE;
> -  edge_iterator ei;
> -  edge e;
> -
>    if (dump_file && (dump_flags & TDF_DETAILS))
>      fprintf (dump_file, "Visiting BB%d\n", bb->index);
>
>    stack.safe_push (std::make_pair (NULL_TREE, (value_range *)NULL));
>
> -  edge pred_e = NULL;
> -  FOR_EACH_EDGE (e, ei, bb->preds)
> -    {
> -      /* Ignore simple backedges from this to allow recording conditions
> -        in loop headers.  */
> -      if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
> -       continue;
> -      if (! pred_e)
> -       pred_e = e;
> -      else
> -       {
> -         pred_e = NULL;
> -         break;
> -       }
> -    }
> +  edge pred_e = single_incoming_edge_ignoring_loop_edges (bb, false);
>    if (pred_e)
>      {
>        gimple *stmt = last_stmt (pred_e->src);
> +      tree op0 = NULL_TREE;
> +
>        if (stmt
>           && gimple_code (stmt) == GIMPLE_COND
>           && (op0 = gimple_cond_lhs (stmt))
> @@ -11040,6 +11024,8 @@ evrp_dom_walker::before_dom_children (basic_block
> bb)
>
>    /* Visit PHI stmts and discover any new VRs possible.  */
>    bool has_unvisited_preds = false;
> +  edge_iterator ei;
> +  edge e;
>    FOR_EACH_EDGE (e, ei, bb->preds)
>      if (e->flags & EDGE_EXECUTABLE
>         && !(e->src->flags & BB_VISITED))
>

Re: [RFA][PATCH] Refactor duplicated code used by various dom walkers

[Jeff Law]

On 11/03/2017 04:05 AM, Richard Biener wrote:
> On Fri, Nov 3, 2017 at 4:49 AM, Jeff Law <law@redhat.com> wrote:
>>
>>
>>
>> Several passes which perform dominator walks want to identify when block has
>> a single incoming edge, ignoring loop backedges.
>>
>> I'm aware of 4 implementations of this code.  3 of the 4 are identical in
>> function.  The 4th (tree-ssa-dom.c) has an additional twist that it also
>> ignores edges that are not marked as executable.
>>
>> So I've taken the more general implementation from tree-ssa-dom.c and
>> conditionalized the handling of unexecutable edges on a flag and moved the
>> implementation into cfganal.c where it more naturally belongs.
>>
>> Bootstrapped and regression tested on x86_64.  OK for the trunk?
> 
> Minor nits (sorry...)
No need to apologize.  I'm always appreciative of feedback as it 
consistently improves what ultimately lands in the tree.


> 
>> Jeff
>>
>>          * cfganal.c (single_incoming_edge_ignoring_loop_edges): New function
>>          extracted from tree-ssa-dom.c.
>>          * cfganal.h (single_incoming_edge_ignoring_loop_edges): Prototype.
>>          * tree-ssa-dom.c (single_incoming_edge_ignoring_loop_edges): Remove.
>>          (record_equivalences_from_incoming_edge): Add additional argument
>>          to single_incoming_edge_ignoring_loop_edges call.
>>          * tree-ssa-uncprop.c (single_incoming_edge_ignoring_loop_edges):
>> Remove.
>>          (uncprop_dom_walker::before_dom_children): Add additional argument
>>          to single_incoming_edge_ignoring_loop_edges call.
>>          * tree-ssa-sccvn.c (sccvn_dom_walker::before_dom_children): Use
>>          single_incoming_edge_ignoring_loop_edges rather than open coding.
>>          * tree-vrp.c (evrp_dom_walker::before_dom_children): Similarly.
>>
>>
>>
>>
>>
>> diff --git a/gcc/cfganal.c b/gcc/cfganal.c
>> index c506067..14d94b2 100644
>> --- a/gcc/cfganal.c
>> +++ b/gcc/cfganal.c
>> @@ -1554,3 +1554,38 @@ single_pred_before_succ_order (void)
>>   #undef MARK_VISITED
>>   #undef VISITED_P
>>   }
>> +
>> +/* Ignoring loop backedges, if BB has precisely one incoming edge then
>> +   return that edge.  Otherwise return NULL.  */
>> +edge
>> +single_incoming_edge_ignoring_loop_edges (basic_block bb,
>> +                                         bool ignore_unreachable)
> 
> single_pred_edge_ignoring_loop_edges and ignore_not_executable
> 
> to better match existing CFG functions and actual edge flag use.
> 
> Ok with that change.
Sure.  Easy to change.

Jeff

Re: [RFA][PATCH] Refactor duplicated code used by various dom walkers

[Jeff Law]

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

On 11/03/2017 09:01 AM, Jeff Law wrote:
> On 11/03/2017 04:05 AM, Richard Biener wrote:
>> On Fri, Nov 3, 2017 at 4:49 AM, Jeff Law <law@redhat.com> wrote:
>>>
>>>
>>>
>>> Several passes which perform dominator walks want to identify when 
>>> block has
>>> a single incoming edge, ignoring loop backedges.
>>>
>>> I'm aware of 4 implementations of this code.  3 of the 4 are 
>>> identical in
>>> function.  The 4th (tree-ssa-dom.c) has an additional twist that it also
>>> ignores edges that are not marked as executable.
>>>
>>> So I've taken the more general implementation from tree-ssa-dom.c and
>>> conditionalized the handling of unexecutable edges on a flag and 
>>> moved the
>>> implementation into cfganal.c where it more naturally belongs.
>>>
>>> Bootstrapped and regression tested on x86_64.  OK for the trunk?
>>
>> Minor nits (sorry...)
> No need to apologize.  I'm always appreciative of feedback as it 
> consistently improves what ultimately lands in the tree.
> 
> 
>>
>>> Jeff
>>>
>>>          * cfganal.c (single_incoming_edge_ignoring_loop_edges): New 
>>> function
>>>          extracted from tree-ssa-dom.c.
>>>          * cfganal.h (single_incoming_edge_ignoring_loop_edges): 
>>> Prototype.
>>>          * tree-ssa-dom.c (single_incoming_edge_ignoring_loop_edges): 
>>> Remove.
>>>          (record_equivalences_from_incoming_edge): Add additional 
>>> argument
>>>          to single_incoming_edge_ignoring_loop_edges call.
>>>          * tree-ssa-uncprop.c 
>>> (single_incoming_edge_ignoring_loop_edges):
>>> Remove.
>>>          (uncprop_dom_walker::before_dom_children): Add additional 
>>> argument
>>>          to single_incoming_edge_ignoring_loop_edges call.
>>>          * tree-ssa-sccvn.c (sccvn_dom_walker::before_dom_children): Use
>>>          single_incoming_edge_ignoring_loop_edges rather than open 
>>> coding.
>>>          * tree-vrp.c (evrp_dom_walker::before_dom_children): Similarly.
>>>
>>>
>>>
>>>
>>>
>>> diff --git a/gcc/cfganal.c b/gcc/cfganal.c
>>> index c506067..14d94b2 100644
>>> --- a/gcc/cfganal.c
>>> +++ b/gcc/cfganal.c
>>> @@ -1554,3 +1554,38 @@ single_pred_before_succ_order (void)
>>>   #undef MARK_VISITED
>>>   #undef VISITED_P
>>>   }
>>> +
>>> +/* Ignoring loop backedges, if BB has precisely one incoming edge then
>>> +   return that edge.  Otherwise return NULL.  */
>>> +edge
>>> +single_incoming_edge_ignoring_loop_edges (basic_block bb,
>>> +                                         bool ignore_unreachable)
>>
>> single_pred_edge_ignoring_loop_edges and ignore_not_executable
>>
>> to better match existing CFG functions and actual edge flag use.
>>
>> Ok with that change.
> Sure.  Easy to change.
Final patch attached for archival purposes.  I took the liberty of also 
documenting the new IGNORE_NOT_EXECUTABLE argument.

Jeff

[-- Attachment #2: P --]
[-- Type: text/plain, Size: 10377 bytes --]

commit 1477a5a7a0a0a93cb8b1c79581134b8ccdca072b
Author: law <law@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Fri Nov 3 16:28:28 2017 +0000

            * cfganal.c (single_pred_edge_ignoring_loop_edges): New function
            extracted from tree-ssa-dom.c.
            * cfganal.h (single_pred_edge_ignoring_loop_edges): Prototype.
            * tree-ssa-dom.c (single_incoming_edge_ignoring_loop_edges): Remove.
            (record_equivalences_from_incoming_edge): Add additional argument
            to single_pred_edge_ignoring_loop_edges call.
            * tree-ssa-uncprop.c (single_incoming_edge_ignoring_loop_edges): Remove.
            (uncprop_dom_walker::before_dom_children): Add additional argument
            to single_pred_edge_ignoring_loop_edges call.
            * tree-ssa-sccvn.c (sccvn_dom_walker::before_dom_children): Use
            single_pred_edge_ignoring_loop_edges rather than open coding.
            * tree-vrp.c (evrp_dom_walker::before_dom_children): Similarly.
    
    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@254383 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 83dbaaaa8bf..2fc7db44f7b 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,18 @@
+2017-11-03  Jeff Law  <law@redhat.com>
+
+	* cfganal.c (single_pred_edge_ignoring_loop_edges): New function
+	extracted from tree-ssa-dom.c.
+	* cfganal.h (single_pred_edge_ignoring_loop_edges): Prototype.
+	* tree-ssa-dom.c (single_incoming_edge_ignoring_loop_edges): Remove.
+	(record_equivalences_from_incoming_edge): Add additional argument
+	to single_pred_edge_ignoring_loop_edges call.
+	* tree-ssa-uncprop.c (single_incoming_edge_ignoring_loop_edges): Remove.
+	(uncprop_dom_walker::before_dom_children): Add additional argument
+	to single_pred_edge_ignoring_loop_edges call.
+	* tree-ssa-sccvn.c (sccvn_dom_walker::before_dom_children): Use
+	single_pred_edge_ignoring_loop_edges rather than open coding.
+	* tree-vrp.c (evrp_dom_walker::before_dom_children): Similarly.
+
 2017-11-03  Marc Glisse  <marc.glisse@inria.fr>
 
 	* match.pd (-(-A)): Rewrite.
diff --git a/gcc/cfganal.c b/gcc/cfganal.c
index c506067fdcd..8bf8a53fa58 100644
--- a/gcc/cfganal.c
+++ b/gcc/cfganal.c
@@ -1554,3 +1554,42 @@ single_pred_before_succ_order (void)
 #undef MARK_VISITED
 #undef VISITED_P
 }
+
+/* Ignoring loop backedges, if BB has precisely one incoming edge then
+   return that edge.  Otherwise return NULL.
+
+   When IGNORE_NOT_EXECUTABLE is true, also ignore edges that are not marked
+   as executable.  */
+
+edge
+single_pred_edge_ignoring_loop_edges (basic_block bb,
+				      bool ignore_not_executable)
+{
+  edge retval = NULL;
+  edge e;
+  edge_iterator ei;
+
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    {
+      /* A loop back edge can be identified by the destination of
+	 the edge dominating the source of the edge.  */
+      if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
+	continue;
+
+      /* We can safely ignore edges that are not executable.  */
+      if (ignore_not_executable
+	  && (e->flags & EDGE_EXECUTABLE) == 0)
+	continue;
+
+      /* If we have already seen a non-loop edge, then we must have
+	 multiple incoming non-loop edges and thus we return NULL.  */
+      if (retval)
+	return NULL;
+
+      /* This is the first non-loop incoming edge we have found.  Record
+	 it.  */
+      retval = e;
+    }
+
+  return retval;
+}
diff --git a/gcc/cfganal.h b/gcc/cfganal.h
index 39bb5e547a5..c5cb51d9cf8 100644
--- a/gcc/cfganal.h
+++ b/gcc/cfganal.h
@@ -77,5 +77,8 @@ extern void bitmap_intersection_of_preds (sbitmap, sbitmap *, basic_block);
 extern void bitmap_union_of_succs (sbitmap, sbitmap *, basic_block);
 extern void bitmap_union_of_preds (sbitmap, sbitmap *, basic_block);
 extern basic_block * single_pred_before_succ_order (void);
+extern edge single_incoming_edge_ignoring_loop_edges (basic_block, bool);
+extern edge single_pred_edge_ignoring_loop_edges (basic_block, bool);
+
 
 #endif /* GCC_CFGANAL_H */
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index 06be69a530c..eb85b4a09ad 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -113,7 +113,6 @@ static void eliminate_redundant_computations (gimple_stmt_iterator *,
 					      class avail_exprs_stack *);
 static void record_equivalences_from_stmt (gimple *, int,
 					   class avail_exprs_stack *);
-static edge single_incoming_edge_ignoring_loop_edges (basic_block);
 static void dump_dominator_optimization_stats (FILE *file,
 					       hash_table<expr_elt_hasher> *);
 
@@ -1057,39 +1056,6 @@ record_equivalences_from_phis (basic_block bb)
     }
 }
 
-/* Ignoring loop backedges, if BB has precisely one incoming edge then
-   return that edge.  Otherwise return NULL.  */
-static edge
-single_incoming_edge_ignoring_loop_edges (basic_block bb)
-{
-  edge retval = NULL;
-  edge e;
-  edge_iterator ei;
-
-  FOR_EACH_EDGE (e, ei, bb->preds)
-    {
-      /* A loop back edge can be identified by the destination of
-	 the edge dominating the source of the edge.  */
-      if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
-	continue;
-
-      /* We can safely ignore edges that are not executable.  */
-      if ((e->flags & EDGE_EXECUTABLE) == 0)
-	continue;
-
-      /* If we have already seen a non-loop edge, then we must have
-	 multiple incoming non-loop edges and thus we return NULL.  */
-      if (retval)
-	return NULL;
-
-      /* This is the first non-loop incoming edge we have found.  Record
-	 it.  */
-      retval = e;
-    }
-
-  return retval;
-}
-
 /* Record any equivalences created by the incoming edge to BB into
    CONST_AND_COPIES and AVAIL_EXPRS_STACK.  If BB has more than one
    incoming edge, then no equivalence is created.  */
@@ -1107,7 +1073,7 @@ record_equivalences_from_incoming_edge (basic_block bb,
      the parent was followed.  */
   parent = get_immediate_dominator (CDI_DOMINATORS, bb);
 
-  e = single_incoming_edge_ignoring_loop_edges (bb);
+  e = single_pred_edge_ignoring_loop_edges (bb, true);
 
   /* If we had a single incoming edge from our parent block, then enter
      any data associated with the edge into our tables.  */
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index 306080b6a41..f5bc28efa70 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -4847,34 +4847,18 @@ sccvn_dom_walker::after_dom_children (basic_block bb)
 edge
 sccvn_dom_walker::before_dom_children (basic_block bb)
 {
-  edge e;
-  edge_iterator ei;
-
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "Visiting BB %d\n", bb->index);
 
   /* If we have a single predecessor record the equivalence from a
      possible condition on the predecessor edge.  */
-  edge pred_e = NULL;
-  FOR_EACH_EDGE (e, ei, bb->preds)
-    {
-      /* Ignore simple backedges from this to allow recording conditions
-         in loop headers.  */
-      if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
-	continue;
-      if (! pred_e)
-	pred_e = e;
-      else
-	{
-	  pred_e = NULL;
-	  break;
-	}
-    }
+  edge pred_e = single_pred_edge_ignoring_loop_edges (bb, false);
   if (pred_e)
     {
       /* Check if there are multiple executable successor edges in
 	 the source block.  Otherwise there is no additional info
 	 to be recorded.  */
+      edge_iterator ei;
       edge e2;
       FOR_EACH_EDGE (e2, ei, pred_e->src->succs)
 	if (e2 != pred_e
diff --git a/gcc/tree-ssa-uncprop.c b/gcc/tree-ssa-uncprop.c
index 200ec70c9b7..35a49d28420 100644
--- a/gcc/tree-ssa-uncprop.c
+++ b/gcc/tree-ssa-uncprop.c
@@ -408,40 +408,10 @@ uncprop_into_successor_phis (basic_block bb)
     }
 }
 
-/* Ignoring loop backedges, if BB has precisely one incoming edge then
-   return that edge.  Otherwise return NULL.  */
-static edge
-single_incoming_edge_ignoring_loop_edges (basic_block bb)
-{
-  edge retval = NULL;
-  edge e;
-  edge_iterator ei;
-
-  FOR_EACH_EDGE (e, ei, bb->preds)
-    {
-      /* A loop back edge can be identified by the destination of
-	 the edge dominating the source of the edge.  */
-      if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
-	continue;
-
-      /* If we have already seen a non-loop edge, then we must have
-	 multiple incoming non-loop edges and thus we return NULL.  */
-      if (retval)
-	return NULL;
-
-      /* This is the first non-loop incoming edge we have found.  Record
-	 it.  */
-      retval = e;
-    }
-
-  return retval;
-}
-
 edge
 uncprop_dom_walker::before_dom_children (basic_block bb)
 {
   basic_block parent;
-  edge e;
   bool recorded = false;
 
   /* If this block is dominated by a single incoming edge and that edge
@@ -450,7 +420,7 @@ uncprop_dom_walker::before_dom_children (basic_block bb)
   parent = get_immediate_dominator (CDI_DOMINATORS, bb);
   if (parent)
     {
-      e = single_incoming_edge_ignoring_loop_edges (bb);
+      edge e = single_pred_edge_ignoring_loop_edges (bb, false);
 
       if (e && e->src == parent && e->aux)
 	{
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 63ee1568990..541c5c4eaf9 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -10970,33 +10970,17 @@ evrp_dom_walker::try_find_new_range (tree name,
 edge
 evrp_dom_walker::before_dom_children (basic_block bb)
 {
-  tree op0 = NULL_TREE;
-  edge_iterator ei;
-  edge e;
-
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "Visiting BB%d\n", bb->index);
 
   stack.safe_push (std::make_pair (NULL_TREE, (value_range *)NULL));
 
-  edge pred_e = NULL;
-  FOR_EACH_EDGE (e, ei, bb->preds)
-    {
-      /* Ignore simple backedges from this to allow recording conditions
-	 in loop headers.  */
-      if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
-	continue;
-      if (! pred_e)
-	pred_e = e;
-      else
-	{
-	  pred_e = NULL;
-	  break;
-	}
-    }
+  edge pred_e = single_pred_edge_ignoring_loop_edges (bb, false);
   if (pred_e)
     {
       gimple *stmt = last_stmt (pred_e->src);
+      tree op0 = NULL_TREE;
+
       if (stmt
 	  && gimple_code (stmt) == GIMPLE_COND
 	  && (op0 = gimple_cond_lhs (stmt))
@@ -11040,6 +11024,8 @@ evrp_dom_walker::before_dom_children (basic_block bb)
 
   /* Visit PHI stmts and discover any new VRs possible.  */
   bool has_unvisited_preds = false;
+  edge_iterator ei;
+  edge e;
   FOR_EACH_EDGE (e, ei, bb->preds)
     if (e->flags & EDGE_EXECUTABLE
 	&& !(e->src->flags & BB_VISITED))