[wide-int 3/8] Add and use udiv_ceil

[wide-int 3/8] Add and use udiv_ceil

[Richard Sandiford]

Just a minor tweak to avoid several calculations when one would do.
Since we have a function for rounded-up division, we might as well
use it instead of the (X + Y - 1) / Y idiom.

Tested on x86_64-linux-gnu.  OK to install?

Thanks,
Richard


Index: gcc/dwarf2out.c
===================================================================
--- gcc/dwarf2out.c	2014-04-22 20:31:25.187000808 +0100
+++ gcc/dwarf2out.c	2014-04-22 20:31:26.374009366 +0100
@@ -14824,7 +14824,7 @@ simple_decl_align_in_bits (const_tree de
 static inline offset_int
 round_up_to_align (const offset_int &t, unsigned int align)
 {
-  return wi::udiv_trunc (t + align - 1, align) * align;
+  return wi::udiv_ceil (t, align) * align;
 }
 
 /* Given a pointer to a FIELD_DECL, compute and return the byte offset of the
Index: gcc/wide-int.h
===================================================================
--- gcc/wide-int.h	2014-04-22 20:31:25.842005530 +0100
+++ gcc/wide-int.h	2014-04-22 20:31:26.375009373 +0100
@@ -521,6 +521,7 @@ #define SHIFT_FUNCTION \
   BINARY_FUNCTION udiv_floor (const T1 &, const T2 &);
   BINARY_FUNCTION sdiv_floor (const T1 &, const T2 &);
   BINARY_FUNCTION div_ceil (const T1 &, const T2 &, signop, bool * = 0);
+  BINARY_FUNCTION udiv_ceil (const T1 &, const T2 &);
   BINARY_FUNCTION div_round (const T1 &, const T2 &, signop, bool * = 0);
   BINARY_FUNCTION divmod_trunc (const T1 &, const T2 &, signop,
 				WI_BINARY_RESULT (T1, T2) *);
@@ -2566,6 +2567,13 @@ wi::div_ceil (const T1 &x, const T2 &y,
   return quotient;
 }
 
+template <typename T1, typename T2>
+inline WI_BINARY_RESULT (T1, T2)
+wi::udiv_ceil (const T1 &x, const T2 &y)
+{
+  return div_ceil (x, y, UNSIGNED);
+}
+
 /* Return X / Y, rouding towards nearest with ties away from zero.
    Treat X and Y as having the signedness given by SGN.  Indicate
    in *OVERFLOW if the result overflows.  */

Re: [wide-int 3/8] Add and use udiv_ceil

[Richard Biener]

On Tue, Apr 22, 2014 at 9:51 PM, Richard Sandiford
<rdsandiford@googlemail.com> wrote:
> Just a minor tweak to avoid several calculations when one would do.
> Since we have a function for rounded-up division, we might as well
> use it instead of the (X + Y - 1) / Y idiom.
>
> Tested on x86_64-linux-gnu.  OK to install?

Ok.

Thanks,
Richard.

> Thanks,
> Richard
>
>
> Index: gcc/dwarf2out.c
> ===================================================================
> --- gcc/dwarf2out.c     2014-04-22 20:31:25.187000808 +0100
> +++ gcc/dwarf2out.c     2014-04-22 20:31:26.374009366 +0100
> @@ -14824,7 +14824,7 @@ simple_decl_align_in_bits (const_tree de
>  static inline offset_int
>  round_up_to_align (const offset_int &t, unsigned int align)
>  {
> -  return wi::udiv_trunc (t + align - 1, align) * align;
> +  return wi::udiv_ceil (t, align) * align;
>  }
>
>  /* Given a pointer to a FIELD_DECL, compute and return the byte offset of the
> Index: gcc/wide-int.h
> ===================================================================
> --- gcc/wide-int.h      2014-04-22 20:31:25.842005530 +0100
> +++ gcc/wide-int.h      2014-04-22 20:31:26.375009373 +0100
> @@ -521,6 +521,7 @@ #define SHIFT_FUNCTION \
>    BINARY_FUNCTION udiv_floor (const T1 &, const T2 &);
>    BINARY_FUNCTION sdiv_floor (const T1 &, const T2 &);
>    BINARY_FUNCTION div_ceil (const T1 &, const T2 &, signop, bool * = 0);
> +  BINARY_FUNCTION udiv_ceil (const T1 &, const T2 &);
>    BINARY_FUNCTION div_round (const T1 &, const T2 &, signop, bool * = 0);
>    BINARY_FUNCTION divmod_trunc (const T1 &, const T2 &, signop,
>                                 WI_BINARY_RESULT (T1, T2) *);
> @@ -2566,6 +2567,13 @@ wi::div_ceil (const T1 &x, const T2 &y,
>    return quotient;
>  }
>
> +template <typename T1, typename T2>
> +inline WI_BINARY_RESULT (T1, T2)
> +wi::udiv_ceil (const T1 &x, const T2 &y)
> +{
> +  return div_ceil (x, y, UNSIGNED);
> +}
> +
>  /* Return X / Y, rouding towards nearest with ties away from zero.
>     Treat X and Y as having the signedness given by SGN.  Indicate
>     in *OVERFLOW if the result overflows.  */

Re: [wide-int 3/8] Add and use udiv_ceil

[Richard Sandiford]

Richard Sandiford <rdsandiford@googlemail.com> writes:
> Just a minor tweak to avoid several calculations when one would do.
> Since we have a function for rounded-up division, we might as well
> use it instead of the (X + Y - 1) / Y idiom.
>
> Tested on x86_64-linux-gnu.  OK to install?

I ended up reverting this.  I'd assumed that T would be nonnegative,
but it turns out that there are cases where T itself is negative
but T + ALIGN - 1 is nonnegative.  In those cases the effect of
this patch was to do an unsigned division on the "negative"
(i.e. very large positive) number, add 1 to the large result,
and then multiply the large result by ALIGN to get zero.

Using a ubsan bootstrap after this change showed up some bugs in the
divmod code; the symptoms were non-fatal overflow warnings during the
bootstrap itself.  I sent a separate patch for that and made sure
that the failures were gone.

With that fixed, the udiv_ceil version gave the same result as
the original, but it's a non-optimisation after all.

> Thanks,
> Richard
>
>
> Index: gcc/dwarf2out.c
> ===================================================================
> --- gcc/dwarf2out.c	2014-04-22 20:31:25.187000808 +0100
> +++ gcc/dwarf2out.c	2014-04-22 20:31:26.374009366 +0100
> @@ -14824,7 +14824,7 @@ simple_decl_align_in_bits (const_tree de
>  static inline offset_int
>  round_up_to_align (const offset_int &t, unsigned int align)
>  {
> -  return wi::udiv_trunc (t + align - 1, align) * align;
> +  return wi::udiv_ceil (t, align) * align;
>  }
>  
>  /* Given a pointer to a FIELD_DECL, compute and return the byte offset of the
> Index: gcc/wide-int.h
> ===================================================================
> --- gcc/wide-int.h	2014-04-22 20:31:25.842005530 +0100
> +++ gcc/wide-int.h	2014-04-22 20:31:26.375009373 +0100
> @@ -521,6 +521,7 @@ #define SHIFT_FUNCTION \
>    BINARY_FUNCTION udiv_floor (const T1 &, const T2 &);
>    BINARY_FUNCTION sdiv_floor (const T1 &, const T2 &);
>    BINARY_FUNCTION div_ceil (const T1 &, const T2 &, signop, bool * = 0);
> +  BINARY_FUNCTION udiv_ceil (const T1 &, const T2 &);
>    BINARY_FUNCTION div_round (const T1 &, const T2 &, signop, bool * = 0);
>    BINARY_FUNCTION divmod_trunc (const T1 &, const T2 &, signop,
>  				WI_BINARY_RESULT (T1, T2) *);
> @@ -2566,6 +2567,13 @@ wi::div_ceil (const T1 &x, const T2 &y,
>    return quotient;
>  }
>  
> +template <typename T1, typename T2>
> +inline WI_BINARY_RESULT (T1, T2)
> +wi::udiv_ceil (const T1 &x, const T2 &y)
> +{
> +  return div_ceil (x, y, UNSIGNED);
> +}
> +
>  /* Return X / Y, rouding towards nearest with ties away from zero.
>     Treat X and Y as having the signedness given by SGN.  Indicate
>     in *OVERFLOW if the result overflows.  */