Generalize get_most_common_single_value to return n_th value & count

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.

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.

From-SVN: r273789

1 files changed, 40 insertions, 0 deletions

diff --git a/gcc/profile.c b/gcc/profile.c
index 441cb8e..6c8127a 100644
--- a/gcc/profile.c
+++ b/gcc/profile.c
@@ -743,6 +743,42 @@ 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 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 decrease 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 +844,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.  */