[gcc r14-10013] libgcc: Fix up __divmodbitint4 [PR114755]

[gcc r14-10013] libgcc: Fix up __divmodbitint4 [PR114755]

[Jakub Jelinek]

https://gcc.gnu.org/g:82d6d385f9708fb6d5e2a2bacd003155cfc41c08

commit r14-10013-g82d6d385f9708fb6d5e2a2bacd003155cfc41c08
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Thu Apr 18 09:49:02 2024 +0200

    libgcc: Fix up __divmodbitint4 [PR114755]
    
    The following testcase aborts on aarch64-linux but does not on x86_64-linux.
    In both cases there is UB in the __divmodbitint4 implemenetation.
    When the divisor is negative with most significant limb (even when partial)
    all ones, has at least 2 limbs and the second most significant limb has the
    most significant bit clear, when this number is negated, it will have 0
    in the most significant limb.
    Already in the PR114397 r14-9592 fix I was dealing with such divisors, but
    thought the problem is only if because of that un < vn doesn't imply the
    quotient is 0 and remainder u.
    But as this testcase shows, the problem is with such divisors always.
    What happens is that we use __builtin_clz* on the most significant limb,
    and assume it will not be 0 because that is UB for the builtins.
    Normally the most significant limb of the divisor shouldn't be 0, as
    guaranteed by the bitint_reduce_prec e.g. for the positive numbers, unless
    the divisor is just 0 (but for vn == 1 we have special cases).
    
    The following patch moves the handling of this corner case a few lines
    earlier before the un < vn check, because adjusting the vn later is harder.
    
    2024-04-18  Jakub Jelinek  <jakub@redhat.com>
    
            PR libgcc/114755
            * libgcc2.c (__divmodbitint4): Perform the decrement on negative
            v with most significant limb all ones and the second least
            significant limb with most significant bit clear always, regardless of
            un < vn.
    
            * gcc.dg/torture/bitint-69.c: New test.

Diff:
---
 gcc/testsuite/gcc.dg/torture/bitint-69.c |  26 ++++++++
 libgcc/libgcc2.c                         | 105 +++++++++++++++----------------
 2 files changed, 75 insertions(+), 56 deletions(-)

diff --git a/gcc/testsuite/gcc.dg/torture/bitint-69.c b/gcc/testsuite/gcc.dg/torture/bitint-69.c
new file mode 100644
index 00000000000..5f89357678e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/bitint-69.c
@@ -0,0 +1,26 @@
+/* PR libgcc/114755 */
+/* { 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__ >= 255
+_BitInt(65)
+foo (void)
+{
+  _BitInt(255) a = 0x040404040404040404040404wb;
+  _BitInt(65) b = -0xffffffffffffffffwb;
+  _BitInt(65) r = a % b;
+  return r;
+}
+#endif
+
+int
+main ()
+{
+#if __BITINT_MAXWIDTH__ >= 255
+  _BitInt(65) x = foo ();
+  if (x != 0x0404040408080808wb)
+    __builtin_abort ();
+#endif
+}
diff --git a/libgcc/libgcc2.c b/libgcc/libgcc2.c
index 71c73d6b846..120d071a168 100644
--- a/libgcc/libgcc2.c
+++ b/libgcc/libgcc2.c
@@ -1705,69 +1705,62 @@ __divmodbitint4 (UBILtype *q, SItype qprec,
   USItype rn = ((USItype) rprec + W_TYPE_SIZE - 1) / W_TYPE_SIZE;
   USItype up = auprec % W_TYPE_SIZE;
   USItype vp = avprec % W_TYPE_SIZE;
-  if (__builtin_expect (un < vn, 0))
+  /* If vprec < 0 and the top limb of v is all ones and the second most
+     significant limb has most significant bit clear, then just decrease
+     vn/avprec/vp, because after negation otherwise v2 would have most
+     significant limb clear.  */
+  if (vprec < 0
+      && ((v[BITINT_END (0, vn - 1)] | (vp ? ((UWtype) -1 << vp) : 0))
+	  == (UWtype) -1)
+      && vn > 1
+      && (Wtype) v[BITINT_END (1, vn - 2)] >= 0)
     {
-      /* If abs(v) > abs(u), then q is 0 and r is u.
-	 Unfortunately un < vn doesn't always mean abs(v) > abs(u).
-	 If uprec > 0 and vprec < 0 and vn == un + 1, if the
-	 top limb of v is all ones and the second most significant
-	 limb has most significant bit clear, then just decrease
-	 vn/avprec/vp and continue, after negation both numbers
-	 will have the same number of limbs.  */
-      if (un + 1 == vn
-	  && uprec >= 0
-	  && vprec < 0
-	  && ((v[BITINT_END (0, vn - 1)] | (vp ? ((UWtype) -1 << vp) : 0))
-	      == (UWtype) -1)
-	  && (Wtype) v[BITINT_END (1, vn - 2)] >= 0)
-	{
-	  vp = 0;
-	  --vn;
+      vp = 0;
+      --vn;
 #if __LIBGCC_BITINT_ORDER__ == __ORDER_BIG_ENDIAN__
-	  ++v;
+      ++v;
 #endif
+    }
+  if (__builtin_expect (un < vn, 0))
+    {
+      /* q is 0 and r is u.  */
+      if (q)
+	__builtin_memset (q, 0, qn * sizeof (UWtype));
+      if (r == NULL)
+	return;
+#if __LIBGCC_BITINT_ORDER__ == __ORDER_BIG_ENDIAN__
+      r += rn - 1;
+      u += un - 1;
+#endif
+      if (up)
+	--un;
+      if (rn < un)
+	un = rn;
+      for (rn -= un; un; --un)
+	{
+	  *r = *u;
+	  r += BITINT_INC;
+	  u += BITINT_INC;
 	}
-      else
+      if (!rn)
+	return;
+      if (up)
 	{
-	  /* q is 0 and r is u.  */
-	  if (q)
-	    __builtin_memset (q, 0, qn * sizeof (UWtype));
-	  if (r == NULL)
-	    return;
-#if __LIBGCC_BITINT_ORDER__ == __ORDER_BIG_ENDIAN__
-	  r += rn - 1;
-	  u += un - 1;
-#endif
-	  if (up)
-	    --un;
-	  if (rn < un)
-	    un = rn;
-	  for (rn -= un; un; --un)
-	    {
-	      *r = *u;
-	      r += BITINT_INC;
-	      u += BITINT_INC;
-	    }
-	  if (!rn)
+	  if (uprec > 0)
+	    *r = *u & (((UWtype) 1 << up) - 1);
+	  else
+	    *r = *u | ((UWtype) -1 << up);
+	  r += BITINT_INC;
+	  if (!--rn)
 	    return;
-	  if (up)
-	    {
-	      if (uprec > 0)
-		*r = *u & (((UWtype) 1 << up) - 1);
-	      else
-		*r = *u | ((UWtype) -1 << up);
-	      r += BITINT_INC;
-	      if (!--rn)
-		return;
-	    }
-	  UWtype c = uprec < 0 ? (UWtype) -1 : (UWtype) 0;
-	  for (; rn; --rn)
-	    {
-	      *r = c;
-	      r += BITINT_INC;
-	    }
-	  return;
 	}
+      UWtype c = uprec < 0 ? (UWtype) -1 : (UWtype) 0;
+      for (; rn; --rn)
+	{
+	  *r = c;
+	  r += BITINT_INC;
+	}
+      return;
     }
   USItype qn2 = un - vn + 1;
   if (qn >= qn2)