PR middle-end/61409

	* tree-ssa-uninit.c: Define new global max_phi_args.
	(compute_uninit_opnds_pos): Use max_phi_args.
	(prune_uninit_phi_opnds): Same.
	(use_pred_not_overlap_with_undef_path_pred): Remove reference to
	missing NUM_PREDS in function comment.
	(can_one_predicate_be_invalidated_p): New.
	(can_chain_union_be_invalidated_p): New.
	(flatten_out_predicate_chains): New.
	(uninit_ops_invalidate_phi_use): New.
	(is_use_properly_guarded): Call uninit_ops_invalidate_phi_use.

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

3 files changed, 207 insertions, 7 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index d02d6e5b536..0f3d3187ffd 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,17 @@
+2016-08-25  Aldy Hernandez  <aldyh@redhat.com>
+
+	PR middle-end/61409
+	* tree-ssa-uninit.c: Define new global max_phi_args.
+	(compute_uninit_opnds_pos): Use max_phi_args.
+	(prune_uninit_phi_opnds): Same.
+	(use_pred_not_overlap_with_undef_path_pred): Remove reference to
+	missing NUM_PREDS in function comment.
+	(can_one_predicate_be_invalidated_p): New.
+	(can_chain_union_be_invalidated_p): New.
+	(flatten_out_predicate_chains): New.
+	(uninit_ops_invalidate_phi_use): New.
+	(is_use_properly_guarded): Call uninit_ops_invalidate_phi_use.
+
 2016-11-20  Marc Glisse  <marc.glisse@inria.fr>
 
 	* fold-const.c (fold_comparison): Ignore EXACT_DIV_EXPR.
diff --git a/gcc/testsuite/gcc.dg/uninit-pr61409.c b/gcc/testsuite/gcc.dg/uninit-pr61409.c
new file mode 100644
index 00000000000..c27a67bd07f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/uninit-pr61409.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -Wuninitialized" } */
+
+int *rw;
+int line_height;
+int pixel_width;
+int text_cols;
+int width1, width2, width3;
+
+void *pointer;
+
+void f (int i, int j)
+{
+  void *ptr;
+  if (i)
+    {
+      if (j)
+	return;
+      ptr = pointer;
+    }
+  pixel_width = 1234 + width1 + 2 * width2 + 2 * width3;
+  *rw = text_cols + line_height;
+  if (i)
+    rw=ptr; /* { dg-bogus "uninitialized" "bogus warning" } */
+}
diff --git a/gcc/tree-ssa-uninit.c b/gcc/tree-ssa-uninit.c
index dfee0ea72d1..68dcf156da2 100644
--- a/gcc/tree-ssa-uninit.c
+++ b/gcc/tree-ssa-uninit.c
@@ -44,6 +44,9 @@ along with GCC; see the file COPYING3.  If not see
    default definitions or by checking if the predicate set that guards the
    defining paths is a superset of the use predicate.  */
 
+/* Max PHI args we can handle in pass.  */
+const unsigned max_phi_args = 32;
+
 /* Pointer set of potentially undefined ssa names, i.e.,
    ssa names that are defined by phi with operands that
    are not defined or potentially undefined.  */
@@ -314,7 +317,7 @@ compute_uninit_opnds_pos (gphi *phi)
 
   n = gimple_phi_num_args (phi);
   /* Bail out for phi with too many args.  */
-  if (n > 32)
+  if (n > max_phi_args)
     return 0;
 
   for (i = 0; i < n; ++i)
@@ -1031,7 +1034,7 @@ prune_uninit_phi_opnds (gphi *phi, unsigned uninit_opnds, gphi *flag_def,
 {
   unsigned i;
 
-  for (i = 0; i < MIN (32, gimple_phi_num_args (flag_def)); i++)
+  for (i = 0; i < MIN (max_phi_args, gimple_phi_num_args (flag_def)); i++)
     {
       tree flag_arg;
 
@@ -1192,11 +1195,10 @@ prune_uninit_phi_opnds (gphi *phi, unsigned uninit_opnds, gphi *flag_def,
      transformation which eliminates the merge point thus makes
      path sensitive analysis unnecessary.)
 
-     NUM_PREDS is the number is the number predicate chains, PREDS is
-     the array of chains, PHI is the phi node whose incoming (undefined)
-     paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
-     uninit operand positions.  VISITED_PHIS is the pointer set of phi
-     stmts being checked.  */
+     PHI is the phi node whose incoming (undefined) paths need to be
+     pruned, and UNINIT_OPNDS is the bitmap holding uninit operand
+     positions.  VISITED_PHIS is the pointer set of phi stmts being
+     checked.  */
 
 static bool
 use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds,
@@ -2148,6 +2150,158 @@ normalize_preds (pred_chain_union preds, gimple *use_or_def, bool is_use)
   return norm_preds;
 }
 
+/* Return TRUE if PREDICATE can be invalidated by any individual
+   predicate in WORKLIST.  */
+
+static bool
+can_one_predicate_be_invalidated_p (pred_info predicate,
+				    vec<pred_info *> worklist)
+{
+  for (size_t i = 0; i < worklist.length (); ++i)
+    {
+      pred_info *p = worklist[i];
+
+      /* NOTE: This is a very simple check, and only understands an
+	 exact opposite.  So, [i == 0] is currently only invalidated
+	 by [.NOT. i == 0] or [i != 0].  Ideally we should also
+	 invalidate with say [i > 5] or [i == 8].  There is certainly
+	 room for improvement here.  */
+      if (pred_neg_p (predicate, *p))
+	return true;
+    }
+  return false;
+}
+
+/* Return TRUE if all USE_PREDS can be invalidated by some predicate
+   in WORKLIST.  */
+
+static bool
+can_chain_union_be_invalidated_p (pred_chain_union use_preds,
+				  vec<pred_info *> worklist)
+{
+  /* Remember:
+       PRED_CHAIN_UNION = PRED_CHAIN1 || PRED_CHAIN2 || PRED_CHAIN3
+       PRED_CHAIN = PRED_INFO1 && PRED_INFO2 && PRED_INFO3, etc.
+
+       We need to invalidate the entire PRED_CHAIN_UNION, which means,
+       invalidating every PRED_CHAIN in this union.  But to invalidate
+       an individual PRED_CHAIN, all we need to invalidate is _any_ one
+       PRED_INFO, by boolean algebra !PRED_INFO1 || !PRED_INFO2...  */
+  for (size_t i = 0; i < use_preds.length (); ++i)
+    {
+      pred_chain c = use_preds[i];
+      bool entire_pred_chain_invalidated = false;
+      for (size_t j = 0; j < c.length (); ++j)
+	if (can_one_predicate_be_invalidated_p (c[i], worklist))
+	  {
+	    entire_pred_chain_invalidated = true;
+	    break;
+	  }
+      if (!entire_pred_chain_invalidated)
+	return false;
+    }
+  return true;
+}
+
+/* Flatten out all the factors in all the pred_chain_union's in PREDS
+   into a WORKLIST of individual PRED_INFO's.
+
+   N is the number of pred_chain_union's in PREDS.
+
+   Since we are interested in the inverse of the PRED_CHAIN's, by
+   boolean algebra, an inverse turns those PRED_CHAINS into unions,
+   which means we can flatten all the factors out for easy access.  */
+
+static void
+flatten_out_predicate_chains (pred_chain_union preds[], size_t n,
+			      vec<pred_info *> *worklist)
+{
+  for (size_t i = 0; i < n; ++i)
+    {
+      pred_chain_union u = preds[i];
+      for (size_t j = 0; j < u.length (); ++j)
+	{
+	  pred_chain c = u[j];
+	  for (size_t k = 0; k < c.length (); ++k)
+	    worklist->safe_push (&c[k]);
+	}
+    }
+}
+
+/* Return TRUE if executing the path to some uninitialized operands in
+   a PHI will invalidate the use of the PHI result later on.
+
+   UNINIT_OPNDS is a bit vector specifying which PHI arguments have
+   arguments which are considered uninitialized.
+
+   USE_PREDS is the pred_chain_union specifying the guard conditions
+   for the use of the PHI result.
+
+   What we want to do is disprove each of the guards in the factors of
+   the USE_PREDS.  So if we have:
+
+   # USE_PREDS guards of:
+   #	1. i > 5 && i < 100
+   #	2. j > 10 && j < 88
+
+   Then proving that the control dependenies for the UNINIT_OPNDS are:
+
+   #      [i <= 5]
+   # .OR. [i >= 100]
+   #
+
+   ...we can prove that the 1st guard above in USE_PREDS is invalid.
+   Similarly for the 2nd guard.  We return TRUE if we can disprove
+   both of the guards in USE_PREDS above.  */
+
+static bool
+uninit_ops_invalidate_phi_use (gphi *phi, unsigned uninit_opnds,
+			       pred_chain_union use_preds)
+{
+  /* Look for the control dependencies of all the uninitialized
+     operands and build predicates describing them.  */
+  unsigned i;
+  pred_chain_union uninit_preds[max_phi_args];
+  memset (uninit_preds, 0, sizeof (pred_chain_union) * max_phi_args);
+  for (i = 0; i < MIN (max_phi_args, gimple_phi_num_args (phi)); i++)
+    {
+      if (!MASK_TEST_BIT (uninit_opnds, i))
+	continue;
+
+      edge e = gimple_phi_arg_edge (phi, i);
+      vec<edge> dep_chains[MAX_NUM_CHAINS];
+      auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
+      size_t num_chains = 0;
+      int num_calls = 0;
+
+      /* Build the control dependency chain for `i'...  */
+      if (compute_control_dep_chain (find_dom (e->src),
+				     e->src,
+				     dep_chains,
+				     &num_chains,
+				     &cur_chain,
+				     &num_calls))
+	{
+	  /* ...and convert it into a set of predicates.  */
+	  convert_control_dep_chain_into_preds (dep_chains, num_chains,
+						&uninit_preds[i]);
+	  for (size_t j = 0; j < num_chains; ++j)
+	    dep_chains[j].release ();
+	  simplify_preds (&uninit_preds[i], NULL, false);
+	  uninit_preds[i]
+	    = normalize_preds (uninit_preds[i], NULL, false);
+	}
+    }
+
+  /* Munge all the predicates into one worklist, and see if we can
+     invalidate all the chains in USE_PREDs with the predicates in
+     WORKLIST.  */
+  auto_vec<pred_info *> worklist;
+  flatten_out_predicate_chains (uninit_preds, i, &worklist);
+  bool ret = can_chain_union_be_invalidated_p (use_preds, worklist);
+  return ret;
+}
+
 /* Computes the predicates that guard the use and checks
    if the incoming paths that have empty (or possibly
    empty) definition can be pruned/filtered.  The function returns
@@ -2203,6 +2357,13 @@ is_use_properly_guarded (gimple *use_stmt,
     = use_pred_not_overlap_with_undef_path_pred (preds, phi, uninit_opnds,
 						 visited_phis);
 
+  /* We might be able to prove that if the control dependencies
+     for UNINIT_OPNDS are true, that the control dependencies for
+     USE_STMT can never be true.  */
+  if (!is_properly_guarded)
+    is_properly_guarded |= uninit_ops_invalidate_phi_use (phi, uninit_opnds,
+							  preds);
+
   if (is_properly_guarded)
     {
       destroy_predicate_vecs (&preds);