From 982b149787057bb288caed389f231c4979e969dc Mon Sep 17 00:00:00 2001 From: Xiong Hu Luo Date: Thu, 25 Jul 2019 09:20:13 +0000 Subject: [PATCH] Generalize get_most_common_single_value to return n_th value & count Currently get_most_common_single_value could only return the max hist , 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 * 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 --- gcc/ChangeLog | 17 +++++++++++++++++ gcc/ipa-profile.c | 4 ++-- gcc/profile.c | 40 ++++++++++++++++++++++++++++++++++++++++ gcc/value-prof.c | 53 +++++++++++++++++++++++------------------------------ gcc/value-prof.h | 9 ++++----- 5 files changed, 86 insertions(+), 37 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 16757b0..ef12578 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,20 @@ +2019-07-25 Xiong Hu Luo + + * 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. + 2019-07-25 Richard Biener PR tree-optimization/91236 diff --git a/gcc/ipa-profile.c b/gcc/ipa-profile.c index 1fb939b..970dba3 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 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 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. */ diff --git a/gcc/value-prof.c b/gcc/value-prof.c index 32e6ddd..7594588 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 ca846d0..1078722 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.7.4