Bug 78420 - [6/7/8 Regression] std::less<T*> is not a total order with -O2 enabled
Summary: [6/7/8 Regression] std::less<T*> is not a total order with -O2 enabled
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: libstdc++ (show other bugs)
Version: 4.9.0
: P2 normal
Target Milestone: 6.5
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2016-11-18 13:08 UTC by Tomasz Kamiński
Modified: 2017-10-10 13:28 UTC (History)
6 users (show)

See Also:
Host:
Target:
Build:
Known to work: 4.5.4
Known to fail: 4.6.4, 4.7.3, 4.8.5, 4.9.3, 5.3.0, 6.1.0, 7.0
Last reconfirmed: 2017-01-18 00:00:00


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Tomasz Kamiński 2016-11-18 13:08:49 UTC
The 20.14.6 [comparisons] p14:
For templates greater, less, greater_equal, and less_equal, the specializations for any pointer type yield a total order, even if the built-in operators <, >, <=
, >= do not. 

Requires that the less<T*> is an total order, which means that the one of the following is true for every pair of pointer values a,b:
1) lt(a, b)
2) lt(b, a)
3) !lt(a,b) && !lt(b, a) //i.e. a == b, where equality is generated from lessw
where lt is object on less<T*>.

This does not hold for following code snippet when compared with O2:
#include <iostream>

int b[8];
int a[8];

int main()
{
    auto p = a + 8;
    std::less<int*> lt;
    std::cout << p << ' ' << b 
              << ' ' << lt(p, b) 
              << ' ' << lt(b, p) 
              << ' ' << (!lt(p, b) && !lt(b, p)) << std::endl;
}
The output is: 0x6015c0 0x6015c0 0 0 0
(link to live example, require optimization to be enabled: http://melpon.org/wandbox/permlink/vyY82MsxrxWNyOOJ#).
Comment 1 Tomasz Kamiński 2016-11-18 13:12:13 UTC
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.
Comment 2 Jason Merrill 2016-11-18 15:01:25 UTC
(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.
Comment 3 Tomasz Kamiński 2016-11-18 15:05:09 UTC
> 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.
Comment 4 Tomasz Kamiński 2016-11-18 15:14:24 UTC
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.
Comment 5 Andrew Pinski 2016-11-18 19:43:01 UTC
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.
Comment 6 Jason Merrill 2016-11-18 19:54:53 UTC
(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.
Comment 7 Tomasz Kamiński 2016-11-18 21:15:52 UTC
> 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.
Comment 8 Jason Merrill 2016-11-18 21:24:32 UTC
(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++.
Comment 9 Ville Voutilainen 2017-01-22 15:48:55 UTC
Patch available:

https://gcc.gnu.org/ml/gcc-patches/2017-01/msg01688.html
Comment 10 Ville Voutilainen 2017-01-22 16:37:00 UTC
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.
Comment 11 Ville Voutilainen 2017-01-22 22:11:56 UTC
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.
Comment 12 Ville Voutilainen 2017-01-22 22:17:52 UTC
..which is http://cplusplus.github.io/LWG/lwg-active.html#2491
Comment 13 Jason Merrill 2017-01-23 21:45:23 UTC
(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?
Comment 14 Ville Voutilainen 2017-01-23 21:59:46 UTC
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.
Comment 15 Jason Merrill 2017-01-23 22:14:52 UTC
(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.
Comment 16 Jens Maurer 2017-01-23 22:37:31 UTC
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.
Comment 17 Ville Voutilainen 2017-01-23 22:49:22 UTC
(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.
Comment 18 Jens Maurer 2017-01-23 22:57:45 UTC
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.
Comment 19 Jonathan Wakely 2017-01-23 23:18:42 UTC
(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.
Comment 20 Jakub Jelinek 2017-10-10 13:28:26 UTC
GCC 5 branch is being closed