Increase base of profile probabilities

Increase base of profile probabilities

[Jan Hubicka]

Hi,
this patch makes profile probability use more precise representation
and takes care of places where 32bit artithmetic will possibly overflow.
This will make it possible to drop counts on edges next.

Bootstrapped/regtested x86_64-linux, comitted.

Honza

	* profile-count.c (safe_scale_64bit): Fix GCC4.x path.
	(profile_probability): Set max_probability
	to (uint32_t) 1 << (n_bits - 2) and update accessors to avoid overlfows
	in temporaries.
	* profile-count.c (profile_probability::differs_from_p): Do not
	rely on max_probaiblity == 10000

	* gcc.dg/predict-13.c: Update template for probaility change.
	* gcc.dg/predict-8.c: Likewise.
Index: profile-count.c
===================================================================
--- profile-count.c	(revision 253683)
+++ profile-count.c	(working copy)
@@ -147,12 +147,12 @@ profile_probability::differs_from_p (pro
 {
   if (!initialized_p () || !other.initialized_p ())
     return false;
-  if ((uint64_t)m_val - (uint64_t)other.m_val < 10
-      || (uint64_t)other.m_val - (uint64_t)m_val < 10)
+  if ((uint64_t)m_val - (uint64_t)other.m_val < max_probability / 1000
+      || (uint64_t)other.m_val - (uint64_t)max_probability < 1000)
     return false;
   if (!other.m_val)
     return true;
-  int64_t ratio = m_val * 100 / other.m_val;
+  int64_t ratio = (int64_t)m_val * 100 / other.m_val;
   return ratio < 99 || ratio > 101;
 }
 
Index: profile-count.h
===================================================================
--- profile-count.h	(revision 253683)
+++ profile-count.h	(working copy)
@@ -67,7 +67,10 @@ safe_scale_64bit (uint64_t a, uint64_t b
   if (a < ((uint64_t)1 << 31)
       && b < ((uint64_t)1 << 31)
       && c < ((uint64_t)1 << 31))
-    return (a * b + (c / 2)) / c;
+    {
+      *res = (a * b + (c / 2)) / c;
+      return true;
+    }
 #endif
   return slow_safe_scale_64bit (a, b, c, res);
 }
@@ -111,11 +114,10 @@ safe_scale_64bit (uint64_t a, uint64_t b
 
 class GTY((user)) profile_probability
 {
-  /* For now use values in range 0...REG_BR_PROB_BASE.  Later we can use full
-     precision of 30 bits available.  */
-
   static const int n_bits = 30;
-  static const uint32_t max_probability = REG_BR_PROB_BASE;
+  /* We can technically use ((uint32_t) 1 << (n_bits - 1)) - 2 but that
+     will lead to harder multiplication sequences.  */
+  static const uint32_t max_probability = (uint32_t) 1 << (n_bits - 2);
   static const uint32_t uninitialized_probability
 		 = ((uint32_t) 1 << (n_bits - 1)) - 1;
 
@@ -210,14 +212,14 @@ public:
     {
       profile_probability ret;
       gcc_checking_assert (v >= 0 && v <= REG_BR_PROB_BASE);
-      ret.m_val = RDIV (v * max_probability, REG_BR_PROB_BASE);
+      ret.m_val = RDIV (v * (uint64_t) max_probability, REG_BR_PROB_BASE);
       ret.m_quality = profile_guessed;
       return ret;
     }
   int to_reg_br_prob_base () const
     {
       gcc_checking_assert (initialized_p ());
-      return RDIV (m_val * REG_BR_PROB_BASE, max_probability);
+      return RDIV (m_val * (uint64_t) REG_BR_PROB_BASE, max_probability);
     }
 
   /* Conversion to and from RTL representation of profile probabilities.  */
@@ -246,7 +248,12 @@ public:
       if (val1 > val2)
 	ret.m_val = max_probability;
       else
-	ret.m_val = RDIV (val1 * max_probability, val2);
+	{
+	  uint64_t tmp;
+	  safe_scale_64bit (val1, max_probability, val2, &tmp);
+	  gcc_checking_assert (tmp <= max_probability);
+	  ret.m_val = tmp;
+	}
       ret.m_quality = profile_precise;
       return ret;
     }
@@ -443,8 +450,9 @@ public:
       if (!initialized_p ())
 	return profile_probability::uninitialized ();
       profile_probability ret;
-      ret.m_val = MIN (RDIV (m_val * num, den),
-		       max_probability);
+      uint64_t tmp;
+      safe_scale_64bit (m_val, num, den, &tmp);
+      ret.m_val = MIN (tmp, max_probability);
       ret.m_quality = MIN (m_quality, profile_adjusted);
       return ret;
     }
@@ -482,7 +490,7 @@ public:
       if (m_val == uninitialized_probability)
 	return m_quality == profile_guessed;
       else
-	return m_val <= REG_BR_PROB_BASE;
+	return m_val <= max_probability;
     }
 
   /* Comparsions are three-state and conservative.  False is returned if
@@ -781,8 +789,10 @@ public:
       if (!initialized_p ())
 	return profile_count::uninitialized ();
       profile_count ret;
-      ret.m_val = RDIV (m_val * prob.m_val,
-			profile_probability::max_probability);
+      uint64_t tmp;
+      safe_scale_64bit (m_val, prob.m_val, profile_probability::max_probability,
+			&tmp);
+      ret.m_val = tmp;
       ret.m_quality = MIN (m_quality, prob.m_quality);
       return ret;
     }
@@ -794,11 +804,11 @@ public:
       if (!initialized_p ())
 	return profile_count::uninitialized ();
       profile_count ret;
+      uint64_t tmp;
+
       gcc_checking_assert (num >= 0 && den > 0);
-      /* FIXME: shrink wrapping violates this sanity check.  */
-      gcc_checking_assert ((num <= REG_BR_PROB_BASE
-			    || den <= REG_BR_PROB_BASE) || 1);
-      ret.m_val = RDIV (m_val * num, den);
+      safe_scale_64bit (m_val, num, den, &tmp);
+      ret.m_val = MIN (tmp, max_count);
       ret.m_quality = MIN (m_quality, profile_adjusted);
       return ret;
     }
Index: testsuite/gcc.dg/predict-13.c
===================================================================
--- testsuite/gcc.dg/predict-13.c	(revision 253683)
+++ testsuite/gcc.dg/predict-13.c	(working copy)
@@ -21,4 +21,4 @@ int main(int argc, char **argv)
 }
 
 /* { dg-final { scan-tree-dump-times "combined heuristics of edge\[^:\]*: 33.3%" 3 "profile_estimate"} } */
-/* { dg-final { scan-tree-dump-times "combined heuristics of edge\[^:\]*: 0.0%" 2 "profile_estimate"} } */
+/* { dg-final { scan-tree-dump-times "combined heuristics of edge\[^:\]*: 0.1%" 2 "profile_estimate"} } */
Index: testsuite/gcc.dg/predict-8.c
===================================================================
--- testsuite/gcc.dg/predict-8.c	(revision 253683)
+++ testsuite/gcc.dg/predict-8.c	(working copy)
@@ -1,5 +1,5 @@
 /* { dg-do compile { target { i?86-*-* x86_64-*-* } } } */
-/* { dg-options "-O2 -fdump-rtl-expand" } */
+/* { dg-options "-O2 -fdump-rtl-expand-details-blocks" } */
 
 int foo(float a, float b) {
   if (a == b)
@@ -8,4 +8,4 @@ int foo(float a, float b) {
     return 2;
 }
 
-/* { dg-final { scan-rtl-dump-times "REG_BR_PROB 400 " 1 "expand"} } */
+/* { dg-final { scan-rtl-dump-times "99.0. .guessed" 1 "expand"} } */