From 0d57370c9cc3c1fb68be96b8cc15b92496c4dd21 Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Thu, 6 Feb 2020 13:31:36 +0000 Subject: [PATCH] libstdc++: Optimize C++20 comparison category types This reduces the size and alignment of all three comparison category types to a single byte. The partial_ordering::_M_is_ordered flag is replaced by the value 0x02 in the _M_value member. This also optimizes conversion and comparison operators to avoid conditional branches where possible, by comparing _M_value to constants or using bitwise operations to correctly handle the unordered state. * libsupc++/compare (__cmp_cat::type): Define typedef for underlying type of enumerations and comparison category types. (__cmp_cat::_Ord, __cmp_cat::_Ncmp): Add underlying type. (__cmp_cat::_Ncmp::unordered): Change value to 2. (partial_ordering::_M_value, weak_ordering::_M_value) (strong_ordering::_M_value): Change type to __cmp_cat::type. (partial_ordering::_M_is_ordered): Remove data member. (partial_ordering): Use second bit of _M_value for unordered. Adjust comparison operators. (weak_ordering::operator partial_ordering): Simplify to remove branches. (operator<=>(unspecified, weak_ordering)): Likewise. (strong_ordering::operator partial_ordering): Likewise. (strong_ordering::operator weak_ordering): Likewise. (operator<=>(unspecified, strong_ordering)): Likewise. * testsuite/18_support/comparisons/categories/partialord.cc: New test. * testsuite/18_support/comparisons/categories/strongord.cc: New test. * testsuite/18_support/comparisons/categories/weakord.cc: New test. --- libstdc++-v3/ChangeLog | 19 ++++ libstdc++-v3/libsupc++/compare | 96 +++++++----------- .../comparisons/categories/partialord.cc | 86 ++++++++++++++++ .../comparisons/categories/strongord.cc | 98 +++++++++++++++++++ .../comparisons/categories/weakord.cc | 75 ++++++++++++++ 5 files changed, 311 insertions(+), 63 deletions(-) create mode 100644 libstdc++-v3/testsuite/18_support/comparisons/categories/partialord.cc create mode 100644 libstdc++-v3/testsuite/18_support/comparisons/categories/strongord.cc create mode 100644 libstdc++-v3/testsuite/18_support/comparisons/categories/weakord.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 18d02cbfb40..0fce279775a 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,5 +1,24 @@ 2020-02-07 Jonathan Wakely + * libsupc++/compare (__cmp_cat::type): Define typedef for underlying + type of enumerations and comparison category types. + (__cmp_cat::_Ord, __cmp_cat::_Ncmp): Add underlying type. + (__cmp_cat::_Ncmp::unordered): Change value to 2. + (partial_ordering::_M_value, weak_ordering::_M_value) + (strong_ordering::_M_value): Change type to __cmp_cat::type. + (partial_ordering::_M_is_ordered): Remove data member. + (partial_ordering): Use second bit of _M_value for unordered. Adjust + comparison operators. + (weak_ordering::operator partial_ordering): Simplify to remove + branches. + (operator<=>(unspecified, weak_ordering)): Likewise. + (strong_ordering::operator partial_ordering): Likewise. + (strong_ordering::operator weak_ordering): Likewise. + (operator<=>(unspecified, strong_ordering)): Likewise. + * testsuite/18_support/comparisons/categories/partialord.cc: New test. + * testsuite/18_support/comparisons/categories/strongord.cc: New test. + * testsuite/18_support/comparisons/categories/weakord.cc: New test. + * include/std/ranges (iota_view::_Iterator): Fix typo in name of __cpp_lib_three_way_comparison macro and use deduced return type for operator<=>. diff --git a/libstdc++-v3/libsupc++/compare b/libstdc++-v3/libsupc++/compare index a7a29ef0440..b2d64ef74a4 100644 --- a/libstdc++-v3/libsupc++/compare +++ b/libstdc++-v3/libsupc++/compare @@ -48,9 +48,11 @@ namespace std namespace __cmp_cat { - enum class _Ord { equivalent = 0, less = -1, greater = 1 }; + using type = signed char; - enum class _Ncmp { _Unordered = -127 }; + enum class _Ord : type { equivalent = 0, less = -1, greater = 1 }; + + enum class _Ncmp : type { _Unordered = 2 }; struct __unspec { @@ -60,19 +62,22 @@ namespace std class partial_ordering { - int _M_value; - bool _M_is_ordered; + // less=0xff, equiv=0x00, greater=0x01, unordered=0x02 + __cmp_cat::type _M_value; constexpr explicit partial_ordering(__cmp_cat::_Ord __v) noexcept - : _M_value(int(__v)), _M_is_ordered(true) + : _M_value(__cmp_cat::type(__v)) { } constexpr explicit partial_ordering(__cmp_cat::_Ncmp __v) noexcept - : _M_value(int(__v)), _M_is_ordered(false) + : _M_value(__cmp_cat::type(__v)) { } + friend class weak_ordering; + friend class strong_ordering; + public: // valid values static const partial_ordering less; @@ -83,42 +88,42 @@ namespace std // comparisons friend constexpr bool operator==(partial_ordering __v, __cmp_cat::__unspec) noexcept - { return __v._M_is_ordered && __v._M_value == 0; } + { return __v._M_value == 0; } friend constexpr bool operator==(partial_ordering, partial_ordering) noexcept = default; friend constexpr bool operator< (partial_ordering __v, __cmp_cat::__unspec) noexcept - { return __v._M_is_ordered && __v._M_value < 0; } + { return __v._M_value == -1; } friend constexpr bool operator> (partial_ordering __v, __cmp_cat::__unspec) noexcept - { return __v._M_is_ordered && __v._M_value > 0; } + { return __v._M_value == 1; } friend constexpr bool operator<=(partial_ordering __v, __cmp_cat::__unspec) noexcept - { return __v._M_is_ordered && __v._M_value <= 0; } + { return __v._M_value <= 0; } friend constexpr bool operator>=(partial_ordering __v, __cmp_cat::__unspec) noexcept - { return __v._M_is_ordered && __v._M_value >= 0; } + { return __cmp_cat::type(__v._M_value & 1) == __v._M_value; } friend constexpr bool operator< (__cmp_cat::__unspec, partial_ordering __v) noexcept - { return __v._M_is_ordered && 0 < __v._M_value; } + { return __v._M_value == 1; } friend constexpr bool operator> (__cmp_cat::__unspec, partial_ordering __v) noexcept - { return __v._M_is_ordered && 0 > __v._M_value; } + { return __v._M_value == -1; } friend constexpr bool operator<=(__cmp_cat::__unspec, partial_ordering __v) noexcept - { return __v._M_is_ordered && 0 <= __v._M_value; } + { return __cmp_cat::type(__v._M_value & 1) == __v._M_value; } friend constexpr bool operator>=(__cmp_cat::__unspec, partial_ordering __v) noexcept - { return __v._M_is_ordered && 0 >= __v._M_value; } + { return 0 >= __v._M_value; } friend constexpr partial_ordering operator<=>(partial_ordering __v, __cmp_cat::__unspec) noexcept @@ -127,10 +132,8 @@ namespace std friend constexpr partial_ordering operator<=>(__cmp_cat::__unspec, partial_ordering __v) noexcept { - if (__v < 0) - return partial_ordering::greater; - else if (__v > 0) - return partial_ordering::less; + if (__v._M_value & 1) + return partial_ordering(__cmp_cat::_Ord(-__v._M_value)); else return __v; } @@ -151,12 +154,14 @@ namespace std class weak_ordering { - int _M_value; + __cmp_cat::type _M_value; constexpr explicit - weak_ordering(__cmp_cat::_Ord __v) noexcept : _M_value(int(__v)) + weak_ordering(__cmp_cat::_Ord __v) noexcept : _M_value(__cmp_cat::type(__v)) { } + friend class strong_ordering; + public: // valid values static const weak_ordering less; @@ -164,14 +169,7 @@ namespace std static const weak_ordering greater; constexpr operator partial_ordering() const noexcept - { - if (_M_value == 0) - return partial_ordering::equivalent; - else if (_M_value < 0) - return partial_ordering::less; - else - return partial_ordering::greater; - } + { return partial_ordering(__cmp_cat::_Ord(_M_value)); } // comparisons friend constexpr bool @@ -219,14 +217,7 @@ namespace std friend constexpr weak_ordering operator<=>(__cmp_cat::__unspec, weak_ordering __v) noexcept - { - if (__v < 0) - return weak_ordering::greater; - else if (__v > 0) - return weak_ordering::less; - else - return __v; - } + { return weak_ordering(__cmp_cat::_Ord(-__v._M_value)); } }; // valid values' definitions @@ -241,11 +232,11 @@ namespace std class strong_ordering { - int _M_value; + __cmp_cat::type _M_value; constexpr explicit strong_ordering(__cmp_cat::_Ord __v) noexcept - : _M_value(int(__v)) + : _M_value(__cmp_cat::type(__v)) { } public: @@ -256,24 +247,10 @@ namespace std static const strong_ordering greater; constexpr operator partial_ordering() const noexcept - { - if (_M_value == 0) - return partial_ordering::equivalent; - else if (_M_value < 0) - return partial_ordering::less; - else - return partial_ordering::greater; - } + { return partial_ordering(__cmp_cat::_Ord(_M_value)); } constexpr operator weak_ordering() const noexcept - { - if (_M_value == 0) - return weak_ordering::equivalent; - else if (_M_value < 0) - return weak_ordering::less; - else - return weak_ordering::greater; - } + { return weak_ordering(__cmp_cat::_Ord(_M_value)); } // comparisons friend constexpr bool @@ -321,14 +298,7 @@ namespace std friend constexpr strong_ordering operator<=>(__cmp_cat::__unspec, strong_ordering __v) noexcept - { - if (__v < 0) - return strong_ordering::greater; - else if (__v > 0) - return strong_ordering::less; - else - return __v; - } + { return strong_ordering(__cmp_cat::_Ord(-__v._M_value)); } }; // valid values' definitions diff --git a/libstdc++-v3/testsuite/18_support/comparisons/categories/partialord.cc b/libstdc++-v3/testsuite/18_support/comparisons/categories/partialord.cc new file mode 100644 index 00000000000..01db2ca055e --- /dev/null +++ b/libstdc++-v3/testsuite/18_support/comparisons/categories/partialord.cc @@ -0,0 +1,86 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++2a" } +// { dg-do compile { target c++2a } } + +#include + +using std::partial_ordering; + +static_assert( partial_ordering::less == partial_ordering::less ); +static_assert( partial_ordering::less != partial_ordering::equivalent ); +static_assert( partial_ordering::less != partial_ordering::greater ); +static_assert( partial_ordering::less != partial_ordering::unordered ); +static_assert( partial_ordering::equivalent == partial_ordering::equivalent ); +static_assert( partial_ordering::equivalent != partial_ordering::greater ); +static_assert( partial_ordering::equivalent != partial_ordering::unordered ); +static_assert( partial_ordering::greater == partial_ordering::greater ); +static_assert( partial_ordering::greater != partial_ordering::unordered ); +static_assert( partial_ordering::unordered == partial_ordering::unordered ); + +static_assert( ! (partial_ordering::less == 0) ); +static_assert( partial_ordering::less < 0 ); +static_assert( ! (partial_ordering::less > 0) ); +static_assert( partial_ordering::less <= 0 ); +static_assert( ! (partial_ordering::less >= 0) ); +static_assert( ! (0 == partial_ordering::less) ); +static_assert( ! (0 < partial_ordering::less) ); +static_assert( 0 > partial_ordering::less ); +static_assert( ! (0 <= partial_ordering::less) ); +static_assert( 0 >= partial_ordering::less ); +static_assert( (partial_ordering::less <=> 0) == partial_ordering::less ); +static_assert( (0 <=> partial_ordering::less) == partial_ordering::greater ); + +static_assert( (partial_ordering::equivalent == 0) ); +static_assert( ! (partial_ordering::equivalent < 0) ); +static_assert( ! (partial_ordering::equivalent > 0) ); +static_assert( partial_ordering::equivalent <= 0 ); +static_assert( partial_ordering::equivalent >= 0 ); +static_assert( 0 == partial_ordering::equivalent ); +static_assert( ! (0 < partial_ordering::equivalent) ); +static_assert( ! (0 > partial_ordering::equivalent) ); +static_assert( 0 <= partial_ordering::equivalent ); +static_assert( 0 >= partial_ordering::equivalent ); +static_assert( (partial_ordering::equivalent <=> 0) == partial_ordering::equivalent ); +static_assert( (0 <=> partial_ordering::equivalent) == partial_ordering::equivalent ); + +static_assert( ! (partial_ordering::greater == 0) ); +static_assert( ! (partial_ordering::greater < 0) ); +static_assert( partial_ordering::greater > 0 ); +static_assert( ! (partial_ordering::greater <= 0) ); +static_assert( partial_ordering::greater >= 0 ); +static_assert( ! (0 == partial_ordering::greater) ); +static_assert( 0 < partial_ordering::greater ); +static_assert( ! (0 > partial_ordering::greater) ); +static_assert( 0 <= partial_ordering::greater ); +static_assert( ! (0 >= partial_ordering::greater) ); +static_assert( (partial_ordering::greater <=> 0) == partial_ordering::greater ); +static_assert( (0 <=> partial_ordering::greater) == partial_ordering::less ); + +static_assert( ! (partial_ordering::unordered == 0) ); +static_assert( ! (partial_ordering::unordered < 0) ); +static_assert( ! (partial_ordering::unordered > 0) ); +static_assert( ! (partial_ordering::unordered <= 0) ); +static_assert( ! (partial_ordering::unordered >= 0) ); +static_assert( ! (0 == partial_ordering::unordered) ); +static_assert( ! (0 < partial_ordering::unordered) ); +static_assert( ! (0 > partial_ordering::unordered) ); +static_assert( ! (0 <= partial_ordering::unordered) ); +static_assert( ! (0 >= partial_ordering::unordered) ); +static_assert( (partial_ordering::unordered <=> 0) == partial_ordering::unordered ); +static_assert( (0 <=> partial_ordering::unordered) == partial_ordering::unordered ); diff --git a/libstdc++-v3/testsuite/18_support/comparisons/categories/strongord.cc b/libstdc++-v3/testsuite/18_support/comparisons/categories/strongord.cc new file mode 100644 index 00000000000..0485e5a1463 --- /dev/null +++ b/libstdc++-v3/testsuite/18_support/comparisons/categories/strongord.cc @@ -0,0 +1,98 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++2a" } +// { dg-do compile { target c++2a } } + +#include + +using std::strong_ordering; + +static_assert( strong_ordering::less == strong_ordering::less ); +static_assert( strong_ordering::less != strong_ordering::equal ); +static_assert( strong_ordering::less != strong_ordering::equivalent ); +static_assert( strong_ordering::less != strong_ordering::greater ); +static_assert( strong_ordering::equivalent == strong_ordering::equivalent ); +static_assert( strong_ordering::equivalent == strong_ordering::equal ); +static_assert( strong_ordering::equivalent != strong_ordering::greater ); +static_assert( strong_ordering::equal == strong_ordering::equal ); +static_assert( strong_ordering::equal != strong_ordering::greater ); +static_assert( strong_ordering::greater == strong_ordering::greater ); + +static_assert( ! (strong_ordering::less == 0) ); +static_assert( strong_ordering::less < 0 ); +static_assert( ! (strong_ordering::less > 0) ); +static_assert( strong_ordering::less <= 0 ); +static_assert( ! (strong_ordering::less >= 0) ); +static_assert( ! (0 == strong_ordering::less) ); +static_assert( ! (0 < strong_ordering::less) ); +static_assert( 0 > strong_ordering::less ); +static_assert( ! (0 <= strong_ordering::less) ); +static_assert( 0 >= strong_ordering::less ); +static_assert( (strong_ordering::less <=> 0) == strong_ordering::less ); +static_assert( (0 <=> strong_ordering::less) == strong_ordering::greater ); + +static_assert( (strong_ordering::equal == 0) ); +static_assert( ! (strong_ordering::equal < 0) ); +static_assert( ! (strong_ordering::equal > 0) ); +static_assert( strong_ordering::equal <= 0 ); +static_assert( strong_ordering::equal >= 0 ); +static_assert( 0 == strong_ordering::equal ); +static_assert( ! (0 < strong_ordering::equal) ); +static_assert( ! (0 > strong_ordering::equal) ); +static_assert( 0 <= strong_ordering::equal ); +static_assert( 0 >= strong_ordering::equal ); +static_assert( (strong_ordering::equal <=> 0) == strong_ordering::equal ); +static_assert( (0 <=> strong_ordering::equal) == strong_ordering::equal ); + +static_assert( (strong_ordering::equivalent == 0) ); +static_assert( ! (strong_ordering::equivalent < 0) ); +static_assert( ! (strong_ordering::equivalent > 0) ); +static_assert( strong_ordering::equivalent <= 0 ); +static_assert( strong_ordering::equivalent >= 0 ); +static_assert( 0 == strong_ordering::equivalent ); +static_assert( ! (0 < strong_ordering::equivalent) ); +static_assert( ! (0 > strong_ordering::equivalent) ); +static_assert( 0 <= strong_ordering::equivalent ); +static_assert( 0 >= strong_ordering::equivalent ); +static_assert( (strong_ordering::equivalent <=> 0) == strong_ordering::equivalent ); +static_assert( (0 <=> strong_ordering::equivalent) == strong_ordering::equivalent ); + +static_assert( ! (strong_ordering::greater == 0) ); +static_assert( ! (strong_ordering::greater < 0) ); +static_assert( strong_ordering::greater > 0 ); +static_assert( ! (strong_ordering::greater <= 0) ); +static_assert( strong_ordering::greater >= 0 ); +static_assert( ! (0 == strong_ordering::greater) ); +static_assert( 0 < strong_ordering::greater ); +static_assert( ! (0 > strong_ordering::greater) ); +static_assert( 0 <= strong_ordering::greater ); +static_assert( ! (0 >= strong_ordering::greater) ); +static_assert( (strong_ordering::greater <=> 0) == strong_ordering::greater ); +static_assert( (0 <=> strong_ordering::greater) == strong_ordering::less ); + +// Conversions +using std::partial_ordering; +static_assert( partial_ordering(strong_ordering::less) == partial_ordering::less ); +static_assert( partial_ordering(strong_ordering::equal) == partial_ordering::equivalent ); +static_assert( partial_ordering(strong_ordering::equivalent) == partial_ordering::equivalent ); +static_assert( partial_ordering(strong_ordering::greater) == partial_ordering::greater ); +using std::weak_ordering; +static_assert( weak_ordering(strong_ordering::less) == weak_ordering::less ); +static_assert( partial_ordering(strong_ordering::equal) == weak_ordering::equivalent ); +static_assert( partial_ordering(strong_ordering::equivalent) == weak_ordering::equivalent ); +static_assert( weak_ordering(strong_ordering::greater) == weak_ordering::greater ); diff --git a/libstdc++-v3/testsuite/18_support/comparisons/categories/weakord.cc b/libstdc++-v3/testsuite/18_support/comparisons/categories/weakord.cc new file mode 100644 index 00000000000..0720e1f86af --- /dev/null +++ b/libstdc++-v3/testsuite/18_support/comparisons/categories/weakord.cc @@ -0,0 +1,75 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++2a" } +// { dg-do compile { target c++2a } } + +#include + +using std::weak_ordering; + +static_assert( weak_ordering::less == weak_ordering::less ); +static_assert( weak_ordering::less != weak_ordering::equivalent ); +static_assert( weak_ordering::less != weak_ordering::greater ); +static_assert( weak_ordering::equivalent == weak_ordering::equivalent ); +static_assert( weak_ordering::equivalent != weak_ordering::greater ); +static_assert( weak_ordering::greater == weak_ordering::greater ); + +static_assert( ! (weak_ordering::less == 0) ); +static_assert( weak_ordering::less < 0 ); +static_assert( ! (weak_ordering::less > 0) ); +static_assert( weak_ordering::less <= 0 ); +static_assert( ! (weak_ordering::less >= 0) ); +static_assert( ! (0 == weak_ordering::less) ); +static_assert( ! (0 < weak_ordering::less) ); +static_assert( 0 > weak_ordering::less ); +static_assert( ! (0 <= weak_ordering::less) ); +static_assert( 0 >= weak_ordering::less ); +static_assert( (weak_ordering::less <=> 0) == weak_ordering::less ); +static_assert( (0 <=> weak_ordering::less) == weak_ordering::greater ); + +static_assert( (weak_ordering::equivalent == 0) ); +static_assert( ! (weak_ordering::equivalent < 0) ); +static_assert( ! (weak_ordering::equivalent > 0) ); +static_assert( weak_ordering::equivalent <= 0 ); +static_assert( weak_ordering::equivalent >= 0 ); +static_assert( 0 == weak_ordering::equivalent ); +static_assert( ! (0 < weak_ordering::equivalent) ); +static_assert( ! (0 > weak_ordering::equivalent) ); +static_assert( 0 <= weak_ordering::equivalent ); +static_assert( 0 >= weak_ordering::equivalent ); +static_assert( (weak_ordering::equivalent <=> 0) == weak_ordering::equivalent ); +static_assert( (0 <=> weak_ordering::equivalent) == weak_ordering::equivalent ); + +static_assert( ! (weak_ordering::greater == 0) ); +static_assert( ! (weak_ordering::greater < 0) ); +static_assert( weak_ordering::greater > 0 ); +static_assert( ! (weak_ordering::greater <= 0) ); +static_assert( weak_ordering::greater >= 0 ); +static_assert( ! (0 == weak_ordering::greater) ); +static_assert( 0 < weak_ordering::greater ); +static_assert( ! (0 > weak_ordering::greater) ); +static_assert( 0 <= weak_ordering::greater ); +static_assert( ! (0 >= weak_ordering::greater) ); +static_assert( (weak_ordering::greater <=> 0) == weak_ordering::greater ); +static_assert( (0 <=> weak_ordering::greater) == weak_ordering::less ); + +// Conversions +using std::partial_ordering; +static_assert( partial_ordering(weak_ordering::less) == partial_ordering::less ); +static_assert( partial_ordering(weak_ordering::equivalent) == partial_ordering::equivalent ); +static_assert( partial_ordering(weak_ordering::greater) == partial_ordering::greater ); -- 2.30.2