[Bug tree-optimization/113138] New: `x < ~x` can be simplified to `((signed)x) < 0`

[Bug tree-optimization/113138] New: `x < ~x` can be simplified to `((signed)x) < 0`

[pinskia at gcc dot gnu.org]

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

            Bug ID: 113138
           Summary: `x < ~x` can be simplified to `((signed)x) < 0`
           Product: gcc
           Version: 14.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
  Target Milestone: ---

Take:
```
#include <stdint.h>
bool srcu(uint32_t x) { return x < ~x; }
bool srcs(int32_t x) { return x < ~x; }
```

But of these can be optimized to:

```
#include <stdint.h>
bool tgt(int32_t x) { return x < 0; }
```

`x >= ~x` can be optimzed to `x >=s 0` (boolean opposites).
While `x > ~x` can be optimized to `(~x) <s 0` or rather `x >s -1` or rather `x
>=s 0`.
While `x <= ~x` can be optimized to `x <s 0`.

So the resulting for loop is:
cmp   lt le gt ge
rcmp  lt lt ge ge

[Bug tree-optimization/113138] `x < ~x` can be simplified to `((signed)x) < 0`

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org
   Last reconfirmed|                            |2023-12-25
             Status|UNCONFIRMED                 |ASSIGNED

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Actually the following list is correct:
signed
X s< ~X   -->     X s< 0
X s<= ~X  -->     X s< ~X  --> X s< 0

X s> ~X   -->     X s> 0
X s>= ~X  -->     X s> ~X  --> X s> 0

unsigned:
X u< ~X   -->                  X u> SIGNBIT_OF(X)
X u<= ~X  -->     X u< ~X  --> X u> SIGNBIT_OF(X)

X u> ~X   -->                  X u< SIGNBIT_OF(X)
X u>= ~X  -->    ~X u> X   --> X u< SIGNBIT_OF(X)

So the correct idea is this:
(for (cmp  lt le gt ge)
     (rcmp gt gt lt lt)
 (simplify
  (cmp @0 @1)
  (with { bool wascmp; }
   (if (bitwise_inverted_equal_p (@0, @1, wascmp)
        && (!wascmp || element_precision (type) == 1))
   (with {
     tree inner_type = TREE_TYPE (@0);
     int precision = TYPE_PRECISION (inner_type);
     // the min value here is in the opposite signedness.
     auto ncst = wi::min_value (precision, TYPE_UNSIGNED (inner_type) ? SIGNED
: UNSIGNED);
    }
    (rcmp @0 { wide_int_to_tree (inner_type, ncst); })
  )
 )
)

[Bug tree-optimization/113138] `x < ~x` can be simplified to `((signed)x) < 0`

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #1)
> Actually the following list is correct:
> signed
> X s< ~X   -->     X s< 0
> X s<= ~X  -->     X s< ~X  --> X s< 0
> 
> X s> ~X   -->     X s> 0
> X s>= ~X  -->     X s> ~X  --> X s> 0
> 
> unsigned:
> X u< ~X   -->                  X u> SIGNBIT_OF(X)
> X u<= ~X  -->     X u< ~X  --> X u> SIGNBIT_OF(X)
> 
> X u> ~X   -->                  X u< SIGNBIT_OF(X)
> X u>= ~X  -->    ~X u> X   --> X u< SIGNBIT_OF(X)
> 
> So the correct idea is this:
> (for (cmp  lt le gt ge)
>      (rcmp gt gt lt lt)
>  (simplify
>   (cmp @0 @1)
>   (with { bool wascmp; }
>    (if (bitwise_inverted_equal_p (@0, @1, wascmp)
>         && (!wascmp || element_precision (type) == 1))
>    (with {
>      tree inner_type = TREE_TYPE (@0);
>      int precision = TYPE_PRECISION (inner_type);
>      // the min value here is in the opposite signedness.
>      auto ncst = wi::min_value (precision, TYPE_UNSIGNED (inner_type) ?
> SIGNED : UNSIGNED);
>     }
>     (rcmp @0 { wide_int_to_tree (inner_type, ncst); })
>   )
>  )
> )

Will something then fold it further if it is actually ~X s< X (because the
above would then fold it into ~X s< 0)?

[Bug tree-optimization/113138] `x < ~x` can be simplified to `((signed)x) < 0`

[pinskia at gcc dot gnu.org]

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #2)
> Will something then fold it further if it is actually ~X s< X (because the
> above would then fold it into ~X s< 0)?

Yes there is already a pattern for that:
/* Fold ~X op C as X op' ~C, where op' is the swapped comparison.  */

Which should handle the `~X u< signbit(X)` one too.