On Tue, Mar 8, 2011 at 10:55 AM, Diego Novillo <dnovi...@google.com> wrote:
> On 03/08/2011 12:54 PM, Xinliang David Li wrote:
>>
>> Please review the attached patch, it does some simplification of the
>> complicated logical or expressions (x1 or x2 or x3 ...) constructed
>> from control flow analysis into simpler form.
>>
>> Bootstraps and works on s390x for both testcases.
>>
>> Bootstraps on x86-64. Regression testing is on going (it takes forever
>> (whole night already) to finish possibly because the lto test in
>> c-torture ..).
>>
>> Ok for trunk?
>
> As a general comment, do you think we will start adding more and more of
> these special pattern matchers into uninit analysis? I'm wondering how much
> effort should we make into creating something more generic.
Good question. The answer is probably only for common expressions like
this one. We don't have generic way of doing expression reassociation
that can be invoked on the fly -- only in the future.
> Right now it's this pattern, but there may be others. It could grow pretty
> big and ugly.
Any generic way is also going to be big and ugly just like any
simplification/folding functions.
> Could you add some tests? I realize this fixes 390 testcases, but are there
> tests where we could explicitly check that this is triggering?
Added.
>
> s/simplication/simplification/
> There is another instance of this later.
corrected.
>
>> + VEC(use_pred_info_t, heap) * const*chain2
>> + = (VEC(use_pred_info_t, heap) * const*)p2;
>
> space around '*'.
corrected.
\>
> Why not just one 'if (ll == 2)'?
good catch -- missed an 'else' branch.
>
> So, this has been modifying the input array, what happens if it at some
> point during the iteration, it decides to return false? The caller will
> need to cope with the modified version of 'preds'?
It is outside the loop. which is an independent simplification -- the
number of chains are updated and the resulting chains are valid even
the latter replace does not happen.
> Space around '+'.
Added.
> Please add a comment describing what this loop does.
Done.
> End comment with '. */'
Done.
Thanks,
David
2011-03-08 Xinliang David Li <davi...@google.com>
* gcc.dg/uninit-pred-7_d.c: New test.
* gcc.dg/uninit-pred-8_d.c: New test.
Index: tree-ssa-uninit.c
===================================================================
--- tree-ssa-uninit.c (revision 170150)
+++ tree-ssa-uninit.c (working copy)
@@ -1605,6 +1605,157 @@ is_superset_of (VEC(use_pred_info_t, hea
return true;
}
+/* Comparison function used by qsort. It is used to
+ sort predicate chains to allow predicate
+ simplification. */
+
+static int
+pred_chain_length_cmp (const void *p1, const void *p2)
+{
+ use_pred_info_t i1, i2;
+ VEC(use_pred_info_t, heap) * const *chain1
+ = (VEC(use_pred_info_t, heap) * const *)p1;
+ VEC(use_pred_info_t, heap) * const *chain2
+ = (VEC(use_pred_info_t, heap) * const *)p2;
+
+ if (VEC_length (use_pred_info_t, *chain1)
+ != VEC_length (use_pred_info_t, *chain2))
+ return (VEC_length (use_pred_info_t, *chain1)
+ - VEC_length (use_pred_info_t, *chain2));
+
+ i1 = VEC_index (use_pred_info_t, *chain1, 0);
+ i2 = VEC_index (use_pred_info_t, *chain2, 0);
+
+ /* Allow predicates with similar prefix come together. */
+ if (!i1->invert && i2->invert)
+ return -1;
+ else if (i1->invert && !i2->invert)
+ return 1;
+
+ return gimple_uid (i1->cond) - gimple_uid (i2->cond);
+}
+
+/* x OR (!x AND y) is equivalent to x OR y.
+ This function normalizes x1 OR (!x1 AND x2) OR (!x1 AND !x2 AND x3)
+ into x1 OR x2 OR x3. PREDS is the predicate chains, and N is
+ the number of chains. Returns true if normalization happens. */
+
+static bool
+normalize_preds (VEC(use_pred_info_t, heap) **preds, size_t *n)
+{
+ size_t i, j, ll;
+ VEC(use_pred_info_t, heap) *pred_chain;
+ VEC(use_pred_info_t, heap) *x = 0;
+ use_pred_info_t xj = 0, nxj = 0;
+
+ if (*n < 2)
+ return false;
+
+ /* First sort the chains in ascending order of lengths. */
+ qsort (preds, *n, sizeof (void *), pred_chain_length_cmp);
+ pred_chain = preds[0];
+ ll = VEC_length (use_pred_info_t, pred_chain);
+ if (ll != 1)
+ {
+ if (ll == 2)
+ {
+ use_pred_info_t xx, yy, xx2, nyy;
+ VEC(use_pred_info_t, heap) *pred_chain2 = preds[1];
+ if (VEC_length (use_pred_info_t, pred_chain2) != 2)
+ return false;
+
+ /* See if simplification x AND y OR x AND !y is possible. */
+ xx = VEC_index (use_pred_info_t, pred_chain, 0);
+ yy = VEC_index (use_pred_info_t, pred_chain, 1);
+ xx2 = VEC_index (use_pred_info_t, pred_chain2, 0);
+ nyy = VEC_index (use_pred_info_t, pred_chain2, 1);
+ if (gimple_cond_lhs (xx->cond) != gimple_cond_lhs (xx2->cond)
+ || gimple_cond_rhs (xx->cond) != gimple_cond_rhs (xx2->cond)
+ || gimple_cond_code (xx->cond) != gimple_cond_code (xx2->cond)
+ || (xx->invert != xx2->invert))
+ return false;
+ if (gimple_cond_lhs (yy->cond) != gimple_cond_lhs (nyy->cond)
+ || gimple_cond_rhs (yy->cond) != gimple_cond_rhs (nyy->cond)
+ || gimple_cond_code (yy->cond) != gimple_cond_code (nyy->cond)
+ || (yy->invert == nyy->invert))
+ return false;
+
+ /* Now merge the first two chains. */
+ free (yy);
+ free (nyy);
+ free (xx2);
+ VEC_free (use_pred_info_t, heap, pred_chain);
+ VEC_free (use_pred_info_t, heap, pred_chain2);
+ pred_chain = 0;
+ VEC_safe_push (use_pred_info_t, heap, pred_chain, xx);
+ preds[0] = pred_chain;
+ for (i = 1; i < *n - 1; i++)
+ preds[i] = preds[i + 1];
+
+ preds[*n - 1] = 0;
+ *n = *n - 1;
+ }
+ else
+ return false;
+ }
+
+ VEC_safe_push (use_pred_info_t, heap, x,
+ VEC_index (use_pred_info_t, pred_chain, 0));
+
+ /* The loop extracts x1, x2, x3, etc from chains
+ x1 OR (!x1 AND x2) OR (!x1 AND !x2 AND x3) OR ... */
+ for (i = 1; i < *n; i++)
+ {
+ pred_chain = preds[i];
+ if (VEC_length (use_pred_info_t, pred_chain) != i + 1)
+ return false;
+
+ for (j = 0; j < i; j++)
+ {
+ xj = VEC_index (use_pred_info_t, x, j);
+ nxj = VEC_index (use_pred_info_t, pred_chain, j);
+
+ /* Check if nxj is !xj */
+ if (gimple_cond_lhs (xj->cond) != gimple_cond_lhs (nxj->cond)
+ || gimple_cond_rhs (xj->cond) != gimple_cond_rhs (nxj->cond)
+ || gimple_cond_code (xj->cond) != gimple_cond_code (nxj->cond)
+ || (xj->invert == nxj->invert))
+ return false;
+ }
+
+ VEC_safe_push (use_pred_info_t, heap, x,
+ VEC_index (use_pred_info_t, pred_chain, i));
+ }
+
+ /* Now normalize the pred chains using the extraced x1, x2, x3 etc. */
+ for (j = 0; j < *n; j++)
+ {
+ use_pred_info_t t;
+ xj = VEC_index (use_pred_info_t, x, j);
+
+ t = XNEW (struct use_pred_info);
+ *t = *xj;
+
+ VEC_replace (use_pred_info_t, x, j, t);
+ }
+
+ for (i = 0; i < *n; i++)
+ {
+ pred_chain = preds[i];
+ for (j = 0; j < VEC_length (use_pred_info_t, pred_chain); j++)
+ free (VEC_index (use_pred_info_t, pred_chain, j));
+ VEC_free (use_pred_info_t, heap, pred_chain);
+ pred_chain = 0;
+ /* A new chain. */
+ VEC_safe_push (use_pred_info_t, heap, pred_chain,
+ VEC_index (use_pred_info_t, x, i));
+ preds[i] = pred_chain;
+ }
+ return true;
+}
+
+
+
/* Computes the predicates that guard the use and checks
if the incoming paths that have empty (or possibly
empty) defintion can be pruned/filtered. The function returns
@@ -1658,9 +1809,18 @@ is_use_properly_guarded (gimple use_stmt
if (has_valid_preds)
{
+ bool normed;
if (dump_file)
dump_predicates (phi, num_def_preds, def_preds,
"Operand defs of phi ");
+
+ normed = normalize_preds (def_preds, &num_def_preds);
+ if (normed && dump_file)
+ {
+ fprintf (dump_file, "\nNormalized to\n");
+ dump_predicates (phi, num_def_preds, def_preds,
+ "Operand defs of phi ");
+ }
is_properly_guarded =
is_superset_of (def_preds, num_def_preds,
preds, num_preds);
Index: testsuite/gcc.dg/uninit-pred-7_d.c
===================================================================
--- testsuite/gcc.dg/uninit-pred-7_d.c (revision 0)
+++ testsuite/gcc.dg/uninit-pred-7_d.c (revision 0)
@@ -0,0 +1,54 @@
+
+/* { dg-do compile { target i?86-*-* x86_64-*-* } } */
+/* { dg-options "-Wuninitialized -O2 -mbranch-cost=0" } */
+
+int g;
+void bar();
+void blah(int);
+
+int foo (int n, int l, int m, int r)
+{
+ int v;
+
+ if (n || l)
+ v = r;
+
+ if (m) g++;
+ else bar();
+
+ if ( n && l)
+ blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */
+
+ if ( n )
+ blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */
+
+ if ( l )
+ blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */
+
+ return 0;
+}
+
+int foo_2 (int n, int l, int m, int r)
+{
+ int v;
+
+ if (n || l)
+ v = r;
+
+ if (m) g++;
+ else bar();
+
+ if ( n && l)
+ blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */
+
+ if ( n )
+ blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */
+
+ if (m || l)
+ blah (v); /* { dg-warning "uninitialized" "warning" } */
+
+ if ( l )
+ blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */
+
+ return 0;
+}
Index: testsuite/gcc.dg/uninit-pred-8_d.c
===================================================================
--- testsuite/gcc.dg/uninit-pred-8_d.c (revision 0)
+++ testsuite/gcc.dg/uninit-pred-8_d.c (revision 0)
@@ -0,0 +1,45 @@
+
+/* { dg-do compile { target i?86-*-* x86_64-*-* } } */
+/* { dg-options "-Wuninitialized -O2 -mbranch-cost=0" } */
+
+int g;
+void bar();
+void blah(int);
+
+int foo (int n, int l, int m, int r)
+{
+ int v;
+
+ if (n || m || r || l)
+ v = r;
+
+ if (m) g++;
+ else bar();
+
+ if ( n || m || r || l)
+ blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */
+
+ if ( n )
+ blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */
+
+ if ( l )
+ blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */
+
+ return 0;
+}
+
+int foo_2 (int n, int l, int m, int r)
+{
+ int v;
+
+ if (n || m || r )
+ v = r;
+
+ if (m) g++;
+ else bar();
+
+ if ( n || m || r || l)
+ blah(v); /* { dg-warning "uninitialized" "warning" } */
+
+ return 0;
+}
