Re: [RFC] overflow safe scaling of 64bit values

[Richard Biener <rguenther at suse dot de>]

On Tue, 10 Oct 2017, Jan Hubicka wrote:

> Hi,
> in order to drop frequencies from basic blocks and counts from edges I need
> to make probabilities more precise (so we do not get all those roundoff errors
> from 10000-base fixpoint arithmetics).  Increasing base is easy now, but it
> means that in temporaries one can get overflows easily.
> 
> I need to compute (a*b)/c in a overflow safe way when a*b does not necessarily
> need to fit into 64bit integer.  The following implement safe_scale_64bit for
> it but I am not quite sure if that is most reasonable implementation.
> (it uses builtins to detect overflows, inline 64bit computation if it is safe
> and 128bit computation if it is not).
> 
> Any ideas for better version? If not I will go ahead with this variant and
> increase profile probability base.
> 
> Honza
> 
> 	* profile-count.h (slow_safe_scale_64bit): New function.
> 	(safe_scale_64bit): New inline.
> 	(profile_count::max_safe_multiplier): Remove; use safe_scale_64bit.
> Index: profile-count.h
> ===================================================================
> --- profile-count.h	(revision 253512)
> +++ profile-count.h	(working copy)
> @@ -43,6 +43,35 @@ enum profile_quality {
>  
>  #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
>  
> +bool slow_safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res);
> +
> +/* Compute RES=(a*b + c/2)/c capping and return false if overflow happened.  */
> +
> +inline bool
> +safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res)
> +{
> +#if (GCC_VERSION >= 5000)
> +  uint64_t tmp;
> +  if (!__builtin_mul_overflow (a, b, &tmp)
> +      && !__builtin_add_overflow (tmp, c/2, &tmp))
> +    {
> +      *res = tmp / c;
> +      return true;
> +    }
> +  if (c == 1)
> +    {
> +      *res = (uint64_t) -1;
> +      return false;
> +    }
> +#else
> +  if (a < ((uint64_t)1 << 31)
> +      && b < ((uint64_t)1 << 31)
> +      && c < ((uint64_t)1 << 31))

I think you can allow (uint64_t)1 << 32, the maximum value you'll get
is 0xffffffff then which won't overflow uint64_t.  c could be even
larger, up to (1 << 34) - 4 I think but I guess that doesn't matter.

"safe_scale_64bit" sounds a bit odd but I don't have a better one.

Richard.

> +    return (a * b + (c / 2)) / c;
> +#endif
> +  return slow_safe_scale_64bit (a, b, c, res);
> +}
> +
>  /* Data type to hold probabilities.  It implements fixed point arithmetics
>     with capping so probability is always in range [0,1] and scaling requiring
>     values greater than 1 needs to be represented otherwise.
> @@ -87,7 +116,8 @@ class GTY((user)) profile_probability
>  
>    static const int n_bits = 30;
>    static const uint32_t max_probability = REG_BR_PROB_BASE;
> -  static const uint32_t uninitialized_probability = ((uint32_t) 1 << n_bits) - 1;
> +  static const uint32_t uninitialized_probability
> +		 = ((uint32_t) 1 << (n_bits - 1)) - 1;
>  
>    uint32_t m_val : 30;
>    enum profile_quality m_quality : 2;
> @@ -535,11 +565,6 @@ class GTY(()) profile_count
>  
>    uint64_t m_val : n_bits;
>    enum profile_quality m_quality : 2;
> -
> -  /* Assume numbers smaller than this to multiply.  This is set to make
> -     testsuite pass, in future we may implement precise multiplication in higer
> -     rangers.  */
> -  static const uint64_t max_safe_multiplier = 131072;
>  public:
>  
>    /* Used for counters which are expected to be never executed.  */
> @@ -790,12 +815,9 @@ public:
>  	return *this;
>  
>        profile_count ret;
> -      /* Take care for overflows!  */
> -      if (num.m_val < max_safe_multiplier || m_val < max_safe_multiplier)
> -	ret.m_val = RDIV (m_val * num.m_val, den.m_val);
> -      else
> -	ret.m_val = RDIV (m_val * RDIV (num.m_val * max_safe_multiplier,
> -					den.m_val), max_safe_multiplier);
> +      uint64_t val;
> +      safe_scale_64bit (m_val, num.m_val, den.m_val, &val);
> +      ret.m_val = MIN (val, max_count);
>        ret.m_quality = MIN (m_quality, profile_adjusted);
>        return ret;
>      }
> Index: profile-count.c
> ===================================================================
> --- profile-count.c	(revision 253512)
> +++ profile-count.c	(working copy)
> @@ -30,6 +30,7 @@ along with GCC; see the file COPYING3.
>  #include "gimple.h"
>  #include "data-streamer.h"
>  #include "cgraph.h"
> +#include "wide-int.h"
>  
>  /* Dump THIS to F.  */
>  
> @@ -194,3 +195,21 @@ profile_probability::stream_out (struct
>    streamer_write_uhwi_stream (ob, m_val);
>    streamer_write_uhwi_stream (ob, m_quality);
>  }
> +
> +/* Compute RES=(a*b + c/2)/c capping and return false if overflow happened.  */
> +
> +bool
> +slow_safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res)
> +{
> +  FIXED_WIDE_INT (128) tmp = a;
> +  bool overflow;
> +  tmp = wi::udiv_floor (wi::umul (tmp, b, &overflow) + (c / 2), c);
> +  gcc_checking_assert (!overflow);
> +  if (wi::fits_uhwi_p (tmp))
> +    {
> +      *res = tmp.to_uhwi ();
> +      return true;
> +    }
> +  *res = (uint64_t) -1;
> +  return false;
> +}
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)