From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 73965 invoked by alias); 15 Jul 2019 09:20:38 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 73955 invoked by uid 89); 15 Jul 2019 09:20:38 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-17.2 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,SPF_PASS autolearn=ham version=3.3.1 spammy= X-HELO: mx1.suse.de Received: from mx2.suse.de (HELO mx1.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 15 Jul 2019 09:20:37 +0000 Received: from relay2.suse.de (unknown [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id B5CE0AFCC; Mon, 15 Jul 2019 09:20:34 +0000 (UTC) Subject: Re: [PATCH v2] Generalize get_most_common_single_value to return k_th value & count To: Xiong Hu Luo , gcc-patches@gcc.gnu.org Cc: hubicka@ucw.cz, segher@kernel.crashing.org, wschmidt@linux.ibm.com References: <20190715082043.24541-1-luoxhu@linux.ibm.com> From: =?UTF-8?Q?Martin_Li=c5=a1ka?= Message-ID: <622d5e32-f430-2b07-2902-463f8770e984@suse.cz> Date: Mon, 15 Jul 2019 10:36:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.7.2 MIME-Version: 1.0 In-Reply-To: <20190715082043.24541-1-luoxhu@linux.ibm.com> Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-IsSubscribed: yes X-SW-Source: 2019-07/txt/msg01053.txt.bz2 On 7/15/19 10:20 AM, Xiong Hu Luo wrote: > Currently get_most_common_single_value could only return the max hist > , add qsort to enable this function return kth value. > Rename it to get_kth_value_count. > > gcc/ChangeLog: > > 2019-07-15 Xiong Hu Luo > > * 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 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); >