[Bug c++/99772] New: New built-ins for pointer comparisons that yield a total order

[Bug c++/99772] New: New built-ins for pointer comparisons that yield a total order

[redi at gcc dot gnu.org]

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

            Bug ID: 99772
           Summary: New built-ins for pointer comparisons that yield a
                    total order
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: redi at gcc dot gnu.org
            Blocks: 93628
  Target Milestone: ---

[comparisons.general] says:

For templates less, greater, less_equal, and greater_equal, the specializations
for any pointer type yield a result consistent with the implementation-defined
strict total order over pointers (3.27).

We do:

      _GLIBCXX14_CONSTEXPR bool
      operator()(_Tp* __x, _Tp* __y) const _GLIBCXX_NOTHROW
      {
#if __cplusplus >= 201402L
#ifdef _GLIBCXX_HAVE_BUILTIN_IS_CONSTANT_EVALUATED
        if (__builtin_is_constant_evaluated())
#else
        if (__builtin_constant_p(__x < __y))
#endif
          return __x < __y;
#endif
        return (__UINTPTR_TYPE__)__x < (__UINTPTR_TYPE__)__y;
      }

The casts were added for PR libstdc++/78420 because GCC started to optimize
based on unspecified < comparisons. So we can't just use the built-in
comparisons.

Furthermore:

For template specializations less<void>, greater<void>, less_­equal<void>, and
greater_­equal<void>, if the call operator calls a built-in operator comparing
pointers, the call operator yields a result consistent with the
implementation-defined strict total order over pointers.

This one is harder, as we have to jump through several hoops to detect "if the
call operator calls a built-in operator comparing pointers", and if it does,
then use std::less<const volatile void*> to get a total order.

Then [comparisons.three.way] has another "if <=> ... resolve to a built-in
operator comparing pointers" and again requires a total order. And again in
[range.cmp].

Our current approach doesn't work for std::compare_three_way
std::ranges::equal_to with two types that are (or convert to) function pointers
(see PR 93628).

It would be faster to compile and (I assume) more reliable if we could just ask
the compiler to do the comparison and give a total order (so that the
middle-end doesn't optimize as though the result is unspecified).

I don't know exactly what the front-end support would look like. Maybe one
helper to check whether a given expression "resolves to a built-in operator
comparing pointers" and another to do the comparison to get a total order, but
I'm not sure that would solve PR 93628.

Maybe what we want is __builtin_less(x, y) and __builtin_equal_to(x, y) and
__builtin_compare_three_way(x, y) which evaluate x<y, x==y, and x<=>y
respectively, but guarantee a total order. If x<y would use a built-in
operator< then do that, otherwise use whatever overloaded operator< it would
use.

Alternatively, we could have a single built-in which takes the operator token
as the third argument, __builtin_cmp(x, y, <), but I don't know if that would
be easier or harder for the FE.

There is already a request for a new built-in to do <=> for floating-point
types (PR 96526) which could presumably be subsumed by
__builtin_compare_three_way.


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93628
[Bug 93628] ranges::equal_to doesn't work for types convertible to function
pointers

[Bug c++/99772] New built-ins for comparisons that must yield a total order

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
            Version|unknown                     |11.0

[Bug c++/99772] New built-ins for comparisons that must yield a total order

[pinskia at gcc dot gnu.org]

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

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

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

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