diff mbox series

[v2] Generalize get_most_common_single_value to return k_th value & count

Message ID 20190715082043.24541-1-luoxhu@linux.ibm.com
State New
Headers show
Series [v2] Generalize get_most_common_single_value to return k_th value & count | expand

Commit Message

Xionghu Luo July 15, 2019, 8:20 a.m. UTC 
Currently get_most_common_single_value could only return the max hist
<value, count>, add qsort to enable this function return kth value.
Rename it to get_kth_value_count.

gcc/ChangeLog:

	2019-07-15  Xiong Hu Luo  <luoxhu@linux.ibm.com>

	* ipa-profile.c (get_most_common_single_value): Use
	get_kth_value_count.
	* value-prof.c (struct value_count_t): New struct.
	(cmp_counts): New function.
	(get_most_common_single_value): Rename to ...
	get_kth_value_count.  Add input params k, return
	the k_th value and count.
	(gimple_divmod_fixed_value_transform): Use get_kth_value_count.
	(gimple_ic_transform): Likewise.
	(gimple_stringops_transform): Likewise.
	* value-prof.h (get_most_common_single_value): Add input params
	k, default to 0.
---
 gcc/ipa-profile.c |  4 +--
 gcc/value-prof.c  | 66 +++++++++++++++++++++++++++++++++--------------
 gcc/value-prof.h  |  8 +++---
 3 files changed, 52 insertions(+), 26 deletions(-)

Comments

Martin Liška July 15, 2019, 9:20 a.m. UTC | #1 
On 7/15/19 10:20 AM, Xiong Hu Luo wrote:
> Currently get_most_common_single_value could only return the max hist
> <value, count>, add qsort to enable this function return kth value.
> Rename it to get_kth_value_count.
> 
> gcc/ChangeLog:
> 
> 	2019-07-15  Xiong Hu Luo  <luoxhu@linux.ibm.com>
> 
> 	* ipa-profile.c (get_most_common_single_value): Use
> 	get_kth_value_count.
> 	* value-prof.c (struct value_count_t): New struct.
> 	(cmp_counts): New function.
> 	(get_most_common_single_value): Rename to ...
> 	get_kth_value_count.  Add input params k, return
> 	the k_th value and count.
> 	(gimple_divmod_fixed_value_transform): Use get_kth_value_count.
> 	(gimple_ic_transform): Likewise.
> 	(gimple_stringops_transform): Likewise.
> 	* value-prof.h (get_most_common_single_value): Add input params
> 	k, default to 0.
> ---
>  gcc/ipa-profile.c |  4 +--
>  gcc/value-prof.c  | 66 +++++++++++++++++++++++++++++++++--------------
>  gcc/value-prof.h  |  8 +++---
>  3 files changed, 52 insertions(+), 26 deletions(-)
> 
> diff --git a/gcc/ipa-profile.c b/gcc/ipa-profile.c
> index 1fb939b73d0..37a004c4ce4 100644
> --- a/gcc/ipa-profile.c
> +++ b/gcc/ipa-profile.c
> @@ -192,8 +192,8 @@ ipa_profile_generate_summary (void)
>  		  if (h)
>  		    {
>  		      gcov_type val, count, all;
> -		      if (get_most_common_single_value (NULL, "indirect call",
> -							h, &val, &count, &all))
> +		      if (get_kth_value_count (NULL, "indirect call", h, &val,
> +					       &count, &all))
>  			{
>  			  struct cgraph_edge * e = node->get_edge (stmt);
>  			  if (e && !e->indirect_unknown_callee)
> diff --git a/gcc/value-prof.c b/gcc/value-prof.c
> index 32e6ddd8165..9b7fb52dcd2 100644
> --- a/gcc/value-prof.c
> +++ b/gcc/value-prof.c
> @@ -713,19 +713,42 @@ gimple_divmod_fixed_value (gassign *stmt, tree value, profile_probability prob,
>    return tmp2;
>  }
>  
> -/* Return most common value of TOPN_VALUE histogram.  If
> -   there's a unique value, return true and set VALUE and COUNT
> +struct value_count_t {
> +  gcov_type value;
> +  gcov_type count;
> +};

I like introduction of the tuple, please fix GNU coding style: '{' shoud
be on the next line.

> +typedef struct value_count_t *value_count;
> +typedef const struct value_count_t *const_value_count;

We use C++, please do not come up with these defines.

> +
> +static int
> +cmp_counts (const void *v1, const void *v2)
> +{
> +  const_value_count h1 = (const_value_count) v1;
> +  const_value_count h2 = (const_value_count) v2;
> +  if (h1->count < h2->count)
> +    return 1;
> +  if (h1->count > h2->count)
> +    return -1;
> +  return 0;
> +}

In order to provide stable results, we want secondary comparison based on 'value'.

> +
> +/* Return the k-th value count of TOPN_VALUE histogram.  If
> +   there's a value, return true and set VALUE and COUNT
>     arguments.  */
>  
>  bool
> -get_most_common_single_value (gimple *stmt, const char *counter_type,
> -			      histogram_value hist,
> -			      gcov_type *value, gcov_type *count,
> -			      gcov_type *all)
> +get_kth_value_count (gimple *stmt, const char *counter_type,
> +		     histogram_value hist, gcov_type *value, gcov_type *count,
> +		     gcov_type *all, unsigned k)
>  {
> +  auto_vec<struct value_count_t, 4> value_vec;

Please replace '4' with GCOV_TOPN_VALUES.

> +  struct value_count_t temp;
> +
>    if (hist->hvalue.counters[2] == -1)
>      return false;
>  
> +  gcc_assert (k < GCOV_TOPN_VALUES);
> +
>    *count = 0;
>    *value = 0;
>  
> @@ -743,14 +766,21 @@ get_most_common_single_value (gimple *stmt, const char *counter_type,
>  
>        *all = read_all;
>  
> -      if (c > *count)
> -	{
> -	  *value = v;
> -	  *count = c;
> -	}
> -      else if (c == *count && v > *value)
> -	*value = v;
> +     temp.value = v;
> +     temp.count = c;
> +
> +     value_vec.safe_push (temp);
> +    }
> +
> +  value_vec.qsort (cmp_counts);

I don't like sorting that all the time. Please sort the values once when we load it from disk.

About the name, I would prefer:
get_nth_most_common_value instead.

Thanks,
Martin

> +
> +  if (k < value_vec.length ())
> +    {
> +      *value = value_vec[k].value;
> +      *count = value_vec[k].count;
>      }
> +  else
> +    return false;
>  
>    return true;
>  }
> @@ -784,8 +814,7 @@ gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si)
>    if (!histogram)
>      return false;
>  
> -  if (!get_most_common_single_value (stmt, "divmod", histogram, &val, &count,
> -				     &all))
> +  if (!get_kth_value_count (stmt, "divmod", histogram, &val, &count, &all))
>      return false;
>  
>    value = histogram->hvalue.value;
> @@ -1439,8 +1468,8 @@ gimple_ic_transform (gimple_stmt_iterator *gsi)
>    if (!histogram)
>      return false;
>  
> -  if (!get_most_common_single_value (NULL, "indirect call", histogram, &val,
> -				     &count, &all))
> +  if (!get_kth_value_count (NULL, "indirect call", histogram, &val, &count,
> +			    &all))
>      return false;
>  
>    if (4 * count <= 3 * all)
> @@ -1658,8 +1687,7 @@ gimple_stringops_transform (gimple_stmt_iterator *gsi)
>    if (!histogram)
>      return false;
>  
> -  if (!get_most_common_single_value (stmt, "stringops", histogram, &val,
> -				     &count, &all))
> +  if (!get_kth_value_count (stmt, "stringops", histogram, &val, &count, &all))
>      return false;
>  
>    gimple_remove_histogram_value (cfun, stmt, histogram);
> diff --git a/gcc/value-prof.h b/gcc/value-prof.h
> index ca846d08cbd..228bd0f2f70 100644
> --- a/gcc/value-prof.h
> +++ b/gcc/value-prof.h
> @@ -89,11 +89,9 @@ void free_histograms (function *);
>  void stringop_block_profile (gimple *, unsigned int *, HOST_WIDE_INT *);
>  gcall *gimple_ic (gcall *, struct cgraph_node *, profile_probability);
>  bool check_ic_target (gcall *, struct cgraph_node *);
> -bool get_most_common_single_value (gimple *stmt, const char *counter_type,
> -				   histogram_value hist,
> -				   gcov_type *value, gcov_type *count,
> -				   gcov_type *all);
> -
> +bool get_kth_value_count (gimple *stmt, const char *counter_type,
> +			  histogram_value hist, gcov_type *value,
> +			  gcov_type *count, gcov_type *all, unsigned k = 0);
>  
>  /* In tree-profile.c.  */
>  extern void gimple_init_gcov_profiler (void);
>
Segher Boessenkool July 15, 2019, 2:17 p.m. UTC | #2 
On Mon, Jul 15, 2019 at 11:20:34AM +0200, Martin Liška wrote:
> On 7/15/19 10:20 AM, Xiong Hu Luo wrote:
> > -/* Return most common value of TOPN_VALUE histogram.  If
> > -   there's a unique value, return true and set VALUE and COUNT
> > +struct value_count_t {
> > +  gcov_type value;
> > +  gcov_type count;
> > +};
> 
> I like introduction of the tuple, please fix GNU coding style: '{' shoud
> be on the next line.

Only in function definitions.

> > +static int
> > +cmp_counts (const void *v1, const void *v2)
> > +{
> > +  const_value_count h1 = (const_value_count) v1;
> > +  const_value_count h2 = (const_value_count) v2;
> > +  if (h1->count < h2->count)
> > +    return 1;
> > +  if (h1->count > h2->count)
> > +    return -1;
> > +  return 0;
> > +}
> 
> In order to provide stable results, we want secondary comparison based on 'value'.

Is that enough?  Can there be two entries with the same count as well
as value?


Segher
Martin Liška July 15, 2019, 2:23 p.m. UTC | #3 
On 7/15/19 4:17 PM, Segher Boessenkool wrote:
> Is that enough?  Can there be two entries with the same count as well
> as value?

Yes, it can happen very unlikely in a multi-threaded instrumentation,
but it will not make a problem.

Martin
Segher Boessenkool July 15, 2019, 2:31 p.m. UTC | #4 
On Mon, Jul 15, 2019 at 04:23:18PM +0200, Martin Liška wrote:
> On 7/15/19 4:17 PM, Segher Boessenkool wrote:
> > Is that enough?  Can there be two entries with the same count as well
> > as value?
> 
> Yes, it can happen very unlikely in a multi-threaded instrumentation,
> but it will not make a problem.

It will result in different sort order on different hosts, then.  Is
that okay here?  Does a different order here not lead to different
compiler output?

(Consider the case where you copied the data files between hosts).


Segher
Martin Liška July 15, 2019, 2:41 p.m. UTC | #5 
On 7/15/19 4:31 PM, Segher Boessenkool wrote:
> On Mon, Jul 15, 2019 at 04:23:18PM +0200, Martin Liška wrote:
>> On 7/15/19 4:17 PM, Segher Boessenkool wrote:
>>> Is that enough?  Can there be two entries with the same count as well
>>> as value?
>>
>> Yes, it can happen very unlikely in a multi-threaded instrumentation,
>> but it will not make a problem.
> 
> It will result in different sort order on different hosts, then.  Is
> that okay here?  Does a different order here not lead to different
> compiler output?

The memory layout of the {value, count} tuple can be different. But the
function will return you K-th most common value. And that will return the same.

Martin

> 
> (Consider the case where you copied the data files between hosts).
> 
> 
> Segher
>
Segher Boessenkool July 15, 2019, 2:51 p.m. UTC | #6 
On Mon, Jul 15, 2019 at 04:41:28PM +0200, Martin Liška wrote:
> On 7/15/19 4:31 PM, Segher Boessenkool wrote:
> > On Mon, Jul 15, 2019 at 04:23:18PM +0200, Martin Liška wrote:
> >> On 7/15/19 4:17 PM, Segher Boessenkool wrote:
> >>> Is that enough?  Can there be two entries with the same count as well
> >>> as value?
> >>
> >> Yes, it can happen very unlikely in a multi-threaded instrumentation,
> >> but it will not make a problem.
> > 
> > It will result in different sort order on different hosts, then.  Is
> > that okay here?  Does a different order here not lead to different
> > compiler output?
> 
> The memory layout of the {value, count} tuple can be different. But the
> function will return you K-th most common value. And that will return the same.

Ah okay, we only look at the value later.  This should be documented I
think (just in the comparison routine is fine).


Segher
Xionghu Luo July 16, 2019, 6:53 a.m. UTC | #7 
Currently get_most_common_single_value could only return the max hist
<value, count>, add qsort to enable this function return nth value.
Rename it to get_nth_most_common_value.

v3 Changes:
  1. Move sort to profile.c after loading values from disk.  Simplify
     get_nth_most_common_value.
  2. Make qsort stable with value check if count is same.
  3. Other comments from v2.

gcc/ChangeLog:

	2019-07-15  Xiong Hu Luo  <luoxhu@linux.ibm.com>

	* ipa-profile.c (get_most_common_single_value): Use
	get_nth_most_common_value.
	* profile.c (struct value_count_t): New struct.
	(cmp_counts): New function.
	(sort_hist_value): New function.
	(compute_value_histograms): Call sort_hist_value to sort the
	values after loading from disk.
	* value-prof.c (get_most_common_single_value): Rename to ...
	get_nth_most_common_value.  Add input params n, return
	the n_th value and count.
	(gimple_divmod_fixed_value_transform): Use
	get_nth_most_common_value.
	(gimple_ic_transform): Likewise.
	(gimple_stringops_transform): Likewise.
	* value-prof.h (get_most_common_single_value): Add input params
	n, default to 0.
---
  gcc/ipa-profile.c |  4 +--
  gcc/profile.c     | 74 +++++++++++++++++++++++++++++++++++++++++++++++
  gcc/value-prof.c  | 53 +++++++++++++++------------------
  gcc/value-prof.h  |  9 +++---
  4 files changed, 103 insertions(+), 37 deletions(-)

diff --git a/gcc/ipa-profile.c b/gcc/ipa-profile.c
index 1fb939b73d0..970dba39c80 100644
--- a/gcc/ipa-profile.c
+++ b/gcc/ipa-profile.c
@@ -192,8 +192,8 @@ ipa_profile_generate_summary (void)
  		  if (h)
  		    {
  		      gcov_type val, count, all;
-		      if (get_most_common_single_value (NULL, "indirect call",
-							h, &val, &count, &all))
+		      if (get_nth_most_common_value (NULL, "indirect call", h,
+						     &val, &count, &all))
  			{
  			  struct cgraph_edge * e = node->get_edge (stmt);
  			  if (e && !e->indirect_unknown_callee)
diff --git a/gcc/profile.c b/gcc/profile.c
index 441cb8eb183..54780b44859 100644
--- a/gcc/profile.c
+++ b/gcc/profile.c
@@ -743,6 +743,74 @@ compute_branch_probabilities (unsigned cfg_checksum, 
unsigned lineno_checksum)
    free_aux_for_blocks ();
  }

+struct value_count_t
+{
+  gcov_type value;
+  gcov_type count;
+};
+
+static int
+cmp_counts (const void *v1, const void *v2)
+{
+  const value_count_t *h1 = (const value_count_t *) v1;
+  const value_count_t *h2 = (const value_count_t *) v2;
+  if (h1->count < h2->count)
+    return 1;
+  if (h1->count > h2->count)
+    return -1;
+  if (h1->count == h2->count)
+    {
+      if (h1->value < h2->value)
+	return 1;
+      if (h1->value > h2->value)
+	return -1;
+    }
+  /* There may be two entries with same count as well as value very unlikely
+     in a multi-threaded instrumentation.  But the memory layout of the 
{value,
+     count} tuple can be different.  The function will return K-th most
+     common value.  */
+  return 0;
+}
+
+/* Sort the histogram value and count for TOPN and INDIR_CALL type.  */
+
+static bool
+sort_hist_value (histogram_value hist)
+{
+  auto_vec<struct value_count_t, GCOV_TOPN_VALUES> value_vec;
+  struct value_count_t temp;
+  unsigned i;
+
+  if (hist->hvalue.counters[2] == -1)
+    return false;
+
+  gcc_assert (hist->type == HIST_TYPE_TOPN_VALUES
+	      || hist->type == HIST_TYPE_INDIR_CALL);
+
+  gcc_assert (hist->n_counters == GCOV_TOPN_VALUES_COUNTERS);
+
+  for (i = 0; i < GCOV_TOPN_VALUES; i++)
+    {
+      gcov_type v = hist->hvalue.counters[2 * i + 1];
+      gcov_type c = hist->hvalue.counters[2 * i + 2];
+
+      temp.value = v;
+      temp.count = c;
+
+      value_vec.safe_push (temp);
+    }
+
+  value_vec.qsort (cmp_counts);
+
+  gcc_assert (value_vec.length () == GCOV_TOPN_VALUES);
+
+  for (i = 0; i < GCOV_TOPN_VALUES; i++)
+    {
+      hist->hvalue.counters[2 * i + 1] = value_vec[i].value;
+      hist->hvalue.counters[2 * i + 2] = value_vec[i].count;
+    }
+  return true;
+}
  /* Load value histograms values whose description is stored in VALUES array
     from .gcda file.

@@ -808,6 +876,12 @@ compute_value_histograms (histogram_values values, 
unsigned cfg_checksum,
          else
            hist->hvalue.counters[j] = 0;

+      if (hist->type == HIST_TYPE_TOPN_VALUES
+	  || hist->type == HIST_TYPE_INDIR_CALL)
+	{
+	  sort_hist_value (hist);
+	}
+
        /* Time profiler counter is not related to any statement,
           so that we have to read the counter and set the value to
           the corresponding call graph node.  */
diff --git a/gcc/value-prof.c b/gcc/value-prof.c
index 32e6ddd8165..97e4ae18ba3 100644
--- a/gcc/value-prof.c
+++ b/gcc/value-prof.c
@@ -713,45 +713,38 @@ gimple_divmod_fixed_value (gassign *stmt, tree value, 
profile_probability prob,
    return tmp2;
  }

-/* Return most common value of TOPN_VALUE histogram.  If
-   there's a unique value, return true and set VALUE and COUNT
+/* Return the n-th value count of TOPN_VALUE histogram.  If
+   there's a value, return true and set VALUE and COUNT
     arguments.  */

  bool
-get_most_common_single_value (gimple *stmt, const char *counter_type,
-			      histogram_value hist,
-			      gcov_type *value, gcov_type *count,
-			      gcov_type *all)
+get_nth_most_common_value (gimple *stmt, const char *counter_type,
+			   histogram_value hist, gcov_type *value,
+			   gcov_type *count, gcov_type *all, unsigned n)
  {
    if (hist->hvalue.counters[2] == -1)
      return false;

+  gcc_assert (n < GCOV_TOPN_VALUES);
+
    *count = 0;
    *value = 0;

    gcov_type read_all = hist->hvalue.counters[0];

-  for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
-    {
-      gcov_type v = hist->hvalue.counters[2 * i + 1];
-      gcov_type c = hist->hvalue.counters[2 * i + 2];
-
-      /* Indirect calls can't be vereified.  */
-      if (stmt && check_counter (stmt, counter_type, &c, &read_all,
-				 gimple_bb (stmt)->count))
-	return false;
+  gcov_type v = hist->hvalue.counters[2 * n + 1];
+  gcov_type c = hist->hvalue.counters[2 * n + 2];

-      *all = read_all;
+  /* Indirect calls can't be vereified.  */
+  if (stmt
+      && check_counter (stmt, counter_type, &c, &read_all,
+			gimple_bb (stmt)->count))
+    return false;

-      if (c > *count)
-	{
-	  *value = v;
-	  *count = c;
-	}
-      else if (c == *count && v > *value)
-	*value = v;
-    }
+  *all = read_all;

+  *value = v;
+  *count = c;
    return true;
  }

@@ -784,8 +777,8 @@ gimple_divmod_fixed_value_transform 
(gimple_stmt_iterator *si)
    if (!histogram)
      return false;

-  if (!get_most_common_single_value (stmt, "divmod", histogram, &val, &count,
-				     &all))
+  if (!get_nth_most_common_value (stmt, "divmod", histogram, &val, &count,
+				  &all))
      return false;

    value = histogram->hvalue.value;
@@ -1439,8 +1432,8 @@ gimple_ic_transform (gimple_stmt_iterator *gsi)
    if (!histogram)
      return false;

-  if (!get_most_common_single_value (NULL, "indirect call", histogram, &val,
-				     &count, &all))
+  if (!get_nth_most_common_value (NULL, "indirect call", histogram, &val,
+				  &count, &all))
      return false;

    if (4 * count <= 3 * all)
@@ -1658,8 +1651,8 @@ gimple_stringops_transform (gimple_stmt_iterator *gsi)
    if (!histogram)
      return false;

-  if (!get_most_common_single_value (stmt, "stringops", histogram, &val,
-				     &count, &all))
+  if (!get_nth_most_common_value (stmt, "stringops", histogram, &val, &count,
+				  &all))
      return false;

    gimple_remove_histogram_value (cfun, stmt, histogram);
diff --git a/gcc/value-prof.h b/gcc/value-prof.h
index ca846d08cbd..1078722163b 100644
--- a/gcc/value-prof.h
+++ b/gcc/value-prof.h
@@ -89,11 +89,10 @@ void free_histograms (function *);
  void stringop_block_profile (gimple *, unsigned int *, HOST_WIDE_INT *);
  gcall *gimple_ic (gcall *, struct cgraph_node *, profile_probability);
  bool check_ic_target (gcall *, struct cgraph_node *);
-bool get_most_common_single_value (gimple *stmt, const char *counter_type,
-				   histogram_value hist,
-				   gcov_type *value, gcov_type *count,
-				   gcov_type *all);
-
+bool get_nth_most_common_value (gimple *stmt, const char *counter_type,
+				histogram_value hist, gcov_type *value,
+				gcov_type *count, gcov_type *all,
+				unsigned n = 0);

  /* In tree-profile.c.  */
  extern void gimple_init_gcov_profiler (void);
Martin Liška July 16, 2019, 10:30 a.m. UTC | #8 
On 7/16/19 8:53 AM, luoxhu wrote:
> Currently get_most_common_single_value could only return the max hist
> <value, count>, add qsort to enable this function return nth value.
> Rename it to get_nth_most_common_value.
> 
> v3 Changes:
>  1. Move sort to profile.c after loading values from disk.  Simplify
>     get_nth_most_common_value.
>  2. Make qsort stable with value check if count is same.
>  3. Other comments from v2.

Hi.

Thank you for the updated patch. But you are probably using a line wrapping
in your email client and I can't apply the patch. 

> 
> gcc/ChangeLog:
> 
>     2019-07-15  Xiong Hu Luo  <luoxhu@linux.ibm.com>
> 
>     * ipa-profile.c (get_most_common_single_value): Use
>     get_nth_most_common_value.
>     * profile.c (struct value_count_t): New struct.
>     (cmp_counts): New function.
>     (sort_hist_value): New function.
>     (compute_value_histograms): Call sort_hist_value to sort the
>     values after loading from disk.
>     * value-prof.c (get_most_common_single_value): Rename to ...
>     get_nth_most_common_value.  Add input params n, return
>     the n_th value and count.
>     (gimple_divmod_fixed_value_transform): Use
>     get_nth_most_common_value.
>     (gimple_ic_transform): Likewise.
>     (gimple_stringops_transform): Likewise.
>     * value-prof.h (get_most_common_single_value): Add input params
>     n, default to 0.
> ---
>  gcc/ipa-profile.c |  4 +--
>  gcc/profile.c     | 74 +++++++++++++++++++++++++++++++++++++++++++++++
>  gcc/value-prof.c  | 53 +++++++++++++++------------------
>  gcc/value-prof.h  |  9 +++---
>  4 files changed, 103 insertions(+), 37 deletions(-)
> 
> diff --git a/gcc/ipa-profile.c b/gcc/ipa-profile.c
> index 1fb939b73d0..970dba39c80 100644
> --- a/gcc/ipa-profile.c
> +++ b/gcc/ipa-profile.c
> @@ -192,8 +192,8 @@ ipa_profile_generate_summary (void)
>            if (h)
>              {
>                gcov_type val, count, all;
> -              if (get_most_common_single_value (NULL, "indirect call",
> -                            h, &val, &count, &all))
> +              if (get_nth_most_common_value (NULL, "indirect call", h,
> +                             &val, &count, &all))
>              {
>                struct cgraph_edge * e = node->get_edge (stmt);
>                if (e && !e->indirect_unknown_callee)
> diff --git a/gcc/profile.c b/gcc/profile.c
> index 441cb8eb183..54780b44859 100644
> --- a/gcc/profile.c
> +++ b/gcc/profile.c
> @@ -743,6 +743,74 @@ compute_branch_probabilities (unsigned cfg_checksum, unsigned lineno_checksum)
>    free_aux_for_blocks ();
>  }
> 
> +struct value_count_t
> +{
> +  gcov_type value;
> +  gcov_type count;
> +};
> +

Please make a brief comment here.

> +static int
> +cmp_counts (const void *v1, const void *v2)
> +{
> +  const value_count_t *h1 = (const value_count_t *) v1;
> +  const value_count_t *h2 = (const value_count_t *) v2;
> +  if (h1->count < h2->count)
> +    return 1;
> +  if (h1->count > h2->count)
> +    return -1;
> +  if (h1->count == h2->count)
> +    {
> +      if (h1->value < h2->value)
> +    return 1;
> +      if (h1->value > h2->value)
> +    return -1;
> +    }

What about something easier like:
return (h1->count != h2->count ? h2->count - h1->count : h2->value - h1->value) ?

> +  /* There may be two entries with same count as well as value very unlikely
> +     in a multi-threaded instrumentation.  But the memory layout of the {value,
> +     count} tuple can be different.  The function will return K-th most
> +     common value.  */
> +  return 0;
> +}
> +
> +/* Sort the histogram value and count for TOPN and INDIR_CALL type.  */
> +
> +static bool
> +sort_hist_value (histogram_value hist)
> +{
> +  auto_vec<struct value_count_t, GCOV_TOPN_VALUES> value_vec;
> +  struct value_count_t temp;
> +  unsigned i;
> +
> +  if (hist->hvalue.counters[2] == -1)
> +    return false;
> +
> +  gcc_assert (hist->type == HIST_TYPE_TOPN_VALUES
> +          || hist->type == HIST_TYPE_INDIR_CALL);
> +
> +  gcc_assert (hist->n_counters == GCOV_TOPN_VALUES_COUNTERS);
> +
> +  for (i = 0; i < GCOV_TOPN_VALUES; i++)
> +    {
> +      gcov_type v = hist->hvalue.counters[2 * i + 1];
> +      gcov_type c = hist->hvalue.counters[2 * i + 2];
> +
> +      temp.value = v;
> +      temp.count = c;
> +
> +      value_vec.safe_push (temp);
> +    }
> +
> +  value_vec.qsort (cmp_counts);
> +
> +  gcc_assert (value_vec.length () == GCOV_TOPN_VALUES);
> +
> +  for (i = 0; i < GCOV_TOPN_VALUES; i++)
> +    {
> +      hist->hvalue.counters[2 * i + 1] = value_vec[i].value;
> +      hist->hvalue.counters[2 * i + 2] = value_vec[i].count;
> +    }
> +  return true;
> +}

Well, to be honest I don't like so much manipulation for sorting of 4 values.
Please implement a simple bubble sort which will do sorting in place and
will finish as soon as the sequence is sorted. Using qsort is overkill
in my opinion.

Thanks,
Martin

>  /* Load value histograms values whose description is stored in VALUES array
>     from .gcda file.
> 
> @@ -808,6 +876,12 @@ compute_value_histograms (histogram_values values, unsigned cfg_checksum,
>          else
>            hist->hvalue.counters[j] = 0;
> 
> +      if (hist->type == HIST_TYPE_TOPN_VALUES
> +      || hist->type == HIST_TYPE_INDIR_CALL)
> +    {
> +      sort_hist_value (hist);
> +    }
> +
>        /* Time profiler counter is not related to any statement,
>           so that we have to read the counter and set the value to
>           the corresponding call graph node.  */
> diff --git a/gcc/value-prof.c b/gcc/value-prof.c
> index 32e6ddd8165..97e4ae18ba3 100644
> --- a/gcc/value-prof.c
> +++ b/gcc/value-prof.c
> @@ -713,45 +713,38 @@ gimple_divmod_fixed_value (gassign *stmt, tree value, profile_probability prob,
>    return tmp2;
>  }
> 
> -/* Return most common value of TOPN_VALUE histogram.  If
> -   there's a unique value, return true and set VALUE and COUNT
> +/* Return the n-th value count of TOPN_VALUE histogram.  If
> +   there's a value, return true and set VALUE and COUNT
>     arguments.  */
> 
>  bool
> -get_most_common_single_value (gimple *stmt, const char *counter_type,
> -                  histogram_value hist,
> -                  gcov_type *value, gcov_type *count,
> -                  gcov_type *all)
> +get_nth_most_common_value (gimple *stmt, const char *counter_type,
> +               histogram_value hist, gcov_type *value,
> +               gcov_type *count, gcov_type *all, unsigned n)
>  {
>    if (hist->hvalue.counters[2] == -1)
>      return false;
> 
> +  gcc_assert (n < GCOV_TOPN_VALUES);
> +
>    *count = 0;
>    *value = 0;
> 
>    gcov_type read_all = hist->hvalue.counters[0];
> 
> -  for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
> -    {
> -      gcov_type v = hist->hvalue.counters[2 * i + 1];
> -      gcov_type c = hist->hvalue.counters[2 * i + 2];
> -
> -      /* Indirect calls can't be vereified.  */
> -      if (stmt && check_counter (stmt, counter_type, &c, &read_all,
> -                 gimple_bb (stmt)->count))
> -    return false;
> +  gcov_type v = hist->hvalue.counters[2 * n + 1];
> +  gcov_type c = hist->hvalue.counters[2 * n + 2];
> 
> -      *all = read_all;
> +  /* Indirect calls can't be vereified.  */
> +  if (stmt
> +      && check_counter (stmt, counter_type, &c, &read_all,
> +            gimple_bb (stmt)->count))
> +    return false;
> 
> -      if (c > *count)
> -    {
> -      *value = v;
> -      *count = c;
> -    }
> -      else if (c == *count && v > *value)
> -    *value = v;
> -    }
> +  *all = read_all;
> 
> +  *value = v;
> +  *count = c;
>    return true;
>  }
> 
> @@ -784,8 +777,8 @@ gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si)
>    if (!histogram)
>      return false;
> 
> -  if (!get_most_common_single_value (stmt, "divmod", histogram, &val, &count,
> -                     &all))
> +  if (!get_nth_most_common_value (stmt, "divmod", histogram, &val, &count,
> +                  &all))
>      return false;
> 
>    value = histogram->hvalue.value;
> @@ -1439,8 +1432,8 @@ gimple_ic_transform (gimple_stmt_iterator *gsi)
>    if (!histogram)
>      return false;
> 
> -  if (!get_most_common_single_value (NULL, "indirect call", histogram, &val,
> -                     &count, &all))
> +  if (!get_nth_most_common_value (NULL, "indirect call", histogram, &val,
> +                  &count, &all))
>      return false;
> 
>    if (4 * count <= 3 * all)
> @@ -1658,8 +1651,8 @@ gimple_stringops_transform (gimple_stmt_iterator *gsi)
>    if (!histogram)
>      return false;
> 
> -  if (!get_most_common_single_value (stmt, "stringops", histogram, &val,
> -                     &count, &all))
> +  if (!get_nth_most_common_value (stmt, "stringops", histogram, &val, &count,
> +                  &all))
>      return false;
> 
>    gimple_remove_histogram_value (cfun, stmt, histogram);
> diff --git a/gcc/value-prof.h b/gcc/value-prof.h
> index ca846d08cbd..1078722163b 100644
> --- a/gcc/value-prof.h
> +++ b/gcc/value-prof.h
> @@ -89,11 +89,10 @@ void free_histograms (function *);
>  void stringop_block_profile (gimple *, unsigned int *, HOST_WIDE_INT *);
>  gcall *gimple_ic (gcall *, struct cgraph_node *, profile_probability);
>  bool check_ic_target (gcall *, struct cgraph_node *);
> -bool get_most_common_single_value (gimple *stmt, const char *counter_type,
> -                   histogram_value hist,
> -                   gcov_type *value, gcov_type *count,
> -                   gcov_type *all);
> -
> +bool get_nth_most_common_value (gimple *stmt, const char *counter_type,
> +                histogram_value hist, gcov_type *value,
> +                gcov_type *count, gcov_type *all,
> +                unsigned n = 0);
> 
>  /* In tree-profile.c.  */
>  extern void gimple_init_gcov_profiler (void);
Xionghu Luo July 17, 2019, 5:44 a.m. UTC | #9 
Currently get_most_common_single_value could only return the max hist
<value, count>, add sort after reading from disk, then it return nth value
in later use.  Rename it to get_nth_most_common_value.

Hi Martin,
Thanks for your review, v4 Changes as below:
 1. Use decrease bubble sort.
BTW, I have a question about hist->hvalue.counters[2], when will it become
 -1, please? Thanks.  Currently, if it is -1, the function will return false.

gcc/ChangeLog:

	2019-07-15  Xiong Hu Luo  <luoxhu@linux.ibm.com>

	* ipa-profile.c (get_most_common_single_value): Use
	get_nth_most_common_value.
	* profile.c (sort_hist_value): New function.
	(compute_value_histograms): Call sort_hist_value to sort the
	values after loading from disk.
	* value-prof.c (get_most_common_single_value): Rename to ...
	get_nth_most_common_value.  Add input params n, return
	the n_th value and count.
	(gimple_divmod_fixed_value_transform): Use
	get_nth_most_common_value.
	(gimple_ic_transform): Likewise.
	(gimple_stringops_transform): Likewise.
	* value-prof.h (get_most_common_single_value): Add input params
	n, default to 0.
---
 gcc/ipa-profile.c |  4 ++--
 gcc/profile.c     | 44 +++++++++++++++++++++++++++++++++++++++
 gcc/value-prof.c  | 53 ++++++++++++++++++++---------------------------
 gcc/value-prof.h  |  9 ++++----
 4 files changed, 73 insertions(+), 37 deletions(-)

diff --git a/gcc/ipa-profile.c b/gcc/ipa-profile.c
index 1fb939b73d0..970dba39c80 100644
--- a/gcc/ipa-profile.c
+++ b/gcc/ipa-profile.c
@@ -192,8 +192,8 @@ ipa_profile_generate_summary (void)
 		  if (h)
 		    {
 		      gcov_type val, count, all;
-		      if (get_most_common_single_value (NULL, "indirect call",
-							h, &val, &count, &all))
+		      if (get_nth_most_common_value (NULL, "indirect call", h,
+						     &val, &count, &all))
 			{
 			  struct cgraph_edge * e = node->get_edge (stmt);
 			  if (e && !e->indirect_unknown_callee)
diff --git a/gcc/profile.c b/gcc/profile.c
index 441cb8eb183..ae21b1192a0 100644
--- a/gcc/profile.c
+++ b/gcc/profile.c
@@ -743,6 +743,44 @@ compute_branch_probabilities (unsigned cfg_checksum, unsigned lineno_checksum)
   free_aux_for_blocks ();
 }
 
+  /* Sort the histogram value and count for TOPN and INDIR_CALL type.  */
+
+static bool
+sort_hist_value (histogram_value hist)
+{
+
+  if (hist->hvalue.counters[2] == -1)
+    return false;
+
+  gcc_assert (hist->type == HIST_TYPE_TOPN_VALUES
+	      || hist->type == HIST_TYPE_INDIR_CALL);
+
+  gcc_assert (hist->n_counters == GCOV_TOPN_VALUES_COUNTERS);
+
+  unsigned i, j;
+  bool swapped = true;
+  /* Hist value is organized as:
+     [counter0 value1 counter1 value2 counter2 value3 counter3 value4 counter4]
+     Use decrese bubble sort to rearrange it.  The sort starts from <value1,
+     counter1> and compares counter first, If counter is same, compares the
+     value, exchange it if small to keep stable.  */
+  for (i = 0; i < GCOV_TOPN_VALUES - 1 && swapped; i++)
+    {
+      swapped = false;
+      for (j = 0; j < GCOV_TOPN_VALUES - 1 - i; j++)
+	{
+	  gcov_type *p = &hist->hvalue.counters[2 * j + 1];
+	  if (p[1] < p[3] || (p[1] == p[3] && p[0] < p[2]))
+	    {
+	      std::swap (p[0], p[2]);
+	      std::swap (p[1], p[3]);
+	      swapped = true;
+	    }
+	}
+    }
+
+  return true;
+}
 /* Load value histograms values whose description is stored in VALUES array
    from .gcda file.  
 
@@ -808,6 +846,12 @@ compute_value_histograms (histogram_values values, unsigned cfg_checksum,
         else
           hist->hvalue.counters[j] = 0;
 
+      if (hist->type == HIST_TYPE_TOPN_VALUES
+	  || hist->type == HIST_TYPE_INDIR_CALL)
+	{
+	  sort_hist_value (hist);
+	}
+
       /* Time profiler counter is not related to any statement,
          so that we have to read the counter and set the value to
          the corresponding call graph node.  */
diff --git a/gcc/value-prof.c b/gcc/value-prof.c
index 32e6ddd8165..759458868a8 100644
--- a/gcc/value-prof.c
+++ b/gcc/value-prof.c
@@ -713,45 +713,38 @@ gimple_divmod_fixed_value (gassign *stmt, tree value, profile_probability prob,
   return tmp2;
 }
 
-/* Return most common value of TOPN_VALUE histogram.  If
-   there's a unique value, return true and set VALUE and COUNT
+/* Return the n-th value count of TOPN_VALUE histogram.  If
+   there's a value, return true and set VALUE and COUNT
    arguments.  */
 
 bool
-get_most_common_single_value (gimple *stmt, const char *counter_type,
-			      histogram_value hist,
-			      gcov_type *value, gcov_type *count,
-			      gcov_type *all)
+get_nth_most_common_value (gimple *stmt, const char *counter_type,
+			   histogram_value hist, gcov_type *value,
+			   gcov_type *count, gcov_type *all, unsigned n)
 {
   if (hist->hvalue.counters[2] == -1)
     return false;
 
+  gcc_assert (n < GCOV_TOPN_VALUES);
+
   *count = 0;
   *value = 0;
 
   gcov_type read_all = hist->hvalue.counters[0];
 
-  for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
-    {
-      gcov_type v = hist->hvalue.counters[2 * i + 1];
-      gcov_type c = hist->hvalue.counters[2 * i + 2];
-
-      /* Indirect calls can't be vereified.  */
-      if (stmt && check_counter (stmt, counter_type, &c, &read_all,
-				 gimple_bb (stmt)->count))
-	return false;
+  gcov_type v = hist->hvalue.counters[2 * n + 1];
+  gcov_type c = hist->hvalue.counters[2 * n + 2];
 
-      *all = read_all;
+  /* Indirect calls can't be verified.  */
+  if (stmt
+      && check_counter (stmt, counter_type, &c, &read_all,
+			gimple_bb (stmt)->count))
+    return false;
 
-      if (c > *count)
-	{
-	  *value = v;
-	  *count = c;
-	}
-      else if (c == *count && v > *value)
-	*value = v;
-    }
+  *all = read_all;
 
+  *value = v;
+  *count = c;
   return true;
 }
 
@@ -784,8 +777,8 @@ gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si)
   if (!histogram)
     return false;
 
-  if (!get_most_common_single_value (stmt, "divmod", histogram, &val, &count,
-				     &all))
+  if (!get_nth_most_common_value (stmt, "divmod", histogram, &val, &count,
+				  &all))
     return false;
 
   value = histogram->hvalue.value;
@@ -1439,8 +1432,8 @@ gimple_ic_transform (gimple_stmt_iterator *gsi)
   if (!histogram)
     return false;
 
-  if (!get_most_common_single_value (NULL, "indirect call", histogram, &val,
-				     &count, &all))
+  if (!get_nth_most_common_value (NULL, "indirect call", histogram, &val,
+				  &count, &all))
     return false;
 
   if (4 * count <= 3 * all)
@@ -1658,8 +1651,8 @@ gimple_stringops_transform (gimple_stmt_iterator *gsi)
   if (!histogram)
     return false;
 
-  if (!get_most_common_single_value (stmt, "stringops", histogram, &val,
-				     &count, &all))
+  if (!get_nth_most_common_value (stmt, "stringops", histogram, &val, &count,
+				  &all))
     return false;
 
   gimple_remove_histogram_value (cfun, stmt, histogram);
diff --git a/gcc/value-prof.h b/gcc/value-prof.h
index ca846d08cbd..1078722163b 100644
--- a/gcc/value-prof.h
+++ b/gcc/value-prof.h
@@ -89,11 +89,10 @@ void free_histograms (function *);
 void stringop_block_profile (gimple *, unsigned int *, HOST_WIDE_INT *);
 gcall *gimple_ic (gcall *, struct cgraph_node *, profile_probability);
 bool check_ic_target (gcall *, struct cgraph_node *);
-bool get_most_common_single_value (gimple *stmt, const char *counter_type,
-				   histogram_value hist,
-				   gcov_type *value, gcov_type *count,
-				   gcov_type *all);
-
+bool get_nth_most_common_value (gimple *stmt, const char *counter_type,
+				histogram_value hist, gcov_type *value,
+				gcov_type *count, gcov_type *all,
+				unsigned n = 0);
 
 /* In tree-profile.c.  */
 extern void gimple_init_gcov_profiler (void);
Martin Liška July 17, 2019, 7:55 a.m. UTC | #10 
On 7/17/19 7:44 AM, luoxhu wrote:
> Hi Martin,
> Thanks for your review, v4 Changes as below:
>  1. Use decrease bubble sort.
> BTW, I have a question about hist->hvalue.counters[2], when will it become
>  -1, please? Thanks.  Currently, if it is -1, the function will return false.

Hi.

Thanks for that. I made a minor changes to your patch, please see it in attachment.
-1 is a value that we use for invalidated histogram. That happens when you need
to fit in more values during instrumentation than you have counters in the histogram.
It helps to make reproducible builds of a software.

Martin
Xionghu Luo July 17, 2019, 8:44 a.m. UTC | #11 
Hi Martin,

On 2019/7/17 15:55, Martin Liška wrote:
> On 7/17/19 7:44 AM, luoxhu wrote:
>> Hi Martin,
>> Thanks for your review, v4 Changes as below:
>>   1. Use decrease bubble sort.
>> BTW, I have a question about hist->hvalue.counters[2], when will it become
>>   -1, please? Thanks.  Currently, if it is -1, the function will return false.
> 
> Hi.
> 
> Thanks for that. I made a minor changes to your patch, please see it in attachment.
> -1 is a value that we use for invalidated histogram. That happens when you need
> to fit in more values during instrumentation than you have counters in the histogram.
> It helps to make reproducible builds of a software.
Thanks for your patience with many tiny fixes.  I will install the updated
patch to trunk.

Xionghu

> 
> Martin
>
Martin Liška July 17, 2019, 8:46 a.m. UTC | #12 
On 7/17/19 10:44 AM, luoxhu wrote:
> Hi Martin,
> 
> On 2019/7/17 15:55, Martin Liška wrote:
>> On 7/17/19 7:44 AM, luoxhu wrote:
>>> Hi Martin,
>>> Thanks for your review, v4 Changes as below:
>>>   1. Use decrease bubble sort.
>>> BTW, I have a question about hist->hvalue.counters[2], when will it become
>>>   -1, please? Thanks.  Currently, if it is -1, the function will return false.
>>
>> Hi.
>>
>> Thanks for that. I made a minor changes to your patch, please see it in attachment.
>> -1 is a value that we use for invalidated histogram. That happens when you need
>> to fit in more values during instrumentation than you have counters in the histogram.
>> It helps to make reproducible builds of a software.
> Thanks for your patience with many tiny fixes.  I will install the updated
> patch to trunk.

Please wait for an approval of a maintainer, I'm not one of them ;)

Thanks,
Martin

> 
> Xionghu
> 
>>
>> Martin
>>
>
Jeff Law July 24, 2019, 6:56 p.m. UTC | #13 
On 7/17/19 1:55 AM, Martin Liška wrote:
> On 7/17/19 7:44 AM, luoxhu wrote:
>> Hi Martin,
>> Thanks for your review, v4 Changes as below:
>>  1. Use decrease bubble sort.
>> BTW, I have a question about hist->hvalue.counters[2], when will it become
>>  -1, please? Thanks.  Currently, if it is -1, the function will return false.
> Hi.
> 
> Thanks for that. I made a minor changes to your patch, please see it in attachment.
> -1 is a value that we use for invalidated histogram. That happens when you need
> to fit in more values during instrumentation than you have counters in the histogram.
> It helps to make reproducible builds of a software.
> 
> Martin
> 
> 
> most-common-value.patch
> 
> diff --git a/gcc/profile.c b/gcc/profile.c
> index 441cb8eb183..1151b491848 100644
> --- a/gcc/profile.c
> +++ b/gcc/profile.c
> @@ -743,6 +743,44 @@ compute_branch_probabilities (unsigned cfg_checksum, unsigned lineno_checksum)
>    free_aux_for_blocks ();
>  }
>  
> +/* Sort the histogram value and count for TOPN and INDIR_CALL types.  */
> +
> +static void
> +sort_hist_values (histogram_value hist)
> +{
> +  /* counters[2] equal to -1 means that all counters are invalidated.  */
> +  if (hist->hvalue.counters[2] == -1)
> +    return;
> +
> +  gcc_assert (hist->type == HIST_TYPE_TOPN_VALUES
> +	      || hist->type == HIST_TYPE_INDIR_CALL);
> +
> +  gcc_assert (hist->n_counters == GCOV_TOPN_VALUES_COUNTERS);
> +
> +  /* Hist value is organized as:
> +     [total_executions, value1, counter1, ..., value4, counter4]
> +     Use decrese bubble sort to rearrange it.  The sort starts from <value1,
s/decrese/decrease/


OK with that nit fixed.

jeff
diff mbox series

Patch

diff --git a/gcc/ipa-profile.c b/gcc/ipa-profile.c
index 1fb939b73d0..37a004c4ce4 100644
--- a/gcc/ipa-profile.c
+++ b/gcc/ipa-profile.c
@@ -192,8 +192,8 @@  ipa_profile_generate_summary (void)
 		  if (h)
 		    {
 		      gcov_type val, count, all;
-		      if (get_most_common_single_value (NULL, "indirect call",
-							h, &val, &count, &all))
+		      if (get_kth_value_count (NULL, "indirect call", h, &val,
+					       &count, &all))
 			{
 			  struct cgraph_edge * e = node->get_edge (stmt);
 			  if (e && !e->indirect_unknown_callee)
diff --git a/gcc/value-prof.c b/gcc/value-prof.c
index 32e6ddd8165..9b7fb52dcd2 100644
--- a/gcc/value-prof.c
+++ b/gcc/value-prof.c
@@ -713,19 +713,42 @@  gimple_divmod_fixed_value (gassign *stmt, tree value, profile_probability prob,
   return tmp2;
 }
 
-/* Return most common value of TOPN_VALUE histogram.  If
-   there's a unique value, return true and set VALUE and COUNT
+struct value_count_t {
+  gcov_type value;
+  gcov_type count;
+};
+typedef struct value_count_t *value_count;
+typedef const struct value_count_t *const_value_count;
+
+static int
+cmp_counts (const void *v1, const void *v2)
+{
+  const_value_count h1 = (const_value_count) v1;
+  const_value_count h2 = (const_value_count) v2;
+  if (h1->count < h2->count)
+    return 1;
+  if (h1->count > h2->count)
+    return -1;
+  return 0;
+}
+
+/* Return the k-th value count of TOPN_VALUE histogram.  If
+   there's a value, return true and set VALUE and COUNT
    arguments.  */
 
 bool
-get_most_common_single_value (gimple *stmt, const char *counter_type,
-			      histogram_value hist,
-			      gcov_type *value, gcov_type *count,
-			      gcov_type *all)
+get_kth_value_count (gimple *stmt, const char *counter_type,
+		     histogram_value hist, gcov_type *value, gcov_type *count,
+		     gcov_type *all, unsigned k)
 {
+  auto_vec<struct value_count_t, 4> value_vec;
+  struct value_count_t temp;
+
   if (hist->hvalue.counters[2] == -1)
     return false;
 
+  gcc_assert (k < GCOV_TOPN_VALUES);
+
   *count = 0;
   *value = 0;
 
@@ -743,14 +766,21 @@  get_most_common_single_value (gimple *stmt, const char *counter_type,
 
       *all = read_all;
 
-      if (c > *count)
-	{
-	  *value = v;
-	  *count = c;
-	}
-      else if (c == *count && v > *value)
-	*value = v;
+     temp.value = v;
+     temp.count = c;
+
+     value_vec.safe_push (temp);
+    }
+
+  value_vec.qsort (cmp_counts);
+
+  if (k < value_vec.length ())
+    {
+      *value = value_vec[k].value;
+      *count = value_vec[k].count;
     }
+  else
+    return false;
 
   return true;
 }
@@ -784,8 +814,7 @@  gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si)
   if (!histogram)
     return false;
 
-  if (!get_most_common_single_value (stmt, "divmod", histogram, &val, &count,
-				     &all))
+  if (!get_kth_value_count (stmt, "divmod", histogram, &val, &count, &all))
     return false;
 
   value = histogram->hvalue.value;
@@ -1439,8 +1468,8 @@  gimple_ic_transform (gimple_stmt_iterator *gsi)
   if (!histogram)
     return false;
 
-  if (!get_most_common_single_value (NULL, "indirect call", histogram, &val,
-				     &count, &all))
+  if (!get_kth_value_count (NULL, "indirect call", histogram, &val, &count,
+			    &all))
     return false;
 
   if (4 * count <= 3 * all)
@@ -1658,8 +1687,7 @@  gimple_stringops_transform (gimple_stmt_iterator *gsi)
   if (!histogram)
     return false;
 
-  if (!get_most_common_single_value (stmt, "stringops", histogram, &val,
-				     &count, &all))
+  if (!get_kth_value_count (stmt, "stringops", histogram, &val, &count, &all))
     return false;
 
   gimple_remove_histogram_value (cfun, stmt, histogram);
diff --git a/gcc/value-prof.h b/gcc/value-prof.h
index ca846d08cbd..228bd0f2f70 100644
--- a/gcc/value-prof.h
+++ b/gcc/value-prof.h
@@ -89,11 +89,9 @@  void free_histograms (function *);
 void stringop_block_profile (gimple *, unsigned int *, HOST_WIDE_INT *);
 gcall *gimple_ic (gcall *, struct cgraph_node *, profile_probability);
 bool check_ic_target (gcall *, struct cgraph_node *);
-bool get_most_common_single_value (gimple *stmt, const char *counter_type,
-				   histogram_value hist,
-				   gcov_type *value, gcov_type *count,
-				   gcov_type *all);
-
+bool get_kth_value_count (gimple *stmt, const char *counter_type,
+			  histogram_value hist, gcov_type *value,
+			  gcov_type *count, gcov_type *all, unsigned k = 0);
 
 /* In tree-profile.c.  */
 extern void gimple_init_gcov_profiler (void);