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

gcc/ChangeLog:
	PR tree-optimization/83312
	* domwalk.h (dom_walker::dom_walker): Fix typo in comment.
	* tree-cfg.c (find_taken_edge): Update to handle NULL_TREE for
	"val" param, and to cope with arbitrary basic blocks.
	(find_taken_edge_cond_expr): Add "cond_stmt" param and use it to
	handle NULL_TREE for "val", dropping "bb" param.
	(find_taken_edge_switch_expr): Make "switch_stmt" param const and
	drop "bb" param.  Handle NULL_TREE for "val".
	(find_case_label_for_value): Make "switch_stmt" param const.
	* 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 via dominator walk.

gcc/testsuite/ChangeLog:
	PR tree-optimization/83312
	* gcc.dg/pr83312.c: New test case.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@255649 138bc75d-0d04-0410-961f-82ee72b054a4

6 files changed, 152 insertions, 58 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 8753aa0e4ec..7473263a62c 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,21 @@
+2017-12-14  David Malcolm  <dmalcolm@redhat.com>
+
+	PR tree-optimization/83312
+	* domwalk.h (dom_walker::dom_walker): Fix typo in comment.
+	* tree-cfg.c (find_taken_edge): Update to handle NULL_TREE for
+	"val" param, and to cope with arbitrary basic blocks.
+	(find_taken_edge_cond_expr): Add "cond_stmt" param and use it to
+	handle NULL_TREE for "val", dropping "bb" param.
+	(find_taken_edge_switch_expr): Make "switch_stmt" param const and
+	drop "bb" param.  Handle NULL_TREE for "val".
+	(find_case_label_for_value): Make "switch_stmt" param const.
+	* 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 via dominator walk.
+
 2017-12-14  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>
 
 	* config/arm/arm.opt (mverbose-cost-dump): New option.
diff --git a/gcc/domwalk.h b/gcc/domwalk.h
index 6ac93eb06ad..c7e3450cf94 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/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index f87fb481899..81d28f1adb6 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2017-12-14  David Malcolm  <dmalcolm@redhat.com>
+
+	PR tree-optimization/83312
+	* gcc.dg/pr83312.c: New test case.
+
 2017-12-14  Eric Botcazou  <ebotcazou@adacore.com>
 
 	* gnat.dg/alignment13.adb: New test.
diff --git a/gcc/testsuite/gcc.dg/pr83312.c b/gcc/testsuite/gcc.dg/pr83312.c
new file mode 100644
index 00000000000..2eb241dfdfe
--- /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-cfg.c b/gcc/tree-cfg.c
index 75a0a302e96..3b16c101a6f 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -170,9 +170,9 @@ static void gimple_merge_blocks (basic_block, basic_block);
 static bool gimple_can_merge_blocks_p (basic_block, basic_block);
 static void remove_bb (basic_block);
 static edge find_taken_edge_computed_goto (basic_block, tree);
-static edge find_taken_edge_cond_expr (basic_block, tree);
-static edge find_taken_edge_switch_expr (gswitch *, basic_block, tree);
-static tree find_case_label_for_value (gswitch *, tree);
+static edge find_taken_edge_cond_expr (const gcond *, tree);
+static edge find_taken_edge_switch_expr (const gswitch *, tree);
+static tree find_case_label_for_value (const gswitch *, tree);
 static void lower_phi_internal_fn ();
 
 void
@@ -2278,9 +2278,12 @@ remove_bb (basic_block bb)
 }
 
 
-/* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
-   predicate VAL, return the edge that will be taken out of the block.
-   If VAL does not match a unique edge, NULL is returned.  */
+/* Given a basic block BB and a value VAL for use in the final statement
+   of the block (if a GIMPLE_COND, GIMPLE_SWITCH, or computed goto), return
+   the edge that will be taken out of the block.
+   If VAL is NULL_TREE, then the current value of the final statement's
+   predicate or index is used.
+   If the value does not match a unique edge, NULL is returned.  */
 
 edge
 find_taken_edge (basic_block bb, tree val)
@@ -2289,13 +2292,15 @@ find_taken_edge (basic_block bb, tree val)
 
   stmt = last_stmt (bb);
 
-  gcc_assert (is_ctrl_stmt (stmt));
+  /* Handle ENTRY and EXIT.  */
+  if (!stmt)
+    return NULL;
 
   if (gimple_code (stmt) == GIMPLE_COND)
-    return find_taken_edge_cond_expr (bb, val);
+    return find_taken_edge_cond_expr (as_a <gcond *> (stmt), val);
 
   if (gimple_code (stmt) == GIMPLE_SWITCH)
-    return find_taken_edge_switch_expr (as_a <gswitch *> (stmt), bb, val);
+    return find_taken_edge_switch_expr (as_a <gswitch *> (stmt), val);
 
   if (computed_goto_p (stmt))
     {
@@ -2309,10 +2314,10 @@ find_taken_edge (basic_block bb, tree val)
 	  && (TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
 	  && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
 	return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
-      return NULL;
     }
 
-  gcc_unreachable ();
+  /* Otherwise we only know the taken successor edge if it's unique.  */
+  return single_succ_p (bb) ? single_succ_edge (bb) : NULL;
 }
 
 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
@@ -2335,31 +2340,44 @@ find_taken_edge_computed_goto (basic_block bb, tree val)
   return e;
 }
 
-/* Given a constant value VAL and the entry block BB to a COND_EXPR
-   statement, determine which of the two edges will be taken out of the
-   block.  Return NULL if either edge may be taken.  */
+/* Given COND_STMT and a constant value VAL for use as the predicate,
+   determine which of the two edges will be taken out of
+   the statement's block.  Return NULL if either edge may be taken.
+   If VAL is NULL_TREE, then the current value of COND_STMT's predicate
+   is used.  */
 
 static edge
-find_taken_edge_cond_expr (basic_block bb, tree val)
+find_taken_edge_cond_expr (const gcond *cond_stmt, tree val)
 {
   edge true_edge, false_edge;
 
-  if (val == NULL
-      || TREE_CODE (val) != INTEGER_CST)
+  if (val == NULL_TREE)
+    {
+      /* Use the current value of the predicate.  */
+      if (gimple_cond_true_p (cond_stmt))
+	val = integer_one_node;
+      else if (gimple_cond_false_p (cond_stmt))
+	val = integer_zero_node;
+      else
+	return NULL;
+    }
+  else if (TREE_CODE (val) != INTEGER_CST)
     return NULL;
 
-  extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
+  extract_true_false_edges_from_block (gimple_bb (cond_stmt),
+				       &true_edge, &false_edge);
 
   return (integer_zerop (val) ? false_edge : true_edge);
 }
 
-/* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
-   statement, determine which edge will be taken out of the block.  Return
-   NULL if any edge may be taken.  */
+/* Given SWITCH_STMT and an INTEGER_CST VAL for use as the index, determine
+   which edge will be taken out of the statement's block.  Return NULL if any
+   edge may be taken.
+   If VAL is NULL_TREE, then the current value of SWITCH_STMT's index
+   is used.  */
 
 static edge
-find_taken_edge_switch_expr (gswitch *switch_stmt, basic_block bb,
-			     tree val)
+find_taken_edge_switch_expr (const gswitch *switch_stmt, tree val)
 {
   basic_block dest_bb;
   edge e;
@@ -2367,13 +2385,18 @@ find_taken_edge_switch_expr (gswitch *switch_stmt, basic_block bb,
 
   if (gimple_switch_num_labels (switch_stmt) == 1)
     taken_case = gimple_switch_default_label (switch_stmt);
-  else if (! val || TREE_CODE (val) != INTEGER_CST)
-    return NULL;
   else
-    taken_case = find_case_label_for_value (switch_stmt, val);
+    {
+      if (val == NULL_TREE)
+	val = gimple_switch_index (switch_stmt);
+      if (TREE_CODE (val) != INTEGER_CST)
+	return NULL;
+      else
+	taken_case = find_case_label_for_value (switch_stmt, val);
+    }
   dest_bb = label_to_block (CASE_LABEL (taken_case));
 
-  e = find_edge (bb, dest_bb);
+  e = find_edge (gimple_bb (switch_stmt), dest_bb);
   gcc_assert (e);
   return e;
 }
@@ -2384,7 +2407,7 @@ find_taken_edge_switch_expr (gswitch *switch_stmt, basic_block bb,
    sorted: We can do a binary search for a case matching VAL.  */
 
 static tree
-find_case_label_for_value (gswitch *switch_stmt, tree val)
+find_case_label_for_value (const gswitch *switch_stmt, tree val)
 {
   size_t low, high, n = gimple_switch_num_labels (switch_stmt);
   tree default_case = gimple_switch_default_label (switch_stmt);
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 7df6f244657..8fa8616c795 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -5000,44 +5000,62 @@ 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.
 
-	  memset (&wi, 0, sizeof (wi));
+   Walk over all statements of BB and call check_array_bounds on them,
+   and determine if there's a unique successor edge.  */
 
-	  wi.info = this;
+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;
 
-	  walk_gimple_op (gsi_stmt (si),
-			  check_array_bounds,
-			  &wi);
-	}
+      memset (&wi, 0, sizeof (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).  */
+  return find_taken_edge (bb, NULL_TREE);
+}
+
+/* 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