STL: Compiler intrinsics for BUILTIN-PTR-XXX

[CaseyCarter]

The concept-constrained comparisons (std::ranges::equal_to, std::ranges::not_equal_to, std::ranges::less, std::ranges::greater, std::ranges::less_equal, std::ranges::greater_equal, std::compare_three_way) admit pairs of arguments that compare as pointers despite that they do not otherwise meet the constraints. Such arguments are recognized via the exposition-only magic macros BUILTIN-PTR-CMP ([range.cmp]/1) and BUILTIN-PTR-THREE-WAY
([comparisons.three.way]/1). These magic macros can be implemented as three compiler intrinsics:

• __builtin_ptr_equal(T, U) which evaluates to true iff t == u for expressions t and u such that decltype((t)) is T and decltype((u)) is U resolves to a builtin == operator that compares pointers.

• __builtin_ptr_less(T, U) which evaluates to true iff t < u for expressions t and u such that decltype((t)) is T and decltype((u)) is U resolves to a builtin < operator that compares pointers.

• __builtin_ptr_spaceship(T, U) which evaluates to true iff t <=> u for expressions t and u such that decltype((t)) is T and decltype((u)) is U resolves to a builtin <=> operator that compares pointers.

If we cannot find a way to implement the equivalent of these intrinsics in C++ - there are library implementations, but to my knowledge none that properly handle types that convert to function pointers - we need to get these intrinsics implemented in our compiler front-ends, ideally with the same set of names. (I'm not married to the names above, but they seem as good as any.)

[StephanTLavavej]

I am confused about:

• You said "The concept-constrained comparisons ([...] std::compare_three_way) admit pairs of arguments that compare as pointers despite that they do not otherwise meet the constraints." What's an example where three_way_comparable_with<T, U> is false but BUILTIN-PTR-THREE-WAY(T, U) is true?
  • I think this involves cases where common_reference_with<const remove_reference_t<T>&, const remove_reference_t<U>&> isn't satisfied, but (for example) T is a pointer and U is a class that's convertible to that pointer type. Maybe?
• The proposed intrinsics answer the question "would comparing these expressions resolve to a builtin operator that compares pointers?" I see that that's sufficient to implement the requires constraint. However, these function objects have two-part Effects, where they have to do something special (not just using the plain operator) when a builtin pointer operator would be used. Is this wording phrased in a general manner, such that implementations where ptr1 < ptr2 at runtime doesn't implement a strict total order need to do something "special", but implementations such as ours where ptr1 < ptr2 at runtime has always implemented a strict total order can simply say ptr1 < ptr2 directly (as our std::less has done for aeons)? Or is this two-part Effects trying to say that we need to do something special so that invoking these function objects during constexpr evaluation allows pointers to be compared in a strict total order, despite the fact that constexpr prevents ptr1 < ptr2 from compiling for unrelated pointers?
  • If we need to do something special for constexpr, then do we need new intrinsics to actually perform this constexpr comparison?
• Do we need to modify the "classic" function objects (std::less<T> and std::less<void>, etc.) in any way? They clearly aren't concept-constrained, but I can't see whether they have to do something special for constexpr that we aren't doing today.

[CaseyCarter]

I am confused about:

• You said "The concept-constrained comparisons ([...] std::compare_three_way) admit pairs of arguments that compare as pointers despite that they do not otherwise meet the constraints." What's an example where three_way_comparable_with<T, U> is false but BUILTIN-PTR-THREE-WAY(T, U) is true?

  • I think this involves cases where common_reference_with<const remove_reference_t<T>&, const remove_reference_t<U>&> isn't satisfied, but (for example) T is a pointer and U is a class that's convertible to that pointer type. Maybe?

Yes, that's one set of problematic cases; I think it's possible that both arguments are non-pointers with no common reference which convert to pointers when compared. Another problem set is "t < u is well-formed and results in a call to a builtin operator that compares pointers, but t > u is ill-formed."

(Disclosure: this is largely my design/wording so any errors are mine.) It's a defect that the design permits these cases. WG21 should have specified that the same syntax is always required, and that the "converts to a builtin pointer" bit punches a hole through the semantics and not the syntax of equality_comparable_with / totally_ordered_with. I think implementations like ours that don't do aggressively silly things when they see UB comparisons then wouldn't need any intrinsics or even to care at all about the special-cased pointer behavior.

• The proposed intrinsics answer the question "would comparing these expressions resolve to a builtin operator that compares pointers?" I see that that's sufficient to implement the requires constraint. However, these function objects have two-part Effects, where they have to do something special (not just using the plain operator) when a builtin pointer operator would be used. Is this wording phrased in a general manner, such that implementations where ptr1 < ptr2 at runtime doesn't implement a strict total order need to do something "special", but implementations such as ours where ptr1 < ptr2 at runtime has always implemented a strict total order can simply say ptr1 < ptr2 directly (as our std::less has done for aeons)? Or is this two-part Effects trying to say that we need to do something special so that invoking these function objects during constexpr evaluation allows pointers to be compared in a strict total order, despite the fact that constexpr prevents ptr1 < ptr2 from compiling for unrelated pointers?

My current belief is that we only need the intrinsics to punch through the constraints and that return left < right; continues to be the correct body for ranges::less::operator()(const T& left, const U& right). (I don't think Clang does Bad Things when it sees a comparison of unrelated pointers. Certainly such a comparison is not a constant expression, but I don't think the formal UB is allowed to start fires in the code like GCC will do when it sees such a thing.)

• If we need to do something special for constexpr, then do we need new intrinsics to actually perform this constexpr comparison?

As I state above, I don't think we need to do something special. If we did, I think we could e.g.:

if constexpr (__builtin_ptr_eq(T, U)) {
  const auto tptr = static_cast<const volatile void*>(t);
  const auto uptr = static_cast<const volatile void*>(u);
  if (is_constant_evaluated()) {
    return tptr == uptr;
  } else {
    return reinterpret_cast<uintptr_t>(t) == reinterpret_cast<uintptr_t>(u);
  }
} else {
  return t == u;
}

Which I believe works portably for arguments that convert to object pointers, but not with arguments that convert to function pointers. Our implementation allows function pointers to implicitly convert to void*, so I think for us this would be a complete solution even if optimizers start doing evil things with comparisons that have UB. (Unless, obviously, the conditionally-supported conversion of function to object pointers goes away.)

• Do we need to modify the "classic" function objects (std::less<T> and std::less<void>, etc.) in any way? They clearly aren't concept-constrained, but I can't see whether they have to do something special for constexpr that we aren't doing today.

I think not for the same reasons that we don't need to do anything special with the Range flavors, but again if optimizers become more aggressive we should change their bodies similarly to the above.

[timsong-cpp]

It's a defect that the design permits these cases. WG21 should have specified that the same syntax is always required, and that the "converts to a builtin pointer" bit punches a hole through the semantics and not the syntax of equality_comparable_with / totally_ordered_with. I think implementations like ours that don't do aggressively silly things when they see UB comparisons then wouldn't need any intrinsics or even to care at all about the special-cased pointer behavior.

Can we get this defect fixed instead?

[CaseyCarter]

Can we get this defect fixed instead?

Yep - that's the idea.

[timsong-cpp]

Can we get this defect fixed instead?

Yep - that's the idea.

You may find a certain library issue being prioritized today to be of interest, then :)

[StephanTLavavej]

Tracked by LWG-3530 "BUILTIN-PTR-MEOW should not opt the type out of syntactic checks".

[StephanTLavavej]

LWG-3530 has been resolved by the Library Working Group, and I've filed a follow-up issue to clean up the comments we left in the code.