Patchwork Compute and emit working set information from gcov-dump (issue6940061)

login
register
mail settings
Submitter Teresa Johnson
Date Dec. 15, 2012, 2:11 a.m.
Message ID <20121215021147.58465615D9@tjsboxrox.mtv.corp.google.com>
Download mbox | patch
Permalink /patch/206601/
State New
Headers show

Comments

Teresa Johnson - Dec. 15, 2012, 2:11 a.m.
This patch enables the gcov-dump tool to optionally compute and dump
the working set information from the counter histogram, via a new -w option.
This is useful to help understand and tune how the compiler will use
the counter histogram, since it first computes the working set and selects
thresholds based on that.

This required moving the bulk of the compute_working_sets functionality
into gcov-io.c so that it was accessible by gcov-dump.c.

Bootstrapped and tested on x86_64-unknown-linux-gnu, and tested with various
gcda files. Ok for trunk?

2012-12-14  Teresa Johnson  <tejohnson@google.com>

	* lto-cgraph.c (input_symtab): Replace call to compute_working_sets
        to get_working_sets.
	* gcov-io.c (compute_working_sets): Moved most of body of old
        compute_working_sets here from profile.c.
	* gcov-io.h (NUM_GCOV_WORKING_SETS): Moved here from profile.c.
        (gcov_working_set_t): Moved typedef here from basic-block.h
        (compute_working_set): Declare.
	* profile.c (NUM_GCOV_WORKING_SETS): Moved to gcov-io.h.
	(get_working_sets): Renamed from compute_working_set,
        replace most of body with call to new compute_working_sets.
	(get_exec_counts): Replace call to compute_working_sets
        to get_working_sets.
	* profile.h (get_working_sets): Renamed from
        compute_working_set.
	* basic-block.h (gcov_working_set_t): Moved to gcov-io.h.
	* gcov-dump.c (dump_working_sets): New function.


--
This patch is available for review at http://codereview.appspot.com/6940061
Teresa Johnson - March 27, 2013, 5:47 p.m.
Ping. Thanks, Teresa

On Fri, Dec 14, 2012 at 6:11 PM, Teresa Johnson <tejohnson@google.com> wrote:
> This patch enables the gcov-dump tool to optionally compute and dump
> the working set information from the counter histogram, via a new -w option.
> This is useful to help understand and tune how the compiler will use
> the counter histogram, since it first computes the working set and selects
> thresholds based on that.
>
> This required moving the bulk of the compute_working_sets functionality
> into gcov-io.c so that it was accessible by gcov-dump.c.
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu, and tested with various
> gcda files. Ok for trunk?
>
> 2012-12-14  Teresa Johnson  <tejohnson@google.com>
>
>         * lto-cgraph.c (input_symtab): Replace call to compute_working_sets
>         to get_working_sets.
>         * gcov-io.c (compute_working_sets): Moved most of body of old
>         compute_working_sets here from profile.c.
>         * gcov-io.h (NUM_GCOV_WORKING_SETS): Moved here from profile.c.
>         (gcov_working_set_t): Moved typedef here from basic-block.h
>         (compute_working_set): Declare.
>         * profile.c (NUM_GCOV_WORKING_SETS): Moved to gcov-io.h.
>         (get_working_sets): Renamed from compute_working_set,
>         replace most of body with call to new compute_working_sets.
>         (get_exec_counts): Replace call to compute_working_sets
>         to get_working_sets.
>         * profile.h (get_working_sets): Renamed from
>         compute_working_set.
>         * basic-block.h (gcov_working_set_t): Moved to gcov-io.h.
>         * gcov-dump.c (dump_working_sets): New function.
>
> Index: lto-cgraph.c
> ===================================================================
> --- lto-cgraph.c        (revision 194502)
> +++ lto-cgraph.c        (working copy)
> @@ -1457,7 +1457,7 @@ input_symtab (void)
>      }
>
>    merge_profile_summaries (file_data_vec);
> -  compute_working_sets ();
> +  get_working_sets ();
>
>
>    /* Clear out the aux field that was used to store enough state to
> Index: gcov-io.c
> ===================================================================
> --- gcov-io.c   (revision 194502)
> +++ gcov-io.c   (working copy)
> @@ -806,3 +806,110 @@ static void gcov_histogram_merge (gcov_bucket_type
>    memcpy(tgt_histo, tmp_histo, sizeof (gcov_bucket_type) * GCOV_HISTOGRAM_SIZE);
>  }
>  #endif /* !IN_GCOV */
> +
> +/* This is used by gcov-dump (IN_GCOV == -1) and in the compiler
> +   (!IN_GCOV && !IN_LIBGCOV).  */
> +#if IN_GCOV <= 0 && !IN_LIBGCOV
> +/* Compute the working set information from the counter histogram in
> +   the profile summary. This is an array of information corresponding to a
> +   range of percentages of the total execution count (sum_all), and includes
> +   the number of counters required to cover that working set percentage and
> +   the minimum counter value in that working set.  */
> +
> +GCOV_LINKAGE void
> +compute_working_sets (const struct gcov_ctr_summary *summary,
> +                      gcov_working_set_t *gcov_working_sets)
> +{
> +  gcov_type working_set_cum_values[NUM_GCOV_WORKING_SETS];
> +  gcov_type ws_cum_hotness_incr;
> +  gcov_type cum, tmp_cum;
> +  const gcov_bucket_type *histo_bucket;
> +  unsigned ws_ix, c_num, count;
> +  int h_ix;
> +
> +  /* Compute the amount of sum_all that the cumulative hotness grows
> +     by in each successive working set entry, which depends on the
> +     number of working set entries.  */
> +  ws_cum_hotness_incr = summary->sum_all / NUM_GCOV_WORKING_SETS;
> +
> +  /* Next fill in an array of the cumulative hotness values corresponding
> +     to each working set summary entry we are going to compute below.
> +     Skip 0% statistics, which can be extrapolated from the
> +     rest of the summary data.  */
> +  cum = ws_cum_hotness_incr;
> +  for (ws_ix = 0; ws_ix < NUM_GCOV_WORKING_SETS;
> +       ws_ix++, cum += ws_cum_hotness_incr)
> +    working_set_cum_values[ws_ix] = cum;
> +  /* The last summary entry is reserved for (roughly) 99.9% of the
> +     working set. Divide by 1024 so it becomes a shift, which gives
> +     almost exactly 99.9%.  */
> +  working_set_cum_values[NUM_GCOV_WORKING_SETS-1]
> +      = summary->sum_all - summary->sum_all/1024;
> +
> +  /* Next, walk through the histogram in decending order of hotness
> +     and compute the statistics for the working set summary array.
> +     As histogram entries are accumulated, we check to see which
> +     working set entries have had their expected cum_value reached
> +     and fill them in, walking the working set entries in increasing
> +     size of cum_value.  */
> +  ws_ix = 0; /* The current entry into the working set array.  */
> +  cum = 0; /* The current accumulated counter sum.  */
> +  count = 0; /* The current accumulated count of block counters.  */
> +  for (h_ix = GCOV_HISTOGRAM_SIZE - 1;
> +       h_ix >= 0 && ws_ix < NUM_GCOV_WORKING_SETS; h_ix--)
> +    {
> +      histo_bucket = &summary->histogram[h_ix];
> +
> +      /* If we haven't reached the required cumulative counter value for
> +         the current working set percentage, simply accumulate this histogram
> +         entry into the running sums and continue to the next histogram
> +         entry.  */
> +      if (cum + histo_bucket->cum_value < working_set_cum_values[ws_ix])
> +        {
> +          cum += histo_bucket->cum_value;
> +          count += histo_bucket->num_counters;
> +          continue;
> +        }
> +
> +      /* If adding the current histogram entry's cumulative counter value
> +         causes us to exceed the current working set size, then estimate
> +         how many of this histogram entry's counter values are required to
> +         reach the working set size, and fill in working set entries
> +         as we reach their expected cumulative value.  */
> +      for (c_num = 0, tmp_cum = cum;
> +           c_num < histo_bucket->num_counters && ws_ix < NUM_GCOV_WORKING_SETS;
> +           c_num++)
> +        {
> +          count++;
> +          /* If we haven't reached the last histogram entry counter, add
> +             in the minimum value again. This will underestimate the
> +             cumulative sum so far, because many of the counter values in this
> +             entry may have been larger than the minimum. We could add in the
> +             average value every time, but that would require an expensive
> +             divide operation.  */
> +          if (c_num + 1 < histo_bucket->num_counters)
> +            tmp_cum += histo_bucket->min_value;
> +          /* If we have reached the last histogram entry counter, then add
> +             in the entire cumulative value.  */
> +          else
> +            tmp_cum = cum + histo_bucket->cum_value;
> +
> +         /* Next walk through successive working set entries and fill in
> +            the statistics for any whose size we have reached by accumulating
> +            this histogram counter.  */
> +         while (ws_ix < NUM_GCOV_WORKING_SETS
> +                && tmp_cum >= working_set_cum_values[ws_ix])
> +            {
> +              gcov_working_sets[ws_ix].num_counters = count;
> +              gcov_working_sets[ws_ix].min_counter
> +                  = histo_bucket->min_value;
> +              ws_ix++;
> +            }
> +        }
> +      /* Finally, update the running cumulative value since we were
> +         using a temporary above.  */
> +      cum += histo_bucket->cum_value;
> +    }
> +  gcc_assert (ws_ix == NUM_GCOV_WORKING_SETS);
> +}
> +#endif /* IN_GCOV <= 0 && !IN_LIBGCOV */
> Index: gcov-io.h
> ===================================================================
> --- gcov-io.h   (revision 194502)
> +++ gcov-io.h   (working copy)
> @@ -618,6 +618,28 @@ GCOV_LINKAGE gcov_position_t gcov_write_tag (gcov_
>  GCOV_LINKAGE void gcov_write_length (gcov_position_t /*position*/);
>  #endif
>
> +#if IN_GCOV <= 0 && !IN_LIBGCOV
> +/* Available in gcov-dump and the compiler.  */
> +
> +/* Number of data points in the working set summary array. Using 128
> +   provides information for at least every 1% increment of the total
> +   profile size. The last entry is hardwired to 99.9% of the total.  */
> +#define NUM_GCOV_WORKING_SETS 128
> +
> +/* Working set size statistics for a given percentage of the entire
> +   profile (sum_all from the counter summary).  */
> +typedef struct gcov_working_set_info
> +{
> +  /* Number of hot counters included in this working set.  */
> +  unsigned num_counters;
> +  /* Smallest counter included in this working set.  */
> +  gcov_type min_counter;
> +} gcov_working_set_t;
> +
> +GCOV_LINKAGE void compute_working_sets (const struct gcov_ctr_summary *summary,
> +                                        gcov_working_set_t *gcov_working_sets);
> +#endif
> +
>  #if IN_GCOV > 0
>  /* Available in gcov */
>  GCOV_LINKAGE time_t gcov_time (void);
> Index: profile.c
> ===================================================================
> --- profile.c   (revision 194502)
> +++ profile.c   (working copy)
> @@ -84,11 +84,6 @@ struct bb_info {
>
>  const struct gcov_ctr_summary *profile_info;
>
> -/* Number of data points in the working set summary array. Using 128
> -   provides information for at least every 1% increment of the total
> -   profile size. The last entry is hardwired to 99.9% of the total.  */
> -#define NUM_GCOV_WORKING_SETS 128
> -
>  /* Counter working set information computed from the current counter
>     summary. Not initialized unless profile_info summary is non-NULL.  */
>  static gcov_working_set_t gcov_working_sets[NUM_GCOV_WORKING_SETS];
> @@ -208,104 +203,16 @@ instrument_values (histogram_values values)
>     the minimum counter value in that working set.  */
>
>  void
> -compute_working_sets (void)
> +get_working_sets (void)
>  {
> -  gcov_type working_set_cum_values[NUM_GCOV_WORKING_SETS];
> -  gcov_type ws_cum_hotness_incr;
> -  gcov_type cum, tmp_cum;
> -  const gcov_bucket_type *histo_bucket;
> -  unsigned ws_ix, c_num, count, pctinc, pct;
> -  int h_ix;
> +  unsigned ws_ix, pctinc, pct;
>    gcov_working_set_t *ws_info;
>
>    if (!profile_info)
>      return;
>
> -  /* Compute the amount of sum_all that the cumulative hotness grows
> -     by in each successive working set entry, which depends on the
> -     number of working set entries.  */
> -  ws_cum_hotness_incr = profile_info->sum_all / NUM_GCOV_WORKING_SETS;
> +  compute_working_sets (profile_info, gcov_working_sets);
>
> -  /* Next fill in an array of the cumulative hotness values corresponding
> -     to each working set summary entry we are going to compute below.
> -     Skip 0% statistics, which can be extrapolated from the
> -     rest of the summary data.  */
> -  cum = ws_cum_hotness_incr;
> -  for (ws_ix = 0; ws_ix < NUM_GCOV_WORKING_SETS;
> -       ws_ix++, cum += ws_cum_hotness_incr)
> -    working_set_cum_values[ws_ix] = cum;
> -  /* The last summary entry is reserved for (roughly) 99.9% of the
> -     working set. Divide by 1024 so it becomes a shift, which gives
> -     almost exactly 99.9%.  */
> -  working_set_cum_values[NUM_GCOV_WORKING_SETS-1]
> -      = profile_info->sum_all - profile_info->sum_all/1024;
> -
> -  /* Next, walk through the histogram in decending order of hotness
> -     and compute the statistics for the working set summary array.
> -     As histogram entries are accumulated, we check to see which
> -     working set entries have had their expected cum_value reached
> -     and fill them in, walking the working set entries in increasing
> -     size of cum_value.  */
> -  ws_ix = 0; /* The current entry into the working set array.  */
> -  cum = 0; /* The current accumulated counter sum.  */
> -  count = 0; /* The current accumulated count of block counters.  */
> -  for (h_ix = GCOV_HISTOGRAM_SIZE - 1;
> -       h_ix >= 0 && ws_ix < NUM_GCOV_WORKING_SETS; h_ix--)
> -    {
> -      histo_bucket = &profile_info->histogram[h_ix];
> -
> -      /* If we haven't reached the required cumulative counter value for
> -         the current working set percentage, simply accumulate this histogram
> -         entry into the running sums and continue to the next histogram
> -         entry.  */
> -      if (cum + histo_bucket->cum_value < working_set_cum_values[ws_ix])
> -        {
> -          cum += histo_bucket->cum_value;
> -          count += histo_bucket->num_counters;
> -          continue;
> -        }
> -
> -      /* If adding the current histogram entry's cumulative counter value
> -         causes us to exceed the current working set size, then estimate
> -         how many of this histogram entry's counter values are required to
> -         reach the working set size, and fill in working set entries
> -         as we reach their expected cumulative value.  */
> -      for (c_num = 0, tmp_cum = cum;
> -           c_num < histo_bucket->num_counters && ws_ix < NUM_GCOV_WORKING_SETS;
> -           c_num++)
> -        {
> -          count++;
> -          /* If we haven't reached the last histogram entry counter, add
> -             in the minimum value again. This will underestimate the
> -             cumulative sum so far, because many of the counter values in this
> -             entry may have been larger than the minimum. We could add in the
> -             average value every time, but that would require an expensive
> -             divide operation.  */
> -          if (c_num + 1 < histo_bucket->num_counters)
> -            tmp_cum += histo_bucket->min_value;
> -          /* If we have reached the last histogram entry counter, then add
> -             in the entire cumulative value.  */
> -          else
> -            tmp_cum = cum + histo_bucket->cum_value;
> -
> -         /* Next walk through successive working set entries and fill in
> -            the statistics for any whose size we have reached by accumulating
> -            this histogram counter.  */
> -         while (ws_ix < NUM_GCOV_WORKING_SETS
> -                && tmp_cum >= working_set_cum_values[ws_ix])
> -            {
> -              gcov_working_sets[ws_ix].num_counters = count;
> -              gcov_working_sets[ws_ix].min_counter
> -                  = histo_bucket->min_value;
> -              ws_ix++;
> -            }
> -        }
> -      /* Finally, update the running cumulative value since we were
> -         using a temporary above.  */
> -      cum += histo_bucket->cum_value;
> -    }
> -  gcc_assert (ws_ix == NUM_GCOV_WORKING_SETS);
> -
>    if (dump_file)
>      {
>        fprintf (dump_file, "Counter working sets:\n");
> @@ -374,7 +281,7 @@ get_exec_counts (unsigned cfg_checksum, unsigned l
>    if (!counts)
>      return NULL;
>
> -  compute_working_sets();
> +  get_working_sets();
>
>    if (dump_file && profile_info)
>      fprintf(dump_file, "Merged %u profiles with maximal count %u.\n",
> Index: profile.h
> ===================================================================
> --- profile.h   (revision 194502)
> +++ profile.h   (working copy)
> @@ -47,6 +47,6 @@ extern gcov_type sum_edge_counts (vec<edge, va_gc>
>  extern void init_node_map (void);
>  extern void del_node_map (void);
>
> -extern void compute_working_sets (void);
> +extern void get_working_sets (void);
>
>  #endif /* PROFILE_H */
> Index: basic-block.h
> ===================================================================
> --- basic-block.h       (revision 194502)
> +++ basic-block.h       (working copy)
> @@ -88,16 +88,6 @@ enum cfg_edge_flags {
>     profile.c.  */
>  extern const struct gcov_ctr_summary *profile_info;
>
> -/* Working set size statistics for a given percentage of the entire
> -   profile (sum_all from the counter summary).  */
> -typedef struct gcov_working_set_info
> -{
> -  /* Number of hot counters included in this working set.  */
> -  unsigned num_counters;
> -  /* Smallest counter included in this working set.  */
> -  gcov_type min_counter;
> -} gcov_working_set_t;
> -
>  /* Structure to gather statistic about profile consistency, per pass.
>     An array of this structure, indexed by pass static number, is allocated
>     in passes.c.  The structure is defined here so that different CFG modes
> @@ -934,6 +924,7 @@ extern void rtl_profile_for_edge (edge);
>  extern void default_rtl_profile (void);
>
>  /* In profile.c.  */
> +typedef struct gcov_working_set_info gcov_working_set_t;
>  extern gcov_working_set_t *find_working_set(unsigned pct_times_10);
>
>  /* Check tha probability is sane.  */
> Index: gcov-dump.c
> ===================================================================
> --- gcov-dump.c (revision 194502)
> +++ gcov-dump.c (working copy)
> @@ -39,6 +39,8 @@ static void tag_arcs (const char *, unsigned, unsi
>  static void tag_lines (const char *, unsigned, unsigned);
>  static void tag_counters (const char *, unsigned, unsigned);
>  static void tag_summary (const char *, unsigned, unsigned);
> +static void dump_working_sets (const char *filename ATTRIBUTE_UNUSED,
> +                               const struct gcov_ctr_summary *summary);
>  extern int main (int, char **);
>
>  typedef struct tag_format
> @@ -50,6 +52,7 @@ typedef struct tag_format
>
>  static int flag_dump_contents = 0;
>  static int flag_dump_positions = 0;
> +static int flag_dump_working_sets = 0;
>
>  static const struct option options[] =
>  {
> @@ -57,6 +60,7 @@ static const struct option options[] =
>    { "version",              no_argument,       NULL, 'v' },
>    { "long",                 no_argument,       NULL, 'l' },
>    { "positions",           no_argument,       NULL, 'o' },
> +  { "working-sets",        no_argument,       NULL, 'w' },
>    { 0, 0, 0, 0 }
>  };
>
> @@ -94,7 +98,7 @@ main (int argc ATTRIBUTE_UNUSED, char **argv)
>
>    diagnostic_initialize (global_dc, 0);
>
> -  while ((opt = getopt_long (argc, argv, "hlpv", options, NULL)) != -1)
> +  while ((opt = getopt_long (argc, argv, "hlpvw", options, NULL)) != -1)
>      {
>        switch (opt)
>         {
> @@ -110,6 +114,9 @@ main (int argc ATTRIBUTE_UNUSED, char **argv)
>         case 'p':
>           flag_dump_positions = 1;
>           break;
> +       case 'w':
> +         flag_dump_working_sets = 1;
> +         break;
>         default:
>           fprintf (stderr, "unknown flag `%c'\n", opt);
>         }
> @@ -129,6 +136,7 @@ print_usage (void)
>    printf ("  -v, --version        Print version number\n");
>    printf ("  -l, --long           Dump record contents too\n");
>    printf ("  -p, --positions      Dump record positions\n");
> +  printf ("  -w, --working-sets   Dump working set computed from summary\n");
>  }
>
>  static void
> @@ -485,5 +493,39 @@ tag_summary (const char *filename ATTRIBUTE_UNUSED
>                (HOST_WIDEST_INT)histo_bucket->min_value,
>                (HOST_WIDEST_INT)histo_bucket->cum_value);
>          }
> +      if (flag_dump_working_sets)
> +        dump_working_sets (filename, &summary.ctrs[ix]);
>      }
>  }
> +
> +static void
> +dump_working_sets (const char *filename ATTRIBUTE_UNUSED,
> +                   const struct gcov_ctr_summary *summary)
> +{
> +  gcov_working_set_t gcov_working_sets[NUM_GCOV_WORKING_SETS];
> +  unsigned ws_ix, pctinc, pct;
> +  gcov_working_set_t *ws_info;
> +
> +  compute_working_sets (summary, gcov_working_sets);
> +
> +  printf ("\n");
> +  print_prefix (filename, 0, 0);
> +  printf ("\t\tcounter working sets:");
> +  /* Multiply the percentage by 100 to avoid float.  */
> +  pctinc = 100 * 100 / NUM_GCOV_WORKING_SETS;
> +  for (ws_ix = 0, pct = pctinc; ws_ix < NUM_GCOV_WORKING_SETS;
> +       ws_ix++, pct += pctinc)
> +    {
> +      if (ws_ix == NUM_GCOV_WORKING_SETS - 1)
> +        pct = 9990;
> +      ws_info = &gcov_working_sets[ws_ix];
> +      /* Print out the percentage using int arithmatic to avoid float.  */
> +      printf ("\n");
> +      print_prefix (filename, 0, 0);
> +      printf ("\t\t%u.%02u%%: num counts=%u, min counter="
> +               HOST_WIDEST_INT_PRINT_DEC,
> +               pct / 100, pct - (pct / 100 * 100),
> +               ws_info->num_counters,
> +               (HOST_WIDEST_INT)ws_info->min_counter);
> +    }
> +}
>
> --
> This patch is available for review at http://codereview.appspot.com/6940061
Jan Hubicka - April 3, 2013, 5:52 p.m.
> >
> > 2012-12-14  Teresa Johnson  <tejohnson@google.com>
> >
> >         * lto-cgraph.c (input_symtab): Replace call to compute_working_sets
> >         to get_working_sets.
> >         * gcov-io.c (compute_working_sets): Moved most of body of old
> >         compute_working_sets here from profile.c.
> >         * gcov-io.h (NUM_GCOV_WORKING_SETS): Moved here from profile.c.
> >         (gcov_working_set_t): Moved typedef here from basic-block.h
> >         (compute_working_set): Declare.
> >         * profile.c (NUM_GCOV_WORKING_SETS): Moved to gcov-io.h.
> >         (get_working_sets): Renamed from compute_working_set,
> >         replace most of body with call to new compute_working_sets.
> >         (get_exec_counts): Replace call to compute_working_sets
> >         to get_working_sets.
> >         * profile.h (get_working_sets): Renamed from
> >         compute_working_set.
> >         * basic-block.h (gcov_working_set_t): Moved to gcov-io.h.
> >         * gcov-dump.c (dump_working_sets): New function.

Looks like good idea.  We probaby couold extend gcov-dump to also compute the real
histogram across multiple input files and compare these two.

Patch is OK.
Thanks,
Honza
Teresa Johnson - April 3, 2013, 8:54 p.m.
On Wed, Apr 3, 2013 at 10:52 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> >
>> > 2012-12-14  Teresa Johnson  <tejohnson@google.com>
>> >
>> >         * lto-cgraph.c (input_symtab): Replace call to compute_working_sets
>> >         to get_working_sets.
>> >         * gcov-io.c (compute_working_sets): Moved most of body of old
>> >         compute_working_sets here from profile.c.
>> >         * gcov-io.h (NUM_GCOV_WORKING_SETS): Moved here from profile.c.
>> >         (gcov_working_set_t): Moved typedef here from basic-block.h
>> >         (compute_working_set): Declare.
>> >         * profile.c (NUM_GCOV_WORKING_SETS): Moved to gcov-io.h.
>> >         (get_working_sets): Renamed from compute_working_set,
>> >         replace most of body with call to new compute_working_sets.
>> >         (get_exec_counts): Replace call to compute_working_sets
>> >         to get_working_sets.
>> >         * profile.h (get_working_sets): Renamed from
>> >         compute_working_set.
>> >         * basic-block.h (gcov_working_set_t): Moved to gcov-io.h.
>> >         * gcov-dump.c (dump_working_sets): New function.
>
> Looks like good idea.  We probaby couold extend gcov-dump to also compute the real
> histogram across multiple input files and compare these two.

cc'ing Rong Xu - he has a tool under development that he plans to
contribute upstream which does both offline merging of different sets
of profile data, and full, exact recomputation of the histogram. I'm
using an early version of his tool right now to compare the accuracy
of the libgcov-merged histogram to the exactly merged histogram (I'll
update the thread on that hopefully later today).

>
> Patch is OK.

Thanks, committed.

Teresa

> Thanks,
> Honza



--
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413

Patch

Index: lto-cgraph.c
===================================================================
--- lto-cgraph.c	(revision 194502)
+++ lto-cgraph.c	(working copy)
@@ -1457,7 +1457,7 @@  input_symtab (void)
     }
 
   merge_profile_summaries (file_data_vec);
-  compute_working_sets ();
+  get_working_sets ();
 
 
   /* Clear out the aux field that was used to store enough state to
Index: gcov-io.c
===================================================================
--- gcov-io.c	(revision 194502)
+++ gcov-io.c	(working copy)
@@ -806,3 +806,110 @@  static void gcov_histogram_merge (gcov_bucket_type
   memcpy(tgt_histo, tmp_histo, sizeof (gcov_bucket_type) * GCOV_HISTOGRAM_SIZE);
 }
 #endif /* !IN_GCOV */
+
+/* This is used by gcov-dump (IN_GCOV == -1) and in the compiler
+   (!IN_GCOV && !IN_LIBGCOV).  */
+#if IN_GCOV <= 0 && !IN_LIBGCOV
+/* Compute the working set information from the counter histogram in
+   the profile summary. This is an array of information corresponding to a
+   range of percentages of the total execution count (sum_all), and includes
+   the number of counters required to cover that working set percentage and
+   the minimum counter value in that working set.  */
+
+GCOV_LINKAGE void
+compute_working_sets (const struct gcov_ctr_summary *summary,
+                      gcov_working_set_t *gcov_working_sets)
+{
+  gcov_type working_set_cum_values[NUM_GCOV_WORKING_SETS];
+  gcov_type ws_cum_hotness_incr;
+  gcov_type cum, tmp_cum;
+  const gcov_bucket_type *histo_bucket;
+  unsigned ws_ix, c_num, count;
+  int h_ix;
+
+  /* Compute the amount of sum_all that the cumulative hotness grows
+     by in each successive working set entry, which depends on the
+     number of working set entries.  */
+  ws_cum_hotness_incr = summary->sum_all / NUM_GCOV_WORKING_SETS;
+
+  /* Next fill in an array of the cumulative hotness values corresponding
+     to each working set summary entry we are going to compute below.
+     Skip 0% statistics, which can be extrapolated from the
+     rest of the summary data.  */
+  cum = ws_cum_hotness_incr;
+  for (ws_ix = 0; ws_ix < NUM_GCOV_WORKING_SETS;
+       ws_ix++, cum += ws_cum_hotness_incr)
+    working_set_cum_values[ws_ix] = cum;
+  /* The last summary entry is reserved for (roughly) 99.9% of the
+     working set. Divide by 1024 so it becomes a shift, which gives
+     almost exactly 99.9%.  */
+  working_set_cum_values[NUM_GCOV_WORKING_SETS-1]
+      = summary->sum_all - summary->sum_all/1024;
+
+  /* Next, walk through the histogram in decending order of hotness
+     and compute the statistics for the working set summary array.
+     As histogram entries are accumulated, we check to see which
+     working set entries have had their expected cum_value reached
+     and fill them in, walking the working set entries in increasing
+     size of cum_value.  */
+  ws_ix = 0; /* The current entry into the working set array.  */
+  cum = 0; /* The current accumulated counter sum.  */
+  count = 0; /* The current accumulated count of block counters.  */
+  for (h_ix = GCOV_HISTOGRAM_SIZE - 1;
+       h_ix >= 0 && ws_ix < NUM_GCOV_WORKING_SETS; h_ix--)
+    {
+      histo_bucket = &summary->histogram[h_ix];
+
+      /* If we haven't reached the required cumulative counter value for
+         the current working set percentage, simply accumulate this histogram
+         entry into the running sums and continue to the next histogram
+         entry.  */
+      if (cum + histo_bucket->cum_value < working_set_cum_values[ws_ix])
+        {
+          cum += histo_bucket->cum_value;
+          count += histo_bucket->num_counters;
+          continue;
+        }
+
+      /* If adding the current histogram entry's cumulative counter value
+         causes us to exceed the current working set size, then estimate
+         how many of this histogram entry's counter values are required to
+         reach the working set size, and fill in working set entries
+         as we reach their expected cumulative value.  */
+      for (c_num = 0, tmp_cum = cum;
+           c_num < histo_bucket->num_counters && ws_ix < NUM_GCOV_WORKING_SETS;
+           c_num++)
+        {
+          count++;
+          /* If we haven't reached the last histogram entry counter, add
+             in the minimum value again. This will underestimate the
+             cumulative sum so far, because many of the counter values in this
+             entry may have been larger than the minimum. We could add in the
+             average value every time, but that would require an expensive
+             divide operation.  */
+          if (c_num + 1 < histo_bucket->num_counters)
+            tmp_cum += histo_bucket->min_value;
+          /* If we have reached the last histogram entry counter, then add
+             in the entire cumulative value.  */
+          else
+            tmp_cum = cum + histo_bucket->cum_value;
+
+	  /* Next walk through successive working set entries and fill in
+	     the statistics for any whose size we have reached by accumulating
+	     this histogram counter.  */
+	  while (ws_ix < NUM_GCOV_WORKING_SETS
+		 && tmp_cum >= working_set_cum_values[ws_ix])
+            {
+              gcov_working_sets[ws_ix].num_counters = count;
+              gcov_working_sets[ws_ix].min_counter
+                  = histo_bucket->min_value;
+              ws_ix++;
+            }
+        }
+      /* Finally, update the running cumulative value since we were
+         using a temporary above.  */
+      cum += histo_bucket->cum_value;
+    }
+  gcc_assert (ws_ix == NUM_GCOV_WORKING_SETS);
+}
+#endif /* IN_GCOV <= 0 && !IN_LIBGCOV */
Index: gcov-io.h
===================================================================
--- gcov-io.h	(revision 194502)
+++ gcov-io.h	(working copy)
@@ -618,6 +618,28 @@  GCOV_LINKAGE gcov_position_t gcov_write_tag (gcov_
 GCOV_LINKAGE void gcov_write_length (gcov_position_t /*position*/);
 #endif
 
+#if IN_GCOV <= 0 && !IN_LIBGCOV
+/* Available in gcov-dump and the compiler.  */
+
+/* Number of data points in the working set summary array. Using 128
+   provides information for at least every 1% increment of the total
+   profile size. The last entry is hardwired to 99.9% of the total.  */
+#define NUM_GCOV_WORKING_SETS 128
+
+/* Working set size statistics for a given percentage of the entire
+   profile (sum_all from the counter summary).  */
+typedef struct gcov_working_set_info
+{
+  /* Number of hot counters included in this working set.  */
+  unsigned num_counters;
+  /* Smallest counter included in this working set.  */
+  gcov_type min_counter;
+} gcov_working_set_t;
+
+GCOV_LINKAGE void compute_working_sets (const struct gcov_ctr_summary *summary,
+                                        gcov_working_set_t *gcov_working_sets);
+#endif
+
 #if IN_GCOV > 0
 /* Available in gcov */
 GCOV_LINKAGE time_t gcov_time (void);
Index: profile.c
===================================================================
--- profile.c	(revision 194502)
+++ profile.c	(working copy)
@@ -84,11 +84,6 @@  struct bb_info {
 
 const struct gcov_ctr_summary *profile_info;
 
-/* Number of data points in the working set summary array. Using 128
-   provides information for at least every 1% increment of the total
-   profile size. The last entry is hardwired to 99.9% of the total.  */
-#define NUM_GCOV_WORKING_SETS 128
-
 /* Counter working set information computed from the current counter
    summary. Not initialized unless profile_info summary is non-NULL.  */
 static gcov_working_set_t gcov_working_sets[NUM_GCOV_WORKING_SETS];
@@ -208,104 +203,16 @@  instrument_values (histogram_values values)
    the minimum counter value in that working set.  */
 
 void
-compute_working_sets (void)
+get_working_sets (void)
 {
-  gcov_type working_set_cum_values[NUM_GCOV_WORKING_SETS];
-  gcov_type ws_cum_hotness_incr;
-  gcov_type cum, tmp_cum;
-  const gcov_bucket_type *histo_bucket;
-  unsigned ws_ix, c_num, count, pctinc, pct;
-  int h_ix;
+  unsigned ws_ix, pctinc, pct;
   gcov_working_set_t *ws_info;
 
   if (!profile_info)
     return;
 
-  /* Compute the amount of sum_all that the cumulative hotness grows
-     by in each successive working set entry, which depends on the
-     number of working set entries.  */
-  ws_cum_hotness_incr = profile_info->sum_all / NUM_GCOV_WORKING_SETS;
+  compute_working_sets (profile_info, gcov_working_sets);
 
-  /* Next fill in an array of the cumulative hotness values corresponding
-     to each working set summary entry we are going to compute below.
-     Skip 0% statistics, which can be extrapolated from the
-     rest of the summary data.  */
-  cum = ws_cum_hotness_incr;
-  for (ws_ix = 0; ws_ix < NUM_GCOV_WORKING_SETS;
-       ws_ix++, cum += ws_cum_hotness_incr)
-    working_set_cum_values[ws_ix] = cum;
-  /* The last summary entry is reserved for (roughly) 99.9% of the
-     working set. Divide by 1024 so it becomes a shift, which gives
-     almost exactly 99.9%.  */
-  working_set_cum_values[NUM_GCOV_WORKING_SETS-1]
-      = profile_info->sum_all - profile_info->sum_all/1024;
-
-  /* Next, walk through the histogram in decending order of hotness
-     and compute the statistics for the working set summary array.
-     As histogram entries are accumulated, we check to see which
-     working set entries have had their expected cum_value reached
-     and fill them in, walking the working set entries in increasing
-     size of cum_value.  */
-  ws_ix = 0; /* The current entry into the working set array.  */
-  cum = 0; /* The current accumulated counter sum.  */
-  count = 0; /* The current accumulated count of block counters.  */
-  for (h_ix = GCOV_HISTOGRAM_SIZE - 1;
-       h_ix >= 0 && ws_ix < NUM_GCOV_WORKING_SETS; h_ix--)
-    {
-      histo_bucket = &profile_info->histogram[h_ix];
-
-      /* If we haven't reached the required cumulative counter value for
-         the current working set percentage, simply accumulate this histogram
-         entry into the running sums and continue to the next histogram
-         entry.  */
-      if (cum + histo_bucket->cum_value < working_set_cum_values[ws_ix])
-        {
-          cum += histo_bucket->cum_value;
-          count += histo_bucket->num_counters;
-          continue;
-        }
-
-      /* If adding the current histogram entry's cumulative counter value
-         causes us to exceed the current working set size, then estimate
-         how many of this histogram entry's counter values are required to
-         reach the working set size, and fill in working set entries
-         as we reach their expected cumulative value.  */
-      for (c_num = 0, tmp_cum = cum;
-           c_num < histo_bucket->num_counters && ws_ix < NUM_GCOV_WORKING_SETS;
-           c_num++)
-        {
-          count++;
-          /* If we haven't reached the last histogram entry counter, add
-             in the minimum value again. This will underestimate the
-             cumulative sum so far, because many of the counter values in this
-             entry may have been larger than the minimum. We could add in the
-             average value every time, but that would require an expensive
-             divide operation.  */
-          if (c_num + 1 < histo_bucket->num_counters)
-            tmp_cum += histo_bucket->min_value;
-          /* If we have reached the last histogram entry counter, then add
-             in the entire cumulative value.  */
-          else
-            tmp_cum = cum + histo_bucket->cum_value;
-
-	  /* Next walk through successive working set entries and fill in
-	     the statistics for any whose size we have reached by accumulating
-	     this histogram counter.  */
-	  while (ws_ix < NUM_GCOV_WORKING_SETS
-		 && tmp_cum >= working_set_cum_values[ws_ix])
-            {
-              gcov_working_sets[ws_ix].num_counters = count;
-              gcov_working_sets[ws_ix].min_counter
-                  = histo_bucket->min_value;
-              ws_ix++;
-            }
-        }
-      /* Finally, update the running cumulative value since we were
-         using a temporary above.  */
-      cum += histo_bucket->cum_value;
-    }
-  gcc_assert (ws_ix == NUM_GCOV_WORKING_SETS);
-
   if (dump_file)
     {
       fprintf (dump_file, "Counter working sets:\n");
@@ -374,7 +281,7 @@  get_exec_counts (unsigned cfg_checksum, unsigned l
   if (!counts)
     return NULL;
 
-  compute_working_sets();
+  get_working_sets();
 
   if (dump_file && profile_info)
     fprintf(dump_file, "Merged %u profiles with maximal count %u.\n",
Index: profile.h
===================================================================
--- profile.h	(revision 194502)
+++ profile.h	(working copy)
@@ -47,6 +47,6 @@  extern gcov_type sum_edge_counts (vec<edge, va_gc>
 extern void init_node_map (void);
 extern void del_node_map (void);
 
-extern void compute_working_sets (void);
+extern void get_working_sets (void);
 
 #endif /* PROFILE_H */
Index: basic-block.h
===================================================================
--- basic-block.h	(revision 194502)
+++ basic-block.h	(working copy)
@@ -88,16 +88,6 @@  enum cfg_edge_flags {
    profile.c.  */
 extern const struct gcov_ctr_summary *profile_info;
 
-/* Working set size statistics for a given percentage of the entire
-   profile (sum_all from the counter summary).  */
-typedef struct gcov_working_set_info
-{
-  /* Number of hot counters included in this working set.  */
-  unsigned num_counters;
-  /* Smallest counter included in this working set.  */
-  gcov_type min_counter;
-} gcov_working_set_t;
-
 /* Structure to gather statistic about profile consistency, per pass.
    An array of this structure, indexed by pass static number, is allocated
    in passes.c.  The structure is defined here so that different CFG modes
@@ -934,6 +924,7 @@  extern void rtl_profile_for_edge (edge);
 extern void default_rtl_profile (void);
 
 /* In profile.c.  */
+typedef struct gcov_working_set_info gcov_working_set_t;
 extern gcov_working_set_t *find_working_set(unsigned pct_times_10);
 
 /* Check tha probability is sane.  */
Index: gcov-dump.c
===================================================================
--- gcov-dump.c	(revision 194502)
+++ gcov-dump.c	(working copy)
@@ -39,6 +39,8 @@  static void tag_arcs (const char *, unsigned, unsi
 static void tag_lines (const char *, unsigned, unsigned);
 static void tag_counters (const char *, unsigned, unsigned);
 static void tag_summary (const char *, unsigned, unsigned);
+static void dump_working_sets (const char *filename ATTRIBUTE_UNUSED,
+                               const struct gcov_ctr_summary *summary);
 extern int main (int, char **);
 
 typedef struct tag_format
@@ -50,6 +52,7 @@  typedef struct tag_format
 
 static int flag_dump_contents = 0;
 static int flag_dump_positions = 0;
+static int flag_dump_working_sets = 0;
 
 static const struct option options[] =
 {
@@ -57,6 +60,7 @@  static const struct option options[] =
   { "version",              no_argument,       NULL, 'v' },
   { "long",                 no_argument,       NULL, 'l' },
   { "positions",	    no_argument,       NULL, 'o' },
+  { "working-sets",	    no_argument,       NULL, 'w' },
   { 0, 0, 0, 0 }
 };
 
@@ -94,7 +98,7 @@  main (int argc ATTRIBUTE_UNUSED, char **argv)
 
   diagnostic_initialize (global_dc, 0);
 
-  while ((opt = getopt_long (argc, argv, "hlpv", options, NULL)) != -1)
+  while ((opt = getopt_long (argc, argv, "hlpvw", options, NULL)) != -1)
     {
       switch (opt)
 	{
@@ -110,6 +114,9 @@  main (int argc ATTRIBUTE_UNUSED, char **argv)
 	case 'p':
 	  flag_dump_positions = 1;
 	  break;
+	case 'w':
+	  flag_dump_working_sets = 1;
+	  break;
 	default:
 	  fprintf (stderr, "unknown flag `%c'\n", opt);
 	}
@@ -129,6 +136,7 @@  print_usage (void)
   printf ("  -v, --version        Print version number\n");
   printf ("  -l, --long           Dump record contents too\n");
   printf ("  -p, --positions      Dump record positions\n");
+  printf ("  -w, --working-sets   Dump working set computed from summary\n");
 }
 
 static void
@@ -485,5 +493,39 @@  tag_summary (const char *filename ATTRIBUTE_UNUSED
               (HOST_WIDEST_INT)histo_bucket->min_value,
               (HOST_WIDEST_INT)histo_bucket->cum_value);
         }
+      if (flag_dump_working_sets)
+        dump_working_sets (filename, &summary.ctrs[ix]);
     }
 }
+
+static void
+dump_working_sets (const char *filename ATTRIBUTE_UNUSED,
+                   const struct gcov_ctr_summary *summary)
+{
+  gcov_working_set_t gcov_working_sets[NUM_GCOV_WORKING_SETS];
+  unsigned ws_ix, pctinc, pct;
+  gcov_working_set_t *ws_info;
+
+  compute_working_sets (summary, gcov_working_sets);
+
+  printf ("\n");
+  print_prefix (filename, 0, 0);
+  printf ("\t\tcounter working sets:");
+  /* Multiply the percentage by 100 to avoid float.  */
+  pctinc = 100 * 100 / NUM_GCOV_WORKING_SETS;
+  for (ws_ix = 0, pct = pctinc; ws_ix < NUM_GCOV_WORKING_SETS;
+       ws_ix++, pct += pctinc)
+    {
+      if (ws_ix == NUM_GCOV_WORKING_SETS - 1)
+        pct = 9990;
+      ws_info = &gcov_working_sets[ws_ix];
+      /* Print out the percentage using int arithmatic to avoid float.  */
+      printf ("\n");
+      print_prefix (filename, 0, 0);
+      printf ("\t\t%u.%02u%%: num counts=%u, min counter="
+               HOST_WIDEST_INT_PRINT_DEC,
+               pct / 100, pct - (pct / 100 * 100),
+               ws_info->num_counters,
+               (HOST_WIDEST_INT)ws_info->min_counter);
+    }
+}