fix for pr47837

fix for pr47837

[Xinliang David Li]

[-- Attachment #1: Type: text/plain, Size: 622 bytes --]

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.

[-- Attachment #2: uninit-norm2.p --]
[-- Type: text/x-pascal, Size: 6027 bytes --]

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);

Re: fix for pr47837

[Xinliang David Li]

On Tue, Mar 8, 2011 at 9:54 AM, Xinliang David Li <davidxl@google.com> 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.

This is done by Andreas Krebble.

David

>
> 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.
>

Re: fix for pr47837

[Diego Novillo]

On Tue, Mar 8, 2011 at 12:54, Xinliang David Li <davidxl@google.com> wrote:

> 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 ..).

I don't think so.  We have been having weird kernel problems in our
machines when running dejagnu.  Try using the kernel I described in a
separate message.


Diego.

Re: fix for pr47837

[Diego Novillo]

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<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.

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);

Re: fix for pr47837

[Xinliang David Li]

[-- Attachment #1: Type: text/plain, Size: 2379 bytes --]

On Tue, Mar 8, 2011 at 10:55 AM, Diego Novillo <dnovillo@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  <davidxl@google.com>

	* gcc.dg/uninit-pred-7_d.c: New test.
	* gcc.dg/uninit-pred-8_d.c: New test.

[-- Attachment #2: uninit-norm3.p --]
[-- Type: text/x-pascal, Size: 8478 bytes --]

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;
+}

Re: fix for pr47837

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 03/08/11 11:55, Diego Novillo 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.
> 
> Right now it's this pattern, but there may be others.  It could grow
> pretty big and ugly.
We have a real problem in that our underlying analysis to eliminate
unexecutable edges is the CFG needs help, particularly for path
sensitive cases.

Given that I'm seeing a real interest in other analysis that ultimately
have problems similar to those for uninitialized variable analysis,
building too much goo into tree-ssa-uninit doesn't seem like a long term
solution.

Jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJNdqfpAAoJEBRtltQi2kC7eaEH/RW9KeI/ak0ZuRa3q1vABWlz
ludq1GhcFC3PETXN7c89a9kfNF3fsSCEUrDWI+klddQVTuJW00915ZcK361Q9K91
ra/uGXJA1N2Uk/sVyb939Q3LkXtyCUrHGT/AIJe8e6FzXEZYCFt1UqOk5O0SVcqb
VNAkZIHagdrGkGBpdn0nyDwf8nJly9iLq6koBPX1gRKXfeboMRUBSno0smqRi4GA
91JLYRwLx/Xydwyxg4hPTdhDZZKWbLhr8exrdvJCJ/eFJBpqtyVVtt5yS+km6Gbv
xe/p/LOVfydNLgLeoAlEPrGIBmp/p5DOtg4MqLt51whJZ7TTveECwNdh3/57mXI=
=BIpv
-----END PGP SIGNATURE-----

Re: fix for pr47837

[Xinliang David Li]

On Tue, Mar 8, 2011 at 2:04 PM, Jeff Law <law@redhat.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 03/08/11 11:55, Diego Novillo 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.
>>
>> Right now it's this pattern, but there may be others.  It could grow
>> pretty big and ugly.
> We have a real problem in that our underlying analysis to eliminate
> unexecutable edges is the CFG needs help, particularly for path
> sensitive cases.
>
> Given that I'm seeing a real interest in other analysis that ultimately
> have problems similar to those for uninitialized variable analysis,
> building too much goo into tree-ssa-uninit doesn't seem like a long term
> solution.

Understood. Is it ok for short term until the long term solution
exists -- this is a small incremental patch which has real benefit
(reducing false positives).

Thanks,

David

>
> Jeff
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.11 (GNU/Linux)
> Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
>
> iQEcBAEBAgAGBQJNdqfpAAoJEBRtltQi2kC7eaEH/RW9KeI/ak0ZuRa3q1vABWlz
> ludq1GhcFC3PETXN7c89a9kfNF3fsSCEUrDWI+klddQVTuJW00915ZcK361Q9K91
> ra/uGXJA1N2Uk/sVyb939Q3LkXtyCUrHGT/AIJe8e6FzXEZYCFt1UqOk5O0SVcqb
> VNAkZIHagdrGkGBpdn0nyDwf8nJly9iLq6koBPX1gRKXfeboMRUBSno0smqRi4GA
> 91JLYRwLx/Xydwyxg4hPTdhDZZKWbLhr8exrdvJCJ/eFJBpqtyVVtt5yS+km6Gbv
> xe/p/LOVfydNLgLeoAlEPrGIBmp/p5DOtg4MqLt51whJZ7TTveECwNdh3/57mXI=
> =BIpv
> -----END PGP SIGNATURE-----
>

Re: fix for pr47837

[Richard Guenther]

On Tue, Mar 8, 2011 at 11:04 PM, Jeff Law <law@redhat.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 03/08/11 11:55, Diego Novillo 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.
>>
>> Right now it's this pattern, but there may be others.  It could grow
>> pretty big and ugly.
> We have a real problem in that our underlying analysis to eliminate
> unexecutable edges is the CFG needs help, particularly for path
> sensitive cases.
>
> Given that I'm seeing a real interest in other analysis that ultimately
> have problems similar to those for uninitialized variable analysis,
> building too much goo into tree-ssa-uninit doesn't seem like a long term
> solution.

True.  I've been repeatedly thinking of building some on-the-side CFG
with value-numbered predicates to also catch the CFG vs. scalar-code
predicate combinations we have.  On such on-the-side data structure
we could do very aggressive jump-threading just for analysis purposes
(experiments when working on separating conditions shows that
a PRE-like algorithm could drive this).

Thanks,
Richard.

Re: fix for pr47837

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 03/09/11 02:45, Richard Guenther wrote:
> On Tue, Mar 8, 2011 at 11:04 PM, Jeff Law <law@redhat.com> wrote:

> True.  I've been repeatedly thinking of building some on-the-side CFG
> with value-numbered predicates to also catch the CFG vs. scalar-code
> predicate combinations we have.  On such on-the-side data structure
> we could do very aggressive jump-threading just for analysis purposes
> (experiments when working on separating conditions shows that
> a PRE-like algorithm could drive this).
I'm pondering the same kind of thing.  PRE on the predicates with a more
structured approach to block copying to isolate the paths seems to be
the way to go.

jeff


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJNd4irAAoJEBRtltQi2kC73SAH/jIC30j/CkWSV9rQGYn+gtfD
WiBXnbYxv7rc6PUqkT8U5I3upk/subJKlAhAQ1D1Eg6355QqpcMh7yZJGz20ovGc
CXQOK1ZbtCXvk6uZ8QamdfowojhkkxQo900c9mJtuaaevjywwt+MX3VwShNIrfbA
bKSIjHVeeZ2qwymNYHV8C82Zss5WA72FQqIpmlTlPKEwWFO49jLld/iXszyjC1cF
OWQdH37ZNgXARibaWI28KZCz5B39yz5F4mljVCyMS9XvNKzfwabT5FHj8btYzdAK
HYoAsBtONN/0/FJPn3I9VwyYC0q8M6tm9BgMyhhVmCU2PWMCt0jZJZA9aW/4X+o=
=R64B
-----END PGP SIGNATURE-----

Re: fix for pr47837

[Richard Guenther]

On Wed, Mar 9, 2011 at 3:03 PM, Jeff Law <law@redhat.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 03/09/11 02:45, Richard Guenther wrote:
>> On Tue, Mar 8, 2011 at 11:04 PM, Jeff Law <law@redhat.com> wrote:
>
>> True.  I've been repeatedly thinking of building some on-the-side CFG
>> with value-numbered predicates to also catch the CFG vs. scalar-code
>> predicate combinations we have.  On such on-the-side data structure
>> we could do very aggressive jump-threading just for analysis purposes
>> (experiments when working on separating conditions shows that
>> a PRE-like algorithm could drive this).
> I'm pondering the same kind of thing.  PRE on the predicates with a more
> structured approach to block copying to isolate the paths seems to be
> the way to go.

FYI I was talking about
http://gcc.gnu.org/ml/gcc-patches/2010-08/msg02098.html, a start to
force preidcate computations to separate
statements.  First post for the idea was at
http://gcc.gnu.org/ml/gcc-patches/2010-08/msg01001.html

Richard.

> jeff
>
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.11 (GNU/Linux)
> Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
>
> iQEcBAEBAgAGBQJNd4irAAoJEBRtltQi2kC73SAH/jIC30j/CkWSV9rQGYn+gtfD
> WiBXnbYxv7rc6PUqkT8U5I3upk/subJKlAhAQ1D1Eg6355QqpcMh7yZJGz20ovGc
> CXQOK1ZbtCXvk6uZ8QamdfowojhkkxQo900c9mJtuaaevjywwt+MX3VwShNIrfbA
> bKSIjHVeeZ2qwymNYHV8C82Zss5WA72FQqIpmlTlPKEwWFO49jLld/iXszyjC1cF
> OWQdH37ZNgXARibaWI28KZCz5B39yz5F4mljVCyMS9XvNKzfwabT5FHj8btYzdAK
> HYoAsBtONN/0/FJPn3I9VwyYC0q8M6tm9BgMyhhVmCU2PWMCt0jZJZA9aW/4X+o=
> =R64B
> -----END PGP SIGNATURE-----
>

Re: fix for pr47837

[Xinliang David Li]

On Wed, Mar 9, 2011 at 6:03 AM, Jeff Law <law@redhat.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 03/09/11 02:45, Richard Guenther wrote:
>> On Tue, Mar 8, 2011 at 11:04 PM, Jeff Law <law@redhat.com> wrote:
>
>> True.  I've been repeatedly thinking of building some on-the-side CFG
>> with value-numbered predicates to also catch the CFG vs. scalar-code
>> predicate combinations we have.  On such on-the-side data structure
>> we could do very aggressive jump-threading just for analysis purposes
>> (experiments when working on separating conditions shows that
>> a PRE-like algorithm could drive this).
> I'm pondering the same kind of thing.  PRE on the predicates with a more
> structured approach to block copying to isolate the paths seems to be
> the way to go.


Any simple examples to show how your idea would work?

Thanks,

David
>
> jeff
>
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.11 (GNU/Linux)
> Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
>
> iQEcBAEBAgAGBQJNd4irAAoJEBRtltQi2kC73SAH/jIC30j/CkWSV9rQGYn+gtfD
> WiBXnbYxv7rc6PUqkT8U5I3upk/subJKlAhAQ1D1Eg6355QqpcMh7yZJGz20ovGc
> CXQOK1ZbtCXvk6uZ8QamdfowojhkkxQo900c9mJtuaaevjywwt+MX3VwShNIrfbA
> bKSIjHVeeZ2qwymNYHV8C82Zss5WA72FQqIpmlTlPKEwWFO49jLld/iXszyjC1cF
> OWQdH37ZNgXARibaWI28KZCz5B39yz5F4mljVCyMS9XvNKzfwabT5FHj8btYzdAK
> HYoAsBtONN/0/FJPn3I9VwyYC0q8M6tm9BgMyhhVmCU2PWMCt0jZJZA9aW/4X+o=
> =R64B
> -----END PGP SIGNATURE-----
>

Re: fix for pr47837

[Richard Guenther]

On Wed, Mar 9, 2011 at 5:24 PM, Xinliang David Li <davidxl@google.com> wrote:
> On Wed, Mar 9, 2011 at 6:03 AM, Jeff Law <law@redhat.com> wrote:
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> On 03/09/11 02:45, Richard Guenther wrote:
>>> On Tue, Mar 8, 2011 at 11:04 PM, Jeff Law <law@redhat.com> wrote:
>>
>>> True.  I've been repeatedly thinking of building some on-the-side CFG
>>> with value-numbered predicates to also catch the CFG vs. scalar-code
>>> predicate combinations we have.  On such on-the-side data structure
>>> we could do very aggressive jump-threading just for analysis purposes
>>> (experiments when working on separating conditions shows that
>>> a PRE-like algorithm could drive this).
>> I'm pondering the same kind of thing.  PRE on the predicates with a more
>> structured approach to block copying to isolate the paths seems to be
>> the way to go.
>
>
> Any simple examples to show how your idea would work?

You basically would copy all paths with redundant predicate computations,
removing them and leaving no redundant checks around.  Of course you
wouldn't really do this code-transformation but just do it to help analyses.

Like in

 if (p)
   foo();
 bar();
 if (p)
   baz();

you'd generate

  if(p)
   {
     foo();
     bar();
     baz();
   }
else
  bar();

for all, even partially redundant predicates.  See the patch I linked to, it
causes PRE to identify them (but do nothing too useful yet)

Richard.

> Thanks,
>
> David
>>
>> jeff
>>
>>
>> -----BEGIN PGP SIGNATURE-----
>> Version: GnuPG v1.4.11 (GNU/Linux)
>> Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
>>
>> iQEcBAEBAgAGBQJNd4irAAoJEBRtltQi2kC73SAH/jIC30j/CkWSV9rQGYn+gtfD
>> WiBXnbYxv7rc6PUqkT8U5I3upk/subJKlAhAQ1D1Eg6355QqpcMh7yZJGz20ovGc
>> CXQOK1ZbtCXvk6uZ8QamdfowojhkkxQo900c9mJtuaaevjywwt+MX3VwShNIrfbA
>> bKSIjHVeeZ2qwymNYHV8C82Zss5WA72FQqIpmlTlPKEwWFO49jLld/iXszyjC1cF
>> OWQdH37ZNgXARibaWI28KZCz5B39yz5F4mljVCyMS9XvNKzfwabT5FHj8btYzdAK
>> HYoAsBtONN/0/FJPn3I9VwyYC0q8M6tm9BgMyhhVmCU2PWMCt0jZJZA9aW/4X+o=
>> =R64B
>> -----END PGP SIGNATURE-----
>>
>

Re: fix for pr47837

[Xinliang David Li]

On Wed, Mar 9, 2011 at 8:29 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Wed, Mar 9, 2011 at 5:24 PM, Xinliang David Li <davidxl@google.com> wrote:
>> On Wed, Mar 9, 2011 at 6:03 AM, Jeff Law <law@redhat.com> wrote:
>>> -----BEGIN PGP SIGNED MESSAGE-----
>>> Hash: SHA1
>>>
>>> On 03/09/11 02:45, Richard Guenther wrote:
>>>> On Tue, Mar 8, 2011 at 11:04 PM, Jeff Law <law@redhat.com> wrote:
>>>
>>>> True.  I've been repeatedly thinking of building some on-the-side CFG
>>>> with value-numbered predicates to also catch the CFG vs. scalar-code
>>>> predicate combinations we have.  On such on-the-side data structure
>>>> we could do very aggressive jump-threading just for analysis purposes
>>>> (experiments when working on separating conditions shows that
>>>> a PRE-like algorithm could drive this).
>>> I'm pondering the same kind of thing.  PRE on the predicates with a more
>>> structured approach to block copying to isolate the paths seems to be
>>> the way to go.
>>
>>
>> Any simple examples to show how your idea would work?
>
> You basically would copy all paths with redundant predicate computations,
> removing them and leaving no redundant checks around.  Of course you
> wouldn't really do this code-transformation but just do it to help analyses.

You will also need to compute SSA on the alternate CFG as well, right?
How will partially redundant predicates handled? Split the predicates?

if (p1 OR p2)
  foo();
bar();
if (p1)
   baz();

==>

if (p1)
{
    foo(); bar(); baz();
}
else if (p2)
{
   foo(); bar();
}
else
   bar();

Things can be complicated when dealing with slightly complex
predicates. For instance

p1 = x | y;   // bitwise OR

p2_1 = (x!=0);
p2_2 = (y!=0);
p2 = (p2_1 & p2_2);

p1 can be split into (x AND !y), p2 , and (!x AND y).

How about short circuite &&, || expressions lowered into if-then-else?
 Will the side CFG collapse the expanded branches and expose the
'original' predicates that are easier to analyze?

Thanks,

David


>
> Like in
>
>  if (p)
>   foo();
>  bar();
>  if (p)
>   baz();
>
> you'd generate
>
>  if(p)
>   {
>     foo();
>     bar();
>     baz();
>   }
> else
>  bar();
>
> for all, even partially redundant predicates.  See the patch I linked to, it
> causes PRE to identify them (but do nothing too useful yet)
>
> Richard.
>
>> Thanks,
>>
>> David
>>>
>>> jeff
>>>
>>>
>>> -----BEGIN PGP SIGNATURE-----
>>> Version: GnuPG v1.4.11 (GNU/Linux)
>>> Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
>>>
>>> iQEcBAEBAgAGBQJNd4irAAoJEBRtltQi2kC73SAH/jIC30j/CkWSV9rQGYn+gtfD
>>> WiBXnbYxv7rc6PUqkT8U5I3upk/subJKlAhAQ1D1Eg6355QqpcMh7yZJGz20ovGc
>>> CXQOK1ZbtCXvk6uZ8QamdfowojhkkxQo900c9mJtuaaevjywwt+MX3VwShNIrfbA
>>> bKSIjHVeeZ2qwymNYHV8C82Zss5WA72FQqIpmlTlPKEwWFO49jLld/iXszyjC1cF
>>> OWQdH37ZNgXARibaWI28KZCz5B39yz5F4mljVCyMS9XvNKzfwabT5FHj8btYzdAK
>>> HYoAsBtONN/0/FJPn3I9VwyYC0q8M6tm9BgMyhhVmCU2PWMCt0jZJZA9aW/4X+o=
>>> =R64B
>>> -----END PGP SIGNATURE-----
>>>
>>
>

Re: fix for pr47837

[Richard Guenther]

On Wed, Mar 9, 2011 at 6:34 PM, Xinliang David Li <davidxl@google.com> wrote:
> On Wed, Mar 9, 2011 at 8:29 AM, Richard Guenther
> <richard.guenther@gmail.com> wrote:
>> On Wed, Mar 9, 2011 at 5:24 PM, Xinliang David Li <davidxl@google.com> wrote:
>>> On Wed, Mar 9, 2011 at 6:03 AM, Jeff Law <law@redhat.com> wrote:
>>>> -----BEGIN PGP SIGNED MESSAGE-----
>>>> Hash: SHA1
>>>>
>>>> On 03/09/11 02:45, Richard Guenther wrote:
>>>>> On Tue, Mar 8, 2011 at 11:04 PM, Jeff Law <law@redhat.com> wrote:
>>>>
>>>>> True.  I've been repeatedly thinking of building some on-the-side CFG
>>>>> with value-numbered predicates to also catch the CFG vs. scalar-code
>>>>> predicate combinations we have.  On such on-the-side data structure
>>>>> we could do very aggressive jump-threading just for analysis purposes
>>>>> (experiments when working on separating conditions shows that
>>>>> a PRE-like algorithm could drive this).
>>>> I'm pondering the same kind of thing.  PRE on the predicates with a more
>>>> structured approach to block copying to isolate the paths seems to be
>>>> the way to go.
>>>
>>>
>>> Any simple examples to show how your idea would work?
>>
>> You basically would copy all paths with redundant predicate computations,
>> removing them and leaving no redundant checks around.  Of course you
>> wouldn't really do this code-transformation but just do it to help analyses.
>
> You will also need to compute SSA on the alternate CFG as well, right?

It depends on what task you want to perform on the alternate CFG.  For
uninitialized vars, yes, likely.

> How will partially redundant predicates handled? Split the predicates?

Yes.

> if (p1 OR p2)
>  foo();
> bar();
> if (p1)
>   baz();
>
> ==>
>
> if (p1)
> {
>    foo(); bar(); baz();
> }
> else if (p2)
> {
>   foo(); bar();
> }
> else
>   bar();
>
> Things can be complicated when dealing with slightly complex
> predicates. For instance
>
> p1 = x | y;   // bitwise OR
>
> p2_1 = (x!=0);
> p2_2 = (y!=0);
> p2 = (p2_1 & p2_2);
>
> p1 can be split into (x AND !y), p2 , and (!x AND y).
>
> How about short circuite &&, || expressions lowered into if-then-else?
>  Will the side CFG collapse the expanded branches and expose the
> 'original' predicates that are easier to analyze?

That all remains to be seen.  Just the current restriction of working on
the present IL for analysis purposes should be lifted (and made easier
w/o the need to re-invent the wheel everywhere).

Richard.

> Thanks,
>
> David
>
>
>>
>> Like in
>>
>>  if (p)
>>   foo();
>>  bar();
>>  if (p)
>>   baz();
>>
>> you'd generate
>>
>>  if(p)
>>   {
>>     foo();
>>     bar();
>>     baz();
>>   }
>> else
>>  bar();
>>
>> for all, even partially redundant predicates.  See the patch I linked to, it
>> causes PRE to identify them (but do nothing too useful yet)
>>
>> Richard.
>>
>>> Thanks,
>>>
>>> David
>>>>
>>>> jeff
>>>>
>>>>
>>>> -----BEGIN PGP SIGNATURE-----
>>>> Version: GnuPG v1.4.11 (GNU/Linux)
>>>> Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
>>>>
>>>> iQEcBAEBAgAGBQJNd4irAAoJEBRtltQi2kC73SAH/jIC30j/CkWSV9rQGYn+gtfD
>>>> WiBXnbYxv7rc6PUqkT8U5I3upk/subJKlAhAQ1D1Eg6355QqpcMh7yZJGz20ovGc
>>>> CXQOK1ZbtCXvk6uZ8QamdfowojhkkxQo900c9mJtuaaevjywwt+MX3VwShNIrfbA
>>>> bKSIjHVeeZ2qwymNYHV8C82Zss5WA72FQqIpmlTlPKEwWFO49jLld/iXszyjC1cF
>>>> OWQdH37ZNgXARibaWI28KZCz5B39yz5F4mljVCyMS9XvNKzfwabT5FHj8btYzdAK
>>>> HYoAsBtONN/0/FJPn3I9VwyYC0q8M6tm9BgMyhhVmCU2PWMCt0jZJZA9aW/4X+o=
>>>> =R64B
>>>> -----END PGP SIGNATURE-----
>>>>
>>>
>>
>

Re: fix for pr47837

[Xinliang David Li]

Ok.

Regarding this particular patch, I hope it can be checked in to make
the test clean. It is a simple enhancement to a wheel that is already
there. It also serves as a case that can be referenced in the future
when the more general mechanism is available.

Thanks,

David

On Wed, Mar 9, 2011 at 9:54 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Wed, Mar 9, 2011 at 6:34 PM, Xinliang David Li <davidxl@google.com> wrote:
>> On Wed, Mar 9, 2011 at 8:29 AM, Richard Guenther
>> <richard.guenther@gmail.com> wrote:
>>> On Wed, Mar 9, 2011 at 5:24 PM, Xinliang David Li <davidxl@google.com> wrote:
>>>> On Wed, Mar 9, 2011 at 6:03 AM, Jeff Law <law@redhat.com> wrote:
>>>>> -----BEGIN PGP SIGNED MESSAGE-----
>>>>> Hash: SHA1
>>>>>
>>>>> On 03/09/11 02:45, Richard Guenther wrote:
>>>>>> On Tue, Mar 8, 2011 at 11:04 PM, Jeff Law <law@redhat.com> wrote:
>>>>>
>>>>>> True.  I've been repeatedly thinking of building some on-the-side CFG
>>>>>> with value-numbered predicates to also catch the CFG vs. scalar-code
>>>>>> predicate combinations we have.  On such on-the-side data structure
>>>>>> we could do very aggressive jump-threading just for analysis purposes
>>>>>> (experiments when working on separating conditions shows that
>>>>>> a PRE-like algorithm could drive this).
>>>>> I'm pondering the same kind of thing.  PRE on the predicates with a more
>>>>> structured approach to block copying to isolate the paths seems to be
>>>>> the way to go.
>>>>
>>>>
>>>> Any simple examples to show how your idea would work?
>>>
>>> You basically would copy all paths with redundant predicate computations,
>>> removing them and leaving no redundant checks around.  Of course you
>>> wouldn't really do this code-transformation but just do it to help analyses.
>>
>> You will also need to compute SSA on the alternate CFG as well, right?
>
> It depends on what task you want to perform on the alternate CFG.  For
> uninitialized vars, yes, likely.
>
>> How will partially redundant predicates handled? Split the predicates?
>
> Yes.
>
>> if (p1 OR p2)
>>  foo();
>> bar();
>> if (p1)
>>   baz();
>>
>> ==>
>>
>> if (p1)
>> {
>>    foo(); bar(); baz();
>> }
>> else if (p2)
>> {
>>   foo(); bar();
>> }
>> else
>>   bar();
>>
>> Things can be complicated when dealing with slightly complex
>> predicates. For instance
>>
>> p1 = x | y;   // bitwise OR
>>
>> p2_1 = (x!=0);
>> p2_2 = (y!=0);
>> p2 = (p2_1 & p2_2);
>>
>> p1 can be split into (x AND !y), p2 , and (!x AND y).
>>
>> How about short circuite &&, || expressions lowered into if-then-else?
>>  Will the side CFG collapse the expanded branches and expose the
>> 'original' predicates that are easier to analyze?
>
> That all remains to be seen.  Just the current restriction of working on
> the present IL for analysis purposes should be lifted (and made easier
> w/o the need to re-invent the wheel everywhere).
>
> Richard.
>
>> Thanks,
>>
>> David
>>
>>
>>>
>>> Like in
>>>
>>>  if (p)
>>>   foo();
>>>  bar();
>>>  if (p)
>>>   baz();
>>>
>>> you'd generate
>>>
>>>  if(p)
>>>   {
>>>     foo();
>>>     bar();
>>>     baz();
>>>   }
>>> else
>>>  bar();
>>>
>>> for all, even partially redundant predicates.  See the patch I linked to, it
>>> causes PRE to identify them (but do nothing too useful yet)
>>>
>>> Richard.
>>>
>>>> Thanks,
>>>>
>>>> David
>>>>>
>>>>> jeff
>>>>>
>>>>>
>>>>> -----BEGIN PGP SIGNATURE-----
>>>>> Version: GnuPG v1.4.11 (GNU/Linux)
>>>>> Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
>>>>>
>>>>> iQEcBAEBAgAGBQJNd4irAAoJEBRtltQi2kC73SAH/jIC30j/CkWSV9rQGYn+gtfD
>>>>> WiBXnbYxv7rc6PUqkT8U5I3upk/subJKlAhAQ1D1Eg6355QqpcMh7yZJGz20ovGc
>>>>> CXQOK1ZbtCXvk6uZ8QamdfowojhkkxQo900c9mJtuaaevjywwt+MX3VwShNIrfbA
>>>>> bKSIjHVeeZ2qwymNYHV8C82Zss5WA72FQqIpmlTlPKEwWFO49jLld/iXszyjC1cF
>>>>> OWQdH37ZNgXARibaWI28KZCz5B39yz5F4mljVCyMS9XvNKzfwabT5FHj8btYzdAK
>>>>> HYoAsBtONN/0/FJPn3I9VwyYC0q8M6tm9BgMyhhVmCU2PWMCt0jZJZA9aW/4X+o=
>>>>> =R64B
>>>>> -----END PGP SIGNATURE-----
>>>>>
>>>>
>>>
>>
>

Re: fix for pr47837

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 03/09/11 11:07, Xinliang David Li wrote:
> Ok.
> 
> Regarding this particular patch, I hope it can be checked in to make
> the test clean. It is a simple enhancement to a wheel that is already
> there. It also serves as a case that can be referenced in the future
> when the more general mechanism is available.
Just to be clear, I'm not going to object to this patch; I don't have
the time right now to really look at it.

I was merely raising the issue that we have a need to solve the larger
problem and that we need to be looking a the bigger picture.

jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJNenjEAAoJEBRtltQi2kC7UmcH/0NmpkxPnJNdYzs0VxeU1ywJ
OnYxF1Za0T0JGgFpVB6NUIPwqTM/2oVG5dth6yk8wOyoVAoDKn/T7LgiLtoa/zRL
Zrr45TpvOytfrfhXmnBZCCRg7J+96GWSo4sFTlCPJe97WY9mBLLgaFgjTvHLdDPu
rA24+3a7U5eIxwvT/xfE9SdJr+GVlSiB1Ud0v9sEKlrb+hhe5pXsus3oD/oaIw08
zVqRcfTIvViA8/9c3Gqj/g6yk6Wu5aHjETtxHIQcP8OWasPioLmCda6Or43pJnJX
p8RhCov6FgWTYXdC62XwXNqPJtBE3q8rVadwz6xG28xf7GuNz7uevIfnWPK4i20=
=g4+b
-----END PGP SIGNATURE-----

Re: fix for pr47837

[Diego Novillo]

On Fri, Mar 11, 2011 at 14:32, Jeff Law <law@redhat.com> wrote:

>> Regarding this particular patch, I hope it can be checked in to make
>> the test clean. It is a simple enhancement to a wheel that is already
>> there. It also serves as a case that can be referenced in the future
>> when the more general mechanism is available.
> Just to be clear, I'm not going to object to this patch; I don't have
> the time right now to really look at it.
>
> I was merely raising the issue that we have a need to solve the larger
> problem and that we need to be looking a the bigger picture.

Agreed.  I'm not happy about the patch, but I won't object to it.
It's clear, however, that we cannot keep adding hack on top of hack
here.  David, will you be looking at creating a more general solution
for 4.7?

Given the stage we are in, you will need OKs from our release managers for 4.6.


Diego.

Re: fix for pr47837

[Xinliang David Li]

On Mon, Mar 14, 2011 at 6:16 AM, Diego Novillo <dnovillo@google.com> wrote:
> On Fri, Mar 11, 2011 at 14:32, Jeff Law <law@redhat.com> wrote:
>
>>> Regarding this particular patch, I hope it can be checked in to make
>>> the test clean. It is a simple enhancement to a wheel that is already
>>> there. It also serves as a case that can be referenced in the future
>>> when the more general mechanism is available.
>> Just to be clear, I'm not going to object to this patch; I don't have
>> the time right now to really look at it.
>>
>> I was merely raising the issue that we have a need to solve the larger
>> problem and that we need to be looking a the bigger picture.
>
> Agreed.  I'm not happy about the patch, but I won't object to it.
> It's clear, however, that we cannot keep adding hack on top of hack
> here.

I don't think I have added too many pattern handling (aka Hack) since
the predicate aware analysis was checked in -- this is actually the
first attempt to try to do predicate simplification.  Things like this
is a natural course of software evolution.

> David, will you be looking at creating a more general solution
> for 4.7?

I think it is a good area to explore, not necessarily by me though.

>
> Given the stage we are in, you will need OKs from our release managers for 4.6.
>

Richard, if it is too late for 4.6, I can wait until stage-1 is reopened.

Thanks,

David

>
> Diego.
>

Re: fix for pr47837

[Richard Guenther]

On Mon, Mar 14, 2011 at 5:33 PM, Xinliang David Li <davidxl@google.com> wrote:
> On Mon, Mar 14, 2011 at 6:16 AM, Diego Novillo <dnovillo@google.com> wrote:
>> On Fri, Mar 11, 2011 at 14:32, Jeff Law <law@redhat.com> wrote:
>>
>>>> Regarding this particular patch, I hope it can be checked in to make
>>>> the test clean. It is a simple enhancement to a wheel that is already
>>>> there. It also serves as a case that can be referenced in the future
>>>> when the more general mechanism is available.
>>> Just to be clear, I'm not going to object to this patch; I don't have
>>> the time right now to really look at it.
>>>
>>> I was merely raising the issue that we have a need to solve the larger
>>> problem and that we need to be looking a the bigger picture.
>>
>> Agreed.  I'm not happy about the patch, but I won't object to it.
>> It's clear, however, that we cannot keep adding hack on top of hack
>> here.
>
> I don't think I have added too many pattern handling (aka Hack) since
> the predicate aware analysis was checked in -- this is actually the
> first attempt to try to do predicate simplification.  Things like this
> is a natural course of software evolution.
>
>> David, will you be looking at creating a more general solution
>> for 4.7?
>
> I think it is a good area to explore, not necessarily by me though.
>
>>
>> Given the stage we are in, you will need OKs from our release managers for 4.6.
>>
>
> Richard, if it is too late for 4.6, I can wait until stage-1 is reopened.

Should happen soon.  So, yes, please wait for stage1 and then eventually
backport for 4.6.1.

Thanks,
Richard.

Re: fix for pr47837

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 03/09/11 09:24, Xinliang David Li wrote:
> On Wed, Mar 9, 2011 at 6:03 AM, Jeff Law <law@redhat.com> wrote:
> On 03/09/11 02:45, Richard Guenther wrote:
>>>> On Tue, Mar 8, 2011 at 11:04 PM, Jeff Law <law@redhat.com> wrote:
> 
>>>> True.  I've been repeatedly thinking of building some on-the-side CFG
>>>> with value-numbered predicates to also catch the CFG vs. scalar-code
>>>> predicate combinations we have.  On such on-the-side data structure
>>>> we could do very aggressive jump-threading just for analysis purposes
>>>> (experiments when working on separating conditions shows that
>>>> a PRE-like algorithm could drive this).
> I'm pondering the same kind of thing.  PRE on the predicates with a more
> structured approach to block copying to isolate the paths seems to be
> the way to go.
> 
> 
>> Any simple examples to show how your idea would work?
Our current jump threading is just a special case of path isolation; the
biggest problem with path isolation is exploding codesize.

I'd like to see that code generalized in a few ways based on well known
algorithms rather than the ad-hoc stuff we've got now keeping a
reasonable knob on the codesize bloat.

In cases where we want more accurate warnings, but aren't willing to
accept the size bloat, on the side structures might be the way to go.

I'm still looking a literature on the subject, but there's clearly
things we can do to improve the path sensitivity of the optimizers and
warning analysis.

jeff

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJNenzuAAoJEBRtltQi2kC78csH/iBQvJ7UC8NQSgyYg6VRs0zZ
PeQtFOkEmZ5cmnBSswl6y82hXmBERXrvqx2/jkQa5AkM7m1gOwh8ieI40hDdsDZi
6253orEdlsWxnXJ7LOm/pmGD5JexSPNq2bbPD+fQZ6W+Xtoh4ckoyCA/f3PMQpXG
gugkRMKjwAoMHplEOZHDCQpdgssPQjsa226UwyEcvEb5mi01Atfq4PtvchYF8rnY
P2FisaYgHIbi9Ct7infXZVkPyvh0tVbbCwS/s/OPBkf+Ez6mHmEOx9dwOIkJdQEv
8uV7hXQmGbI9wLh+0Q1ZQ36o918mL4h4zYXQ8TGlqY4kVg1WEWRr1Pt+iNs7heA=
=2zgD
-----END PGP SIGNATURE-----

Re: fix for pr47837

[Richard Guenther]

On Fri, Mar 11, 2011 at 8:50 PM, Jeff Law <law@redhat.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 03/09/11 09:24, Xinliang David Li wrote:
>> On Wed, Mar 9, 2011 at 6:03 AM, Jeff Law <law@redhat.com> wrote:
>> On 03/09/11 02:45, Richard Guenther wrote:
>>>>> On Tue, Mar 8, 2011 at 11:04 PM, Jeff Law <law@redhat.com> wrote:
>>
>>>>> True.  I've been repeatedly thinking of building some on-the-side CFG
>>>>> with value-numbered predicates to also catch the CFG vs. scalar-code
>>>>> predicate combinations we have.  On such on-the-side data structure
>>>>> we could do very aggressive jump-threading just for analysis purposes
>>>>> (experiments when working on separating conditions shows that
>>>>> a PRE-like algorithm could drive this).
>> I'm pondering the same kind of thing.  PRE on the predicates with a more
>> structured approach to block copying to isolate the paths seems to be
>> the way to go.
>>
>>
>>> Any simple examples to show how your idea would work?
> Our current jump threading is just a special case of path isolation; the
> biggest problem with path isolation is exploding codesize.
>
> I'd like to see that code generalized in a few ways based on well known
> algorithms rather than the ad-hoc stuff we've got now keeping a
> reasonable knob on the codesize bloat.
>
> In cases where we want more accurate warnings, but aren't willing to
> accept the size bloat, on the side structures might be the way to go.
>
> I'm still looking a literature on the subject, but there's clearly
> things we can do to improve the path sensitivity of the optimizers and
> warning analysis.

Yes, I am also thinking of static analysis stuff people seem to want.
That requires us to not actually do any transform.

Richard.

Re: fix for pr47837

[Xinliang David Li]

On Fri, Mar 11, 2011 at 11:50 AM, Jeff Law <law@redhat.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 03/09/11 09:24, Xinliang David Li wrote:
>> On Wed, Mar 9, 2011 at 6:03 AM, Jeff Law <law@redhat.com> wrote:
>> On 03/09/11 02:45, Richard Guenther wrote:
>>>>> On Tue, Mar 8, 2011 at 11:04 PM, Jeff Law <law@redhat.com> wrote:
>>
>>>>> True.  I've been repeatedly thinking of building some on-the-side CFG
>>>>> with value-numbered predicates to also catch the CFG vs. scalar-code
>>>>> predicate combinations we have.  On such on-the-side data structure
>>>>> we could do very aggressive jump-threading just for analysis purposes
>>>>> (experiments when working on separating conditions shows that
>>>>> a PRE-like algorithm could drive this).
>> I'm pondering the same kind of thing.  PRE on the predicates with a more
>> structured approach to block copying to isolate the paths seems to be
>> the way to go.
>>
>>
>>> Any simple examples to show how your idea would work?
> Our current jump threading is just a special case of path isolation; the
> biggest problem with path isolation is exploding codesize.

Jump threading can reduce size in some cases -- due to more aggressive
cleanups -- the -Os need to be more intelligent about it.

>
> I'd like to see that code generalized in a few ways based on well known
> algorithms rather than the ad-hoc stuff we've got now keeping a
> reasonable knob on the codesize bloat.
>
> In cases where we want more accurate warnings, but aren't willing to
> accept the size bloat, on the side structures might be the way to go.
>
> I'm still looking a literature on the subject, but there's clearly
> things we can do to improve the path sensitivity of the optimizers and
> warning analysis.

There are actually many papers on this (e.g. IMPACT group)  as a
result of research for EPIC optimizations (predication and if
convert). Most of them talk about predicate query systems (efficient
and accurate), e.g PQS using partition graph, PAS using BDD etc.  The
predicates relation can be built as side data structure, and the
following queries can be made:

 p1 = get_predicate (gimple_stmt1);
 p2 = get_predicate (gimple_stmt2);

if (is_disjoint (p1, p2) )
  ..
else if is_subset(p1, p2).
   ..

Keeping the information up to date with transformations can be difficult.

David


>
> jeff
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.11 (GNU/Linux)
> Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
>
> iQEcBAEBAgAGBQJNenzuAAoJEBRtltQi2kC78csH/iBQvJ7UC8NQSgyYg6VRs0zZ
> PeQtFOkEmZ5cmnBSswl6y82hXmBERXrvqx2/jkQa5AkM7m1gOwh8ieI40hDdsDZi
> 6253orEdlsWxnXJ7LOm/pmGD5JexSPNq2bbPD+fQZ6W+Xtoh4ckoyCA/f3PMQpXG
> gugkRMKjwAoMHplEOZHDCQpdgssPQjsa226UwyEcvEb5mi01Atfq4PtvchYF8rnY
> P2FisaYgHIbi9Ct7infXZVkPyvh0tVbbCwS/s/OPBkf+Ez6mHmEOx9dwOIkJdQEv
> 8uV7hXQmGbI9wLh+0Q1ZQ36o918mL4h4zYXQ8TGlqY4kVg1WEWRr1Pt+iNs7heA=
> =2zgD
> -----END PGP SIGNATURE-----
>

Re: fix for pr47837

[Richard Guenther]

On Sat, Mar 12, 2011 at 1:44 AM, Xinliang David Li <davidxl@google.com> wrote:
> On Fri, Mar 11, 2011 at 11:50 AM, Jeff Law <law@redhat.com> wrote:
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> On 03/09/11 09:24, Xinliang David Li wrote:
>>> On Wed, Mar 9, 2011 at 6:03 AM, Jeff Law <law@redhat.com> wrote:
>>> On 03/09/11 02:45, Richard Guenther wrote:
>>>>>> On Tue, Mar 8, 2011 at 11:04 PM, Jeff Law <law@redhat.com> wrote:
>>>
>>>>>> True.  I've been repeatedly thinking of building some on-the-side CFG
>>>>>> with value-numbered predicates to also catch the CFG vs. scalar-code
>>>>>> predicate combinations we have.  On such on-the-side data structure
>>>>>> we could do very aggressive jump-threading just for analysis purposes
>>>>>> (experiments when working on separating conditions shows that
>>>>>> a PRE-like algorithm could drive this).
>>> I'm pondering the same kind of thing.  PRE on the predicates with a more
>>> structured approach to block copying to isolate the paths seems to be
>>> the way to go.
>>>
>>>
>>>> Any simple examples to show how your idea would work?
>> Our current jump threading is just a special case of path isolation; the
>> biggest problem with path isolation is exploding codesize.
>
> Jump threading can reduce size in some cases -- due to more aggressive
> cleanups -- the -Os need to be more intelligent about it.
>
>>
>> I'd like to see that code generalized in a few ways based on well known
>> algorithms rather than the ad-hoc stuff we've got now keeping a
>> reasonable knob on the codesize bloat.
>>
>> In cases where we want more accurate warnings, but aren't willing to
>> accept the size bloat, on the side structures might be the way to go.
>>
>> I'm still looking a literature on the subject, but there's clearly
>> things we can do to improve the path sensitivity of the optimizers and
>> warning analysis.
>
> There are actually many papers on this (e.g. IMPACT group)  as a
> result of research for EPIC optimizations (predication and if
> convert). Most of them talk about predicate query systems (efficient
> and accurate), e.g PQS using partition graph, PAS using BDD etc.  The
> predicates relation can be built as side data structure, and the
> following queries can be made:
>
>  p1 = get_predicate (gimple_stmt1);
>  p2 = get_predicate (gimple_stmt2);
>
> if (is_disjoint (p1, p2) )
>  ..
> else if is_subset(p1, p2).
>   ..
>
> Keeping the information up to date with transformations can be difficult.

Sure, I'd say this is a clear candidate for something that would get
re-computed if needed.

Richard.

Re: fix for pr47837

[Xinliang David Li]

Sounds interesting. Do you have examples to illustrate your idea?

Thanks,

David

On Wed, Mar 9, 2011 at 1:45 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Tue, Mar 8, 2011 at 11:04 PM, Jeff Law <law@redhat.com> wrote:
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> On 03/08/11 11:55, Diego Novillo 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.
>>>
>>> Right now it's this pattern, but there may be others.  It could grow
>>> pretty big and ugly.
>> We have a real problem in that our underlying analysis to eliminate
>> unexecutable edges is the CFG needs help, particularly for path
>> sensitive cases.
>>
>> Given that I'm seeing a real interest in other analysis that ultimately
>> have problems similar to those for uninitialized variable analysis,
>> building too much goo into tree-ssa-uninit doesn't seem like a long term
>> solution.
>
> True.  I've been repeatedly thinking of building some on-the-side CFG
> with value-numbered predicates to also catch the CFG vs. scalar-code
> predicate combinations we have.  On such on-the-side data structure
> we could do very aggressive jump-threading just for analysis purposes
> (experiments when working on separating conditions shows that
> a PRE-like algorithm could drive this).
>
> Thanks,
> Richard.
>

Re: fix for pr47837

[Jakub Jelinek]

On Tue, Mar 08, 2011 at 09:54:42AM -0800, 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.

BTW, PR47679 is another case of predicates too complicated for
tree-ssa-uninit ATM.

	Jakub

Re: fix for pr47837

[Eric Botcazou]

> 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.

This broke the Ada compiler on some platforms, see PR tree-opt/48988.

-- 
Eric Botcazou