Backport PR 69400: Invalid 128-bit modulus result

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.

On Thu, May 19, 2016 at 9:27 AM, Richard Sandiford
<richard.sandiford@arm.com> wrote:
> 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?

Ok.

Thanks,
Richard.

> 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;
> +}