[PATCH] wide-int: Fix up wi::divmod_internal [PR110731]

[PATCH] wide-int: Fix up wi::divmod_internal [PR110731]

[Jakub Jelinek]

Hi!

As the following testcase shows, wi::divmod_internal doesn't handle
correctly signed division with precision > 64 when the dividend (and likely
divisor as well) is the type's minimum and the precision isn't divisible
by 64.

A few lines above what the patch hunk changes is:
  /* Make the divisor and dividend positive and remember what we
     did.  */
  if (sgn == SIGNED)
    {
      if (wi::neg_p (dividend))
        {
          neg_dividend = -dividend;
          dividend = neg_dividend;
          dividend_neg = true;
        }
      if (wi::neg_p (divisor))
        {
          neg_divisor = -divisor;
          divisor = neg_divisor;
          divisor_neg = true;
        }
    }
i.e. we negate negative dividend or divisor and remember those.
But, after we do that, when unpacking those values into b_dividend and
b_divisor we need to always treat the wide_ints as UNSIGNED,
because divmod_internal_2 performs an unsigned division only.
Now, if precision <= 64, we don't reach here at all, earlier code
handles it.  If dividend or divisor aren't the most negative values,
the negation clears their most significant bit, so it doesn't really
matter if we unpack SIGNED or UNSIGNED.  And if precision is multiple
of HOST_BITS_PER_WIDE_INT, there is no difference in behavior, while
-0x80000000000000000000000000000000 negates to
-0x80000000000000000000000000000000 the unpacking of it as SIGNED
or UNSIGNED works the same.
In the testcase, we have signed precision 119 and the dividend is
val = { 0, 0xffc0000000000000 }, len = 2, precision = 119
both before and after negation.
Divisor is
val = { 2 }, len = 1, precision = 119
But we really want to divide 0x400000000000000000000000000000 by 2
unsigned and then negate at the end.
If it is unsigned precision 119 division
0x400000000000000000000000000000 by 2
dividend is
val = { 0, 0xffc0000000000000 }, len = 2, precision = 119
but as we unpack it UNSIGNED, it is unpacked into
0, 0, 0, 0x00400000

The following patch fixes it by always using UNSIGNED unpacking
because we've already negated negative values at that point if
sgn == SIGNED and so most negative constants should be treated as
positive.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk, 13.2
and later for older branches?

2023-07-19  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/110731
	* wide-int.cc (wi::divmod_internal): Always unpack dividend and
	divisor as UNSIGNED regardless of sgn.

	* gcc.dg/pr110731.c: New test.

--- gcc/wide-int.cc.jj	2023-06-12 15:47:22.461502821 +0200
+++ gcc/wide-int.cc	2023-07-19 09:52:40.241661869 +0200
@@ -1911,9 +1911,9 @@ wi::divmod_internal (HOST_WIDE_INT *quot
     }
 
   wi_unpack (b_dividend, dividend.get_val (), dividend.get_len (),
-	     dividend_blocks_needed, dividend_prec, sgn);
+	     dividend_blocks_needed, dividend_prec, UNSIGNED);
   wi_unpack (b_divisor, divisor.get_val (), divisor.get_len (),
-	     divisor_blocks_needed, divisor_prec, sgn);
+	     divisor_blocks_needed, divisor_prec, UNSIGNED);
 
   m = dividend_blocks_needed;
   b_dividend[m] = 0;
--- gcc/testsuite/gcc.dg/pr110731.c.jj	2023-07-19 10:03:03.707986705 +0200
+++ gcc/testsuite/gcc.dg/pr110731.c	2023-07-19 10:04:34.857716862 +0200
@@ -0,0 +1,17 @@
+/* PR tree-optimization/110731 */
+/* { dg-do run { target int128 } } */
+/* { dg-options "-O2" } */
+
+__int128
+foo (void)
+{
+  struct S { __int128 f : 119; } s = { ((__int128) -18014398509481984) << 64 };
+  return s.f / 2;
+}
+
+int
+main ()
+{
+  if (foo () != (((__int128) -9007199254740992) << 64))
+    __builtin_abort ();
+}

	Jakub

Re: [PATCH] wide-int: Fix up wi::divmod_internal [PR110731]

[Richard Biener]

On Wed, 19 Jul 2023, Jakub Jelinek wrote:

> Hi!
> 
> As the following testcase shows, wi::divmod_internal doesn't handle
> correctly signed division with precision > 64 when the dividend (and likely
> divisor as well) is the type's minimum and the precision isn't divisible
> by 64.
> 
> A few lines above what the patch hunk changes is:
>   /* Make the divisor and dividend positive and remember what we
>      did.  */
>   if (sgn == SIGNED)
>     {
>       if (wi::neg_p (dividend))
>         {
>           neg_dividend = -dividend;
>           dividend = neg_dividend;
>           dividend_neg = true;
>         }
>       if (wi::neg_p (divisor))
>         {
>           neg_divisor = -divisor;
>           divisor = neg_divisor;
>           divisor_neg = true;
>         }
>     }
> i.e. we negate negative dividend or divisor and remember those.
> But, after we do that, when unpacking those values into b_dividend and
> b_divisor we need to always treat the wide_ints as UNSIGNED,
> because divmod_internal_2 performs an unsigned division only.
> Now, if precision <= 64, we don't reach here at all, earlier code
> handles it.  If dividend or divisor aren't the most negative values,
> the negation clears their most significant bit, so it doesn't really
> matter if we unpack SIGNED or UNSIGNED.  And if precision is multiple
> of HOST_BITS_PER_WIDE_INT, there is no difference in behavior, while
> -0x80000000000000000000000000000000 negates to
> -0x80000000000000000000000000000000 the unpacking of it as SIGNED
> or UNSIGNED works the same.
> In the testcase, we have signed precision 119 and the dividend is
> val = { 0, 0xffc0000000000000 }, len = 2, precision = 119
> both before and after negation.
> Divisor is
> val = { 2 }, len = 1, precision = 119
> But we really want to divide 0x400000000000000000000000000000 by 2
> unsigned and then negate at the end.
> If it is unsigned precision 119 division
> 0x400000000000000000000000000000 by 2
> dividend is
> val = { 0, 0xffc0000000000000 }, len = 2, precision = 119
> but as we unpack it UNSIGNED, it is unpacked into
> 0, 0, 0, 0x00400000
> 
> The following patch fixes it by always using UNSIGNED unpacking
> because we've already negated negative values at that point if
> sgn == SIGNED and so most negative constants should be treated as
> positive.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk, 13.2
> and later for older branches?

OK.

Thanks,
Richard.

> 2023-07-19  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/110731
> 	* wide-int.cc (wi::divmod_internal): Always unpack dividend and
> 	divisor as UNSIGNED regardless of sgn.
> 
> 	* gcc.dg/pr110731.c: New test.
> 
> --- gcc/wide-int.cc.jj	2023-06-12 15:47:22.461502821 +0200
> +++ gcc/wide-int.cc	2023-07-19 09:52:40.241661869 +0200
> @@ -1911,9 +1911,9 @@ wi::divmod_internal (HOST_WIDE_INT *quot
>      }
>  
>    wi_unpack (b_dividend, dividend.get_val (), dividend.get_len (),
> -	     dividend_blocks_needed, dividend_prec, sgn);
> +	     dividend_blocks_needed, dividend_prec, UNSIGNED);
>    wi_unpack (b_divisor, divisor.get_val (), divisor.get_len (),
> -	     divisor_blocks_needed, divisor_prec, sgn);
> +	     divisor_blocks_needed, divisor_prec, UNSIGNED);
>  
>    m = dividend_blocks_needed;
>    b_dividend[m] = 0;
> --- gcc/testsuite/gcc.dg/pr110731.c.jj	2023-07-19 10:03:03.707986705 +0200
> +++ gcc/testsuite/gcc.dg/pr110731.c	2023-07-19 10:04:34.857716862 +0200
> @@ -0,0 +1,17 @@
> +/* PR tree-optimization/110731 */
> +/* { dg-do run { target int128 } } */
> +/* { dg-options "-O2" } */
> +
> +__int128
> +foo (void)
> +{
> +  struct S { __int128 f : 119; } s = { ((__int128) -18014398509481984) << 64 };
> +  return s.f / 2;
> +}
> +
> +int
> +main ()
> +{
> +  if (foo () != (((__int128) -9007199254740992) << 64))
> +    __builtin_abort ();
> +}
> 
> 	Jakub
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg,
Germany; GF: Ivo Totev, Andrew Myers, Andrew McDonald, Boudien Moerman;
HRB 36809 (AG Nuernberg)