[gcc r14-9498] libgcc: Fix quotient and/or remainder negation in __divmodbitint4 [PR114327]

[gcc r14-9498] libgcc: Fix quotient and/or remainder negation in __divmodbitint4 [PR114327]

[Jakub Jelinek]

https://gcc.gnu.org/g:a6dab195f7041671166b9aa6a37e0db4236c829d

commit r14-9498-ga6dab195f7041671166b9aa6a37e0db4236c829d
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Fri Mar 15 19:04:33 2024 +0100

    libgcc: Fix quotient and/or remainder negation in __divmodbitint4 [PR114327]
    
    While for __mulbitint3 we actually don't negate anything and perform the
    multiplication in unsigned style always, for __divmodbitint4 if the operands
    aren't unsigned and are negative, we negate them first and then try to
    negate them as needed at the end.
    quotient is negated if just one of the operands was negated and the other
    wasn't or vice versa, and remainder is negated if the first operand was
    negated.
    The case which doesn't work correctly is if due to limited range of the
    operands we perform the division/modulo in some smaller number of limbs
    and then extend it to the desired precision of the quotient and/or
    remainder results.  If they aren't negated, the extension is done with
    memset to 0, if they are negated, the extension was done with memset
    to -1.  The problem is that if the quotient or remainder is zero,
    then bitint_negate negates it again to zero (that is ok), but we should
    then extend with memset to 0, not memset to -1.
    
    The following patch achieves that by letting bitint_negate also check if
    the negated operand is zero and changes the memset argument based on that.
    
    2024-03-15  Jakub Jelinek  <jakub@redhat.com>
    
            PR libgcc/114327
            * libgcc2.c (bitint_negate): Return UWtype bitwise or of all the limbs
            before negation rather than void.
            (__divmodbitint4): Determine whether to fill in the upper limbs after
            negation based on whether bitint_negate returned 0 or non-zero, rather
            then always filling with -1.
    
            * gcc.dg/torture/bitint-63.c: New test.

Diff:
---
 gcc/testsuite/gcc.dg/torture/bitint-63.c | 30 ++++++++++++++++++++++++++++++
 libgcc/libgcc2.c                         | 19 +++++++++++--------
 2 files changed, 41 insertions(+), 8 deletions(-)

diff --git a/gcc/testsuite/gcc.dg/torture/bitint-63.c b/gcc/testsuite/gcc.dg/torture/bitint-63.c
new file mode 100644
index 00000000000..97acba0fa1e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/bitint-63.c
@@ -0,0 +1,30 @@
+/* PR libgcc/114327 */
+/* { dg-do run { target bitint } } */
+/* { dg-options "-std=c23" } */
+/* { dg-skip-if "" { ! run_expensive_tests }  { "*" } { "-O0" "-O2" } } */
+/* { dg-skip-if "" { ! run_expensive_tests } { "-flto" } { "" } } */
+
+#if __BITINT_MAXWIDTH__ >= 256
+_BitInt(256)
+foo (_BitInt(256) b, _BitInt(256) c)
+{
+  return b % c;
+}
+
+_BitInt(256)
+bar (_BitInt(256) b, _BitInt(256) c)
+{
+  return b / c;
+}
+#endif
+
+int
+main ()
+{
+#if __BITINT_MAXWIDTH__ >= 256
+  if (foo (-0x9e9b9fe60wb, 1wb))
+    __builtin_abort ();
+  if (bar (1wb, -0x9e9b9fe60wb))
+    __builtin_abort ();
+#endif
+}
diff --git a/libgcc/libgcc2.c b/libgcc/libgcc2.c
index ef46153731f..dc856740a69 100644
--- a/libgcc/libgcc2.c
+++ b/libgcc/libgcc2.c
@@ -1642,19 +1642,22 @@ __mulbitint3 (UBILtype *ret, SItype retprec,
 #ifdef L_divmodbitint4
 /* D = -S.  */
 
-static void
+static UWtype
 bitint_negate (UBILtype *d, const UBILtype *s, SItype n)
 {
   UWtype c = 1;
+  UWtype r = 0;
   do
     {
       UWtype sv = *s, lo;
+      r |= sv;
       s += BITINT_INC;
       c = __builtin_add_overflow (~sv, c, &lo);
       *d = lo;
       d += BITINT_INC;
     }
   while (--n);
+  return r;
 }
 
 /* D -= S * L.  */
@@ -1977,10 +1980,10 @@ __divmodbitint4 (UBILtype *q, SItype qprec,
 	    n = qn;
 	  else
 	    n = un - vn + 1;
-	  bitint_negate (q + BITINT_END (qn - 1, 0),
-			 q2 + BITINT_END (un - vn, 0), n);
+	  SItype c = bitint_negate (q + BITINT_END (qn - 1, 0),
+				    q2 + BITINT_END (un - vn, 0), n) ? -1 : 0;
 	  if (qn > n)
-	    __builtin_memset (q + BITINT_END (0, n), -1,
+	    __builtin_memset (q + BITINT_END (0, n), c,
 			      (qn - n) * sizeof (UWtype));
 	}
       else
@@ -1999,11 +2002,11 @@ __divmodbitint4 (UBILtype *q, SItype qprec,
       if (uprec < 0)
 	{
 	  /* Negative remainder.  */
-	  bitint_negate (r + BITINT_END (rn - 1, 0),
-			 r + BITINT_END (rn - 1, 0),
-			 rn > vn ? vn : rn);
+	  SItype c = bitint_negate (r + BITINT_END (rn - 1, 0),
+				    r + BITINT_END (rn - 1, 0),
+				    rn > vn ? vn : rn) ? -1 : 0;
 	  if (rn > vn)
-	    __builtin_memset (r + BITINT_END (0, vn), -1,
+	    __builtin_memset (r + BITINT_END (0, vn), c,
 			      (rn - vn) * sizeof (UWtype));
 	}
       else