vrp_prop: Use dom_walker for -Warray-bounds (PR tree-optimization/83312)

Message ID 1513111838-37626-1-git-send-email-dmalcolm@redhat.com
State New
Headers show
Series
  • vrp_prop: Use dom_walker for -Warray-bounds (PR tree-optimization/83312)
Related show

Commit Message

David Malcolm Dec. 12, 2017, 8:50 p.m.
PR tree-optimization/83312 reports a false positive from -Warray-bounds.
The root cause is that VRP both:

(a) updates a GIMPLE_COND to be always false, and

(b) updates an ARRAY_REF in the now-unreachable other path to use an
    ASSERT_EXPR with a negative index:
      def_stmt j_6 = ASSERT_EXPR <j_9, j_9 < 0>;

When vrp_prop::check_all_array_refs () runs, the CFG hasn't yet been
updated to take account of (a), and so a false positive is emitted
when (b) is encountered.

This patch fixes the false warning by converting
  vrp_prop::check_all_array_refs
from a simple iteration over all BBs to use a new dom_walker subclass,
using the "skip_unreachable_blocks = true" mechanism to avoid analyzing
(b).

There didn't seem to be a pre-existing way to determine the unique
out-edge after a GIMPLE_COND (if it has a constant cond), so I added
a new gimple_cond_get_unique_successor_edge function.  Similarly,
something similar may apply for switches, so I put in a
gimple_get_unique_successor_edge (though I wasn't able to create a
reproducer that used a switch).

Successfully bootstrapped&regrtested on x86_64-pc-linux-gnu.

OK for trunk?

gcc/ChangeLog:
	PR tree-optimization/83312
	* domwalk.h (dom_walker::dom_walker): Fix typo in comment.
	* gimple.c: Include "tree-cfg.h".
	(gimple_get_unique_successor_edge): New function.
	(gimple_cond_get_unique_successor_edge): New function.
	* gimple.h (gimple_get_unique_successor_edge): New decl.
	(gimple_cond_get_unique_successor_edge): New decl.
	* tree-vrp.c (class check_array_bounds_dom_walker): New subclass
	of dom_walker.
	(vrp_prop::check_all_array_refs): Reimplement as...
	(check_array_bounds_dom_walker::before_dom_children): ...this new
	vfunc.  Replace linear search through BB block list, excluding
	those with non-executable in-edges, with dominator walk.

gcc/testsuite/ChangeLog:
	PR tree-optimization/83312
	* gcc.dg/pr83312.c: New test case.
---
 gcc/domwalk.h                  |  2 +-
 gcc/gimple.c                   | 36 +++++++++++++++++++
 gcc/gimple.h                   |  2 ++
 gcc/testsuite/gcc.dg/pr83312.c | 30 ++++++++++++++++
 gcc/tree-vrp.c                 | 80 +++++++++++++++++++++++++++---------------
 5 files changed, 120 insertions(+), 30 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/pr83312.c

-- 
1.8.5.3

Comments

Richard Biener Dec. 13, 2017, 10:06 a.m. | #1
On December 12, 2017 9:50:38 PM GMT+01:00, David Malcolm <dmalcolm@redhat.com> wrote:
>PR tree-optimization/83312 reports a false positive from

>-Warray-bounds.

>The root cause is that VRP both:

>

>(a) updates a GIMPLE_COND to be always false, and

>

>(b) updates an ARRAY_REF in the now-unreachable other path to use an

>    ASSERT_EXPR with a negative index:

>      def_stmt j_6 = ASSERT_EXPR <j_9, j_9 < 0>;

>

>When vrp_prop::check_all_array_refs () runs, the CFG hasn't yet been

>updated to take account of (a), and so a false positive is emitted

>when (b) is encountered.

>

>This patch fixes the false warning by converting

>  vrp_prop::check_all_array_refs

>from a simple iteration over all BBs to use a new dom_walker subclass,

>using the "skip_unreachable_blocks = true" mechanism to avoid analyzing

>(b).

>

>There didn't seem to be a pre-existing way to determine the unique

>out-edge after a GIMPLE_COND (if it has a constant cond), so I added

>a new gimple_cond_get_unique_successor_edge function.  Similarly,

>something similar may apply for switches, so I put in a

>gimple_get_unique_successor_edge (though I wasn't able to create a

>reproducer that used a switch).

>

>Successfully bootstrapped&regrtested on x86_64-pc-linux-gnu.

>

>OK for trunk?


I don't like the GIMPLE.c bits a lot. Can't you use the existing known taken edge helper (too lazy to look up from my phone...) basically splitting out some code from cond processing in evrp for example? 

The Dom walk itself looks like a good solution to me. 

Richard. 

>gcc/ChangeLog:

>	PR tree-optimization/83312

>	* domwalk.h (dom_walker::dom_walker): Fix typo in comment.

>	* gimple.c: Include "tree-cfg.h".

>	(gimple_get_unique_successor_edge): New function.

>	(gimple_cond_get_unique_successor_edge): New function.

>	* gimple.h (gimple_get_unique_successor_edge): New decl.

>	(gimple_cond_get_unique_successor_edge): New decl.

>	* tree-vrp.c (class check_array_bounds_dom_walker): New subclass

>	of dom_walker.

>	(vrp_prop::check_all_array_refs): Reimplement as...

>	(check_array_bounds_dom_walker::before_dom_children): ...this new

>	vfunc.  Replace linear search through BB block list, excluding

>	those with non-executable in-edges, with dominator walk.

>

>gcc/testsuite/ChangeLog:

>	PR tree-optimization/83312

>	* gcc.dg/pr83312.c: New test case.

>---

> gcc/domwalk.h                  |  2 +-

> gcc/gimple.c                   | 36 +++++++++++++++++++

> gcc/gimple.h                   |  2 ++

> gcc/testsuite/gcc.dg/pr83312.c | 30 ++++++++++++++++

>gcc/tree-vrp.c                 | 80

>+++++++++++++++++++++++++++---------------

> 5 files changed, 120 insertions(+), 30 deletions(-)

> create mode 100644 gcc/testsuite/gcc.dg/pr83312.c

>

>diff --git a/gcc/domwalk.h b/gcc/domwalk.h

>index 6ac93eb..c7e3450 100644

>--- a/gcc/domwalk.h

>+++ b/gcc/domwalk.h

>@@ -32,7 +32,7 @@ class dom_walker

> public:

>   static const edge STOP;

> 

>-  /* Use SKIP_UNREACHBLE_BLOCKS = true when your client can discover

>+  /* Use SKIP_UNREACHABLE_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

>diff --git a/gcc/gimple.c b/gcc/gimple.c

>index c986a73..e22fcda 100644

>--- a/gcc/gimple.c

>+++ b/gcc/gimple.c

>@@ -44,6 +44,7 @@ along with GCC; see the file COPYING3.  If not see

> #include "stringpool.h"

> #include "attribs.h"

> #include "asan.h"

>+#include "tree-cfg.h"

> 

> 

>/* All the tuples have their operand vector (if present) at the very

>bottom

>@@ -3087,6 +3088,41 @@ gimple_inexpensive_call_p (gcall *stmt)

>   return false;

> }

> 

>+/* If STMT terminates its basic block, determine if it has a uniquely

>+   valid successor edge and if so return it.

>+

>+   Otherwise, return NULL.  */

>+

>+edge

>+gimple_get_unique_successor_edge (const gimple *stmt)

>+{

>+  switch (gimple_code (stmt))

>+    {

>+    case GIMPLE_COND:

>+      return gimple_cond_get_unique_successor_edge

>+	(as_a <const gcond *> (stmt));

>+    default:

>+      return NULL;

>+    }

>+}

>+

>+/* Determine if COND has a uniquely valid successor edge and if so

>return it.

>+

>+   Otherwise, return NULL.  */

>+

>+edge

>+gimple_cond_get_unique_successor_edge (const gcond *cond)

>+{

>+  edge te, fe;

>+  extract_true_false_edges_from_block (gimple_bb (cond), &te, &fe);

>+  if (gimple_cond_true_p (cond))

>+    return te;

>+  else if (gimple_cond_false_p (cond))

>+    return fe;

>+  else

>+    return NULL;

>+}

>+

> #if CHECKING_P

> 

> namespace selftest {

>diff --git a/gcc/gimple.h b/gcc/gimple.h

>index 0fcdd05..ab4cb8b 100644

>--- a/gcc/gimple.h

>+++ b/gcc/gimple.h

>@@ -1529,6 +1529,8 @@ extern void gimple_seq_discard (gimple_seq);

>extern void maybe_remove_unused_call_args (struct function *, gimple

>*);

> extern bool gimple_inexpensive_call_p (gcall *);

> extern bool stmt_can_terminate_bb_p (gimple *);

>+extern edge gimple_get_unique_successor_edge (const gimple *stmt);

>+extern edge gimple_cond_get_unique_successor_edge (const gcond *cond);

> 

>/* Formal (expression) temporary table handling: multiple occurrences

>of

>  the same scalar expression are evaluated into the same temporary.  */

>diff --git a/gcc/testsuite/gcc.dg/pr83312.c

>b/gcc/testsuite/gcc.dg/pr83312.c

>new file mode 100644

>index 0000000..2eb241d

>--- /dev/null

>+++ b/gcc/testsuite/gcc.dg/pr83312.c

>@@ -0,0 +1,30 @@

>+/* { dg-options "-O2 -Warray-bounds" } */

>+

>+struct ptlrpcd_ctl {

>+  char pc_name[20];

>+};

>+struct ptlrpcd {

>+  struct ptlrpcd_ctl pd_threads[6];

>+};

>+struct ptlrpcd *ptlrpcd_init_pd;

>+static void ptlrpcd_ctl_init(struct ptlrpcd_ctl *pc, int index) {

>+  if (index < 0)

>+    __builtin_snprintf(pc->pc_name, sizeof(pc->pc_name),

>"ptlrpcd_rcv");

>+  else

>+    __builtin_snprintf(pc->pc_name, sizeof(pc->pc_name), "ptlrpcd_%d",

>index);

>+}

>+int ptlrpcd_init_ncpts;

>+static int ptlrpcd_init(int nthreads) {

>+  int j;

>+  if (ptlrpcd_init_ncpts) {

>+    ptlrpcd_ctl_init(&ptlrpcd_init_pd->pd_threads[0], -1);

>+    for (j = 1; j < nthreads; j++)

>+      ptlrpcd_ctl_init(&ptlrpcd_init_pd->pd_threads[j], j);

>+  }

>+  return 0;

>+}

>+int ptlrpcd_init_groupsize;

>+void ptlrpcd_addref(void) {

>+    ptlrpcd_init(ptlrpcd_init_groupsize);

>+}

>+

>diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c

>index a86b382..67bc118 100644

>--- a/gcc/tree-vrp.c

>+++ b/gcc/tree-vrp.c

>@@ -5000,44 +5000,66 @@ check_array_bounds (tree *tp, int

>*walk_subtree, void *data)

>   return NULL_TREE;

> }

> 

>-/* Walk over all statements of all reachable BBs and call

>check_array_bounds

>-   on them.  */

>+/* A dom_walker subclass for use by vrp_prop::check_all_array_refs,

>+   to walk over all statements of all reachable BBs and call

>+   check_array_bounds on them.  */

> 

>-void

>-vrp_prop::check_all_array_refs ()

>+class check_array_bounds_dom_walker : public dom_walker

> {

>-  basic_block bb;

>-  gimple_stmt_iterator si;

>+ public:

>+  check_array_bounds_dom_walker (vrp_prop *prop)

>+    : dom_walker (CDI_DOMINATORS, true), m_prop (prop) {}

>+  ~check_array_bounds_dom_walker () {}

> 

>-  FOR_EACH_BB_FN (bb, cfun)

>-    {

>-      edge_iterator ei;

>-      edge e;

>-      bool executable = false;

>+  edge before_dom_children (basic_block) FINAL OVERRIDE;

> 

>-      /* Skip blocks that were found to be unreachable.  */

>-      FOR_EACH_EDGE (e, ei, bb->preds)

>-	executable |= !!(e->flags & EDGE_EXECUTABLE);

>-      if (!executable)

>-	continue;

>+ private:

>+  vrp_prop *m_prop;

>+};

> 

>-      for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))

>-	{

>-	  gimple *stmt = gsi_stmt (si);

>-	  struct walk_stmt_info wi;

>-	  if (!gimple_has_location (stmt)

>-	      || is_gimple_debug (stmt))

>-	    continue;

>+/* Implementation of dom_walker::before_dom_children.

>+

>+   Walk over all statements of BB and call check_array_bounds on them,

>+   and determine if there's a unique successor edge.  */

> 

>-	  memset (&wi, 0, sizeof (wi));

>+edge

>+check_array_bounds_dom_walker::before_dom_children (basic_block bb)

>+{

>+  gimple_stmt_iterator si;

>+  for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))

>+    {

>+      gimple *stmt = gsi_stmt (si);

>+      struct walk_stmt_info wi;

>+      if (!gimple_has_location (stmt)

>+	  || is_gimple_debug (stmt))

>+	continue;

> 

>-	  wi.info = this;

>+      memset (&wi, 0, sizeof (wi));

> 

>-	  walk_gimple_op (gsi_stmt (si),

>-			  check_array_bounds,

>-			  &wi);

>-	}

>+      wi.info = m_prop;

>+

>+      walk_gimple_op (stmt, check_array_bounds, &wi);

>     }

>+

>+  /* Determine if there's a unique successor edge, and if so, return

>+     that back to dom_walker, ensuring that we don't visit blocks that

>+     became unreachable during the VRP propagation

>+     (PR tree-optimization/83312).  */

>+  gimple *last = last_stmt (bb);

>+  if (last)

>+    return gimple_get_unique_successor_edge (last);

>+

>+  return NULL;

>+}

>+

>+/* Walk over all statements of all reachable BBs and call

>check_array_bounds

>+   on them.  */

>+

>+void

>+vrp_prop::check_all_array_refs ()

>+{

>+  check_array_bounds_dom_walker w (this);

>+  w.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));

> }

> 

> /* Return true if all imm uses of VAR are either in STMT, or
Jeff Law Dec. 13, 2017, 3:46 p.m. | #2
On 12/13/2017 03:06 AM, Richard Biener wrote:
> On December 12, 2017 9:50:38 PM GMT+01:00, David Malcolm <dmalcolm@redhat.com> wrote:

>> PR tree-optimization/83312 reports a false positive from

>> -Warray-bounds.

>> The root cause is that VRP both:

>>

>> (a) updates a GIMPLE_COND to be always false, and

>>

>> (b) updates an ARRAY_REF in the now-unreachable other path to use an

>>    ASSERT_EXPR with a negative index:

>>      def_stmt j_6 = ASSERT_EXPR <j_9, j_9 < 0>;

>>

>> When vrp_prop::check_all_array_refs () runs, the CFG hasn't yet been

>> updated to take account of (a), and so a false positive is emitted

>> when (b) is encountered.

>>

>> This patch fixes the false warning by converting

>>  vrp_prop::check_all_array_refs

>>from a simple iteration over all BBs to use a new dom_walker subclass,

>> using the "skip_unreachable_blocks = true" mechanism to avoid analyzing

>> (b).

>>

>> There didn't seem to be a pre-existing way to determine the unique

>> out-edge after a GIMPLE_COND (if it has a constant cond), so I added

>> a new gimple_cond_get_unique_successor_edge function.  Similarly,

>> something similar may apply for switches, so I put in a

>> gimple_get_unique_successor_edge (though I wasn't able to create a

>> reproducer that used a switch).

>>

>> Successfully bootstrapped&regrtested on x86_64-pc-linux-gnu.

>>

>> OK for trunk?

> 

> I don't like the GIMPLE.c bits a lot. Can't you use the existing known taken edge helper (too lazy to look up from my phone...) basically splitting out some code from cond processing in evrp for example? 

I'm not sure those bits are needed at all. I think the right things will
happen if we clear EDGE_EXECUTABLE on the appropriate edge in
vrp_folder::fold_predicate_in.

That should cause the block in question to become unreachable (zero
preds).  So later when we do the domwal dom_walker::walk will see the
block as unreachable -- which avoids walking into it and also triggers
the call to propagate_unreachable_to_edges which marks the outgoing
edges as not executable.

I think David's got to go back to some diagnostics/FE stuff, so I'll
probably be wrapping this up.

Thanks David!

jeff
David Malcolm Dec. 13, 2017, 4:02 p.m. | #3
On Wed, 2017-12-13 at 08:46 -0700, Jeff Law wrote:
> On 12/13/2017 03:06 AM, Richard Biener wrote:

> > On December 12, 2017 9:50:38 PM GMT+01:00, David Malcolm <dmalcolm@

> > redhat.com> wrote:

> > > PR tree-optimization/83312 reports a false positive from

> > > -Warray-bounds.

> > > The root cause is that VRP both:

> > > 

> > > (a) updates a GIMPLE_COND to be always false, and

> > > 

> > > (b) updates an ARRAY_REF in the now-unreachable other path to use

> > > an

> > >    ASSERT_EXPR with a negative index:

> > >      def_stmt j_6 = ASSERT_EXPR <j_9, j_9 < 0>;

> > > 

> > > When vrp_prop::check_all_array_refs () runs, the CFG hasn't yet

> > > been

> > > updated to take account of (a), and so a false positive is

> > > emitted

> > > when (b) is encountered.

> > > 

> > > This patch fixes the false warning by converting

> > >  vrp_prop::check_all_array_refs

> > > from a simple iteration over all BBs to use a new dom_walker

> > > subclass,

> > > using the "skip_unreachable_blocks = true" mechanism to avoid

> > > analyzing

> > > (b).

> > > 

> > > There didn't seem to be a pre-existing way to determine the

> > > unique

> > > out-edge after a GIMPLE_COND (if it has a constant cond), so I

> > > added

> > > a new gimple_cond_get_unique_successor_edge function.  Similarly,

> > > something similar may apply for switches, so I put in a

> > > gimple_get_unique_successor_edge (though I wasn't able to create

> > > a

> > > reproducer that used a switch).

> > > 

> > > Successfully bootstrapped&regrtested on x86_64-pc-linux-gnu.

> > > 

> > > OK for trunk?

> > 

> > I don't like the GIMPLE.c bits a lot. Can't you use the existing

> > known taken edge helper (too lazy to look up from my phone...)

> > basically splitting out some code from cond processing in evrp for

> > example? 

> 

> I'm not sure those bits are needed at all. I think the right things

> will

> happen if we clear EDGE_EXECUTABLE on the appropriate edge in

> vrp_folder::fold_predicate_in.

> 

> That should cause the block in question to become unreachable (zero

> preds).  So later when we do the domwal dom_walker::walk will see the

> block as unreachable -- which avoids walking into it and also

> triggers

> the call to propagate_unreachable_to_edges which marks the outgoing

> edges as not executable.


AIUI, dom_walker::bb_reachable only honors the EDGE_EXECUTABLE flags if
m_skip_unreachable_blocks is set on the dom_walker.

However, dom_walker's ctor clears all of the EDGE_EXECUTABLE if that
bool is set.

So, as written any edge flags that are touched in
vrp_folder::fold_predicate_in will get reset when the dom walker is
created.

So should the dom walker get created before the vrp_folder runs?

> I think David's got to go back to some diagnostics/FE stuff, so I'll

> probably be wrapping this up.

> 

> Thanks David!

> 

> jeff
Jeff Law Dec. 13, 2017, 4:18 p.m. | #4
On 12/13/2017 09:02 AM, David Malcolm wrote:
> On Wed, 2017-12-13 at 08:46 -0700, Jeff Law wrote:

>> On 12/13/2017 03:06 AM, Richard Biener wrote:

>>> On December 12, 2017 9:50:38 PM GMT+01:00, David Malcolm <dmalcolm@

>>> redhat.com> wrote:

>>>> PR tree-optimization/83312 reports a false positive from

>>>> -Warray-bounds.

>>>> The root cause is that VRP both:

>>>>

>>>> (a) updates a GIMPLE_COND to be always false, and

>>>>

>>>> (b) updates an ARRAY_REF in the now-unreachable other path to use

>>>> an

>>>>    ASSERT_EXPR with a negative index:

>>>>      def_stmt j_6 = ASSERT_EXPR <j_9, j_9 < 0>;

>>>>

>>>> When vrp_prop::check_all_array_refs () runs, the CFG hasn't yet

>>>> been

>>>> updated to take account of (a), and so a false positive is

>>>> emitted

>>>> when (b) is encountered.

>>>>

>>>> This patch fixes the false warning by converting

>>>>  vrp_prop::check_all_array_refs

>>>> from a simple iteration over all BBs to use a new dom_walker

>>>> subclass,

>>>> using the "skip_unreachable_blocks = true" mechanism to avoid

>>>> analyzing

>>>> (b).

>>>>

>>>> There didn't seem to be a pre-existing way to determine the

>>>> unique

>>>> out-edge after a GIMPLE_COND (if it has a constant cond), so I

>>>> added

>>>> a new gimple_cond_get_unique_successor_edge function.  Similarly,

>>>> something similar may apply for switches, so I put in a

>>>> gimple_get_unique_successor_edge (though I wasn't able to create

>>>> a

>>>> reproducer that used a switch).

>>>>

>>>> Successfully bootstrapped&regrtested on x86_64-pc-linux-gnu.

>>>>

>>>> OK for trunk?

>>>

>>> I don't like the GIMPLE.c bits a lot. Can't you use the existing

>>> known taken edge helper (too lazy to look up from my phone...)

>>> basically splitting out some code from cond processing in evrp for

>>> example? 

>>

>> I'm not sure those bits are needed at all. I think the right things

>> will

>> happen if we clear EDGE_EXECUTABLE on the appropriate edge in

>> vrp_folder::fold_predicate_in.

>>

>> That should cause the block in question to become unreachable (zero

>> preds).  So later when we do the domwal dom_walker::walk will see the

>> block as unreachable -- which avoids walking into it and also

>> triggers

>> the call to propagate_unreachable_to_edges which marks the outgoing

>> edges as not executable.

> 

> AIUI, dom_walker::bb_reachable only honors the EDGE_EXECUTABLE flags if

> m_skip_unreachable_blocks is set on the dom_walker.

> 

> However, dom_walker's ctor clears all of the EDGE_EXECUTABLE if that

> bool is set.

Ugh.  How unfortunate, though I understand why it would be written that way.

> 

> So, as written any edge flags that are touched in

> vrp_folder::fold_predicate_in will get reset when the dom walker is

> created.

> 

> So should the dom walker get created before the vrp_folder runs?

That would probably work, but something doesn't feel right about it.

Alternately we could to the dom_walker ctor that an initial state of
EDGE_EXECUTABLE is already set.

Jeff
Richard Biener Dec. 13, 2017, 4:24 p.m. | #5
On December 13, 2017 5:18:16 PM GMT+01:00, Jeff Law <law@redhat.com> wrote:
>On 12/13/2017 09:02 AM, David Malcolm wrote:

>> On Wed, 2017-12-13 at 08:46 -0700, Jeff Law wrote:

>>> On 12/13/2017 03:06 AM, Richard Biener wrote:

>>>> On December 12, 2017 9:50:38 PM GMT+01:00, David Malcolm <dmalcolm@

>>>> redhat.com> wrote:

>>>>> PR tree-optimization/83312 reports a false positive from

>>>>> -Warray-bounds.

>>>>> The root cause is that VRP both:

>>>>>

>>>>> (a) updates a GIMPLE_COND to be always false, and

>>>>>

>>>>> (b) updates an ARRAY_REF in the now-unreachable other path to use

>>>>> an

>>>>>    ASSERT_EXPR with a negative index:

>>>>>      def_stmt j_6 = ASSERT_EXPR <j_9, j_9 < 0>;

>>>>>

>>>>> When vrp_prop::check_all_array_refs () runs, the CFG hasn't yet

>>>>> been

>>>>> updated to take account of (a), and so a false positive is

>>>>> emitted

>>>>> when (b) is encountered.

>>>>>

>>>>> This patch fixes the false warning by converting

>>>>>  vrp_prop::check_all_array_refs

>>>>> from a simple iteration over all BBs to use a new dom_walker

>>>>> subclass,

>>>>> using the "skip_unreachable_blocks = true" mechanism to avoid

>>>>> analyzing

>>>>> (b).

>>>>>

>>>>> There didn't seem to be a pre-existing way to determine the

>>>>> unique

>>>>> out-edge after a GIMPLE_COND (if it has a constant cond), so I

>>>>> added

>>>>> a new gimple_cond_get_unique_successor_edge function.  Similarly,

>>>>> something similar may apply for switches, so I put in a

>>>>> gimple_get_unique_successor_edge (though I wasn't able to create

>>>>> a

>>>>> reproducer that used a switch).

>>>>>

>>>>> Successfully bootstrapped&regrtested on x86_64-pc-linux-gnu.

>>>>>

>>>>> OK for trunk?

>>>>

>>>> I don't like the GIMPLE.c bits a lot. Can't you use the existing

>>>> known taken edge helper (too lazy to look up from my phone...)

>>>> basically splitting out some code from cond processing in evrp for

>>>> example? 

>>>

>>> I'm not sure those bits are needed at all. I think the right things

>>> will

>>> happen if we clear EDGE_EXECUTABLE on the appropriate edge in

>>> vrp_folder::fold_predicate_in.

>>>

>>> That should cause the block in question to become unreachable (zero

>>> preds).  So later when we do the domwal dom_walker::walk will see

>the

>>> block as unreachable -- which avoids walking into it and also

>>> triggers

>>> the call to propagate_unreachable_to_edges which marks the outgoing

>>> edges as not executable.

>> 

>> AIUI, dom_walker::bb_reachable only honors the EDGE_EXECUTABLE flags

>if

>> m_skip_unreachable_blocks is set on the dom_walker.

>> 

>> However, dom_walker's ctor clears all of the EDGE_EXECUTABLE if that

>> bool is set.

>Ugh.  How unfortunate, though I understand why it would be written that

>way.

>

>> 

>> So, as written any edge flags that are touched in

>> vrp_folder::fold_predicate_in will get reset when the dom walker is

>> created.

>> 

>> So should the dom walker get created before the vrp_folder runs?

>That would probably work, but something doesn't feel right about it.

>

>Alternately we could to the dom_walker ctor that an initial state of

>EDGE_EXECUTABLE is already set.


I'm quite sure that wouldn't help for VRP. 
I think David's approach is fine just we don't need any other API to get at a known executable outgoing edge. We can improve the existing one or just add the trivial folding required. 

Richard. 

>Jeff
Michael Matz Dec. 13, 2017, 4:55 p.m. | #6
Hi,

On Tue, 12 Dec 2017, David Malcolm wrote:

> There didn't seem to be a pre-existing way to determine the unique

> out-edge after a GIMPLE_COND (if it has a constant cond), so I added

> a new gimple_cond_get_unique_successor_edge function.  Similarly,

> something similar may apply for switches, so I put in a

> gimple_get_unique_successor_edge (though I wasn't able to create a

> reproducer that used a switch).


Please instead extend find_taken_edge() (its sub routines).  E.g. let it 
accept a NULL val and initialize it with the cond from a gcond.


Ciao,
Michael.
Jeff Law Dec. 13, 2017, 5:30 p.m. | #7
On 12/13/2017 09:55 AM, Michael Matz wrote:
> Hi,

> 

> On Tue, 12 Dec 2017, David Malcolm wrote:

> 

>> There didn't seem to be a pre-existing way to determine the unique

>> out-edge after a GIMPLE_COND (if it has a constant cond), so I added

>> a new gimple_cond_get_unique_successor_edge function.  Similarly,

>> something similar may apply for switches, so I put in a

>> gimple_get_unique_successor_edge (though I wasn't able to create a

>> reproducer that used a switch).

> 

> Please instead extend find_taken_edge() (its sub routines).  E.g. let it 

> accept a NULL val and initialize it with the cond from a gcond.

Yea.  That seems like the best way to go.

Jeff
Jeff Law Dec. 13, 2017, 5:47 p.m. | #8
On 12/13/2017 09:24 AM, Richard Biener wrote:
>>

>> Alternately we could to the dom_walker ctor that an initial state of

>> EDGE_EXECUTABLE is already set.

> 

> I'm quite sure that wouldn't help for VRP. 

Not sure why.  But it's not worth digging deep into.

I do think the current structure could still fail to pick up some
secondary cases where blocks become unreachable as a result of both not
needing to visit during the lattice propagation step and the
substitution step.  But I'd expect this to be rare.

> I think David's approach is fine just we don't need any other API to get at a known executable outgoing edge. We can improve the existing one or just add the trivial folding required. 

I think Michael's suggestion to pass in NULL for the value and allow
find_edge to try and determine the value makes the most sense here.

Jeff

Patch

diff --git a/gcc/domwalk.h b/gcc/domwalk.h
index 6ac93eb..c7e3450 100644
--- a/gcc/domwalk.h
+++ b/gcc/domwalk.h
@@ -32,7 +32,7 @@  class dom_walker
 public:
   static const edge STOP;
 
-  /* Use SKIP_UNREACHBLE_BLOCKS = true when your client can discover
+  /* Use SKIP_UNREACHABLE_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
diff --git a/gcc/gimple.c b/gcc/gimple.c
index c986a73..e22fcda 100644
--- a/gcc/gimple.c
+++ b/gcc/gimple.c
@@ -44,6 +44,7 @@  along with GCC; see the file COPYING3.  If not see
 #include "stringpool.h"
 #include "attribs.h"
 #include "asan.h"
+#include "tree-cfg.h"
 
 
 /* All the tuples have their operand vector (if present) at the very bottom
@@ -3087,6 +3088,41 @@  gimple_inexpensive_call_p (gcall *stmt)
   return false;
 }
 
+/* If STMT terminates its basic block, determine if it has a uniquely
+   valid successor edge and if so return it.
+
+   Otherwise, return NULL.  */
+
+edge
+gimple_get_unique_successor_edge (const gimple *stmt)
+{
+  switch (gimple_code (stmt))
+    {
+    case GIMPLE_COND:
+      return gimple_cond_get_unique_successor_edge
+	(as_a <const gcond *> (stmt));
+    default:
+      return NULL;
+    }
+}
+
+/* Determine if COND has a uniquely valid successor edge and if so return it.
+
+   Otherwise, return NULL.  */
+
+edge
+gimple_cond_get_unique_successor_edge (const gcond *cond)
+{
+  edge te, fe;
+  extract_true_false_edges_from_block (gimple_bb (cond), &te, &fe);
+  if (gimple_cond_true_p (cond))
+    return te;
+  else if (gimple_cond_false_p (cond))
+    return fe;
+  else
+    return NULL;
+}
+
 #if CHECKING_P
 
 namespace selftest {
diff --git a/gcc/gimple.h b/gcc/gimple.h
index 0fcdd05..ab4cb8b 100644
--- a/gcc/gimple.h
+++ b/gcc/gimple.h
@@ -1529,6 +1529,8 @@  extern void gimple_seq_discard (gimple_seq);
 extern void maybe_remove_unused_call_args (struct function *, gimple *);
 extern bool gimple_inexpensive_call_p (gcall *);
 extern bool stmt_can_terminate_bb_p (gimple *);
+extern edge gimple_get_unique_successor_edge (const gimple *stmt);
+extern edge gimple_cond_get_unique_successor_edge (const gcond *cond);
 
 /* Formal (expression) temporary table handling: multiple occurrences of
    the same scalar expression are evaluated into the same temporary.  */
diff --git a/gcc/testsuite/gcc.dg/pr83312.c b/gcc/testsuite/gcc.dg/pr83312.c
new file mode 100644
index 0000000..2eb241d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr83312.c
@@ -0,0 +1,30 @@ 
+/* { dg-options "-O2 -Warray-bounds" } */
+
+struct ptlrpcd_ctl {
+  char pc_name[20];
+};
+struct ptlrpcd {
+  struct ptlrpcd_ctl pd_threads[6];
+};
+struct ptlrpcd *ptlrpcd_init_pd;
+static void ptlrpcd_ctl_init(struct ptlrpcd_ctl *pc, int index) {
+  if (index < 0)
+    __builtin_snprintf(pc->pc_name, sizeof(pc->pc_name), "ptlrpcd_rcv");
+  else
+    __builtin_snprintf(pc->pc_name, sizeof(pc->pc_name), "ptlrpcd_%d", index);
+}
+int ptlrpcd_init_ncpts;
+static int ptlrpcd_init(int nthreads) {
+  int j;
+  if (ptlrpcd_init_ncpts) {
+    ptlrpcd_ctl_init(&ptlrpcd_init_pd->pd_threads[0], -1);
+    for (j = 1; j < nthreads; j++)
+      ptlrpcd_ctl_init(&ptlrpcd_init_pd->pd_threads[j], j);
+  }
+  return 0;
+}
+int ptlrpcd_init_groupsize;
+void ptlrpcd_addref(void) {
+    ptlrpcd_init(ptlrpcd_init_groupsize);
+}
+
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index a86b382..67bc118 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -5000,44 +5000,66 @@  check_array_bounds (tree *tp, int *walk_subtree, void *data)
   return NULL_TREE;
 }
 
-/* Walk over all statements of all reachable BBs and call check_array_bounds
-   on them.  */
+/* A dom_walker subclass for use by vrp_prop::check_all_array_refs,
+   to walk over all statements of all reachable BBs and call
+   check_array_bounds on them.  */
 
-void
-vrp_prop::check_all_array_refs ()
+class check_array_bounds_dom_walker : public dom_walker
 {
-  basic_block bb;
-  gimple_stmt_iterator si;
+ public:
+  check_array_bounds_dom_walker (vrp_prop *prop)
+    : dom_walker (CDI_DOMINATORS, true), m_prop (prop) {}
+  ~check_array_bounds_dom_walker () {}
 
-  FOR_EACH_BB_FN (bb, cfun)
-    {
-      edge_iterator ei;
-      edge e;
-      bool executable = false;
+  edge before_dom_children (basic_block) FINAL OVERRIDE;
 
-      /* Skip blocks that were found to be unreachable.  */
-      FOR_EACH_EDGE (e, ei, bb->preds)
-	executable |= !!(e->flags & EDGE_EXECUTABLE);
-      if (!executable)
-	continue;
+ private:
+  vrp_prop *m_prop;
+};
 
-      for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
-	{
-	  gimple *stmt = gsi_stmt (si);
-	  struct walk_stmt_info wi;
-	  if (!gimple_has_location (stmt)
-	      || is_gimple_debug (stmt))
-	    continue;
+/* Implementation of dom_walker::before_dom_children.
+
+   Walk over all statements of BB and call check_array_bounds on them,
+   and determine if there's a unique successor edge.  */
 
-	  memset (&wi, 0, sizeof (wi));
+edge
+check_array_bounds_dom_walker::before_dom_children (basic_block bb)
+{
+  gimple_stmt_iterator si;
+  for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
+    {
+      gimple *stmt = gsi_stmt (si);
+      struct walk_stmt_info wi;
+      if (!gimple_has_location (stmt)
+	  || is_gimple_debug (stmt))
+	continue;
 
-	  wi.info = this;
+      memset (&wi, 0, sizeof (wi));
 
-	  walk_gimple_op (gsi_stmt (si),
-			  check_array_bounds,
-			  &wi);
-	}
+      wi.info = m_prop;
+
+      walk_gimple_op (stmt, check_array_bounds, &wi);
     }
+
+  /* Determine if there's a unique successor edge, and if so, return
+     that back to dom_walker, ensuring that we don't visit blocks that
+     became unreachable during the VRP propagation
+     (PR tree-optimization/83312).  */
+  gimple *last = last_stmt (bb);
+  if (last)
+    return gimple_get_unique_successor_edge (last);
+
+  return NULL;
+}
+
+/* Walk over all statements of all reachable BBs and call check_array_bounds
+   on them.  */
+
+void
+vrp_prop::check_all_array_refs ()
+{
+  check_array_bounds_dom_walker w (this);
+  w.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
 }
 
 /* Return true if all imm uses of VAR are either in STMT, or