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