[PATCH] Fix wide_int unsigned division (PR tree-optimization/69546, take 2)

[Jakub Jelinek]

On Sat, Jan 30, 2016 at 12:31:05PM +0000, Richard Sandiford wrote:
> Might be wrong, but couldn't the same thing happen for the remainder,
> e.g. for 0xfffffffe % 0xffffffff ?

You're right, that is broken too.  Adjusted patch below.

>  Maybe we should have a helper
> function to handle storing uhwis in an array and returning the length.

Any suggestion how to call it, whether to put it in wi namespace, somewhere
else etc.?  Can that be done as a follow-up?  Certainly it would need
to take the uhwi to store, pointer to the array of hwis, and precision.

2016-01-30  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/69546
	* wide-int.cc (wi::divmod_internal): For unsigned division
	where both operands fit into uhwi, if o1 is 1 and o0 has
	msb set, if divident_prec is larger than bits per hwi,
	clear another quotient word and return 2 instead of 1.
	Similarly for remainder with msb in HWI set, if dividend_prec
	is larger than bits per hwi.

	* gcc.dg/torture/pr69546.c: New test.

--- gcc/wide-int.cc.jj	2016-01-29 12:12:43.486930641 +0100
+++ gcc/wide-int.cc	2016-01-30 14:08:18.293537813 +0100
@@ -1788,15 +1788,32 @@ wi::divmod_internal (HOST_WIDE_INT *quot
     {
       unsigned HOST_WIDE_INT o0 = dividend.to_uhwi ();
       unsigned HOST_WIDE_INT o1 = divisor.to_uhwi ();
+      unsigned int quotient_len = 1;
 
       if (quotient)
-	quotient[0] = o0 / o1;
+	{
+	  quotient[0] = o0 / o1;
+	  if (o1 == 1
+	      && (HOST_WIDE_INT) o0 < 0
+	      && dividend_prec > HOST_BITS_PER_WIDE_INT)
+	    {
+	      quotient[1] = 0;
+	      quotient_len = 2;
+	    }
+	}
       if (remainder)
 	{
 	  remainder[0] = o0 % o1;
-	  *remainder_len = 1;
+	  if ((HOST_WIDE_INT) remainder[0] < 0
+	      && dividend_prec > HOST_BITS_PER_WIDE_INT)
+	    {
+	      remainder[1] = 0;
+	      *remainder_len = 2;
+	    }
+	  else
+	    *remainder_len = 1;
 	}
-      return 1;
+      return quotient_len;
     }
 
   /* Make the divisor and dividend positive and remember what we
--- gcc/testsuite/gcc.dg/torture/pr69546-1.c.jj	2016-01-30 13:58:25.925056607 +0100
+++ gcc/testsuite/gcc.dg/torture/pr69546-1.c	2016-01-30 13:58:25.925056607 +0100
@@ -0,0 +1,26 @@
+/* PR tree-optimization/69546 */
+/* { dg-do run { target int128 } } */
+
+unsigned __int128 __attribute__ ((noinline, noclone))
+foo (unsigned long long x)
+{
+  unsigned __int128 y = ~0ULL;
+  x >>= 63;
+  return y / (x | 1);
+}
+
+unsigned __int128 __attribute__ ((noinline, noclone))
+bar (unsigned long long x)
+{
+  unsigned __int128 y = ~33ULL;
+  x >>= 63;
+  return y / (x | 1);
+}
+
+int
+main ()
+{
+  if (foo (1) != ~0ULL || bar (17) != ~33ULL)
+    __builtin_abort ();
+  return 0;
+}
--- gcc/testsuite/gcc.dg/torture/pr69546-2.c.jj	2016-01-30 14:09:40.403364637 +0100
+++ gcc/testsuite/gcc.dg/torture/pr69546-2.c	2016-01-30 14:10:15.591861868 +0100
@@ -0,0 +1,18 @@
+/* PR tree-optimization/69546 */
+/* { dg-do run { target int128 } } */
+
+unsigned __int128
+foo (void)
+{
+  unsigned __int128 a = 0xfffffffffffffffeULL;
+  unsigned __int128 b = 0xffffffffffffffffULL;
+  return a % b;
+}
+
+int
+main ()
+{
+  if (foo () != 0xfffffffffffffffeULL)
+    __builtin_abort ();
+  return 0;
+}


	Jakub