[gcc r10-11388] libstdc++: Make std::lcm and std::gcd detect overflow [PR105844]

[gcc r10-11388] libstdc++: Make std::lcm and std::gcd detect overflow [PR105844]

[Jonathan Wakely]

https://gcc.gnu.org/g:14175f2262c94868e26f01eef1e14418f2b5e6a9

commit r10-11388-g14175f2262c94868e26f01eef1e14418f2b5e6a9
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Fri Jun 10 14:39:13 2022 +0100

    libstdc++: Make std::lcm and std::gcd detect overflow [PR105844]
    
    When I fixed PR libstdc++/92978 I introduced a regression whereby
    std::lcm(INT_MIN, 1) and std::lcm(50000, 49999) would no longer produce
    errors during constant evaluation. Those calls are undefined, because
    they violate the preconditions that |m| and the result can be
    represented in the return type (which is int in both those cases). The
    regression occurred because __absu<unsigned>(INT_MIN) is well-formed,
    due to the explicit casts to unsigned in that new helper function, and
    the out-of-range multiplication is well-formed, because unsigned
    arithmetic wraps instead of overflowing.
    
    To fix 92978 I made std::gcm and std::lcm calculate |m| and |n|
    immediately, yielding a common unsigned type that was used to calculate
    the result. That was partly correct, but there's no need to use an
    unsigned type. Doing so only suppresses the overflow errors so the
    compiler can't detect them. This change replaces __absu with __abs_r
    that returns the common type (not its corresponding unsigned type). This
    way we can detect overflow in __abs_r when required, while still
    supporting the most-negative value when it can be represented in the
    result type. To detect LCM results that are out of range of the result
    type we still need explicit checks, because neither constant evaluation
    nor UBsan will complain about unsigned wrapping for cases such as
    std::lcm(500000u, 499999u). We can detect those overflows efficiently by
    using __builtin_mul_overflow and asserting.
    
    libstdc++-v3/ChangeLog:
    
            PR libstdc++/105844
            * include/experimental/numeric (experimental::gcd): Simplify
            assertions. Use __abs_r instead of __absu.
            (experimental::lcm): Likewise. Remove use of __detail::__lcm so
            overflow can be detected.
            * include/std/numeric (__detail::__absu): Rename to __abs_r and
            change to allow signed result type, so overflow can be detected.
            (__detail::__lcm): Remove.
            (gcd): Simplify assertions. Use __abs_r instead of __absu.
            (lcm): Likewise. Remove use of __detail::__lcm so overflow can
            be detected.
            * testsuite/26_numerics/gcd/gcd_neg.cc: Adjust dg-error lines.
            * testsuite/26_numerics/lcm/lcm_neg.cc: Likewise.
            * testsuite/26_numerics/gcd/105844.cc: New test.
            * testsuite/26_numerics/lcm/105844.cc: New test.
    
    (cherry picked from commit 671970a5621e18e7079b4ca113e56434c858db66)

Diff:
---
 libstdc++-v3/include/experimental/numeric         | 48 ++++++++------
 libstdc++-v3/include/std/numeric                  | 77 +++++++++++++----------
 libstdc++-v3/testsuite/26_numerics/gcd/105844.cc  | 23 +++++++
 libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc | 10 +--
 libstdc++-v3/testsuite/26_numerics/lcm/105844.cc  | 24 +++++++
 libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc | 10 +--
 6 files changed, 131 insertions(+), 61 deletions(-)

diff --git a/libstdc++-v3/include/experimental/numeric b/libstdc++-v3/include/experimental/numeric
index 4154e535a94..2b06d9ffb51 100644
--- a/libstdc++-v3/include/experimental/numeric
+++ b/libstdc++-v3/include/experimental/numeric
@@ -56,17 +56,15 @@ inline namespace fundamentals_v2
     constexpr common_type_t<_Mn, _Nn>
     gcd(_Mn __m, _Nn __n) noexcept
     {
-      static_assert(is_integral_v<_Mn>,
-	  "std::experimental::gcd arguments must be integers");
-      static_assert(is_integral_v<_Nn>,
-	  "std::experimental::gcd arguments must be integers");
-      static_assert(_Mn(2) != _Mn(1),
-	  "std::experimental::gcd arguments must not be bool");
-      static_assert(_Nn(2) != _Nn(1),
-	  "std::experimental::gcd arguments must not be bool");
-      using _Up = make_unsigned_t<common_type_t<_Mn, _Nn>>;
-      return std::__detail::__gcd(std::__detail::__absu<_Up>(__m),
-				  std::__detail::__absu<_Up>(__n));
+      static_assert(is_integral_v<_Mn> && is_integral_v<_Nn>,
+		    "std::experimental::gcd arguments must be integers");
+      static_assert(_Mn(2) == 2 && _Nn(2) == 2,
+		    "std::experimental::gcd arguments must not be bool");
+      namespace __detail = std::__detail;
+      using _Ct = common_type_t<_Mn, _Nn>;
+      const _Ct __m2 = __detail::__abs_r<_Ct>(__m);
+      const _Ct __n2 = __detail::__abs_r<_Ct>(__n);
+      return __detail::__gcd<make_unsigned_t<_Ct>>(__m2, __n2);
     }
 
   /// Least common multiple
@@ -74,17 +72,27 @@ inline namespace fundamentals_v2
     constexpr common_type_t<_Mn, _Nn>
     lcm(_Mn __m, _Nn __n)
     {
-      static_assert(is_integral_v<_Mn>,
+      static_assert(is_integral_v<_Mn> && is_integral_v<_Nn>,
 	  "std::experimental::lcm arguments must be integers");
-      static_assert(is_integral_v<_Nn>,
-	  "std::experimental::lcm arguments must be integers");
-      static_assert(_Mn(2) != _Mn(1),
-	  "std::experimental::lcm arguments must not be bool");
-      static_assert(_Nn(2) != _Nn(1),
+      static_assert(_Mn(2) == 2 && _Nn(2) == 2,
 	  "std::experimental::lcm arguments must not be bool");
-      using _Up = make_unsigned_t<common_type_t<_Mn, _Nn>>;
-      return std::__detail::__lcm(std::__detail::__absu<_Up>(__m),
-				  std::__detail::__absu<_Up>(__n));
+      namespace __detail = std::__detail;
+      using _Ct = common_type_t<_Mn, _Nn>;
+      const _Ct __m2 = __detail::__abs_r<_Ct>(__m);
+      const _Ct __n2 = __detail::__abs_r<_Ct>(__n);
+      if (__m2 == 0 || __n2 == 0)
+	return 0;
+      _Ct __r = __m2 / __detail::__gcd<make_unsigned_t<_Ct>>(__m2, __n2);
+
+#if defined _GLIBCXX_HAVE_BUILTIN_IS_CONSTANT_EVALUATED
+      if _GLIBCXX17_CONSTEXPR (is_signed_v<_Ct>)
+	if (__builtin_is_constant_evaluated())
+	  return __r * __n2; // constant evaluation can detect overflow here.
+#endif
+
+      bool __overflow = __builtin_mul_overflow(__r, __n2, &__r);
+      __glibcxx_assert(!__overflow);
+      return __r;
     }
 } // namespace fundamentals_v2
 } // namespace experimental
diff --git a/libstdc++-v3/include/std/numeric b/libstdc++-v3/include/std/numeric
index 03cf719c676..b81b5e4a30f 100644
--- a/libstdc++-v3/include/std/numeric
+++ b/libstdc++-v3/include/std/numeric
@@ -76,6 +76,7 @@
 
 #if __cplusplus >= 201402L
 #include <type_traits>
+#include <ext/numeric_traits.h>
 
 namespace std _GLIBCXX_VISIBILITY(default)
 {
@@ -83,19 +84,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 namespace __detail
 {
-  // std::abs is not constexpr, doesn't support unsigned integers,
-  // and std::abs(std::numeric_limits<T>::min()) is undefined.
-  template<typename _Up, typename _Tp>
-    constexpr _Up
-    __absu(_Tp __val)
+  // Like std::abs, but supports unsigned types and returns the specified type,
+  // so |std::numeric_limits<_Tp>::min()| is OK if representable in _Res.
+  template<typename _Res, typename _Tp>
+    constexpr _Res
+    __abs_r(_Tp __val)
     {
-      static_assert(is_unsigned<_Up>::value, "result type must be unsigned");
-      static_assert(sizeof(_Up) >= sizeof(_Tp),
+      static_assert(sizeof(_Res) >= sizeof(_Tp),
 	  "result type must be at least as wide as the input type");
-      return __val < 0 ? -(_Up)__val : (_Up)__val;
+
+      if (__val >= 0)
+	return __val;
+#if defined _GLIBCXX_ASSERTIONS && defined _GLIBCXX_HAVE_BUILTIN_IS_CONSTANT_EVALUATED
+      if (!__builtin_is_constant_evaluated()) // overflow already detected in constexpr
+	__glibcxx_assert(__val != __gnu_cxx::__int_traits<_Res>::__min);
+#endif
+      return -static_cast<_Res>(__val);
     }
 
-  template<typename _Up> void __absu(bool) = delete;
+  template<typename> void __abs_r(bool) = delete;
 
   // GCD implementation
   template<typename _Tp>
@@ -107,16 +114,6 @@ namespace __detail
 	: __n == 0 ? __m
 	: __detail::__gcd(__n, _Tp(__m % __n));
     }
-
-  // LCM implementation
-  template<typename _Tp>
-    constexpr _Tp
-    __lcm(_Tp __m, _Tp __n)
-    {
-      return (__m != 0 && __n != 0)
-	? (__m / __detail::__gcd(__m, __n)) * __n
-	: 0;
-    }
 } // namespace __detail
 
 #if __cplusplus >= 201703L
@@ -131,13 +128,14 @@ namespace __detail
     constexpr common_type_t<_Mn, _Nn>
     gcd(_Mn __m, _Nn __n) noexcept
     {
-      static_assert(is_integral_v<_Mn>, "std::gcd arguments must be integers");
-      static_assert(is_integral_v<_Nn>, "std::gcd arguments must be integers");
-      static_assert(_Mn(2) != _Mn(1), "std::gcd arguments must not be bool");
-      static_assert(_Nn(2) != _Nn(1), "std::gcd arguments must not be bool");
-      using _Up = make_unsigned_t<common_type_t<_Mn, _Nn>>;
-      return __detail::__gcd(__detail::__absu<_Up>(__m),
-			     __detail::__absu<_Up>(__n));
+      static_assert(is_integral_v<_Mn> && is_integral_v<_Nn>,
+		    "std::gcd arguments must be integers");
+      static_assert(_Mn(2) == 2 && _Nn(2) == 2,
+		    "std::gcd arguments must not be bool");
+      using _Ct = common_type_t<_Mn, _Nn>;
+      const _Ct __m2 = __detail::__abs_r<_Ct>(__m);
+      const _Ct __n2 = __detail::__abs_r<_Ct>(__n);
+      return __detail::__gcd<make_unsigned_t<_Ct>>(__m2, __n2);
     }
 
   /// Least common multiple
@@ -145,13 +143,26 @@ namespace __detail
     constexpr common_type_t<_Mn, _Nn>
     lcm(_Mn __m, _Nn __n) noexcept
     {
-      static_assert(is_integral_v<_Mn>, "std::lcm arguments must be integers");
-      static_assert(is_integral_v<_Nn>, "std::lcm arguments must be integers");
-      static_assert(_Mn(2) == 2, "std::lcm arguments must not be bool");
-      static_assert(_Nn(2) == 2, "std::lcm arguments must not be bool");
-      using _Up = make_unsigned_t<common_type_t<_Mn, _Nn>>;
-      return __detail::__lcm(__detail::__absu<_Up>(__m),
-			     __detail::__absu<_Up>(__n));
+      static_assert(is_integral_v<_Mn> && is_integral_v<_Nn>,
+		    "std::lcm arguments must be integers");
+      static_assert(_Mn(2) == 2 && _Nn(2) == 2,
+		    "std::lcm arguments must not be bool");
+      using _Ct = common_type_t<_Mn, _Nn>;
+      const _Ct __m2 = __detail::__abs_r<_Ct>(__m);
+      const _Ct __n2 = __detail::__abs_r<_Ct>(__n);
+      if (__m2 == 0 || __n2 == 0)
+	return 0;
+      _Ct __r = __m2 / __detail::__gcd<make_unsigned_t<_Ct>>(__m2, __n2);
+
+#if defined _GLIBCXX_HAVE_BUILTIN_IS_CONSTANT_EVALUATED
+      if constexpr (is_signed_v<_Ct>)
+	if (__builtin_is_constant_evaluated())
+	  return __r * __n2; // constant evaluation can detect overflow here.
+#endif
+
+      bool __overflow = __builtin_mul_overflow(__r, __n2, &__r);
+      __glibcxx_assert(!__overflow);
+      return __r;
     }
 
 #endif // C++17
diff --git a/libstdc++-v3/testsuite/26_numerics/gcd/105844.cc b/libstdc++-v3/testsuite/26_numerics/gcd/105844.cc
new file mode 100644
index 00000000000..3be18330a0f
--- /dev/null
+++ b/libstdc++-v3/testsuite/26_numerics/gcd/105844.cc
@@ -0,0 +1,23 @@
+// { dg-do compile { target c++17 } }
+#include <numeric>
+#include <climits>
+
+// PR libstdc++/105844
+
+// |INT_MIN| can be represented in common_type_t<int, unsigned> i.e. unsigned.
+static_assert( std::gcd(INT_MIN, 2u) == 2 );
+static_assert( std::gcd(2u, INT_MIN) == 2 );
+
+// |LLONG_MIN| can be represented in unsigned long long.
+static_assert( std::gcd(LLONG_MIN, 2ull) == 2 );
+static_assert( std::gcd(2ull, LLONG_MIN) == 2 );
+
+// But |INT_MIN| cannot be represented in common_type<int, int> i.e. int.
+constexpr int a = std::gcd(INT_MIN, 1); // { dg-error "overflow" }
+constexpr int b = std::gcd(1, INT_MIN); // { dg-error "overflow" }
+
+// And |LLONG_MIN| cannot be represented in long.
+constexpr long long c = std::gcd(LLONG_MIN, 1); // { dg-error "overflow" }
+constexpr long long d = std::gcd(1, LLONG_MIN); // { dg-error "overflow" }
+
+// { dg-prune-output "in 'constexpr' expansion" }
diff --git a/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc b/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc
index 2e56bc650a7..393863cce0a 100644
--- a/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc
+++ b/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc
@@ -46,9 +46,11 @@ test01()
   std::gcd<const int&, const int&>(0.1, 0.1);   // { dg-error "from here" }
 }
 
-// { dg-error "must be integers" "" { target *-*-* } 134 }
-// { dg-error "must be integers" "" { target *-*-* } 135 }
-// { dg-error "must not be bool" "" { target *-*-* } 136 }
-// { dg-error "must not be bool" "" { target *-*-* } 137 }
+// { dg-error "must be integers" "" { target *-*-* } 0 }
+// { dg-error "must not be bool" "" { target *-*-* } 0 }
+// These prunes could be removed if a fix for PR c++/96286 stops them.
 // { dg-prune-output "deleted function" }
 // { dg-prune-output "incomplete type .*make_unsigned" }
+// { dg-prune-output "does not have integral type" }
+// { dg-prune-output "non-integral type" }
+// { dg-prune-output "invalid specialization" }
diff --git a/libstdc++-v3/testsuite/26_numerics/lcm/105844.cc b/libstdc++-v3/testsuite/26_numerics/lcm/105844.cc
new file mode 100644
index 00000000000..0b5ef5ae5e9
--- /dev/null
+++ b/libstdc++-v3/testsuite/26_numerics/lcm/105844.cc
@@ -0,0 +1,24 @@
+// { dg-do compile { target c++17 } }
+#include <numeric>
+#include <climits>
+
+// PR libstdc++/105844
+
+// |INT_MIN| can be represented in common_type_t<int, unsigned> i.e. unsigned.
+static_assert( std::lcm(INT_MIN, 1u) == INT_MAX+1u );
+static_assert( std::lcm(1u, INT_MIN) == INT_MAX+1u );
+
+// But |INT_MIN| cannot be represented in common_type<int, int> i.e. int.
+constexpr int a = std::lcm(INT_MIN, 1); // { dg-error "overflow" }
+constexpr int b = std::lcm(1, INT_MIN); // { dg-error "overflow" }
+
+// And the LCM of 50000 and 49999 cannot be represented in int.
+constexpr int c = std::lcm(50000, 49999); // { dg-error "overflow" }
+constexpr int d = std::lcm(49999, 50000); // { dg-error "overflow" }
+
+// Similarly for unsigned, but the diagnostic is a failed assertion instead.
+constexpr int e = std::lcm(500000u, 499999); // { dg-error "in 'constexpr'" }
+constexpr int f = std::lcm(499999u, 500000); // { dg-error "in 'constexpr'" }
+// { dg-error "unreachable" "" { target *-*-* } 0 }
+
+// { dg-prune-output "in 'constexpr' expansion" }
diff --git a/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc b/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc
index 9e83fdcae0b..5616aa132fa 100644
--- a/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc
+++ b/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc
@@ -46,9 +46,11 @@ test01()
   std::lcm<const int&, const int&>(0.1, 0.1);   // { dg-error "from here" }
 }
 
-// { dg-error "must be integers" "" { target *-*-* } 148 }
-// { dg-error "must be integers" "" { target *-*-* } 149 }
-// { dg-error "must not be bool" "" { target *-*-* } 150 }
-// { dg-error "must not be bool" "" { target *-*-* } 151 }
+// { dg-error "must be integers" "" { target *-*-* } 0 }
+// { dg-error "must not be bool" "" { target *-*-* } 0 }
+// These prunes could be removed if a fix for PR c++/96286 stops them.
 // { dg-prune-output "deleted function" }
 // { dg-prune-output "incomplete type .*make_unsigned" }
+// { dg-prune-output "does not have integral type" }
+// { dg-prune-output "non-integral type" }
+// { dg-prune-output "invalid specialization" }