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.
Right now it's this pattern, but there may be others. It could grow
pretty big and ugly.
2011-03-08 Xinliang David Li<davi...@google.com>
PR c/47837
* tree-ssa-uninit.c (pred_chain_length_cmp): New function.
(normalize_preds): New function.
(is_use_properly_guarded): Normalize def predicates.
Could you add some tests? I realize this fixes 390 testcases, but are
there tests where we could explicitly check that this is triggering?
Index: tree-ssa-uninit.c
===================================================================
--- tree-ssa-uninit.c (revision 170150)
+++ tree-ssa-uninit.c (working copy)
@@ -1605,6 +1605,153 @@ 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
+ simplication. */
s/simplication/simplification/
There is another instance of this later.
+
+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;
space around '*'.
+
+ 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);
The UIDs are not necessarily stable from call to call. Would this be a
problem? It doesn't seem that it would.
+}
+
+/* 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)
+ {
Why not just one '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 simplication 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;
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'?
+
+ /* 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];
Space around '+'.
+
+ preds[*n - 1] = 0;
+ *n = *n - 1;
+ }
+ }
+
+ VEC_safe_push (use_pred_info_t, heap, x,
+ VEC_index (use_pred_info_t, pred_chain, 0));
+
+ for (i = 1; i < *n; i++)
+ {
Please add a comment describing what this loop does.
+ 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 chain. */
+ 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 */
End comment with '. */'
+ 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 +1805,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);
