On 11/16/2016 03:57 PM, Jeff Law wrote:
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 <al...@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.
Ok.
+
+/* 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?
IOR, so yes.
+
+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.
Done.
+
+ /* 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.
Hmmm, probably not. So yeah, let's put that in the 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.
I've retested with no regressions on x86-64 Linux.
OK for trunk?
commit 42f32d1e064613d031c1e82f259d89f290355dd2
Author: Aldy Hernandez <al...@redhat.com>
Date: Thu Aug 25 10:44:29 2016 -0400
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.
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 dfee0ea..68dcf15 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);
