PR61409: -Wmaybe-uninitialized false-positive with -O2
diff mbox

Message ID 8c90256b-a9a1-b849-08ce-9435fdb8c770@redhat.com
State New
Headers show

Commit Message

Aldy Hernandez Nov. 2, 2016, 5:16 p.m. UTC
Hi Jeff.

As discussed in the PR, here is a patch exploring your idea of ignoring 
unguarded uses if we can prove that the guards for such uses are 
invalidated by the uninitialized operand paths being executed.

This is an updated patch from my suggestion in the PR.  It bootstraps 
with no regression on x86-64 Linux, and fixes the PR in question.

As the "NOTE:" in the code states, we could be much smarter when 
invalidating predicates, but for now let's do straight negation which 
works for the simple case.  We could expand on this in the future.

OK for trunk?
commit 8375d7e28c1a798dd0cc0f487d7fa1068d9eb124
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Thu Aug 25 10:44:29 2016 -0400

    	PR middle-end/61409
    	* tree-ssa-uninit.c (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.

Comments

Jeff Law Nov. 16, 2016, 8:57 p.m. UTC | #1
On 11/02/2016 11:16 AM, Aldy Hernandez wrote:
> Hi Jeff.
>
> As discussed in the PR, here is a patch exploring your idea of ignoring
> unguarded uses if we can prove that the guards for such uses are
> invalidated by the uninitialized operand paths being executed.
>
> This is an updated patch from my suggestion in the PR.  It bootstraps
> with no regression on x86-64 Linux, and fixes the PR in question.
>
> As the "NOTE:" in the code states, we could be much smarter when
> invalidating predicates, but for now let's do straight negation which
> works for the simple case.  We could expand on this in the future.
>
> OK for trunk?
>
>
> curr
>
>
> commit 8375d7e28c1a798dd0cc0f487d7fa1068d9eb124
> Author: Aldy Hernandez <aldyh@redhat.com>
> Date:   Thu Aug 25 10:44:29 2016 -0400
>
>     	PR middle-end/61409
>     	* tree-ssa-uninit.c (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.
[ snip ]

>
> +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))
It's good enough for now.  I saw some other routines that might allow us 
to handle more cases.  I'm OK with faulting those in if/when we see such 
cases in real code.


> +
> +/* 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
Are USE_PREDS joined by an AND or IOR?  I guess based on their type it 
must be IOR.   Thus to get to a use  #1 or #2 must be true.  So to prove 
we can't reach a use, we have to prove that #1 and #2 are both not true. 
  Right?


> +
> +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[32];
> +  memset (uninit_preds, 0, sizeof (pred_chain_union) * 32);
> +  for (i = 0; i < MIN (32, gimple_phi_num_args (phi)); i++)
Can you replace the magic "32" with a file scoped const or #define?  I 
believe there's 2 existing uses of a magic "32" elsewhere in 
tree-ssa-uninit.c as well.

> +
> +      /* 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))
Does this miss the control dependency carried by E itself.

ie, if e->src ends in a conditional, shouldn't that conditional be 
reflected in the control dependency chain as well?  I guess we'd have to 
have the notion of computing the control dependency for an edge rather 
than a block.  It doesn't look like compute_control_dep_chain is ready 
for that.  I'm willing to put that into a "future work" bucket.

So I think just confirming my question about how USE_PREDS are joined at 
the call to uninit_opts_invalidate_phi_use and fixing the magic 32 to be 
a file scoped const or a #define and this is good to go on the trunk.

jeff

Patch
diff mbox

diff --git a/gcc/testsuite/gcc.dg/uninit-pr61409.c b/gcc/testsuite/gcc.dg/uninit-pr61409.c
new file mode 100644
index 0000000..c27a67b
--- /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 1344854..37c99a7 100644
--- a/gcc/tree-ssa-uninit.c
+++ b/gcc/tree-ssa-uninit.c
@@ -1184,11 +1184,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,
@@ -2140,6 +2139,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[32];
+  memset (uninit_preds, 0, sizeof (pred_chain_union) * 32);
+  for (i = 0; i < MIN (32, 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
@@ -2195,6 +2346,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);