Backport PR 69400: Invalid 128-bit modulus result

[Richard Sandiford <richard dot sandiford at arm dot com>]

There doesn't seem to have been any fallout from the fix for PR69400
and it applies cleanly to gcc-5-branch.

Bootstrapped & regression-tested on x86_64-linux-ngu.  OK for gcc 5?

Thanks,
Richard


Backport from mainline:

gcc/
2016-01-26  Richard Sandiford  <richard.sandiford@arm.com>

	PR tree-optimization/69400
	* wide-int.cc (wi_pack): Take the precision as argument and
	perform canonicalization here rather than in the callers.
	Use the main loop to handle all full-width HWIs.  Add a
	zero HWI if in_len isn't a full result.
	(wi::divmod_internal): Update accordingly.
	(wi::mul_internal): Likewise.  Simplify.

gcc/testsuite/
2016-01-26  Richard Sandiford  <richard.sandiford@arm.com>

	PR tree-optimization/69400
	* gcc.dg/plugin/wide-int_plugin.c (test_wide_int_mod_trunc): New
	function.
	(plugin_init): Call it.
	* gcc.dg/torture/pr69400.c: New test.

Index: gcc/wide-int.cc
===================================================================
--- gcc/wide-int.cc
+++ gcc/wide-int.cc
@@ -1225,30 +1225,32 @@ wi_unpack (unsigned HOST_HALF_WIDE_INT *result, const HOST_WIDE_INT *input,
     result[j++] = mask;
 }
 
-/* The inverse of wi_unpack.  IN_LEN is the the number of input
-   blocks.  The number of output blocks will be half this amount.  */
-static void
-wi_pack (unsigned HOST_WIDE_INT *result,
+/* The inverse of wi_unpack.  IN_LEN is the number of input
+   blocks and PRECISION is the precision of the result.  Return the
+   number of blocks in the canonicalized result.  */
+static unsigned int
+wi_pack (HOST_WIDE_INT *result,
 	 const unsigned HOST_HALF_WIDE_INT *input,
-	 unsigned int in_len)
+	 unsigned int in_len, unsigned int precision)
 {
   unsigned int i = 0;
   unsigned int j = 0;
+  unsigned int blocks_needed = BLOCKS_NEEDED (precision);
 
-  while (i + 2 < in_len)
+  while (i + 1 < in_len)
     {
-      result[j++] = (unsigned HOST_WIDE_INT)input[i]
-	| ((unsigned HOST_WIDE_INT)input[i + 1]
-	   << HOST_BITS_PER_HALF_WIDE_INT);
+      result[j++] = ((unsigned HOST_WIDE_INT) input[i]
+		     | ((unsigned HOST_WIDE_INT) input[i + 1]
+			<< HOST_BITS_PER_HALF_WIDE_INT));
       i += 2;
     }
 
   /* Handle the case where in_len is odd.   For this we zero extend.  */
   if (in_len & 1)
-    result[j++] = (unsigned HOST_WIDE_INT)input[i];
-  else
-    result[j++] = (unsigned HOST_WIDE_INT)input[i]
-      | ((unsigned HOST_WIDE_INT)input[i + 1] << HOST_BITS_PER_HALF_WIDE_INT);
+    result[j++] = (unsigned HOST_WIDE_INT) input[i];
+  else if (j < blocks_needed)
+    result[j++] = 0;
+  return canonize (result, j, precision);
 }
 
 /* Multiply Op1 by Op2.  If HIGH is set, only the upper half of the
@@ -1471,19 +1473,8 @@ wi::mul_internal (HOST_WIDE_INT *val, const HOST_WIDE_INT *op1val,
 	  *overflow = true;
     }
 
-  if (high)
-    {
-      /* compute [prec] <- ([prec] * [prec]) >> [prec] */
-      wi_pack ((unsigned HOST_WIDE_INT *) val,
-	       &r[half_blocks_needed], half_blocks_needed);
-      return canonize (val, blocks_needed, prec);
-    }
-  else
-    {
-      /* compute [prec] <- ([prec] * [prec]) && ((1 << [prec]) - 1) */
-      wi_pack ((unsigned HOST_WIDE_INT *) val, r, half_blocks_needed);
-      return canonize (val, blocks_needed, prec);
-    }
+  int r_offset = high ? half_blocks_needed : 0;
+  return wi_pack (val, &r[r_offset], half_blocks_needed, prec);
 }
 
 /* Compute the population count of X.  */
@@ -1875,8 +1866,7 @@ wi::divmod_internal (HOST_WIDE_INT *quotient, unsigned int *remainder_len,
   unsigned int quotient_len = 0;
   if (quotient)
     {
-      wi_pack ((unsigned HOST_WIDE_INT *) quotient, b_quotient, m);
-      quotient_len = canonize (quotient, (m + 1) / 2, dividend_prec);
+      quotient_len = wi_pack (quotient, b_quotient, m, dividend_prec);
       /* The quotient is neg if exactly one of the divisor or dividend is
 	 neg.  */
       if (dividend_neg != divisor_neg)
@@ -1887,8 +1877,7 @@ wi::divmod_internal (HOST_WIDE_INT *quotient, unsigned int *remainder_len,
 
   if (remainder)
     {
-      wi_pack ((unsigned HOST_WIDE_INT *) remainder, b_remainder, n);
-      *remainder_len = canonize (remainder, (n + 1) / 2, dividend_prec);
+      *remainder_len = wi_pack (remainder, b_remainder, n, dividend_prec);
       /* The remainder is always the same sign as the dividend.  */
       if (dividend_neg)
 	*remainder_len = wi::sub_large (remainder, zeros, 1, remainder,
Index: gcc/testsuite/gcc.dg/plugin/wide-int_plugin.c
===================================================================
--- gcc/testsuite/gcc.dg/plugin/wide-int_plugin.c
+++ gcc/testsuite/gcc.dg/plugin/wide-int_plugin.c
@@ -36,11 +36,44 @@ test_wide_int_round_sdiv (void)
     abort ();
 }
 
+static void
+test_wide_int_mod_trunc (void)
+{
+  for (unsigned int i = 1; i < MAX_BITSIZE_MODE_ANY_INT; ++i)
+    {
+      if (wi::smod_trunc (wi::lshift (1, i + 1) - 3,
+			  wi::lshift (1, i) - 1)
+	  != wi::lshift (1, i) - 2)
+	abort ();
+      for (unsigned int base = 32; base <= MAX_BITSIZE_MODE_ANY_INT; base *= 2)
+	for (int bias = -1; bias <= 1; ++bias)
+	  {
+	    unsigned int precision = base + bias;
+	    if (i + 1 < precision && precision <= MAX_BITSIZE_MODE_ANY_INT)
+	      {
+		wide_int one = wi::uhwi (1, precision);
+		wide_int a = wi::lshift (one, i + 1) - 3;
+		wide_int b = wi::lshift (one, i) - 1;
+		wide_int c = wi::lshift (one, i) - 2;
+		if (wi::umod_trunc (a, b) != c)
+		  abort ();
+		if (wi::smod_trunc (a, b) != c)
+		  abort ();
+		if (wi::smod_trunc (-a, b) != -c)
+		  abort ();
+		if (wi::smod_trunc (a, -b) != c)
+		  abort ();
+	      }
+	  }
+    }
+}
+
 int
 plugin_init (struct plugin_name_args *plugin_info,
 	     struct plugin_gcc_version *version)
 {
   test_double_int_round_udiv ();
   test_wide_int_round_sdiv ();
+  test_wide_int_mod_trunc ();
   return 0;
 }
Index: gcc/testsuite/gcc.dg/torture/pr69400.c
===================================================================
--- /dev/null
+++ gcc/testsuite/gcc.dg/torture/pr69400.c
@@ -0,0 +1,20 @@
+/* { dg-do run { target int128 } } */
+
+typedef unsigned __int128 u128;
+
+u128 __attribute__((noinline, noclone))
+foo(void)
+{
+	u128 u = -2;
+	u %= 0xffffffffffffffffllu;
+	return u;
+}
+
+int
+main()
+{
+	u128 x = foo();
+	if (x != 0xfffffffffffffffellu)
+		__builtin_abort();
+	return 0;
+}