From: "Martin Liška" <mliska@suse.cz>
To: luoxhu <luoxhu@linux.ibm.com>, gcc-patches@gcc.gnu.org
Cc: hubicka@ucw.cz, segher@kernel.crashing.org, wschmidt@linux.ibm.com
Subject: Re: [PATCH v3] Generalize get_most_common_single_value to return k_th value & count
Date: Tue, 16 Jul 2019 10:34:00 -0000 [thread overview]
Message-ID: <7e334738-324f-1e0d-b368-ac4ce1d9869c@suse.cz> (raw)
In-Reply-To: <c7761de9-d252-525c-c1d1-bdcbcacac59a@linux.ibm.com>
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);
next prev parent reply other threads:[~2019-07-16 10:30 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-07-15 8:50 [PATCH v2] " Xiong Hu Luo
2019-07-15 10:36 ` Martin Liška
2019-07-15 14:23 ` Segher Boessenkool
2019-07-15 14:31 ` Martin Liška
2019-07-15 14:41 ` Segher Boessenkool
2019-07-15 14:44 ` Martin Liška
2019-07-15 15:28 ` Segher Boessenkool
2019-07-16 7:42 ` [PATCH v3] " luoxhu
2019-07-16 10:34 ` Martin Liška [this message]
2019-07-17 6:02 ` [PATCH v4] " luoxhu
2019-07-17 8:05 ` Martin Liška
2019-07-17 8:46 ` luoxhu
2019-07-17 9:23 ` Martin Liška
2019-07-24 18:57 ` Jeff Law
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=7e334738-324f-1e0d-b368-ac4ce1d9869c@suse.cz \
--to=mliska@suse.cz \
--cc=gcc-patches@gcc.gnu.org \
--cc=hubicka@ucw.cz \
--cc=luoxhu@linux.ibm.com \
--cc=segher@kernel.crashing.org \
--cc=wschmidt@linux.ibm.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).