[Bug tree-optimization/107881] New: (a <= b) == (b >= a) should be optimized to (a == b)

[Bug tree-optimization/107881] New: (a <= b) == (b >= a) should be optimized to (a == b)

[pinskia at gcc dot gnu.org]

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

            Bug ID: 107881
           Summary: (a <= b) == (b >= a) should be optimized to (a == b)
           Product: gcc
           Version: 13.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: 107880
  Target Milestone: ---

Take:
```
bool f(int a, int b)
{
  bool t = b <= a;
  bool t1 = a <= b;
  return t == t1;
}
```

We should optimize this to just:
```
bool f1(int a, int b)
{
  return a == b;
}
```
LLVM is able to do it.
We can optimize for & and | but not ^ or ==. (note != gets changed into ^)


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107880
[Bug 107880] bool tautology missed optimisation

[Bug tree-optimization/107881] (a <= b) == (b >= a) should be optimized to (a == b)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2022-11-26
     Ever confirmed|0                           |1

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Reassociation is what does it for the `&` case:

Equivalence: t1_4 & t_3 -> b_1(D) == a_2(D)
Transforming _6 = t_3 & t1_4;
 into _6 = _7;

[Bug tree-optimization/107881] (a <= b) == (b >= a) should be optimized to (a == b)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I have a Reassociation patch which handles == and ^ (but not fully, I don't
handle some cases where maybe_fold_or_comparisons/maybe_fold_and_comparisons
return a constant, will handle that seperately).

[Bug tree-optimization/107881] (a <= b) == (b >= a) should be optimized to (a == b)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|pinskia at gcc dot gnu.org         |unassigned at gcc dot gnu.org
             Status|ASSIGNED                    |NEW

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Actually it only handles ^ . I will attach it here. maybe someone can look into
improving it for GCC 14.

[Bug tree-optimization/107881] (a <= b) == (b >= a) should be optimized to (a == b)

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 53970
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53970&action=edit
patch which handles some parts of the xor in tree-ssa-reassoc.cc

This is the patch which I was talking about which is able to handle xor but
someone should take it over for GCC 14.

[Bug tree-optimization/107881] (a <= b) == (b >= a) should be optimized to (a == b)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #53970|0                           |1
        is obsolete|                            |

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 53971
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53971&action=edit
Slightly better xor patch

Here is a slightly better xor one. It moves most of the stuff to gimple-fold.cc
really and is able to handle CSTs now.

[Bug tree-optimization/107881] (a <= b) == (b >= a) should be optimized to (a == b)

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I was thinking about having reassociation changing bool == bool, bool < bool,
and bool <= bool into ~(bool ^ bool), !bool & bool, !bool | bool to
"linearizing" so then reassociation can handle the rest (with the xor patch
still? or we change ^ to how we expand xor like it is done in the patch) and
then when finalizing, we simplify back to ==, <, and <= (and ^).

[Bug tree-optimization/107881] (a <= b) == (b >= a) should be optimized to (a == b)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Mine.

[Bug tree-optimization/107881] (a <= b) == (b >= a) should be optimized to (a == b)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |NEW
           Assignee|pinskia at gcc dot gnu.org         |unassigned at gcc dot gnu.org

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Hmm, the code of reassociation is somewhat hard to follow. So I am not going to
work on this.

[Bug tree-optimization/107881] (a <= b) == (b >= a) should be optimized to (a == b)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |antoshkka at gmail dot com

--- Comment #9 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 108465 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/107881] (a <= b) == (b >= a) should be optimized to (a == b)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

--- Comment #10 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Mine, there was another bug where we had `cmp == b` and I Mentioned the way to
improve that is prefer ^ and `~cmp`.

[Bug tree-optimization/107881] (a <= b) == (b >= a) should be optimized to (a == b)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |DUPLICATE
             Status|ASSIGNED                    |RESOLVED

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Basically a dup of bug 95185.

*** This bug has been marked as a duplicate of bug 95185 ***

[Bug tree-optimization/107881] (a <= b) == (b >= a) should be optimized to (a == b)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |ASSIGNED
         Resolution|DUPLICATE                   |---

--- Comment #12 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Actually reopen since it is not an exact dup.

But still mine.

[Bug tree-optimization/107881] (a <= b) == (b >= a) should be optimized to (a == b)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Depends on|                            |95185

--- Comment #13 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
But this depends on PR 95185 still.


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95185
[Bug 95185] Failure to optimize specific kind of sign comparison check

[Bug tree-optimization/107881] (a <= b) == (b >= a) should be optimized to (a == b)

[pinskia at gcc dot gnu.org]

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

--- Comment #14 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I have a patch which is able to optimize this to:
  t1_3 = b_1(D) >= a_2(D);
  _6 = b_1(D) > a_2(D);
  _4 = t1_3 ^ _6;


But then we need to handle some simplifications for ^.

I will handle that next week or so ...

[Bug tree-optimization/107881] (a <= b) == (b >= a) should be optimized to (a == b)

[pinskia at gcc dot gnu.org]

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

--- Comment #15 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
For the ^/!= case here are the missing optimizations (note == can be handled
too):
```
int ltgtxor(int a, int b)
{
        _Bool c = a < b;
        _Bool d = a > b;
        return c ^ d; // a != b
}

int lteqxor(int a, int b)
{
        _Bool c = a < b;
        _Bool d = a == b;
        return c ^ d; // a <= b (basically | here)
}

int ltnexor(int a, int b)
{
        _Bool c = a < b;
        _Bool d = a != b;
        return c ^ d; // a > b
}
int legexor(int a, int b)
{
        _Bool c = a <= b;
        _Bool d = a >= b;
        return c ^ d; // a != b
}

int leeqxor(int a, int b)
{
        _Bool c = a <= b;
        _Bool d = a == b;
        return c ^ d; // a < b
}

int lenexor(int a, int b)
{
        _Bool c = a <= b;
        _Bool d = a != b;
        return c ^ d; // a >= b
}

```

Match pattern I think:
```
(for op (bit_xor ne)
 (for cmp1 (lt lt lt le le le)
      cmp2 (gt eq ne ge eq ne)
      rcmp (ne le gt ne lt ge)
  (simplify
   (op:c (cmp1:c @0 @1) (cmp2:c @0 @1))
   (rcmp @0 @1))))
```

For eq:
```
(for cmp1 (lt lt lt le le le)
     cmp2 (gt eq ne ge eq ne)
     rcmp (eq ge le eq ge lt)
 (simplify
  (eq:c (cmp1:c @0 @1) (cmp2:c @0 @1))
  (rcmp @0 @1)))
```

Both of these this check though:
(INTEGRAL_TYPE_P (TREE_TYPE (@0)) || POINTER_TYPE_P (TREE_TYPE (@0)))

[Bug tree-optimization/107881] (a <= b) == (b >= a) should be optimized to (a == b)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                URL|                            |https://gcc.gnu.org/piperma
                   |                            |il/gcc-patches/2023-Septemb
                   |                            |er/629951.html

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

[Bug tree-optimization/107881] (a <= b) == (b >= a) should be optimized to (a == b)

[cvs-commit at gcc dot gnu.org]

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

--- 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:895e476f64c308dfdbf49693d0b1166c0b7733de

commit r14-3881-g895e476f64c308dfdbf49693d0b1166c0b7733de
Author: Andrew Pinski <apinski@marvell.com>
Date:   Mon Sep 11 15:35:59 2023 -0700

    MATCH: Simplify (a CMP1 b) ^ (a CMP2 b)

    This adds the missing optimizations here.
    Note we don't need to match where CMP1 and CMP2 are complements of each
    other as that is already handled elsewhere.

    I added a new executable testcase to make sure we optimize it correctly
    as I had originally messed up one of the entries for the resulting
    comparison to make sure they were 100% correct.

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

            PR tree-optimization/107881

    gcc/ChangeLog:

            * match.pd (`(a CMP1 b) ^ (a CMP2 b)`): New pattern.
            (`(a CMP1 b) == (a CMP2 b)`): New pattern.

    gcc/testsuite/ChangeLog:

            * gcc.c-torture/execute/pr107881-1.c: New test.
            * gcc.dg/tree-ssa/cmpeq-4.c: New test.
            * gcc.dg/tree-ssa/cmpxor-1.c: New test.

[Bug tree-optimization/107881] (a <= b) == (b >= a) should be optimized to (a == b)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |14.0
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #18 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Fixed.