Fix profile update after vectorize loop versioning

Vectorizer while loop versioning produces a versioned loop
guarded with two conditionals of the form

  if (cond1)
    goto scalar_loop
  else
    goto next_bb
next_bb:
  if (cond2)
    godo scalar_loop
  else
    goto vector_loop

It wants the combined test to be prob (whch is set to likely)
and uses profile_probability::split to determine probability
of cond1 and cond2.

However spliting  is turning:

     if (cond)
       goto lab; // ORIG probability
 into
     if (cond1)
       goto lab; // FIRST = ORIG * CPROB probability
     if (cond2)
       goto lab; // SECOND probability

Which is or instead of and.  As a result we get pretty low probabiility
of entering vectorized loop.

The fixes this by introducing sqrt to profile probability (which is correct
way to split this) and also adding pow that is needed elsewhere.

While loop versioning I now produce code as if there was only one combined
conditional and then update probability of conditional produced (containig
cond1).  Later edge is split and new conditional is added. At that time
it is necessary to update probability of the BB containing second conditional
so everything matches.

gcc/ChangeLog:

	* profile-count.cc (profile_probability::sqrt): New member function.
	(profile_probability::pow): Likewise.
	* profile-count.h: (profile_probability::sqrt): Declare
	(profile_probability::pow): Likewise.
	* tree-vect-loop-manip.cc (vect_loop_versioning): Fix profile update.

diff --git a/gcc/profile-count.cc b/gcc/profile-count.cc
index eaf0f0d787e6abf6206d179f8c8519ae5355c2ee..e63c9432388b0c827341890632a4c87edaa04f19 100644 (file)
--- a/gcc/profile-count.cc
+++ b/gcc/profile-count.cc
@@ -471,3 +471,60 @@ profile_probability::to_sreal () const
   gcc_checking_assert (initialized_p ());
   return ((sreal)m_val) >> (n_bits - 2);
 }
+
+/* Compute square root.  */
+
+profile_probability
+profile_probability::sqrt () const
+{
+  if (!initialized_p () || *this == never () || *this == always ())
+    return *this;
+  profile_probability ret = *this;
+  ret.m_quality = MIN (ret.m_quality, ADJUSTED);
+  uint32_t min_range = m_val;
+  uint32_t max_range = max_probability;
+  if (!m_val)
+    max_range = 0;
+  if (m_val == max_probability)
+    min_range = max_probability;
+  while (min_range != max_range)
+    {
+      uint32_t val = (min_range + max_range) / 2;
+      uint32_t val2 = RDIV ((uint64_t)val * val, max_probability);
+      if (val2 == m_val)
+       min_range = max_range = m_val;
+      else if (val2 > m_val)
+       max_range = val - 1;
+      else if (val2 < m_val)
+       min_range = val + 1;
+    }
+  ret.m_val = min_range;
+  return ret;
+}
+
+/* Compute n-th power of THIS.  */
+
+profile_probability
+profile_probability::pow (int n) const
+{
+  if (n == 1 || !initialized_p ())
+    return *this;
+  if (!n)
+    return profile_probability::always ();
+  if (!nonzero_p ()
+      || !(profile_probability::always () - *this).nonzero_p ())
+    return *this;
+  profile_probability ret = profile_probability::always ();
+  profile_probability v = *this;
+  int p = 1;
+  while (true)
+    {
+      if (n & p)
+       ret = ret * v;
+      p <<= 1;
+      if (p > n)
+       break;
+      v = v * v;
+    }
+  return ret;
+}

diff --git a/gcc/profile-count.h b/gcc/profile-count.h
index 88a6431c21a02c23c9df32a12615837c32f1728e..002bcb834816e2bbd42c22fa33b50b73b4b4ea95 100644 (file)
--- a/gcc/profile-count.h
+++ b/gcc/profile-count.h
@@ -650,6 +650,12 @@ public:
       return *this;
     }
 
+  /* Compute n-th power.  */
+  profile_probability pow (int) const;
+
+  /* Compute sware root.  */
+  profile_probability sqrt () const;
+
   /* Get the value of the count.  */
   uint32_t value () const { return m_val; }
 

diff --git a/gcc/tree-vect-loop-manip.cc b/gcc/tree-vect-loop-manip.cc
index 30baac6db446a6051afbd641ef5c057e6b395655..e53a99e7c3ce58e18df594ca8893740db73b44dc 100644 (file)
--- a/gcc/tree-vect-loop-manip.cc
+++ b/gcc/tree-vect-loop-manip.cc
@@ -3784,7 +3784,7 @@ vect_loop_versioning (loop_vec_info loop_vinfo,
     }
 
   tree cost_name = NULL_TREE;
-  profile_probability prob2 = profile_probability::uninitialized ();
+  profile_probability prob2 = profile_probability::always ();
   if (cond_expr
       && EXPR_P (cond_expr)
       && (version_niter
@@ -3797,7 +3797,7 @@ vect_loop_versioning (loop_vec_info loop_vinfo,
                                                      is_gimple_val, NULL_TREE);
       /* Split prob () into two so that the overall probability of passing
         both the cost-model and versioning checks is the orig prob.  */
-      prob2 = prob.split (prob);
+      prob2 = prob = prob.sqrt ();
     }
 
   if (version_niter)
@@ -3941,7 +3941,15 @@ vect_loop_versioning (loop_vec_info loop_vinfo,
 
       initialize_original_copy_tables ();
       nloop = loop_version (loop_to_version, cond_expr, &condition_bb,
-                           prob, prob.invert (), prob, prob.invert (), true);
+                           prob * prob2, (prob * prob2).invert (),
+                           prob * prob2, (prob * prob2).invert (),
+                           true);
+      /* We will later insert second conditional so overall outcome of
+        both is prob * prob2.  */
+      edge true_e, false_e;
+      extract_true_false_edges_from_block (condition_bb, &true_e, &false_e);
+      true_e->probability = prob;
+      false_e->probability = prob.invert ();
       gcc_assert (nloop);
       nloop = get_loop_copy (loop);
 
@@ -4037,6 +4045,7 @@ vect_loop_versioning (loop_vec_info loop_vinfo,
       edge e2 = make_edge (e->src, false_e->dest, EDGE_FALSE_VALUE);
       e->probability = prob2;
       e2->probability = prob2.invert ();
+      e->dest->count = e->count ();
       set_immediate_dominator (CDI_DOMINATORS, false_e->dest, e->src);
       auto_vec<basic_block, 3> adj;
       for (basic_block son = first_dom_son (CDI_DOMINATORS, e->dest);