[PR/middle-end,81897] make tree-ssa-uninit.c handle longer sequences
diff mbox series

Message ID f8cc93a9-4b46-7451-06dc-31163fc3eaae@redhat.com
State New
Headers show
Series
  • [PR/middle-end,81897] make tree-ssa-uninit.c handle longer sequences
Related show

Commit Message

Aldy Hernandez Jan. 5, 2018, 8:59 p.m. UTC
This fixes the code that verifies that none of the uninitialized paths 
reaching a PHI are actually taken (uninit_uses_cannot_happen).

As discussed in the PR, this is done by fixing the predicate analysis in 
tree-ssa-uninit.c so that the set of predicates reaching the use of a 
PHI take into the entire path from the entry block.  Previously we were 
starting at the immediate dominator of the PHI (for some obscure reason, 
or brain fart on my part).

Fixing the predicate analysis to go all the way back to ENTRY, uncovers 
some latent limitations in compute_control_dep_chain().  I've fixed 
those as well.

Note, I don't know why we were excluding basic blocks with a small (< 2) 
number of successors, but the exclusion was keeping us from looking at 
the ENTRY block.  If this was by design, I can special case the ENTRY 
block.  Similarly, convert_control_dep_chain_into_preds() was ignoring 
basic blocks with no instructions.  This was making us skip the ENTRY 
block, which is just an empty forwarder block.  Again, if this was by 
design, I can just special case the ENTRY block.

Finally, I've split up the dumping routine into member functions so we 
can get finer grained debugging help.

Tested on x86-64 Linux.

OK for trunk?

Comments

Jeff Law Jan. 6, 2018, 8:01 a.m. UTC | #1
On 01/05/2018 01:59 PM, Aldy Hernandez wrote:
> This fixes the code that verifies that none of the uninitialized paths
> reaching a PHI are actually taken (uninit_uses_cannot_happen).
> 
> As discussed in the PR, this is done by fixing the predicate analysis in
> tree-ssa-uninit.c so that the set of predicates reaching the use of a
> PHI take into the entire path from the entry block.  Previously we were
> starting at the immediate dominator of the PHI (for some obscure reason,
> or brain fart on my part).
> 
> Fixing the predicate analysis to go all the way back to ENTRY, uncovers
> some latent limitations in compute_control_dep_chain().  I've fixed
> those as well.
> 
> Note, I don't know why we were excluding basic blocks with a small (< 2)
> number of successors, but the exclusion was keeping us from looking at
> the ENTRY block.  If this was by design, I can special case the ENTRY
> block.  Similarly, convert_control_dep_chain_into_preds() was ignoring
> basic blocks with no instructions.  This was making us skip the ENTRY
> block, which is just an empty forwarder block.  Again, if this was by
> design, I can just special case the ENTRY block.
It's almost certainly the case they're ignored because a block with a
single successor never controls whether or not we execute some other
block in the CFG.  A block with a single successor always transfers
control to that successor.

But the existence of a block with a single successor shouldn't stop
building the control dependence chain.  We should just proceed into that
single successor and continue to build the control dependency chain.


> 
> Finally, I've split up the dumping routine into member functions so we
> can get finer grained debugging help.
> 
> Tested on x86-64 Linux.
> 
> OK for trunk?
> 
> curr.patch
> 
> 
> gcc/
> 
> 	PR middle-end/81897
> 	* tree-ssa-uninit.c (compute_control_dep_chain): Do not bail on
> 	basic blocks with a small number of successors.
> 	(convert_control_dep_chain_into_preds): Special case the entry
> 	block.
> 	(dump_predicates): Split apart into...
> 	(dump_pred_chain): ...here...
> 	(dump_pred_info): ...and here.
> 	(can_one_predicate_be_invalidated_p): Add debugging printfs.
> 	(can_chain_union_be_invalidated_p): Return TRUE if any predicate
> 	was invalidated.
> 	(uninit_uses_cannot_happen): Avoid unnecessary if
> 	convert_control_dep_chain_into_preds yielded nothing.
So given that we regressed last time we poked around in here, I'm
looking this much deeper.  For reference 78566 and 61409 were the bugs
we looked at last cycle.


> diff --git a/gcc/tree-ssa-uninit.c b/gcc/tree-ssa-uninit.c
> index 6930a243deb..58590a7763b 100644
> --- a/gcc/tree-ssa-uninit.c
> +++ b/gcc/tree-ssa-uninit.c
> @@ -543,9 +543,6 @@ compute_control_dep_chain (basic_block bb, basic_block dep_bb,
>    bool found_cd_chain = false;
>    size_t cur_chain_len = 0;
>  
> -  if (EDGE_COUNT (bb->succs) < 2)
> -    return false;
So the worry here would be a block with no successors, but I think the
right thing will happen in this case.


> @@ -671,11 +668,9 @@ convert_control_dep_chain_into_preds (vec<edge> *dep_chains,
>  	  e = one_cd_chain[j];
>  	  guard_bb = e->src;
>  	  gsi = gsi_last_bb (guard_bb);
> +	  /* Ignore empty BBs as they're basically forwarder blocks.  */
>  	  if (gsi_end_p (gsi))
> -	    {
> -	      has_valid_pred = false;
> -	      break;
> -	    }
> +	    continue;
>  	  cond_stmt = gsi_stmt (gsi);
>  	  if (is_gimple_call (cond_stmt) && EDGE_COUNT (e->src->succs) >= 2)
>  	    /* Ignore EH edge.  Can add assertion on the other edge's flag.  */
ISTM that you want to use empty_block_p (bb) && single_succ_p (bb) to
detect the forwarder block.  Otherwise ISTM that labels and debug
statements would affect the uninit analysis.


> @@ -2287,14 +2308,17 @@ can_chain_union_be_invalidated_p (pred_chain_union uninit_pred,
>  {
>    if (uninit_pred.is_empty ())
>      return false;
> +  if (dump_file && dump_flags & TDF_DETAILS)
> +    dump_predicates (NULL, uninit_pred,
> +		     "Testing if anything here can be invalidated: ");
>    for (size_t i = 0; i < uninit_pred.length (); ++i)
>      {
>        pred_chain c = uninit_pred[i];
>        for (size_t j = 0; j < c.length (); ++j)
> -	if (!can_one_predicate_be_invalidated_p (c[j], use_guard))
> -	  return false;
> +	if (can_one_predicate_be_invalidated_p (c[j], use_guard))
> +	  return true;
>      }
> -  return true;
> +  return false;
>  }
This seems close, but not quite right.

We want to prove (in the most general form) that for all paths from
ENTRY to the PHI which result in the PHI taking on an uninitialized
value that there is no viable path from the PHI to any use of the PHI
result.

We prune that search space by only allowing a single path from the PHI
to uses of the PHI.  So we just have to prove that for all paths from
ENTRY to the PHI where the PHI takes on an uninitialized value the
single path from the PHI to the use is not viable.

USE_GUARD is the predicate chain for that one and only one path from the
PHI to the use of the PHI.

UNINIT_PRED is a vector of predicate chains for the uninitialized PHI
arguments.  One predicate chain per uninitialized PHI argument (C in the
loop).

Thus we have to iterate over each predicate chain in UNINIT_PRED and
verify that it can be invalidated by USE_GUARD.  If any predicate chain
in UNINIT_PRED can not be invalidated by USE_GUARD, then the chain union
can not be invalidated.

So we walk a given chain from UNINIT_PRED, C.  If we are unable to
invalidate any predicates in C we must return false.  If we are able to
invalidate a predicate in C, then we go to the next chain within
UNINIT_PRED and try to invalidate it.  If we are successful in
invalidating all the chains in UNINIT_PRED, then and only then can we
return true.

So I think this ought to look like:


  for (size_t i = 0; i < uninit_pred.length (); ++i)
    {
      pred_chain c = uninit_pred[i];
      size_t j;
      for (j = 0; j < c.length (); ++j)
        if (can_one_predicate_be_invalidated_p (c[j], use_guard))
          break;

      /* If we were unable to invalidate any predicate in C, then there
         is a viable path from entry to the PHI where the PHI takes
         an uninitialized value and continues to a use of the PHI.  */
      if (j == c.length ())
        return false;
    }

  /* We were able to invalidate each chain within UNINIT_PRED.  */
  return true;

Thoughts?

Jeff
Jeff Law Jan. 7, 2018, 5:32 a.m. UTC | #2
On 01/06/2018 01:01 AM, Jeff Law wrote:
> On 01/05/2018 01:59 PM, Aldy Hernandez wrote:
>> This fixes the code that verifies that none of the uninitialized paths
>> reaching a PHI are actually taken (uninit_uses_cannot_happen).
>>
>> As discussed in the PR, this is done by fixing the predicate analysis in
>> tree-ssa-uninit.c so that the set of predicates reaching the use of a
>> PHI take into the entire path from the entry block.  Previously we were
>> starting at the immediate dominator of the PHI (for some obscure reason,
>> or brain fart on my part).
>>
>> Fixing the predicate analysis to go all the way back to ENTRY, uncovers
>> some latent limitations in compute_control_dep_chain().  I've fixed
>> those as well.
>>
>> Note, I don't know why we were excluding basic blocks with a small (< 2)
>> number of successors, but the exclusion was keeping us from looking at
>> the ENTRY block.  If this was by design, I can special case the ENTRY
>> block.  Similarly, convert_control_dep_chain_into_preds() was ignoring
>> basic blocks with no instructions.  This was making us skip the ENTRY
>> block, which is just an empty forwarder block.  Again, if this was by
>> design, I can just special case the ENTRY block.
> It's almost certainly the case they're ignored because a block with a
> single successor never controls whether or not we execute some other
> block in the CFG.  A block with a single successor always transfers
> control to that successor.
> 
> But the existence of a block with a single successor shouldn't stop
> building the control dependence chain.  We should just proceed into that
> single successor and continue to build the control dependency chain.
> 
> 
>>
>> Finally, I've split up the dumping routine into member functions so we
>> can get finer grained debugging help.
>>
>> Tested on x86-64 Linux.
>>
>> OK for trunk?
>>
>> curr.patch
>>
>>
>> gcc/
>>
>> 	PR middle-end/81897
>> 	* tree-ssa-uninit.c (compute_control_dep_chain): Do not bail on
>> 	basic blocks with a small number of successors.
>> 	(convert_control_dep_chain_into_preds): Special case the entry
>> 	block.
>> 	(dump_predicates): Split apart into...
>> 	(dump_pred_chain): ...here...
>> 	(dump_pred_info): ...and here.
>> 	(can_one_predicate_be_invalidated_p): Add debugging printfs.
>> 	(can_chain_union_be_invalidated_p): Return TRUE if any predicate
>> 	was invalidated.
>> 	(uninit_uses_cannot_happen): Avoid unnecessary if
>> 	convert_control_dep_chain_into_preds yielded nothing.
> So given that we regressed last time we poked around in here, I'm
> looking this much deeper.  For reference 78566 and 61409 were the bugs
> we looked at last cycle.
> 
> 
>> diff --git a/gcc/tree-ssa-uninit.c b/gcc/tree-ssa-uninit.c
>> index 6930a243deb..58590a7763b 100644
>> --- a/gcc/tree-ssa-uninit.c
>> +++ b/gcc/tree-ssa-uninit.c
>> @@ -543,9 +543,6 @@ compute_control_dep_chain (basic_block bb, basic_block dep_bb,
>>    bool found_cd_chain = false;
>>    size_t cur_chain_len = 0;
>>  
>> -  if (EDGE_COUNT (bb->succs) < 2)
>> -    return false;
> So the worry here would be a block with no successors, but I think the
> right thing will happen in this case.
> 
> 
>> @@ -671,11 +668,9 @@ convert_control_dep_chain_into_preds (vec<edge> *dep_chains,
>>  	  e = one_cd_chain[j];
>>  	  guard_bb = e->src;
>>  	  gsi = gsi_last_bb (guard_bb);
>> +	  /* Ignore empty BBs as they're basically forwarder blocks.  */
>>  	  if (gsi_end_p (gsi))
>> -	    {
>> -	      has_valid_pred = false;
>> -	      break;
>> -	    }
>> +	    continue;
>>  	  cond_stmt = gsi_stmt (gsi);
>>  	  if (is_gimple_call (cond_stmt) && EDGE_COUNT (e->src->succs) >= 2)
>>  	    /* Ignore EH edge.  Can add assertion on the other edge's flag.  */
> ISTM that you want to use empty_block_p (bb) && single_succ_p (bb) to
> detect the forwarder block.  Otherwise ISTM that labels and debug
> statements would affect the uninit analysis.
> 
> 
>> @@ -2287,14 +2308,17 @@ can_chain_union_be_invalidated_p (pred_chain_union uninit_pred,
>>  {
>>    if (uninit_pred.is_empty ())
>>      return false;
>> +  if (dump_file && dump_flags & TDF_DETAILS)
>> +    dump_predicates (NULL, uninit_pred,
>> +		     "Testing if anything here can be invalidated: ");
>>    for (size_t i = 0; i < uninit_pred.length (); ++i)
>>      {
>>        pred_chain c = uninit_pred[i];
>>        for (size_t j = 0; j < c.length (); ++j)
>> -	if (!can_one_predicate_be_invalidated_p (c[j], use_guard))
>> -	  return false;
>> +	if (can_one_predicate_be_invalidated_p (c[j], use_guard))
>> +	  return true;
>>      }
>> -  return true;
>> +  return false;
>>  }
> This seems close, but not quite right.
> 
> We want to prove (in the most general form) that for all paths from
> ENTRY to the PHI which result in the PHI taking on an uninitialized
> value that there is no viable path from the PHI to any use of the PHI
> result.
> 
> We prune that search space by only allowing a single path from the PHI
> to uses of the PHI.  So we just have to prove that for all paths from
> ENTRY to the PHI where the PHI takes on an uninitialized value the
> single path from the PHI to the use is not viable.
> 
> USE_GUARD is the predicate chain for that one and only one path from the
> PHI to the use of the PHI.
> 
> UNINIT_PRED is a vector of predicate chains for the uninitialized PHI
> arguments.  One predicate chain per uninitialized PHI argument (C in the
> loop).
> 
> Thus we have to iterate over each predicate chain in UNINIT_PRED and
> verify that it can be invalidated by USE_GUARD.  If any predicate chain
> in UNINIT_PRED can not be invalidated by USE_GUARD, then the chain union
> can not be invalidated.
> 
> So we walk a given chain from UNINIT_PRED, C.  If we are unable to
> invalidate any predicates in C we must return false.  If we are able to
> invalidate a predicate in C, then we go to the next chain within
> UNINIT_PRED and try to invalidate it.  If we are successful in
> invalidating all the chains in UNINIT_PRED, then and only then can we
> return true.
> 
> So I think this ought to look like:
> 
> 
>   for (size_t i = 0; i < uninit_pred.length (); ++i)
>     {
>       pred_chain c = uninit_pred[i];
>       size_t j;
>       for (j = 0; j < c.length (); ++j)
>         if (can_one_predicate_be_invalidated_p (c[j], use_guard))
>           break;
> 
>       /* If we were unable to invalidate any predicate in C, then there
>          is a viable path from entry to the PHI where the PHI takes
>          an uninitialized value and continues to a use of the PHI.  */
>       if (j == c.length ())
>         return false;
>     }
> 
>   /* We were able to invalidate each chain within UNINIT_PRED.  */
>   return true;
> 
> Thoughts?
I went ahead and fixed up the empty block test, and the invalidation
code above.  Bootstrapped and regression tested on x86_64.  Installing
on the trunk.

jeff
commit 13f02fc3e1c3abedeb1f551fc232b432f233988a
Author: Jeff Law <law@torsion.usersys.redhat.com>
Date:   Sun Jan 7 00:24:07 2018 -0500

            PR middle-end/81897
            * tree-ssa-uninit.c (compute_control_dep_chain): Do not bail on
            basic blocks with a small number of successors.
            (convert_control_dep_chain_into_preds): Improve handling of
            forwarder blocks.
            (dump_predicates): Split apart into...
            (dump_pred_chain): ...here...
            (dump_pred_info): ...and here.
            (can_one_predicate_be_invalidated_p): Add debugging printfs.
            (can_chain_union_be_invalidated_p): Improve check for invalidation
            of paths.
            (uninit_uses_cannot_happen): Avoid unnecessary if
            convert_control_dep_chain_into_preds yielded nothing.
    
            PR middle-end/81897
            * gcc.dg/uninit-pr81897.c: New test.

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index cd9971d0d1a..f6fe407051a 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,19 @@
+2018-01-06  Aldy Hernandez  <aldyh@redhat.com>
+
+	PR middle-end/81897
+	* tree-ssa-uninit.c (compute_control_dep_chain): Do not bail on
+	basic blocks with a small number of successors.
+	(convert_control_dep_chain_into_preds): Improve handling of
+	forwarder blocks.
+	(dump_predicates): Split apart into...
+	(dump_pred_chain): ...here...
+	(dump_pred_info): ...and here.
+	(can_one_predicate_be_invalidated_p): Add debugging printfs.
+	(can_chain_union_be_invalidated_p): Improve check for invalidation
+	of paths.
+	(uninit_uses_cannot_happen): Avoid unnecessary if
+	convert_control_dep_chain_into_preds yielded nothing.
+
 2018-01-06  Martin Sebor  <msebor@redhat.com>
 
 	PR tree-optimization/83640
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 3b1548dde20..218e7821df7 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2018-01-06  Aldy Hernandez  <aldyh@redhat.com>
+
+	PR middle-end/81897
+	* gcc.dg/uninit-pr81897.c: New test.
+
 2018-01-06  Martin Sebor  <msebor@redhat.com>
 
 	PR tree-optimization/83640
diff --git a/gcc/testsuite/gcc.dg/uninit-pr81897.c b/gcc/testsuite/gcc.dg/uninit-pr81897.c
new file mode 100644
index 00000000000..0323050839d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/uninit-pr81897.c
@@ -0,0 +1,24 @@
+/* { dg-do compile }  */
+/* { dg-options "-O2 -Wuninitialized" } */
+
+int f(void);
+static inline void rcu_read_unlock(void)
+{
+        static _Bool __warned;
+        if (f() && !__warned && !f()) {
+                __warned = 1;
+        }
+}
+int inet6_rtm_getroute(void)
+{
+        int dst;
+        int fibmatch = f();
+
+        if (!fibmatch)
+                dst = f();
+        rcu_read_unlock();
+        if (fibmatch)
+                dst = 0;
+
+        return dst;
+}
diff --git a/gcc/tree-ssa-uninit.c b/gcc/tree-ssa-uninit.c
index 6930a243deb..38239476286 100644
--- a/gcc/tree-ssa-uninit.c
+++ b/gcc/tree-ssa-uninit.c
@@ -33,6 +33,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-ssa.h"
 #include "params.h"
 #include "tree-cfg.h"
+#include "cfghooks.h"
 
 /* This implements the pass that does predicate aware warning on uses of
    possibly uninitialized variables.  The pass first collects the set of
@@ -543,9 +544,6 @@ compute_control_dep_chain (basic_block bb, basic_block dep_bb,
   bool found_cd_chain = false;
   size_t cur_chain_len = 0;
 
-  if (EDGE_COUNT (bb->succs) < 2)
-    return false;
-
   if (*num_calls > PARAM_VALUE (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS))
     return false;
   ++*num_calls;
@@ -671,11 +669,9 @@ convert_control_dep_chain_into_preds (vec<edge> *dep_chains,
 	  e = one_cd_chain[j];
 	  guard_bb = e->src;
 	  gsi = gsi_last_bb (guard_bb);
-	  if (gsi_end_p (gsi))
-	    {
-	      has_valid_pred = false;
-	      break;
-	    }
+	  /* Ignore empty BBs as they're basically forwarder blocks.  */
+	  if (empty_block_p (guard_bb) && single_succ_p (guard_bb))
+	    continue;
 	  cond_stmt = gsi_stmt (gsi);
 	  if (is_gimple_call (cond_stmt) && EDGE_COUNT (e->src->succs) >= 2)
 	    /* Ignore EH edge.  Can add assertion on the other edge's flag.  */
@@ -916,38 +912,49 @@ find_def_preds (pred_chain_union *preds, gphi *phi)
   return has_valid_pred;
 }
 
+/* Dump a pred_info.  */
+
+static void
+dump_pred_info (pred_info one_pred)
+{
+  if (one_pred.invert)
+    fprintf (dump_file, " (.NOT.) ");
+  print_generic_expr (dump_file, one_pred.pred_lhs);
+  fprintf (dump_file, " %s ", op_symbol_code (one_pred.cond_code));
+  print_generic_expr (dump_file, one_pred.pred_rhs);
+}
+
+/* Dump a pred_chain.  */
+
+static void
+dump_pred_chain (pred_chain one_pred_chain)
+{
+  size_t np = one_pred_chain.length ();
+  for (size_t j = 0; j < np; j++)
+    {
+      dump_pred_info (one_pred_chain[j]);
+      if (j < np - 1)
+	fprintf (dump_file, " (.AND.) ");
+      else
+	fprintf (dump_file, "\n");
+    }
+}
+
 /* Dumps the predicates (PREDS) for USESTMT.  */
 
 static void
 dump_predicates (gimple *usestmt, pred_chain_union preds, const char *msg)
 {
-  size_t i, j;
-  pred_chain one_pred_chain = vNULL;
   fprintf (dump_file, "%s", msg);
-  print_gimple_stmt (dump_file, usestmt, 0);
-  fprintf (dump_file, "is guarded by :\n\n");
+  if (usestmt)
+    {
+      print_gimple_stmt (dump_file, usestmt, 0);
+      fprintf (dump_file, "is guarded by :\n\n");
+    }
   size_t num_preds = preds.length ();
-  /* Do some dumping here:  */
-  for (i = 0; i < num_preds; i++)
+  for (size_t i = 0; i < num_preds; i++)
     {
-      size_t np;
-
-      one_pred_chain = preds[i];
-      np = one_pred_chain.length ();
-
-      for (j = 0; j < np; j++)
-	{
-	  pred_info one_pred = one_pred_chain[j];
-	  if (one_pred.invert)
-	    fprintf (dump_file, " (.NOT.) ");
-	  print_generic_expr (dump_file, one_pred.pred_lhs);
-	  fprintf (dump_file, " %s ", op_symbol_code (one_pred.cond_code));
-	  print_generic_expr (dump_file, one_pred.pred_rhs);
-	  if (j < np - 1)
-	    fprintf (dump_file, " (.AND.) ");
-	  else
-	    fprintf (dump_file, "\n");
-	}
+      dump_pred_chain (preds[i]);
       if (i < num_preds - 1)
 	fprintf (dump_file, "(.OR.)\n");
       else
@@ -2259,12 +2266,19 @@ normalize_preds (pred_chain_union preds, gimple *use_or_def, bool is_use)
 }
 
 /* Return TRUE if PREDICATE can be invalidated by any individual
-   predicate in WORKLIST.  */
+   predicate in USE_GUARD.  */
 
 static bool
 can_one_predicate_be_invalidated_p (pred_info predicate,
 				    pred_chain use_guard)
 {
+  if (dump_file && dump_flags & TDF_DETAILS)
+    {
+      fprintf (dump_file, "Testing if this predicate: ");
+      dump_pred_info (predicate);
+      fprintf (dump_file, "\n...can be invalidated by a USE guard of: ");
+      dump_pred_chain (use_guard);
+    }
   for (size_t i = 0; i < use_guard.length (); ++i)
     {
       /* NOTE: This is a very simple check, and only understands an
@@ -2273,7 +2287,15 @@ can_one_predicate_be_invalidated_p (pred_info predicate,
 	 invalidate with say [i > 5] or [i == 8].  There is certainly
 	 room for improvement here.  */
       if (pred_neg_p (predicate, use_guard[i]))
-	return true;
+	{
+	  if (dump_file && dump_flags & TDF_DETAILS)
+	    {
+	      fprintf (dump_file, "  Predicate was invalidated by: ");
+	      dump_pred_info (use_guard[i]);
+	      fputc ('\n', dump_file);
+	    }
+	  return true;
+	}
     }
   return false;
 }
@@ -2287,12 +2309,22 @@ can_chain_union_be_invalidated_p (pred_chain_union uninit_pred,
 {
   if (uninit_pred.is_empty ())
     return false;
+  if (dump_file && dump_flags & TDF_DETAILS)
+    dump_predicates (NULL, uninit_pred,
+		     "Testing if anything here can be invalidated: ");
   for (size_t i = 0; i < uninit_pred.length (); ++i)
     {
       pred_chain c = uninit_pred[i];
-      for (size_t j = 0; j < c.length (); ++j)
-	if (!can_one_predicate_be_invalidated_p (c[j], use_guard))
-	  return false;
+      size_t j;
+      for (j = 0; j < c.length (); ++j)
+	if (can_one_predicate_be_invalidated_p (c[j], use_guard))
+	  break;
+
+      /* If we were unable to invalidate any predicate in C, then there
+	 is a viable path from entry to the PHI where the PHI takes
+	 an uninitialized value and continues to a use of the PHI.  */
+      if (j == c.length ())
+	return false;
     }
   return true;
 }
@@ -2334,7 +2366,7 @@ uninit_uses_cannot_happen (gphi *phi, unsigned uninit_opnds,
 
       /* Build the control dependency chain for uninit operand `i'...  */
       uninit_preds = vNULL;
-      if (!compute_control_dep_chain (find_dom (e->src),
+      if (!compute_control_dep_chain (ENTRY_BLOCK_PTR_FOR_FN (cfun),
 				      e->src, dep_chains, &num_chains,
 				      &cur_chain, &num_calls))
 	{
@@ -2342,10 +2374,16 @@ uninit_uses_cannot_happen (gphi *phi, unsigned uninit_opnds,
 	  break;
 	}
       /* ...and convert it into a set of predicates.  */
-      convert_control_dep_chain_into_preds (dep_chains, num_chains,
-					    &uninit_preds);
+      bool has_valid_preds
+	= convert_control_dep_chain_into_preds (dep_chains, num_chains,
+						&uninit_preds);
       for (size_t j = 0; j < num_chains; ++j)
 	dep_chains[j].release ();
+      if (!has_valid_preds)
+	{
+	  ret = false;
+	  break;
+	}
       simplify_preds (&uninit_preds, NULL, false);
       uninit_preds = normalize_preds (uninit_preds, NULL, false);
Aldy Hernandez Jan. 9, 2018, 6:05 p.m. UTC | #3
On 01/07/2018 12:32 AM, Jeff Law wrote:
> On 01/06/2018 01:01 AM, Jeff Law wrote:
>> On 01/05/2018 01:59 PM, Aldy Hernandez wrote:

> I went ahead and fixed up the empty block test, and the invalidation
> code above.  Bootstrapped and regression tested on x86_64.  Installing
> on the trunk.

Thanks.

Aldy
Aldy Hernandez Jan. 10, 2018, 5:45 p.m. UTC | #4
>> @@ -671,11 +668,9 @@ convert_control_dep_chain_into_preds (vec<edge> *dep_chains,
>>         e = one_cd_chain[j];
>>         guard_bb = e->src;
>>         gsi = gsi_last_bb (guard_bb);
>> +       /* Ignore empty BBs as they're basically forwarder blocks.  */
>>         if (gsi_end_p (gsi))
>> -         {
>> -           has_valid_pred = false;
>> -           break;
>> -         }
>> +         continue;
>>         cond_stmt = gsi_stmt (gsi);
>>         if (is_gimple_call (cond_stmt) && EDGE_COUNT (e->src->succs) >= 2)
>>           /* Ignore EH edge.  Can add assertion on the other edge's flag.  */
> ISTM that you want to use empty_block_p (bb) && single_succ_p (bb) to
> detect the forwarder block.  Otherwise ISTM that labels and debug
> statements would affect the uninit analysis.

We still need to check for gsi_end_p() because guard_bb can have no
statements but be considered non empty according to empty_block_p().
This is the case with a seemingly empty basic block that actually has
an incoming PHI.

Jakub suggested the following patch which fixes the new ICE in the PR.
I've adjusted the comments accordingly.

OK?
gcc/

	PR middle-end/81897
	* tree-ssa-uninit.c (convert_control_dep_chain_into_preds): Skip
	empty blocks.

diff --git a/gcc/testsuite/gcc.dg/uninit-pr81897-2.c b/gcc/testsuite/gcc.dg/uninit-pr81897-2.c
new file mode 100644
index 00000000000..3960af454e5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/uninit-pr81897-2.c
@@ -0,0 +1,35 @@
+/* { dg-do compile }  */
+/* { dg-options "-O1 -fno-tree-ccp -Wmaybe-uninitialized" } */
+
+int oo;
+
+void
+pc (int *tt)
+{
+  int cf = 0;
+
+  if (*tt != 0)
+    {
+      if (0)
+        {
+          int *qg;
+          int uj = 0;
+
+ t6:
+          tt = &cf;
+          if (oo != 0)
+            {
+              ++uj; /* { dg-warning "may be used uninit" } */
+              *qg = !!oo && !!uj; /* { dg-warning "may be used uninit" } */
+            }
+        }
+      cf = 0;
+      goto t6;
+    }
+
+  if (oo != 0)
+    {
+      *tt = 1;
+      goto t6;
+    }
+}
diff --git a/gcc/tree-ssa-uninit.c b/gcc/tree-ssa-uninit.c
index 38239476286..8ccbc85970a 100644
--- a/gcc/tree-ssa-uninit.c
+++ b/gcc/tree-ssa-uninit.c
@@ -669,9 +669,16 @@ convert_control_dep_chain_into_preds (vec<edge> *dep_chains,
 	  e = one_cd_chain[j];
 	  guard_bb = e->src;
 	  gsi = gsi_last_bb (guard_bb);
-	  /* Ignore empty BBs as they're basically forwarder blocks.  */
+	  /* Ignore empty forwarder blocks.  */
 	  if (empty_block_p (guard_bb) && single_succ_p (guard_bb))
 	    continue;
+	  /* An empty basic block here is likely a PHI, and is not one
+	     of the cases we handle below.  */
+	  if (gsi_end_p (gsi))
+	    {
+	      has_valid_pred = false;
+	      break;
+	    }
 	  cond_stmt = gsi_stmt (gsi);
 	  if (is_gimple_call (cond_stmt) && EDGE_COUNT (e->src->succs) >= 2)
 	    /* Ignore EH edge.  Can add assertion on the other edge's flag.  */
Jeff Law Jan. 10, 2018, 9:16 p.m. UTC | #5
On 01/10/2018 10:45 AM, Aldy Hernandez wrote:
>>> @@ -671,11 +668,9 @@ convert_control_dep_chain_into_preds (vec<edge> *dep_chains,
>>>         e = one_cd_chain[j];
>>>         guard_bb = e->src;
>>>         gsi = gsi_last_bb (guard_bb);
>>> +       /* Ignore empty BBs as they're basically forwarder blocks.  */
>>>         if (gsi_end_p (gsi))
>>> -         {
>>> -           has_valid_pred = false;
>>> -           break;
>>> -         }
>>> +         continue;
>>>         cond_stmt = gsi_stmt (gsi);
>>>         if (is_gimple_call (cond_stmt) && EDGE_COUNT (e->src->succs) >= 2)
>>>           /* Ignore EH edge.  Can add assertion on the other edge's flag.  */
>> ISTM that you want to use empty_block_p (bb) && single_succ_p (bb) to
>> detect the forwarder block.  Otherwise ISTM that labels and debug
>> statements would affect the uninit analysis.
> We still need to check for gsi_end_p() because guard_bb can have no
> statements but be considered non empty according to empty_block_p().
> This is the case with a seemingly empty basic block that actually has
> an incoming PHI.
> 
> Jakub suggested the following patch which fixes the new ICE in the PR.
> I've adjusted the comments accordingly.
> 
> OK?
> 
> 
> curr.patch
> 
> 
> gcc/
> 
> 	PR middle-end/81897
> 	* tree-ssa-uninit.c (convert_control_dep_chain_into_preds): Skip
> 	empty blocks.
OK.

Sorry for mucking things up and making more work :(

jeff
Aldy Hernandez Jan. 10, 2018, 9:40 p.m. UTC | #6
> OK.
>
> Sorry for mucking things up and making more work :(
>

Not at all.  I didn't know PHIs were going to behave that way either ;-).

Thanks for the review.  Committed to trunk.

Aldy

Patch
diff mbox series

gcc/

	PR middle-end/81897
	* tree-ssa-uninit.c (compute_control_dep_chain): Do not bail on
	basic blocks with a small number of successors.
	(convert_control_dep_chain_into_preds): Special case the entry
	block.
	(dump_predicates): Split apart into...
	(dump_pred_chain): ...here...
	(dump_pred_info): ...and here.
	(can_one_predicate_be_invalidated_p): Add debugging printfs.
	(can_chain_union_be_invalidated_p): Return TRUE if any predicate
	was invalidated.
	(uninit_uses_cannot_happen): Avoid unnecessary if
	convert_control_dep_chain_into_preds yielded nothing.

diff --git a/gcc/testsuite/gcc.dg/uninit-pr81897.c b/gcc/testsuite/gcc.dg/uninit-pr81897.c
new file mode 100644
index 00000000000..0323050839d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/uninit-pr81897.c
@@ -0,0 +1,24 @@ 
+/* { dg-do compile }  */
+/* { dg-options "-O2 -Wuninitialized" } */
+
+int f(void);
+static inline void rcu_read_unlock(void)
+{
+        static _Bool __warned;
+        if (f() && !__warned && !f()) {
+                __warned = 1;
+        }
+}
+int inet6_rtm_getroute(void)
+{
+        int dst;
+        int fibmatch = f();
+
+        if (!fibmatch)
+                dst = f();
+        rcu_read_unlock();
+        if (fibmatch)
+                dst = 0;
+
+        return dst;
+}
diff --git a/gcc/tree-ssa-uninit.c b/gcc/tree-ssa-uninit.c
index 6930a243deb..58590a7763b 100644
--- a/gcc/tree-ssa-uninit.c
+++ b/gcc/tree-ssa-uninit.c
@@ -543,9 +543,6 @@  compute_control_dep_chain (basic_block bb, basic_block dep_bb,
   bool found_cd_chain = false;
   size_t cur_chain_len = 0;
 
-  if (EDGE_COUNT (bb->succs) < 2)
-    return false;
-
   if (*num_calls > PARAM_VALUE (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS))
     return false;
   ++*num_calls;
@@ -671,11 +668,9 @@  convert_control_dep_chain_into_preds (vec<edge> *dep_chains,
 	  e = one_cd_chain[j];
 	  guard_bb = e->src;
 	  gsi = gsi_last_bb (guard_bb);
+	  /* Ignore empty BBs as they're basically forwarder blocks.  */
 	  if (gsi_end_p (gsi))
-	    {
-	      has_valid_pred = false;
-	      break;
-	    }
+	    continue;
 	  cond_stmt = gsi_stmt (gsi);
 	  if (is_gimple_call (cond_stmt) && EDGE_COUNT (e->src->succs) >= 2)
 	    /* Ignore EH edge.  Can add assertion on the other edge's flag.  */
@@ -916,38 +911,49 @@  find_def_preds (pred_chain_union *preds, gphi *phi)
   return has_valid_pred;
 }
 
+/* Dump a pred_info.  */
+
+static void
+dump_pred_info (pred_info one_pred)
+{
+  if (one_pred.invert)
+    fprintf (dump_file, " (.NOT.) ");
+  print_generic_expr (dump_file, one_pred.pred_lhs);
+  fprintf (dump_file, " %s ", op_symbol_code (one_pred.cond_code));
+  print_generic_expr (dump_file, one_pred.pred_rhs);
+}
+
+/* Dump a pred_chain.  */
+
+static void
+dump_pred_chain (pred_chain one_pred_chain)
+{
+  size_t np = one_pred_chain.length ();
+  for (size_t j = 0; j < np; j++)
+    {
+      dump_pred_info (one_pred_chain[j]);
+      if (j < np - 1)
+	fprintf (dump_file, " (.AND.) ");
+      else
+	fprintf (dump_file, "\n");
+    }
+}
+
 /* Dumps the predicates (PREDS) for USESTMT.  */
 
 static void
 dump_predicates (gimple *usestmt, pred_chain_union preds, const char *msg)
 {
-  size_t i, j;
-  pred_chain one_pred_chain = vNULL;
   fprintf (dump_file, "%s", msg);
-  print_gimple_stmt (dump_file, usestmt, 0);
-  fprintf (dump_file, "is guarded by :\n\n");
+  if (usestmt)
+    {
+      print_gimple_stmt (dump_file, usestmt, 0);
+      fprintf (dump_file, "is guarded by :\n\n");
+    }
   size_t num_preds = preds.length ();
-  /* Do some dumping here:  */
-  for (i = 0; i < num_preds; i++)
+  for (size_t i = 0; i < num_preds; i++)
     {
-      size_t np;
-
-      one_pred_chain = preds[i];
-      np = one_pred_chain.length ();
-
-      for (j = 0; j < np; j++)
-	{
-	  pred_info one_pred = one_pred_chain[j];
-	  if (one_pred.invert)
-	    fprintf (dump_file, " (.NOT.) ");
-	  print_generic_expr (dump_file, one_pred.pred_lhs);
-	  fprintf (dump_file, " %s ", op_symbol_code (one_pred.cond_code));
-	  print_generic_expr (dump_file, one_pred.pred_rhs);
-	  if (j < np - 1)
-	    fprintf (dump_file, " (.AND.) ");
-	  else
-	    fprintf (dump_file, "\n");
-	}
+      dump_pred_chain (preds[i]);
       if (i < num_preds - 1)
 	fprintf (dump_file, "(.OR.)\n");
       else
@@ -2259,12 +2265,19 @@  normalize_preds (pred_chain_union preds, gimple *use_or_def, bool is_use)
 }
 
 /* Return TRUE if PREDICATE can be invalidated by any individual
-   predicate in WORKLIST.  */
+   predicate in USE_GUARD.  */
 
 static bool
 can_one_predicate_be_invalidated_p (pred_info predicate,
 				    pred_chain use_guard)
 {
+  if (dump_file && dump_flags & TDF_DETAILS)
+    {
+      fprintf (dump_file, "Testing if this predicate: ");
+      dump_pred_info (predicate);
+      fprintf (dump_file, "\n...can be invalidated by a USE guard of: ");
+      dump_pred_chain (use_guard);
+    }
   for (size_t i = 0; i < use_guard.length (); ++i)
     {
       /* NOTE: This is a very simple check, and only understands an
@@ -2273,7 +2286,15 @@  can_one_predicate_be_invalidated_p (pred_info predicate,
 	 invalidate with say [i > 5] or [i == 8].  There is certainly
 	 room for improvement here.  */
       if (pred_neg_p (predicate, use_guard[i]))
-	return true;
+	{
+	  if (dump_file && dump_flags & TDF_DETAILS)
+	    {
+	      fprintf (dump_file, "  Predicate was invalidated by: ");
+	      dump_pred_info (use_guard[i]);
+	      fputc ('\n', dump_file);
+	    }
+	  return true;
+	}
     }
   return false;
 }
@@ -2287,14 +2308,17 @@  can_chain_union_be_invalidated_p (pred_chain_union uninit_pred,
 {
   if (uninit_pred.is_empty ())
     return false;
+  if (dump_file && dump_flags & TDF_DETAILS)
+    dump_predicates (NULL, uninit_pred,
+		     "Testing if anything here can be invalidated: ");
   for (size_t i = 0; i < uninit_pred.length (); ++i)
     {
       pred_chain c = uninit_pred[i];
       for (size_t j = 0; j < c.length (); ++j)
-	if (!can_one_predicate_be_invalidated_p (c[j], use_guard))
-	  return false;
+	if (can_one_predicate_be_invalidated_p (c[j], use_guard))
+	  return true;
     }
-  return true;
+  return false;
 }
 
 /* Return TRUE if none of the uninitialized operands in UNINT_OPNDS
@@ -2334,7 +2358,7 @@  uninit_uses_cannot_happen (gphi *phi, unsigned uninit_opnds,
 
       /* Build the control dependency chain for uninit operand `i'...  */
       uninit_preds = vNULL;
-      if (!compute_control_dep_chain (find_dom (e->src),
+      if (!compute_control_dep_chain (ENTRY_BLOCK_PTR_FOR_FN (cfun),
 				      e->src, dep_chains, &num_chains,
 				      &cur_chain, &num_calls))
 	{
@@ -2342,10 +2366,16 @@  uninit_uses_cannot_happen (gphi *phi, unsigned uninit_opnds,
 	  break;
 	}
       /* ...and convert it into a set of predicates.  */
-      convert_control_dep_chain_into_preds (dep_chains, num_chains,
-					    &uninit_preds);
+      bool has_valid_preds
+	= convert_control_dep_chain_into_preds (dep_chains, num_chains,
+						&uninit_preds);
       for (size_t j = 0; j < num_chains; ++j)
 	dep_chains[j].release ();
+      if (!has_valid_preds)
+	{
+	  ret = false;
+	  break;
+	}
       simplify_preds (&uninit_preds, NULL, false);
       uninit_preds = normalize_preds (uninit_preds, NULL, false);