| Message ID | CAEwic4Z-312Roq3SUML-CzioZd5hjGdv6cnwM6ibNJiWf5ifww@mail.gmail.com |
|---|---|
| State | New |
| Headers | show |
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" } } */ > +
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
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
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
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
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
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
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" } } */ +