From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 3881 invoked by alias); 16 Jul 2019 10:30:44 -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 3687 invoked by uid 89); 16 Jul 2019 10:30:43 -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; Tue, 16 Jul 2019 10:30:40 +0000 Received: from relay2.suse.de (unknown [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id 5DC47AEFF; Tue, 16 Jul 2019 10:30:38 +0000 (UTC) Subject: Re: [PATCH v3] Generalize get_most_common_single_value to return k_th value & count To: luoxhu , 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> <622d5e32-f430-2b07-2902-463f8770e984@suse.cz> From: =?UTF-8?Q?Martin_Li=c5=a1ka?= Message-ID: <7e334738-324f-1e0d-b368-ac4ce1d9869c@suse.cz> Date: Tue, 16 Jul 2019 10:34: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: Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-IsSubscribed: yes X-SW-Source: 2019-07/txt/msg01104.txt.bz2 On 7/16/19 8:53 AM, luoxhu wrote: > Currently get_most_common_single_value could only return the max hist > , 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  > >     * 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 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);