| Message ID | 20190625094005.GA30147@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | Change std::ceil2 to be undefined if the result can't be represented | expand |
On 25/06/19 10:40 +0100, Jonathan Wakely wrote: > * include/std/bit (__ceil2): Make unrepresentable results undefined, > as per P1355R2. Add debug assertion. Perform one left shift, not two, > so that out of range values cause undefined behaviour. Ensure that > shift will still be undefined if left operand is promoted. > * testsuite/26_numerics/bit/bit.pow.two/ceil2.cc: Replace checks for > unrepresentable values with checks that they are not core constant > expressions. > * testsuite/26_numerics/bit/bit.pow.two/ceil2_neg.cc: New test. > >I'm not committing this yet, because P1355 hasn't been accepted into >the draft, but here's a patch to implement it (this reverses the >changes in r263986, and adds special handling for types that undergo >integer promotion). This has now been committed to trunk. I'll backport it to gcc-9-branch soon too. >The goal is that undefined shifts are detectable in three ways, even >if the type is promoted: > >* In constant expressions they make the program ill-formed. >* At runtime they cause UBSan errors. >* At runtime they abort when _GLIBCXX_ASSERTIONS is defined. >commit fd8d9b7898083c8806d2cd300f78739d2afc3503 >Author: Jonathan Wakely <jwakely@redhat.com> >Date: Fri Jun 14 13:32:39 2019 +0100 > > Change std::ceil2 to be undefined if the result can't be represented > > * include/std/bit (__ceil2): Make unrepresentable results undefined, > as per P1355R2. Add debug assertion. Perform one left shift, not two, > so that out of range values cause undefined behaviour. Ensure that > shift will still be undefined if left operand is promoted. > * testsuite/26_numerics/bit/bit.pow.two/ceil2.cc: Replace checks for > unrepresentable values with checks that they are not core constant > expressions. > * testsuite/26_numerics/bit/bit.pow.two/ceil2_neg.cc: New test. > >diff --git a/libstdc++-v3/include/std/bit b/libstdc++-v3/include/std/bit >index e0c53e53756..eb0a7578b8d 100644 >--- a/libstdc++-v3/include/std/bit >+++ b/libstdc++-v3/include/std/bit >@@ -197,9 +197,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > constexpr auto _Nd = numeric_limits<_Tp>::digits; > if (__x == 0 || __x == 1) > return 1; >- const unsigned __n = _Nd - std::__countl_zero((_Tp)(__x - 1u)); >- const _Tp __y_2 = (_Tp)1u << (__n - 1u); >- return __y_2 << 1u; >+ auto __shift_exponent = _Nd - std::__countl_zero((_Tp)(__x - 1u)); >+ // If the shift exponent equals _Nd then the correct result is not >+ // representable as a value of _Tp, and so the result is undefined. >+ // Want that undefined behaviour to be detected in constant expressions, >+ // by UBSan, and by debug assertions. >+#ifdef _GLIBCXX_HAVE_BUILTIN_IS_CONSTANT_EVALUATED >+ if (!__builtin_is_constant_evaluated()) >+ __glibcxx_assert( __shift_exponent != numeric_limits<_Tp>::digits ); >+#endif >+ using __promoted_type = decltype(__x << 1); >+ if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value) >+ { >+ // If __x undergoes integral promotion then shifting by _Nd is >+ // not undefined. In order to make the shift undefined, so that >+ // it is diagnosed in constant expressions and by UBsan, we also >+ // need to "promote" the shift exponent to be too large for the >+ // promoted type. >+ const int __extra_exp = sizeof(__promoted_type) / sizeof(_Tp) / 2; >+ __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp; >+ } >+ return (_Tp)1u << __shift_exponent; > } > > template<typename _Tp> >diff --git a/libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2.cc b/libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2.cc >index 6ffb5f70edb..788c008129e 100644 >--- a/libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2.cc >+++ b/libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2.cc >@@ -20,6 +20,21 @@ > > #include <bit> > >+template<typename T> >+ constexpr T max = std::numeric_limits<T>::max(); >+// Largest representable power of two (i.e. has most significant bit set) >+template<typename T> >+ constexpr T maxpow2 = T(1) << (std::numeric_limits<T>::digits - 1); >+ >+// Detect whether std::ceil2(N) is a constant expression. >+template<auto N, typename = void> >+ struct ceil2_valid >+ : std::false_type { }; >+ >+template<auto N> >+ struct ceil2_valid<N, std::void_t<char[(std::ceil2(N), 1)]>> >+ : std::true_type { }; >+ > template<typename UInt> > constexpr auto > test(UInt x) >@@ -55,13 +70,18 @@ test(UInt x) > static_assert( std::ceil2(UInt(3) << 64) == (UInt(4) << 64) ); > } > >- constexpr UInt msb = UInt(1) << (std::numeric_limits<UInt>::digits - 1); >+ constexpr UInt msb = maxpow2<UInt>; >+ static_assert( ceil2_valid<msb>() ); > static_assert( std::ceil2( msb ) == msb ); >- // Larger values cannot be represented so the return value is unspecified, >- // but must still be valid in constant expressions, i.e. not undefined. >- static_assert( std::ceil2( UInt(msb + 1) ) != 77 ); >- static_assert( std::ceil2( UInt(msb + 2) ) != 77 ); >- static_assert( std::ceil2( UInt(msb + 77) ) != 77 ); >+ static_assert( std::ceil2( UInt(msb - 1) ) == msb ); >+ static_assert( std::ceil2( UInt(msb - 2) ) == msb ); >+ static_assert( std::ceil2( UInt(msb - 3) ) == msb ); >+ >+ // P1355R2: not a constant expression if the result is not representable >+ static_assert( !ceil2_valid<UInt(msb + 1)>() ); >+ static_assert( !ceil2_valid<max<UInt>>() ); >+ static_assert( !ceil2_valid<UInt(max<UInt> - 1)>() ); >+ static_assert( !ceil2_valid<UInt(max<UInt> - 2)>() ); > > return true; > } >@@ -114,3 +134,7 @@ static_assert( test( (__GLIBCXX_TYPE_INT_N_1)0 ).did_not_match() ); > static_assert( test( (unsigned __GLIBCXX_TYPE_INT_N_2)0 ) ); > static_assert( test( (__GLIBCXX_TYPE_INT_N_2)0 ).did_not_match() ); > #endif >+#if defined(__GLIBCXX_TYPE_INT_N_3) >+static_assert( test( (unsigned __GLIBCXX_TYPE_INT_N_3)0 ) ); >+static_assert( test( (__GLIBCXX_TYPE_INT_N_3)0 ).did_not_match() ); >+#endif >diff --git a/libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2_neg.cc b/libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2_neg.cc >new file mode 100644 >index 00000000000..8e107065a92 >--- /dev/null >+++ b/libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2_neg.cc >@@ -0,0 +1,74 @@ >+// Copyright (C) 2019 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 >+// <http://www.gnu.org/licenses/>. >+ >+// { dg-options "-std=gnu++2a -D_GLIBCXX_ASSERTIONS" } >+// { dg-do run { target c++2a } } >+// { dg-xfail-run-if "__glibcxx_assert in ceil2 should fail" { *-*-* } } >+ >+#include <bit> >+ >+// P1355R2: not a constant expression if the result is not representable >+ >+template<auto N, typename = void> >+ struct ceil2_valid >+ : std::false_type { }; >+ >+template<auto N> >+ struct ceil2_valid<N, std::void_t<char[(std::ceil2(N), 1)]>> >+ : std::true_type { }; >+ >+template<typename T> >+ constexpr T max = std::numeric_limits<T>::max(); >+template<typename T> >+ constexpr T maxpow2 = T(1) << (std::numeric_limits<T>::digits - 1); >+ >+static_assert( ceil2_valid<maxpow2<unsigned char>>() ); >+static_assert( !ceil2_valid<maxpow2<unsigned char> + (unsigned char)1>() ); >+ >+static_assert( !ceil2_valid<max<unsigned char>>() ); >+static_assert( !ceil2_valid<max<unsigned char> - (unsigned char)1>() ); >+ >+static_assert( ceil2_valid<maxpow2<unsigned short>>() ); >+static_assert( !ceil2_valid<maxpow2<unsigned short> + (unsigned short)1>() ); >+static_assert( !ceil2_valid<max<unsigned short>>() ); >+static_assert( !ceil2_valid<max<unsigned short> - (unsigned short)1>() ); >+ >+static_assert( ceil2_valid<maxpow2<unsigned int>>() ); >+static_assert( !ceil2_valid<maxpow2<unsigned int> + 1u>() ); >+static_assert( !ceil2_valid<max<unsigned int>>() ); >+static_assert( !ceil2_valid<max<unsigned int> - 1u>() ); >+ >+static_assert( ceil2_valid<maxpow2<unsigned long>>() ); >+static_assert( !ceil2_valid<maxpow2<unsigned long> + 1ul>() ); >+static_assert( !ceil2_valid<max<unsigned long>>() ); >+static_assert( !ceil2_valid<max<unsigned long> - 1ul>() ); >+ >+static_assert( ceil2_valid<maxpow2<unsigned long long>>() ); >+static_assert( !ceil2_valid<maxpow2<unsigned long long> + 1ull>() ); >+static_assert( !ceil2_valid<max<unsigned long long>>() ); >+static_assert( !ceil2_valid<max<unsigned long long> - 1ull>() ); >+ >+void >+test01() >+{ >+ std::ceil2( maxpow2<unsigned> + 1u ); // should fail __glibcxx_assert >+} >+ >+int main() >+{ >+ test01(); >+}
diff --git a/libstdc++-v3/include/std/bit b/libstdc++-v3/include/std/bit index e0c53e53756..eb0a7578b8d 100644 --- a/libstdc++-v3/include/std/bit +++ b/libstdc++-v3/include/std/bit @@ -197,9 +197,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION constexpr auto _Nd = numeric_limits<_Tp>::digits; if (__x == 0 || __x == 1) return 1; - const unsigned __n = _Nd - std::__countl_zero((_Tp)(__x - 1u)); - const _Tp __y_2 = (_Tp)1u << (__n - 1u); - return __y_2 << 1u; + auto __shift_exponent = _Nd - std::__countl_zero((_Tp)(__x - 1u)); + // If the shift exponent equals _Nd then the correct result is not + // representable as a value of _Tp, and so the result is undefined. + // Want that undefined behaviour to be detected in constant expressions, + // by UBSan, and by debug assertions. +#ifdef _GLIBCXX_HAVE_BUILTIN_IS_CONSTANT_EVALUATED + if (!__builtin_is_constant_evaluated()) + __glibcxx_assert( __shift_exponent != numeric_limits<_Tp>::digits ); +#endif + using __promoted_type = decltype(__x << 1); + if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value) + { + // If __x undergoes integral promotion then shifting by _Nd is + // not undefined. In order to make the shift undefined, so that + // it is diagnosed in constant expressions and by UBsan, we also + // need to "promote" the shift exponent to be too large for the + // promoted type. + const int __extra_exp = sizeof(__promoted_type) / sizeof(_Tp) / 2; + __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp; + } + return (_Tp)1u << __shift_exponent; } template<typename _Tp> diff --git a/libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2.cc b/libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2.cc index 6ffb5f70edb..788c008129e 100644 --- a/libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2.cc +++ b/libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2.cc @@ -20,6 +20,21 @@ #include <bit> +template<typename T> + constexpr T max = std::numeric_limits<T>::max(); +// Largest representable power of two (i.e. has most significant bit set) +template<typename T> + constexpr T maxpow2 = T(1) << (std::numeric_limits<T>::digits - 1); + +// Detect whether std::ceil2(N) is a constant expression. +template<auto N, typename = void> + struct ceil2_valid + : std::false_type { }; + +template<auto N> + struct ceil2_valid<N, std::void_t<char[(std::ceil2(N), 1)]>> + : std::true_type { }; + template<typename UInt> constexpr auto test(UInt x) @@ -55,13 +70,18 @@ test(UInt x) static_assert( std::ceil2(UInt(3) << 64) == (UInt(4) << 64) ); } - constexpr UInt msb = UInt(1) << (std::numeric_limits<UInt>::digits - 1); + constexpr UInt msb = maxpow2<UInt>; + static_assert( ceil2_valid<msb>() ); static_assert( std::ceil2( msb ) == msb ); - // Larger values cannot be represented so the return value is unspecified, - // but must still be valid in constant expressions, i.e. not undefined. - static_assert( std::ceil2( UInt(msb + 1) ) != 77 ); - static_assert( std::ceil2( UInt(msb + 2) ) != 77 ); - static_assert( std::ceil2( UInt(msb + 77) ) != 77 ); + static_assert( std::ceil2( UInt(msb - 1) ) == msb ); + static_assert( std::ceil2( UInt(msb - 2) ) == msb ); + static_assert( std::ceil2( UInt(msb - 3) ) == msb ); + + // P1355R2: not a constant expression if the result is not representable + static_assert( !ceil2_valid<UInt(msb + 1)>() ); + static_assert( !ceil2_valid<max<UInt>>() ); + static_assert( !ceil2_valid<UInt(max<UInt> - 1)>() ); + static_assert( !ceil2_valid<UInt(max<UInt> - 2)>() ); return true; } @@ -114,3 +134,7 @@ static_assert( test( (__GLIBCXX_TYPE_INT_N_1)0 ).did_not_match() ); static_assert( test( (unsigned __GLIBCXX_TYPE_INT_N_2)0 ) ); static_assert( test( (__GLIBCXX_TYPE_INT_N_2)0 ).did_not_match() ); #endif +#if defined(__GLIBCXX_TYPE_INT_N_3) +static_assert( test( (unsigned __GLIBCXX_TYPE_INT_N_3)0 ) ); +static_assert( test( (__GLIBCXX_TYPE_INT_N_3)0 ).did_not_match() ); +#endif diff --git a/libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2_neg.cc b/libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2_neg.cc new file mode 100644 index 00000000000..8e107065a92 --- /dev/null +++ b/libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2_neg.cc @@ -0,0 +1,74 @@ +// Copyright (C) 2019 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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a -D_GLIBCXX_ASSERTIONS" } +// { dg-do run { target c++2a } } +// { dg-xfail-run-if "__glibcxx_assert in ceil2 should fail" { *-*-* } } + +#include <bit> + +// P1355R2: not a constant expression if the result is not representable + +template<auto N, typename = void> + struct ceil2_valid + : std::false_type { }; + +template<auto N> + struct ceil2_valid<N, std::void_t<char[(std::ceil2(N), 1)]>> + : std::true_type { }; + +template<typename T> + constexpr T max = std::numeric_limits<T>::max(); +template<typename T> + constexpr T maxpow2 = T(1) << (std::numeric_limits<T>::digits - 1); + +static_assert( ceil2_valid<maxpow2<unsigned char>>() ); +static_assert( !ceil2_valid<maxpow2<unsigned char> + (unsigned char)1>() ); + +static_assert( !ceil2_valid<max<unsigned char>>() ); +static_assert( !ceil2_valid<max<unsigned char> - (unsigned char)1>() ); + +static_assert( ceil2_valid<maxpow2<unsigned short>>() ); +static_assert( !ceil2_valid<maxpow2<unsigned short> + (unsigned short)1>() ); +static_assert( !ceil2_valid<max<unsigned short>>() ); +static_assert( !ceil2_valid<max<unsigned short> - (unsigned short)1>() ); + +static_assert( ceil2_valid<maxpow2<unsigned int>>() ); +static_assert( !ceil2_valid<maxpow2<unsigned int> + 1u>() ); +static_assert( !ceil2_valid<max<unsigned int>>() ); +static_assert( !ceil2_valid<max<unsigned int> - 1u>() ); + +static_assert( ceil2_valid<maxpow2<unsigned long>>() ); +static_assert( !ceil2_valid<maxpow2<unsigned long> + 1ul>() ); +static_assert( !ceil2_valid<max<unsigned long>>() ); +static_assert( !ceil2_valid<max<unsigned long> - 1ul>() ); + +static_assert( ceil2_valid<maxpow2<unsigned long long>>() ); +static_assert( !ceil2_valid<maxpow2<unsigned long long> + 1ull>() ); +static_assert( !ceil2_valid<max<unsigned long long>>() ); +static_assert( !ceil2_valid<max<unsigned long long> - 1ull>() ); + +void +test01() +{ + std::ceil2( maxpow2<unsigned> + 1u ); // should fail __glibcxx_assert +} + +int main() +{ + test01(); +}
* include/std/bit (__ceil2): Make unrepresentable results undefined, as per P1355R2. Add debug assertion. Perform one left shift, not two, so that out of range values cause undefined behaviour. Ensure that shift will still be undefined if left operand is promoted. * testsuite/26_numerics/bit/bit.pow.two/ceil2.cc: Replace checks for unrepresentable values with checks that they are not core constant expressions. * testsuite/26_numerics/bit/bit.pow.two/ceil2_neg.cc: New test. I'm not committing this yet, because P1355 hasn't been accepted into the draft, but here's a patch to implement it (this reverses the changes in r263986, and adds special handling for types that undergo integer promotion). The goal is that undefined shifts are detectable in three ways, even if the type is promoted: * In constant expressions they make the program ill-formed. * At runtime they cause UBSan errors. * At runtime they abort when _GLIBCXX_ASSERTIONS is defined. commit fd8d9b7898083c8806d2cd300f78739d2afc3503 Author: Jonathan Wakely <jwakely@redhat.com> Date: Fri Jun 14 13:32:39 2019 +0100 Change std::ceil2 to be undefined if the result can't be represented * include/std/bit (__ceil2): Make unrepresentable results undefined, as per P1355R2. Add debug assertion. Perform one left shift, not two, so that out of range values cause undefined behaviour. Ensure that shift will still be undefined if left operand is promoted. * testsuite/26_numerics/bit/bit.pow.two/ceil2.cc: Replace checks for unrepresentable values with checks that they are not core constant expressions. * testsuite/26_numerics/bit/bit.pow.two/ceil2_neg.cc: New test.