[PATCH v2] Generalize get_most_common_single_value to return k_th value & count

[PATCH v2] Generalize get_most_common_single_value to return k_th value & count

[Xiong Hu Luo]

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;
+};
+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);
-- 
2.22.0.428.g6d5b264208

Re: [PATCH v2] Generalize get_most_common_single_value to return k_th value & count

[Martin Liška]

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);
> 

Re: [PATCH v2] Generalize get_most_common_single_value to return k_th value & count

[Segher Boessenkool]

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

Re: [PATCH v2] Generalize get_most_common_single_value to return k_th value & count

[Martin Liška]

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

Re: [PATCH v2] Generalize get_most_common_single_value to return k_th value & count

[Segher Boessenkool]

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

Re: [PATCH v2] Generalize get_most_common_single_value to return k_th value & count

[Martin Liška]

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
> 

Re: [PATCH v2] Generalize get_most_common_single_value to return k_th value & count

[Segher Boessenkool]

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

Re: [PATCH v3] Generalize get_most_common_single_value to return k_th value & count

[luoxhu]

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);
-- 
2.22.0.428.g6d5b264208

Re: [PATCH v3] Generalize get_most_common_single_value to return k_th value & count

[Martin Liška]

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);

Re: [PATCH v4] Generalize get_most_common_single_value to return k_th value & count

[luoxhu]

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);
-- 
2.22.0.428.g6d5b264208

Re: [PATCH v4] Generalize get_most_common_single_value to return k_th value & count

[Martin Liška]

[-- Attachment #1: Type: text/plain, Size: 599 bytes --]

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

[-- Attachment #2: most-common-value.patch --]
[-- Type: text/x-patch, Size: 6333 bytes --]

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..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,
+     counter1> and compares counter first.  If counter is same, compares the
+     value, exchange it if small to keep stable.  */
+  for (unsigned i = 0; i < GCOV_TOPN_VALUES - 1; i++)
+    {
+      bool swapped = false;
+      for (unsigned 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;
+	    }
+	}
+
+      if (!swapped)
+	break;
+    }
+}
+
 /* Load value histograms values whose description is stored in VALUES array
    from .gcda file.  
 
@@ -808,6 +846,10 @@ 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_values (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);

Re: [PATCH v4] Generalize get_most_common_single_value to return k_th value & count

[luoxhu]

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
> 

Re: [PATCH v4] Generalize get_most_common_single_value to return k_th value & count

[Martin Liška]

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
>>
> 

Re: [PATCH v4] Generalize get_most_common_single_value to return k_th value & count

[Jeff Law]

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