* [patch tree-optimization]: Fix for PR 45397 part 2 of 2
@ 2012-03-15 13:09 Kai Tietz
2012-03-15 13:36 ` Richard Guenther
0 siblings, 1 reply; 8+ messages in thread
From: Kai Tietz @ 2012-03-15 13:09 UTC (permalink / raw)
To: GCC Patches
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
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" } } */
+
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [patch tree-optimization]: Fix for PR 45397 part 2 of 2
2012-03-15 13:09 [patch tree-optimization]: Fix for PR 45397 part 2 of 2 Kai Tietz
@ 2012-03-15 13:36 ` Richard Guenther
2012-03-15 13:47 ` Kai Tietz
0 siblings, 1 reply; 8+ messages in thread
From: Richard Guenther @ 2012-03-15 13:36 UTC (permalink / raw)
To: Kai Tietz; +Cc: GCC Patches
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" } } */
> +
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [patch tree-optimization]: Fix for PR 45397 part 2 of 2
2012-03-15 13:36 ` Richard Guenther
@ 2012-03-15 13:47 ` Kai Tietz
2012-03-15 14:16 ` Richard Guenther
0 siblings, 1 reply; 8+ messages in thread
From: Kai Tietz @ 2012-03-15 13:47 UTC (permalink / raw)
To: Richard Guenther; +Cc: GCC Patches
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
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [patch tree-optimization]: Fix for PR 45397 part 2 of 2
2012-03-15 13:47 ` Kai Tietz
@ 2012-03-15 14:16 ` Richard Guenther
2012-03-15 14:45 ` Kai Tietz
0 siblings, 1 reply; 8+ messages in thread
From: Richard Guenther @ 2012-03-15 14:16 UTC (permalink / raw)
To: Kai Tietz; +Cc: GCC Patches
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
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [patch tree-optimization]: Fix for PR 45397 part 2 of 2
2012-03-15 14:16 ` Richard Guenther
@ 2012-03-15 14:45 ` Kai Tietz
2012-03-21 9:46 ` Richard Guenther
0 siblings, 1 reply; 8+ messages in thread
From: Kai Tietz @ 2012-03-15 14:45 UTC (permalink / raw)
To: Richard Guenther; +Cc: GCC Patches
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
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [patch tree-optimization]: Fix for PR 45397 part 2 of 2
2012-03-15 14:45 ` Kai Tietz
@ 2012-03-21 9:46 ` Richard Guenther
2012-03-21 9:57 ` Kai Tietz
0 siblings, 1 reply; 8+ messages in thread
From: Richard Guenther @ 2012-03-21 9:46 UTC (permalink / raw)
To: Kai Tietz; +Cc: GCC Patches
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
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [patch tree-optimization]: Fix for PR 45397 part 2 of 2
2012-03-21 9:46 ` Richard Guenther
@ 2012-03-21 9:57 ` Kai Tietz
2012-03-21 10:06 ` Richard Guenther
0 siblings, 1 reply; 8+ messages in thread
From: Kai Tietz @ 2012-03-21 9:57 UTC (permalink / raw)
To: Richard Guenther; +Cc: GCC Patches
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
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [patch tree-optimization]: Fix for PR 45397 part 2 of 2
2012-03-21 9:57 ` Kai Tietz
@ 2012-03-21 10:06 ` Richard Guenther
0 siblings, 0 replies; 8+ messages in thread
From: Richard Guenther @ 2012-03-21 10:06 UTC (permalink / raw)
To: Kai Tietz; +Cc: GCC Patches, Andrew Pinski
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
^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2012-03-21 10:06 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-03-15 13:09 [patch tree-optimization]: Fix for PR 45397 part 2 of 2 Kai Tietz
2012-03-15 13:36 ` Richard Guenther
2012-03-15 13:47 ` Kai Tietz
2012-03-15 14:16 ` Richard Guenther
2012-03-15 14:45 ` Kai Tietz
2012-03-21 9:46 ` Richard Guenther
2012-03-21 9:57 ` Kai Tietz
2012-03-21 10:06 ` Richard Guenther
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).