Patchwork [tree-optimization] : Normalize compares X ==/!= 1 -> X !=/== 0 for truth valued X

login
register
mail settings
Submitter Kai Tietz
Date July 13, 2011, 9 a.m.
Message ID <CAEwic4aF5OAimG8C2o+KBEpDuzea2T3_fjg8aYm63Aw8Tj7ggw@mail.gmail.com>
Download mbox | patch
Permalink /patch/104494/
State New
Headers show

Comments

Kai Tietz - July 13, 2011, 9 a.m.
Hello,

this patch fixes that for replaced uses, we call fold_stmt_inplace. Additionally
it adds to fold_gimple_assign the canonical form for X !=/== 1 -> X ==/!= 0 for
X with one-bit precision type.

ChangeLog gcc/

2011-07-13  Kai Tietz  <ktietz@redhat.com>

	* gimple-fold.c (fold_gimple_assign): Add normalization
	for compares of 1-bit integer precision operands.
	* tree-ssa-propagate.c (replace_uses_in): Call
	fold_stmt_inplace on modified statement.

ChangeLog gcc/testsuite

2011-07-13  Kai Tietz  <ktietz@redhat.com>

	* gcc.dg/tree-ssa/fold-1.c: New test.

Bootstrapped and regression tested for x86_64-pc-linux-gnu.  Ok for apply?

Regards,
Kai
Richard Guenther - July 13, 2011, 10:43 a.m.
On Wed, Jul 13, 2011 at 11:00 AM, Kai Tietz <ktietz70@googlemail.com> wrote:
> Hello,
>
> this patch fixes that for replaced uses, we call fold_stmt_inplace. Additionally
> it adds to fold_gimple_assign the canonical form for X !=/== 1 -> X ==/!= 0 for
> X with one-bit precision type.
>
> ChangeLog gcc/
>
> 2011-07-13  Kai Tietz  <ktietz@redhat.com>
>
>        * gimple-fold.c (fold_gimple_assign): Add normalization
>        for compares of 1-bit integer precision operands.
>        * tree-ssa-propagate.c (replace_uses_in): Call
>        fold_stmt_inplace on modified statement.

err - sure not.  The caller already does that.

Breakpoint 5, substitute_and_fold (get_value_fn=0xc269ae <get_value>,
    fold_fn=0, do_dce=1 '\001')
    at /space/rguenther/src/svn/trunk/gcc/tree-ssa-propagate.c:1134
1134              if (get_value_fn)
D.2696_8 = a_1(D) != D.2704_10;

(gdb) n
1135                did_replace |= replace_uses_in (stmt, get_value_fn);
(gdb)
1138              if (did_replace)
(gdb) call debug_gimple_stmt (stmt)
D.2696_8 = a_1(D) != 1;

(gdb) p did_replace
$1 = 1 '\001'
(gdb) n
1139                fold_stmt (&oldi);

so figure out why fold_stmt does not do its work instead.  Which I
quickly checked in gdb and it dispatches to fold_binary with
boolean-typed arguments as a_1 != 1 where you can see the
canonical form for this is !(int) a_1 because of a bug I think.

      /* bool_var != 1 becomes !bool_var. */
      if (TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE && integer_onep (arg1)
          && code == NE_EXPR)
        return fold_build1_loc (loc, TRUTH_NOT_EXPR, type,
                            fold_convert_loc (loc, type, arg0));

at least I don't see why we need to convert arg0 to the type of the
comparison.

You need to improve your debugging skills and see why existing
transformations are not working before adding new ones.

Richard.

> ChangeLog gcc/testsuite
>
> 2011-07-13  Kai Tietz  <ktietz@redhat.com>
>
>        * gcc.dg/tree-ssa/fold-1.c: New test.
>
> Bootstrapped and regression tested for x86_64-pc-linux-gnu.  Ok for apply?
>
> Regards,
> Kai
>
> Index: gcc/gcc/gimple-fold.c
> ===================================================================
> --- gcc.orig/gcc/gimple-fold.c  2011-07-13 10:37:32.000000000 +0200
> +++ gcc/gcc/gimple-fold.c       2011-07-13 10:39:05.100843400 +0200
> @@ -815,6 +815,17 @@ fold_gimple_assign (gimple_stmt_iterator
>                                             gimple_assign_rhs2 (stmt));
>        }
>
> +      if (!result && (subcode == EQ_EXPR || subcode == NE_EXPR)
> +         && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))
> +         && TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt))) == 1
> +         && integer_onep (gimple_assign_rhs2 (stmt)))
> +       result = build2_loc (loc, (subcode == EQ_EXPR ? NE_EXPR : EQ_EXPR),
> +                            TREE_TYPE (gimple_assign_lhs (stmt)),
> +                            gimple_assign_rhs1 (stmt),
> +                            fold_convert_loc (loc,
> +                               TREE_TYPE (gimple_assign_rhs1 (stmt)),
> +                               integer_zero_node));
> +
>       if (!result)
>         result = fold_binary_loc (loc, subcode,
>                               TREE_TYPE (gimple_assign_lhs (stmt)),
> Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/fold-1.c
> ===================================================================
> --- /dev/null   1970-01-01 00:00:00.000000000 +0000
> +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/fold-1.c  2011-07-13
> 10:50:38.294367800 +0200
> @@ -0,0 +1,9 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +int foo (_Bool a, _Bool b)
> +{
> +  return a != ((b | !b));
> +}
> +/* { dg-final { scan-tree-dump-not " != 1" "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> Index: gcc/gcc/tree-ssa-propagate.c
> ===================================================================
> --- gcc.orig/gcc/tree-ssa-propagate.c   2011-07-13 10:37:42.000000000 +0200
> +++ gcc/gcc/tree-ssa-propagate.c        2011-07-13 10:40:25.688576800 +0200
> @@ -904,6 +904,8 @@ replace_uses_in (gimple stmt, ssa_prop_g
>
>       propagate_value (use, val);
>
> +      fold_stmt_inplace (stmt);
> +
>       replaced = true;
>     }
>
Kai Tietz - July 13, 2011, 10:56 a.m.
2011/7/13 Richard Guenther <richard.guenther@gmail.com>:
> On Wed, Jul 13, 2011 at 11:00 AM, Kai Tietz <ktietz70@googlemail.com> wrote:
>> Hello,
>>
>> this patch fixes that for replaced uses, we call fold_stmt_inplace. Additionally
>> it adds to fold_gimple_assign the canonical form for X !=/== 1 -> X ==/!= 0 for
>> X with one-bit precision type.
>>
>> ChangeLog gcc/
>>
>> 2011-07-13  Kai Tietz  <ktietz@redhat.com>
>>
>>        * gimple-fold.c (fold_gimple_assign): Add normalization
>>        for compares of 1-bit integer precision operands.
>>        * tree-ssa-propagate.c (replace_uses_in): Call
>>        fold_stmt_inplace on modified statement.
>
> err - sure not.  The caller already does that.
>
> Breakpoint 5, substitute_and_fold (get_value_fn=0xc269ae <get_value>,
>    fold_fn=0, do_dce=1 '\001')
>    at /space/rguenther/src/svn/trunk/gcc/tree-ssa-propagate.c:1134
> 1134              if (get_value_fn)
> D.2696_8 = a_1(D) != D.2704_10;
>
> (gdb) n
> 1135                did_replace |= replace_uses_in (stmt, get_value_fn);
> (gdb)
> 1138              if (did_replace)
> (gdb) call debug_gimple_stmt (stmt)
> D.2696_8 = a_1(D) != 1;
>
> (gdb) p did_replace
> $1 = 1 '\001'
> (gdb) n
> 1139                fold_stmt (&oldi);
>
> so figure out why fold_stmt does not do its work instead.  Which I
> quickly checked in gdb and it dispatches to fold_binary with
> boolean-typed arguments as a_1 != 1 where you can see the
> canonical form for this is !(int) a_1 because of a bug I think.
>
>      /* bool_var != 1 becomes !bool_var. */
>      if (TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE && integer_onep (arg1)
>          && code == NE_EXPR)
>        return fold_build1_loc (loc, TRUTH_NOT_EXPR, type,
>                            fold_convert_loc (loc, type, arg0));
>
> at least I don't see why we need to convert arg0 to the type of the
> comparison.

Well, this type-cast is required by C specification - integer
autopromotion - AFAIR.  So I don't think FE maintainer would be happy
about this change.
Nevertheless I saw this pattern before, and was wondering why we check
here for boolean_type at all. This might be in Ada-case even a latent
bug due type-precision, and it prevents signed case detection too.
IMHO this check should look like that:

      /* bool_var != 1 becomes !bool_var. */
      if (INTEGRAL_TYPE_P (TREE_TYPE (arg0))
         && TYPE_PRECISION (TREE_TYPE (arg0)) == 1
         && integer_onep (arg1) && code == NE_EXPR)
        return fold_build1_loc (loc, TRUTH_NOT_EXPR, type,
                            fold_convert_loc (loc, type, arg0));

For thie BIT_NOT_EXPR variant, the cast of arg0 would be of course
false, as ~(bool) is of course different in result then ~(int)

> You need to improve your debugging skills and see why existing
> transformations are not working before adding new ones.

I work on that.

Kai
Richard Guenther - July 13, 2011, 11:06 a.m.
On Wed, Jul 13, 2011 at 12:56 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> 2011/7/13 Richard Guenther <richard.guenther@gmail.com>:
>> On Wed, Jul 13, 2011 at 11:00 AM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>> Hello,
>>>
>>> this patch fixes that for replaced uses, we call fold_stmt_inplace. Additionally
>>> it adds to fold_gimple_assign the canonical form for X !=/== 1 -> X ==/!= 0 for
>>> X with one-bit precision type.
>>>
>>> ChangeLog gcc/
>>>
>>> 2011-07-13  Kai Tietz  <ktietz@redhat.com>
>>>
>>>        * gimple-fold.c (fold_gimple_assign): Add normalization
>>>        for compares of 1-bit integer precision operands.
>>>        * tree-ssa-propagate.c (replace_uses_in): Call
>>>        fold_stmt_inplace on modified statement.
>>
>> err - sure not.  The caller already does that.
>>
>> Breakpoint 5, substitute_and_fold (get_value_fn=0xc269ae <get_value>,
>>    fold_fn=0, do_dce=1 '\001')
>>    at /space/rguenther/src/svn/trunk/gcc/tree-ssa-propagate.c:1134
>> 1134              if (get_value_fn)
>> D.2696_8 = a_1(D) != D.2704_10;
>>
>> (gdb) n
>> 1135                did_replace |= replace_uses_in (stmt, get_value_fn);
>> (gdb)
>> 1138              if (did_replace)
>> (gdb) call debug_gimple_stmt (stmt)
>> D.2696_8 = a_1(D) != 1;
>>
>> (gdb) p did_replace
>> $1 = 1 '\001'
>> (gdb) n
>> 1139                fold_stmt (&oldi);
>>
>> so figure out why fold_stmt does not do its work instead.  Which I
>> quickly checked in gdb and it dispatches to fold_binary with
>> boolean-typed arguments as a_1 != 1 where you can see the
>> canonical form for this is !(int) a_1 because of a bug I think.
>>
>>      /* bool_var != 1 becomes !bool_var. */
>>      if (TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE && integer_onep (arg1)
>>          && code == NE_EXPR)
>>        return fold_build1_loc (loc, TRUTH_NOT_EXPR, type,
>>                            fold_convert_loc (loc, type, arg0));
>>
>> at least I don't see why we need to convert arg0 to the type of the
>> comparison.
>
> Well, this type-cast is required by C specification - integer
> autopromotion - AFAIR.  So I don't think FE maintainer would be happy
> about this change.

?  fold-const.c isn't supposed to perform integer promotion.  It's input
will have integer promotions if the frontend requires them.  If they are
semantically not needed fold-const.c strips them away anyway.

> Nevertheless I saw this pattern before, and was wondering why we check
> here for boolean_type at all. This might be in Ada-case even a latent
> bug due type-precision, and it prevents signed case detection too.
> IMHO this check should look like that:
>
>      /* bool_var != 1 becomes !bool_var. */
>      if (INTEGRAL_TYPE_P (TREE_TYPE (arg0))
>         && TYPE_PRECISION (TREE_TYPE (arg0)) == 1
>         && integer_onep (arg1) && code == NE_EXPR)
>        return fold_build1_loc (loc, TRUTH_NOT_EXPR, type,
>                            fold_convert_loc (loc, type, arg0));

No it should not.  The BOOLEAN_TYPE check is exactly correct.

> For thie BIT_NOT_EXPR variant, the cast of arg0 would be of course
> false, as ~(bool) is of course different in result then ~(int)
>
>> You need to improve your debugging skills and see why existing
>> transformations are not working before adding new ones.
>
> I work on that.
>
> Kai
>

Patch

Index: gcc/gcc/gimple-fold.c
===================================================================
--- gcc.orig/gcc/gimple-fold.c	2011-07-13 10:37:32.000000000 +0200
+++ gcc/gcc/gimple-fold.c	2011-07-13 10:39:05.100843400 +0200
@@ -815,6 +815,17 @@  fold_gimple_assign (gimple_stmt_iterator
 					     gimple_assign_rhs2 (stmt));
 	}

+      if (!result && (subcode == EQ_EXPR || subcode == NE_EXPR)
+	  && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))
+	  && TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt))) == 1
+	  && integer_onep (gimple_assign_rhs2 (stmt)))
+	result = build2_loc (loc, (subcode == EQ_EXPR ? NE_EXPR : EQ_EXPR),
+			     TREE_TYPE (gimple_assign_lhs (stmt)),
+			     gimple_assign_rhs1 (stmt),
+			     fold_convert_loc (loc,
+				TREE_TYPE (gimple_assign_rhs1 (stmt)),
+				integer_zero_node));
+			
       if (!result)
         result = fold_binary_loc (loc, subcode,
                               TREE_TYPE (gimple_assign_lhs (stmt)),
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/fold-1.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/fold-1.c	2011-07-13
10:50:38.294367800 +0200
@@ -0,0 +1,9 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int foo (_Bool a, _Bool b)
+{
+  return a != ((b | !b));
+}
+/* { dg-final { scan-tree-dump-not " != 1" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/gcc/tree-ssa-propagate.c
===================================================================
--- gcc.orig/gcc/tree-ssa-propagate.c	2011-07-13 10:37:42.000000000 +0200
+++ gcc/gcc/tree-ssa-propagate.c	2011-07-13 10:40:25.688576800 +0200
@@ -904,6 +904,8 @@  replace_uses_in (gimple stmt, ssa_prop_g

       propagate_value (use, val);

+      fold_stmt_inplace (stmt);
+
       replaced = true;
     }