Re: [PATCH] Compute and emit working set information from gcov-dump (issue6940061)

[Teresa Johnson <tejohnson at google dot com>]

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



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