This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH v2] Generalize get_most_common_single_value to return k_th value & count
- From: Martin Liška <mliska at suse dot cz>
- To: Xiong Hu Luo <luoxhu at linux dot ibm dot com>, gcc-patches at gcc dot gnu dot org
- Cc: hubicka at ucw dot cz, segher at kernel dot crashing dot org, wschmidt at linux dot ibm dot com
- Date: Mon, 15 Jul 2019 11:20:34 +0200
- Subject: Re: [PATCH v2] Generalize get_most_common_single_value to return k_th value & count
- References: <20190715082043.24541-1-luoxhu@linux.ibm.com>
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);
>