Patchwork Break infinite folding loop

login
register
mail settings
Submitter Marc Glisse
Date May 16, 2013, 6:42 a.m.
Message ID <alpine.DEB.2.02.1305160812140.3250@stedding.saclay.inria.fr>
Download mbox | patch
Permalink /patch/244228/
State New
Headers show

Comments

Marc Glisse - May 16, 2013, 6:42 a.m.
Hello,

we can get into a cycle where:
(x<0)|1 becomes (x<0)?-1:1
and
(y?-1:1) becomes y|1

Contrary to what I posted in the PR, I am disabling the second 
transformation here. It can be done later (the x86 target partially does 
it in the vcond expansion), and the VEC_COND_EXPR allows us to perform 
further operations:
(((x<0)|1)*5-1)/2 becomes (untested) (x<0)?-3:2

Also, this is a partial revert of the last patch, which sounds safer. I am 
leaving the vector tests in the disabled transformations in case we decide 
to re-enable them later.

This isn't the end of the story, even for fold-const.c. I kept the 
transformation a?-1:0 -> a, but it does not work because:

           /* If we try to convert OP0 to our type, the
              call to fold will try to move the conversion inside
              a COND, which will recurse.  In that case, the COND_EXPR
              is probably the best choice, so leave it alone.  */
           && type == TREE_TYPE (arg0))

and when a is a comparison, its type is a different type (even looking 
through main variant and canonical), only useless_type_conversion_p 
notices they are so similar, and I would still need a conversion, 
otherwise the front-end complains when I try to assign the result that it 
has a different type than the variable I want to assign it to (I expected 
the result of the comparison to be opaque, and thus no complaining, but 
apparently not).

Also, we may want to make fold_binary_op_with_conditional_arg more strict 
on how much folding is necessary to consider the transformation worth it. 
For VEC_COND_EXPR where both branches are evaluated anyway, at least if we 
started from a comparison and not already a VEC_COND_EXPR, we could 
require that both branches fold.

But it seems better to fix the ICE quickly and do the rest later.

Passes bootstrap+testsuite on x86_64-linux-gnu.

2013-05-16  Marc Glisse  <marc.glisse@inria.fr>

 	PR middle-end/57286
gcc/
 	* fold-const.c (fold_ternary_loc) <VEC_COND_EXPR>: Disable some
 	transformations to avoid an infinite loop.

gcc/testsuite/
 	* gcc.dg/pr57286.c: New testcase.
 	* gcc.dg/vector-shift-2.c: Don't assume int has size 4.
 	* g++.dg/ext/vector22.C: Comment out transformations not
 	performed anymore.
Richard Guenther - May 16, 2013, 9:02 a.m.
On Thu, May 16, 2013 at 8:42 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
> Hello,
>
> we can get into a cycle where:
> (x<0)|1 becomes (x<0)?-1:1
> and
> (y?-1:1) becomes y|1
>
> Contrary to what I posted in the PR, I am disabling the second
> transformation here. It can be done later (the x86 target partially does it
> in the vcond expansion), and the VEC_COND_EXPR allows us to perform further
> operations:
> (((x<0)|1)*5-1)/2 becomes (untested) (x<0)?-3:2
>
> Also, this is a partial revert of the last patch, which sounds safer. I am
> leaving the vector tests in the disabled transformations in case we decide
> to re-enable them later.
>
> This isn't the end of the story, even for fold-const.c. I kept the
> transformation a?-1:0 -> a, but it does not work because:
>
>           /* If we try to convert OP0 to our type, the
>              call to fold will try to move the conversion inside
>              a COND, which will recurse.  In that case, the COND_EXPR
>              is probably the best choice, so leave it alone.  */
>           && type == TREE_TYPE (arg0))
>
> and when a is a comparison, its type is a different type (even looking
> through main variant and canonical), only useless_type_conversion_p notices
> they are so similar, and I would still need a conversion, otherwise the
> front-end complains when I try to assign the result that it has a different
> type than the variable I want to assign it to (I expected the result of the
> comparison to be opaque, and thus no complaining, but apparently not).

Which is why most of these non-trivial transforms should happen on GIMPLE
via what I and Andrew proposed some year(s) ago.  But well ...

> Also, we may want to make fold_binary_op_with_conditional_arg more strict on
> how much folding is necessary to consider the transformation worth it. For
> VEC_COND_EXPR where both branches are evaluated anyway, at least if we
> started from a comparison and not already a VEC_COND_EXPR, we could require
> that both branches fold.
>
> But it seems better to fix the ICE quickly and do the rest later.
>
> Passes bootstrap+testsuite on x86_64-linux-gnu.

Ok.

Thanks,
Richard.

> 2013-05-16  Marc Glisse  <marc.glisse@inria.fr>
>
>         PR middle-end/57286
> gcc/
>         * fold-const.c (fold_ternary_loc) <VEC_COND_EXPR>: Disable some
>         transformations to avoid an infinite loop.
>
> gcc/testsuite/
>         * gcc.dg/pr57286.c: New testcase.
>         * gcc.dg/vector-shift-2.c: Don't assume int has size 4.
>         * g++.dg/ext/vector22.C: Comment out transformations not
>         performed anymore.
>
> --
> Marc Glisse
> Index: testsuite/gcc.dg/pr57286.c
> ===================================================================
> --- testsuite/gcc.dg/pr57286.c  (revision 0)
> +++ testsuite/gcc.dg/pr57286.c  (revision 0)
> @@ -0,0 +1,7 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O" } */
> +
> +typedef int vec __attribute__ ((vector_size (4*sizeof(int))));
> +void f (vec *x){
> +    *x = (*x < 0) | 1;
> +}
>
> Property changes on: testsuite/gcc.dg/pr57286.c
> ___________________________________________________________________
> Added: svn:keywords
>    + Author Date Id Revision URL
> Added: svn:eol-style
>    + native
>
> Index: testsuite/gcc.dg/vector-shift-2.c
> ===================================================================
> --- testsuite/gcc.dg/vector-shift-2.c   (revision 198950)
> +++ testsuite/gcc.dg/vector-shift-2.c   (working copy)
> @@ -1,13 +1,13 @@
>  /* { dg-do compile } */
>  /* { dg-options "-O -fdump-tree-ccp1" } */
>
> -typedef unsigned vec __attribute__ ((vector_size (16)));
> +typedef unsigned vec __attribute__ ((vector_size (4*sizeof(int))));
>  void
>  f (vec *a)
>  {
>    vec s = { 5, 5, 5, 5 };
>    *a = *a << s;
>  }
>
>  /* { dg-final { scan-tree-dump "<< 5" "ccp1" } } */
>  /* { dg-final { cleanup-tree-dump "ccp1" } } */
> Index: testsuite/g++.dg/ext/vector22.C
> ===================================================================
> --- testsuite/g++.dg/ext/vector22.C     (revision 198950)
> +++ testsuite/g++.dg/ext/vector22.C     (working copy)
> @@ -1,20 +1,22 @@
>  /* { dg-do compile } */
>  /* { dg-options "-O -fdump-tree-gimple" } */
>
>  typedef unsigned vec __attribute__((vector_size(4*sizeof(int))));
>
> +/* Disabled after PR57286
>  void f(vec*a,vec*b){
>    *a=(*a)?-1:(*b<10);
>    *b=(*b)?(*a<10):0;
>  }
> +*/
>  void g(vec*a,vec*b){
>    *a=(*a)?(*a<*a):-1;
> -  *b=(*b)?-1:(*b<*b);
> +// *b=(*b)?-1:(*b<*b);
>  }
>  void h(vec*a){
>    *a=(~*a==5);
>  }
>
>  /* { dg-final { scan-tree-dump-not "~" "gimple" } } */
>  /* { dg-final { scan-tree-dump-not "VEC_COND_EXPR" "gimple" } } */
>  /* { dg-final { cleanup-tree-dump "gimple" } } */
> Index: fold-const.c
> ===================================================================
> --- fold-const.c        (revision 198950)
> +++ fold-const.c        (working copy)
> @@ -14204,20 +14204,26 @@ fold_ternary_loc (location_t loc, enum t
>           && TREE_CODE (arg0) == NE_EXPR
>           && integer_zerop (TREE_OPERAND (arg0, 1))
>           && integer_pow2p (arg1)
>           && TREE_CODE (TREE_OPERAND (arg0, 0)) == BIT_AND_EXPR
>           && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1),
>                               arg1, OEP_ONLY_CONST))
>         return pedantic_non_lvalue_loc (loc,
>                                     fold_convert_loc (loc, type,
>                                                       TREE_OPERAND (arg0,
> 0)));
>
> +      /* Disable the transformations below for vectors, since
> +        fold_binary_op_with_conditional_arg may undo them immediately,
> +        yielding an infinite loop.  */
> +      if (code == VEC_COND_EXPR)
> +       return NULL_TREE;
> +
>        /* Convert A ? B : 0 into A && B if A and B are truth values.  */
>        if (integer_zerop (op2)
>           && truth_value_p (TREE_CODE (arg0))
>           && truth_value_p (TREE_CODE (arg1))
>           && (code == VEC_COND_EXPR || !VECTOR_TYPE_P (type)))
>         return fold_build2_loc (loc, code == VEC_COND_EXPR ? BIT_AND_EXPR
>                                                            :
> TRUTH_ANDIF_EXPR,
>                                 type, fold_convert_loc (loc, type, arg0),
> arg1);
>
>        /* Convert A ? B : 1 into !A || B if A and B are truth values.  */
>
Marc Glisse - May 16, 2013, 10:05 a.m.
On Thu, 16 May 2013, Richard Biener wrote:

> On Thu, May 16, 2013 at 8:42 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> Hello,
>>
>> we can get into a cycle where:
>> (x<0)|1 becomes (x<0)?-1:1
>> and
>> (y?-1:1) becomes y|1
>>
>> Contrary to what I posted in the PR, I am disabling the second
>> transformation here. It can be done later (the x86 target partially does it
>> in the vcond expansion), and the VEC_COND_EXPR allows us to perform further
>> operations:
>> (((x<0)|1)*5-1)/2 becomes (untested) (x<0)?-3:2
>>
>> Also, this is a partial revert of the last patch, which sounds safer. I am
>> leaving the vector tests in the disabled transformations in case we decide
>> to re-enable them later.
>>
>> This isn't the end of the story, even for fold-const.c. I kept the
>> transformation a?-1:0 -> a, but it does not work because:
>>
>>           /* If we try to convert OP0 to our type, the
>>              call to fold will try to move the conversion inside
>>              a COND, which will recurse.  In that case, the COND_EXPR
>>              is probably the best choice, so leave it alone.  */
>>           && type == TREE_TYPE (arg0))
>>
>> and when a is a comparison, its type is a different type (even looking
>> through main variant and canonical), only useless_type_conversion_p notices
>> they are so similar, and I would still need a conversion, otherwise the
>> front-end complains when I try to assign the result that it has a different
>> type than the variable I want to assign it to (I expected the result of the
>> comparison to be opaque, and thus no complaining, but apparently not).
>
> Which is why most of these non-trivial transforms should happen on GIMPLE

Indeed, I guess I'll try that instead of risking more infinite loops, 
thanks. Although when a transformation exists in fold-const.c, it is 
always tempting to adapt it instead of rewriting it elsewhere in the 
compiler (where it ends up 3 times as long and complicated)...

> via what I and Andrew proposed some year(s) ago.  But well ...

You mean the existing tree-ssa-forwprop.c, or something different?
(I remember the valueize idea)

>> Also, we may want to make fold_binary_op_with_conditional_arg more strict on
>> how much folding is necessary to consider the transformation worth it. For
>> VEC_COND_EXPR where both branches are evaluated anyway, at least if we
>> started from a comparison and not already a VEC_COND_EXPR, we could require
>> that both branches fold.
>>
>> But it seems better to fix the ICE quickly and do the rest later.
>>
>> Passes bootstrap+testsuite on x86_64-linux-gnu.
>
> Ok.
>
> Thanks,
> Richard.
>
>> 2013-05-16  Marc Glisse  <marc.glisse@inria.fr>
>>
>>         PR middle-end/57286
>> gcc/
>>         * fold-const.c (fold_ternary_loc) <VEC_COND_EXPR>: Disable some
>>         transformations to avoid an infinite loop.
>>
>> gcc/testsuite/
>>         * gcc.dg/pr57286.c: New testcase.
>>         * gcc.dg/vector-shift-2.c: Don't assume int has size 4.
>>         * g++.dg/ext/vector22.C: Comment out transformations not
>>         performed anymore.
Richard Guenther - May 16, 2013, 12:08 p.m.
On Thu, May 16, 2013 at 12:05 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Thu, 16 May 2013, Richard Biener wrote:
>
>> On Thu, May 16, 2013 at 8:42 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
>>>
>>> Hello,
>>>
>>> we can get into a cycle where:
>>> (x<0)|1 becomes (x<0)?-1:1
>>> and
>>> (y?-1:1) becomes y|1
>>>
>>> Contrary to what I posted in the PR, I am disabling the second
>>> transformation here. It can be done later (the x86 target partially does
>>> it
>>> in the vcond expansion), and the VEC_COND_EXPR allows us to perform
>>> further
>>> operations:
>>> (((x<0)|1)*5-1)/2 becomes (untested) (x<0)?-3:2
>>>
>>> Also, this is a partial revert of the last patch, which sounds safer. I
>>> am
>>> leaving the vector tests in the disabled transformations in case we
>>> decide
>>> to re-enable them later.
>>>
>>> This isn't the end of the story, even for fold-const.c. I kept the
>>> transformation a?-1:0 -> a, but it does not work because:
>>>
>>>           /* If we try to convert OP0 to our type, the
>>>              call to fold will try to move the conversion inside
>>>              a COND, which will recurse.  In that case, the COND_EXPR
>>>              is probably the best choice, so leave it alone.  */
>>>           && type == TREE_TYPE (arg0))
>>>
>>> and when a is a comparison, its type is a different type (even looking
>>> through main variant and canonical), only useless_type_conversion_p
>>> notices
>>> they are so similar, and I would still need a conversion, otherwise the
>>> front-end complains when I try to assign the result that it has a
>>> different
>>> type than the variable I want to assign it to (I expected the result of
>>> the
>>> comparison to be opaque, and thus no complaining, but apparently not).
>>
>>
>> Which is why most of these non-trivial transforms should happen on GIMPLE
>
>
> Indeed, I guess I'll try that instead of risking more infinite loops,
> thanks. Although when a transformation exists in fold-const.c, it is always
> tempting to adapt it instead of rewriting it elsewhere in the compiler
> (where it ends up 3 times as long and complicated)...
>
>
>> via what I and Andrew proposed some year(s) ago.  But well ...
>
>
> You mean the existing tree-ssa-forwprop.c, or something different?
> (I remember the valueize idea)

Basically what tree-ssa-forwprop.c does but wrapped in a fold-const like
interface.  See http://gcc.gnu.org/ml/gcc-patches/2011-03/msg01099.html,
Andrew was having a branch somewhen.

Richard.

>
>>> Also, we may want to make fold_binary_op_with_conditional_arg more strict
>>> on
>>> how much folding is necessary to consider the transformation worth it.
>>> For
>>> VEC_COND_EXPR where both branches are evaluated anyway, at least if we
>>> started from a comparison and not already a VEC_COND_EXPR, we could
>>> require
>>> that both branches fold.
>>>
>>> But it seems better to fix the ICE quickly and do the rest later.
>>>
>>> Passes bootstrap+testsuite on x86_64-linux-gnu.
>>
>>
>> Ok.
>>
>> Thanks,
>> Richard.
>>
>>> 2013-05-16  Marc Glisse  <marc.glisse@inria.fr>
>>>
>>>         PR middle-end/57286
>>> gcc/
>>>         * fold-const.c (fold_ternary_loc) <VEC_COND_EXPR>: Disable some
>>>         transformations to avoid an infinite loop.
>>>
>>> gcc/testsuite/
>>>         * gcc.dg/pr57286.c: New testcase.
>>>         * gcc.dg/vector-shift-2.c: Don't assume int has size 4.
>>>         * g++.dg/ext/vector22.C: Comment out transformations not
>>>         performed anymore.
>
>
> --
> Marc Glisse

Patch

Index: testsuite/gcc.dg/pr57286.c

===================================================================
--- testsuite/gcc.dg/pr57286.c	(revision 0)

+++ testsuite/gcc.dg/pr57286.c	(revision 0)

@@ -0,0 +1,7 @@ 

+/* { dg-do compile } */

+/* { dg-options "-O" } */

+

+typedef int vec __attribute__ ((vector_size (4*sizeof(int))));

+void f (vec *x){

+    *x = (*x < 0) | 1;

+}


Property changes on: testsuite/gcc.dg/pr57286.c
___________________________________________________________________
Added: svn:keywords
   + Author Date Id Revision URL
Added: svn:eol-style
   + native

Index: testsuite/gcc.dg/vector-shift-2.c

===================================================================
--- testsuite/gcc.dg/vector-shift-2.c	(revision 198950)

+++ testsuite/gcc.dg/vector-shift-2.c	(working copy)

@@ -1,13 +1,13 @@ 

 /* { dg-do compile } */
 /* { dg-options "-O -fdump-tree-ccp1" } */
 
-typedef unsigned vec __attribute__ ((vector_size (16)));

+typedef unsigned vec __attribute__ ((vector_size (4*sizeof(int))));

 void
 f (vec *a)
 {
   vec s = { 5, 5, 5, 5 };
   *a = *a << s;
 }
 
 /* { dg-final { scan-tree-dump "<< 5" "ccp1" } } */
 /* { dg-final { cleanup-tree-dump "ccp1" } } */
Index: testsuite/g++.dg/ext/vector22.C

===================================================================
--- testsuite/g++.dg/ext/vector22.C	(revision 198950)

+++ testsuite/g++.dg/ext/vector22.C	(working copy)

@@ -1,20 +1,22 @@ 

 /* { dg-do compile } */
 /* { dg-options "-O -fdump-tree-gimple" } */
 
 typedef unsigned vec __attribute__((vector_size(4*sizeof(int))));
 
+/* Disabled after PR57286

 void f(vec*a,vec*b){
   *a=(*a)?-1:(*b<10);
   *b=(*b)?(*a<10):0;
 }
+*/

 void g(vec*a,vec*b){
   *a=(*a)?(*a<*a):-1;
-  *b=(*b)?-1:(*b<*b);

+// *b=(*b)?-1:(*b<*b);

 }
 void h(vec*a){
   *a=(~*a==5);
 }
 
 /* { dg-final { scan-tree-dump-not "~" "gimple" } } */
 /* { dg-final { scan-tree-dump-not "VEC_COND_EXPR" "gimple" } } */
 /* { dg-final { cleanup-tree-dump "gimple" } } */
Index: fold-const.c

===================================================================
--- fold-const.c	(revision 198950)

+++ fold-const.c	(working copy)

@@ -14204,20 +14204,26 @@  fold_ternary_loc (location_t loc, enum t

 	  && TREE_CODE (arg0) == NE_EXPR
 	  && integer_zerop (TREE_OPERAND (arg0, 1))
 	  && integer_pow2p (arg1)
 	  && TREE_CODE (TREE_OPERAND (arg0, 0)) == BIT_AND_EXPR
 	  && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1),
 			      arg1, OEP_ONLY_CONST))
 	return pedantic_non_lvalue_loc (loc,
 				    fold_convert_loc (loc, type,
 						      TREE_OPERAND (arg0, 0)));
 
+      /* Disable the transformations below for vectors, since

+	 fold_binary_op_with_conditional_arg may undo them immediately,

+	 yielding an infinite loop.  */

+      if (code == VEC_COND_EXPR)

+	return NULL_TREE;

+

       /* Convert A ? B : 0 into A && B if A and B are truth values.  */
       if (integer_zerop (op2)
 	  && truth_value_p (TREE_CODE (arg0))
 	  && truth_value_p (TREE_CODE (arg1))
 	  && (code == VEC_COND_EXPR || !VECTOR_TYPE_P (type)))
 	return fold_build2_loc (loc, code == VEC_COND_EXPR ? BIT_AND_EXPR
 							   : TRUTH_ANDIF_EXPR,
 				type, fold_convert_loc (loc, type, arg0), arg1);
 
       /* Convert A ? B : 1 into !A || B if A and B are truth values.  */