Patchwork [tree-optimization] : Fix for PR 45397 part 2 of 2

login
register
mail settings
Submitter Kai Tietz
Date March 15, 2012, 1:09 p.m.
Message ID <CAEwic4Z-312Roq3SUML-CzioZd5hjGdv6cnwM6ibNJiWf5ifww@mail.gmail.com>
Download mbox | patch
Permalink /patch/146949/
State New
Headers show

Comments

Kai Tietz - March 15, 2012, 1:09 p.m.
Hi,

this is the second part of the patch for this problem.  It adds some
basic simplifications for ==/!=
comparisons for eliminating redudant operands.

It adds the following patterns:
  -X ==/!= Z - X -> Z ==/!= 0.
  ~X ==/!= Z ^ X -> Z ==/!= ~0
  X ==/!= X - Y -> Y == 0
  X ==/!= X + Y -> Y == 0
  X ==/!= X ^ Y -> Y == 0
  (X - Y) ==/!= (Z - Y) -> X ==/!= Z
  (Y - X) ==/!= (Y - Z) -> X ==/!= Z
  (X + Y) ==/!= (X + Z) -> Y ==/!= Z
  (X + Y) ==/!= (Z + X) -> Y ==/!= Z
  (X ^ Y) ==/!= (Z ^ X) -> Y ==/!= Z

ChangeLog

2012-03-15  Kai Tietz  <ktietz@redhat.com>

	PR tree-optimization/45397
	* tree-ssa-forwprop.c (compare_equal_optimized_1): Add
	simplification patterns for ==/!= comparison.

2012-03-15  Kai Tietz  <ktietz@redhat.com>

	* gcc.dg/tree-ssa/pr45397-2.c: New test.

Regression tested for all languages (including Ada and Obj-C) on
x86_64-unknown-linux-gnu.  Ok for apply?

Regards,
Kai
Richard Guenther - March 15, 2012, 1:35 p.m.
On Thu, Mar 15, 2012 at 2:09 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> Hi,
>
> this is the second part of the patch for this problem.  It adds some
> basic simplifications for ==/!=
> comparisons for eliminating redudant operands.
>
> It adds the following patterns:
>  -X ==/!= Z - X -> Z ==/!= 0.
>  ~X ==/!= Z ^ X -> Z ==/!= ~0
>  X ==/!= X - Y -> Y == 0
>  X ==/!= X + Y -> Y == 0
>  X ==/!= X ^ Y -> Y == 0
>  (X - Y) ==/!= (Z - Y) -> X ==/!= Z
>  (Y - X) ==/!= (Y - Z) -> X ==/!= Z
>  (X + Y) ==/!= (X + Z) -> Y ==/!= Z
>  (X + Y) ==/!= (Z + X) -> Y ==/!= Z
>  (X ^ Y) ==/!= (Z ^ X) -> Y ==/!= Z

Can you re-base this patch to work without the previous one?  Also
please coordinate with Andrew.  Note that all of these(?) simplifications
are already done by fold_comparison which we could share if you'd split
out the EXPR_P op0/op1 cases with separated operands/code.

Richard.

> ChangeLog
>
> 2012-03-15  Kai Tietz  <ktietz@redhat.com>
>
>        PR tree-optimization/45397
>        * tree-ssa-forwprop.c (compare_equal_optimized_1): Add
>        simplification patterns for ==/!= comparison.
>
> 2012-03-15  Kai Tietz  <ktietz@redhat.com>
>
>        * gcc.dg/tree-ssa/pr45397-2.c: New test.
>
> Regression tested for all languages (including Ada and Obj-C) on
> x86_64-unknown-linux-gnu.  Ok for apply?
>
> Regards,
> Kai
>
> Index: gcc-trunk/gcc/tree-ssa-forwprop.c
> ===================================================================
> --- gcc-trunk.orig/gcc/tree-ssa-forwprop.c
> +++ gcc-trunk/gcc/tree-ssa-forwprop.c
> @@ -381,6 +381,99 @@ compare_equal_optimize_1 (gimple stmt, e
>       || !INTEGRAL_TYPE_P (type_outer))
>     return NULL_TREE;
>
> +  /* Simplify -X ==/!= Z - X -> Z ==/!= 0.  */
> +  if (TREE_CODE (op0) == NEGATE_EXPR
> +      && !TREE_SIDE_EFFECTS (TREE_OPERAND (op0, 0))
> +      && TREE_CODE (op1) == MINUS_EXPR
> +      && TREE_OPERAND (op0, 0) == TREE_OPERAND (op1, 1))
> +       return fold_build2_loc (gimple_location (stmt), code, type,
> +                               TREE_OPERAND (op1, 0),
> +                               build_zero_cst (TREE_TYPE (op1)));
> +
> +  /* Simplify X - Z ==/!= -X -> Z ==/!= 0.  */
> +  if (TREE_CODE (op1) == NEGATE_EXPR
> +      && !TREE_SIDE_EFFECTS (TREE_OPERAND (op1, 0))
> +      && TREE_CODE (op0) == MINUS_EXPR
> +      && TREE_OPERAND (op1, 0) == TREE_OPERAND (op0, 1))
> +       return fold_build2_loc (gimple_location (stmt), code, type,
> +                               TREE_OPERAND (op0, 0),
> +                               build_zero_cst (TREE_TYPE (op0)));
> +
> +  /* Simplify ~X ==/!= X ^ Y to Y ==/!= ~0.  */
> +  if (TREE_CODE (op0) == BIT_NOT_EXPR
> +      && !TREE_SIDE_EFFECTS (TREE_OPERAND (op0, 0))
> +      && TREE_CODE (op1) == BIT_XOR_EXPR)
> +    {
> +      if (TREE_OPERAND (op0, 0) == TREE_OPERAND (op1, 1))
> +       return fold_build2_loc (gimple_location (stmt), code, type,
> +                               TREE_OPERAND (op1, 0),
> +                               fold_build1 (BIT_NOT_EXPR,
> +                                            TREE_TYPE (op1),
> +                                            build_zero_cst (TREE_TYPE (op1))));
> +      if (TREE_OPERAND (op0, 0) == TREE_OPERAND (op1, 0))
> +       return fold_build2_loc (gimple_location (stmt), code, type,
> +                               TREE_OPERAND (op1, 1),
> +                               fold_build1 (BIT_NOT_EXPR,
> +                                            TREE_TYPE (op1),
> +                                            build_zero_cst (TREE_TYPE (op1))));
> +    }
> +
> +  /* Simplify X ^ Y ==/!= ~X to Y ==/!= ~0.  */
> +  if (TREE_CODE (op1) == BIT_NOT_EXPR
> +      && !TREE_SIDE_EFFECTS (TREE_OPERAND (op1, 0))
> +      && TREE_CODE (op0) == BIT_XOR_EXPR)
> +    {
> +      if (TREE_OPERAND (op1, 0) == TREE_OPERAND (op0, 1))
> +       return fold_build2_loc (gimple_location (stmt), code, type,
> +                               TREE_OPERAND (op0, 0),
> +                               fold_build1 (BIT_NOT_EXPR,
> +                                            TREE_TYPE (op0),
> +                                            build_zero_cst (TREE_TYPE (op0))));
> +      if (TREE_OPERAND (op1, 0) == TREE_OPERAND (op0, 0))
> +       return fold_build2_loc (gimple_location (stmt), code, type,
> +                               TREE_OPERAND (op0, 1),
> +                               fold_build1 (BIT_NOT_EXPR,
> +                                            TREE_TYPE (op0),
> +                                            build_zero_cst (TREE_TYPE (op0))));
> +    }
> +
> +  /* For code being +, -, or ^-expression simplify (X code Y) ==/!= (Z code Y)
> +     to (X ==/!= Z), and (X code Y) ==/!= (X code Z) to (Y ==/!= Z).  */
> +  if (TREE_CODE (op0) == TREE_CODE (op1)
> +      && (TREE_CODE (op0) == PLUS_EXPR
> +          || TREE_CODE (op0) == MINUS_EXPR
> +          || TREE_CODE (op0) == BIT_XOR_EXPR))
> +    {
> +      /* Simplify (X code Y) ==/!= (X code Z) to Y ==/!= Z.  */
> +      if (TREE_OPERAND (op0, 0) == TREE_OPERAND (op1, 0)
> +          && !TREE_SIDE_EFFECTS (TREE_OPERAND (op0, 0)))
> +       return fold_build2_loc (gimple_location (stmt), code, type,
> +                               TREE_OPERAND (op0, 1),
> +                               TREE_OPERAND (op1, 1));
> +      /* Simplify (X code Y) ==/!= (Z code X) to Y ==/!= Z, if code isn't
> +        minus operation.  */
> +      if (TREE_CODE (op0) != MINUS_EXPR
> +          && TREE_OPERAND (op0, 0) == TREE_OPERAND (op1, 1)
> +          && !TREE_SIDE_EFFECTS (TREE_OPERAND (op0, 0)))
> +        return fold_build2_loc (gimple_location (stmt), code, type,
> +                               TREE_OPERAND (op0, 1),
> +                               TREE_OPERAND (op1, 0));
> +      /* Simplify (Y code X) ==/!= (X code Z) to Y ==/!= Z, if code isn't
> +        minus operation.  */
> +      if (TREE_CODE (op0) != MINUS_EXPR
> +          && TREE_OPERAND (op0, 1) == TREE_OPERAND (op1, 0)
> +          && !TREE_SIDE_EFFECTS (TREE_OPERAND (op0, 1)))
> +        return fold_build2_loc (gimple_location (stmt), code, type,
> +                               TREE_OPERAND (op0, 0),
> +                               TREE_OPERAND (op1, 1));
> +      /* Simplify (Y code X) ==/!= (Z code X) to Y ==/!= Z.  */
> +      if (TREE_OPERAND (op0, 1) == TREE_OPERAND (op1, 1)
> +          && !TREE_SIDE_EFFECTS (TREE_OPERAND (op0, 1)))
> +        return fold_build2_loc (gimple_location (stmt), code, type,
> +                               TREE_OPERAND (op0, 0),
> +                               TREE_OPERAND (op1, 0));
> +    }
> +
>   /* If OP0 isn't a conversion, then check if OP1 might be one.  If so
>      swap arguments, otherwise return NULL_TREE.  */
>   if (!CONVERT_EXPR_P (op0))
> Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/pr45397-2.c
> ===================================================================
> --- /dev/null
> +++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/pr45397-2.c
> @@ -0,0 +1,15 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +int
> +foo (const unsigned char *a, int b, int c)
> +{
> +  int x = (unsigned char) (a[b] + c);
> +  int y = a[b] + c;
> +  int z = (unsigned char) y;
> +  return x == z;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> +
Kai Tietz - March 15, 2012, 1:46 p.m.
2012/3/15 Richard Guenther <richard.guenther@gmail.com>:
> On Thu, Mar 15, 2012 at 2:09 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>> Hi,
>>
>> this is the second part of the patch for this problem.  It adds some
>> basic simplifications for ==/!=
>> comparisons for eliminating redudant operands.
>>
>> It adds the following patterns:
>>  -X ==/!= Z - X -> Z ==/!= 0.
>>  ~X ==/!= Z ^ X -> Z ==/!= ~0
>>  X ==/!= X - Y -> Y == 0
>>  X ==/!= X + Y -> Y == 0
>>  X ==/!= X ^ Y -> Y == 0
>>  (X - Y) ==/!= (Z - Y) -> X ==/!= Z
>>  (Y - X) ==/!= (Y - Z) -> X ==/!= Z
>>  (X + Y) ==/!= (X + Z) -> Y ==/!= Z
>>  (X + Y) ==/!= (Z + X) -> Y ==/!= Z
>>  (X ^ Y) ==/!= (Z ^ X) -> Y ==/!= Z
>
> Can you re-base this patch to work without the previous one?  Also
> please coordinate with Andrew.  Note that all of these(?) simplifications
> are already done by fold_comparison which we could share if you'd split
> out the EXPR_P op0/op1 cases with separated operands/code.
>
> Richard.

Hmm, fold_comparison doesn't do the same thing as it checks for
possible overflow.  This is true for comparisons not being ==/!= or
having operands of none-integral-type.  But for ==/!= with integral
typed arguments  the overflow doesn't matter at all.  And exactly this
is what patch implements here.
This optimization of course is just desired in non-AST form, as we
otherwise loose information in FE.  Therefore I didn't added it to
fold_const.

I can rework the patch so that it works without the other one.

Regards,
Kai
Richard Guenther - March 15, 2012, 2:16 p.m.
On Thu, Mar 15, 2012 at 2:46 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> 2012/3/15 Richard Guenther <richard.guenther@gmail.com>:
>> On Thu, Mar 15, 2012 at 2:09 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>> Hi,
>>>
>>> this is the second part of the patch for this problem.  It adds some
>>> basic simplifications for ==/!=
>>> comparisons for eliminating redudant operands.
>>>
>>> It adds the following patterns:
>>>  -X ==/!= Z - X -> Z ==/!= 0.
>>>  ~X ==/!= Z ^ X -> Z ==/!= ~0
>>>  X ==/!= X - Y -> Y == 0
>>>  X ==/!= X + Y -> Y == 0
>>>  X ==/!= X ^ Y -> Y == 0
>>>  (X - Y) ==/!= (Z - Y) -> X ==/!= Z
>>>  (Y - X) ==/!= (Y - Z) -> X ==/!= Z
>>>  (X + Y) ==/!= (X + Z) -> Y ==/!= Z
>>>  (X + Y) ==/!= (Z + X) -> Y ==/!= Z
>>>  (X ^ Y) ==/!= (Z ^ X) -> Y ==/!= Z
>>
>> Can you re-base this patch to work without the previous one?  Also
>> please coordinate with Andrew.  Note that all of these(?) simplifications
>> are already done by fold_comparison which we could share if you'd split
>> out the EXPR_P op0/op1 cases with separated operands/code.
>>
>> Richard.
>
> Hmm, fold_comparison doesn't do the same thing as it checks for
> possible overflow.  This is true for comparisons not being ==/!= or
> having operands of none-integral-type.  But for ==/!= with integral
> typed arguments  the overflow doesn't matter at all.  And exactly this
> is what patch implements here.

fold_comparison does not check for overflow for ==/!=.

> This optimization of course is just desired in non-AST form, as we
> otherwise loose information in FE.  Therefore I didn't added it to
> fold_const.

Which pieces are not already in fold-const btw?  forwprop already
re-constructs trees for the defs of the lhs/rhs of a comparison.

Richard.


> I can rework the patch so that it works without the other one.
>
> Regards,
> Kai
Kai Tietz - March 15, 2012, 2:45 p.m.
2012/3/15 Richard Guenther <richard.guenther@gmail.com>:
> On Thu, Mar 15, 2012 at 2:46 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>> 2012/3/15 Richard Guenther <richard.guenther@gmail.com>:
>>> On Thu, Mar 15, 2012 at 2:09 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>>> Hi,
>>>>
>>>> this is the second part of the patch for this problem.  It adds some
>>>> basic simplifications for ==/!=
>>>> comparisons for eliminating redudant operands.
>>>>
>>>> It adds the following patterns:
>>>>  -X ==/!= Z - X -> Z ==/!= 0.
>>>>  ~X ==/!= Z ^ X -> Z ==/!= ~0
>>>>  X ==/!= X - Y -> Y == 0
>>>>  X ==/!= X + Y -> Y == 0
>>>>  X ==/!= X ^ Y -> Y == 0
>>>>  (X - Y) ==/!= (Z - Y) -> X ==/!= Z
>>>>  (Y - X) ==/!= (Y - Z) -> X ==/!= Z
>>>>  (X + Y) ==/!= (X + Z) -> Y ==/!= Z
>>>>  (X + Y) ==/!= (Z + X) -> Y ==/!= Z
>>>>  (X ^ Y) ==/!= (Z ^ X) -> Y ==/!= Z
>>>
>>> Can you re-base this patch to work without the previous one?  Also
>>> please coordinate with Andrew.  Note that all of these(?) simplifications
>>> are already done by fold_comparison which we could share if you'd split
>>> out the EXPR_P op0/op1 cases with separated operands/code.
>>>
>>> Richard.
>>
>> Hmm, fold_comparison doesn't do the same thing as it checks for
>> possible overflow.  This is true for comparisons not being ==/!= or
>> having operands of none-integral-type.  But for ==/!= with integral
>> typed arguments  the overflow doesn't matter at all.  And exactly this
>> is what patch implements here.
>
> fold_comparison does not check for overflow for ==/!=.
>
>> This optimization of course is just desired in non-AST form, as we
>> otherwise loose information in FE.  Therefore I didn't added it to
>> fold_const.
>
> Which pieces are not already in fold-const btw?  forwprop already
> re-constructs trees for the defs of the lhs/rhs of a comparison.
>
> Richard.

I have tried to use here instead a call to fold_build2 instead, and I
had to notice that it didn't optimized a single case (beside the - and
~ case on both sides).

I see in fold const for example in the pattern 'X +- C1 CMP Y +- C2'
to 'X CMP Y +- C2 +- C1' explicit the check for it.

...
/* Transform comparisons of the form X +- C1 CMP Y +- C2 to
   X CMP Y +- C2 +- C1 for signed X, Y.  This is valid if
   the resulting offset is smaller in absolute value than the
   original one.  */
if (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg0))
    && (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
...

The same for pattern X +- C1 CMP C2 to X CMP C2 +- C1.

The cases for '(X + Y) ==/!= (Z + X)' and co have the same issue or
are simply not present.

Sorry fold_const doesn't cover this at all.

Kai
Richard Guenther - March 21, 2012, 9:45 a.m.
On Thu, Mar 15, 2012 at 3:45 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> 2012/3/15 Richard Guenther <richard.guenther@gmail.com>:
>> On Thu, Mar 15, 2012 at 2:46 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>> 2012/3/15 Richard Guenther <richard.guenther@gmail.com>:
>>>> On Thu, Mar 15, 2012 at 2:09 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>>>> Hi,
>>>>>
>>>>> this is the second part of the patch for this problem.  It adds some
>>>>> basic simplifications for ==/!=
>>>>> comparisons for eliminating redudant operands.
>>>>>
>>>>> It adds the following patterns:
>>>>>  -X ==/!= Z - X -> Z ==/!= 0.
>>>>>  ~X ==/!= Z ^ X -> Z ==/!= ~0
>>>>>  X ==/!= X - Y -> Y == 0
>>>>>  X ==/!= X + Y -> Y == 0
>>>>>  X ==/!= X ^ Y -> Y == 0
>>>>>  (X - Y) ==/!= (Z - Y) -> X ==/!= Z
>>>>>  (Y - X) ==/!= (Y - Z) -> X ==/!= Z
>>>>>  (X + Y) ==/!= (X + Z) -> Y ==/!= Z
>>>>>  (X + Y) ==/!= (Z + X) -> Y ==/!= Z
>>>>>  (X ^ Y) ==/!= (Z ^ X) -> Y ==/!= Z
>>>>
>>>> Can you re-base this patch to work without the previous one?  Also
>>>> please coordinate with Andrew.  Note that all of these(?) simplifications
>>>> are already done by fold_comparison which we could share if you'd split
>>>> out the EXPR_P op0/op1 cases with separated operands/code.
>>>>
>>>> Richard.
>>>
>>> Hmm, fold_comparison doesn't do the same thing as it checks for
>>> possible overflow.  This is true for comparisons not being ==/!= or
>>> having operands of none-integral-type.  But for ==/!= with integral
>>> typed arguments  the overflow doesn't matter at all.  And exactly this
>>> is what patch implements here.
>>
>> fold_comparison does not check for overflow for ==/!=.
>>
>>> This optimization of course is just desired in non-AST form, as we
>>> otherwise loose information in FE.  Therefore I didn't added it to
>>> fold_const.
>>
>> Which pieces are not already in fold-const btw?  forwprop already
>> re-constructs trees for the defs of the lhs/rhs of a comparison.
>>
>> Richard.
>
> I have tried to use here instead a call to fold_build2 instead, and I
> had to notice that it didn't optimized a single case (beside the - and
> ~ case on both sides).
>
> I see in fold const for example in the pattern 'X +- C1 CMP Y +- C2'
> to 'X CMP Y +- C2 +- C1' explicit the check for it.
>
> ...
> /* Transform comparisons of the form X +- C1 CMP Y +- C2 to
>   X CMP Y +- C2 +- C1 for signed X, Y.  This is valid if
>   the resulting offset is smaller in absolute value than the
>   original one.  */
> if (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg0))
>    && (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
> ...

Because the transform is not valid if Y +- C2 +- C1 overflows.  It is not valid
because overflow is undefined, not because the comparison would do the
wrong thing.  You'd have to change the addition to unsigned.

> The same for pattern X +- C1 CMP C2 to X CMP C2 +- C1.

Well, this is obviously just a missed optimization in fold-const.c then.  Mind
conditionalizing the overflow check to codes not NE_EXPR or EQ_EXPR?

> The cases for '(X + Y) ==/!= (Z + X)' and co have the same issue or
> are simply not present.

That's true.  I suppose they were considered too special to worry about.
Did you see these cases in real code?

> Sorry fold_const doesn't cover this at all.

It covers part of it.

> Kai
Kai Tietz - March 21, 2012, 9:56 a.m.
2012/3/21 Richard Guenther <richard.guenther@gmail.com>:
> On Thu, Mar 15, 2012 at 3:45 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>> 2012/3/15 Richard Guenther <richard.guenther@gmail.com>:
>>> On Thu, Mar 15, 2012 at 2:46 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>>> 2012/3/15 Richard Guenther <richard.guenther@gmail.com>:
>>>>> On Thu, Mar 15, 2012 at 2:09 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>>>>> Hi,
>>>>>>
>>>>>> this is the second part of the patch for this problem.  It adds some
>>>>>> basic simplifications for ==/!=
>>>>>> comparisons for eliminating redudant operands.
>>>>>>
>>>>>> It adds the following patterns:
>>>>>>  -X ==/!= Z - X -> Z ==/!= 0.
>>>>>>  ~X ==/!= Z ^ X -> Z ==/!= ~0
>>>>>>  X ==/!= X - Y -> Y == 0
>>>>>>  X ==/!= X + Y -> Y == 0
>>>>>>  X ==/!= X ^ Y -> Y == 0
>>>>>>  (X - Y) ==/!= (Z - Y) -> X ==/!= Z
>>>>>>  (Y - X) ==/!= (Y - Z) -> X ==/!= Z
>>>>>>  (X + Y) ==/!= (X + Z) -> Y ==/!= Z
>>>>>>  (X + Y) ==/!= (Z + X) -> Y ==/!= Z
>>>>>>  (X ^ Y) ==/!= (Z ^ X) -> Y ==/!= Z
>>>>>
>>>>> Can you re-base this patch to work without the previous one?  Also
>>>>> please coordinate with Andrew.  Note that all of these(?) simplifications
>>>>> are already done by fold_comparison which we could share if you'd split
>>>>> out the EXPR_P op0/op1 cases with separated operands/code.
>>>>>
>>>>> Richard.
>>>>
>>>> Hmm, fold_comparison doesn't do the same thing as it checks for
>>>> possible overflow.  This is true for comparisons not being ==/!= or
>>>> having operands of none-integral-type.  But for ==/!= with integral
>>>> typed arguments  the overflow doesn't matter at all.  And exactly this
>>>> is what patch implements here.
>>>
>>> fold_comparison does not check for overflow for ==/!=.
>>>
>>>> This optimization of course is just desired in non-AST form, as we
>>>> otherwise loose information in FE.  Therefore I didn't added it to
>>>> fold_const.
>>>
>>> Which pieces are not already in fold-const btw?  forwprop already
>>> re-constructs trees for the defs of the lhs/rhs of a comparison.
>>>
>>> Richard.
>>
>> I have tried to use here instead a call to fold_build2 instead, and I
>> had to notice that it didn't optimized a single case (beside the - and
>> ~ case on both sides).
>>
>> I see in fold const for example in the pattern 'X +- C1 CMP Y +- C2'
>> to 'X CMP Y +- C2 +- C1' explicit the check for it.
>>
>> ...
>> /* Transform comparisons of the form X +- C1 CMP Y +- C2 to
>>   X CMP Y +- C2 +- C1 for signed X, Y.  This is valid if
>>   the resulting offset is smaller in absolute value than the
>>   original one.  */
>> if (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg0))
>>    && (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
>> ...
>
> Because the transform is not valid if Y +- C2 +- C1 overflows.  It is not valid
> because overflow is undefined, not because the comparison would do the
> wrong thing.  You'd have to change the addition to unsigned.
>
>> The same for pattern X +- C1 CMP C2 to X CMP C2 +- C1.
>
> Well, this is obviously just a missed optimization in fold-const.c then.  Mind
> conditionalizing the overflow check to codes not NE_EXPR or EQ_EXPR?
>
>> The cases for '(X + Y) ==/!= (Z + X)' and co have the same issue or
>> are simply not present.
>
> That's true.  I suppose they were considered too special to worry about.
> Did you see these cases in real code?
>
>> Sorry fold_const doesn't cover this at all.
>
> It covers part of it.
>
>> Kai

Sure, the test code shown in this patch isn't that unusual.
Especially in gimple (by using different statements) such construct
are happening.

Eg.:

int f1 (int a, int b, int c)
{
  if ((a + b) == (c + a))
   return 1;
  return 0;
}

int f2 (int a, int b, int c)
{
  if ((a ^ b) == (a  ^ c))
   return 1;
  return 0;
}


int f2 (int a, int b)
{
  if (-a == (b - a))
   return 1;
  return 0;
}

In all those cases the use of variable should be optimized out.
Instead we are producing pretty weak code for those cases.

Kai
Richard Guenther - March 21, 2012, 10:06 a.m.
On Wed, Mar 21, 2012 at 10:56 AM, Kai Tietz <ktietz70@googlemail.com> wrote:
> 2012/3/21 Richard Guenther <richard.guenther@gmail.com>:
>> On Thu, Mar 15, 2012 at 3:45 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>> 2012/3/15 Richard Guenther <richard.guenther@gmail.com>:
>>>> On Thu, Mar 15, 2012 at 2:46 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>>>> 2012/3/15 Richard Guenther <richard.guenther@gmail.com>:
>>>>>> On Thu, Mar 15, 2012 at 2:09 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>>>>>> Hi,
>>>>>>>
>>>>>>> this is the second part of the patch for this problem.  It adds some
>>>>>>> basic simplifications for ==/!=
>>>>>>> comparisons for eliminating redudant operands.
>>>>>>>
>>>>>>> It adds the following patterns:
>>>>>>>  -X ==/!= Z - X -> Z ==/!= 0.
>>>>>>>  ~X ==/!= Z ^ X -> Z ==/!= ~0
>>>>>>>  X ==/!= X - Y -> Y == 0
>>>>>>>  X ==/!= X + Y -> Y == 0
>>>>>>>  X ==/!= X ^ Y -> Y == 0
>>>>>>>  (X - Y) ==/!= (Z - Y) -> X ==/!= Z
>>>>>>>  (Y - X) ==/!= (Y - Z) -> X ==/!= Z
>>>>>>>  (X + Y) ==/!= (X + Z) -> Y ==/!= Z
>>>>>>>  (X + Y) ==/!= (Z + X) -> Y ==/!= Z
>>>>>>>  (X ^ Y) ==/!= (Z ^ X) -> Y ==/!= Z
>>>>>>
>>>>>> Can you re-base this patch to work without the previous one?  Also
>>>>>> please coordinate with Andrew.  Note that all of these(?) simplifications
>>>>>> are already done by fold_comparison which we could share if you'd split
>>>>>> out the EXPR_P op0/op1 cases with separated operands/code.
>>>>>>
>>>>>> Richard.
>>>>>
>>>>> Hmm, fold_comparison doesn't do the same thing as it checks for
>>>>> possible overflow.  This is true for comparisons not being ==/!= or
>>>>> having operands of none-integral-type.  But for ==/!= with integral
>>>>> typed arguments  the overflow doesn't matter at all.  And exactly this
>>>>> is what patch implements here.
>>>>
>>>> fold_comparison does not check for overflow for ==/!=.
>>>>
>>>>> This optimization of course is just desired in non-AST form, as we
>>>>> otherwise loose information in FE.  Therefore I didn't added it to
>>>>> fold_const.
>>>>
>>>> Which pieces are not already in fold-const btw?  forwprop already
>>>> re-constructs trees for the defs of the lhs/rhs of a comparison.
>>>>
>>>> Richard.
>>>
>>> I have tried to use here instead a call to fold_build2 instead, and I
>>> had to notice that it didn't optimized a single case (beside the - and
>>> ~ case on both sides).
>>>
>>> I see in fold const for example in the pattern 'X +- C1 CMP Y +- C2'
>>> to 'X CMP Y +- C2 +- C1' explicit the check for it.
>>>
>>> ...
>>> /* Transform comparisons of the form X +- C1 CMP Y +- C2 to
>>>   X CMP Y +- C2 +- C1 for signed X, Y.  This is valid if
>>>   the resulting offset is smaller in absolute value than the
>>>   original one.  */
>>> if (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg0))
>>>    && (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
>>> ...
>>
>> Because the transform is not valid if Y +- C2 +- C1 overflows.  It is not valid
>> because overflow is undefined, not because the comparison would do the
>> wrong thing.  You'd have to change the addition to unsigned.
>>
>>> The same for pattern X +- C1 CMP C2 to X CMP C2 +- C1.
>>
>> Well, this is obviously just a missed optimization in fold-const.c then.  Mind
>> conditionalizing the overflow check to codes not NE_EXPR or EQ_EXPR?
>>
>>> The cases for '(X + Y) ==/!= (Z + X)' and co have the same issue or
>>> are simply not present.
>>
>> That's true.  I suppose they were considered too special to worry about.
>> Did you see these cases in real code?
>>
>>> Sorry fold_const doesn't cover this at all.
>>
>> It covers part of it.
>>
>>> Kai
>
> Sure, the test code shown in this patch isn't that unusual.
> Especially in gimple (by using different statements) such construct
> are happening.
>
> Eg.:
>
> int f1 (int a, int b, int c)
> {
>  if ((a + b) == (c + a))
>   return 1;
>  return 0;
> }
>
> int f2 (int a, int b, int c)
> {
>  if ((a ^ b) == (a  ^ c))
>   return 1;
>  return 0;
> }
>
>
> int f2 (int a, int b)
> {
>  if (-a == (b - a))
>   return 1;
>  return 0;
> }
>
> In all those cases the use of variable should be optimized out.
> Instead we are producing pretty weak code for those cases.

True, I agree we should try to handle these.  Did you talk to Andrew
with respect to the gimple-combining thing he is working on?

Richard.

> Kai

Patch

Index: gcc-trunk/gcc/tree-ssa-forwprop.c
===================================================================
--- gcc-trunk.orig/gcc/tree-ssa-forwprop.c
+++ gcc-trunk/gcc/tree-ssa-forwprop.c
@@ -381,6 +381,99 @@  compare_equal_optimize_1 (gimple stmt, e
       || !INTEGRAL_TYPE_P (type_outer))
     return NULL_TREE;

+  /* Simplify -X ==/!= Z - X -> Z ==/!= 0.  */
+  if (TREE_CODE (op0) == NEGATE_EXPR
+      && !TREE_SIDE_EFFECTS (TREE_OPERAND (op0, 0))
+      && TREE_CODE (op1) == MINUS_EXPR
+      && TREE_OPERAND (op0, 0) == TREE_OPERAND (op1, 1))
+	return fold_build2_loc (gimple_location (stmt), code, type,
+	       			TREE_OPERAND (op1, 0),
+        			build_zero_cst (TREE_TYPE (op1)));
+
+  /* Simplify X - Z ==/!= -X -> Z ==/!= 0.  */
+  if (TREE_CODE (op1) == NEGATE_EXPR
+      && !TREE_SIDE_EFFECTS (TREE_OPERAND (op1, 0))
+      && TREE_CODE (op0) == MINUS_EXPR
+      && TREE_OPERAND (op1, 0) == TREE_OPERAND (op0, 1))
+	return fold_build2_loc (gimple_location (stmt), code, type,
+	       			TREE_OPERAND (op0, 0),
+        			build_zero_cst (TREE_TYPE (op0)));
+
+  /* Simplify ~X ==/!= X ^ Y to Y ==/!= ~0.  */
+  if (TREE_CODE (op0) == BIT_NOT_EXPR
+      && !TREE_SIDE_EFFECTS (TREE_OPERAND (op0, 0))
+      && TREE_CODE (op1) == BIT_XOR_EXPR)
+    {
+      if (TREE_OPERAND (op0, 0) == TREE_OPERAND (op1, 1))
+	return fold_build2_loc (gimple_location (stmt), code, type,
+	       			TREE_OPERAND (op1, 0),
+        			fold_build1 (BIT_NOT_EXPR,
+					     TREE_TYPE (op1),
+					     build_zero_cst (TREE_TYPE (op1))));
+      if (TREE_OPERAND (op0, 0) == TREE_OPERAND (op1, 0))
+	return fold_build2_loc (gimple_location (stmt), code, type,
+	       			TREE_OPERAND (op1, 1),
+        			fold_build1 (BIT_NOT_EXPR,
+					     TREE_TYPE (op1),
+					     build_zero_cst (TREE_TYPE (op1))));
+    }
+
+  /* Simplify X ^ Y ==/!= ~X to Y ==/!= ~0.  */
+  if (TREE_CODE (op1) == BIT_NOT_EXPR
+      && !TREE_SIDE_EFFECTS (TREE_OPERAND (op1, 0))
+      && TREE_CODE (op0) == BIT_XOR_EXPR)
+    {
+      if (TREE_OPERAND (op1, 0) == TREE_OPERAND (op0, 1))
+	return fold_build2_loc (gimple_location (stmt), code, type,
+	       			TREE_OPERAND (op0, 0),
+        			fold_build1 (BIT_NOT_EXPR,
+					     TREE_TYPE (op0),
+					     build_zero_cst (TREE_TYPE (op0))));
+      if (TREE_OPERAND (op1, 0) == TREE_OPERAND (op0, 0))
+	return fold_build2_loc (gimple_location (stmt), code, type,
+	       			TREE_OPERAND (op0, 1),
+        			fold_build1 (BIT_NOT_EXPR,
+					     TREE_TYPE (op0),
+					     build_zero_cst (TREE_TYPE (op0))));
+    }
+
+  /* For code being +, -, or ^-expression simplify (X code Y) ==/!= (Z code Y)
+     to (X ==/!= Z), and (X code Y) ==/!= (X code Z) to (Y ==/!= Z).  */
+  if (TREE_CODE (op0) == TREE_CODE (op1)
+      && (TREE_CODE (op0) == PLUS_EXPR
+          || TREE_CODE (op0) == MINUS_EXPR
+          || TREE_CODE (op0) == BIT_XOR_EXPR))
+    {
+      /* Simplify (X code Y) ==/!= (X code Z) to Y ==/!= Z.  */
+      if (TREE_OPERAND (op0, 0) == TREE_OPERAND (op1, 0)
+          && !TREE_SIDE_EFFECTS (TREE_OPERAND (op0, 0)))
+	return fold_build2_loc (gimple_location (stmt), code, type,
+	       			TREE_OPERAND (op0, 1),
+        			TREE_OPERAND (op1, 1));
+      /* Simplify (X code Y) ==/!= (Z code X) to Y ==/!= Z, if code isn't
+	 minus operation.  */
+      if (TREE_CODE (op0) != MINUS_EXPR
+          && TREE_OPERAND (op0, 0) == TREE_OPERAND (op1, 1)
+          && !TREE_SIDE_EFFECTS (TREE_OPERAND (op0, 0)))
+        return fold_build2_loc (gimple_location (stmt), code, type,
+        			TREE_OPERAND (op0, 1),
+        			TREE_OPERAND (op1, 0));
+      /* Simplify (Y code X) ==/!= (X code Z) to Y ==/!= Z, if code isn't
+	 minus operation.  */
+      if (TREE_CODE (op0) != MINUS_EXPR
+          && TREE_OPERAND (op0, 1) == TREE_OPERAND (op1, 0)
+          && !TREE_SIDE_EFFECTS (TREE_OPERAND (op0, 1)))
+        return fold_build2_loc (gimple_location (stmt), code, type,
+        			TREE_OPERAND (op0, 0),
+        			TREE_OPERAND (op1, 1));
+      /* Simplify (Y code X) ==/!= (Z code X) to Y ==/!= Z.  */
+      if (TREE_OPERAND (op0, 1) == TREE_OPERAND (op1, 1)
+          && !TREE_SIDE_EFFECTS (TREE_OPERAND (op0, 1)))
+        return fold_build2_loc (gimple_location (stmt), code, type,
+        			TREE_OPERAND (op0, 0),
+        			TREE_OPERAND (op1, 0));
+    }
+
   /* If OP0 isn't a conversion, then check if OP1 might be one.  If so
      swap arguments, otherwise return NULL_TREE.  */
   if (!CONVERT_EXPR_P (op0))
Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/pr45397-2.c
===================================================================
--- /dev/null
+++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/pr45397-2.c
@@ -0,0 +1,15 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+foo (const unsigned char *a, int b, int c)
+{
+  int x = (unsigned char) (a[b] + c);
+  int y = a[b] + c;
+  int z = (unsigned char) y;
+  return x == z;
+}
+
+/* { dg-final { scan-tree-dump-times "return 1" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
+