This is probably effect on changing !lt(a,b) && !lt(b, a) into !(a<b) && !(b<a) and then a == b. Then following comparision is unspecified according to 5.10 [expr.eq] p2.1:
If at least one of the operands is a pointer, pointer conversions (4.11), function pointer conversions (4.13), and qualification conversions (4.5) are performed on both operands to bring them to their composite pointer
type (Clause 5). Comparing pointers is defined as follows:
— (2.1) If one pointer represents the address of a complete object, and another pointer represents the address one past the last element of a different complete object, the result of the comparison is unspecified.

However I believe that in light of 20.14.6 [comparisons] p14, above transformation is not allowed.

(In reply to Tomasz Kamiński from comment #1)
> This is probably effect on changing !lt(a,b) && !lt(b, a) into !(a<b) &&
> !(b<a) and then a == b. Then following comparision is unspecified according
> to 5.10 [expr.eq] p2.1:
> If at least one of the operands is a pointer, pointer conversions (4.11),
> function pointer conversions (4.13), and qualification conversions (4.5) are
> performed on both operands to bring them to their composite pointer
> type (Clause 5). Comparing pointers is defined as follows:
> — (2.1) If one pointer represents the address of a complete object, and
> another pointer represents the address one past the last element of a
> different complete object, the result of the comparison is unspecified.
> 
> However I believe that in light of 20.14.6 [comparisons] p14, above
> transformation is not allowed.

I don't see this as prohibiting the transformation.  The standard seems to be saying that they might or might not compare as equal, which presumably depends on how variables are laid out in memory.  The optimization seems wrong to me.

> I don't see this as prohibiting the transformation.  The standard seems to be saying that they might or might not compare as equal, which presumably depends on how variables are laid out in memory.  The optimization seems wrong to me.

But, the code snippet is not using == on this pointer, but std::less specialization that is required to form total order, but in the attached scenario as not because for p and b nor of following hold:
1) r(p, b)
2) r(b, p)
3) b is same as p (!r(p, b) && !r(b, p))
Which proves that r is not an total order. So the guarantee on the less<T*> is no longer provided.

Oh, you mean that compiler is not allowed to turn comparison of p == b into false at compile time, using 5.10 [expr.eq] p2.1? 

Some reference from clang: https://llvm.org/bugs/show_bug.cgi?id=13507. Note that I am unable to reproduce problem on clang.

I think this deserves a Defect report to the C++ committee because even though std::less requires total order, < and <= usage are undefined if used with two different arrays.

(In reply to Tomasz Kamiński from comment #4)
> Oh, you mean that compiler is not allowed to turn comparison of p == b into
> false at compile time, using 5.10 [expr.eq] p2.1? 

No, it's very much allowed to do that.  But I'm skeptical that it's allowed to turn !(a<b)&&!(b<a) into false when a<b and b<a are both false.

This comment doesn't apply to C, where a<b and b<a are both undefined, but in C++ they're only unspecified, and so I would expect them to be consistent.  But Michael Matz disagrees.

(In reply to Andrew Pinski from comment #5)
> I think this deserves a Defect report to the C++ committee because even
> though std::less requires total order, < and <= usage are undefined if used
> with two different arrays.

Which defect?  That just means the implementation has to be more complex, e.g. casting to intptr_t before comparing.

> No, it's very much allowed to do that.  But I'm skeptical that it's allowed to turn !(a<b)&&!(b<a) into false when a<b and b<a are both false.

Notice that I am concerned about !std::less<T*>{}(a,b) && !std::less<T*>(b,a) being false, when std::less<T*>{}(a,b) and std::less<T*>{}(b,a) are both false, and in contrast to raw operator<, std::less is required to provide total order, which is no longer the case.

And my complain, is about behavior of std::less<T*>, that is not standard compliant. If it can be changed without changing <, I am fine with it.

(In reply to Tomasz Kamiński from comment #7)
> Notice that I am concerned about !std::less<T*>{}(a,b) &&
> !std::less<T*>(b,a) being false, when std::less<T*>{}(a,b) and
> std::less<T*>{}(b,a) are both false, and in contrast to raw operator<,
> std::less is required to provide total order, which is no longer the case.
> 
> And my complain, is about behavior of std::less<T*>, that is not standard
> compliant. If it can be changed without changing <, I am fine with it.

Yes, I think the way forward here is to work around this in libstdc++.

Patch available:

https://gcc.gnu.org/ml/gcc-patches/2017-01/msg01688.html

Oh well, the patch is using a reinterpret_cast, and I can't fathom how to work around that problem without compiler help. This problem has been with us since 4.6, so I don't think we should fix it for 7 in its stage4.

Ah, the plot thickens. Jens Maurer wrote:

"Regarding the std::less<T*> issue, it seems a bug in the standard
to require that it be constexpr and deliver a total order.  After
all, the addresses of global objects are defined by the linker,
so it doesn't seem plausible to get a compile-time answer for
std::less<T*> that is the same as a later run-time answer."

So I could theoretically just drop the constexpr from the pointer
specializations and be done with this bugfix. On the other hand,
I expect the plot to thicken further, as library wrappers that contain
pointers don't establish a total order, but in that regard we have
no conformance bugs; the standard doesn't specify that they would.

..which is http://cplusplus.github.io/LWG/lwg-active.html#2491

(In reply to Ville Voutilainen from comment #11)
> Ah, the plot thickens. Jens Maurer wrote:
> 
> "Regarding the std::less<T*> issue, it seems a bug in the standard
> to require that it be constexpr and deliver a total order.  After
> all, the addresses of global objects are defined by the linker,
> so it doesn't seem plausible to get a compile-time answer for
> std::less<T*> that is the same as a later run-time answer."

That doesn't make sense to me; you can call a constexpr function with non-constant arguments and get a non-constant result.  There's no requirement that it give a total order at compile time, is there?

Not in general, no, it doesn't have to always give a compile-time answer. But I believe the library intent is that when it compares compile-time constant pointers, it should give that answer at compile-time, and it should be a toral order. What seems to be suggested by that comment is that since it's possible to compare compile-time constant pointers and run-time values with this function, and it can't know (definition-wise) whether the incoming arguments are constants or not, we could just as well drop the constexpr completely from the pointer specialization of std::less, as that will then open the door to simply reinterpret_cast in it. None of that has been confirmed by LWG, though.

(In reply to Ville Voutilainen from comment #14)
> Not in general, no, it doesn't have to always give a compile-time answer.
> But I believe the library intent is that when it compares compile-time
> constant pointers, it should give that answer at compile-time, and it should
> be a total order.

Right.

> What seems to be suggested by that comment is that since
> it's possible to compare compile-time constant pointers and run-time values
> with this function, and it can't know (definition-wise) whether the incoming
> arguments are constants or not, we could just as well drop the constexpr
> completely from the pointer specialization of std::less, as that will then
> open the door to simply reinterpret_cast in it. None of that has been
> confirmed by LWG, though.

I think this is an example of the prohibition of reinterpret_cast being too broad.

On the other hand, compile-time constant pointers aren't of much use.

On the third hand, using std::less within an array defined in a constexpr function seems entirely reasonable and likely to come up regularly.

I wonder about instead relaxing the total order requirement somewhat, to something like saying that repeated comparisons must be consistent.

I'd like to point out that there is no prohibition against writing reinterpret_cast inside a constexpr function. It's just if you call that function and actually evaluate the reinterpret_cast does the expression turn into an expression that is not a constant expression.

And there is no requirement that calling a constexpr function with arbitrary arguments is, in fact, a constant expression in the sense of C++ section 5.20.  There seems to be a tacit understanding that a standard library function marked as "constexpr" may, in fact, appear in a constant expression if the "obvious" operations on the arguments are suitable (copy constructor, destructor at least), but I couldn't find a statement that would make this expectation explicit.

That means the standard library needs to do its homework to clearly specify under which circumstances (which argument types) it expects a constexpr function to be valid in a constant expression.  Absent that, simply performing the reinterpret_cast is the right answer for std::less<T*>, and seems to be fully conforming with the letter of the current standard.

(In reply to Jens Maurer from comment #16)
> I'd like to point out that there is no prohibition against writing
> reinterpret_cast inside a constexpr function. It's just if you call that
> function and actually evaluate the reinterpret_cast does the expression turn
> into an expression that is not a constant expression.

In this case, it violates [dcl.constexpr]/5, so the function definition
would be ill-formed NDR.

Then you should cheat on [dcl.constexpr] p5 by carving out the nullptr case:

constexpr void less_than(int *p1, int *p2)
{
  if (p1 == nullptr && p2 == nullptr)
    return false;
  return (size_t)p1 < (size_t)p2;
}

This should sidestep [dcl.constexpr] p5, since "less_than(0,0)" seems to be, in fact, a constant expression.

(In reply to Jens Maurer from comment #16)
> That means the standard library needs to do its homework to clearly specify
> under which circumstances (which argument types) it expects a constexpr
> function to be valid in a constant expression.

That's LWG 2833.

GCC 5 branch is being closed

So, any progress here on either the standard side or GCC side?  Do you still need a builtin for constexpr compatible reinterpret cast from the FE, or can it be solved solely in the library?

Hmm, this seems to work:

typedef decltype(sizeof(1)) size_t;

constexpr bool less (const int*a, const int*b)
{
  if (__builtin_constant_p (a < b))
    return a < b;
  return (size_t)a < (size_t)b;
}

int ar[3];
int i;

constexpr bool l1 = less(&ar[0], &ar[1]); // OK
constexpr bool l2 = less(&ar[0], &i);  // error, non-constant

(In reply to Jason Merrill from comment #22)
> Hmm, this seems to work:
> 
> typedef decltype(sizeof(1)) size_t;
> 
> constexpr bool less (const int*a, const int*b)
> {
>   if (__builtin_constant_p (a < b))
>     return a < b;
>   return (size_t)a < (size_t)b;
> }
> 
> int ar[3];
> int i;
> 
> constexpr bool l1 = less(&ar[0], &ar[1]); // OK
> constexpr bool l2 = less(&ar[0], &i);  // error, non-constant

I'd fear about jump-threading vs. __builtin_constant_p issues like PR72785 and others, were the optimizers break the __builtin_constant_p argument and the guarded expression appart and something different might be propagated into them or evaluated differently etc.

One possibility would be a __builtin_constant_p-like builtin that would fold to false much earlier than the current __builtin_constant_p, e.g. during gimplification.
Or use p0595r0 if (constexpr () && a < b) return a < b; or similar builtin
if (__builtin_in_constexpr_p () && a < b) return a < b;
Again, fold this builtin to true if inside constexpr.c, and to false say in the C++ gimplification langhook.

(In reply to Jakub Jelinek from comment #23)
> I'd fear about jump-threading vs. __builtin_constant_p issues like PR72785
> and others, were the optimizers break the __builtin_constant_p argument and
> the guarded expression apart and something different might be propagated
> into them or evaluated differently etc.

I really don't think that's a danger with this usage.  72785 is an abuse of __builtin_constant_p to give wildly different values based on its result: if a is 0, then if b is considered constant we get a NaN, and if it isn't we get 0.  The threading seen in 72785 could only help this usage, by finding more cases where we don't need the conversion to uintptr_t.

About your other comment about the middle-end deciding to do unfriendly things based on undefined behavior in the argument to __builtin_constant_p, the comparison is not undefined, it's unspecified.  I wouldn't expect any surprises from the middle-end.

(In reply to Jakub Jelinek from comment #23)
> One possibility would be a __builtin_constant_p-like builtin that would fold
> to false much earlier than the current __builtin_constant_p, e.g. during
> gimplification.

I think this would only be useful for C++ constexpr evaluation, since most uses in C depend on being folded after inlining.

(In reply to Jason Merrill from comment #25)
> (In reply to Jakub Jelinek from comment #23)
> > One possibility would be a __builtin_constant_p-like builtin that would fold
> > to false much earlier than the current __builtin_constant_p, e.g. during
> > gimplification.
> 
> I think this would only be useful for C++ constexpr evaluation, since most
> uses in C depend on being folded after inlining.

E.g. the kernel ilog2 macro or generally C macro constexpr-like programming would benefit from that too.
One needs to use just macros, not inline functions, sure.
But especially now that c_fully_fold can fold rvalues containing const variables, it can do quite a lot.
The description of kernel ilog2 says:
 * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value
 * @n - parameter
 *
 * constant-capable log of base 2 calculation
 * - this can be used to initialise global variables from constant data, hence
 *   the massive ternary operator construction
 *
 * selects the appropriately-sized optimised version depending on sizeof(n)
so they mostly care that it is usable in constant expressions, if it is used elsewhere, it can be optimized through inlining etc.

Another possible use case is PR83653, there I came up with ugly, but working, workaround, essentially this __builtin_early_constant_p, but only working in macros and not usable in constant expressions.  Store __builtin_constant_p into static const int variable inside a statement expression (when optimizing only), hoping that the static const int var will be optimized away and all it will do is force early evaluation of the __builtin_constant_p.

Here's a really horrible case:

#include <functional>
#include <cassert>

struct X {
  operator const X*() const { return this; }
};

X x;
X y;

int main()
{
  std::less<> lt;
  bool x_less_than_y = lt(x, y);
  bool y_less_than_x = lt(y, x);
  bool x_equal_to_y = !lt(x, y) && !lt(y, x);
  assert( ((int)x_less_than_y + (int)y_less_than_x + (int)x_equal_to_y) == 1 );
}

This happens to give the right answer today, but I don't trust it to always do so. We can't dispatch to the special case for pointers that casts to uintptr_t because we can't know that we'll be comparing pointers (without std::experimental::invocation_type at least ... so I guess I finally have a use case for that).

I can commit a patch that fixes the original testcase, but I now think that the resolution of https://wg21.link/lwg2450 requires compiler help of some kind, at least for cases like comment 27. It effectively says "if x < y uses the built-in operator< for pointers, that comparison yields a total order". That's very different to "if x and y are pointers, comparing them yields a total order". The library can't tell whether x < y uses a built-in operator for pointers, because there could be conversions involved, so the library can't decide whether the cast to uintptr_t is needed.

(In reply to Jakub Jelinek from comment #21)
> So, any progress here on either the standard side or GCC side?  Do you still
> need a builtin for constexpr compatible reinterpret cast from the FE, or can
> it be solved solely in the library?

Even such a magic cast doesn't help, because the library can't tell when that cast should be used. We can't unconditionally cast everything to uintptr_t, only pointers, but we can't tell which operands convert to pointers.

One solution would be a new __builtin_less(op1, op2) builtin that does all the required work:

- if overload resolution for op1 < op2 results in comparing two pointers, then return the result of (uintptr_t)op1 < (uintptr_t)op2 instead, in a constexpr-compatible way (including rejecting comparisons that aren't allowed in constant expressions);
- otherwise, just evaluate op1 < op2 as normal, which may or may not be constexpr-compatible, depending on decltype(op1) and decltype(op2).

Then std::less would just use __builtin_less(x, y) and everything is done by the compiler. And similarly for __builtin_greater/greater_equal/less_equal.

Another solution might be __builtin_totally_ordered(op) which results in some tree type that wraps op, and when used as the operand of a relational operator it performs overload resolution as would happen for op, and if that would compare pointers then op is converted to (uintptr_t)op and that is compared instead. Then std::less would use:
  return __builtin_totally_ordered(x) < __builtin_totally_ordered(y);
But this seems a lot more work to implement, with no advantages.

Another solution would be to change the standard, so that std::less<void> only requires a total order when the arguments are pointers, and not for arbitrary types that might convert to pointers.

(In reply to Jonathan Wakely from comment #28)
> I can commit a patch that fixes the original testcase, but I now think that
> the resolution of https://wg21.link/lwg2450 requires compiler help of some
> kind, at least for cases like comment 27. It effectively says "if x < y uses
> the built-in operator< for pointers, that comparison yields a total order".
> That's very different to "if x and y are pointers, comparing them yields a
> total order". The library can't tell whether x < y uses a built-in operator
> for pointers, because there could be conversions involved, so the library
> can't decide whether the cast to uintptr_t is needed.

https://github.com/ericniebler/stl2/issues/154#issuecomment-311828747 suggests a rather disgusting way for the library to decide whether the built-in operator for pointers would be used.

I guess we'd need to add the full set, i.e. bool __builtin_{less,less_equal,greater,greater_equal}, because e.g. floating point comparisons are in some compilation modes sensitive to what exact operation it is.
I think implementing those shouldn't be that hard, just if the arguments aren't type dependent do a cp_build_binary_op with the arguments and if it returns a pointer comparison, take it appart and stick the new arguments back into the builtin.  Then in constexpr handling handle those like pointer comparisons and in genericization genericize into comparison of the pointers casted to uintptr_t.

If Jason is ok with that and if you don't see other way to implement this properly, I can try to implement that.

First let me try the metaprogramming way to detect when we convert to pointers, and see if it can be done just in the library. I'm working on that ...

Author: redi
Date: Wed Mar 14 23:02:01 2018
New Revision: 258540

URL: https://gcc.gnu.org/viewcvs?rev=258540&root=gcc&view=rev
Log:
PR libstdc++/78420 Make std::less etc. yield total order for pointers

In order for std::less<T*> etc. to meet the total order requirements of
[comparisons] p2 we need to cast unrelated pointers to uintptr_t before
comparing them. Those casts aren't allowed in constant expressions, so
only cast when __builtin_constant_p says the result of the comparison is
not a compile-time constant (because the arguments are not constants, or
the result of the comparison is unspecified). When the result is
constant just compare the pointers directly without casting.

This ensures that the function can be called in constant expressions
with suitable arguments, but still yields a total order even for
otherwise unspecified pointer comparisons.

For std::less<void> etc. add new overloads for pointers, which use
std::less<common_type_t<T*,U*>> directly. Also change the generic
overloads to detect when the comparison would call a built-in relational
operator with pointer operands, and dispatch that case to the
corresponding specialization for void pointers.

	PR libstdc++/78420
	* include/bits/stl_function.h (greater<_Tp*>, less<_Tp*>)
	(greater_equal<_Tp*>, less_equal<_Tp>*): Add partial specializations
	to ensure total order for pointers.
	(greater<void>, less<void>, greater_equal<void>, less_equal<void>):
	Add operator() overloads for pointer arguments and make generic
	overloads dispatch to new _S_cmp functions when comparisons would
	use built-in operators for pointers.
	* testsuite/20_util/function_objects/comparisons_pointer.cc: New.

Added:
    trunk/libstdc++-v3/testsuite/20_util/function_objects/comparisons_pointer.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/stl_function.h

GCC 6 branch is being closed

Fixed in GCC 8.