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.

4 files changed, 55 insertions, 8 deletions

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..5b6fea7b560
--- /dev/null
+++ b/libstdc++-v3/testsuite/26_numerics/gcd/105844.cc
@@ -0,0 +1,21 @@
+// { 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" }
diff --git a/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc b/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc
index c9faeebc269..e5d03a9a453 100644
--- a/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc
+++ b/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc
@@ -45,9 +45,11 @@ test01()
   std::gcd<const int&, const int&>(0.1, 0.1);   // { dg-error "from here" }
 }
 
-// { dg-error "must be integers" "" { target *-*-* } 169 }
-// { dg-error "must be integers" "" { target *-*-* } 170 }
-// { dg-error "must not be bool" "" { target *-*-* } 171 }
-// { dg-error "must not be bool" "" { target *-*-* } 172 }
+// { 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..d0e032e03e0
--- /dev/null
+++ b/libstdc++-v3/testsuite/26_numerics/lcm/105844.cc
@@ -0,0 +1,22 @@
+// { 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 }
diff --git a/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc b/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc
index 6c3c9d0c02a..77cb974aab4 100644
--- a/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc
+++ b/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc
@@ -45,9 +45,11 @@ test01()
   std::lcm<const int&, const int&>(0.1, 0.1);   // { dg-error "from here" }
 }
 
-// { dg-error "must be integers" "" { target *-*-* } 183 }
-// { dg-error "must be integers" "" { target *-*-* } 184 }
-// { dg-error "must not be bool" "" { target *-*-* } 185 }
-// { dg-error "must not be bool" "" { target *-*-* } 186 }
+// { 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" }