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 <[email protected]>
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 <[email protected]>
+
+ 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 <[email protected]>
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 <[email protected]>
+
+ PR middle-end/81897
+ * gcc.dg/uninit-pr81897.c: New test.
+
2018-01-06 Martin Sebor <[email protected]>
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);
