fix for pr47837

[Xinliang David Li <davidxl at google dot com>]

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?

David

2011-03-08  Xinliang David Li  <davidxl@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.

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.  */
+
+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 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;
+
+         /* 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;
+       }
+   }
+
+  VEC_safe_push (use_pred_info_t, heap, x,
+                 VEC_index (use_pred_info_t, pred_chain, 0));
+
+  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 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  */
+      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);