[Bug tree-optimization/106164] New: (a > b) & (a >= b) does not get optimized until reassoc1

[Bug tree-optimization/106164] New: (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

            Bug ID: 106164
           Summary: (a > b) & (a >= b) does not get optimized until
                    reassoc1
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: pinskia at gcc dot gnu.org
            Blocks: 105903
  Target Milestone: ---

Take:
```
_Bool f(int a, int b)
{
  _Bool c = a > b;
  _Bool d = a >= b;
  return c & d;
}
```
This does not get optimized until reassoc1.
While:
```
_Bool f(int a, int b)
{
  return (a > b) & (a >= b);
}
```
Gets optimized during folding (not by match though), I have not looked into
what does it though.

I noticed this while working on PR 105903 as there is not a reassoc pass after
phiopt4 so nothing optimizes.


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105903
[Bug 105903] Missed optimization for __synth3way

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
This is done by fold_range_test in fold-const.cc ....

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2022-07-02
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #1)
> This is done by fold_range_test in fold-const.cc ....

Actually no, it is fold_truth_andor_1. Anyways I am going to fix this one.

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #2)
> (In reply to Andrew Pinski from comment #1)
> > This is done by fold_range_test in fold-const.cc ....
> 
> Actually no, it is fold_truth_andor_1. Anyways I am going to fix this one.

That is combine_comparisons.

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
This is the match.pd code:
(for bitop (bit_and bit_ior)
 (for cmp (tcc_comparison)
  (for ocmp (tcc_comparison)
   (for ncmp (tcc_comparison)
    (simplify
     (bitop (cmp:c @0 @1) (ocmp @0 @1))
     (with {
#if GIMPLE
        location_t loc = UNKNOWN_LOCATION;
#endif
        tree t = combine_comparisons (loc,
                                      bitop == BIT_IOR_EXPR
                                       ? TRUTH_ORIF_EXPR : TRUTH_ANDIF_EXPR,
                                      cmp, ocmp,
                                      type, @0, @1);
      }
      (switch
       (if (GENERIC && t)
        {t;})
       (if (t && CONSTANT_CLASS_P (t))
        {t;})
       (if (t && TREE_CODE (t) == ncmp
            /* Even though combine_comparisons should
               return this, this is to double check. */
            && operand_equal_p (TREE_OPERAND (t, 0), @0)
            && operand_equal_p (TREE_OPERAND (t, 1), @1))
        (ncmp @0 @1)
       )
      )
     )
    )
   )
  )
 )
)

I am not a fan of it though, I think we should change combine_comparisons to
return the comparison code or true/false or error out.
The loc is due to combine_comparisons building the tree rather than match. The
same is true of the whole checking of the result. I am going to test this fully
and see if there is anything I need to change (there might be some testcases
which need to be "improved").

Also the whole ncmp for loop is still another issue which is a genmatch change
to allow a non-name to be there but that is so so much harder to fix and there
is already a case like that too.

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #4)
> This is the match.pd code:
> (for bitop (bit_and bit_ior)
>  (for cmp (tcc_comparison)
>   (for ocmp (tcc_comparison)
>    (for ncmp (tcc_comparison)
>     (simplify
>      (bitop (cmp:c @0 @1) (ocmp @0 @1))
>      (with {
> #if GIMPLE
> 	location_t loc = UNKNOWN_LOCATION;
> #endif
>         tree t = combine_comparisons (loc,
> 				      bitop == BIT_IOR_EXPR
> 				       ? TRUTH_ORIF_EXPR : TRUTH_ANDIF_EXPR,
> 				      cmp, ocmp,
> 				      type, @0, @1);
>       }
>       (switch
>        (if (GENERIC && t)
> 	{t;})
>        (if (t && CONSTANT_CLASS_P (t))
> 	{t;})
>        (if (t && TREE_CODE (t) == ncmp
> 	    /* Even though combine_comparisons should
> 	       return this, this is to double check. */
> 	    && operand_equal_p (TREE_OPERAND (t, 0), @0)
> 	    && operand_equal_p (TREE_OPERAND (t, 1), @1))
> 	(ncmp @0 @1)
>        )
>       )
>      )
>     )
>    )
>   )
>  )
> )
> 
> I am not a fan of it though, I think we should change combine_comparisons to
> return the comparison code or true/false or error out.
> The loc is due to combine_comparisons building the tree rather than match.
> The same is true of the whole checking of the result. I am going to test
> this fully and see if there is anything I need to change (there might be
> some testcases which need to be "improved").
> 
> Also the whole ncmp for loop is still another issue which is a genmatch
> change to allow a non-name to be there but that is so so much harder to fix
> and there is already a case like that too.

Yeah, allowing a "computed" code would be nice to support.  It shouldn't
be _too_ difficult.  Do another overload of id_base, like user_id, call it
sth like runtime_id - allow it only in replacement context and simply
replace with it's variable ID.  The only issue is that genmatch can do
almost no sanity checking on such cases, it would just need to be a
code_helper typed variable.

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I think I have a better patch.

There are patterns for:
Convert (X OP1 CST1) || (X OP2 CST2).

externding them easily to support:
Convert (X OP1 Y) || (X OP2 Y).
is a few lines.
Don't even need to call combine_comparisons either.

Once I test it I will submit the patch.

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 55657
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55657&action=edit
Patch which just needs some testcases

This simple patch implements what I Mentioned about extending those other
patterns.

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #7)
> Created attachment 55657 [details]
> Patch which just needs some testcases
> 
> This simple patch implements what I Mentioned about extending those other
> patterns.

Note this does implement all of what combine_comparisons implements but
implements most of them.
It could easily extend for some more.
Like `x_2 >= y_3 && x_2 != y_3` could be added to convert to `x_2 > y_3`. I
will do that in a different patch.

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #9 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 55658
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55658&action=edit
Secondary patch to add the thing I mentioned

Note this does not handle the constant case since we change `a >= 2` into `a >
1`.
For an example:
```
int f(int a, int b)
{
  b =2;
  int c = a != b;
  int d = a >= b;
  return c & d;
}
```
But we do handle now more ...

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #10 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Patches submitted with testcase:
https://gcc.gnu.org/pipermail/gcc-patches/2023-July/625808.html
https://gcc.gnu.org/pipermail/gcc-patches/2023-July/625807.html

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[rguenther at suse dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #11 from rguenther at suse dot de <rguenther at suse dot de> ---
On Sat, 29 Jul 2023, pinskia at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164
> 
> --- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
> I think I have a better patch.
> 
> There are patterns for:
> Convert (X OP1 CST1) || (X OP2 CST2).
> 
> externding them easily to support:
> Convert (X OP1 Y) || (X OP2 Y).
> is a few lines.
> Don't even need to call combine_comparisons either.
> 
> Once I test it I will submit the patch.

Note moving the non-BIT_FIELD_REF parts of fold_truth_andor_1 to
match.pd was still on the list of things to do.

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #12 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Andrew Pinski <pinskia@gcc.gnu.org>:

https://gcc.gnu.org/g:0258b73680e21fd96290af961c80966ac6b3cc68

commit r14-2886-g0258b73680e21fd96290af961c80966ac6b3cc68
Author: Andrew Pinski <apinski@marvell.com>
Date:   Sat Jul 29 16:59:10 2023 -0700

    MATCH: PR 106164 : Optimize `(X CMP1 Y) AND/IOR (X CMP2 Y)`

    I noticed that there are patterns that optimize
    `(X CMP1 CST1) AND/IOR (X CMP2 CST2)` and we can easily extend
    them to support the  `(X CMP1 Y) AND/IOR (X CMP2 Y)` by saying they
    compare equal. This allows for this kind of optimization for integral
    and pointer types (which have the same semantics).

    OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.

    gcc/ChangeLog:

            PR tree-optimization/106164
            * match.pd: Extend the `(X CMP1 CST1) AND/IOR (X CMP2 CST2)`
            patterns to support `(X CMP1 Y) AND/IOR (X CMP2 Y)`.

    gcc/testsuite/ChangeLog:

            PR tree-optimization/106164
            * gcc.dg/tree-ssa/cmpbit-1.c: New test.

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #13 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Andrew Pinski <pinskia@gcc.gnu.org>:

https://gcc.gnu.org/g:ac0e0966ebf08c454d53042a649403e2880ccbc1

commit r14-2887-gac0e0966ebf08c454d53042a649403e2880ccbc1
Author: Andrew Pinski <apinski@marvell.com>
Date:   Sat Jul 29 21:52:31 2023 -0700

    MATCH: Add `a == b | a cmp b` and `a != b & a cmp b` simplifications

    Even though these are done by combine_comparisons, we can add them to match
    to allow simplifcations during match rather than just during
reassoc/ifcombine.

    OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.

    gcc/ChangeLog:

            PR tree-optimization/106164
            * match.pd (`a != b & a <= b`, `a != b & a >= b`,
            `a == b | a < b`, `a == b | a > b`): Handle these cases
            too.

    gcc/testsuite/ChangeLog:

            PR tree-optimization/106164
            * gcc.dg/tree-ssa/cmpbit-2.c: New test.

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #14 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 55894
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55894&action=edit
Third patch to support the constants that are off by one

This patch adds what I mentioned was missing in comment #9.

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #15 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 55895
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55895&action=edit
testcases for the constants off by one

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #16 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Next patch:
https://gcc.gnu.org/pipermail/gcc-patches/2023-September/630241.html

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #17 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Andrew Pinski <pinskia@gcc.gnu.org>:

https://gcc.gnu.org/g:5e4a248b03f01f422b0dbc9e1464eb6c2f2bafc6

commit r14-3995-g5e4a248b03f01f422b0dbc9e1464eb6c2f2bafc6
Author: Andrew Pinski <apinski@marvell.com>
Date:   Wed Sep 13 16:50:33 2023 -0700

    MATCH: Support `(a != (CST+1)) & (a > CST)` optimizations

    Even though this is done via reassocation, match can support
    these with a simple change to detect that the difference is just
    one. This allows to optimize these earlier and even during phiopt
    for an example.

    This patch adds the following cases:
    (a != (CST+1)) & (a > CST) -> a > (CST+1)
    (a != (CST-1)) & (a < CST) -> a < (CST-1)
    (a == (CST-1)) | (a >= CST) -> a >= (CST-1)
    (a == (CST+1)) | (a <= CST) -> a <= (CST+1)

    Canonicalizations of comparisons causes this case to show up more.

    OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.

            PR tree-optimization/106164

    gcc/ChangeLog:

            * match.pd (`(X CMP1 CST1) AND/IOR (X CMP2 CST2)`):
            Expand to support constants that are off by one.

    gcc/testsuite/ChangeLog:

            * gcc.dg/pr21643.c: Update test now that match does
            the combing of the comparisons.
            * gcc.dg/tree-ssa/cmpbit-5.c: New test.
            * gcc.dg/tree-ssa/phi-opt-35.c: New test.

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #18 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I think the only thing left is supporting floating point.

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=111456

--- Comment #19 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Another integer testcase which is missed here:
```
_Bool f(int a)
{
        _Bool t = a == 0;
        unsigned t1 = a;
        _Bool t2 = t1 >= 3;
        return t & t2;
}
```

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #20 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #19)
> Another integer testcase which is missed here:
> ```
> _Bool f(int a)
> {
>         _Bool t = a == 0;
>         unsigned t1 = a;
>         _Bool t2 = t1 >= 3;
>         return t & t2;
> }
> ```

See PR 111456 for the patch for that.

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #21 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #18)
> I think the only thing left is supporting floating point.

Another testcase for integer but with a nop_conversion:
```
int f(int a)
{
        unsigned b = a;
        int t = (b >= 3);
        return t | (a == 0);
}
```

Without the nop_conversion, the pattern:
/* y == XXX_MIN || x < y --> x <= y - 1 */
(simplify
 (bit_ior:c (eq:s @1 min_value) (lt:cs @0 @1))
  (if (INTEGRAL_TYPE_P (TREE_TYPE (@1))
       && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@1)))
  (le @0 (minus @1 { build_int_cst (TREE_TYPE (@1), 1); }))))

Hits.

I will look into supporting the case where there is a nop_conversion for the @0
in the lt ...

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

--- Comment #22 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Andrew Pinski <pinskia@gcc.gnu.org>:

https://gcc.gnu.org/g:c3c6f30496d945b77dcb7f4ad8c3f8094f5a64a4

commit r14-4280-gc3c6f30496d945b77dcb7f4ad8c3f8094f5a64a4
Author: Andrew Pinski <apinski@marvell.com>
Date:   Wed Sep 20 14:54:31 2023 -0700

    MATCH: Simplify `(A ==/!= B) &/| (((cast)A) CMP C)`

    This patch adds support to the pattern for `(A == B) &/| (A CMP C)`
    where the second A could be casted to a different type.
    Some were handled correctly if using seperate `if` statements
    but not if combined with BIT_AND/BIT_IOR.
    In the case of pr111456-1.c, the testcase would pass if
    `--param=logical-op-non-short-circuit=0` was used but now
    can be optimized always.

    OK? Bootstrapped and tested on x86_64-linux-gnu.

            PR tree-optimization/106164
            PR tree-optimization/111456

    gcc/ChangeLog:

            * match.pd (`(A ==/!= B) & (A CMP C)`):
            Support an optional cast on the second A.
            (`(A ==/!= B) | (A CMP C)`): Likewise.

    gcc/testsuite/ChangeLog:

            * gcc.dg/tree-ssa/cmpbit-6.c: New test.
            * gcc.dg/tree-ssa/cmpbit-7.c: New test.
            * gcc.dg/tree-ssa/pr111456-1.c: New test.

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://github.com/llvm/llv
                   |                            |m-project/issues/63751

--- Comment #23 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Another one:
```
int foo(int a)
{
  int t = (a >= -1);
  return t & (a < 0);
}
```

This is `a == -1`

I noticed this from
https://github.com/llvm/llvm-project/issues/63751

[Bug tree-optimization/106164] (a > b) & (a >= b) does not get optimized until reassoc1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106164

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Depends on|                            |112356

--- Comment #24 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
PR 112356 is for the min/max_value issue.


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112356
[Bug 112356] `x == MIN & x > y` is not optimized to 0 if x was casted to signed
from unsigned